adt ghash: Generic hash tables.

Data Structures
struct	ghash
struct	ghashiter

Macros
#define	ghash_entry_hash(P)   (*(adt_hash_t*)(P))
#define	ghash_entry_keyptr(P)   ((P)+sizeof(adt_hash_t))
#define	ghash_entry_dataptr(P, L)   ((P)+sizeof(adt_hash_t)+(L))
#define	ghash_hashb   adt_hashb
#define	ghash_hashs   adt_hashs
#define	ghash_hashsp   adt_hashsp
#define	GHASH_STRUCT_ENTRY(PREFIX, KTYPE, DTYPE)
#define	GHASH_KEYOFFSET(PREFIX)   ((unsigned long)&((struct PREFIX##_entry*)0)->key)
#define	GHASH_DATAOFFSET(PREFIX)   ((unsigned long)&((struct PREFIX##_entry*)0)->data)
#define	GHASH_KEYSIZE(PREFIX)
#define	GHASH_DECL(PREFIX, KTYPE, DTYPE)
#define	GHASH_INIT_DEFN(PREFIX, KTYPE, DTYPE, HASHFN, CMP, KCOPY, DCOPY, KFREE, DFREE)
#define	GHASH_FREE_DEFN(PREFIX)
#define	GHASH_ADD_DEFN(PREFIX, KTYPE, DTYPE)
#define	GHASH_SET_DEFN(PREFIX, KTYPE, DTYPE)
#define	GHASH_GET_DEFN(PREFIX, KTYPE)
#define	GHASH_REBUILD_DEFN(PREFIX)
#define	GHASH_REHASH_DEFN(PREFIX)
#define	GHASH_REMOVE_DEFN(PREFIX, KTYPE)
#define	GHASH_FOREACH_DEFN(PREFIX)
#define	GHASH_SEARCH_DEFN(PREFIX)
#define	GHASH_DEFN(PREFIX, KTYPE, DTYPE, HASHFN, CMPFN, KCOPY, DCOPY, KFREE, DFREE)
#define	ghashiter_loop(I, G)   for(ghashiter_first(I,G);ghashiter_valid(I);ghashiter_next(I))

Functions
void	ghash_insert (struct ghash *d, void *e)
void *	ghash_add (struct ghash *d, const void *key, const void *data)
void *	ghash_set (struct ghash *d, const void *key, const void *data)
void	ghash_free (struct ghash *d)
void **	ghash_find (struct ghash *d, const void *key)
void *	ghash_get (struct ghash *d, const void *key)
void	ghash_init (struct ghash *d, unsigned long keysize, unsigned long entrysize, adt_hash_fn *hashfn, adt_cmp_fn *keycmp, adt_copy_fn *keycopy, adt_copy_fn *datacopy, adt_free_fn *keyfree, adt_free_fn *datafree)
int	ghash_rebuild (struct ghash *d)
int	ghash_rehash (struct ghash *d)
int	ghash_remove (struct ghash *d, const void *key)
void	ghash_foreach (struct ghash *d, void(*fn)(void *entry))
void *	ghash_search (struct ghash *d, int(*fn)(const void *entry))
void	ghashiter_first (struct ghashiter *, const struct ghash *)
int	ghashiter_valid (const struct ghashiter *)
void	ghashiter_next (struct ghashiter *)

Detailed Description

The actual hash table manipulation functions use a simple linear probing algorithm with a dynamic table size. Since many more slots are allocated than are in use at any given time, there are always plenty of empty slots available to make searches short. Since each shot is a single pointer, these extra slots don't consume a significant amount of memory.

The structure at the center of the ghash implementation contains pointers to the actual data (including all relevant metadata) plus function pointers to the functions needed to manipulate the data.

Macro Definition Documentation

GHASH_ADD_DEFN

#define GHASH_ADD_DEFN	(		PREFIX,
			KTYPE,
			DTYPE
	)

Value:

struct PREFIX##_entry* PREFIX##_add(struct ghash* d, \
                                    KTYPE const* key, DTYPE const* data) { \
  return ghash_add(d, key, data); \
}

Define a specialized ghash table add function.

GHASH_DATAOFFSET

#define GHASH_DATAOFFSET

(

PREFIX

)

