您现在的位置是:首页 >技术杂谈 >轻量级C通用库Klib解读 —— kbtree【待补充】网站首页技术杂谈

轻量级C通用库Klib解读 —— kbtree【待补充】

浅浅280 2025-03-06 12:01:02
简介轻量级C通用库Klib解读 —— kbtree【待补充】

前言

Klib是一个独立的轻量级c通用库,里面大多数组件除了C标准库外不包含外部库,想用对应组件直接拷贝对应文件即可使用。
该库致力于高效和较小的内存占用,其中部分组件(如khashkbtreeksortkvec),无论是内存还是速度方面,都是所有编程语言中相似算法或数据结构最高效的实现之一。

kbtree

源代码在这里
:这个B树并不限定为二叉树,所以一个节点可以有很多子节点

数据结构主体

// 结构图放这里
:这里可以窥见大神写代码的又一个技巧,就是实际结构有一堆但是暴露出来的结构只有一点,像是这里只暴露出来了节点的头4B

typedef struct {
	int32_t is_internal:1, n:31;	// 用 1bit 标记是否是内部节点
} kbnode_t;

#define __KB_TREE_T(name)						
	typedef struct {							
		kbnode_t *root;							
		int	off_key, off_ptr, ilen, elen;		
		int	n, t;								
		int	n_keys, n_nodes;					
	} kbtree_##name##_t;

#define kbtree_t(name) kbtree_##name##_t

