path: root/khashl.h

/* The MIT License

   Copyright (c) 2019-2023 by Attractive Chaos <attractor@live.co.uk>

   Permission is hereby granted, free of charge, to any person obtaining
   a copy of this software and associated documentation files (the
   "Software"), to deal in the Software without restriction, including
   without limitation the rights to use, copy, modify, merge, publish,
   distribute, sublicense, and/or sell copies of the Software, and to
   permit persons to whom the Software is furnished to do so, subject to
   the following conditions:

   The above copyright notice and this permission notice shall be
   included in all copies or substantial portions of the Software.

   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
   BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
   ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
   CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
   SOFTWARE.
*/

#ifndef __AC_KHASHL_H
#define __AC_KHASHL_H

#include "hash.h"

#define AC_VERSION_KHASHL_H "0.2"

typedef uint32_t khint32_t;
typedef uint64_t khint64_t;

typedef khint32_t khint_t;
typedef khint_t khiter_t;

#define kh_inline inline /* portably handled elsewhere */
#define KH_LOCAL static kh_inline MAYBE_UNUSED

#ifndef kcalloc
#define kcalloc(N,Z) xcalloc(N,Z)
#endif
#ifndef kfree
#define kfree(P) free(P)
#endif

/****************************
 * Simple private functions *
 ****************************/

#define __kh_used(flag, i)       (flag[i>>5] >> (i&0x1fU) & 1U)
#define __kh_set_used(flag, i)   (flag[i>>5] |= 1U<<(i&0x1fU))
#define __kh_set_unused(flag, i) (flag[i>>5] &= ~(1U<<(i&0x1fU)))

#define __kh_fsize(m) ((m) < 32? 1 : (m)>>5)

static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 2654435769U >> (32 - bits); }

/*******************
 * Hash table base *
 *******************/

#define __KHASHL_TYPE(HType, khkey_t) \
	typedef struct HType { \
		khint_t bits, count; \
		khint32_t *used; \
		khkey_t *keys; \
	} HType;

#define __KHASHL_PROTOTYPES(HType, prefix, khkey_t) \
	extern HType *prefix##_init(void); \
	extern void prefix##_destroy(HType *h); \
	extern void prefix##_clear(HType *h); \
	extern khint_t prefix##_getp(const HType *h, const khkey_t *key); \
	extern void prefix##_resize(HType *h, khint_t new_n_buckets); \
	extern khint_t prefix##_putp(HType *h, const khkey_t *key, int *absent); \
	extern void prefix##_del(HType *h, khint_t k);

#define __KHASHL_IMPL_BASIC(SCOPE, HType, prefix) \
	SCOPE HType *prefix##_init(void) { \
		return (HType*)kcalloc(1, sizeof(HType)); \
	} \
	SCOPE void prefix##_release(HType *h) { \
		kfree((void *)h->keys); kfree(h->used); \
	} \
	SCOPE void prefix##_destroy(HType *h) { \
		if (!h) return; \
		prefix##_release(h); \
		kfree(h); \
	} \
	SCOPE void prefix##_clear(HType *h) { \
		if (h && h->used) { \
			khint_t n_buckets = (khint_t)1U << h->bits; \
			memset(h->used, 0, __kh_fsize(n_buckets) * sizeof(khint32_t)); \
			h->count = 0; \
		} \
	}

