国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Swoole 源碼分析——基礎模塊之HashMap

Atom / 3193人閱讀

摘要:的數據結構的數據結構很簡單,就是一個根節點一個迭代器還有一個析構函數比較復雜的地方在于其節點的數據成員,該數據成員是語言庫,大部分功能依賴于這個。

HashMap 的數據結構

HashMap 的數據結構很簡單,就是一個根節點、一個迭代器還有一個析構函數

HashMap 比較復雜的地方在于其節點 swHashMap_nodeUT_hash_handle 數據成員,該數據成員是 C 語言 hashuthash,HashMap 大部分功能依賴于這個 uthash

swHashMap_nodekey_int 是鍵值的長度,key_str 是具體的鍵值,datavalue 數據

typedef void (*swHashMap_dtor)(void *data);

typedef struct
{
    struct swHashMap_node *root;
    struct swHashMap_node *iterator;
    swHashMap_dtor dtor;
} swHashMap;

typedef struct swHashMap_node
{
    uint64_t key_int;
    char *key_str;
    void *data;
    UT_hash_handle hh;
} swHashMap_node;
HashMap

由于 HashMap 是在底層 uthash 哈希表的基礎上構建的,如果想要詳細了解其原理大家可以先看看下一節內容后再閱讀本小節。

HashMap 的初始化

HashMap 的初始化主要是對底層 uthash 哈希表進行內存的分配、初始化

uthash 哈希表的初始化包括 tbl、buckets 的初始化,成員變量的具體意義可以參考下一節內容

swHashMap* swHashMap_new(uint32_t bucket_num, swHashMap_dtor dtor)
{
    swHashMap *hmap = sw_malloc(sizeof(swHashMap));
    if (!hmap)
    {
        swWarn("malloc[1] failed.");
        return NULL;
    }
    swHashMap_node *root = sw_malloc(sizeof(swHashMap_node));
    if (!root)
    {
        swWarn("malloc[2] failed.");
        sw_free(hmap);
        return NULL;
    }

    bzero(hmap, sizeof(swHashMap));
    hmap->root = root;

    bzero(root, sizeof(swHashMap_node));

    root->hh.tbl = (UT_hash_table*) sw_malloc(sizeof(UT_hash_table));
    if (!(root->hh.tbl))
    {
        swWarn("malloc for table failed.");
        sw_free(hmap);
        return NULL;
    }

    memset(root->hh.tbl, 0, sizeof(UT_hash_table));
    root->hh.tbl->tail = &(root->hh);
    root->hh.tbl->num_buckets = SW_HASHMAP_INIT_BUCKET_N;
    root->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2;
    root->hh.tbl->hho = (char*) (&root->hh) - (char*) root;
    root->hh.tbl->buckets = (UT_hash_bucket*) sw_malloc(SW_HASHMAP_INIT_BUCKET_N * sizeof(struct UT_hash_bucket));
    if (!root->hh.tbl->buckets)
    {
        swWarn("malloc for buckets failed.");
        sw_free(hmap);
        return NULL;
    }
    memset(root->hh.tbl->buckets, 0, SW_HASHMAP_INIT_BUCKET_N * sizeof(struct UT_hash_bucket));
    root->hh.tbl->signature = HASH_SIGNATURE;

    hmap->dtor = dtor;

    return hmap;
}
HashMap 的新元素添加

首先需要新建一個 swHashMap_node,為 key_str、key_intdata

將新建的 swHashMap_node 添加到哈希表中

UT_hash_handlerprevnext、key、keylen、hashv、tbl 成員變量賦值,將新的 UT_hash_handler 放入雙向鏈表的尾部,更新 tbltail 成員

利用 HASH_ADD_TO_BKT 函數將 UT_hash_handler 插入到哈希桶中

int swHashMap_add(swHashMap* hmap, char *key, uint16_t key_len, void *data)
{
    swHashMap_node *node = (swHashMap_node*) sw_malloc(sizeof(swHashMap_node));
    if (node == NULL)
    {
        swWarn("malloc failed.");
        return SW_ERR;
    }
    bzero(node, sizeof(swHashMap_node));
    swHashMap_node *root = hmap->root;
    node->key_str = sw_strndup(key, key_len);
    node->key_int = key_len;
    node->data = data;
    return swHashMap_node_add(root, node);
}