#define KB_DEFAULT_SIZE 512
  • root:根节点
    • is_internal:节点类型(内部/外部)
    • n:已插入key个数
  • off_key:完全没有用它的地方,不知道这个干嘛的
  • off_ptr:可理解为头4字节加所有key的总大小,或是子节点信息的起始位置
  • ilen:申请内部节点时的内存大小
  • elen:申请外部节点时的内存大小
  • n:存储key个数上限(等于2*t - 1
  • t:key个数上限的一半
  • n_keys:已插入key个数
  • n_nodes:节点总个数(包含内部跟外部)
#define	__KB_KEY(type, x)	((type*)((char*)x + 4))
#define __KB_PTR(btr, x)	((kbnode_t**)((char*)x + btr->off_ptr))

这两个宏的入参x都是节点指针kbnode_t *,分别用于访问子节点的key_t和子节点指针void *(强转成kbnode_t*

初始化/释放

  • kb_init:参数size为用户预期的每个节点大小(单位字节B),根据其进行初始化各个成员
    :这里... + 3) >> 2 << 2是为了把大小变成4的倍数,+3是为了预留一点免得申请少了
    #define __KB_INIT(name, key_t)											
    	kbtree_##name##_t *kb_init_##name(int size)							
    	{																	
    		kbtree_##name##_t *b;											
    		b = (kbtree_##name##_t*)calloc(1, sizeof(kbtree_##name##_t));	
    		b->t = ((size - 4 - sizeof(void*)) / (sizeof(void*) + sizeof(key_t)) + 1) >> 1; 
    		if (b->t < 2) {													
    			free(b); return 0;											
    		}																
    		b->n = 2 * b->t - 1;											
    		b->off_ptr = 4 + b->n * sizeof(key_t);							
    		b->ilen = (4 + sizeof(void*) + b->n * (sizeof(void*) + sizeof(key_t)) + 3) >> 2 << 2; 
    		b->elen = (b->off_ptr + 3) >> 2 << 2;							
    		b->root = (kbnode_t*)calloc(1, b->ilen);						
    		++b->n_nodes;													
    		return b;														
    	}
    
    #define kb_init(name, s) kb_init_##name(s)
    
  • kb_destroy:核心就是用栈按广度优先搜索BFS把所有的节点取出来进行free(如果是外部节点x->is_internal == 0则直接释放,因为没有子节点了)
    #define __kb_destroy(b) do {											
    		int i, max = 8;													
    		kbnode_t *x, **top, **stack = 0;								
    		if (b) {														
    			top = stack = (kbnode_t**)calloc(max, sizeof(kbnode_t*));	
    			*top++ = (b)->root;											
    			while (top != stack) {										
    				x = *--top;												
    				if (x->is_internal == 0) { free(x); continue; }			
    				for (i = 0; i <= x->n; ++i)								
    					if (__KB_PTR(b, x)[i]) {							
    						if (top - stack == max) {						
    							max <<= 1;									
    							stack = (kbnode_t**)realloc(stack, max * sizeof(kbnode_t*)); 
    							top = stack + (max>>1);						
    						}												
    						*top++ = __KB_PTR(b, x)[i];						
    					}													
    				free(x);												
    			}															
    		}																
    		free(b); free(stack);											
    	} while (0)
    
    #define kb_destroy(name, b) __kb_destroy(b)
    

节点操作

增删查等操作输入都有两个版本,一个传入const key_t,另一个传入const key_t *,实际都是调用后者

查:kb_getkb_getp

实际调用__kb_getp_aux_##name并根据返回值和r判断是否找到了插入位置或是继续深入搜索
r为0时表示找到指定keyk,返回其地址;否则i为比key小的最大节点索引(所以要+1再继续搜索)

#define kb_get(name, b, k) kb_get_##name(b, k)
#define kb_getp(name, b, k) kb_getp_##name(b, k)

#define __KB_GET(name, key_t)											
	static key_t *kb_getp_##name(kbtree_##name##_t *b, const key_t * __restrict k) 
	{																	
		int i, r = 0;													
		kbnode_t *x = b->root;											
		while (x) {														
			i = __kb_getp_aux_##name(x, k, &r);							
			if (i >= 0 && r == 0) return &__KB_KEY(key_t, x)[i];		
			if (x->is_internal == 0) return 0;							
			x = __KB_PTR(b, x)[i + 1];									
		}																
		return 0;														
	} ...

:注意__restrict关键字,可查阅__restrictrestrict
该关键字用于修饰变量,表示该变量对应的内存地址只有一个名字(没有alias),方便编译器进一步优化代码

二分搜索

__kb_getp_aux_##name:用二分查找法(Binary Search)搜索keyk应该插入的位置

#define __KB_GET_AUX1(name, key_t, __cmp)								
	static inline int __kb_getp_aux_##name(const kbnode_t * __restrict x, const key_t * __restrict k, int *r) 
	{																	
		int tr, *rr, begin = 0, end = x->n;								
		if (x->n == 0) return -1;										
		rr = r? r : &tr;												
		while (begin < end) {											
			int mid = (begin + end) >> 1;								
			if (__cmp(__KB_KEY(key_t, x)[mid], *k) < 0) begin = mid + 1; 
			else end = mid;												
		}																
		if (begin == x->n) { *rr = 1; return x->n - 1; }				
		if ((*rr = __cmp(*k, __KB_KEY(key_t, x)[begin])) < 0) --begin;	
		return begin;													
	}
默认比较策略

-1:a<b
0 :a=b
1 :a>b

#define kb_generic_cmp(a, b) (((b) < (a)) - ((a) < (b)))
#define kb_str_cmp(a, b) strcmp(a, b)

增:kb_putkb_putp

  1. 如果root节点已满需要拆分则拆分,然后调用__kb_putp_aux_##name往树里添加keyk
    #define kb_put(name, b, k) kb_put_##name(b, k)
    #define kb_putp(name, b, k) kb_putp_##name(b, k)
    
    #define __KB_PUT(name, key_t, __cmp)									
    	...																	
    	static key_t *kb_putp_##name(kbtree_##name##_t *b, const key_t * __restrict k) 
    	{																	
    		kbnode_t *r, *s;												
    		++b->n_keys;													
    		r = b->root;													
    		if (r->n == 2 * b->t - 1) {										
    			++b->n_nodes;												
    			s = (kbnode_t*)calloc(1, b->ilen);							
    			b->root = s; s->is_internal = 1; s->n = 0;					
    			__KB_PTR(b, s)[0] = r;										
    			__kb_split_##name(b, s, 0, r);								
    			r = s;														
    		}																
    		return __kb_putp_aux_##name(b, r, k);							
    	} ...
    
  2. 搜索内部节点直到找到外部节点,最后调用memmove腾出位置后插入key
    注1memmove类似memcpy,但是能保证即使内存区域有overlap也可以正常工作,具体可以看这里
    注2:搜索内部节点的过程中保证有节点满__KB_PTR(b, x)[i]->n == 2 * b->t - 1时及时进行拆分
    #define __KB_PUT(name, key_t, __cmp)									
    	...																	
    	static key_t *__kb_putp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, const key_t * __restrict k) 
    	{																	
    		int i = x->n - 1;												
    		key_t *ret;														
    		if (x->is_internal == 0) {										
    			i = __kb_getp_aux_##name(x, k, 0);							
    			if (i != x->n - 1)											
    				memmove(__KB_KEY(key_t, x) + i + 2, __KB_KEY(key_t, x) + i + 1, (x->n - i - 1) * sizeof(key_t)); 
    			ret = &__KB_KEY(key_t, x)[i + 1];							
    			*ret = *k;													
    			++x->n;														
    		} else {														
    			i = __kb_getp_aux_##name(x, k, 0) + 1;						
    			if (__KB_PTR(b, x)[i]->n == 2 * b->t - 1) {					
    				__kb_split_##name(b, x, i, __KB_PTR(b, x)[i]);			
    				if (__cmp(*k, __KB_KEY(key_t, x)[i]) > 0) ++i;			
    			}															
    			ret = __kb_putp_aux_##name(b, __KB_PTR(b, x)[i], k);		
    		}																
    		return ret; 													
    	}
    