#define __KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
	SCOPE khint_t prefix##_getp_core(const HType *h, const khkey_t *key, khint_t hash) { \
		khint_t i, last, n_buckets, mask; \
		if (!h->keys) return 0; \
		n_buckets = (khint_t)1U << h->bits; \
		mask = n_buckets - 1U; \
		i = last = __kh_h2b(hash, h->bits); \
		while (__kh_used(h->used, i) && !__hash_eq(h->keys[i], *key)) { \
			i = (i + 1U) & mask; \
			if (i == last) return n_buckets; \
		} \
		return !__kh_used(h->used, i)? n_buckets : i; \
	} \
	SCOPE khint_t prefix##_getp(const HType *h, const khkey_t *key) { return prefix##_getp_core(h, key, __hash_fn(*key)); } \
	SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { return prefix##_getp_core(h, &key, __hash_fn(key)); }

#define __KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
	SCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { \
		khint32_t *new_used = NULL; \
		khint_t j = 0, x = new_n_buckets, n_buckets, new_bits, new_mask; \
		while ((x >>= 1) != 0) ++j; \
		if (new_n_buckets & (new_n_buckets - 1)) ++j; \
		new_bits = j > 2? j : 2; \
		new_n_buckets = (khint_t)1U << new_bits; \
		if (h->count > (new_n_buckets>>1) + (new_n_buckets>>2)) return; /* noop, requested size is too small */ \
		new_used = (khint32_t*)kcalloc(__kh_fsize(new_n_buckets), sizeof(khint32_t)); \
		n_buckets = h->keys? (khint_t)1U<<h->bits : 0U; \
		if (n_buckets < new_n_buckets) { /* expand */ \
			REALLOC_ARRAY(h->keys, new_n_buckets); \
		} /* otherwise shrink */ \
		new_mask = new_n_buckets - 1; \
		for (j = 0; j != n_buckets; ++j) { \
			khkey_t key; \
			if (!__kh_used(h->used, j)) continue; \
			key = h->keys[j]; \
			__kh_set_unused(h->used, j); \
			while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \
				khint_t i; \
				i = __kh_h2b(__hash_fn(key), new_bits); \
				while (__kh_used(new_used, i)) i = (i + 1) & new_mask; \
				__kh_set_used(new_used, i); \
				if (i < n_buckets && __kh_used(h->used, i)) { /* kick out the existing element */ \
					{ khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
					__kh_set_unused(h->used, i); /* mark it as deleted in the old hash table */ \
				} else { /* write the element and jump out of the loop */ \
					h->keys[i] = key; \
					break; \
				} \
			} \
		} \
		if (n_buckets > new_n_buckets) /* shrink the hash table */ \
			REALLOC_ARRAY(h->keys, new_n_buckets); \
		kfree(h->used); /* free the working space */ \
		h->used = new_used, h->bits = new_bits; \
	}

#define __KHASHL_IMPL_PUT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
	SCOPE khint_t prefix##_putp_core(HType *h, const khkey_t *key, khint_t hash, int *absent) { \
		khint_t n_buckets, i, last, mask; \
		n_buckets = h->keys? (khint_t)1U<<h->bits : 0U; \
		*absent = -1; \
		if (h->count >= (n_buckets>>1) + (n_buckets>>2)) { /* rehashing */ \
			prefix##_resize(h, n_buckets + 1U); \
			n_buckets = (khint_t)1U<<h->bits; \
		} /* TODO: to implement automatically shrinking; resize() already support shrinking */ \
		mask = n_buckets - 1; \
		i = last = __kh_h2b(hash, h->bits); \
		while (__kh_used(h->used, i) && !__hash_eq(h->keys[i], *key)) { \
			i = (i + 1U) & mask; \
			if (i == last) break; \
		} \
		if (!__kh_used(h->used, i)) { /* not present at all */ \
			h->keys[i] = *key; \
			__kh_set_used(h->used, i); \
			++h->count; \
			*absent = 1; \
		} else *absent = 0; /* Don't touch h->keys[i] if present */ \
		return i; \
	} \
	SCOPE khint_t prefix##_putp(HType *h, const khkey_t *key, int *absent) { return prefix##_putp_core(h, key, __hash_fn(*key), absent); } \
	SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { return prefix##_putp_core(h, &key, __hash_fn(key), absent); }

#define __KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn) \
	SCOPE int prefix##_del(HType *h, khint_t i) { \
		khint_t j = i, k, mask, n_buckets; \
		if (!h->keys) return 0; \
		n_buckets = (khint_t)1U<<h->bits; \
		mask = n_buckets - 1U; \
		while (1) { \
			j = (j + 1U) & mask; \
			if (j == i || !__kh_used(h->used, j)) break; /* j==i only when the table is completely full */ \
			k = __kh_h2b(__hash_fn(h->keys[j]), h->bits); \
			if ((j > i && (k <= i || k > j)) || (j < i && (k <= i && k > j))) \
				h->keys[i] = h->keys[j], i = j; \
		} \
		__kh_set_unused(h->used, i); \
		--h->count; \
		return 1; \
	}

