Libevent源码分析-----event_io_map哈希表

爱被打了一巴掌 2022-05-09 06:06 174阅读 0赞

[ 上一篇博客][Link 1]说到了TAILQ\_QUEUE队列，它可以把多个event结构体连在一起。是一种归类方式。本文也将讲解一种将event归类、连在一起的结构：哈希结构。

# 哈希结构体： #

哈希结构由下面几个结构体一起配合工作：

struct event_list
    
    {
    
    struct event *tqh_first;
    
    struct event **tqh_last;
    
    };
    
    
    struct evmap_io {
    
    //TAILQ_HEAD (event_list, event);
    
    struct event_list events;
    
    ev_uint16_t nread;
    
    ev_uint16_t nwrite;
    
    };
    
    
    struct event_map_entry {
    
    HT_ENTRY(event_map_entry) map_node; //next指针
    
    evutil_socket_t fd;
    
    union { /* This is a union in case we need to make more things that can
    
    be in the hashtable. */
    
    struct evmap_io evmap_io;
    
    } ent;
    
    };
    
    
    struct event_io_map
    
    {
    
    //哈希表
    
    struct event_map_entry **hth_table;
    
    //哈希表的长度
    
    unsigned hth_table_length;
    
    //哈希的元素个数
    
    unsigned hth_n_entries;
    
    //resize 之前可以存多少个元素
    
    //在event_io_map_HT_GROW函数中可以看到其值为hth_table_length的
    
    //一半。但hth_n_entries>=hth_load_limit时，就会发生增长哈希表的长度
    
    unsigned hth_load_limit;
    
    //后面素数表中的下标值。主要是指明用到了哪个素数
    
    int hth_prime_idx;
    
    };

结构体event\_io\_map指明了哈希表的存储位置、哈希表的长度、元素个数等数据。该哈希表是使用链地址法解决冲突问题的，这一点可以从hth\_talbe成员变量看到。它是一个二级指针，因为哈希表的元素是event\_map\_entry指针。

除了怎么解决哈希冲突外，哈希表还有一个问题要解决，那就是哈希函数。这里的哈希函数就是模(%)。用event\_map\_entry结构体中的fd成员值模 event\_io\_map结构体中的hth\_table\_length。

由上面那些结构体配合得到的哈希表结构如下图所示：

![SouthEast][]

从上图可以看到，两个发生了冲突的哈希表元素event\_map\_entry用一个next指向连在一起了(链地址解决冲突)。

另外，从图或者从前面关于event\_map\_entry结构体的定义可以看到，它有一个evmap\_io结构体。而这个evmap\_io结构体又有一个struct event\_list 类型的成员，而struct event\_list类型就是一个TAILQ\_HEAD。这正是[前一篇博客][Link 1]说到的TAILQ\_QUEUE队列的队列头。从这一点可以看到，这个哈希结构还是比较复杂的。

为什么在哈希表的元素里面，还会有一个TAILQ\_QUEUE队列呢？这得由Libevent的一个特征说起。Libevent允许用同一个文件描述符fd或者信号值，调用event\_new、event\_add多次。所以，同一个fd或者信号值就可以对应多个event结构体了。所以这个TAILQ\_QUEUE队列就是将这些具有相同fd或者信号值的多个event结构体连一起。

# 什么情况会使用哈希表： #

有一点需要说明，那就是Libevent中的哈希表只会用于Windows系统，像遵循POSIX标准的OS是不会用到哈希表的。从下面的定义可以看到这一点。

//event-internal.h文件
    
    #ifdef WIN32
    
    /* If we're on win32, then file descriptors are not nice low densely packed
    
    integers. Instead, they are pointer-like windows handles, and we want to
    
    use a hashtable instead of an array to map fds to events.
    
    */
    
    #define EVMAP_USE_HT
    
    #endif
    
    
    
    #ifdef EVMAP_USE_HT
    
    #include "ht-internal.h"
    
    struct event_map_entry;
    
    HT_HEAD(event_io_map, event_map_entry);
    
    #else
    
    #define event_io_map event_signal_map
    
    #endif

可以看到，如果是非Windows系统，那么event\_io\_map就会被定义成event\_signal\_map(这是一个很简单的结构)。而在Windows系统，那么就由HT\_HEAD这个宏定义event\_io\_map。最后得到的event\_io\_map就是本文最前面所示的那样。

为什么只有在Windows系统才会使用这个哈希表呢？代码里面的注释给出了一些解释。因为在Windows系统里面，文件描述符是一个比较大的值，不适合放到event\_signal\_map结构中。而通过哈希(模上一个小的值)，就可以变得比较小，这样就可以放到哈希表的数组中了。而遵循POSIX标准的文件描述符是从0开始递增的，一般都不会太大，适用于event\_signal\_map。