static sw_inline int swHashMap_node_add(swHashMap_node *root, swHashMap_node *add)
{
    unsigned _ha_bkt;
    add->hh.next = NULL;
    add->hh.key = add->key_str;
    add->hh.keylen = add->key_int;

    root->hh.tbl->tail->next = add;
    add->hh.prev = ELMT_FROM_HH(root->hh.tbl, root->hh.tbl->tail);
    root->hh.tbl->tail = &(add->hh);

    root->hh.tbl->num_items++;
    add->hh.tbl = root->hh.tbl;
    add->hh.hashv = swoole_hash_jenkins(add->key_str, add->key_int);
    _ha_bkt = add->hh.hashv & (root->hh.tbl->num_buckets - 1);

    HASH_ADD_TO_BKT(root->hh.tbl->buckets[_ha_bkt], &add->hh);

    return SW_OK;
}
swHashMap_add_int 添加 int 類型元素

swHashMap_add_int 直接調用 HASH_ADD_INT 更新整個哈希表,比起 swHashMap_add 函數,沒有了復雜的 uthash 數據結構的更新

int swHashMap_add_int(swHashMap *hmap, uint64_t key, void *data)
{
    swHashMap_node *node = (swHashMap_node*) sw_malloc(sizeof(swHashMap_node));
    swHashMap_node *root = hmap->root;
    if (node == NULL)
    {
        swWarn("malloc failed");
        return SW_ERR;
    }
    node->key_int = key;
    node->data = data;
    node->key_str = NULL;
    HASH_ADD_INT(root, key_int, node);
    return SW_OK;
}
swHashMap_find 查找元素

首先先通過哈希鍵計算哈希值,找出哈希桶的索引

HASH_FIND_IN_BKT 會根據哈希桶來查找具體的元素

void* swHashMap_find(swHashMap* hmap, char *key, uint16_t key_len)
{
    swHashMap_node *root = hmap->root;
    swHashMap_node *ret = swHashMap_node_find(root, key, key_len);
    if (ret == NULL)
    {
        return NULL;
    }
    return ret->data;
}

static sw_inline swHashMap_node *swHashMap_node_find(swHashMap_node *root, char *key_str, uint16_t key_len)
{
    swHashMap_node *out;
    unsigned bucket, hash;
    out = NULL;
    if (root)
    {
        hash = swoole_hash_jenkins(key_str, key_len);
        bucket = hash & (root->hh.tbl->num_buckets - 1);
        HASH_FIND_IN_BKT(root->hh.tbl, hh, (root)->hh.tbl->buckets[bucket], key_str, key_len, out);
    }
    return out;
}
swHashMap_find_int 函數

swHashMap_find_int 函數直接調用 HASH_FIND_INT 查找

void* swHashMap_find_int(swHashMap* hmap, uint64_t key)
{
    swHashMap_node *ret = NULL;
    swHashMap_node *root = hmap->root;
    HASH_FIND_INT(root, &key, ret);
    if (ret == NULL)
    {
        return NULL;
    }
    return ret->data;
}
swHashMap_each 遍歷

swHashMap_each 利用迭代器不斷獲取下一個元素

void* swHashMap_each(swHashMap* hmap, char **key)
{
    swHashMap_node *node = swHashMap_node_each(hmap);
    if (node)
    {
        *key = node->key_str;
        return node->data;
    }
    else
    {
        return NULL;
    }
}

static sw_inline swHashMap_node* swHashMap_node_each(swHashMap* hmap)
{
    swHashMap_node *iterator = hmap->iterator;
    swHashMap_node *tmp;

    if (hmap->root->hh.tbl->num_items == 0)
    {
        return NULL;
    }
    if (iterator == NULL)
    {
        iterator = hmap->root;
    }
    tmp = iterator->hh.next;
    if (tmp)
    {
        hmap->iterator = tmp;
        return tmp;
    }
    else
    {
        hmap->iterator = NULL;
        return NULL;
    }
}
swHashMap_count 函數
uint32_t swHashMap_count(swHashMap* hmap)
{
    if (hmap == NULL)
    {
        return 0;
    }
    return HASH_COUNT(hmap->root);
}
swHashMap_del 刪除元素

刪除元素首先需要 swHashMap_node_delete 函數來重構哈希表,然后調用 swHashMap_node_free 釋放內存

int swHashMap_del(swHashMap* hmap, char *key, uint16_t key_len)
{
    swHashMap_node *root = hmap->root;
    swHashMap_node *node = swHashMap_node_find(root, key, key_len);
    if (node == NULL)
    {
        return SW_ERR;
    }
    swHashMap_node_delete(root, node);
    swHashMap_node_free(hmap, node);
    return SW_OK;
}