拆分节点

拆分条件:x节点(父节点)的第i个子节点y已经满员n == 2*t - 1
拆分过程:

  1. 新建一个节点z(与y同类型),存储y的后t - 1个key,如果是内部节点还存后t个子节点(因为)
  2. y的中间的key(位置在t)上挪到父节点x
  3. y中只存t - 1个key
#define __KB_PUT(name, key_t, __cmp)									
	/* x must be an internal node */									
	static void __kb_split_##name(kbtree_##name##_t *b, kbnode_t *x, int i, kbnode_t *y) 
	{																	
		kbnode_t *z;													
		z = (kbnode_t*)calloc(1, y->is_internal? b->ilen : b->elen);	
		++b->n_nodes;													
		z->is_internal = y->is_internal;								
		z->n = b->t - 1;												
		memcpy(__KB_KEY(key_t, z), __KB_KEY(key_t, y) + b->t, sizeof(key_t) * (b->t - 1)); 
		if (y->is_internal) memcpy(__KB_PTR(b, z), __KB_PTR(b, y) + b->t, sizeof(void*) * b->t); 
		y->n = b->t - 1;												
		memmove(__KB_PTR(b, x) + i + 2, __KB_PTR(b, x) + i + 1, sizeof(void*) * (x->n - i)); 
		__KB_PTR(b, x)[i + 1] = z;										
		memmove(__KB_KEY(key_t, x) + i + 1, __KB_KEY(key_t, x) + i, sizeof(key_t) * (x->n - i)); 
		__KB_KEY(key_t, x)[i] = __KB_KEY(key_t, y)[b->t - 1];			
		++x->n;															
	} ...

删:kb_delkb_delp

// 这个代码略多,还没细看,后面补充嘿嘿
实际调用__kb_delp_aux_##name删key
参数s:只能为0/1/2
r:标记是否是外部节点
kp:被删除的key结果
删除过程:

  • 先搜索删除的key所在位置
  • 如果找得到key,且当前节点已经是外部节点,则直接删除对应key
  • 如果找得到key,且当前节点是内部节点,则把它的前辈/后辈拿来顶替它,然后把前辈/后辈删掉
  • 如果找不到key,则递归搜索子节点
  • 删除后重新平衡树
