kkty’s blog

node.jsとかvue.jsとかの話が多いと思います

Cの良さげなハッシュテーブルのライブラリ

C++のunordered_mapやPythonのdictなど、ほとんどの言語でハッシュテーブルが使えます。しかし、Cにはハッシュテーブルがありません。

言語仕様が小さいということなのでそれはそれで良いのですが、やはりハッシュテーブルが必要になることが多々あります。

そんな時にこのライブラリがシンプルで(手軽に使いたいときには)良さげです。keyはすべて文字列。 github.com

試してみる(文字列->intのハッシュテーブル)

map_int_t m;
map_init(&m);

map_set(&m, "key", 10);

int *val = map_get(&m, "key");
assert(*val == 10);

map_remove(&m, "key");
assert(val == NULL);

map_deinit(&m);

C++のunordered_set、Pythonのsetみたいなものも簡単に作っておきます

// map.hに追加

#define set_init(m) memset(m, 0, sizeof(*(m)))
#define set_deinit(m) map_deinit_(&(m)->base)
#define set_add(m, key) ( (m)->tmp = (0), map_set_(&(m)->base, key, &(m)->tmp, sizeof((m)->tmp)) )
#define set_contains(m, key) ( ((m)->ref = map_get_(&(m)->base, key)) != NULL )
#define set_remove(m, key) map_remove_(&(m)->base, key)
#define set_iter(m) map_iter_()
#define set_next(m, iter) map_next_(&(m)->base, iter)

keyが文字列だけというのもあれなのでintにもできるようにしておきます(無限に雑です)

// map.hに追加

#define map_i_get(m, key) ( (m)->ref = map_i_get_(&(m)->base, key) )
#define map_i_contains(m, key) ( ((m)->ref = map_i_get_(&(m)->base, key)) != NULL )
#define map_i_set(m, key, value) ( (m)->tmp = (value), map_i_set_(&(m)->base, key, &(m)->tmp, sizeof((m)->tmp)) )
#define map_i_remove(m, key) map_i_remove_(&(m)->base, key)
#define map_i_next(m, iter) map_i_next_(&(m)->base, iter)

void *map_i_get_(map_base_t *m, const int key);
int map_i_set_(map_base_t *m, const int key, void *value, int vsize);
void map_i_remove_(map_base_t *m, const int key);
int map_i_next_(map_base_t *m, map_iter_t *iter);
// map.cに追加

void *map_i_get_(map_base_t *m, const int key) {
  char key_str[20];
  sprintf(key_str, "%d", key);
  return map_get_(m, key_str);
}

int map_i_set_(map_base_t *m, const int key, void *value, int vsize) {
  char key_str[20];
  sprintf(key_str, "%d", key);
  return map_set_(m, key_str, value, vsize);
}

void map_i_remove_(map_base_t *m, const int key) {
  char key_str[20];
  sprintf(key_str, "%d", key);
  return map_remove_(m, key_str);
}

int map_i_next_(map_base_t *m, map_iter_t *iter) {
    if (iter->node) {
        iter->node = iter->node->next;
        if (iter->node == NULL) goto nextBucket;
    } else {
        nextBucket:
        do {
            if (++iter->bucketidx >= m->nbuckets) {
                return NULL;
            }
            iter->node = m->buckets[iter->bucketidx];
        } while (iter->node == NULL);
    }
    return atoi((char*)(iter->node + 1));
}