((unsigned long)&((struct PREFIX##_entry*)0)->data)

The offset of the data into a specialized ghash entry.

GHASH_DECL

#define GHASH_DECL	(		PREFIX,
			KTYPE,
			DTYPE
	)

Value:

GHASH_STRUCT_ENTRY(PREFIX,KTYPE,DTYPE); \
extern void PREFIX##_init(struct ghash* d); \
extern void PREFIX##_free(struct ghash* d); \
extern struct PREFIX##_entry* PREFIX##_add(struct ghash* d, \
                                           KTYPE const* key, \
                                           DTYPE const* data); \
extern struct PREFIX##_entry* PREFIX##_set(struct ghash* d, \
                                           KTYPE const* key, \
                                           DTYPE const* data); \
extern struct PREFIX##_entry* PREFIX##_get(struct ghash* d, \
                                           KTYPE const* key); \
extern int PREFIX##_rebuild(struct ghash* d); \
extern int PREFIX##_rehash(struct ghash* d); \
extern int PREFIX##_remove(struct ghash* d, KTYPE const* key); \
extern void PREFIX##_foreach(struct ghash* d, \
                             void (*fn)(struct PREFIX##_entry*)); \
extern struct PREFIX##_entry* PREFIX##_search(struct ghash* d, \
                                              int (*fn)(const struct PREFIX##_entry*));

Declare all the prototypes for a ghash table, specialized to particular key and data types.

Examples:

adt/ghash_test.c.

GHASH_DEFN

#define GHASH_DEFN	(		PREFIX,
			KTYPE,
			DTYPE,
			HASHFN,
			CMPFN,
			KCOPY,
			DCOPY,
			KFREE,
			DFREE
	)

Value:

GHASH_INIT_DEFN(PREFIX,KTYPE,DTYPE,HASHFN,CMPFN,KCOPY,DCOPY,KFREE,DFREE) \
GHASH_FREE_DEFN(PREFIX) \
GHASH_ADD_DEFN(PREFIX,KTYPE,DTYPE) \
GHASH_SET_DEFN(PREFIX,KTYPE,DTYPE) \
GHASH_GET_DEFN(PREFIX,KTYPE) \
GHASH_REBUILD_DEFN(PREFIX) \
GHASH_REHASH_DEFN(PREFIX) \
GHASH_REMOVE_DEFN(PREFIX,KTYPE) \
GHASH_FOREACH_DEFN(PREFIX) \
GHASH_SEARCH_DEFN(PREFIX)

Define all necessary functions for a specialized ghash table. If either of the copy functions KCOPY or DCOPY are NULL, a simple memcpy is used instead. If either of the free functions KFREE or DFREE are NULL, no data freeing is attempted.

Examples:

adt/ghash_test.c.

ghash_entry_dataptr

#define ghash_entry_dataptr	(		P,
			L
	)		((P)+sizeof(adt_hash_t)+(L))

The data structure address within an entry P . The offset parameter L is the size of the key structure.

Referenced by ghash_add(), ghash_free(), ghash_remove(), and ghash_set().

ghash_entry_hash

#define ghash_entry_hash

(

P

)

(*(adt_hash_t*)(P))

The hash value stored within an entry P .

Referenced by ghash_add(), ghash_find(), ghash_insert(), and ghash_rehash().

ghash_entry_keyptr

#define ghash_entry_keyptr

(

P

)

((P)+sizeof(adt_hash_t))

The key structure address within an entry P .

Referenced by ghash_add(), ghash_find(), ghash_free(), ghash_rehash(), and ghash_remove().

GHASH_FOREACH_DEFN

#define GHASH_FOREACH_DEFN

(

PREFIX

)

Value:

void PREFIX##_foreach(struct ghash* d, void (*fn)(struct PREFIX##_entry*)) { \
  ghash_foreach(d, (void (*)(void*))fn); \
}

Define a specialized ghash table iterator function.

GHASH_FREE_DEFN

#define GHASH_FREE_DEFN

(

PREFIX

)

Value:

void PREFIX##_free(struct ghash* d) { \
  ghash_free(d); \
}

Define a specialized ghash table free function.

GHASH_GET_DEFN

#define GHASH_GET_DEFN	(		PREFIX,
			KTYPE
	)

Value:

struct PREFIX##_entry* PREFIX##_get(struct ghash* d, KTYPE const* key) { \
  return ghash_get(d, key); \
}

Define a specialized ghash table get function.

ghash_hashb