#define __KB_DEL(name, key_t)											
	static key_t __kb_delp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, const key_t * __restrict k, int s) 
	{																	
		int yn, zn, i, r = 0;											
		kbnode_t *xp, *y, *z;											
		key_t kp;														
		if (x == 0) return *k;											
		if (s) { /* s can only be 0, 1 or 2 */							
			r = x->is_internal == 0? 0 : s == 1? 1 : -1;				
			i = s == 1? x->n - 1 : -1;									
		} else i = __kb_getp_aux_##name(x, k, &r);						
		if (x->is_internal == 0) {										
			if (s == 2) ++i;											
			kp = __KB_KEY(key_t, x)[i];									
			memmove(__KB_KEY(key_t, x) + i, __KB_KEY(key_t, x) + i + 1, (x->n - i - 1) * sizeof(key_t)); 
			--x->n;														
			return kp;													
		}																
		if (r == 0) {													
			if ((yn = __KB_PTR(b, x)[i]->n) >= b->t) {					
				xp = __KB_PTR(b, x)[i];									
				kp = __KB_KEY(key_t, x)[i];								
				__KB_KEY(key_t, x)[i] = __kb_delp_aux_##name(b, xp, 0, 1); 
				return kp;												
			} else if ((zn = __KB_PTR(b, x)[i + 1]->n) >= b->t) {		
				xp = __KB_PTR(b, x)[i + 1];								
				kp = __KB_KEY(key_t, x)[i];								
				__KB_KEY(key_t, x)[i] = __kb_delp_aux_##name(b, xp, 0, 2); 
				return kp;												
			} else if (yn == b->t - 1 && zn == b->t - 1) {				
				y = __KB_PTR(b, x)[i]; z = __KB_PTR(b, x)[i + 1];		
				__KB_KEY(key_t, y)[y->n++] = *k;						
				memmove(__KB_KEY(key_t, y) + y->n, __KB_KEY(key_t, z), z->n * sizeof(key_t)); 
				if (y->is_internal) memmove(__KB_PTR(b, y) + y->n, __KB_PTR(b, z), (z->n + 1) * sizeof(void*)); 
				y->n += z->n;											
				memmove(__KB_KEY(key_t, x) + i, __KB_KEY(key_t, x) + i + 1, (x->n - i - 1) * sizeof(key_t)); 
				memmove(__KB_PTR(b, x) + i + 1, __KB_PTR(b, x) + i + 2, (x->n - i - 1) * sizeof(void*)); 
				--x->n;													
				free(z);												
				return __kb_delp_aux_##name(b, y, k, s);				
			}															
		}																
		++i;															
		if ((xp = __KB_PTR(b, x)[i])->n == b->t - 1) {					
			if (i > 0 && (y = __KB_PTR(b, x)[i - 1])->n >= b->t) {		
				memmove(__KB_KEY(key_t, xp) + 1, __KB_KEY(key_t, xp), xp->n * sizeof(key_t)); 
				if (xp->is_internal) memmove(__KB_PTR(b, xp) + 1, __KB_PTR(b, xp), (xp->n + 1) * sizeof(void*)); 
				__KB_KEY(key_t, xp)[0] = __KB_KEY(key_t, x)[i - 1];		
				__KB_KEY(key_t, x)[i - 1] = __KB_KEY(key_t, y)[y->n - 1]; 
				if (xp->is_internal) __KB_PTR(b, xp)[0] = __KB_PTR(b, y)[y->n]; 
				--y->n; ++xp->n;										
			} else if (i < x->n && (y = __KB_PTR(b, x)[i + 1])->n >= b->t) { 
				__KB_KEY(key_t, xp)[xp->n++] = __KB_KEY(key_t, x)[i];	
				__KB_KEY(key_t, x)[i] = __KB_KEY(key_t, y)[0];			
				if (xp->is_internal) __KB_PTR(b, xp)[xp->n] = __KB_PTR(b, y)[0]; 
				--y->n;													
				memmove(__KB_KEY(key_t, y), __KB_KEY(key_t, y) + 1, y->n * sizeof(key_t)); 
				if (y->is_internal) memmove(__KB_PTR(b, y), __KB_PTR(b, y) + 1, (y->n + 1) * sizeof(void*)); 
			} else if (i > 0 && (y = __KB_PTR(b, x)[i - 1])->n == b->t - 1) { 
				__KB_KEY(key_t, y)[y->n++] = __KB_KEY(key_t, x)[i - 1];	
				memmove(__KB_KEY(key_t, y) + y->n, __KB_KEY(key_t, xp), xp->n * sizeof(key_t));	
				if (y->is_internal) memmove(__KB_PTR(b, y) + y->n, __KB_PTR(b, xp), (xp->n + 1) * sizeof(void*)); 
				y->n += xp->n;											
				memmove(__KB_KEY(key_t, x) + i - 1, __KB_KEY(key_t, x) + i, (x->n - i) * sizeof(key_t)); 
				memmove(__KB_PTR(b, x) + i, __KB_PTR(b, x) + i + 1, (x->n - i) * sizeof(void*)); 
				--x->n;													
				free(xp);												
				xp = y;													
			} else if (i < x->n && (y = __KB_PTR(b, x)[i + 1])->n == b->t - 1) { 
				__KB_KEY(key_t, xp)[xp->n++] = __KB_KEY(key_t, x)[i];	
				memmove(__KB_KEY(key_t, xp) + xp->n, __KB_KEY(key_t, y), y->n * sizeof(key_t));	
				if (xp->is_internal) memmove(__KB_PTR(b, xp) + xp->n, __KB_PTR(b, y), (y->n + 1) * sizeof(void*)); 
				xp->n += y->n;											
				memmove(__KB_KEY(key_t, x) + i, __KB_KEY(key_t, x) + i + 1, (x->n - i - 1) * sizeof(key_t)); 
				memmove(__KB_PTR(b, x) + i + 1, __KB_PTR(b, x) + i + 2, (x->n - i - 1) * sizeof(void*)); 
				--x->n;													
				free(y);												
			}															
		}																
		return __kb_delp_aux_##name(b, xp, k, s);						
	} ...