# 哈希函数： #

前面说到哈希函数是 用文件描述符fd 模 哈希表的长度。实际上，并不是直接用fd，而是用一个叫hashsocket的函数将这个fd进行一些处理后，才去模 哈希表的长度。下面是hashsocket函数的实现：

//evmap.c文件
    
    /* Helper used by the event_io_map hashtable code; tries to return a good hash
    
    * of the fd in e->fd. */
    
    static inline unsigned
    
    hashsocket(struct event_map_entry *e)
    
    {
    
    /* On win32, in practice, the low 2-3 bits of a SOCKET seem not to
    
    * matter. Our hashtable implementation really likes low-order bits,
    
    * though, so let's do the rotate-and-add trick. */
    
    unsigned h = (unsigned) e->fd;
    
    h += (h >> 2) | (h << 30);
    
    return h;
    
    }

前面的event\_map\_entry结构体中，还有一个HT\_ENTRY的宏。从名字来看，它是一个哈希表的表项。它是一个条件宏，定义如下：

//ht-internal.h文件
    
    #ifdef HT_CACHE_HASH_VALUES
    
    #define HT_ENTRY(type) \
    
    struct { \
    
    struct type *hte_next; \
    
    unsigned hte_hash; \
    
    }
    
    #else
    
    #define HT_ENTRY(type) \
    
    struct { \
    
    struct type *hte_next; \
    
    }
    
    #endif

可以看到，如果定义了HT\_CACHE\_HASH\_VALUES宏，那么就会多一个hte\_hash变量。从宏的名字来看，这是一个cache。不错，变量hte\_hash就是用来存储前面的hashsocket的返回值。当第一次计算得到后，就存放到hte\_hash变量中。以后需要用到(会经常用到)，就直接向这个变量要即可，无需再次计算hashsocket函数。如果没有这个变量，那么需要用到这个值，都要调用hashsocket函数计算一次。这一点从后面的代码可以看到。

# 哈希表操作函数： #

ht-internal.h文件里面定义了一系列的哈希函数的操作函数。下来就列出这些函数。如果打开ht-internal.h文件，就发现，它是宏的天下。该文件的函数都是由宏定义生成的。下面就贴出宏定义展开后的函数。同前一篇博文那样，是用gcc的-E选项展开的。下面的代码比较长，要有心理准备。

