Nasm源代码解析 预处理器--总结(八)

1．  内存块操作

数据结构和算法：

数据结构是链表

当插入一个block的时候，将该块插入到链表的结尾(思考：是否可以考虑插入到链表头呢？这样貌似对程序没有影响啊，而且大大提高了效率。)

注意:删除block链表：由于头指针的静态变量，不能删除

/*
 * Tokens are allocated in blocks to improve speed
 */

struct Blocks 
{
    Blocks *next;
    void *chunk;
};

static Blocks blocks = { NULL, NULL };
static void *new_Block(size_t size);
static void delete_Blocks(void);

/*
 * this function allocates a new managed block of memory and
 * returns a pointer to the block.  The managed blocks are 
 * deleted only all at once by the delete_Blocks function.
 */
static void *new_Block(size_t size)
{
    Blocks *b = &blocks;

/* first, get to the end of the linked list */
/* 个人观点：可以建立一个指向链表结尾的指针，这样就无需循环获取放在链表尾部的指针了，可以* 大大提高效率 */
    while (b->next)
        b = b->next;

    /* now allocate the requested chunk */
    b->chunk = nasm_malloc(size);

    /* now allocate a new block for the next request */
    b->next = nasm_malloc(sizeof(Blocks));

    /* and initialize the contents of the new block */
    b->next->next = NULL;
    b->next->chunk = NULL;
    return b->chunk;
}

/*
 * this function deletes all managed blocks of memory
 */
static void delete_Blocks(void)
{
    Blocks *a, *b = &blocks;

    /* 
     * keep in mind that the first block, pointed to by blocks
     * is a static and not dynamically allocated, so we don't 
     * free it.
     */
    while (b) {
        if (b->chunk)
            nasm_free(b->chunk);
        a = b;
        b = b->next;
        if (a != &blocks)
            nasm_free(a);
    }
}

2．  Token存储功能操作

Token功能是以以上的块操作为基础开发出来的:

数据结构:链表

#define TOKEN_BLOCKSIZE 4096
static Token *freeTokens = NULL;                        /* 空闲的token链表头 */
struct Token 
{
    Token *next;
    char *text;
    SMacro *mac;                /* associated macro for TOK_SMAC_END */
    int type;
};

enum {
    TOK_WHITESPACE = 1, TOK_COMMENT, TOK_ID, TOK_PREPROC_ID, TOK_STRING,
    TOK_NUMBER, TOK_SMAC_END, TOK_OTHER, TOK_SMAC_PARAM,
    TOK_INTERNAL_STRING
};

/*
 *  this function creates a new Token and passes a pointer to it 
 *  back to the caller.  It sets the type and text elements, and
 *  also the mac and next elements to NULL.
 */
static Token *new_Token(Token * next, int type, char *text, int txtlen)
{
    Token *t;
    int i;

	/* 先获取一个大块，然后在这个大块内存中建立一个链表，freeTokens指向空闲链表的头指针 */
    if (freeTokens == NULL) {
        freeTokens = (Token *) new_Block(TOKEN_BLOCKSIZE * sizeof(Token));
        for (i = 0; i < TOKEN_BLOCKSIZE - 1; i++)
            freeTokens[i].next = &freeTokens[i + 1];
        freeTokens[i].next = NULL;
    }

	/* 取出一个空闲块 */
    t = freeTokens;
    freeTokens = t->next;

	/* 初始化 t */
    t->next = next;
    t->mac = NULL;
    t->type = type;

    /* 存放token */
    if (type == TOK_WHITESPACE || text == NULL) {
        t->text = NULL;
    } else {
        if (txtlen == 0)
            txtlen = strlen(text);
        t->text = nasm_malloc(1 + txtlen);
        strncpy(t->text, text, txtlen);
        t->text[txtlen] = '\0';
    }
    return t;
}

/* 将空闲的内存块插入freeTokens中 */
static Token *delete_Token(Token * t)
{
    Token *next = t->next;
    nasm_free(t->text);
    t->next = freeTokens;
    freeTokens = t;
    return next;
}

3.在static Token *tokenise(char *line)函数中，有一个函数链表操作（其实在Nasm中，经常采用这种方式创建链表的方式），这个链表操作值得我们学习，现在我将相关代码抽出来：

Token *list = NULL;
Token *t, **tail = &list;                           /* list是链表头,tail总是指向链表尾 */     
*tail = t = new_Token(NULL, type, line, p - line); /* 将 t 插入到 list 链表中 */
 tail = &t->next;