adt ghash: Generic hash tables.

## Data Structures

struct | ghash
struct | ghashiter

## Macros

#define | ghash_entry_hash(P)
#define | ghash_entry_keyptr(P)
#define | ghash_entry_dataptr(P, 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)
#define | GHASH_DATAOFFSET(PREFIX)
#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)

## 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); \
}
ghash_add
void * ghash_add(struct ghash *d, const void *key, const void *data)
Definition ghash_add.c:74
ghash
Definition ghash.h:26

Define a specialized `ghash` table add function.

## GHASH_DATAOFFSET

#define GHASH_DATAOFFSET | ( |  | PREFIX | ) |

Value:
((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*));
GHASH_STRUCT_ENTRY
#define GHASH_STRUCT_ENTRY(PREFIX, KTYPE, DTYPE)
Definition ghash.h:92

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

## 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)
GHASH_INIT_DEFN
#define GHASH_INIT_DEFN(PREFIX, KTYPE, DTYPE, HASHFN, CMP, KCOPY, DCOPY, KFREE, DFREE)
Definition ghash.h:131

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.

## ghash_entry_dataptr

#define ghash_entry_dataptr | ( |  | P,
|  |  | L )

Value:
((P)+sizeof(adt_hash_t)+(L))
adt_hash_t
unsigned long adt_hash_t
Definition adt_common.h:10

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 | ) |

Value:
(*(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 | ) |

Value:
((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); \
}
ghash_get
void * ghash_get(struct ghash *d, const void *key)
Definition ghash_get.c:37

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); \
}
GHASH_KEYSIZE
#define GHASH_KEYSIZE(PREFIX)
Definition ghash.h:104
adt_cmp_fn
int adt_cmp_fn(const void *, const void *)
Definition adt_common.h:20
adt_free_fn
void adt_free_fn(void *)
Definition adt_common.h:12
adt_copy_fn
int adt_copy_fn(void *, const void *)
Definition adt_common.h:16
adt_hash_fn
adt_hash_t adt_hash_fn(const void *)
Definition adt_common.h:22

Define a specialized `ghash` table init function.

## GHASH_KEYOFFSET

#define GHASH_KEYOFFSET | ( |  | PREFIX | ) |

Value:
((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) \
)
GHASH_KEYOFFSET
#define GHASH_KEYOFFSET(PREFIX)
Definition ghash.h:100

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); \
}
ghash_rebuild
int ghash_rebuild(struct ghash *d)
Definition ghash_rebuild.c:9

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); \
}
ghash_rehash
int ghash_rehash(struct ghash *d)
Definition ghash_rehash.c:8

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); \
}
ghash_remove
int ghash_remove(struct ghash *d, const void *key)
Definition ghash_remove.c:12

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); \
}
ghash_search
void * ghash_search(struct ghash *d, int(*fn)(const void *entry))
Definition ghash_search.c:5

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); \
}
ghash_set
void * ghash_set(struct ghash *d, const void *key, const void *data)
Definition ghash_set.c:5

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 )

Value:
for(ghashiter_first(I,G);ghashiter_valid(I);ghashiter_next(I))
ghashiter_valid
int ghashiter_valid(const struct ghashiter *iter)
Definition ghash_iter.c:21
ghashiter_first
void ghashiter_first(struct ghashiter *iter, const struct ghash *h)
Definition ghash_iter.c:14
ghashiter_next
void ghashiter_next(struct ghashiter *iter)
Definition ghash_iter.c:29

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

## 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_entry_dataptr, ghash_entry_hash, ghash_entry_keyptr, and ghash_insert().

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, and ghash_entry_keyptr.

Referenced by ghash_get(), and ghash_remove().

## ghash_foreach()

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

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

## ghash_free()

void ghash_free | ( | struct ghash * | d | ) |

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

References ghash_entry_dataptr, and ghash_entry_keyptr.

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

## ghash_insert()

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

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

References ghash_entry_hash.

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_insert().

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, and ghash_rebuild().

## 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_entry_dataptr, ghash_entry_keyptr, ghash_find(), and ghash_insert().

## ghash_search()

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

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

## 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_add(), ghash_entry_dataptr, and ghash_get().

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