static sw_inline void swHashMap_node_free(swHashMap *hmap, swHashMap_node *node)
{
    swHashMap_node_dtor(hmap, node);
    sw_free(node->key_str);
    sw_free(node);
}

刪除重構哈希表流程較為復雜,步驟和 HASH_DELETE 函數邏輯一致,詳細可以看下一節

static int swHashMap_node_delete(swHashMap_node *root, swHashMap_node *del_node)
{
    unsigned bucket;
    struct UT_hash_handle *_hd_hh_del;

    if ((del_node->hh.prev == NULL) && (del_node->hh.next == NULL))
    {
        sw_free(root->hh.tbl->buckets);
        sw_free(root->hh.tbl);
    }
    else
    {
        _hd_hh_del = &(del_node->hh);
        if (del_node == ELMT_FROM_HH(root->hh.tbl, root->hh.tbl->tail))
        {
            root->hh.tbl->tail = (UT_hash_handle*) ((ptrdiff_t) (del_node->hh.prev) + root->hh.tbl->hho);
        }
        if (del_node->hh.prev)
        {
            ((UT_hash_handle*) ((ptrdiff_t) (del_node->hh.prev) + root->hh.tbl->hho))->next = del_node->hh.next;
        }
        else
        {
            DECLTYPE_ASSIGN(root, del_node->hh.next);
        }
        if (_hd_hh_del->next)
        {
            ((UT_hash_handle*) ((ptrdiff_t) _hd_hh_del->next + root->hh.tbl->hho))->prev = _hd_hh_del->prev;
        }
        HASH_TO_BKT(_hd_hh_del->hashv, root->hh.tbl->num_buckets, bucket);
        HASH_DEL_IN_BKT(hh, root->hh.tbl->buckets[bucket], _hd_hh_del);
        root->hh.tbl->num_items--;
    }
    return SW_OK;
}
swHashMap_del_int 函數

swHashMap_del_int 函數沒有復雜邏輯,直接調用了 HASH_DEL 這個第三方庫

int swHashMap_del_int(swHashMap *hmap, uint64_t key)
{
    swHashMap_node *ret = NULL;
    swHashMap_node *root = hmap->root;

    HASH_FIND_INT(root, &key, ret);
    if (ret == NULL)
    {
        return SW_ERR;
    }
    HASH_DEL(root, ret);
    swHashMap_node_free(hmap, ret);
    return SW_OK;
}
swHashMap_free 銷毀哈希表

銷毀哈希表需要循環所有的哈希節點元素,逐個刪除

HASH_ITER 用于循環所有的哈希節點元素

void swHashMap_free(swHashMap* hmap)
{
    swHashMap_node *find, *tmp = NULL;
    swHashMap_node *root = hmap->root;
    HASH_ITER(hh, root, find, tmp)
    {
        if (find == root) continue;
        swHashMap_node_delete(root, find);
        swHashMap_node_free(hmap, find);
    }

    sw_free(hmap->root->hh.tbl->buckets);
    sw_free(hmap->root->hh.tbl);
    sw_free(hmap->root);

    sw_free(hmap);
}
uthash 哈希表

uthash 是使用開鏈法實現的哈希表,其代碼均是宏函數編寫,首先我們先看看這個哈希表的數據結構:

uthash 由三種數據結構構成:UT_hash_table、UT_hash_bucket、UT_hash_handle

UT_hash_table

UT_hash_table 是整個哈希表的核心,UT_hash_bucket 是根據哈希值排列的數組,UT_hash_handle 是開鏈法中哈希沖突的鏈表

從上圖可以清楚的看出來 UT_hash_table 的數據結構:

buckets 是哈希桶數組的首地址;num_buckets 是哈希桶的數量;log2_num_bucketslog2(num_buckets) 的值

tail 是哈希鏈表的最后那個元素地址;num_items 是哈希鏈表的元素個數

hho:成員變量 UT_hash_handle 相對于用戶結構體首部的位置

ideal_chain_maxlen :在理想情況下,即所有的元素剛好平坦到每個 buckets 指向的鏈表中,任何兩個鏈表的數目相差不超過1時,一個鏈表中能夠容納的元素數目,實際上就等于 num_items / num_buckets + (num_items % num_buckets == 0 ? 0 : 1);

nonideal_items :實際上 buckets 的數目超過 ideal_chain_maxlen 的鏈表數;

noexpand:當這個值為1時,永遠不會對 buckets 的大小進行擴充

