hash_table.h File Reference

A general purpose hash table. More...

Go to the source code of this file.

## Macros

#define | HASH_TABLE_ITERATE(table, key, value)
| Utility macro to simplify common case of iterating over a hash table.

## Typedefs

typedef unsigned(* | hash_func_t) (const char *key)
| The type signature for a hash function given to hash_table_create.

## Functions

struct hash_table * | hash_table_create (int buckets, hash_func_t func)
| Create a new hash table.
void | hash_table_clear (struct hash_table *h, void(*delete_func)(void *))
| Remove all entries from an hash table.
void | hash_table_delete (struct hash_table *h)
| Delete a hash table.
int | hash_table_size (struct hash_table *h)
| Count the entries in a hash table.
double | hash_table_load (struct hash_table *h)
| Return the proportion of elements vs buckets in the table.
int | hash_table_insert (struct hash_table *h, const char *key, const void *value)
| Insert a key and value.
void * | hash_table_lookup (struct hash_table *h, const char *key)
| Look up a value by key.
void * | hash_table_remove (struct hash_table *h, const char *key)
| Remove a value by key.
void | hash_table_firstkey (struct hash_table *h)
| Begin iteration over all keys.
int | hash_table_nextkey (struct hash_table *h, char **key, void **value)
| Continue iteration over all keys.
void | hash_table_randomkey (struct hash_table *h, int *offset_bookkeep)
| Begin iteration over all keys from a random offset.
int | hash_table_nextkey_with_offset (struct hash_table *h, int offset_bookkeep, char **key, void **value)
| Continue iteration over all keys from an arbitray offset.
int | hash_table_fromkey (struct hash_table *h, const char *key)
| Begin iteration at the given key.
unsigned | hash_string (const char *s)
| A default hash function.
char ** | hash_table_keys_array (struct hash_table *h)
| Return a NULL-termianted array with a copy of all the current keys.
void | hash_table_free_keys_array (char **keys)
| Free an array generated from hash_table_free_keys_array.

## Detailed Description

A general purpose hash table.

This hash table module maps C strings to arbitrary objects (void pointers). For example, to store a file object using the pathname as a key:

    struct hash_table *h;
    h = hash_table_create(0,0);

    FILE * file = fopen(pathname,"r");

    hash_table_insert(h,pathname,file);
    file = hash_table_lookup(h,pathname);
    file = hash_table_remove(h,pathname);

To list all of the items in a hash table, use hash_table_firstkey and hash_table_nextkey like this:

    char *key;
    void *value;

    hash_table_firstkey(table);
    while(hash_table_nextkey(&key,&value)) {
            printf("table contains: %s\n",key);
    }

## Macro Definition Documentation

## HASH_TABLE_ITERATE

#define HASH_TABLE_ITERATE | ( |  | table,
|  |  | key,
|  |  | value )

Value:
hash_table_firstkey(table); while(hash_table_nextkey(table,&key,(void**)&value))
hash_table_firstkey
void hash_table_firstkey(struct hash_table *h)
Begin iteration over all keys.
hash_table_nextkey
int hash_table_nextkey(struct hash_table *h, char **key, void **value)
Continue iteration over all keys.

Utility macro to simplify common case of iterating over a hash table.

Use as follows:

    char *key;
    void *value;

    HASH_TABLE_ITERATE(table,key,value) {
            printf("table contains: %s\n",key);
    }

## Typedef Documentation

## hash_func_t

typedef unsigned(* hash_func_t) (const char *key)

The type signature for a hash function given to hash_table_create.

## Function Documentation

## hash_table_create()

struct hash_table * hash_table_create | ( | int | buckets,
|  | hash_func_t | func )

Create a new hash table.

Parameters

  buckets | The number of buckets in the table. If zero, a default value will be used.
  func | The default hash function to be used. If zero, hash_string will be used.

Returns
  A pointer to a new hash table.

## hash_table_clear()

void hash_table_clear | ( | struct hash_table * | h,
|  | void(* | delete_func )(void *) )

Remove all entries from an hash table.

Parameters

  h | The hash table to delete.
  delete_func | If non-null, will be invoked on each object to delete it.

## hash_table_delete()

void hash_table_delete | ( | struct hash_table * | h | ) |

Delete a hash table.

Note that this function will not delete all of the objects contained within the hash table.

Parameters

  h | The hash table to delete.

## hash_table_size()

int hash_table_size | ( | struct hash_table * | h | ) |

