浅析Open vSwitch数据结构：哈希表hmap/smap/shash

文章目录

- 概述
- hmap
- - hmap数据结构
  - 初始化hmap
  - 插入节点
  - 扩展hmap空间
  - - resize函数
  - 删除节点
  - 遍历所有节点
  - - 辅助函数hmap_first
    - 辅助函数hmap_next
- smap
- - smap数据结构
  - 插入节点
  - 删除节点
  - 查找节点
  - 遍历所有节点
- shash
- - shash数据结构
  - 插入节点
  - 删除节点
  - 查找节点
  - 遍历所有节点

概述

在OVS软件中，hmap提供了基础的哈希表存储结构，smap和shash基于hmap进行实现，其中smap支持存储字符串，而sshash则支持存储任意类型的数据。

hmap

OVS软件的hmap是基于分离链接法实现的，分离链接法使用链表解决散列冲突，其做法是散列值相同的元素都保存到一个链表中。当查询的时候，首先根据散列值找到元素所在的链表，然后遍历链表查找对应的元素。
在这里插入图片描述

hmap数据结构

struct hmap {struct hmap_node **buckets;     // 哈希数组，本质上是一个分离链表数组，当mask=0时，指向成员one的地址struct hmap_node *one;      // 仅在mask为0时使用size_t mask;    // 哈希桶的大小size_t n;   // 哈希表中存储的hmap_node节点数量
};// 哈希节点
struct hmap_node {size_t hash;    // 哈希值struct hmap_node *next;    // 单向链表，所有哈希值相同的节点会链接到一个链表中
};

初始化hmap

void hmap_init(struct hmap *hmap)
{hmap->buckets = &hmap->one;hmap->one = NULL;hmap->mask = 0;hmap->n = 0;
}

插入节点

#define hmap_insert(HMAP, NODE, HASH) \hmap_insert_at(HMAP, NODE, HASH, OVS_SOURCE_LOCATOR)static inline void
hmap_insert_at(struct hmap *hmap, struct hmap_node *node, size_t hash,const char *where)
{hmap_insert_fast(hmap, node, hash);     // 执行快速插入if (hmap->n / 2 > hmap->mask) {     // 当存储节点数量的一半大于mask时，需要对hmap进行扩容hmap_expand_at(hmap, where);}
}static inline void
hmap_insert_fast(struct hmap *hmap, struct hmap_node *node, size_t hash)
{struct hmap_node **bucket = &hmap->buckets[hash & hmap->mask];      // 计算hash值，并根据hash值确定数组索引node->hash = hash;node->next = *bucket;*bucket = node;     // 新节点插入到链表头部hmap->n++;      // 更新hmap存储节点数量
}

扩展hmap空间

void
hmap_expand_at(struct hmap *hmap, const char *where)
{size_t new_mask = calc_mask(hmap->n);       // 根据已存储节点的数量计算出新的mask值if (new_mask > hmap->mask) {COVERAGE_INC(hmap_expand);resize(hmap, new_mask, where);}
}static size_t
calc_mask(size_t capacity)
{size_t mask = capacity / 2;mask |= mask >> 1;mask |= mask >> 2;mask |= mask >> 4;mask |= mask >> 8;mask |= mask >> 16;
#if SIZE_MAX > UINT32_MAXmask |= mask >> 32;
#endifmask |= (mask & 1) << 1;return mask;
}

resize函数

static void
resize(struct hmap *hmap, size_t new_mask, const char *where)
{struct hmap tmp;size_t i;ovs_assert(is_pow2(new_mask + 1));hmap_init(&tmp);        // 初始化临时的hmapif (new_mask) {tmp.buckets = xmalloc(sizeof *tmp.buckets * (new_mask + 1));    // 根据new_mask创建哈希数组tmp.mask = new_mask;for (i = 0; i <= tmp.mask; i++) {tmp.buckets[i] = NULL;}}int n_big_buckets = 0;int biggest_count = 0;int n_biggest_buckets = 0;for (i = 0; i <= hmap->mask; i++) {struct hmap_node *node, *next;int count = 0;for (node = hmap->buckets[i]; node; node = next) {next = node->next;hmap_insert_fast(&tmp, node, node->hash);       // 将原hmap的元素插入到临时hmap中count++;}}hmap_swap(hmap, &tmp);  // 交换两个hmap的结构，此时hmap的数据与原tmp是相同的hmap_destroy(&tmp);
}

