由于linux內(nèi)核中的struct list_head已經(jīng)定義了指向前驅(qū)的prev指針和指向后繼的next指針，并且提供了相關(guān)的鏈表操作方法，因此為方便復(fù)用，本文在它的基礎(chǔ)上封裝實(shí)現(xiàn)了一種使用開鏈法解決沖突的通用內(nèi)核Hash表
glib_htable，提供了初始化、增加、查找、刪除、清空和銷毀6種操作，除初始化和銷毀外，其它操作都做了同步，適用于中斷和進(jìn)程上下文。與一般的通用Hash表（如c++中的hash_map及某些c語言實(shí)現(xiàn)的泛型哈希表）有以下不同：
● 存儲在glib_htable里的對象由外部而不是內(nèi)部負(fù)責(zé)創(chuàng)建，這個對象必須直接或間接地組合了list_head成員（間接組合，包含下文中的
glib_hentry即可），這里引用UML中的術(shù)語組合，意在強(qiáng)調(diào)不是聚合關(guān)系。
● 刪除操作的語義是從Hash表移去對象的鏈接，但釋放對象是可選的。
● 桶的個數(shù)由外部指定而不是內(nèi)部維護(hù)。
綜上可見glib_htable是使用對象已存在的內(nèi)嵌成員list_head來鏈接到Hash表中的，比一般的通用Hash表，每個表項節(jié)省了1個指針的空間，如下圖所示。
結(jié)構(gòu)定義
1
struct glib_hentry 
{
2
struct list_head list;
3 void *data;
4
};
5
6typedef unsigned int (*glib_htable_hashfun_t)(const void*,unsigned int);
7typedef int (*glib_htable_cmpfun_t)(const void*, const void*);
8typedef void (*glib_htable_cbfun_t)(struct glib_hentry*);
9typedef void (*glib_htable_freefun_t)(struct glib_hentry*);
10
11struct glib_htable {
12 struct list_head *bucket;
13 unsigned int size;
14 unsigned int vmalloced;
15
16 rwlock_t lock;
17
18 glib_htable_hashfun_t hashfun;
19 glib_htable_cmpfun_t cmpfun;
20 glib_htable_cbfun_t cbfun;
21 glib_htable_freefun_t freefun;
22}; 1）glib_hentry抽象了存儲對象的內(nèi)嵌成員，表示Hash項，也可表示整個對象，這時內(nèi)嵌成員就是對象本身了，成員data表示對象關(guān)聯(lián)的任意數(shù)據(jù)，用于計算hash值，當(dāng)關(guān)聯(lián)數(shù)據(jù)大小<=sizeof(void*)時，可直接強(qiáng)制轉(zhuǎn)換為data存儲，而不必為數(shù)據(jù)地址。
2）glib_htable抽象了Hash表，size表示桶個數(shù)，考慮到size可能很多，需要占用大塊內(nèi)存，所以在分配連續(xù)物理頁失敗的情況下，再使用vmalloc嘗試分配不連續(xù)的物理頁，所以引入了vmalloced表示分配方式，非零表示用vmalloc，零則用__get_free_pages；hashfun和cmpfun是實(shí)現(xiàn)Hash表的兩個缺一不可的關(guān)鍵函數(shù)，cbfun用于查找成功時的回調(diào)處理，如打印、增加引用計數(shù)等，freefun用于釋放對象，提供這個回調(diào)接口是為了方便從Hash表移除對象后可以釋放對象，而不必由外部釋放，增加了靈活性。
主要接口 以下所有操作中的第1參數(shù)ht表示glib_htable對象。
● 初始化
int glib_htable_init(struct glib_htable *ht, unsigned int size, glib_htable_hashfun_t hashfun, glib_htable_cmpfun_t cmpfun); size表示Hash表桶的個數(shù)，hashfun為Hash函數(shù)，cmpfun為比較函數(shù)；成功時返回0，ht成員cbfun和freefun設(shè)置為空，失敗返回ENOMEM。由于可能使用vmalloc分配內(nèi)存，因此不能用于中斷上下文。
● 增加
void glib_htable_add(struct glib_htable *ht, struct glib_hentry *he, int num); 在一次同步內(nèi)添加多個對象，he為指向?qū)ο驢ash項的指針，num為個數(shù)。
● 查找
struct glib_hentry* glib_htable_get(struct glib_htable *ht, const void *data);
struct glib_hentry* glib_htable_rget(struct glib_htable *ht, const void *data);
struct glib_hentry* glib_htable_cget(struct glib_htable *ht, const void *data, int(*cmp)(const struct glib_hentry*, void*), void *arg);
struct glib_hentry* glib_htable_crget(struct glib_htable *ht, const void *data, int(*cmp)(const struct glib_hentry*, void*), void *arg);
struct glib_hentry* glib_htable_cget_byidx(struct glib_htable *ht, unsigned int *bucket, int(*cmp)(const struct glib_hentry*, void*), void *arg);
struct glib_hentry* glib_htable_crget_byidx(struct glib_htable *ht, unsigned int *bucket, int(*cmp)(const struct glib_hentry*, void*), void *arg); 從上到下依次為正向查找、反向查找、正向條件查找、反向條件查找、按桶定位的正向條件查找、按桶定位的反向條件查找，data為對象關(guān)聯(lián)數(shù)據(jù)，cmp為自定義的比較函數(shù)，arg為cmp所帶的自定義參數(shù)，bucket為桶索引，若查找成功，則bucket更新為對象所在的桶索引。以上所有操作，當(dāng)失敗時返回NULL。
● 刪除
void glib_htable_del(struct glib_htable *ht, struct glib_hentry *he, int num);
void glib_htable_del_bydata(struct glib_htable *ht, const void **data, int num); 第1個按對象Hash項刪除，第2個按對象關(guān)聯(lián)數(shù)據(jù)刪除，num表示個數(shù)，若ht成員freefun非空，則釋放對象。
● 清空
void glib_htable_clear(struct glib_htable *ht); 在一次同步內(nèi)刪除所有的對象，若ht成員freefun非空，則釋放對象。
● 銷毀
void glib_htable_free(struct glib_htable *ht); 僅釋放所有桶占用的內(nèi)存，應(yīng)在glib_htable_clear后調(diào)用。由于可能使用vfree釋放內(nèi)存，因此不能用于中斷上下文。
接口實(shí)現(xiàn) 其它接口實(shí)現(xiàn)比較簡單，略過講解。對于查找接口，如果增加一個參數(shù)來指示遍歷方向，那么雖然接口總數(shù)減半，但在使用特別是在一個循環(huán)內(nèi)調(diào)用時，每次都進(jìn)行不必要的方向判斷而降低了性能，所以對于正向和反向遍歷，每個都給出一個接口，正如c庫中的strchr與strrchr、c++容器中的iterator與reverse_iterator，這樣一來更清晰明確。在實(shí)現(xiàn)上除了遍歷方向不同外，其它代碼都相同，因此為避免手工編碼冗余，使用了3組宏來生成。
輔助函數(shù)宏生成
1#define DEFINE_GLIB_HTABLE_GET_HELP(name) \
2static struct glib_hentry* __glib_htable_##name(
struct glib_htable *ht, unsigned int hash, const void *data) \
3{\
4 struct glib_hentry *he; \
5\
6
glib_htable_list_##name(he,&ht->bucket[hash],list){ \
7 if(ht->cmpfun(he->data,data)){ \
8 if(ht->cbfun) \
9 ht->cbfun(he); \
10 return he; \
11
} \
12 } \
13\
14 return NULL; \
15}
16
17DEFINE_GLIB_HTABLE_GET_HELP(get)
18DEFINE_GLIB_HTABLE_GET_HELP(rget)
19
20#define DEFINE_GLIB_HTABLE_COND_GET_HELP(name) \
21static struct glib_hentry* __glib_htable_c##name(
struct glib_htable *ht, unsigned int hash, int(*cmp)(const struct glib_hentry*, void*), void *arg) \
22{ \
23 struct glib_hentry *he; \
24\
25 glib_htable_list_##name(he,&ht->bucket[hash],list){ \
26 if(cmp(he, arg)){ \
27 if(ht->cbfun) \
28 ht->cbfun(he); \
29 return he; \
30 } \
31 } \
32\
33 return NULL; \
34}
35
36DEFINE_GLIB_HTABLE_COND_GET_HELP(get)
37DEFINE_GLIB_HTABLE_COND_GET_HELP(rget)
生成宏為DEFINE_GLIB_HTABLE_GET_HELP和DEFINE_GLIB_HTABLE_COND_GET_HELP，展開后就有了__glib_htable_get(rget)和__glib_htable_cget(crget) 4個不加鎖的函數(shù)，用于實(shí)現(xiàn)對應(yīng)的加鎖接口。glib_htable_list_get和glib_htable_list_rget分別是宏list_for_each_entry和list_for_each_entry_reverse的別名。
普通查找宏生成
調(diào)用輔助函數(shù)__glib_htable_get(rget)實(shí)現(xiàn)，生成宏為DEFINE_GLIB_HTABLE_GET，展開后就有了glib_htable_get(rget)接口。
條件查找宏生成
1#define DEFINE_GLIB_HTABLE_COND_GET(name) \
2struct glib_hentry* glib_htable_c##name(
struct glib_htable *ht, const void *data, int(*cmp)(const struct glib_hentry*, void*), void *arg) \
3{ \
4 struct glib_hentry *he; \
5 unsigned int h = ht->hashfun(data,ht->size); \
6\
7 read_lock_bh(&ht->lock); \
8 he = __glib_htable_c##name(ht, h, cmp, arg); \
9 read_unlock_bh(&ht->lock); \
10\
11 return he; \
12}
13
14DEFINE_GLIB_HTABLE_COND_GET(get)
15DEFINE_GLIB_HTABLE_COND_GET(rget)
16
17#define DEFINE_GLIB_HTABLE_COND_GET_BYIDX(name) \
18struct glib_hentry* glib_htable_c##name##_byidx(
struct glib_htable *ht, unsigned int *bucket, int(*cmp)(const struct glib_hentry*, void*), void *arg) \
19{ \
20 unsigned int h; \
21 struct glib_hentry *he = NULL; \
22\
23 read_lock_bh(&ht->lock); \
24\
25 for (h = *bucket; h < ht->size; h = (*bucket)++){ \
26 he = __glib_htable_c##name(ht, h, cmp, arg); \
27 if(he) \
28 break; \
29 } \
30\
31 read_unlock_bh(&ht->lock); \
32\
33 return he; \
34}
35
36DEFINE_GLIB_HTABLE_COND_GET_BYIDX(get)
37DEFINE_GLIB_HTABLE_COND_GET_BYIDX(rget)
前者調(diào)用輔助函數(shù)__glib_htable_cget(rget)實(shí)現(xiàn)，生成宏為DEFINE_GLIB_HTABLE_COND_GET，展開后就有了glib_htable_cget(rget)接口；后者調(diào)用輔助函數(shù)__glib_htable_cget(rget)_byidx實(shí)現(xiàn)，生成宏為DEFINE_GLIB_HTABLE_COND_GET_BYIDX，展開后就有了glib_htable_cget(rget)_byidx接口。
完整源碼下載：
glib_hash，包括glib_htable.h和glib_htable.c文件。
posted on 2015-09-15 17:18
春秋十二月 閱讀(2217)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm