usual/hashtab-impl.h File Reference

Simple customizable hashtable implementation. More...

Data Structures
struct	HashItem
	HashTab slot. More...
struct	HashTab
	Single HashTab segment. More...
Defines
#define	HTAB_KEY_T
	Overridable type for key.
#define	HTAB_VAL_T
	Overridable type for value.
#define	HTAB_MAX_FILL
	Max fill percentage.
Typedefs
typedef HTAB_KEY_T	htab_key_t
	Typedef for key.
typedef HTAB_VAL_T	htab_val_t
	Typedef for value.
typedef bool(*	hash_cmp_fn )(const htab_val_t curval, const void *arg)
	Signature for comparision function.
Functions
static struct HashTab *	hashtab_create (unsigned size, hash_cmp_fn cmp_fn, CxMem *ca)
	Initialize HashTab.
static void	hashtab_destroy (struct HashTab *h)
	Free HashTab.
static htab_val_t *	hashtab_lookup (struct HashTab *h, htab_key_t key, bool do_insert, const void *arg)
	Element lookup, optionally inserting new slot.
static void	hashtab_delete (struct HashTab *h, htab_key_t key, void *arg)
	Delete an element.
static void	hashtab_stats (struct HashTab *h, unsigned *nitem_p, unsigned *ntab_p)
	Count elements and fragments.
static struct HashTab *	hashtab_copy (struct HashTab *h_old, unsigned newsize)
	Copy elements to new hashtab, perhaps with different size.

---

Detailed Description

Simple customizable hashtable implementation.

• Fixed-size hash table, open-addressed
• Extended by linking several together
• Resizable by copying.
• Can be lockless in multi-reader, one-writer situation if mempory barrier macros are defined. This also requires that HashItem must not be split across cachelines.

---

Define Documentation

#define HTAB_KEY_T

Overridable type for key.

#define HTAB_VAL_T

Overridable type for value.

#define HTAB_MAX_FILL

Max fill percentage.

---

Typedef Documentation

typedef HTAB_KEY_T htab_key_t

Typedef for key.

typedef HTAB_VAL_T htab_val_t

Typedef for value.

typedef bool(* hash_cmp_fn)(const htab_val_t curval, const void *arg)

Signature for comparision function.

---

Function Documentation

static struct HashTab* hashtab_create	(	unsigned	size,
		hash_cmp_fn	cmp_fn,
		CxMem *	ca
	)		[static, read]

Initialize HashTab.

References cx_alloc0().

Referenced by hashtab_copy(), and hashtab_lookup().

static void hashtab_destroy

(

struct HashTab *

h

)

[static]

Free HashTab.

References cx_free().

Referenced by hashtab_copy().

static htab_val_t* hashtab_lookup	(	struct HashTab *	h,
		htab_key_t	key,
		bool	do_insert,
		const void *	arg
	)		[static]

Element lookup, optionally inserting new slot.

References hashtab_create().

Referenced by hashtab_copy(), and hashtab_delete().

static void hashtab_delete	(	struct HashTab *	h,
		htab_key_t	key,
		void *	arg
	)		[static]

Delete an element.

References container_of, and hashtab_lookup().

static void hashtab_stats	(	struct HashTab *	h,
		unsigned *	nitem_p,
		unsigned *	ntab_p
	)		[static]

Count elements and fragments.

static struct HashTab* hashtab_copy	(	struct HashTab *	h_old,
		unsigned	newsize
	)		[static, read]

Copy elements to new hashtab, perhaps with different size.

References err(), hashtab_create(), hashtab_destroy(), and hashtab_lookup().