背景：
在偶然的mqtt（mosquitto）中的源码中查看的关于topic的处理，知道了哈希表这种的数据结构，最近花了一点时间将这个部分的源码看了一部分，不知道后面还有没有时间继续查看所以就写一篇文档作为笔记吧。
uthash 使用
uthash 这个开源库使用起来很方便，只有一个头文件（uthash .h），在源代码中只要包含这个头文件就可以进行使用了这个里面的接口
针对使用在网络上能够搜索到的示例代码比较多。这里就是记录一些不一样的地方。
（1）用户结构体
struct my_struct {
char name[10]; /* key (string is WITHIN the structure) */
int id;
UT_hash_handle hh; /* makes this structure hashable */
};
用户定义的结构体中需要包含这个UT_hash_handle,这个元素，这个元素将会在库的内部使用
（2）head
库提供的函数都会有一个head节点，这个实际上也是一个指针，这个指针相当于链表的头或者数组结构体，在这个head添加之后的节点，搜索的时候就只会搜索head下面的节点
源码结构体分析
首先是这个结构体
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;
tbl----存放在数组成员
prev—用户添加的上一个成员
next–该节点之后添加的成员
hh_prev—计算出key的hash冲突的上一个节点
hh_next–hash冲突的下一个节点
key----关键词的内容
keylen—关键词的长度
hashv—关键词的hash结果
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 find hash tables 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;
buckets—数组的地址，存放这个head下面的成员
num_buckets—数组的大小
log2_num_buckets—数组的大小的log
num_items—暂时不清楚
tail----添加的最后一个元素
hho----节点的hh和节点的偏差
UT_hash_handle结构在用户结构中的偏移位置，通过UT_hash_handle对象减去hho定位到用户结构对象
ideal_chain_maxlen—暂时不涉及
nonideal_items—暂时不涉及
.ineff_expands—暂时不涉及
noexpand—暂时不涉及
signature--------0xa0111fe1
typedef struct UT_hash_bucket {
struct UT_hash_handle *hh_head;
unsigned count;
unsigned expand_mult;
} UT_hash_bucket;
UT_hash_handle – 存放节点
count----当前这个位置的节点个数
expand_mult—暂时不涉及
额外的基础知识
typeof的用法
把y定义成x指向的数据类型：
typeof(*x) y;