struct event_list
    
    {
    
    struct event *tqh_first;
    
    struct event **tqh_last;
    
    };
    
    
    struct evmap_io
    
    {
    
    struct event_list events;
    
    ev_uint16_t nread;
    
    ev_uint16_t nwrite;
    
    };
    
    
    
    struct event_map_entry
    
    {
    
    struct
    
    {
    
    struct event_map_entry *hte_next;
    
    #ifdef HT_CACHE_HASH_VALUES
    
    unsigned hte_hash;
    
    #endif
    
    }map_node;
    
    
    evutil_socket_t fd;
    
    union
    
    {
    
    struct evmap_io evmap_io;
    
    }ent;
    
    };
    
    
    struct event_io_map
    
    {
    
    //哈希表
    
    struct event_map_entry **hth_table;
    
    //哈希表的长度
    
    unsigned hth_table_length;
    
    //哈希的元素个数
    
    unsigned hth_n_entries;
    
    //resize 之前可以存多少个元素
    
    //在event_io_map_HT_GROW函数中可以看到其值为hth_table_length的
    
    //一半。但hth_n_entries>=hth_load_limit时，就会发生增长哈希表的长度
    
    unsigned hth_load_limit;
    
    //后面素数表中的下标值。主要是指明用到了哪个素数
    
    int hth_prime_idx;
    
    };
    
    
    
    
    int event_io_map_HT_GROW(struct event_io_map *ht, unsigned min_capacity);
    
    void event_io_map_HT_CLEAR(struct event_io_map *ht);
    
    
    int _event_io_map_HT_REP_IS_BAD(const struct event_io_map *ht);
    
    
    //初始化event_io_map
    
    static inline void event_io_map_HT_INIT(struct event_io_map *head)
    
    {
    
    head->hth_table_length = 0;
    
    head->hth_table = NULL;
    
    head->hth_n_entries = 0;
    
    head->hth_load_limit = 0;
    
    head->hth_prime_idx = -1;
    
    }
    
    
    
    //在event_io_map这个哈希表中，找个表项elm
    
    //在下面还有一个相似的函数，函数名少了最后的_P。那个函数的返回值
    
    //是event_map_entry *。从查找来说，后面那个函数更适合。之所以
    
    //有这个函数，是因为哈希表还有replace、remove这些操作。对于
    
    //A->B->C这样的链表。此时，要replace或者remove节点B。
    
    //如果只有后面那个查找函数，那么只能查找并返回一个指向B的指针。
    
    //此时将无法修改A的next指针了。所以本函数有存在的必要。
    
    //在本文件中，很多函数都使用了event_map_entry **。
    
    //因为event_map_entry **类型变量，既可以修改本元素的hte_next变量
    
    //也能指向下一个元素。
    
    
    //该函数返回的是查找节点的前驱节点的hte_next成员变量的地址。
    
    //所以返回值肯定不会为NULL,但是对返回值取*就可能为NULL
    
    static inline struct event_map_entry **
    
    _event_io_map_HT_FIND_P(struct event_io_map *head,
    
    struct event_map_entry *elm)
    
    {
    
    struct event_map_entry **p;
    
    if (!head->hth_table)
    
    return NULL;
    
    
    #ifdef HT_CACHE_HASH_VALUES
    
    p = &((head)->hth_table[((elm)->map_node.hte_hash)
    
    % head->hth_table_length]);
    
    #else
    
    p = &((head)->hth_table[(hashsocket(*elm))%head->hth_table_length]);
    
    #endif
    
    
    //这里的哈希表是用链地址法解决哈希冲突的。
    
    //上面的 % 只是找到了冲突链的头。现在是在冲突链中查找。
    
    while (*p)
    
    {
    
    //判断是否相等。在实现上，只是简单地根据fd来判断是否相等
    
    if (eqsocket(*p, elm))
    
    return p;
    
    
    //p存放的是hte_next成员变量的地址
    
    p = &(*p)->map_node.hte_next;
    
    }
    
    
    return p;
    
    }
    
    
    /* Return a pointer to the element in the table 'head' matching 'elm',
    
    * or NULL if no such element exists */
    
    //在event_io_map这个哈希表中，找个表项elm
    
    static inline struct event_map_entry *
    
    event_io_map_HT_FIND(const struct event_io_map *head,
    
    struct event_map_entry *elm)
    
    {
    
    struct event_map_entry **p;
    
    struct event_io_map *h = (struct event_io_map *) head;
    
    
    #ifdef HT_CACHE_HASH_VALUES
    
    do
    
    { //计算哈希值
    
    (elm)->map_node.hte_hash = hashsocket(elm);
    
    } while(0);
    
    #endif
    
    
    p = _event_io_map_HT_FIND_P(h, elm);
    
    return p ? *p : NULL;
    
    }
    
    
    
    /* Insert the element 'elm' into the table 'head'. Do not call this
    
    * function if the table might already contain a matching element. */
    
    static inline void
    
    event_io_map_HT_INSERT(struct event_io_map *head,
    
    struct event_map_entry *elm)
    
    {
    
    struct event_map_entry **p;
    
    if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit)
    
    event_io_map_HT_GROW(head, head->hth_n_entries+1);
    
    
    ++head->hth_n_entries;
    
    
    #ifdef HT_CACHE_HASH_VALUES
    
    do
    
    { //计算哈希值.此哈希不同于用%计算的简单哈希。
    
    //存放到hte_hash变量中，作为cache
    
    (elm)->map_node.hte_hash = hashsocket(elm);
    
    } while (0);
    
    
    p = &((head)->hth_table[((elm)->map_node.hte_hash)
    
    % head->hth_table_length]);
    
    #else
    
    p = &((head)->hth_table[(hashsocket(*elm))%head->hth_table_length]);
    
    #endif
    
    
    
    //使用头插法，即后面才插入的链表，反而会在链表头。
    
    elm->map_node.hte_next = *p;
    
    *p = elm;
    
    }
    
    
    
    /* Insert the element 'elm' into the table 'head'. If there already
    
    * a matching element in the table, replace that element and return
    
    * it. */
    
    static inline struct event_map_entry *
    
    event_io_map_HT_REPLACE(struct event_io_map *head,
    
    struct event_map_entry *elm)
    
    {
    
    struct event_map_entry **p, *r;
    
    
    if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit)
    
    event_io_map_HT_GROW(head, head->hth_n_entries+1);
    
    
    #ifdef HT_CACHE_HASH_VALUES
    
    do
    
    {
    
    (elm)->map_node.hte_hash = hashsocket(elm);
    
    } while(0);
    
    #endif
    
    
    p = _event_io_map_HT_FIND_P(head, elm);
    
    
    //由前面的英文注释可知，这个函数是替换插入一起进行的。如果哈希表
    
    //中有和elm相同的元素(指的是event_map_entry的fd成员变量值相等)
    
    //那么就发生替代(其他成员变量值不同，所以不是完全相同，有替换意义)
    
    //如果哈希表中没有和elm相同的元素，那么就进行插入操作
    
    
    //指针p存放的是hte_next成员变量的地址
    
    //这里的p存放的是被替换元素的前驱元素的hte_next变量地址
    
    r = *p; //r指向了要替换的元素。有可能为NULL
    
    *p = elm; //hte_next变量被赋予新值elm
    
    
    //找到了要被替换的元素r(不为NULL)
    
    //而且要插入的元素地址不等于要被替换的元素地址
    
    if (r && (r!=elm))
    
    {
    
    elm->map_node.hte_next = r->map_node.hte_next;
    
    
    r->map_node.hte_next = NULL;
    
    return r; //返回被替换掉的元素
    
    }
    
    else //进行插入操作
    
    {
    
    //这里貌似有一个bug。如果前一个判断中，r 不为 NULL，而且r == elm
    
    //对于同一个元素，多次调用本函数。就会出现这样情况。
    
    //此时，将会来到这个else里面
    
    //实际上没有增加元素，但元素的个数却被++了。因为r 的地址等于 elm
    
    //所以 r = *p; *p = elm; 等于什么也没有做。（r == elm)
    
    //当然，因为这些函数都是Libevent内部使用的。如果它保证不会同于同
    
    //一个元素调用本函数，那么就不会出现bug
    
    ++head->hth_n_entries;
    
    return NULL; //插入操作返回NULL，表示没有替换到元素
    
    }
    
    }
    
    
    
    /* Remove any element matching 'elm' from the table 'head'. If such
    
    * an element is found, return it; otherwise return NULL. */
    
    static inline struct event_map_entry *
    
    event_io_map_HT_REMOVE(struct event_io_map *head,
    
    struct event_map_entry *elm)
    
    {
    
    struct event_map_entry **p, *r;
    
    
    #ifdef HT_CACHE_HASH_VALUES
    
    do
    
    {
    
    (elm)->map_node.hte_hash = hashsocket(elm);
    
    } while (0);
    
    #endif
    
    
    p = _event_io_map_HT_FIND_P(head,elm);
    
    
    if (!p || !*p)//没有找到
    
    return NULL;
    
    
    //指针p存放的是hte_next成员变量的地址
    
    //这里的p存放的是被替换元素的前驱元素的hte_next变量地址
    
    r = *p; //r现在指向要被删除的元素
    
    *p = r->map_node.hte_next;
    
    r->map_node.hte_next = NULL;
    
    
    --head->hth_n_entries;
    
    
    return r;
    
    }
    
    
    
    /* Invoke the function 'fn' on every element of the table 'head',
    
    using 'data' as its second argument. If the function returns
    
    nonzero, remove the most recently examined element before invoking
    
    the function again. */
    
    static inline void
    
    event_io_map_HT_FOREACH_FN(struct event_io_map *head,
    
    int (*fn)(struct event_map_entry *, void *),
    
    void *data)
    
    {
    
    unsigned idx;
    
    struct event_map_entry **p, **nextp, *next;
    
    
    if (!head->hth_table)
    
    return;
    
    
    for (idx=0; idx < head->hth_table_length; ++idx)
    
    {
    
    p = &head->hth_table[idx];
    
    
    while (*p)
    
    {
    
    //像A->B->C链表。p存放了A元素中hte_next变量的地址
    
    //*p则指向B元素。nextp存放B的hte_next变量的地址
    
    //next指向C元素。
    
    nextp = &(*p)->map_node.hte_next;
    
    next = *nextp;
    
    
    //对B元素进行检查
    
    if (fn(*p, data))
    
    {
    
    --head->hth_n_entries;
    
    //p存放了A元素中hte_next变量的地址
    
    //所以*p = next使得A元素的hte_next变量值被赋值为
    
    //next。此时链表变成A->C。即使抛弃了B元素。不知道
    
    //调用方是否能释放B元素的内存。
    
    *p = next;
    
    }
    
    else
    
    {
    
    p = nextp;
    
    }
    
    }
    
    }
    
    }
    
    
    
    /* Return a pointer to the first element in the table 'head', under
    
    * an arbitrary order. This order is stable under remove operations,
    
    * but not under others. If the table is empty, return NULL. */
    
    //获取第一条冲突链的第一个元素
    
    static inline struct event_map_entry **
    
    event_io_map_HT_START(struct event_io_map *head)
    
    {
    
    unsigned b = 0;
    
    
    while (b < head->hth_table_length)
    
    {
    
    //返回哈希表中，第一个不为NULL的节点
    
    //即有event_map_entry元素的节点。
    
    //找到链。因为是哈希。所以不一定哈希表中的每一个节点都存有元素
    
    if (head->hth_table[b])
    
    return &head->hth_table[b];
    
    
    ++b;
    
    }
    
    
    return NULL;
    
    }
    
    
    
    
    /* Return the next element in 'head' after 'elm', under the arbitrary
    
    * order used by HT_START. If there are no more elements, return
    
    * NULL. If 'elm' is to be removed from the table, you must call
    
    * this function for the next value before you remove it.
    
    */
    
    static inline struct event_map_entry **
    
    event_io_map_HT_NEXT(struct event_io_map *head,
    
    struct event_map_entry **elm)
    
    {
    
    //本哈希解决冲突的方式是链地址
    
    //如果参数elm所在的链地址中，elm还有下一个节点，就直接返回下一个节点
    
    if ((*elm)->map_node.hte_next)
    
    {
    
    return &(*elm)->map_node.hte_next;
    
    }
    
    else //否则取哈希表中的下一条链中第一个元素
    
    {
    
    #ifdef HT_CACHE_HASH_VALUES
    
    unsigned b = (((*elm)->map_node.hte_hash)
    
    % head->hth_table_length) + 1;
    
    #else
    
    unsigned b = ( (hashsocket(*elm)) % head->hth_table_length) + 1;
    
    #endif
    
    
    while (b < head->hth_table_length)
    
    {
    
    //找到链。因为是哈希。所以不一定哈希表中的每一个节点都存有元素
    
    if (head->hth_table[b])
    
    return &head->hth_table[b];
    
    ++b;
    
    }
    
    
    return NULL;
    
    }
    
    }
    
    
    
    
    //功能同上一个函数。只是参数不同，另外本函数还会使得--hth_n_entries
    
    //该函数主要是返回elm的下一个元素。并且哈希表的总元素个数减一。
    
    //主调函数会负责释放*elm指向的元素。无需在这里动手
    
    //在evmap_io_clear函数中，会调用本函数。
    
    static inline struct event_map_entry **
    
    event_io_map_HT_NEXT_RMV(struct event_io_map *head,
    
    struct event_map_entry **elm)
    
    {
    
    #ifdef HT_CACHE_HASH_VALUES
    
    unsigned h = ((*elm)->map_node.hte_hash);
    
    #else
    
    unsigned h = (hashsocket(*elm));
    
    #endif
    
    
    //elm变量变成存放下一个元素的hte_next的地址
    
    *elm = (*elm)->map_node.hte_next;
    
    
    --head->hth_n_entries;
    
    
    if (*elm)
    
    {
    
    return elm;
    
    }
    
    else
    
    {
    
    unsigned b = (h % head->hth_table_length)+1;
    
    
    while (b < head->hth_table_length)
    
    {
    
    if (head->hth_table[b])
    
    return &head->hth_table[b];
    
    
    ++b;
    
    }
    
    
    return NULL;
    
    }
    
    }
    
    
    
    
    //素数表。之所以去素数，是因为在取模的时候，素数比合数更有优势。
    
    //听说是更散，更均匀
    
    static unsigned event_io_map_PRIMES[] =
    
    {
    
    //素数表的元素具有差不多2倍的关系。
    
    //这使得扩容操作不会经常发生。每次扩容都预留比较大的空间
    
    53, 97, 193, 389, 769, 1543, 3079,
    
    6151, 12289, 24593, 49157, 98317,
    
    196613, 393241, 786433, 1572869, 3145739,
    
    6291469, 12582917, 25165843, 50331653, 100663319,
    
    201326611, 402653189, 805306457, 1610612741
    
    };
    
    
    
    //素数表中，元素的个数。
    
    static unsigned event_io_map_N_PRIMES =
    
    (unsigned)(sizeof(event_io_map_PRIMES)
    
    /sizeof(event_io_map_PRIMES[0]));
    
    
    
    /* Expand the internal table of 'head' until it is large enough to
    
    * hold 'size' elements. Return 0 on success, -1 on allocation
    
    * failure. */
    
    int event_io_map_HT_GROW(struct event_io_map *head, unsigned size)
    
    {
    
    unsigned new_len, new_load_limit;
    
    int prime_idx;
    
    
    struct event_map_entry **new_table;
    
    //已经用到了素数表中最后一个素数，不能再扩容了。
    
    if (head->hth_prime_idx == (int)event_io_map_N_PRIMES - 1)
    
    return 0;
    
    
    //哈希表中还够容量，无需扩容
    
    if (head->hth_load_limit > size)
    
    return 0;
    
    
    prime_idx = head->hth_prime_idx;
    
    
    do {
    
    new_len = event_io_map_PRIMES[++prime_idx];
    
    
    //从素数表中的数值可以看到，后一个差不多是前一个的2倍。
    
    //从0.5和后的new_load_limit <= size，可以得知此次扩容
    
    //至少得是所需大小(size)的2倍以上。免得经常要进行扩容
    
    new_load_limit = (unsigned)(0.5*new_len);
    
    } while (new_load_limit <= size
    
    && prime_idx < (int)event_io_map_N_PRIMES);
    
    
    if ((new_table = mm_malloc(new_len*sizeof(struct event_map_entry*))))
    
    {
    
    unsigned b;
    
    memset(new_table, 0, new_len*sizeof(struct event_map_entry*));
    
    
    for (b = 0; b < head->hth_table_length; ++b)
    
    {
    
    struct event_map_entry *elm, *next;
    
    unsigned b2;
    
    
    elm = head->hth_table[b];
    
    while (elm) //该节点有冲突链。遍历冲突链中所有的元素
    
    {
    
    next = elm->map_node.hte_next;
    
    
    //冲突链中的元素，相对于前一个素数同余(即模素数后，结果相当)
    
    //但对于现在的新素数就不一定同余了，即它们不一定还会冲突
    
    //所以要对冲突链中的所有元素都再次哈希，并放到它们应该在的地方
    
    //b2存放了再次哈希后，元素应该存放的节点下标。
    
    #ifdef HT_CACHE_HASH_VALUES
    
    b2 = (elm)->map_node.hte_hash % new_len;
    
    #else
    
    b2 = (hashsocket(*elm)) % new_len;
    
    #endif
    
    //用头插法插入数据
    
    elm->map_node.hte_next = new_table[b2];
    
    new_table[b2] = elm;
    
    
    elm = next;
    
    }
    
    }
    
    
    if (head->hth_table)
    
    mm_free(head->hth_table);
    
    
    head->hth_table = new_table;
    
    }
    
    else
    
    {
    
    unsigned b, b2;
    
    
    //刚才mm_malloc失败，可能是内存不够。现在用更省内存的
    
    //mm_realloc方式。当然其代价就是更耗时(下面的代码可以看到)。
    
    //前面的mm_malloc会同时有hth_table和new_table两个数组。
    
    //而mm_realloc则只有一个数组，所以省内存，省了一个hth_table数组
    
    //的内存。此时，new_table数组的前head->hth_table_length个
    
    //元素存放了原来的冲突链的头部。也正是这个原因导致后面代码更耗时。
    
    //其实，只有在很特殊的情况下，这个函数才会比mm_malloc省内存.
    
    //就是堆内存head->hth_table区域的后面刚好有一段可以用的内存。
    
    //具体的，可以搜一下realloc这个函数。
    
    new_table = mm_realloc(head->hth_table,
    
    new_len*sizeof(struct event_map_entry*));
    
    
    if (!new_table)
    
    return -1;
    
    
    memset(new_table + head->hth_table_length, 0,
    
    (new_len - head->hth_table_length)*sizeof(struct event_map_entry*)
    
    );
    
    
    for (b=0; b < head->hth_table_length; ++b)
    
    {
    
    struct event_map_entry *e, **pE;
    
    
    for (pE = &new_table[b], e = *pE; e != NULL; e = *pE)
    
    {
    
    
    #ifdef HT_CACHE_HASH_VALUES
    
    b2 = (e)->map_node.hte_hash % new_len;
    
    #else
    
    b2 = (hashsocket(*elm)) % new_len;
    
    #endif
    
    //对于冲突链A->B->C.
    
    //pE是二级指针，存放的是A元素的hte_next指针的地址值
    
    //e指向B元素。
    
    
    //对新的素数进行哈希，刚好又在原来的位置
    
    if (b2 == b)
    
    {
    
    //此时，无需修改。接着处理冲突链中的下一个元素即可
    
    //pE向前移动，存放B元素的hte_next指针的地址值
    
    pE = &e->map_node.hte_next;
    
    }
    
    else//这个元素会去到其他位置上。
    
    {
    
    //此时冲突链修改成A->C。
    
    //所以pE无需修改，还是存放A元素的hte_next指针的地址值
    
    //但A元素的hte_next指针要指向C元素。用*pE去修改即可
    
    *pE = e->map_node.hte_next;
    
    
    //将这个元素放到正确的位置上。
    
    e->map_node.hte_next = new_table[b2];
    
    new_table[b2] = e;
    
    }
    
    
    //这种再次哈希的方式，很有可能会对某些元素操作两次。
    
    //当某个元素第一次在else中处理，那么它就会被哈希到正确的节点
    
    //的冲突链上。随着外循环的进行，处理到正确的节点时。在遍历该节点
    
    //的冲突链时，又会再次处理该元素。此时，就会在if中处理。而不会
    
    //进入到else中。
    
    }
    
    }
    
    
    head->hth_table = new_table;
    
    }
    
    
    
    //一般是当hth_n_entries >= hth_load_limit时，就会调用
    
    //本函数。hth_n_entries表示的是哈希表中节点的个数。而hth_load_limit
    
    //是hth_table_length的一半。hth_table_length则是哈希表中
    
    //哈希函数被模的数字。所以，当哈希表中的节点个数到达哈希表长度的一半时
    
    //就会发生增长，本函数被调用。这样的结果是：平均来说，哈希表应该比较少发生
    
    //冲突。即使有，冲突链也不会太长。这样就能有比较快的查找速度。
    
    head->hth_table_length = new_len;
    
    head->hth_prime_idx = prime_idx;
    
    head->hth_load_limit = new_load_limit;
    
    
    return 0;
    
    }
    
    
    
    /* Free all storage held by 'head'. Does not free 'head' itself,
    
    * or individual elements. 并不需要释放独立的元素*/
    
    //在evmap_io_clear函数会调用该函数。其是在删除所有哈希表中的元素后
    
    //才调用该函数的。
    
    void event_io_map_HT_CLEAR(struct event_io_map *head)
    
    {
    
    if (head->hth_table)
    
    mm_free(head->hth_table);
    
    
    head->hth_table_length = 0;
    
    
    event_io_map_HT_INIT(head);
    
    }
    
    
    
    /* Debugging helper: return false iff the representation of 'head' is
    
    * internally consistent. */
    
    int _event_io_map_HT_REP_IS_BAD(const struct event_io_map *head)
    
    {
    
    unsigned n, i;
    
    struct event_map_entry *elm;
    
    
    if (!head->hth_table_length)
    
    {
    
    //刚被初始化，还没申请任何空间
    
    if (!head->hth_table && !head->hth_n_entries
    
    && !head->hth_load_limit && head->hth_prime_idx == -1
    
    )
    
    return 0;
    
    else
    
    return 1;
    
    }
    
    
    if (!head->hth_table || head->hth_prime_idx < 0
    
    || !head->hth_load_limit
    
    )
    
    return 2;
    
    
    if (head->hth_n_entries > head->hth_load_limit)
    
    return 3;
    
    
    if (head->hth_table_length != event_io_map_PRIMES[head->hth_prime_idx])
    
    return 4;
    
    
    if (head->hth_load_limit != (unsigned)(0.5*head->hth_table_length))
    
    return 5;
    
    
    for (n = i = 0; i < head->hth_table_length; ++i)
    
    {
    
    for (elm = head->hth_table[i]; elm; elm = elm->map_node.hte_next)
    
    {
    
    
    #ifdef HT_CACHE_HASH_VALUES
    
    
    if (elm->map_node.hte_hash != hashsocket(elm))
    
    return 1000 + i;
    
    
    if( (elm->map_node.hte_hash % head->hth_table_length) != i)
    
    return 10000 + i;
    
    
    #else
    
    if ( (hashsocket(*elm)) != hashsocket(elm))
    
    return 1000 + i;
    
    
    if( ( (hashsocket(*elm)) % head->hth_table_length) != i)
    
    return 10000 + i;
    
    #endif
    
    ++n;
    
    }
    
    }
    
    
    if (n != head->hth_n_entries)
    
    return 6;
    
    
    return 0;
    
    }

