|
xhash是jabberd2的哈希表, 并提供了迭代器用于遍歷xhash.
解釋一下結(jié)構(gòu)體的命名, xht_struct意思是x hash tasble, xhn_struct意思是x hash node, 這樣方便理解記憶. xhn_struct的成員變量顧名思義, 不贅述. xht_struct中, p是內(nèi)存池, 負(fù)責(zé)node的分配等, zen是桶數(shù)組, free_list是回收的node內(nèi)存, iter_bucket和iter_node被用于記錄迭代器的位置.  typedef struct xhn_struct { struct xhn_struct *next; struct xhn_struct *prev; const char *key; int keylen; void *val; } *xhn, _xhn; typedef struct xht_struct { pool_t p; int prime; int dirty; int count; struct xhn_struct *zen; struct xhn_struct *free_list; // list of zaped elements to be reused. int iter_bucket; xhn iter_node; int *stat; } *xht, _xht; JABBERD2_API xht xhash_new(int prime); JABBERD2_API void xhash_put(xht h, const char *key, void *val); JABBERD2_API void xhash_putx(xht h, const char *key, int len, void *val); JABBERD2_API void *xhash_get(xht h, const char *key); JABBERD2_API void *xhash_getx(xht h, const char *key, int len); JABBERD2_API void xhash_zap(xht h, const char *key); JABBERD2_API void xhash_zapx(xht h, const char *key, int len); JABBERD2_API void xhash_stat(xht h); JABBERD2_API void xhash_free(xht h); typedef void (*xhash_walker)(const char *key, int keylen, void *val, void *arg); JABBERD2_API void xhash_walk(xht h, xhash_walker w, void *arg); JABBERD2_API int xhash_dirty(xht h); JABBERD2_API int xhash_count(xht h); JABBERD2_API pool_t xhash_pool(xht h); /* iteration functions */ JABBERD2_API int xhash_iter_first(xht h); JABBERD2_API int xhash_iter_next(xht h); JABBERD2_API void xhash_iter_zap(xht h); JABBERD2_API int xhash_iter_get(xht h, const char **key, int *keylen, void **val); 首先是二進(jìn)制哈希函數(shù), 會(huì)根據(jù)一段內(nèi)存算出哈希值. /* Generates a hash code for a string. * This function uses the ELF hashing algorithm as reprinted in * Andrew Binstock, "Hashing Rehashed," Dr. Dobb's Journal, April 1996. */ static int _xhasher(const char *s, int len) { /* ELF hash uses unsigned chars and unsigned arithmetic for portability */ const unsigned char *name = (const unsigned char *)s; unsigned long h = 0, g; int i; for(i=0;i<len;i++) { /* do some fancy bitwanking on the string */ h = (h << 4) + (unsigned long)(name[i]); if ((g = (h & 0xF0000000UL))!=0) h ^= (g >> 24); h &= ~g; } return (int)h; } xhash_new創(chuàng)建了一個(gè)預(yù)分配內(nèi)存的pool, 尺寸滿足了創(chuàng)建哈希桶數(shù)組以及哈希表自身, Prime是哈希桶的個(gè)數(shù), 從命名來(lái)看作者希望傳入的prime是素?cái)?shù), 但這在實(shí)現(xiàn)上來(lái)說(shuō)并不是必須的. xht xhash_new(int prime) { xht xnew; pool_t p; /* log_debug(ZONE,"creating new hash table of size %d",prime); */ /** * NOTE: * all xhash's memory should be allocated from the pool by using pmalloco()/pmallocx(), * so that the xhash_free() can just call pool_free() simply. */ p = pool_heap(sizeof(_xhn)*prime + sizeof(_xht)); xnew = pmalloco(p, sizeof(_xht)); xnew->prime = prime; xnew->p = p; xnew->zen = pmalloco(p, sizeof(_xhn)*prime); /* array of xhn size of prime */ xnew->free_list = NULL; xnew->iter_bucket = -1; xnew->iter_node = NULL; #ifdef XHASH_DEBUG xnew->stat = pmalloco(p, sizeof(int)*prime ); #else xnew->stat = NULL; #endif return xnew; } 釋放xhash則直接釋放pool即可, 這一點(diǎn)不必多說(shuō)... void xhash_free(xht h) { /* log_debug(ZONE,"hash free %X",h); */ /// want to do more things? Please see the note in xhash_new() first. if(h) pool_free(h->p); } 分配node采用的如下方法: 在實(shí)現(xiàn)上可能有一點(diǎn)迷惑性, 需要注意到哈希桶是實(shí)實(shí)在在分配了內(nèi)存的數(shù)組, 而不是指針數(shù)組, 所以創(chuàng)建一個(gè)新的node時(shí), 會(huì)先檢查哈希桶那個(gè)Node是否被使用了, 如果沒(méi)有使用則直接返回給用戶使用. 否則, 需要另外獲取一個(gè)新的Node, 此時(shí)優(yōu)先檢查free_list, 沒(méi)有free_list則pmalloc重新分配一個(gè)node, 之后將該node插入到哈希桶的第一個(gè)結(jié)點(diǎn)之后(第一個(gè)結(jié)點(diǎn)是靜態(tài)分配的). 另外, 哈希桶鏈表是雙向的. static xhn _xhash_node_new(xht h, int index) { xhn n; int i = index % h->prime; /* track total */ h->count++; #ifdef XHASH_DEBUG h->stat[i]++; #endif // if the zen[i] is empty, reuse it, else get a new one. n = &h->zen[i]; if( n->key != NULL ) { if( h->free_list ) { n = h->free_list; h->free_list = h->free_list->next; }else n = pmalloco(h->p, sizeof(_xhn)); //add it to the bucket list head. n->prev = &h->zen[i]; n->next = h->zen[i].next; if( n->next ) n->next->prev = n; h->zen[i].next = n; } return n; } 下面的函數(shù)給定哈希值index, 將會(huì)定位到特定的哈希桶里順序查找給定的key, 特別注意到, n->key != NULL 的判斷, 一方面哈希桶的第一個(gè)node用key = NULL來(lái)表示未被使用, 另一方面, 當(dāng)刪除一個(gè)正在被迭代器指向的node時(shí), 為了不影響接下來(lái)的迭代, 也會(huì)令key=NULL來(lái)表示刪除.  static xhn _xhash_node_get(xht h, const char *key, int len, int index) { xhn n; int i = index % h->prime; for(n = &h->zen[i]; n != NULL; n = n->next) if(n->key != NULL && (n->keylen==len) && (strncmp(key, n->key, len) == 0)) return n; return NULL; } 插入一個(gè)元素到哈希表, 采用如下接口: 先_xhasher計(jì)算出key的哈希值index, 之后_xhash_node_get查找該key是否已經(jīng)存在,如果已存在則直接替換其中的內(nèi)容即可返回. 如果不存在, 則分配一個(gè)node(從free_list 或者 pool 中), 賦值其中的內(nèi)容即可. 兩個(gè)接口的區(qū)別就是: 后者調(diào)用前者, 前者支持指定key的長(zhǎng)度, 但實(shí)際上, 我發(fā)現(xiàn)這個(gè)哈希表只能支持字符串key, 因?yàn)開(kāi)xhash_node_get里竟然用的是strncmp, 并且xhash_put里也是strlen計(jì)算的key長(zhǎng)度. void xhash_putx(xht h, const char *key, int len, void *val) { int index; xhn n; if(h == NULL || key == NULL) return; index = _xhasher(key,len); /* dirty the xht */ h->dirty++; /* if existing key, replace it */ if((n = _xhash_node_get(h, key, len, index)) != NULL) { /* log_debug(ZONE,"replacing %s with new val %X",key,val); */ n->key = key; n->keylen = len; n->val = val; return; } /* log_debug(ZONE,"saving %s val %X",key,val); */ /* new node */ n = _xhash_node_new(h, index); n->key = key; n->keylen = len; n->val = val; } void xhash_put(xht h, const char *key, void *val) { if(h == NULL || key == NULL) return; xhash_putx(h,key,strlen(key),val); } 查詢更加簡(jiǎn)單, 內(nèi)部調(diào)用了上面的_xhash_node_get, 并做了一些參數(shù)校驗(yàn). void *xhash_getx(xht h, const char *key, int len) { xhn n; if(h == NULL || key == NULL || len <= 0 || (n = _xhash_node_get(h, key, len, _xhasher(key,len))) == NULL) { /* log_debug(ZONE,"failed lookup of %s",key); */ return NULL; } /* log_debug(ZONE,"found %s returning %X",key,n->val); */ return n->val; } void *xhash_get(xht h, const char *key) { if(h == NULL || key == NULL) return NULL; return xhash_getx(h,key,strlen(key)); } 刪除一個(gè)指定的key: 后者調(diào)用前者, 主要是操縱雙向鏈表, 并且需要照顧到迭代器是否指向了要?jiǎng)h除的node. 如果要?jiǎng)h除的node不是哈希桶的那個(gè)靜態(tài)結(jié)點(diǎn)(不需要?jiǎng)h除, key=NULL就可以表示刪除了), 并且也不是當(dāng)前迭代到的結(jié)點(diǎn), 那么就移除并插到free_list頭部. 對(duì)于哈希桶第一個(gè)靜態(tài)Node與被迭代器指向的Node, 作者簡(jiǎn)單的令key=NULL表示刪除, 僅此而已. void xhash_zap_inner( xht h, xhn n, int index) { int i = index % h->prime; // if element:n is in bucket list and it's not the current iter if( &h->zen[i] != n && h->iter_node != n ) { if(n->prev) n->prev->next = n->next; if(n->next) n->next->prev = n->prev; // add it to the free_list head. n->prev = NULL; n->next = h->free_list; h->free_list = n; } //empty the value. n->key = NULL; n->val = NULL; /* dirty the xht and track the total */ h->dirty++; h->count--; #ifdef XHASH_DEBUG h->stat[i]--; #endif } void xhash_zapx(xht h, const char *key, int len) { xhn n; int index; if( !h || !key ) return; index = _xhasher(key,len); n = _xhash_node_get(h, key, len, index); if( !n ) return; /* log_debug(ZONE,"zapping %s",key); */ xhash_zap_inner(h ,n, index ); } 下面是一些比較雜的函數(shù), 其中xhash_dirty返回的dirty值是在每次插入與刪除node時(shí)+1的, 在這里還看不出它的具體用途. /** return the dirty flag (and reset) */ int xhash_dirty(xht h) { int dirty; if(h == NULL) return 1; dirty = h->dirty; h->dirty = 0; return dirty; } /** return the total number of entries in this xht */ int xhash_count(xht h) { if(h == NULL) return 0; return h->count; } /** get our pool */ pool_t xhash_pool(xht h) { return h->p; } xhash提供了一個(gè)遍歷哈希表的接口, 允許用戶指定回調(diào)函數(shù)與自定義數(shù)據(jù), 原理很簡(jiǎn)單: void xhash_walk(xht h, xhash_walker w, void *arg) { int i; xhn n; if(h == NULL || w == NULL) return; /* log_debug(ZONE,"walking %X",h); */ for(i = 0; i < h->prime; i++) for(n = &h->zen[i]; n != NULL; n = n->next) if(n->key != NULL && n->val != NULL) (*w)(n->key, n->keylen, n->val, arg); } 剩下的是迭代器: 迭代器一方面提供了傳統(tǒng)的迭代訪問(wèn)元素的方式, 另一方面其內(nèi)部也在迭代的過(guò)程中回收了那些Key=NULL 或者val=NULL的正常node, 這些node是因?yàn)樯弦淮蔚^(guò)程中zap刪除迭代器指向的node引起的, 在這次迭代過(guò)程中將被回收到free_list中. 初始化迭代器: 令iter_bucket和iter_node為初始化狀態(tài), 前者表示當(dāng)前迭代哪個(gè)桶, 后者表示迭代哪個(gè)結(jié)點(diǎn). 最后會(huì)調(diào)用xhash_iter_next將迭代器挪到第一個(gè)Node. /** iteration */ int xhash_iter_first(xht h) { if(h == NULL) return 0; h->iter_bucket = -1; h->iter_node = NULL; return xhash_iter_next(h); } 令迭代器前進(jìn): 先讓迭代node指向下一個(gè)node, 如果node為空, 那么說(shuō)明當(dāng)前的桶內(nèi)沒(méi)有node了, 必須迭代下一個(gè)哈希桶, 并在新的桶內(nèi)找到一個(gè)key!=NULL&&val!=NULL的Node. 如果當(dāng)前桶內(nèi)還有剩余node, 那么令迭代node(iter_node)指向下一個(gè)node, 這里有一個(gè)while循環(huán), 目的是因?yàn)榭赡艿膎ode是之前被半刪除的node, 這里會(huì)將它們回收到free_list中, 或者遇到一個(gè)key!=NULL&val!=NULL的Node則返回. 注:此處可以看出為什么初始化迭代器設(shè)置iter_node =NULL, iter_bucket= -1的原因. int xhash_iter_next(xht h) { if(h == NULL) return 0; /* next in this bucket */ h->iter_node = h->iter_node ? h->iter_node->next : NULL; while(h->iter_node != NULL) { xhn n = h->iter_node; if(n->key != NULL && n->val != NULL) return 1; h->iter_node = n->next; if (n != &h->zen[h->iter_bucket]) { if(n->prev) n->prev->next = n->next; if(n->next) n->next->prev = n->prev; // add it to the free_list head. n->prev = NULL; n->next = h->free_list; h->free_list = n; } } /* next bucket */ for(h->iter_bucket++; h->iter_bucket < h->prime; h->iter_bucket++) { h->iter_node = &h->zen[h->iter_bucket]; while(h->iter_node != NULL) { if(h->iter_node->key != NULL && h->iter_node->val != NULL) return 1; h->iter_node = h->iter_node->next; } } /* there is no next */ h->iter_bucket = -1; h->iter_node = NULL; return 0; } 剩下的是刪除迭代器指向的Node: 此處不會(huì)真正的刪除該Node, 只會(huì)令key =NULL, 并在下一輪新的迭代過(guò)程中被發(fā)現(xiàn)并回收到free_list. 之所以不刪除是因?yàn)闀?huì)影響接下來(lái)的迭代, 作者這樣實(shí)現(xiàn)迭代器的刪除并不是不能實(shí)現(xiàn)的更直接, 而是一種對(duì)C++ map迭代器類似的原則, 將迭代器正確操作的責(zé)任交給使用者. void xhash_iter_zap(xht h) { int index; if( !h || !h->iter_node ) return; index = _xhasher( h->iter_node->key, h->iter_node->keylen ); xhash_zap_inner( h ,h->iter_node, index); } 最后一個(gè)接口, 允許用戶獲取當(dāng)前迭代器指向node的key和val, 傳入的都是指針的地址: 這里嚴(yán)格判斷, 一個(gè)空的容器的迭代器永遠(yuǎn)iter_node = NULL, 所以要判斷仔細(xì). 下面就是把用戶需要的內(nèi)容返回給用戶. int xhash_iter_get(xht h, const char **key, int *keylen, void **val) { if(h == NULL || (key == NULL && val == NULL) || (key != NULL && keylen == NULL)) return 0; if(h->iter_node == NULL) { if(key != NULL) *key = NULL; if(val != NULL) *val = NULL; return 0; } if(key != NULL) { *key = h->iter_node->key; *keylen = h->iter_node->keylen; } if(val != NULL) *val = h->iter_node->val; return 1; }
在xhash的插入操作中, 并沒(méi)有看到預(yù)想的pstrdup(key)的操作, 作者將key的副本生成的責(zé)任交給了用戶自己, 而xhash內(nèi)部的pool只負(fù)責(zé)分配xht, xhn的內(nèi)存. |
|
|
來(lái)自： 水木天涯閣 > 《jabberd2》