ineff_expands:當某個 buckets 的鏈表過長時,需要對 buckets 指向的數組的大小進行擴充,然后對整個鏈表重新分配各自的哈希桶;擴張后如果 nonideal_items 仍然大于 num_items 的一半時,也就是說明當前哈希表嚴重不平衡,哈希沖突很嚴重,這個時候說明當前的鍵值有問題,或者哈希算法有問題,并不是擴充 buckets 數組能夠解決的。這個時候,就會遞增 ineff_expands 的值,當 ineff_expands 大于 1 的時候,就會設置 noexpand 設置為 1,永遠不會擴充 buckets 的大小。

bloom_bv:指向一個 uint8_t 類型的數組,用來標記 buckets 中每個鏈表是否為空,可以優化查找的速度,因為這個數組中每個元素是一個字節,所以每個元素可以標記8個鏈表,例如要判斷 bucket[1]->hh_head 是否為空,只要判斷(bloom_bv[0] & 2) 是否為0即可;

bloom_nbitsbloom_bv 指向的數組大小為 (1 << bloom_nbits)。

typedef struct UT_hash_table {
   UT_hash_bucket *buckets;
   unsigned num_buckets, log2_num_buckets;
   unsigned num_items;
   struct UT_hash_handle *tail;
   ptrdiff_t hho; 

   unsigned ideal_chain_maxlen;

   unsigned nonideal_items;

   unsigned ineff_expands, noexpand;

   uint32_t signature; /* used only to test bloom exists in external analysis */
   
   #ifdef HASH_BLOOM
   uint32_t bloom_sig; /* used only to test bloom exists in external analysis */
   uint8_t *bloom_bv;
   char bloom_nbits;
#endif

} UT_hash_table;
UT_hash_handle

UT_hash_handle 是存儲數據的真正地方,也是哈希表的最小結構單元,如下圖,不同于一般的開鏈法,只有在哈希沖突的時候才會將兩個元素用鏈表連接起來,uthash 哈希表將所有 UT_hash_handle 元素構成了兩種雙向鏈表

prevnext 構成的雙向鏈表將所有 UT_hash_handle 元素都連接到了一起,這個是為了能夠快速的訪問所有的數據,

hh_prev、hh_next將所有哈希沖突的、哈希值相同的元素歸并到了一起

key、keylen 是存儲的鍵值與長度,hashv 是鍵值的哈希值

tbl 是上一小節的 UT_hash_table

typedef struct UT_hash_handle {
   struct UT_hash_table *tbl;
   void *prev;                       /* prev element in app order      */
   void *next;                       /* next element in app order      */
   struct UT_hash_handle *hh_prev;   /* previous hh in bucket order    */
   struct UT_hash_handle *hh_next;   /* next hh in bucket order        */
   void *key;                        /* ptr to enclosing struct"s key  */
   unsigned keylen;                  /* enclosing struct"s key len     */
   unsigned hashv;                   /* result of hash-fcn(key)        */
} UT_hash_handle;

UT_hash_bucket

哈希桶是哈希表非常重要的成員,位于同一個哈希桶內的 UT_hash_handle 元素擁有相同的哈希值 hashv,不過這種概率很小。

由于 buckets 指向的數組可能比較?。ǔ跏贾禐?2,這個值一定是2的指數次方),所以會先對 UT_hash_handle 元素 中的 hashv 進行一次按位與操作 (idx = (hashv & (num_buckets-1))),然后被插入到 buckets[idx]->hh_head 指向的雙向鏈表中

count: hh_head 指向的鏈表中的元素數目;

expand_mult:當 count 的值大于 (expand_mult+1)*10 時,則對 buckets 指向的數組的大小進行擴充;在擴充之后 expand_mult 被設定為 count / ideal_chain_maxlen

typedef struct UT_hash_bucket {
   struct UT_hash_handle *hh_head;
   unsigned count;
   
   unsigned expand_mult;

} UT_hash_bucket;
ELMT_FROM_HH 函數

我們之前說 UT_hash_handle 元素構成了兩套雙向鏈表,prev、next 構成了其中一套,但是確切地說 prev、next 指向的地址并不是 UT_hash_handle 的地址,而是它的上一層。例如我們之前說的:

typedef struct swHashMap_node
{
    uint64_t key_int;
    char *key_str;
    void *data;
    UT_hash_handle hh;
} swHashMap_node;