删除节点

static inline void
hmap_remove(struct hmap *hmap, struct hmap_node *node)
{struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];while (*bucket != node) {bucket = &(*bucket)->next;}*bucket = node->next;hmap->n--;
}

遍历所有节点

// 普通版本的遍历，不支持删除节点
#define HMAP_FOR_EACH(NODE, MEMBER, HMAP) \HMAP_FOR_EACH_INIT(NODE, MEMBER, HMAP, (void) 0)#define HMAP_FOR_EACH_INIT(NODE, MEMBER, HMAP, ...)                     \for (INIT_CONTAINER(NODE, hmap_first(HMAP), MEMBER), __VA_ARGS__;   \(NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER))                \|| ((NODE = NULL), false);                                     \ASSIGN_CONTAINER(NODE, hmap_next(HMAP, &(NODE)->MEMBER), MEMBER))// 安全版本的遍历，支持删除节点
#define HMAP_FOR_EACH_SAFE(NODE, NEXT, MEMBER, HMAP) \HMAP_FOR_EACH_SAFE_INIT(NODE, NEXT, MEMBER, HMAP, (void) 0)#define HMAP_FOR_EACH_SAFE_INIT(NODE, NEXT, MEMBER, HMAP, ...)          \for (INIT_CONTAINER(NODE, hmap_first(HMAP), MEMBER), __VA_ARGS__;   \((NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER))               \|| ((NODE = NULL), false)                                     \? INIT_CONTAINER(NEXT, hmap_next(HMAP, &(NODE)->MEMBER), MEMBER), 1 \: 0);                                                         \(NODE) = (NEXT))

辅助函数hmap_first

static inline struct hmap_node *
hmap_next__(const struct hmap *hmap, size_t start)
{size_t i;for (i = start; i <= hmap->mask; i++) {struct hmap_node *node = hmap->buckets[i];if (node) {return node;}}return NULL;
}static inline struct hmap_node *
hmap_first(const struct hmap *hmap)
{return hmap_next__(hmap, 0);
}

辅助函数hmap_next

