frr底层中hash表的不同之处
这里用到的hash表也是传统的数组桶链方式，有几点不同，同样也很精妙的点：
1：数组每个元素不是单纯一个指针，也是一个桶元素。并且只有数组上的桶元素会记录该桶所在的链上所有桶的个数。为了描述方便，直接将数组元素上的桶联合挂在该桶上的所有桶统称为桶链。
2：hash表主体结构维护有一些很有价值的数据，例如，
2.1 max_size，hash表数组的最大长度，避免表无上限扩容；
2.2 count，已分配内存的桶个数，也是hash表中挂载数据的个数，也便于分析相关内存分配的问题；
2.3 hashstats中的数据，尤其是ssq，每次hash节点变动都会修改，记录了整个表的过程动态变化，从一个过程的角度来评定hash函数的好坏
数据结构
//hash主体的结构
struct hash {/* Hash bucket. */struct hash_bucket **index; //桶链的hash表/* Hash table size. Must be power of 2 */ //2的幂能够保证hash_key%size == hash_key&(size-1)，提高计算效率unsigned int size; //hash表数组的长度/* If max_size is 0 there is no limit */unsigned int max_size; //hash数组长度的限制，扩容时会用/* Key make function. */unsigned int (*hash_key)(const void *); //hash函数/* Data compare function. */bool (*hash_cmp)(const void *, const void *); //查找和跟新桶里数据会用到的比较回调函数/* Backet alloc. */unsigned long count; //已分配内存的桶个数struct hashstats stats;/* hash name */char *name;
};//用于计算负载，慢负载和标准差等一系列评定hash函数的参数
struct hashstats {/* number of empty hash buckets */atomic_uint_fast32_t empty; //空数组元素的个数/* sum of squares of bucket length */atomic_uint_fast32_t ssq; //记录hash表每次跟新桶的过程负载因子//用于评定hash函数的优劣
};struct hash_bucket {/** if this bucket is the head of the linked listed, len denotes the* number of elements in the list*///只有链首的桶中记录非0值，也是该链上所有桶的总个数，以此值区分链首与链上其他桶节点int len; //记录的桶个数/* Linked list. */struct hash_bucket *next;/* Hash key. */unsigned int key; //经hash函数计算过多的key值/* Data. */void *data; //挂在桶上的数据
};
函数
1：hash扩容
/* Expand hash if the chain length exceeds the threshold. */
static void hash_expand(struct hash *hash)
{unsigned int i, new_size;struct hash_bucket *hb, *hbnext, **new_index;new_size = hash->size * 2;//max_size 为0则不作最大长度限制if (hash->max_size && new_size > hash->max_size)return;new_index = XCALLOC(MTYPE_HASH_INDEX,sizeof(struct hash_bucket *) * new_size);hash->stats.empty = new_size;//遍历数组上每个桶链for (i = 0; i < hash->size; i++)//遍历每个链表for (hb = hash->index[i]; hb; hb = hbnext) {unsigned int h = hb->key & (new_size - 1); //要处理的桶元素hbnext = hb->next; //记录下一个桶元素hb->next = new_index[h]; //旧表中每个元素插在新表新桶链的首元素位置上int oldlen = hb->next ? hb->next->len : 0; //将元素插入前，新表新桶链是否为空int newlen = oldlen + 1;if (newlen == 1)hash->stats.empty--; //插入前非空桶链，新表空桶链少了一个elsehb->next->len = 0;hb->len = newlen; //记录新长度hash_update_ssq(hash, oldlen, newlen); //跟新ssq值new_index[h] = hb;}/* Switch to new table */XFREE(MTYPE_HASH_INDEX, hash->index);hash->size = new_size;hash->index = new_index;
}//关于ssq跟新的宏
#define hash_update_ssq(hz, old, new) \atomic_fetch_add_explicit(&hz->stats.ssq, (new + old) * (new - old), \memory_order_relaxed);#define atomic_fetch_add_explicit(ptr, val, mem) \({ \__sync_synchronize(); \typeof(*ptr) rval = __sync_fetch_and_add((ptr), (val)); \__sync_synchronize(); \rval; \})
其中__sync_synchronize()和__sync_fetch_and_add的理解可参考博文__sync_*系列原子操作函数等
2：字符串的hash函数
unsigned int string_hash_make(const char *str)
{unsigned int hash = 0;while (*str)hash = (hash * 33) ^ (unsigned int)*str++;return hash;
}
3：hash表释放某数据所在的桶
void *hash_release(struct hash *hash, void *data)
{void *ret;unsigned int key;unsigned int index;struct hash_bucket *bucket;struct hash_bucket *pp;key = (*hash->hash_key)(data);index = key & (hash->size - 1);//pp初始化和bucket指向桶链首元素，之后pp指向bucket的上一个桶元素for (bucket = pp = hash->index[index]; bucket; bucket = bucket->next) {if (bucket->key == key&& (*hash->hash_cmp)(bucket->data, data)) { //找到数据int oldlen = hash->index[index]->len; //首元素存的桶链长度int newlen = oldlen - 1;if (bucket == pp) //要删除的节点是桶链首节点hash->index[index] = bucket->next; //直接删除首节点elsepp->next = bucket->next; //删除非首元素的链表节点if (hash->index[index])hash->index[index]->len = newlen; //给桶链首元素赋值该链新长度elsehash->stats.empty++; //删除完，成了空桶链hash_update_ssq(hash, oldlen, newlen);ret = bucket->data; //返回同上的数据XFREE(MTYPE_HASH_BACKET, bucket); //删除桶所占的内存hash->count--; //分配节点的个数少了一个return ret;}pp = bucket;}return NULL;
}
4：hash元素迭代
//hash迭代
void hash_iterate(struct hash *hash, void (*func)(struct hash_bucket *, void *),void *arg)
{unsigned int i;struct hash_bucket *hb;struct hash_bucket *hbnext;for (i = 0; i < hash->size; i++)for (hb = hash->index[i]; hb; hb = hbnext) {/* get pointer to next hash bucket here, in case (*func)* decides to delete hb by calling hash_release*/hbnext = hb->next; //记录下一个节点，保证此次迭代链不断(*func)(hb, arg); //对当前节点进行删除等操作处理}
}
5：hash表中各种数据的计算和输出
//一个输出hash参数的命令，只需要关注函数体中各参数的计算即可，中间的英文备注可帮助解释
DEFUN_NOSH(show_hash_stats,show_hash_stats_cmd,"show debugging hashtable [statistics]",SHOW_STRDEBUG_STR"Statistics about hash tables\n""Statistics about hash tables\n")
{struct hash *h;struct listnode *ln;struct ttable *tt = ttable_new(&ttable_styles[TTSTYLE_BLANK]);ttable_add_row(tt, "Hash table|Buckets|Entries|Empty|LF|SD|FLF|SD");tt->style.cell.lpad = 2;tt->style.cell.rpad = 1;tt->style.corner = '+';ttable_restyle(tt);ttable_rowseps(tt, 0, BOTTOM, true, '-');/* Summary statistics calculated are:** - Load factor: This is the number of elements in the table divided* by the number of buckets. Since this hash table implementation* uses chaining, this value can be greater than 1.* This number provides information on how 'full' the table is, but* does not provide information on how evenly distributed the* elements are.* Notably, a load factor >= 1 does not imply that every bucket has* an element; with a pathological hash function, all elements could* be in a single bucket.** - Full load factor: this is the number of elements in the table* divided by the number of buckets that have some elements in them.** - Std. Dev.: This is the standard deviation calculated from the* relevant load factor. If the load factor is the mean of number of* elements per bucket, the standard deviation measures how much any* particular bucket is likely to deviate from the mean.* As a rule of thumb this number should be less than 2, and ideally* <= 1 for optimal performance. A number larger than 3 generally* indicates a poor hash function.*/double lf; // load factordouble flf; // full load factordouble var; // overall variancedouble fvar; // full variancedouble stdv; // overall stddevdouble fstdv; // full stddevlong double x2; // h->count ^ 2long double ldc; // (long double) h->countlong double full; // h->size - h->stats.emptylong double ssq; // ssq casted to long doublepthread_mutex_lock(&_hashes_mtx);if (!_hashes) {pthread_mutex_unlock(&_hashes_mtx);ttable_del(tt);vty_out(vty, "No hash tables in use.\n");return CMD_SUCCESS;}for (ALL_LIST_ELEMENTS_RO(_hashes, ln, h)) {if (!h->name)continue;ssq = (long double)h->stats.ssq;x2 = h->count * h->count;ldc = (long double)h->count;full = h->size - h->stats.empty;lf = h->count / (double)h->size; //LF,负载系数flf = full ? h->count / (double)(full) : 0; //FLF,满负载var = ldc ? (1.0 / ldc) * (ssq - x2 / ldc) : 0;fvar = full ? (1.0 / full) * (ssq - x2 / full) : 0;var = (var < .0001) ? 0 : var;fvar = (fvar < .0001) ? 0 : fvar;stdv = sqrt(var);fstdv = sqrt(fvar); //标准差，<=1最好，<2符合标准，>3则hash效果很差ttable_add_row(tt, "%s|%d|%ld|%.0f%%|%.2lf|%.2lf|%.2lf|%.2lf",h->name, h->size, h->count,(h->stats.empty / (double)h->size) * 100, lf,stdv, flf, fstdv);}pthread_mutex_unlock(&_hashes_mtx);/* display header */char header[] = "Showing hash table statistics for ";char underln[sizeof(header) + strlen(frr_protonameinst)];memset(underln, '-', sizeof(underln));underln[sizeof(underln) - 1] = '\0';vty_out(vty, "%s%s\n", header, frr_protonameinst);vty_out(vty, "%s\n", underln);vty_out(vty, "# allocated: %d\n", _hashes->count);vty_out(vty, "# named: %d\n\n", tt->nrows - 1);if (tt->nrows > 1) {ttable_colseps(tt, 0, RIGHT, true, '|');char *table = ttable_dump(tt, "\n");vty_out(vty, "%s\n", table);XFREE(MTYPE_TMP, table);} elsevty_out(vty, "No named hash tables to display.\n");ttable_del(tt);return CMD_SUCCESS;
}
6：hash表释放
void hash_free(struct hash *hash)
{frr_with_mutex(&_hashes_mtx) {if (_hashes) {listnode_delete(_hashes, hash); //从list里找到hash所在的节点，然后删除这个节点if (_hashes->count == 0) { //若链表为空，删除链表主体结构list_delete(&_hashes);}}}XFREE(MTYPE_HASH, hash->name); //表名XFREE(MTYPE_HASH_INDEX, hash->index); //桶链结构XFREE(MTYPE_HASH, hash); //表结构
}//_hashes结构是一个个hash表用双向指针连起来的总hash链表
static struct list *_hashes;