初始化、清空和删除
khash使用kcalloc(等同于calloc)申请一个大小为1的kh_##name##_t, 所有元素默认值都是0.
SCOPE kh_##name##_t *kh_init_##name(void) { \
return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \
}
SCOPE第一层替换代码是static kh_inline klib_unused, 第二层替换就是static inline __attribute__ ((__unused__)). static inline用于提高函数的执行效率，但是此类函数如果没有被使用，编译器会有警告，但是定义了__attribute__ ((__unused__))就可以避免这种警告。
因此，SCOPE是一种提高代码执行效率的函数修饰符。
和初始化相对的操作，一种是清空表里的元素，也就是将size和n_occupied都设置为0，把所有的flags都设置为0xaa也就是为空
SCOPE void kh_clear_##name(kh_##name##_t *h) \
{ \
if (h && h->flags) { \
memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \
h->size = h->n_occupied = 0; \
} \
}
另一种是直接释放所有内存。但它不会释放你在堆(heap)中申请的动态内存），也就是你需要自己手动释放你为字符串类型的key和value申请的内存。
SCOPE void kh_destroy_##name(kh_##name##_t *h) \
{ \
if (h) { \
kfree((void *)h->keys); kfree(h->flags); \
kfree((void *)h->vals); \
kfree(h); \
} \
} \
状态(flag)设置和查询
在kh_##name##_t数据结构中，flags用于记录不同位置的状态。为了节约空间，flags用的1/16的桶大小来记录信息。
这是因为flags是一个指向khint32_t元素的指针，khint32_t表示的是32位无符号整型，如果使用2个二进制位表示状态，那么一个32位无符号整型就能记录16个元素。
#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)
new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t));
memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t));
那么这里有一个问题，为啥不用一个二进制位来表示每个位置的状态呢？这是因为记录的状态有4种，分别是
-
empty(10): 空，没有存放key
-
delete(01), 虽然有key，但是标记为删除
-
either(11): 要么是空，要么是删除了，总之可以放key
-
occupied(00): 已经占用了元素
所以，必须要用2个二进制位。使用memset设置的0xaa对应二进制的0b10101010， 表示默认状态是empty.
下面这四行用于设置第i位的状态
#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
在设置第i位状态时，也就是设置i右移四位(也就是除以16)的状态，接着用((i&0xfU)<<1))计算出状态左移步数，例如i=17时，左移2位，i=16时, 左移0位。
如果我们设置的是is(del|empty|both)_false, 也就是需要反向设置，那么还需要对状态按位取反。接着和原来的情况按位与操作。
相对于设置状态，提取状态就变得容易些，只需要提取对应位置的状态，然后左移，然后和状态进行按位与运算即可。
#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
-
ul: unsigned long, 无符号长整型 -
0xfU: f就是10进制的16, U表示unsigned(无符号)，等价于2进制的0b1111U
如果是我设计flag的话，我估计会申请一个和key大小一样内容空间，直接用1/2/3的数字来表示，而不会用到位运算了。
网友评论