#define ghash_hashb   adt_hashb

The adt_hashb function also works for ghash

ghash_hashs

#define ghash_hashs   adt_hashs

The adt_hashs function also works for ghash

ghash_hashsp

#define ghash_hashsp   adt_hashsp

The adt_hashsp function also works for ghash

GHASH_INIT_DEFN

#define GHASH_INIT_DEFN	(		PREFIX,
			KTYPE,
			DTYPE,
			HASHFN,
			CMP,
			KCOPY,
			DCOPY,
			KFREE,
			DFREE
	)

Value:

void PREFIX##_init(struct ghash* d) { \
  ghash_init(d, \
             GHASH_KEYSIZE(PREFIX), \
             sizeof(struct PREFIX##_entry), \
             (adt_hash_fn*)HASHFN, \
             (adt_cmp_fn*)CMP, \
             (adt_copy_fn*)KCOPY, \
             (adt_copy_fn*)DCOPY, \
             (adt_free_fn*)KFREE, \
             (adt_free_fn*)DFREE); \
}

Define a specialized ghash table init function.

GHASH_KEYOFFSET

#define GHASH_KEYOFFSET

(

PREFIX

)

((unsigned long)&((struct PREFIX##_entry*)0)->key)

The offset of the key into a specialized ghash entry.

GHASH_KEYSIZE

#define GHASH_KEYSIZE

(

PREFIX

)

Value:

( \
  GHASH_DATAOFFSET(PREFIX)-GHASH_KEYOFFSET(PREFIX) \
)

The actual size of the key data in a specialized ghash entry.

GHASH_REBUILD_DEFN

#define GHASH_REBUILD_DEFN

(

PREFIX

)

Value:

int PREFIX##_rebuild(struct ghash* d) { \
  return ghash_rebuild(d); \
}

Define a specialized ghash table rebuild function.

GHASH_REHASH_DEFN

#define GHASH_REHASH_DEFN

(

PREFIX

)

Value:

int PREFIX##_rehash(struct ghash* d) { \
  return ghash_rehash(d); \
}

Define a specialized ghash table rehash function.

GHASH_REMOVE_DEFN

#define GHASH_REMOVE_DEFN	(		PREFIX,
			KTYPE
	)

Value:

extern int PREFIX##_remove(struct ghash* d, KTYPE const* key) { \
  return ghash_remove(d, (void*)key); \
}

Define a specialized ghash table remove function.

GHASH_SEARCH_DEFN

#define GHASH_SEARCH_DEFN

(

PREFIX

)

Value:

struct PREFIX##_entry* PREFIX##_search(struct ghash* d, int (*fn)(const struct PREFIX##_entry*)) { \
  return ghash_search(d, (int (*)(const void*))fn); \
}

Define a specialized ghash table search function.

GHASH_SET_DEFN

#define GHASH_SET_DEFN	(		PREFIX,
			KTYPE,
			DTYPE
	)

Value:

struct PREFIX##_entry* PREFIX##_set(struct ghash* d, \
                                    KTYPE const* key, DTYPE const* data) { \
  return ghash_set(d, key, data); \
}

Define a specialized ghash table add function.

GHASH_STRUCT_ENTRY

#define GHASH_STRUCT_ENTRY	(		PREFIX,
			KTYPE,
			DTYPE
	)

Value:

struct PREFIX##_entry { \
  adt_hash_t hash; \
  KTYPE key; \
  DTYPE data; \
}

Prototype for the ghash entry structure, containing a key of type KTYPE and data of type DTYPE .

ghashiter_loop

#define ghashiter_loop	(		I,
			G
	)		for(ghashiter_first(I,G);ghashiter_valid(I);ghashiter_next(I))

A convenience macro which expands to a for loop using the ghashiter I to iterate over the table G .

Examples:

adt/ghash_test.c.

Function Documentation

ghash_add()

void* ghash_add	(	struct ghash *	d,
		const void *	key,
		const void *	data
	)

Add an entry into a generic hash table. This function adds a new entry into the given hash table. If the table is too small to provide sufficient slots for efficient access, the table is automatically expanded to the next larger size and all the existing entries are copied over.

References ghash::count, ghash::datacopy, ghash::entrysize, ghash_entry_dataptr, ghash_entry_hash, ghash_entry_keyptr, ghash_insert(), ghash::hashfn, ghash::keycopy, ghash::keyfree, and ghash::keysize.