prev、next 指向的地址實際是 swHashMap_node 的地址,這個 swHashMap_nodeUT_hash_handle 之間還有用戶自定義的 header 數據,這個數據的大小就是 UT_hash_tablehho 成員變量的值。

ELMT_FROM_HH 就是通過 UT_hash_handle 的地址反算 swHashMap_node 地址的函數:

#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho)))
HASH_TO_BKT 函數

HASH_TO_BKT 函數根據哈希值計算哈希桶的索引值,因為哈希值會很大,必然要轉為哈希桶數組的 index

#define HASH_TO_BKT( hashv, num_bkts, bkt )                                      
do {                                                                             
  bkt = ((hashv) & ((num_bkts) - 1));                                            
} while(0)
HASH_MAKE_TABLE 函數

HASH_MAKE_TABLE 函數用于創建 UT_hash_table

#define HASH_MAKE_TABLE(hh,head)                                                 
do {                                                                             
  (head)->hh.tbl = (UT_hash_table*)uthash_malloc(                                
                  sizeof(UT_hash_table));                                        
  if (!((head)->hh.tbl))  { uthash_fatal( "out of memory"); }                    
  memset((head)->hh.tbl, 0, sizeof(UT_hash_table));                              
  (head)->hh.tbl->tail = &((head)->hh);                                          
  (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS;                        
  (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2;              
  (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head);                    
  (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc(                      
          HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket));               
  if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); }             
  memset((head)->hh.tbl->buckets, 0,                                             
          HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket));               
  HASH_BLOOM_MAKE((head)->hh.tbl);                                               
  (head)->hh.tbl->signature = HASH_SIGNATURE;                                    
} while(0)
HASH_ADD_TO_BKT 函數

HASH_ADD_TO_BKT 函數用于向 UT_hash_bucket 中添加新的 UT_hash_handle 元素

head 是通過哈希已經計算好的哈希桶,addhh 是要新添加的 UT_hash_handle 元素

新添加的元素會替換哈希桶的 hh_head

如果當前哈希桶中的 UT_hash_handle 元素數量過多,就會考慮擴充 UT_hash_bucket 的數量,并且重新分配

/* add an item to a bucket  */
#define HASH_ADD_TO_BKT(head,addhh)                                              
do {                                                                             
 head.count++;                                                                   
 (addhh)->hh_next = head.hh_head;                                                
 (addhh)->hh_prev = NULL;                                                        
 if (head.hh_head) { (head).hh_head->hh_prev = (addhh); }                        
 (head).hh_head=addhh;                                                           
 if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH)             
     && (addhh)->tbl->noexpand != 1) {                                           
       HASH_EXPAND_BUCKETS((addhh)->tbl);                                        
 }                                                                               
} while(0)
HASH_EXPAND_BUCKETS 函數

HASH_EXPAND_BUCKETS 函數用于擴充哈希桶的數量

每次擴充都會增長一倍,并且重新計算 ideal_chain_maxlen

遍歷所有的 UT_hash_handle 元素,并且根據他們的 hashv 重新計算它們歸屬的哈希桶的索引,并將其放入新的哈希桶中

更新 UT_hash_tablenum_buckets、log2_num_buckets

重新計算 nonideal_items 值,如果大于元素的一半,說明哈希沖突仍然嚴重,哈希桶的擴容并不能解決問題,那么就將 ineff_expands 遞增,必要的時候禁止哈希桶的擴容

