vppinfra----hash结构简单介绍

/* Vector header for hash tables. */
typedef struct hash_header
{
  /* hash结构中当前已存储d的元素个数*/
  uword elts;
  /*Bit 1和bit2 表是否支持动态扩容调整哈希*/
  u32 flags;
  /* Set if user does not want table to auto-resize when sufficiently full. */
#define HASH_FLAG_NO_AUTO_GROW    (1 << 0)
  /* Set if user does not want table to auto-resize when sufficiently empty. */
#define HASH_FLAG_NO_AUTO_SHRINK  (1 << 1)
  /* Set when hash_next is in the process of iterating through this hash table. */
#define HASH_FLAG_HASH_NEXT_IN_PROGRESS (1 << 2)
  /*占有sizeof(hash_pair_t) 空间大小的个数的2的次幂数：
     h->log2_pair_size = max_log2（x）
     比如x=8 = 2的3次方（_size = 3）；
      x=9 ：2的3次方不够（_size=3+1） 
     为0时，说明当前不存储value，只存储key。*/
  u32 log2_pair_size;

  /* 计算散列键的函数指针。哈希函数是哈希表素数大小的模等于(vec_len (v))。*/
  hash_key_sum_function_t *key_sum;

  /* Special values for key_sum "function". */
#define KEY_FUNC_NONE    (0)  /*< sum = key */
#define KEY_FUNC_POINTER_UWORD  (1)  /*< sum = *(uword *) key */
#define KEY_FUNC_POINTER_U32  (2)  /*< sum = *(u32 *) key */
#define KEY_FUNC_STRING         (3)  /*< sum = string_key_sum, etc. */
#define KEY_FUNC_MEM    (4)  /*< sum = mem_key_sum */
  /* key比较函数，不同的key类型对比不同的比较函数 */
  hash_key_equal_function_t *key_equal;
  /* 用户数据的勾子函数，在mhash结构中使用Hook for user's data.  Used to parameterize sum/equal functions. */
  any user;
  /* Format a (k,v) pair */
  format_function_t *format_pair;
  /* 格式化输出函数 的参数*/
  void *format_pair_arg;
  /* 哈希函数获得的键值的bitmap位2层意思：
   * 0是：是当前未存储数据或者当前已经存储数据但有hash冲突
   * 1：当前键值对应位置已存储数据*/
  uword is_user[0];
} hash_t;

/* 键值对结构体 */
typedef struct
{
  /*默认key是8字节*/
  uword key;
  /* 数值. Length is 2^log2_pair_size - 1. */
  uword value[0];
} hash_pair_t;

/* 哈希间接存储结构：当log2_pair_size >0 时使用
*/
typedef struct
{
  /* pair vector */
  hash_pair_t *pairs;
  /* padding */
  u8 pad[sizeof (uword) - sizeof (hash_pair_t *)];
  /* allocated length */
  uword alloc_len;
}
hash_pair_indirect_t;
/* Direct / Indirect pair union */
typedef union
{
  hash_pair_t direct;
  hash_pair_indirect_t indirect;
} hash_pair_union_t;

void *
_hash_set3 (void *v, uword key, void *value, void *old_value)
{
  hash_t *h;

  if (!v)
    v = hash_create (0, sizeof (uword));

  h = hash_header (v);
  (void) lookup (v, key, SET, value, old_value);

  if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
    {
      /* 当哈希因子大于0.75时，hash设置自动扩容标识，
       会进行hash 2倍的扩容. */
      if (4 * (h->elts + 1) > 3 * vec_len (v))
  v = hash_resize (v, 2 * vec_len (v));
    }
  return v;
}
static void *
hash_resize_internal (void *old, uword new_size, uword free_old)
{
  void *new;
  hash_pair_t *p;

  new = 0;
  if (new_size > 0)
    {
      hash_t *h = old ? hash_header (old) : 0;
      new = _hash_create (new_size, h);
      /* *INDENT-OFF* */
      hash_foreach_pair (p, old, {
  new = _hash_set3 (new, p->key, &p->value[0], 0);
      });
      /* *INDENT-ON* */
    }

  if (free_old)
    hash_free (old);
  return new;
}

hash_create2((elts),0,(value_bytes)，
               (hash_key_sum_function_t *) KEY_FUNC_NONE,
               (hash_key_equal_function_t *) KEY_FUNC_NONE,
               0,0)