adt ghash: Generic hash tables.


Data Structures
struct	ghash
struct	ghashiter
Defines
#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.

Define Documentation

#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.

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

The offset of the data into a specialized ghash entry.

#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.

#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.

#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.

#define ghash_entry_hash ( P ) (*(adt_hash_t*)(P))

The hash value stored within an entry P .

#define ghash_entry_keyptr ( P ) ((P)+sizeof(adt_hash_t))

The key structure address within an entry P .

#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.

#define GHASH_FREE_DEFN ( PREFIX )

Value:

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

Define a specialized ghash table free function.

#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.

#define ghash_hashb adt_hashb

The adt_hashb function also works for ghash

#define ghash_hashs adt_hashs

The adt_hashs function also works for ghash

#define ghash_hashsp adt_hashsp

The adt_hashsp function also works for ghash

#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.

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

The offset of the key into a specialized ghash entry.

#define GHASH_KEYSIZE ( PREFIX )

Value:

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

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

#define GHASH_REBUILD_DEFN ( PREFIX )

Value:

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

Define a specialized ghash table rebuild function.

#define GHASH_REHASH_DEFN ( PREFIX )

Value:

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

Define a specialized ghash table rehash function.

#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.

#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.

#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.

#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 .

#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

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.

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.

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

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

void ghash_free ( struct ghash * d )

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

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.

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.

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

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

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.

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.

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.

Examples:: adt/ghash_test.c.

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.

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

Replace or add an entry into a generic hash table.

Examples:: adt/ghash_test.c.

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

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

void ghashiter_next ( struct ghashiter * iter )

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

int ghashiter_valid ( const struct ghashiter * iter )

Check if the ghash iterator is still valid.

Generated on Thu Feb 19 11:11:50 2009 for bglibs by

1.5.4

adt ghash: Generic hash tables.

Data Structures

Defines

Functions

Detailed Description

Define Documentation

Function Documentation