#define HASH_EXPAND_BUCKETS(tbl)                                                 
do {                                                                             
    unsigned _he_bkt;                                                            
    unsigned _he_bkt_i;                                                          
    struct UT_hash_handle *_he_thh, *_he_hh_nxt;                                 
    UT_hash_bucket *_he_new_buckets, *_he_newbkt;                                
    _he_new_buckets = (UT_hash_bucket*)uthash_malloc(                            
             2 * tbl->num_buckets * sizeof(struct UT_hash_bucket));              
    if (!_he_new_buckets) { uthash_fatal( "out of memory"); }                    
    memset(_he_new_buckets, 0,                                                   
            2 * tbl->num_buckets * sizeof(struct UT_hash_bucket));               
    tbl->ideal_chain_maxlen =                                                    
       (tbl->num_items >> (tbl->log2_num_buckets+1)) +                           
       ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0);                    
    tbl->nonideal_items = 0;                                                     
    for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++)                
    {                                                                            
        _he_thh = tbl->buckets[ _he_bkt_i ].hh_head;                             
        while (_he_thh) {                                                        
           _he_hh_nxt = _he_thh->hh_next;                                        
           HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt);            
           _he_newbkt = &(_he_new_buckets[ _he_bkt ]);                           
           if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) {                
             tbl->nonideal_items++;                                              
             _he_newbkt->expand_mult = _he_newbkt->count /                       
                                        tbl->ideal_chain_maxlen;                 
           }                                                                     
           _he_thh->hh_prev = NULL;                                              
           _he_thh->hh_next = _he_newbkt->hh_head;                               
           if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev =               
                _he_thh;                                                         
           _he_newbkt->hh_head = _he_thh;                                        
           _he_thh = _he_hh_nxt;                                                 
        }                                                                        
    }                                                                            
    uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); 
    tbl->num_buckets *= 2;                                                       
    tbl->log2_num_buckets++;                                                     
    tbl->buckets = _he_new_buckets;                                              
    tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ?         
        (tbl->ineff_expands+1) : 0;                                              
    if (tbl->ineff_expands > 1) {                                                
        tbl->noexpand=1;                                                         
        uthash_noexpand_fyi(tbl);                                                
    }                                                                            
    uthash_expand_fyi(tbl);                                                      
} while(0)
HASH_ADD_INT 函數

HASH_ADD_INT 函數是 HASH_ADD_TO_BKTint 特例

首先判斷當前哈希表是否存在,如果不存在,那么就用 HASH_MAKE_TABLE 創建一個哈希表

如果哈希表存在,那么就將 UT_hash_handle 放入雙向鏈表表尾

利用 HASH_FCN 計算哈希值,并利用 HASH_ADD_TO_BKT 將其放入對應的哈希桶中

HASH_BLOOM_ADD 函數為 bloom_bv 設置位,用于快速判斷當前 hashv 值存在元素

#define HASH_ADD_INT(head,intfield,add)                                          
    HASH_ADD(hh,head,intfield,sizeof(int),add)
    
#define HASH_ADD(hh,head,fieldname,keylen_in,add)                                
    HASH_ADD_KEYPTR(hh,head,&((add)->fieldname),keylen_in,add)
    
#define HASH_BLOOM_ADD(tbl,hashv)                                                
  HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1)))
  
#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8)))
        
#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add)                            
do {                                                                             
 unsigned _ha_bkt;                                                               
 (add)->hh.next = NULL;                                                          
 (add)->hh.key = (char*)(keyptr);                                                
 (add)->hh.keylen = (unsigned)(keylen_in);                                       
 if (!(head)) {                                                                  
    head = (add);                                                                
    (head)->hh.prev = NULL;                                                      
    HASH_MAKE_TABLE(hh,head);                                                    
 } else {                                                                        
    (head)->hh.tbl->tail->next = (add);                                          
    (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail);         
    (head)->hh.tbl->tail = &((add)->hh);                                         
 }                                                                               
 (head)->hh.tbl->num_items++;                                                    
 (add)->hh.tbl = (head)->hh.tbl;                                                 
 HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets,                         
         (add)->hh.hashv, _ha_bkt);                                              
 HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh);                   
 HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv);                                 
 HASH_EMIT_KEY(hh,head,keyptr,keylen_in);                                        
 HASH_FSCK(hh,head);                                                             
} while(0)        
HASH_FIND_IN_BKT 函數

HASH_FIND_IN_BKT 用于根據 keyptrhead 哈希桶中尋找 UT_hash_handle

DECLTYPE_ASSIGN 用于轉化 out 為用戶自定義的數據類型(也就是 swHashMap_node

不斷循環 hh_next、hh_pre 組成的雙向鏈表,找出與 keyptr 相同的元素

#define HASH_KEYCMP(a,b,len) memcmp(a,b,len) 

#define DECLTYPE(x) (__typeof(x))
#endif

#define DECLTYPE_ASSIGN(dst,src)                                                 
do {                                                                             
  (dst) = DECLTYPE(dst)(src);                                                    
} while(0)
#endif

#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out)                       
do {                                                                             
 if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head));          
 else out=NULL;                                                                  
 while (out) {                                                                   
    if ((out)->hh.keylen == keylen_in) {                                           
        if ((HASH_KEYCMP((out)->hh.key,keyptr,keylen_in)) == 0) break;             
    }                                                                            
    if ((out)->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,(out)->hh.hh_next)); 
    else out = NULL;                                                             
 }                                                                               
} while(0)
HASH_FIND_INT 函數

HASH_FIND_INT 函數是上一個函數的特殊化,專門查找 int 類型的鍵值