遍历

使用结构体:kbitr_tkb_itr_key
typedef struct {
	kbnode_t *x;
	int i;
} kbpos_t;

typedef struct {
	kbpos_t stack[KB_MAX_DEPTH], *p;
} kbitr_t;

#define kb_itr_key(type, itr) __KB_KEY(type, (itr)->p->x)[(itr)->p->i]
#define kb_itr_valid(itr) ((itr)->p >= (itr)->stack)
  • kbitr_t:栈用于遍历时使用,p存储搜索结果在栈中的位置(栈顶)
  • kbpos_t:某个节点位置(父节点x、在父节点中的索引i
  • kb_itr_key:获取结果指针
  • kb_itr_valid:检验结果是否合理
API接口:kb_itr_firstkb_itr_getkb_itr_next
  • kb_itr_first:初始化迭代器itr,指向最小的外部节点itr->p->i = 0
    #define kb_itr_first(name, b, i) kb_itr_first_##name(b, i)
    
    #define __KB_ITR(name, key_t) 
    	static inline void kb_itr_first_##name(kbtree_##name##_t *b, kbitr_t *itr) 
    	{ 
    		itr->p = 0; 
    		if (b->n_keys == 0) return; 
    		itr->p = itr->stack; 
    		itr->p->x = b->root; itr->p->i = 0; 
    		while (itr->p->x->is_internal && __KB_PTR(b, itr->p->x)[0] != 0) { 
    			kbnode_t *x = itr->p->x; 
    			++itr->p; 
    			itr->p->x = __KB_PTR(b, x)[0]; itr->p->i = 0; 
    		} 
    	} ...
    
  • kb_itr_get:初始化迭代器itr,指向包含指定keyk的外部节点
    成功返回0,搜到外部节点都没搜到则返回-1
    过程与kb_get基本类似
    #define kb_itr_get(name, b, k, i) kb_itr_get_##name(b, k, i)
    
    #define __KB_ITR(name, key_t) 
    	... 
    	static int kb_itr_get_##name(kbtree_##name##_t *b, const key_t * __restrict k, kbitr_t *itr) 
    	{ 
    		int i, r = 0; 
    		itr->p = itr->stack; 
    		itr->p->x = b->root; itr->p->i = 0; 
    		while (itr->p->x) { 
    			i = __kb_getp_aux_##name(itr->p->x, k, &r); 
    			if (i >= 0 && r == 0) return 0; 
    			if (itr->p->x->is_internal == 0) return -1; 
    			itr->p[1].x = __KB_PTR(b, itr->p->x)[i + 1]; 
    			itr->p[1].i = i; 
    			++itr->p; 
    		} 
    		return -1; 
    	} ...
    
  • kb_itr_next:把迭代器itr更新指向下一个元素key
    成功返回1,没有下一个节点了返回0
    #define kb_itr_next(name, b, i) kb_itr_next_##name(b, i)
    
    #define __KB_ITR(name, key_t) 
    	... 
    	static inline int kb_itr_next_##name(kbtree_##name##_t *b, kbitr_t *itr) 
    	{ 
    		if (itr->p < itr->stack) return 0; 
    		for (;;) { 
    			++itr->p->i; 
    			while (itr->p->x && itr->p->i <= itr->p->x->n) { 
    				itr->p[1].i = 0; 
    				itr->p[1].x = itr->p->x->is_internal? __KB_PTR(b, itr->p->x)[itr->p->i] : 0; 
    				++itr->p; 
    			} 
    			--itr->p; 
    			if (itr->p < itr->stack) return 0; 
    			if (itr->p->x && itr->p->i < itr->p->x->n) return 1; 
    		} 
    	}
    
    :这里我感觉有点问题,每次调用应该都是返回指向外部节点的itr,但是感觉并没有,不知道有没有大神帮忙解释一下
    • 如果当前外部节点还有key,那while循环其实只会执行一次就退出,p位置不变只是++itr->p->i,这没问题
    • 如果当前外部节点遍历完了,假设此节点有3个key,即itr->p->x->n : 3, itr->p->i : 2,此时再次调用kb_itr_next
      第一次for循环,++i3,此次循环p仍然不变,由itr->p->i < itr->p->x->n不成立所以继续循环
      第二次for循环,++i4,这次不进while循环,itr->p指向上一层内部节点,此时判断itr->p->i < itr->p->x->n成立岂不是返回1了,但是这样itr->p并没有指向下一个外部节点,有点怪

其他

interval:kb_intervalkb_intervalp

找出keyk属于的区间,还是与kb_get类似
如果存在key则*lower = *upper = &__KB_KEY(key_t, x)[i];
不存在则分别等于ii + 1对应的位置

#define kb_interval(name, b, k, l, u) kb_interval_##name(b, k, l, u)
#define kb_intervalp(name, b, k, l, u) kb_intervalp_##name(b, k, l, u)

#define __KB_INTERVAL(name, key_t)										
	static void kb_intervalp_##name(kbtree_##name##_t *b, const key_t * __restrict k, key_t **lower, key_t **upper)	
	{																	
		int i, r = 0;													
		kbnode_t *x = b->root;											
		*lower = *upper = 0;											
		while (x) {														
			i = __kb_getp_aux_##name(x, k, &r);							
			if (i >= 0 && r == 0) {										
				*lower = *upper = &__KB_KEY(key_t, x)[i];				
				return;													
			}															
			if (i >= 0) *lower = &__KB_KEY(key_t, x)[i];				
			if (i < x->n - 1) *upper = &__KB_KEY(key_t, x)[i + 1];		
			if (x->is_internal == 0) return;							
			x = __KB_PTR(b, x)[i + 1];									
		}																
	} ...
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。