#define KHASHL_DECLARE(HType, prefix, khkey_t) \
	__KHASHL_TYPE(HType, khkey_t) \
	__KHASHL_PROTOTYPES(HType, prefix, khkey_t)

/* compatibility wrappers to make khash -> khashl migration easier */
#define __KHASH_COMPAT(SCOPE, HType, prefix, khkey_t) \
	typedef HType HType##_t; \
	SCOPE HType *kh_init_##prefix(void) { return prefix##_init(); } \
	SCOPE void kh_release_##prefix(HType *h) { prefix##_release(h); } \
	SCOPE void kh_destroy_##prefix(HType *h) { prefix##_destroy(h); } \
	SCOPE void kh_clear_##prefix(HType *h) { prefix##_clear(h); } \
	SCOPE khint_t kh_get_##prefix(const HType *h, khkey_t key) { \
		return prefix##_get(h, key); \
	} \
	SCOPE void kh_resize_##prefix(HType *h, khint_t new_n_buckets) { \
		prefix##_resize(h, new_n_buckets); \
	} \
	SCOPE khint_t kh_put_##prefix(HType *h, khkey_t key, int *absent) { \
		return prefix##_put(h, key, absent); \
	} \
	SCOPE int kh_del_##prefix(HType *h, khint_t i) { \
		return prefix##_del(h, i); \
	}

#define KHASHL_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
	__KHASHL_TYPE(HType, khkey_t) \
	__KHASHL_IMPL_BASIC(SCOPE, HType, prefix) \
	__KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
	__KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
	__KHASHL_IMPL_PUT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
	__KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn)

/***************************
 * Ensemble of hash tables *
 ***************************/

typedef struct {
	khint_t sub, pos;
} kh_ensitr_t;

#define KHASHE_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
	KHASHL_INIT(KH_LOCAL, HType##_sub, prefix##_sub, khkey_t, __hash_fn, __hash_eq) \
	typedef struct HType { \
		khint64_t count:54, bits:8; \
		HType##_sub *sub; \
	} HType; \
	SCOPE HType *prefix##_init(int bits) { \
		HType *g; \
		g = (HType*)kcalloc(1, sizeof(*g)); \
		g->bits = bits; \
		g->sub = (HType##_sub*)kcalloc(1U<<bits, sizeof(*g->sub)); \
		return g; \
	} \
	SCOPE void prefix##_destroy(HType *g) { \
		int t; \
		if (!g) return; \
		for (t = 0; t < 1<<g->bits; ++t) { kfree((void*)g->sub[t].keys); kfree(g->sub[t].used); } \
		kfree(g->sub); kfree(g); \
	} \
	SCOPE kh_ensitr_t prefix##_getp(const HType *g, const khkey_t *key) { \
		khint_t hash, low, ret; \
		kh_ensitr_t r; \
		HType##_sub *h; \
		hash = __hash_fn(*key); \
		low = hash & ((1U<<g->bits) - 1); \
		h = &g->sub[low]; \
		ret = prefix##_sub_getp_core(h, key, hash); \
		if (ret >= kh_end(h)) r.sub = low, r.pos = (khint_t)-1; \
		else r.sub = low, r.pos = ret; \
		return r; \
	} \
	SCOPE kh_ensitr_t prefix##_get(const HType *g, const khkey_t key) { return prefix##_getp(g, &key); } \
	SCOPE kh_ensitr_t prefix##_putp(HType *g, const khkey_t *key, int *absent) { \
		khint_t hash, low, ret; \
		kh_ensitr_t r; \
		HType##_sub *h; \
		hash = __hash_fn(*key); \
		low = hash & ((1U<<g->bits) - 1); \
		h = &g->sub[low]; \
		ret = prefix##_sub_putp_core(h, key, hash, absent); \
		if (*absent) ++g->count; \
		if (ret == 1U<<h->bits) r.sub = low, r.pos = (khint_t)-1; \
		else r.sub = low, r.pos = ret; \
		return r; \
	} \
	SCOPE kh_ensitr_t prefix##_put(HType *g, const khkey_t key, int *absent) { return prefix##_putp(g, &key, absent); } \
	SCOPE int prefix##_del(HType *g, kh_ensitr_t itr) { \
		HType##_sub *h = &g->sub[itr.sub]; \
		int ret; \
		ret = prefix##_sub_del(h, itr.pos); \
		if (ret) --g->count; \
		return ret; \
	}

