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

                     Nasm源代码解析     RAA算法分析

RAA是用来单个字节存储和读取的，这部分我们分成两部分分析：

1.数据结构和算法分析

2.给出代码注释                    

数据结构和算法分析

RAA给出了4个操作：

l  初始化节点(包括叶子节点和分支节点)；

l  读取数据

l  插入数据

l  删除整棵树

该程序其实是一棵树，一开始先建立一个叶子节点：

当要向这颗树插入数据的时候(所有的数据都只能放在layers = 0的节点)，有三种情况

l  直接插入

l  建立一个节点，再插入

l  需要在多建立一个层次

下面重点解释第2，第3中情况:

l  建立一个节点，再插入

    

假设是要在上面这棵树上插入一个数据。建立一个节点再插入数据可能出现这样情况：

l  需要在多建立一个层次

假设是要在上面这棵树上插入一个数据。需要多建立一层在插入数据是的情况:

代码注释

/*
 * Routines to manage a dynamic random access array of longs which
 * may grow in size to be more than the largest single malloc'able
 * chunk.
 */

#defineRAA_BLKSIZE 4096 /* this many longs allocated at once */
#defineRAA_LAYERSIZE 1024 /* this many _pointers_ allocated */

typedefstructRAA RAA;
typedefunionRAA_UNION RAA_UNION;
typedefstructRAA_LEAF RAA_LEAF;
typedefstructRAA_BRANCH RAA_BRANCH;

/*叶子或者分支*/
structRAA {
    /*
     * Number of layers below this one to get to the real data. 0
     * means this structure is a leaf, holding RAA_BLKSIZE real
     * data items; 1 and above mean it's a branch, holding
     * RAA_LAYERSIZE pointers to the next level branch or leaf
     * structures.
     */
    intlayers;
    /*
     * Number of real data items spanned by one position in the
     * `data' array at this level. This number is 1, trivially, for
     * a leaf (level 0): for a level 1 branch it should be
     * RAA_BLKSIZE, and for a level 2 branch it's
     * RAA_LAYERSIZE*RAA_BLKSIZE.
     */
    longstepsize;
    unionRAA_UNION {
        structRAA_LEAF {
            longdata[RAA_BLKSIZE];
        } l;
        structRAA_BRANCH {
            structRAA *data[RAA_LAYERSIZE];
        } b;
    } u;
};

structRAA *raa_init(void);
voidraa_free(structRAA *);
longraa_read(structRAA *, long);
structRAA *raa_write(structRAA *r, longposn, longvalue);
/*计算叶子节点所占的内存大小*/
#defineLEAFSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_LEAF))
/*计算树枝节点所占的内存大小*/
#defineBRANCHSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_BRANCH))
/*判断该节点存储数据的大小*/
#defineLAYERSIZ(r) ( (r)->layers==0 ? RAA_BLKSIZE : RAA_LAYERSIZE )
/*建立并初始化struct RAA item */
staticstructRAA *real_raa_init(intlayers)
{
    structRAA *r;
    inti;

    if(layers == 0) { /*建立叶子节点*/
        r = nasm_malloc(LEAFSIZ);
        r->layers = 0;
        memset(r->u.l.data, 0, sizeof(r->u.l.data));
        r->stepsize = 1L; /* 子结点中，r->stepsize = 1，即每个存储单元可以存储1个long */
    } else{ /* 建立树枝节点*/
        r = nasm_malloc(BRANCHSIZ);
        r->layers = layers;
        for(i = 0; i < RAA_LAYERSIZE; i++)
            r->u.b.data[i] = NULL;
        r->stepsize = RAA_BLKSIZE; /* 该节点的每个存储单元可以存储多大的数据*/
        while(--layers) /* r->stepsize = (RAA_LAYERSIZE ^ (layers - 1)) * RAA_BLKSIZE */
            r->stepsize *= RAA_LAYERSIZE;
    }
    returnr;
}

/*初始化叶子*/
structRAA *raa_init(void)
{
    returnreal_raa_init(0);
}

/*删除struct RAA生成的树*/
voidraa_free(structRAA *r)
{
    if(r->layers == 0)
        nasm_free(r);
    else{
        structRAA **p;
        for(p = r->u.b.data; p - r->u.b.data < RAA_LAYERSIZE; p++)
            if(*p)
                raa_free(*p);
    }
}

/*以下程序也可以用递归实现，不过用迭代更好*/
longraa_read(structRAA *r, longposn)
{
/*计算要读取的数据的地址是否超出了该节点的所能容纳的范围*/
if(posn >= r->stepsize * LAYERSIZ(r))
        return0; /* Return 0 for undefined entries */
    while(r->layers > 0) {
        ldiv_t l;
        l = ldiv(posn, r->stepsize);
        r = r->u.b.data[l.quot]; /* 数据在第几个存储单元*/
        posn = l.rem;
        if(!r)
            return0; /* Return 0 for undefined entries */
    }
    returnr->u.l.data[posn];
}

structRAA *raa_write(structRAA *r, longposn, longvalue)
{
    structRAA *result;

    if(posn < 0)
        nasm_malloc_error(ERR_PANIC, "negative position in raa_write");

    while(r->stepsize * LAYERSIZ(r) <= posn) {
        /*
         * Must add a layer.
         */
        structRAA *s;
        inti;

        s = nasm_malloc(BRANCHSIZ);
        for(i = 0; i < RAA_LAYERSIZE; i++)
            s->u.b.data[i] = NULL;
        s->layers = r->layers + 1;
        s->stepsize = LAYERSIZ(r) * r->stepsize;
        s->u.b.data[0] = r;
        r = s;
    }

    result = r;

    /* 插入数据的实际操作*/
    while(r->layers > 0) {
        ldiv_t l;
        structRAA **s;
        l = ldiv(posn, r->stepsize);
        s = &r->u.b.data[l.quot];
        if(!*s)
            *s = real_raa_init(r->layers - 1);
        r = *s;
        posn = l.rem;
    }

    r->u.l.data[posn] = value;

    returnresult;
}