Chinaunix首页 | 论坛 | 博客
  • 博客访问: 930033
  • 博文数量: 197
  • 博客积分: 4141
  • 博客等级: 中将
  • 技术积分: 2293
  • 用 户 组: 普通用户
  • 注册时间: 2009-03-21 20:04
  • 认证徽章:
文章存档

2019年(32)

2016年(1)

2014年(16)

2011年(8)

2010年(25)

2009年(115)

分类: 嵌入式

2019-02-19 17:18:23

                     Nasm源代码解析     RAA算法分析

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

1.数据结构和算法分析

2.给出代码注释                    

数据结构和算法分析

RAA给出了4个操作:

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

l  读取数据

l  插入数据

l  删除整棵树

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

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

l  直接插入

l  建立一个节点,再插入

l  需要在多建立一个层次

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

l  建立一个节点,再插入

    

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

l  需要在多建立一个层次

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

代码注释


  1. /*
  2.  * Routines to manage a dynamic random access array of longs which
  3.  * may grow in size to be more than the largest single malloc'able
  4.  * chunk.
  5.  */
  6.  
  7. #defineRAA_BLKSIZE 4096 /* this many longs allocated at once */
  8. #defineRAA_LAYERSIZE 1024 /* this many _pointers_ allocated */
  9.  
  10. typedefstructRAA RAA;
  11. typedefunionRAA_UNION RAA_UNION;
  12. typedefstructRAA_LEAF RAA_LEAF;
  13. typedefstructRAA_BRANCH RAA_BRANCH;
  14.  
  15. /*叶子或者分支*/
  16. structRAA {
  17.     /*
  18.      * Number of layers below this one to get to the real data. 0
  19.      * means this structure is a leaf, holding RAA_BLKSIZE real
  20.      * data items; 1 and above mean it's a branch, holding
  21.      * RAA_LAYERSIZE pointers to the next level branch or leaf
  22.      * structures.
  23.      */
  24.     intlayers;
  25.     /*
  26.      * Number of real data items spanned by one position in the
  27.      * `data' array at this level. This number is 1, trivially, for
  28.      * a leaf (level 0): for a level 1 branch it should be
  29.      * RAA_BLKSIZE, and for a level 2 branch it's
  30.      * RAA_LAYERSIZE*RAA_BLKSIZE.
  31.      */
  32.     longstepsize;
  33.     unionRAA_UNION {
  34.         structRAA_LEAF {
  35.             longdata[RAA_BLKSIZE];
  36.         } l;
  37.         structRAA_BRANCH {
  38.             structRAA *data[RAA_LAYERSIZE];
  39.         } b;
  40.     } u;
  41. };
  42.  
  43. structRAA *raa_init(void);
  44. voidraa_free(structRAA *);
  45. longraa_read(structRAA *, long);
  46. structRAA *raa_write(structRAA *r, longposn, longvalue);
  47. /*计算叶子节点所占的内存大小*/
  48. #defineLEAFSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_LEAF))
  49. /*计算树枝节点所占的内存大小*/
  50. #defineBRANCHSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_BRANCH))
  51. /*判断该节点存储数据的大小*/
  52. #defineLAYERSIZ(r) ( (r)->layers==0 ? RAA_BLKSIZE : RAA_LAYERSIZE )
  53. /*建立并初始化struct RAA item */
  54. staticstructRAA *real_raa_init(intlayers)
  55. {
  56.     structRAA *r;
  57.     inti;
  58.  
  59.     if(layers == 0) { /*建立叶子节点*/
  60.         r = nasm_malloc(LEAFSIZ);
  61.         r->layers = 0;
  62.         memset(r->u.l.data, 0, sizeof(r->u.l.data));
  63.         r->stepsize = 1L; /* 子结点中,r->stepsize = 1,即每个存储单元可以存储1个long */
  64.     } else{ /* 建立树枝节点*/
  65.         r = nasm_malloc(BRANCHSIZ);
  66.         r->layers = layers;
  67.         for(i = 0; i < RAA_LAYERSIZE; i++)
  68.             r->u.b.data[i] = NULL;
  69.         r->stepsize = RAA_BLKSIZE; /* 该节点的每个存储单元可以存储多大的数据*/
  70.         while(--layers) /* r->stepsize = (RAA_LAYERSIZE ^ (layers - 1)) * RAA_BLKSIZE */
  71.             r->stepsize *= RAA_LAYERSIZE;
  72.     }
  73.     returnr;
  74. }
  75.  
  76. /*初始化叶子*/
  77. structRAA *raa_init(void)
  78. {
  79.     returnreal_raa_init(0);
  80. }
  81.  
  82. /*删除struct RAA生成的树*/
  83. voidraa_free(structRAA *r)
  84. {
  85.     if(r->layers == 0)
  86.         nasm_free(r);
  87.     else{
  88.         structRAA **p;
  89.         for(p = r->u.b.data; p - r->u.b.data < RAA_LAYERSIZE; p++)
  90.             if(*p)
  91.                 raa_free(*p);
  92.     }
  93. }
  94.  
  95. /*以下程序也可以用递归实现,不过用迭代更好*/
  96. longraa_read(structRAA *r, longposn)
  97. {
  98. /*计算要读取的数据的地址是否超出了该节点的所能容纳的范围*/
  99. if(posn >= r->stepsize * LAYERSIZ(r))
  100.         return0; /* Return 0 for undefined entries */
  101.     while(r->layers > 0) {
  102.         ldiv_t l;
  103.         l = ldiv(posn, r->stepsize);
  104.         r = r->u.b.data[l.quot]; /* 数据在第几个存储单元*/
  105.         posn = l.rem;
  106.         if(!r)
  107.             return0; /* Return 0 for undefined entries */
  108.     }
  109.     returnr->u.l.data[posn];
  110. }
  111.  
  112. structRAA *raa_write(structRAA *r, longposn, longvalue)
  113. {
  114.     structRAA *result;
  115.  
  116.     if(posn < 0)
  117.         nasm_malloc_error(ERR_PANIC, "negative position in raa_write");
  118.  
  119.     while(r->stepsize * LAYERSIZ(r) <= posn) {
  120.         /*
  121.          * Must add a layer.
  122.          */
  123.         structRAA *s;
  124.         inti;
  125.  
  126.         s = nasm_malloc(BRANCHSIZ);
  127.         for(i = 0; i < RAA_LAYERSIZE; i++)
  128.             s->u.b.data[i] = NULL;
  129.         s->layers = r->layers + 1;
  130.         s->stepsize = LAYERSIZ(r) * r->stepsize;
  131.         s->u.b.data[0] = r;
  132.         r = s;
  133.     }
  134.  
  135.     result = r;
  136.  
  137.     /* 插入数据的实际操作*/
  138.     while(r->layers > 0) {
  139.         ldiv_t l;
  140.         structRAA **s;
  141.         l = ldiv(posn, r->stepsize);
  142.         s = &r->u.b.data[l.quot];
  143.         if(!*s)
  144.             *s = real_raa_init(r->layers - 1);
  145.         r = *s;
  146.         posn = l.rem;
  147.     }
  148.  
  149.     r->u.l.data[posn] = value;
  150.  
  151.     returnresult;
  152. }

阅读(3335) | 评论(0) | 转发(0) |
0

上一篇:TCP/IP 协议详解 传输层

下一篇:Paint Chain

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册