首页 > 代码库 > kbtree的源码阅读

kbtree的源码阅读

2024-09-16 18:04:13   219人阅读

kbtree.h: generic search tree based on B-tree.

 

 

 

第一部分: 在算法开始前, 定义一些数据结构:

定义树的最大深度.

0035 #define KB_MAX_DEPTH 64  定义树的最大深度是64

 

这是树的一个结点的定义, 这里面使用的是C语言的bit fields

在这里, 就是四个字节,分别is_internal是占一个bit, n占了31个bit

0037 typedef struct {
0038     int32_t is_internal:1, n:31;
0039 } kbnode_t;

 

 

 

 

第二部分: 所暴露的函数, 与初始化

 

0364 #define KBTREE_INIT(name, key_t, __cmp)         0365     __KB_TREE_T(name)                           0366     __KB_INIT(name, key_t)                      0367     __KB_GET_AUX1(name, key_t, __cmp)           0368     __KB_GET(name, key_t)                       0369     __KB_INTERVAL(name, key_t)                  0370     __KB_PUT(name, key_t, __cmp)                0371     __KB_DEL(name, key_t) 0372     __KB_ITR(name, key_t)

 

2.1 定义代表树的结构

第一个__KB_TREE_T(name)所定义的是一个结构体, 用于代表这个树

0053 #define __KB_TREE_T(name)                       0054     typedef struct {                            0055         kbnode_t *root;                         0056         int off_key, off_ptr, ilen, elen;       0057         int n, t;                               0058         int n_keys, n_nodes;                    0059     } kbtree_##name##_t;

 

2.2 定义初始化树的函数

0061 #define __KB_INIT(name, key_t)                                          0062     kbtree_##name##_t *kb_init_##name(int size)

具体的函数实现在 3.1 中说明这个函数说什么

 

 

 

 

第三部分: 具体的函数的实现



3.1 初始化函数
kb_init_##name(s) 的函数的代码如下:




0062     kbtree_##name##_t *kb_init_##name(int size)                         0063     {                                                                   0064         kbtree_##name##_t *b;                                           \                                             定义一个名字为b的树的代表
0065         b = (kbtree_##name##_t*)calloc(1, sizeof(kbtree_##name##_t));   \                         给b分配相关的内存
0066         b->t = ((size - 4 - sizeof(void*)) / (sizeof(void*) + sizeof(key_t)) + 1) >> 1; \               key_t 是自己定义的一个键值的类型.
0067         if (b->t < 2) {                                                 0068             free(b); return 0;                                          0069         }                                                               0070         b->n = 2 * b->t - 1;                                            0071         b->off_ptr = 4 + b->n * sizeof(key_t);                          0072         b->ilen = (4 + sizeof(void*) + b->n * (sizeof(void*) + sizeof(key_t)) + 3) >> 2 << 2; 0073         b->elen = (b->off_ptr + 3) >> 2 << 2;                           0074         b->root = (kbnode_t*)calloc(1, b->ilen);                        \                                           分配一个root结点
0075         ++b->n_nodes;                                                   \                                                    结点数加1 
0076         return b;                                                       0077     }




 




kbtree的源码阅读






























        

            
                
                  
                
                

                    联系

                    我们