Find file
Fetching contributors…
Cannot retrieve contributors at this time
122 lines (101 sloc) 3.72 KB
/* An implementation of hash tables:
* Copyright(C) 2000-2002 by Salvatore Sanfilippo <>
* This software is under the GNU GPL license
#include <sys/types.h>
#include "ens.h"
#ifndef _AHT_H
#define _AHT_H
/* #define AHT_USE_SLAB */
/* ------------------------------ exit codes -------------------------------- */
#define HT_OK 0 /* Success */
#define HT_FOUND 1 /* Key found */
#define HT_NOTFOUND 2 /* Key not found */
#define HT_BUSY 3 /* Key already exist */
#define HT_NOMEM 4 /* Out of memory */
#define HT_IOVERFLOW 5 /* Index overflow */
#define HT_INVALID 6 /* Invalid argument */
#define HT_INITIAL_SIZE 256
/* ------------------ structures for the object allocator ------------------- */
#define SLAB_ELE 256 /* cant be > of 256 */
#define SLAB_OBJSZ 8 /* need to be multiple of 4 */
#define SLAB_PTRSZ (sizeof(void*))
struct ht_cache; /* forward declaration */
struct ht_slab {
struct ht_slab *next;
struct ht_slab *prev;
struct ht_cache *parent;
u_int32_t free;
u_int8_t freelist[SLAB_ELE];
unsigned char mem[SLAB_ELE*(SLAB_OBJSZ+SLAB_PTRSZ)];
struct ht_cache {
struct ht_slab *head;
struct ht_slab *tail;
u_int32_t slabs;
#endif /* AHT_USE_SLAB */
/* ----------------------- hash table structures -----------------------------*/
struct ht_ele {
void *key;
void *data;
struct hashtable {
struct ht_ele **table;
unsigned int size;
unsigned int sizemask;
unsigned int used;
unsigned int collisions;
u_int32_t (*hashf)(void *key);
int (*key_compare)(void *key1, void *key2);
void (*key_destructor)(void *key);
void (*val_destructor)(void *obj);
struct ht_cache *cache;
/* ----------------------------- Prototypes ----------------------------------*/
int ht_init(struct hashtable *t);
int ht_move(struct hashtable *orig, struct hashtable *dest, unsigned int index);
int ht_expand(struct hashtable *t, size_t size);
int ht_add(struct hashtable *t, void *key, void *data);
int ht_replace(struct hashtable *t, void *key, void *data);
int ht_rm(struct hashtable *t, void *key);
int ht_destroy(struct hashtable *t);
int ht_free(struct hashtable *t, unsigned int index);
int ht_search(struct hashtable *t, void *key, unsigned int *found_index);
int ht_get_byindex(struct hashtable *t, unsigned int index);
int ht_resize(struct hashtable *t);
/* provided destructors */
void ht_destructor_free(void *obj);
#define ht_no_destructor NULL
/* provided compare functions */
int ht_compare_ptr(void *key1, void *key2);
int ht_compare_string(void *key1, void *key2);
/* ------------------------ The hash functions ------------------------------ */
u_int32_t djb_hash(unsigned char *buf, size_t len);
u_int32_t djb_hashR(unsigned char *buf, size_t len);
u_int32_t trivial_hash(unsigned char *buf, size_t len);
u_int32_t trivial_hashR(unsigned char *buf, size_t len);
u_int32_t ht_strong_hash(u_int8_t *k, u_int32_t length, u_int32_t initval);
u_int32_t __ht_strong_hash(u_int8_t *k, u_int32_t length, u_int32_t initval);
/* ----------------- hash functions for common data types ------------------- */
u_int32_t ht_hash_string(void *key);
/* ----------------------------- macros --------------------------------------*/
#define ht_set_hash(t,f) ((t)->hashf = (f))
#define ht_set_key_destructor(t,f) ((t)->key_destructor = (f))
#define ht_set_val_destructor(t,f) ((t)->val_destructor = (f))
#define ht_set_key_compare(t,f) ((t)->key_compare = (f))
#define ht_collisions(t) ((t)->collisions)
#define ht_size(t) ((t)->size)
#define ht_used(t) ((t)->used)
#define ht_key(t, i) ((t)->table[(i)]->key)
#define ht_value(t, i) ((t)->table[(i)]->data)
#define dprintf(x...) do { printf(x); fflush(stdout); } while(0)
#define dprintf(x...)
#endif /* _AHT_H */