HASH_FCN 實際上是 Jenkins 哈希算法,用于計算哈希值

HASH_BLOOM_TEST 用于快速判斷哈希桶內到底有沒有元素,如果沒有那么沒有必要進行下去

#define HASH_FIND_INT(head,findint,out)                                          
    HASH_FIND(hh,head,findint,sizeof(int),out)
    
#define HASH_FCN HASH_JEN
#endif

#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8)))

#define HASH_BLOOM_TEST(tbl,hashv)                                               
  HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1)))
    
#define HASH_FIND(hh,head,keyptr,keylen,out)                                     
do {                                                                             
  unsigned _hf_bkt,_hf_hashv;                                                    
  out=NULL;                                                                      
  if (head) {                                                                    
     HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt);   
     if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) {                           
       HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ],  
                        keyptr,keylen,out);                                      
     }                                                                           
  }                                                                              
} while (0)

HASH_COUNT 函數

HASH_COUNT 函數用于計算所有元素的數量

#define HASH_COUNT(head) HASH_CNT(hh,head) 
#define HASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0)
HASH_DEL_IN_BKT 函數

HASH_DEL_IN_BKT 函數用于刪除已知的哈希桶的某一個鏈表元素

#define HASH_DEL_IN_BKT(hh,head,hh_del)                                          
    (head).count--;                                                              
    if ((head).hh_head == hh_del) {                                              
      (head).hh_head = hh_del->hh_next;                                          
    }                                                                            
    if (hh_del->hh_prev) {                                                       
        hh_del->hh_prev->hh_next = hh_del->hh_next;                              
    }                                                                            
    if (hh_del->hh_next) {                                                       
        hh_del->hh_next->hh_prev = hh_del->hh_prev;                              
    }   
HASH_DEL 函數

HASH_DEL 函數也是刪除哈希表中的元素,但是不同于上一個小節 HASH_DEL_IN_BKT 函數,這個函數不需要知道元素落在了哪個哈希桶中

HASH_DEL 函數如果發現當前要刪除的是哈希表唯一的元素,這個函數還好進一步刪除整個哈希表,這一特性與 HASH_ADD 對應

HASH_DEL 函數不僅更新了哈希桶的鏈表結構,還更新了 UT_hash_handle 雙向鏈表結構和 UT_hash_tabletail 成員變量

HASH_DEL 函數最后利用了 HASH_DEL_IN_BKT 函數更新哈希桶的鏈表數據

#define HASH_DEL(head,delptr)                                                    
    HASH_DELETE(hh,head,delptr)
    
#define HASH_DELETE(hh,head,delptr)                                              
do {                                                                             
    unsigned _hd_bkt;                                                            
    struct UT_hash_handle *_hd_hh_del;                                           
    if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) )  {         
        uthash_free((head)->hh.tbl->buckets,                                     
                    (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); 
        HASH_BLOOM_FREE((head)->hh.tbl);                                         
        uthash_free((head)->hh.tbl, sizeof(UT_hash_table));                      
        head = NULL;                                                             
    } else {                                                                     
        _hd_hh_del = &((delptr)->hh);                                            
        if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) {     
            (head)->hh.tbl->tail =                                               
                (UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) +               
                (head)->hh.tbl->hho);                                            
        }                                                                        
        if ((delptr)->hh.prev) {                                                 
            ((UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) +                  
                    (head)->hh.tbl->hho))->next = (delptr)->hh.next;             
        } else {                                                                 
            DECLTYPE_ASSIGN(head,(delptr)->hh.next);                             
        }                                                                        
        if (_hd_hh_del->next) {                                                  
            ((UT_hash_handle*)((ptrdiff_t)_hd_hh_del->next +                     
                    (head)->hh.tbl->hho))->prev =                                
                    _hd_hh_del->prev;                                            
        }                                                                        
        HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt);   
        HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del);        
        (head)->hh.tbl->num_items--;                                             
    }                                                                            
    HASH_FSCK(hh,head);                                                          
} while (0)
HASH_ITER 函數

HASH_ITER 函數用于循環所有的哈希表的元素

#define HASH_ITER(hh,head,el,tmp)                                                
for((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL);                 
   el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL))
#endif
哈希算法

swoole_hash_php 算法

