core | glapi | vbo | math | shader | swrast | swrast_setup | tnl | tnl_dd

hash_table.c File Reference

Detailed Description

Implementation of a generic, opaque hash table data type.

Ian Romanick <>

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "main/imports.h"
#include "main/simple_list.h"
#include "hash_table.h"

Data Structures

struct  node
struct  hash_table
struct  hash_node


struct hash_tablehash_table_ctor (unsigned num_buckets, hash_func_t hash, hash_compare_func_t compare)
 Hash table constructor.
void hash_table_dtor (struct hash_table *ht)
 Release all memory associated with a hash table.
void hash_table_clear (struct hash_table *ht)
 Flush all entries from a hash table.
void * hash_table_find (struct hash_table *ht, const void *key)
 Search a hash table for a specific element.
void hash_table_insert (struct hash_table *ht, void *data, const void *key)
 Add an element to a hash table.
unsigned hash_table_string_hash (const void *key)
 Compute hash value of a string.

Function Documentation

void hash_table_clear ( struct hash_table ht  ) 

Flush all entries from a hash table.

ht Table to be cleared of its entries.

struct hash_table* hash_table_ctor ( unsigned  num_buckets,
hash_func_t  hash,
hash_compare_func_t  compare 
) [read]

Hash table constructor.

Creates a hash table with the specified number of buckets. The supplied hash and compare routines are used when adding elements to the table and when searching for elements in the table.

num_buckets Number of buckets (bins) in the hash table.
hash Function used to compute hash value of input keys.
compare Function used to compare keys.

void hash_table_dtor ( struct hash_table ht  ) 

Release all memory associated with a hash table.

This function cannot release memory occupied either by keys or data.

void* hash_table_find ( struct hash_table ht,
const void *  key 

Search a hash table for a specific element.

ht Table to be searched
key Key of the desired element
The data value supplied to hash_table_insert when the element with the matching key was added. If no matching key exists in the table, NULL is returned.

void hash_table_insert ( struct hash_table ht,
void *  data,
const void *  key 

Add an element to a hash table.

unsigned hash_table_string_hash ( const void *  key  ) 

Compute hash value of a string.

Computes the hash value of a string using the DJB2 algorithm developed by Professor Daniel J. Bernstein. It was published on comp.lang.c once upon a time. I was unable to find the original posting in the archives.

key Pointer to a NUL terminated string to be hashed.
See also:

Generated on Sun Sep 27 06:48:02 2009 for Mesa Vertex and Fragment Program code by  doxygen 1.5.4