1/*********************************************************************** 2* 3* hash.h 4* 5* Hash table utilities 6* 7* Copyright (C) 2002 Roaring Penguin Software Inc. 8* 9* LIC: GPL 10* 11***********************************************************************/ 12 13#ifndef HASH_H 14#define HASH_H 15 16#include <stdlib.h> 17/* Fixed-size hash tables for now */ 18#define HASHTAB_SIZE 67 19 20/* A hash bucket */ 21typedef struct hash_bucket_t { 22 struct hash_bucket_t *next; 23 struct hash_bucket_t *prev; 24 unsigned int hashval; 25} hash_bucket; 26 27/* A hash table */ 28typedef struct hash_table_t { 29 hash_bucket *buckets[HASHTAB_SIZE]; 30 size_t hash_offset; 31 unsigned int (*compute_hash)(void *data); 32 int (*compare)(void *item1, void *item2); 33 size_t num_entries; 34} hash_table; 35 36/* Functions */ 37void hash_init(hash_table *tab, 38 size_t hash_offset, 39 unsigned int (*compute)(void *data), 40 int (*compare)(void *item1, void *item2)); 41void hash_insert(hash_table *tab, void *item); 42void hash_remove(hash_table *tab, void *item); 43void *hash_find(hash_table *tab, void *item); 44void *hash_find_next(hash_table *tab, void *item); 45size_t hash_num_entries(hash_table *tab); 46 47/* Iteration functions */ 48void *hash_start(hash_table *tab, void **cursor); 49void *hash_next(hash_table *tab, void **cursor); 50 51/* Utility function: hashpjw for strings */ 52unsigned int hash_pjw(char const *str); 53 54#endif 55