/*****************************
 * More convenient interface *
 *****************************/

#define __kh_packed /* noop, we use -Werror=address-of-packed-member */
#define __kh_cached_hash(x) ((x).hash)

#define KHASHL_SET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
	typedef struct { khkey_t key; } __kh_packed HType##_s_bucket_t; \
	static kh_inline khint_t prefix##_s_hash(HType##_s_bucket_t x) { return __hash_fn(x.key); } \
	static kh_inline int prefix##_s_eq(HType##_s_bucket_t x, HType##_s_bucket_t y) { return __hash_eq(x.key, y.key); } \
	KHASHL_INIT(KH_LOCAL, HType, prefix##_s, HType##_s_bucket_t, prefix##_s_hash, prefix##_s_eq) \
	SCOPE HType *prefix##_init(void) { return prefix##_s_init(); } \
	SCOPE void prefix##_release(HType *h) { prefix##_s_release(h); } \
	SCOPE void prefix##_destroy(HType *h) { prefix##_s_destroy(h); } \
	SCOPE void prefix##_clear(HType *h) { prefix##_s_clear(h); } \
	SCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { prefix##_s_resize(h, new_n_buckets); } \
	SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_s_bucket_t t; t.key = key; return prefix##_s_getp(h, &t); } \
	SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_s_del(h, k); } \
	SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_s_bucket_t t; t.key = key; return prefix##_s_putp(h, &t, absent); } \
	__KHASH_COMPAT(SCOPE, HType, prefix, khkey_t)

#define KHASHL_MAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \
	typedef struct { khkey_t key; kh_val_t val; } __kh_packed HType##_m_bucket_t; \
	static kh_inline khint_t prefix##_m_hash(HType##_m_bucket_t x) { return __hash_fn(x.key); } \
	static kh_inline int prefix##_m_eq(HType##_m_bucket_t x, HType##_m_bucket_t y) { return __hash_eq(x.key, y.key); } \
	KHASHL_INIT(KH_LOCAL, HType, prefix##_m, HType##_m_bucket_t, prefix##_m_hash, prefix##_m_eq) \
	SCOPE HType *prefix##_init(void) { return prefix##_m_init(); } \
	SCOPE void prefix##_release(HType *h) { prefix##_m_release(h); } \
	SCOPE void prefix##_destroy(HType *h) { prefix##_m_destroy(h); } \
	SCOPE void prefix##_clear(HType *h) { prefix##_m_clear(h); } \
	SCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { prefix##_m_resize(h, new_n_buckets); } \
	SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_m_bucket_t t; t.key = key; return prefix##_m_getp(h, &t); } \
	SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_m_del(h, k); } \
	SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_m_bucket_t t; t.key = key; return prefix##_m_putp(h, &t, absent); } \
	__KHASH_COMPAT(SCOPE, HType, prefix, khkey_t)

#define KHASHL_CSET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
	typedef struct { khkey_t key; khint_t hash; } __kh_packed HType##_cs_bucket_t; \
	static kh_inline int prefix##_cs_eq(HType##_cs_bucket_t x, HType##_cs_bucket_t y) { return x.hash == y.hash && __hash_eq(x.key, y.key); } \
	KHASHL_INIT(KH_LOCAL, HType, prefix##_cs, HType##_cs_bucket_t, __kh_cached_hash, prefix##_cs_eq) \
	SCOPE HType *prefix##_init(void) { return prefix##_cs_init(); } \
	SCOPE void prefix##_destroy(HType *h) { prefix##_cs_destroy(h); } \
	SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_cs_bucket_t t; t.key = key; t.hash = __hash_fn(key); return prefix##_cs_getp(h, &t); } \
	SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_cs_del(h, k); } \
	SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_cs_bucket_t t; t.key = key, t.hash = __hash_fn(key); return prefix##_cs_putp(h, &t, absent); }

#define KHASHL_CMAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \
	typedef struct { khkey_t key; kh_val_t val; khint_t hash; } __kh_packed HType##_cm_bucket_t; \
	static kh_inline int prefix##_cm_eq(HType##_cm_bucket_t x, HType##_cm_bucket_t y) { return x.hash == y.hash && __hash_eq(x.key, y.key); } \
	KHASHL_INIT(KH_LOCAL, HType, prefix##_cm, HType##_cm_bucket_t, __kh_cached_hash, prefix##_cm_eq) \
	SCOPE HType *prefix##_init(void) { return prefix##_cm_init(); } \
	SCOPE void prefix##_destroy(HType *h) { prefix##_cm_destroy(h); } \
	SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_cm_bucket_t t; t.key = key; t.hash = __hash_fn(key); return prefix##_cm_getp(h, &t); } \
	SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_cm_del(h, k); } \
	SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_cm_bucket_t t; t.key = key, t.hash = __hash_fn(key); return prefix##_cm_putp(h, &t, absent); }

#define KHASHE_MAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \
	typedef struct { khkey_t key; kh_val_t val; } __kh_packed HType##_m_bucket_t; \
	static kh_inline khint_t prefix##_m_hash(HType##_m_bucket_t x) { return __hash_fn(x.key); } \
	static kh_inline int prefix##_m_eq(HType##_m_bucket_t x, HType##_m_bucket_t y) { return __hash_eq(x.key, y.key); } \
	KHASHE_INIT(KH_LOCAL, HType, prefix##_m, HType##_m_bucket_t, prefix##_m_hash, prefix##_m_eq) \
	SCOPE HType *prefix##_init(int bits) { return prefix##_m_init(bits); } \
	SCOPE void prefix##_destroy(HType *h) { prefix##_m_destroy(h); } \
	SCOPE kh_ensitr_t prefix##_get(const HType *h, khkey_t key) { HType##_m_bucket_t t; t.key = key; return prefix##_m_getp(h, &t); } \
	SCOPE int prefix##_del(HType *h, kh_ensitr_t k) { return prefix##_m_del(h, k); } \
	SCOPE kh_ensitr_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_m_bucket_t t; t.key = key; return prefix##_m_putp(h, &t, absent); }

/**************************
 * Public macro functions *
 **************************/

#define kh_bucket(h, x) ((h)->keys[x])

/*! @function
  @abstract     Get the number of elements in the hash table
  @param  h     Pointer to the hash table
  @return       Number of elements in the hash table [khint_t]
 */
#define kh_size(h) ((h)->count)

#define kh_capacity(h) ((h)->keys? 1U<<(h)->bits : 0U)

/*! @function
  @abstract     Get the end iterator
  @param  h     Pointer to the hash table
  @return       The end iterator [khint_t]
 */
#define kh_end(h) kh_capacity(h)

/*! @function
  @abstract     Get key given an iterator
  @param  h     Pointer to the hash table
  @param  x     Iterator to the bucket [khint_t]
  @return       Key [type of keys]
 */
#define kh_key(h, x) ((h)->keys[x].key)

/*! @function
  @abstract     Get value given an iterator
  @param  h     Pointer to the hash table
  @param  x     Iterator to the bucket [khint_t]
  @return       Value [type of values]
  @discussion   For hash sets, calling this results in segfault.
 */
#define kh_val(h, x) ((h)->keys[x].val)

/*! @function
  @abstract     Alias of kh_val()
 */
#define kh_value(h, x) kh_val(h, x)

/*! @function
  @abstract     Test whether a bucket contains data.
  @param  h     Pointer to the hash table
  @param  x     Iterator to the bucket [khint_t]
  @return       1 if containing data; 0 otherwise [int]
 */
#define kh_exist(h, x) __kh_used((h)->used, (x))

#define kh_ens_key(g, x) kh_key(&(g)->sub[(x).sub], (x).pos)
#define kh_ens_val(g, x) kh_val(&(g)->sub[(x).sub], (x).pos)
#define kh_ens_exist(g, x) kh_exist(&(g)->sub[(x).sub], (x).pos)
#define kh_ens_is_end(x) ((x).pos == (khint_t)-1)
#define kh_ens_size(g) ((g)->count)

/**************************************
 * Common hash and equality functions *
 **************************************/

#define kh_eq_generic(a, b) ((a) == (b))
#define kh_eq_str(a, b) (strcmp((a), (b)) == 0)
#define kh_hash_dummy(x) ((khint_t)(x))

static kh_inline khint_t kh_hash_uint32(khint_t key) {
	key += ~(key << 15);
	key ^=  (key >> 10);
	key +=  (key << 3);
	key ^=  (key >> 6);
	key += ~(key << 11);
	key ^=  (key >> 16);
	return key;
}

static kh_inline khint_t kh_hash_uint64(khint64_t key) {
	key = ~key + (key << 21);
	key = key ^ key >> 24;
	key = (key + (key << 3)) + (key << 8);
	key = key ^ key >> 14;
	key = (key + (key << 2)) + (key << 4);
	key = key ^ key >> 28;
	key = key + (key << 31);
	return (khint_t)key;
}

#define KH_FNV_SEED 11

static kh_inline khint_t kh_hash_str(const char *s) { /* FNV1a */
	khint_t h = KH_FNV_SEED ^ 2166136261U;
	const unsigned char *t = (const unsigned char*)s;
	for (; *t; ++t)
		h ^= *t, h *= 16777619;
	return h;
}

static kh_inline khint_t kh_hash_bytes(int len, const unsigned char *s) {
	khint_t h = KH_FNV_SEED ^ 2166136261U;
	int i;
	for (i = 0; i < len; ++i)
		h ^= s[i], h *= 16777619;
	return h;
}

/*! @function
  @abstract     Get the start iterator
  @param  h     Pointer to the hash table
  @return       The start iterator [khint_t]
 */
#define kh_begin(h) (khint_t)(0)

/*! @function
  @abstract     Iterate over the entries in the hash table
  @param  h     Pointer to the hash table
  @param  kvar  Variable to which key will be assigned
  @param  vvar  Variable to which value will be assigned
  @param  code  Block of code to execute
 */
#define kh_foreach(h, kvar, vvar, code) { khint_t __i;		\
	for (__i = kh_begin(h); __i != kh_end(h); ++__i) {	\
		if (!kh_exist(h,__i)) continue;			\
		(kvar) = kh_key(h,__i);				\
		(vvar) = kh_val(h,__i);				\
		code;						\
	} }

/*! @function
  @abstract     Iterate over the values in the hash table
  @param  h     Pointer to the hash table
  @param  vvar  Variable to which value will be assigned
  @param  code  Block of code to execute
 */
#define kh_foreach_value(h, vvar, code) { khint_t __i;		\
	for (__i = kh_begin(h); __i != kh_end(h); ++__i) {	\
		if (!kh_exist(h,__i)) continue;			\
		(vvar) = kh_val(h,__i);				\
		code;						\
	} }

static inline unsigned int oidhash_by_value(struct object_id oid)
{
	return oidhash(&oid);
}

static inline int oideq_by_value(struct object_id a, struct object_id b)
{
	return oideq(&a, &b);
}

KHASHL_SET_INIT(KH_LOCAL, kh_oid_set, oid_set, struct object_id,
		oidhash_by_value, oideq_by_value)

KHASHL_MAP_INIT(KH_LOCAL, kh_oid_map, oid_map, struct object_id, void *,
		oidhash_by_value, oideq_by_value)

KHASHL_MAP_INIT(KH_LOCAL, kh_oid_pos, oid_pos, struct object_id, int,
		oidhash_by_value, oideq_by_value)

#endif /* __AC_KHASHL_H */