青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆-162  評論-223  文章-30  trackbacks-0
   由于linux內核中的struct list_head已經定義了指向前驅的prev指針和指向后繼的next指針,并且提供了相關的鏈表操作方法,因此為方便復用,本文在它的基礎上封裝實現了一種使用開鏈法解決沖突的通用內核Hash表glib_htable,提供了初始化、增加、查找、刪除、清空和銷毀6種操作,除初始化和銷毀外,其它操作都做了同步,適用于中斷和進程上下文。與一般的通用Hash表(如c++中的hash_map及某些c語言實現的泛型哈希表)有以下不同:
   ● 存儲在glib_htable里的對象由外部而不是內部負責創建,這個對象必須直接或間接地組合了list_head成員(間接組合,包含下文中的glib_hentry即可),這里引用UML中的術語組合,意在強調不是聚合關系。
   ● 刪除操作的語義是從Hash表移去對象的鏈接,但釋放對象是可選的。 
   ● 桶的個數由外部指定而不是內部維護。
   綜上可見glib_htable是使用對象已存在的內嵌成員list_head來鏈接到Hash表中的,比一般的通用Hash表,每個表項節省了1個指針的空間,如下圖所示。

結構定義
 1struct 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抽象了存儲對象的內嵌成員,表示Hash項,也可表示整個對象,這時內嵌成員就是對象本身了,成員data表示對象關聯的任意數據,用于計算hash值,當關聯數據大小<=sizeof(void*)時,可直接強制轉換為data存儲,而不必為數據地址。
   2)glib_htable抽象了Hash表,size表示桶個數,考慮到size可能很多,需要占用大塊內存,所以在分配連續物理頁失敗的情況下,再使用vmalloc嘗試分配不連續的物理頁,所以引入了vmalloced表示分配方式,非零表示用vmalloc,零則用__get_free_pages;hashfun和cmpfun是實現Hash表的兩個缺一不可的關鍵函數,cbfun用于查找成功時的回調處理,如打印、增加引用計數等,freefun用于釋放對象,提供這個回調接口是為了方便從Hash表移除對象后可以釋放對象,而不必由外部釋放,增加了靈活性。

主要接口
   以下所有操作中的第1參數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表桶的個數,hashfun為Hash函數,cmpfun為比較函數;成功時返回0,ht成員cbfun和freefun設置為空,失敗返回ENOMEM。由于可能使用vmalloc分配內存,因此不能用于中斷上下文。

   ● 增加       
void glib_htable_add(struct glib_htable *ht, struct glib_hentry *he, int num);
   在一次同步內添加多個對象,he為指向對象Hash項的指針,num為個數。

   ● 查找   
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為對象關聯數據,cmp為自定義的比較函數,arg為cmp所帶的自定義參數,bucket為桶索引,若查找成功,則bucket更新為對象所在的桶索引。以上所有操作,當失敗時返回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個按對象關聯數據刪除,num表示個數,若ht成員freefun非空,則釋放對象。

   ● 清空   
void glib_htable_clear(struct glib_htable *ht);
   在一次同步內刪除所有的對象,若ht成員freefun非空,則釋放對象。

   ● 銷毀   
void glib_htable_free(struct glib_htable *ht);
    僅釋放所有桶占用的內存,應在glib_htable_clear后調用。由于可能使用vfree釋放內存,因此不能用于中斷上下文。

接口實現
   其它接口實現比較簡單,略過講解。對于查找接口,如果增加一個參數來指示遍歷方向,那么雖然接口總數減半,但在使用特別是在一個循環內調用時,每次都進行不必要的方向判斷而降低了性能,所以對于正向和反向遍歷,每個都給出一個接口,正如c庫中的strchr與strrchr、c++容器中的iterator與reverse_iterator,這樣一來更清晰明確。在實現上除了遍歷方向不同外,其它代碼都相同,因此為避免手工編碼冗余,使用了3組宏來生成。
   輔助函數宏生成   
 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個不加鎖的函數,用于實現對應的加鎖接口。glib_htable_list_get和glib_htable_list_rget分別是宏list_for_each_entry和list_for_each_entry_reverse的別名。

   普通查找宏生成   
 1#define DEFINE_GLIB_HTABLE_GET(name) \
 2struct glib_hentry* glib_htable_##name(struct glib_htable *ht, const void *data) \
 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_##name(ht, h, data); \
 9     read_unlock_bh(&ht->lock); \
10\
11    return he; \
12}

