nasm源代码解析 SAA 与 RAA部分(上)(08.5.11)

Nasm源代码解析     SAA算法分析

SAA是用来顺序存取操作的，这部分我们分成两部分分析：

1.数据结构和算法分析

2.给出代码注释

数据结构和算法分析

SAA是一个链表，结构如下：

/*
 * Routines to manage a dynamic sequential-access array, under the
 * same restriction on maximum mallocable block. This array may be
 * written to in two ways: a contiguous chunk can be reserved of a
 * given size, and a pointer returned, or single-byte data may be
 * written. The array can also be read back in the same two ways:
 * as a series of big byte-data blocks or as a list of structures
 * of a given size.
 */

/**//* start:该节点的起始地址
 * end :指向该链表的最有一个单元
 * rptr :指向要读取的数据的节点
 * rpos :节点中的偏移
 * 个人观点:这个数据结构里面有很多指针和long（end,rptr,rpos,elem_len）只在一个节点中用到，是 * 否可以把他单独定义成一个结构体或者采用其他的更好方法来节省空间
 */
struct SAA ...{
    /**//*
     * members `end' and `elem_len' are only valid in first link in
     * list; `rptr' and `rpos' are used for reading
     */
    struct SAA *next, *end, *rptr;
    long elem_len, length, posn, start, rpos;
    char *data;
};

#define SAA_MAXLEN 8192

struct SAA *saa_init(long elem_len)
...{
    struct SAA *s;

    /**//* 判断元素的的长度是否超过了规定的最大值 */
    if (elem_len > SAA_MAXLEN)
        nasm_malloc_error(ERR_PANIC | ERR_NOFILE,
                          "SAA with huge elements");

    s = nasm_malloc(sizeof(struct SAA));
    s->posn = s->start = 0L;
    s->elem_len = elem_len;
    s->length = SAA_MAXLEN - (SAA_MAXLEN % elem_len); /**//*s->length 是 elem_len的倍数，为何？*/
    s->data = nasm_malloc(s->length);
    s->next = NULL;
    s->end = s;

    return s;
}

/**//* 摧毁struct SAA链表 */
void saa_free(struct SAA *s)
...{
    struct SAA *t;

    while (s) ...{
        t = s->next;
        nasm_free(s->data);
        nasm_free(s);
        s = t;
    }
}

/**//* 进行添加一个s->elem_len长度的数据的操作（其实是插入一个结构体），但实际并未真正插入这个数据
 * 返回插入数据的插入地址 */
void *saa_wstruct(struct SAA *s)
...{
    void *p;

    /**//* 如果存储不下数据，则另外建立一个节点 */
    if (s->end->length - s->end->posn < s->elem_len) ...{
        s->end->next = nasm_malloc(sizeof(struct SAA));
        s->end->next->start = s->end->start + s->end->posn; /**//* 该节点的起始地址 */
        s->end = s->end->next;
        s->end->length = s->length;
        s->end->next = NULL;
        s->end->posn = 0L;
        s->end->data = nasm_malloc(s->length);
    }

    p = s->end->data + s->end->posn; /**//* p:指向数据的起始地址 */
    s->end->posn += s->elem_len; /**//* 该节点存储有多少数据 */
    return p;
}

/**//* 插入一个数据块。跟saa_wstruct有一段相似的代码，是否可以考虑抽出来单独成一个函数？ */
void saa_wbytes(struct SAA *s, const void *data, long len)
...{
    const char *d = data;

    while (len > 0) ...{
        long l = s->end->length - s->end->posn;
        if (l > len)
            l = len;
        if (l > 0) ...{
            if (d) ...{
                memcpy(s->end->data + s->end->posn, d, l);
                d += l;
            } else
                memset(s->end->data + s->end->posn, 0, l);
            s->end->posn += l;
            len -= l;
        }
        if (len > 0) ...{
            s->end->next = nasm_malloc(sizeof(struct SAA));
            s->end->next->start = s->end->start + s->end->posn;
            s->end = s->end->next;
            s->end->length = s->length;
            s->end->next = NULL;
            s->end->posn = 0L;
            s->end->data = nasm_malloc(s->length);
        }
    }
}

/**//* 重置读操作指针 */
void saa_rewind(struct SAA *s)
...{
    s->rptr = s;
    s->rpos = 0L;
}

/**//* 读取结构体 */
void *saa_rstruct(struct SAA *s)
...{
    void *p;

    /**//* 出错检查 */
    if (!s->rptr)
        return NULL;

    if (s->rptr->posn - s->rpos < s->elem_len) ...{
        s->rptr = s->rptr->next;
        if (!s->rptr)
            return NULL; /**//* end of array */
        s->rpos = 0L;
    }

    p = s->rptr->data + s->rpos;
    s->rpos