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