Count the entries in a hash table.

Returns
  The number of entries in the table.

Parameters

  h | A pointer to a hash table.

## hash_table_load()

double hash_table_load | ( | struct hash_table * | h | ) |

Return the proportion of elements vs buckets in the table.

Returns
  The load of the table.

Parameters

  h | A pointer to a hash table.

## hash_table_insert()

int hash_table_insert | ( | struct hash_table * | h,
|  | const char * | key,
|  | const void * | value )

Insert a key and value.

This call will fail if the table already contains the same key. You must call hash_table_remove to remove it. Also note that you cannot insert a null value into the table.

Parameters

  h | A pointer to a hash table.
  key | A pointer to a string key which will be hashed and duplicated.
  value | A pointer to store with the key.

Returns
  One if the insert succeeded, failure otherwise

## hash_table_lookup()

void * hash_table_lookup | ( | struct hash_table * | h,
|  | const char * | key )

Look up a value by key.

Parameters

  h | A pointer to a hash table.
  key | A string key to search for.

Returns
  If found, the pointer associated with the key, otherwise null.

## hash_table_remove()

void * hash_table_remove | ( | struct hash_table * | h,
|  | const char * | key )

Remove a value by key.

Parameters

  h | A pointer to a hash table.
  key | A string key to remove.

Returns
  If found, the pointer associated with the key, otherwise null.

## hash_table_firstkey()

void hash_table_firstkey | ( | struct hash_table * | h | ) |

Begin iteration over all keys.

This function begins a new iteration over a hash table, allowing you to visit every key and value in the table. Next, invoke hash_table_nextkey to retrieve each value in order.

Parameters

  h | A pointer to a hash table.

## hash_table_nextkey()

int hash_table_nextkey | ( | struct hash_table * | h,
|  | char ** | key,
|  | void ** | value )

Continue iteration over all keys.

This function returns the next key and value in the iteration. Warning: It cannot be called after either hash_table_insert or hash_table_remove during the same iteration. If this is needed, consider iterating using manual hash_table_lookup with keys from hash_table_keys_array.

Parameters

  h | A pointer to a hash table.
  key | A pointer to a key pointer.
  value | A pointer to a value pointer.

Returns
  Zero if there are no more elements to visit, one otherwise.

## hash_table_randomkey()

void hash_table_randomkey | ( | struct hash_table * | h,
|  | int * | offset_bookkeep )

Begin iteration over all keys from a random offset.

This function begins a new iteration over a hash table, allowing you to visit every key and value in the table. Next, invoke hash_table_nextkey_with_offset to retrieve each value in order.

Parameters

  h | A pointer to a hash table.
  offset_bookkeep | An integer to pointer where the origin to the iteration is recorded.

## hash_table_nextkey_with_offset()

int hash_table_nextkey_with_offset | ( | struct hash_table * | h,
|  | int | offset_bookkeep,
|  | char ** | key,
|  | void ** | value )

Continue iteration over all keys from an arbitray offset.

This function returns the next key and value in the iteration.

Parameters

  h | A pointer to a hash table.
  offset_bookkeep | The origin for this iteration. See hash_table_randomkey
  key | A pointer to a key pointer.
  value | A pointer to a value pointer.

Returns
  Zero if there are no more elements to visit, one otherwise.

## hash_table_fromkey()

int hash_table_fromkey | ( | struct hash_table * | h,
|  | const char * | key )

Begin iteration at the given key.

Invoke hash_table_nextkey to retrieve each value in order. Note that subsequent calls to this functions may result in different iteration orders as the hash_table may have been resized.

Parameters

  h | A pointer to a hash table.
  key | A string key to search for.

Returns
  Zero if key not in hash table, one otherwise.

## hash_string()

unsigned hash_string | ( | const char * | s | ) |

A default hash function.

Parameters

  s | A string to hash.

Returns
  An integer hash of the string.

## hash_table_keys_array()

char ** hash_table_keys_array | ( | struct hash_table * | h | ) |

Return a NULL-termianted array with a copy of all the current keys.

It is the responsibility of the caller to free this array with hash_table_free_keys_array.

Parameters

  h | A pointer to a hash table.

Returns
  NULL-termianted array of size with a copy of all the current keys.

## hash_table_free_keys_array()

void hash_table_free_keys_array | ( | char ** | keys | ) |

Free an array generated from hash_table_free_keys_array.

Parameters

  keys | NULL-termianted array of size with a copy of keys.