13
14DEFINE_GLIB_HTABLE_GET(get)
15DEFINE_GLIB_HTABLE_GET(rget)
    調用輔助函數__glib_htable_get(rget)實現,生成宏為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)
    前者調用輔助函數__glib_htable_cget(rget)實現,生成宏為DEFINE_GLIB_HTABLE_COND_GET,展開后就有了glib_htable_cget(rget)接口;后者調用輔助函數__glib_htable_cget(rget)_byidx實現,生成宏為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 春秋十二月 閱讀(2231) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美aⅴ99久久黑人专区| 中文久久精品| 亚洲黄一区二区| 欧美日韩在线视频一区| 亚洲在线一区| 欧美成人69av| 久久精品国产96久久久香蕉| 午夜亚洲视频| 国产综合视频在线观看| 欧美精品免费看| 欧美a级一区二区| 亚洲少妇在线| 亚洲电影免费在线观看| 久久综合九色综合欧美狠狠| 亚洲在线免费视频| 亚洲国产精品一区| 国产精品久久午夜夜伦鲁鲁| 欧美不卡视频一区| 欧美精品免费看| 国产精品一区在线观看你懂的| 国产精品乱码人人做人人爱| 国产精品专区h在线观看| 国产精品日韩| 国产精品久久久久影院色老大| 国产精品久久久久久av下载红粉| 国产精品毛片高清在线完整版| 国产精品看片你懂得| 国产精品夜夜夜| 精品99一区二区| 国产精品五区| 亚洲卡通欧美制服中文| 久久久久综合| 在线视频日韩精品| 午夜精品福利一区二区三区av| 久久久综合网| 国产欧美va欧美va香蕉在| 影音先锋久久久| 亚洲无吗在线| 久久激情一区| 亚洲国产精品一区二区久| 欧美国产1区2区| 欧美日韩第一区| aa日韩免费精品视频一| 一区二区三区四区五区视频| 欧美精品在线视频| 99国产一区| 亚洲三级电影在线观看| 巨乳诱惑日韩免费av| 国产精品一区二区三区观看| 日韩视频免费在线| 亚洲国产高清在线| 久久久久免费视频| 国产麻豆综合| 亚洲一区不卡| 亚洲九九九在线观看| 久久久噜噜噜久久人人看| 亚洲美女毛片| 亚洲小说欧美另类婷婷| 国产精品高潮粉嫩av| 亚洲综合另类| 久久爱www久久做| 在线成人激情黄色| 欧美激情综合色| 国产精品xxxxx| 午夜精品久久久久久久99热浪潮| 91久久极品少妇xxxxⅹ软件| 国产精品午夜在线观看| 久久久久久黄| 免费国产一区二区| 亚洲美女91| 欧美不卡视频一区发布| 欧美美女福利视频| 亚洲小说区图片区| 亚洲欧美一区二区三区极速播放| 国产精品欧美一区二区三区奶水| 国产亚洲精品久久久久婷婷瑜伽| 中文亚洲视频在线| 亚洲一品av免费观看| 欧美精品免费在线观看| 欧美制服丝袜| 欧美激情一区二区三区在线| 久久国产精品久久久久久| 一区二区日韩| 亚洲欧洲日产国码二区| 午夜电影亚洲| 一区二区三区国产| 久久九九国产| 欧美亚洲在线播放| 欧美成人在线网站| 欧美成人资源| 亚洲黑丝一区二区| 久久精品卡一| 欧美成人dvd在线视频| 国产精品国产三级国产专播精品人| 欧美激情性爽国产精品17p| 狠狠色综合日日| 欧美影视一区| 午夜一区二区三区在线观看| 在线视频日韩精品| 亚洲国产高清高潮精品美女| 亚洲素人一区二区| 一区二区三区在线视频免费观看 | 亚洲免费观看视频| 欧美日韩国产色综合一二三四 | 国产精品久久久久久久午夜片| 亚洲永久在线| 亚洲一区黄色| 亚洲午夜一区二区| 亚洲国产欧美一区二区三区同亚洲 | 亚洲免费影视| 91久久精品一区二区三区| 欧美日韩免费网站| 久久精品久久综合| 日韩图片一区| 久久女同精品一区二区| 亚洲人成在线播放| 国产伦精品一区| 欧美国产日韩在线| 亚洲欧美激情视频| 亚洲综合欧美| 一本色道久久综合精品竹菊 | 在线观看视频一区| 欧美激情第3页| 欧美专区亚洲专区| 日韩亚洲欧美成人一区| 欧美中文在线观看国产| 欧美另类在线观看| 国产精品国产精品| 国产精品高潮呻吟久久av无限| 欧美电影免费| 蜜桃av久久久亚洲精品| 久久九九免费| 亚洲自拍另类| 亚洲国产小视频在线观看| 午夜精品网站| 久久久99国产精品免费| 欧美α欧美αv大片| 欧美韩国日本综合| 欧美国产精品v| 亚洲国产一区二区精品专区| 欧美成人网在线| 极品少妇一区二区| 亚洲国产视频一区二区| 影音先锋久久久| 亚洲一区二区三区三| 亚洲欧美视频一区| 久久riav二区三区| 亚洲国产一区二区在线| av成人老司机| 99视频日韩| 欧美高清影院| 国产精品r级在线| 亚洲国产一区二区精品专区| 久久免费视频在线| 午夜精品一区二区三区四区| 欧美激情国产日韩精品一区18| 永久555www成人免费| 欧美午夜视频在线| 国产精品高清网站| 亚洲精品免费电影| 欧美激情亚洲| 免费一级欧美片在线播放| 国产一级一区二区| 亚洲综合成人婷婷小说| 一区二区国产日产| 国产精品久久国产三级国电话系列| 亚洲黄一区二区| 亚洲国产成人久久综合一区| 亚洲国产精品123| 久久综合一区| 欧美成人一区二区| 亚洲香蕉网站| 一本一本久久a久久精品综合麻豆| 欧美在线视频a| 久久天天躁狠狠躁夜夜爽蜜月| 精品动漫3d一区二区三区免费版 | 亚洲电影天堂av| 六月丁香综合| 亚洲欧美区自拍先锋| 亚洲一区精品视频| 一区二区欧美在线观看| 在线视频日韩| 亚洲高清色综合| 亚洲人体一区| 国产精品视频免费观看www| 久久久综合激的五月天| 久久美女艺术照精彩视频福利播放| 精品二区视频| 亚洲人精品午夜| 国产欧美日韩三级| 久久久久这里只有精品| 美女日韩在线中文字幕| 久久夜色精品国产噜噜av| 欧美一级理论片| 久久精品亚洲一区二区三区浴池| 国产精品网站在线观看| 久久五月天婷婷| 亚洲精品资源| 欧美一区二区精品| 黄色成人在线网站|