Referenced by ghash_set().

ghash_find()

void** ghash_find	(	struct ghash *	d,
		const void *	key
	)

Find an entry in a ghash table.

Returns

A pointer to the entry structure, or NULL if the key was not found.

References ghash_entry_hash, ghash_entry_keyptr, ghash::hashfn, ghash::keycmp, ghash::size, and ghash::table.

Referenced by ghash_get(), and ghash_remove().

ghash_foreach()

void ghash_foreach	(	struct ghash *	d,
		void(*)(void *entry)	fn
	)

Iterate over a ghash table, calling a function for each entry.

References ghash::size, and ghash::table.

ghash_free()

void ghash_free

(

struct ghash *

d

)

Free all data (and entries) in a ghash table.

References ghash::datafree, ghash_entry_dataptr, ghash_entry_keyptr, ghash::keyfree, ghash::keysize, ghash::size, and ghash::table.

ghash_get()

void* ghash_get	(	struct ghash *	d,
		const void *	key
	)

Find an entry in a ghash table.

Returns

A pointer to the data structure or NULL if the key was not found.

References ghash_find().

Referenced by ghash_set().

ghash_init()

void ghash_init	(	struct ghash *	d,
		unsigned long	keysize,
		unsigned long	entrysize,
		adt_hash_fn *	hashfn,
		adt_cmp_fn *	keycmp,
		adt_copy_fn *	keycopy,
		adt_copy_fn *	datacopy,
		adt_free_fn *	keyfree,
		adt_free_fn *	datafree
	)

Initialize an empty ghash table.

References ghash::count, ghash::datacopy, ghash::datafree, ghash::entrysize, ghash::hashfn, ghash::keycmp, ghash::keycopy, ghash::keyfree, ghash::keysize, ghash::size, and ghash::table.

ghash_insert()

void ghash_insert	(	struct ghash *	d,
		void *	e
	)

Insert an entry into a ghash table, without resizing it.

References ghash::count, ghash_entry_hash, ghash::size, and ghash::table.

Referenced by ghash_add(), ghash_rebuild(), and ghash_remove().

ghash_rebuild()

int ghash_rebuild

(

struct ghash *

d

)

Rebuild the entry pointer table in a ghash table. This function is used internally after either rehashing the table or removing an entry.

References ghash::count, ghash_insert(), ghash::size, and ghash::table.

Referenced by ghash_rehash().

ghash_rehash()

int ghash_rehash

(

struct ghash *

d

)

Regenerate all the hash values in a ghash table and then rebuild it. Use this function when any of the keys change value.

References ghash_entry_hash, ghash_entry_keyptr, ghash_rebuild(), ghash::hashfn, ghash::size, and ghash::table.

ghash_remove()

int ghash_remove	(	struct ghash *	d,
		const void *	key
	)

Remove an entry from a ghash table. This function attempts to do the minimum amount of rebuilding necessary to adjust the positions of entries that may fall in the same slot as the newly removed entry.

Returns

True if the entry was found (and removed), false otherwise.

References ghash::count, ghash::datafree, ghash_entry_dataptr, ghash_entry_keyptr, ghash_find(), ghash_insert(), ghash::keyfree, ghash::keysize, ghash::size, and ghash::table.

ghash_search()

void* ghash_search	(	struct ghash *	d,
		int(*)(const void *entry)	fn
	)

Search for the first entry in the ghash table for which the given function returns true.

References ghash::size, and ghash::table.

ghash_set()

void* ghash_set	(	struct ghash *	d,
		const void *	key,
		const void *	data
	)

Replace or add an entry into a generic hash table.

References ghash::datacopy, ghash::entrysize, ghash_add(), ghash_entry_dataptr, ghash_get(), and ghash::keysize.

ghashiter_first()

void ghashiter_first	(	struct ghashiter *	iter,
		const struct ghash *	h
	)

Set a ghash iterator to the first element in the table.

References ghashiter::ghashp.

ghashiter_next()

void ghashiter_next

(

struct ghashiter *

iter

)

Advance the ghash iterator to the next element in the table.

References ghashiter::index.

ghashiter_valid()

int ghashiter_valid

(

const struct ghashiter *

iter

)

Check if the ghash iterator is still valid.

References ghashiter::ghashp, ghashiter::index, ghash::size, and ghash::table.