您现在的位置是：首页 >其他 >轻量级C通用库Klib解读 —— kdq网站首页其他

前言

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

kdq

代码比较简单，源代码在这里

数据结构主体：kdq_t

类似于c++的STL里的deque，本质上是封装了一个动态申请的数组，在c数组固定大小的基础上增加了自动扩容的操作
擅长首尾两端的增删与任意位置的读取，相比

#define __KDQ_TYPE(type) 
	typedef struct { 
		size_t front:58, bits:6, count, mask; 
		type *a; 
	} kdq_##type##_t;

#define kdq_t(type) kdq_##type##_t

• type：指定元素类型
• front：标记存储元素的起始位置
• bits：容量使用的bit位数，所以容量必为2的整数次方，即2^bits
• count：元素个数
• mask：掩码
• a：存储元素的数组

注1：容量的设置算是与常规实现deque想法最不一样的地方，一般想法是用取余%实现数组的循环利用，这里容量的特殊使得可以直接用与掩码的与&操作完成索引归零，相比取余更加高效
注2：front与bits共用4B的设计节省了4B的空间，虽然很小，但小细节也能组成大优势

声明与初始化：KDQ_INIT、kdq_init、kdq_destroy

这几个没啥好说的，初始化时设置容量为4

#define KDQ_INIT(type) KDQ_INIT2(type, static inline klib_unused)
#define kdq_init(type) kdq_init_##type()
#define kdq_destroy(type, q) kdq_destroy_##type(q)

#define KDQ_INIT2(type, SCOPE) 
	__KDQ_TYPE(type) 
	__KDQ_IMPL(type, SCOPE)

#define __KDQ_IMPL(type, SCOPE) 
	SCOPE kdq_##type##_t *kdq_init_##type() 
	{ 
		kdq_##type##_t *q; 
		q = (kdq_##type##_t*)calloc(1, sizeof(kdq_##type##_t)); 
		q->bits = 2, q->mask = (1ULL<<q->bits) - 1; 
		q->a = (type*)malloc((1<<q->bits) * sizeof(type)); 
		return q; 
	} ...

元素操作

增：kdq_push、kdq_pushp、kdq_unshift、kdq_unshiftp

• kdq_push：队尾添加数据v
• kdq_pushp：队尾并不加数据，返回数据应该加的位置

  #define kdq_pushp(type, q) kdq_pushp_##type(q)
  #define kdq_push(type, q, v) kdq_push_##type(q, v)
  
  #define __KDQ_IMPL(type, SCOPE) 
  	... 
  	SCOPE type *kdq_pushp_##type(kdq_##type##_t *q) 
  	{ 
  		if (q->count == 1ULL<<q->bits) kdq_resize_##type(q, q->bits + 1); 
  		return &q->a[((q->count++) + q->front) & (q)->mask]; 
  	} 
  	SCOPE void kdq_push_##type(kdq_##type##_t *q, type v) 
  	{ 
  		if (q->count == 1ULL<<q->bits) kdq_resize_##type(q, q->bits + 1); 
  		q->a[((q->count++) + q->front) & (q)->mask] = v; 
  	} ...
  

• kdq_unshift：队首添加数据v
• kdq_unshiftp：队首并不加数据，返回数据应该加的位置

  #define kdq_unshiftp(type, q) kdq_unshiftp_##type(q)
  #define kdq_unshift(type, q, v) kdq_unshift_##type(q, v)
  
  #define __KDQ_IMPL(type, SCOPE) 
  	... 
  	SCOPE type *kdq_unshiftp_##type(kdq_##type##_t *q) 
  	{ 
  		if (q->count == 1ULL<<q->bits) kdq_resize_##type(q, q->bits + 1); 
  		++q->count; 
  		q->front = q->front? q->front - 1 : (1ULL<<q->bits) - 1; 
  		return &q->a[q->front]; 
  	} 
  	SCOPE void kdq_unshift_##type(kdq_##type##_t *q, type v) 
  	{ 
  		type *p; 
  		p = kdq_unshiftp_##type(q); 
  		*p = v; 
  	} ...
  

删：kdq_pop、kdq_shift

• kdq_pop：删除队尾元素，返回被删除元素的位置

  #define kdq_pop(type, q) kdq_pop_##type(q)
  
  #define __KDQ_IMPL(type, SCOPE) 
  	... 
  	SCOPE type *kdq_pop_##type(kdq_##type##_t *q) 
  	{ 
  		return q->count? &q->a[((--q->count) + q->front) & q->mask] : 0; 
  	} ...
  

• kdq_shift：删除队首元素，返回被删除元素的位置

  #define kdq_shift(type, q) kdq_shift_##type(q)
  
  #define __KDQ_IMPL(type, SCOPE) 
  	... 
  	SCOPE type *kdq_shift_##type(kdq_##type##_t *q) 
  	{ 
  		type *d = 0; 
  		if (q->count == 0) return 0; 
  		d = &q->a[q->front++]; 
  		q->front &= q->mask; 
  		--q->count; 
  		return d; 
  	}
  

扩容：kdq_resize

入参new_bits是新容量占用bit数
kdq_push、kdq_unshift等扩容时new_bits = q->bits + 1，相当于原容量翻倍

• 新容量不够时new_size < q->count重新设置为能容纳当前size的大小
• 后面是考虑原数据是否需要迁移：当原数据分成两段q->front + q->count > old_size，或是超出新容量末尾时q->front + q->count > new_size需迁移

#define kdq_resize(type, q, new_bits) kdq_resize_##type(q, new_bits)

#define __KDQ_IMPL(type, SCOPE) 
	... 
	SCOPE int kdq_resize_##type(kdq_##type##_t *q, int new_bits) 
	{ 
		size_t new_size = 1ULL<<new_bits, old_size = 1ULL<<q->bits; 
		if (new_size < q->count) { /* not big enough */ 
			int i; 
			for (i = 0; i < 64; ++i) 
				if (1ULL<<i > q->count) break; 
			new_bits = i, new_size = 1ULL<<new_bits; 
		} 
		if (new_bits == q->bits) return q->bits; /* unchanged */ 
		if (new_bits > q->bits) q->a = (type*)realloc(q->a, (1ULL<<new_bits) * sizeof(type)); 
		if (q->front + q->count <= old_size) { /* unwrapped */ 
			if (q->front + q->count > new_size) /* only happens for shrinking */ 
				memmove(q->a, q->a + new_size, (q->front + q->count - new_size) * sizeof(type)); 
		} else { /* wrapped */ 
			memmove(q->a + (new_size - (old_size - q->front)), q->a + q->front, (old_size - q->front) * sizeof(type)); 
			q->front = new_size - (old_size - q->front); 
		} 
		q->bits = new_bits, q->mask = (1ULL<<q->bits) - 1; 
		if (new_bits < q->bits) q->a = (type*)realloc(q->a, (1ULL<<new_bits) * sizeof(type)); 
		return q->bits; 
	} ...

其他操作

#define kdq_size(q)  ((q)->count)
#define kdq_first(q) ((q)->a[(q)->front])
#define kdq_last(q)	 ((q)->a[((q)->front + (q)->count - 1) & (q)->mask])
#define kdq_at(q, i) ((q)->a[((q)->front + (i)) & (q)->mask])