代码中的注释已经对这个哈希表的一些特征进行了描述，这里就不多说了。

# 哈希表在Libevent的使用： #

现在来讲一下event\_io\_map的应用。

在event\_base这个结构体中有一个event\_io\_map类型的成员变量io。它就是一个哈希表。当一个监听读或者写操作的event，调用event\_add函数插入到event\_base中时，就会调用evmap\_io\_add函数。evmap\_io\_add函数应用到这个event\_io\_map结构体。该函数的定义如下，其中使用到了一个宏定义，我已经展开了。

int
    
    evmap_io_add(struct event_base *base, evutil_socket_t fd, struct event *ev)
    
    {
    
    const struct eventop *evsel = base->evsel;
    
    struct event_io_map *io = &base->io;
    
    struct evmap_io *ctx = NULL;
    
    int nread, nwrite, retval = 0;
    
    short res = 0, old = 0;
    
    struct event *old_ev;
    
    
    EVUTIL_ASSERT(fd == ev->ev_fd);
    
    
    if (fd < 0)
    
    return 0;
    
    
    //GET_IO_SLOT_AND_CTOR(ctx, io, fd, evmap_io, evmap_io_init,
    
    // evsel->fdinfo_len);SLOT指的是fd
    
    //GET_IO_SLOT_AND_CTOR宏将展开成下面这个do{}while(0);
    
    do
    
    {
    
    struct event_map_entry _key, *_ent;
    
    _key.fd = fd;
    
    
    struct event_io_map *_ptr_head = io;
    
    struct event_map_entry **ptr;
    
    
    //哈希表扩容，减少冲突的可能性
    
    if (!_ptr_head->hth_table
    
    || _ptr_head->hth_n_entries >= _ptr_head->hth_load_limit)
    
    {
    
    event_io_map_HT_GROW(_ptr_head,
    
    _ptr_head->hth_n_entries + 1);
    
    }
    
    
    #ifdef HT_CACHE_HASH_VALUES
    
    do{
    
    (&_key)->map_node.hte_hash = hashsocket((&_key));
    
    } while(0);
    
    #endif
    
    
    //返回值ptr,是要查找节点的前驱节点的hte_next成员变量的地址.
    
    //所以返回值肯定不会为NULL,而*ptr就可能为NULL。说明hte_next
    
    //不指向任何节点。也正由于这个原因，所以即使*ptr 为NULL,但是可以
    
    //给*ptr赋值。此时，是修改前驱节点的hte_next成员变量的值，使之
    
    //指向另外一个节点。
    
    //这里调用_event_io_map_HT_FIND_P原因有二：1.查看该fd是否已经
    
    //插入过这个哈希表中。2.得到这个fd计算哈希位置。
    
    ptr = _event_io_map_HT_FIND_P(_ptr_head, (&_key));
    
    
    //在event_io_map这个哈希表中查找是否已经存在该fd的event_map_entry了
    
    //因为同一个fd可以调用event_new多次，然后event_add多次的。
    
    if (*ptr)
    
    {
    
    _ent = *ptr;
    
    }
    
    else
    
    {
    
    _ent = mm_calloc(1, sizeof(struct event_map_entry) + evsel->fdinfo_len);
    
    if (EVUTIL_UNLIKELY(_ent == NULL))
    
    return (-1);
    
    
    _ent->fd = fd;
    
    //调用初始化函数初始化这个evmap_io
    
    (evmap_io_init)(&_ent->ent.evmap_io);
    
    
    #ifdef HT_CACHE_HASH_VALUES
    
    do
    
    {
    
    ent->map_node.hte_hash = (&_key)->map_node.hte_hash;
    
    }while(0);
    
    #endif
    
    _ent->map_node.hte_next = NULL;
    
    
    //把这个新建的节点插入到哈希表中。ptr已经包含了哈希位置
    
    *ptr = _ent;
    
    ++(io->hth_n_entries);
    
    }
    
    
    
    //这里是获取该event_map_entry的next和prev指针。因为
    
    //evmap_io含有next、prev变量。这样在之后就可以把这个
    
    //event_map_entry连起来。这个外do{}while(0)的功能是
    
    //为这个fd分配一个event_map_entry,并且插入到现有的哈希
    
    //表中。同时，这个fd还是结构体event的一部分。而event必须
    
    //插入到event队列中。
    
    (ctx) = &_ent->ent.evmap_io;
    
    
    } while (0);
    
    
    
    ....
    
    
    //ctx->events是一个TAILQ_HEAD。结合之前讲到的TAILQ_QUEUE队列，
    
    //就可以知道：同一个fd，可能有多个event结构体。这里就把这些结构体连
    
    //起来。依靠的链表是，event结构体中的ev_io_next。ev_io_next是
    
    //一个TAILQ_ENTRY,具有前驱和后驱指针。队列头部为event_map_entry
    
    //结构体中的evmap_io成员的events成员。
    
    TAILQ_INSERT_TAIL(&ctx->events, ev, ev_io_next);
    
    
    return (retval);
    
    }

GET\_IO\_SLOT\_AND\_CTOR宏的作用就是让ctx指向struct event\_map\_entry结构体中的TAILQ\_HEAD。这样就可以使用TAILQ\_INSERT\_TAIL宏，把ev变量插入到队列中。如果有现成的event\_map\_entry就直接使用，没有的话就新建一个。

[Link 1]: http://blog.csdn.net/luotuo44/article/details/38374009
[SouthEast]: /images/20220509/414c132d7bd340a3b18b5615d7bb8eb6.png