static inline uint64_t swoole_hash_php(char *key, uint32_t len)
{
    register ulong_t hash = 5381;
    /* variant with the hash unrolled eight times */
    for (; len >= 8; len -= 8)
    {
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
    }

    switch (len)
    {
        case 7: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        /* no break */
        case 6: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        /* no break */
        case 5: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        /* no break */
        case 4: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        /* no break */
        case 3: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        /* no break */
        case 2: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        /* no break */
        case 1: hash = ((hash << 5) + hash) + *key++; break;
        case 0: break;
        default: break;
    }
    return hash;
}

swoole_hash_austin 算法

static inline uint32_t swoole_hash_austin(char *key, unsigned int keylen)
{
    unsigned int h, k;
    h = 0 ^ keylen;

    while (keylen >= 4)
    {
        k  = key[0];
        k |= key[1] << 8;
        k |= key[2] << 16;
        k |= key[3] << 24;

        k *= 0x5bd1e995;
        k ^= k >> 24;
        k *= 0x5bd1e995;

        h *= 0x5bd1e995;
        h ^= k;

        key += 4;
        keylen -= 4;
    }

    switch (keylen)
    {
    case 3:
        h ^= key[2] << 16;
        /* no break */
    case 2:
        h ^= key[1] << 8;
        /* no break */
    case 1:
        h ^= key[0];
        h *= 0x5bd1e995;
    }

    h ^= h >> 13;
    h *= 0x5bd1e995;
    h ^= h >> 15;

    return h;
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/29219.html

相關文章

  • Swoole 源碼分析——基礎模塊 Heap 堆

    摘要:中是數據堆的權重,也是數據堆排序的依據,是其在數據堆中的位置。改變數據的權重改變了數據節點的權重之后,需要重新進行堆排序,將數據節點向上提升,或者將數據向下調整。 前言 heap 堆是 swoole 實現定時器最重要的數據結構,定時器將各個定時任務按照其下一次執行的時間構建最小堆,快速進行插入與刪除。 heap 數據結構 heap 中 num 是現有數據堆的數量,size 是數據堆的...

    callmewhy 評論0 收藏0
  • Swoole 源碼分析——基礎模塊Queue隊列

    摘要:消息隊列的接受消息隊列的接受是利用函數,其中是消息的類型,該參數會取出指定類型的消息,如果設定的是爭搶模式,該值會統一為,否則該值就是消息發送目的的。環形隊列的消息入隊發送消息首先要確定環形隊列的隊尾。取模操作可以優化 前言 swoole 的底層隊列有兩種:進程間通信 IPC 的消息隊列 swMsgQueue,與環形隊列 swRingQueue。IPC 的消息隊列用于 task_wor...

    jollywing 評論0 收藏0
  • Swoole 源碼分析——基礎模塊 Channel 隊列

    摘要:前言內存數據結構,類似于的通道,底層基于共享內存互斥鎖實現,可實現用戶態的高性能內存隊列。是當前隊列占用的內存大小,用來指定是否使用共享內存是否使用鎖是否使用通知。 前言 內存數據結構 Channel,類似于 Go 的 chan 通道,底層基于 共享內存 + Mutex 互斥鎖實現,可實現用戶態的高性能內存隊列。Channel 可用于多進程環境下,底層在讀取寫入時會自動加鎖,應用層不需...

    txgcwm 評論0 收藏0
  • Swoole 源碼分析——內存模塊共享內存

    摘要:前言我們知道,由于沒有多線程模型,所以更多的使用多進程模型,因此代碼相對來說更加簡潔,減少了各種線程鎖的阻塞與同步,但是也帶來了新的問題數據同步。相比多線程之前可以直接共享進程的內存,進程之間數據的相互同步依賴于共享內存。 前言 我們知道,由于 PHP 沒有多線程模型,所以 swoole 更多的使用多進程模型,因此代碼相對來說更加簡潔,減少了各種線程鎖的阻塞與同步,但是也帶來了新的問題...

    diabloneo 評論0 收藏0
  • Swoole 源碼分析——基礎模塊 Pipe 管道

    摘要:并沒有使用命名管道。的創建創建匿名管道就是調用函數,程序自動設置管道為非阻塞式。函數同樣的獲取管道文件描述符根據來決定。模塊負責為進程創建與。當線程啟動的時候,會將加入的監控當中。 前言 管道是進程間通信 IPC 的最基礎的方式,管道有兩種類型:命名管道和匿名管道,匿名管道專門用于具有血緣關系的進程之間,完成數據傳遞,命名管道可以用于任何兩個進程之間。swoole 中的管道都是匿名管道...

    Tikitoo 評論0 收藏0

發表評論

0條評論

Atom

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<