static inline struct hmap_node *
hmap_next(const struct hmap *hmap, const struct hmap_node *node)
{return (node->next? node->next        // 下一节点非空，返回下一节点: hmap_next__(hmap, (node->hash & hmap->mask) + 1));    
}

smap

smap基于hmap实现，是一个专用于存储key-value的哈希表，其中key和value类型都是字符串。

smap数据结构

struct smap {struct hmap map; 
};struct smap_node {struct hmap_node node;  char *key;char *value;
};

插入节点

struct smap_node *
smap_add(struct smap *smap, const char *key, const char *value)
{size_t key_len = strlen(key);return smap_add__(smap, xmemdup0(key, key_len), xstrdup(value),hash_bytes(key, key_len, 0));     // 为key和value申请内存空间
}static struct smap_node *
smap_add__(struct smap *smap, char *key, void *value, size_t hash)
{struct smap_node *node = xmalloc(sizeof *node);node->key = key;node->value = value;hmap_insert(&smap->map, &node->node, hash);     // 调用hmap接口插入节点return node;
}

删除节点

void
smap_remove_node(struct smap *smap, struct smap_node *node)
{hmap_remove(&smap->map, &node->node);free(node->key);free(node->value);free(node);
}void
smap_remove(struct smap *smap, const char *key)
{struct smap_node *node = smap_get_node(smap, key);if (node) {smap_remove_node(smap, node);}
}

查找节点

struct smap_node *
smap_get_node(const struct smap *smap, const char *key)
{size_t key_len = strlen(key);return smap_find__(smap, key, key_len, hash_bytes(key, key_len, 0));
}static struct smap_node *
smap_find__(const struct smap *smap, const char *key, size_t key_len,size_t hash)
{struct smap_node *node;HMAP_FOR_EACH_WITH_HASH (node, node, hash, &smap->map) {if (!strncmp(node->key, key, key_len) && !node->key[key_len]) {return node;}}return NULL;
}

遍历所有节点

// 普通版本的遍历，不支持删除，调用hmap的接口
#define SMAP_FOR_EACH(SMAP_NODE, SMAP)                                  \HMAP_FOR_EACH_INIT (SMAP_NODE, node, &(SMAP)->map,                  \BUILD_ASSERT_TYPE(SMAP_NODE, struct smap_node *), \BUILD_ASSERT_TYPE(SMAP, struct smap *))// 安全版本的遍历，支持删除，调用hmap的接口
#define SMAP_FOR_EACH_SAFE(SMAP_NODE, NEXT, SMAP)           \HMAP_FOR_EACH_SAFE_INIT (                               \SMAP_NODE, NEXT, node, &(SMAP)->map,                \BUILD_ASSERT_TYPE(SMAP_NODE, struct smap_node *),   \BUILD_ASSERT_TYPE(NEXT, struct smap_node *),        \BUILD_ASSERT_TYPE(SMAP, struct smap *))

shash

shash也是基于hmap进行扩展，支持存储任意类型的数据。

shash数据结构

struct shash_node {struct hmap_node node;char *name;void *data;
};struct shash {struct hmap map;
};

插入节点

static struct shash_node *
shash_add_nocopy__(struct shash *sh, char *name, const void *data, size_t hash)
{struct shash_node *node = xmalloc(sizeof *node);node->name = name;node->data = CONST_CAST(void *, data);      // 去除const属性进行存储hmap_insert(&sh->map, &node->node, hash);return node;
}struct shash_node *
shash_add_nocopy(struct shash *sh, char *name, const void *data)
{return shash_add_nocopy__(sh, name, data, hash_name(name));
}struct shash_node *
shash_add(struct shash *sh, const char *name, const void *data)
{return shash_add_nocopy(sh, xstrdup(name), data);       // 为key申请内存空间
}

删除节点

void
shash_delete(struct shash *sh, struct shash_node *node)
{free(shash_steal(sh, node));
}char *
shash_steal(struct shash *sh, struct shash_node *node)
{char *name = node->name;hmap_remove(&sh->map, &node->node);free(node);return name;
}

查找节点

static struct shash_node *
shash_find__(const struct shash *sh, const char *name, size_t name_len,size_t hash)
{struct shash_node *node;HMAP_FOR_EACH_WITH_HASH (node, node, hash, &sh->map) {if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {return node;}}return NULL;
}struct shash_node *
shash_find(const struct shash *sh, const char *name)
{return shash_find__(sh, name, strlen(name), hash_name(name));
}

遍历所有节点

#define SHASH_FOR_EACH(SHASH_NODE, SHASH)                               \HMAP_FOR_EACH_INIT (SHASH_NODE, node, &(SHASH)->map,                \BUILD_ASSERT_TYPE(SHASH_NODE, struct shash_node *), \BUILD_ASSERT_TYPE(SHASH, struct shash *))#define SHASH_FOR_EACH_SAFE(SHASH_NODE, NEXT, SHASH)        \HMAP_FOR_EACH_SAFE_INIT (                               \SHASH_NODE, NEXT, node, &(SHASH)->map,              \BUILD_ASSERT_TYPE(SHASH_NODE, struct shash_node *), \BUILD_ASSERT_TYPE(NEXT, struct shash_node *),       \BUILD_ASSERT_TYPE(SHASH, struct shash *))