bglibs: adt ghash: Generic hash tables.

bglibs

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

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

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

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); \
}
ghash
Definition: ghash.h:25

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); \
}
ghash
Definition: ghash.h:25

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
Definition: ghash.h:25
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); \
}
adt_free_fn
void adt_free_fn(void *)
Definition: adt_common.h:12
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
ghash
Definition: ghash.h:25
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 | ) | ((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
ghash
Definition: ghash.h:25

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
ghash
Definition: ghash.h:25

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
ghash
Definition: ghash.h:25

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
Definition: ghash.h:25
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
Definition: ghash.h:25
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
| ) |  | 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.