1 /* An implementation of hash tables: 2 * Copyright(C) 2000-2004 by Salvatore Sanfilippo <antirez@invece.org> 3 * 4 * This software is under the GNU GPL license 5 */ 6 7 #include <sys/types.h> 8 9 #ifndef _AHT_H 10 #define _AHT_H 11 12 /* Fix to compile under WIN32/MINGW and SunOS */ 13 #if defined(WIN32) || defined(__sun__) 14 #ifndef u_int8_t 15 #define u_int8_t unsigned char 16 #define u_int16_t unsigned short 17 #define u_int32_t unsigned int 18 #endif 19 #endif 20 21 /* ------------------------------ exit codes -------------------------------- */ 22 #define HT_OK 0 /* Success */ 23 #define HT_FOUND 1 /* Key found */ 24 #define HT_NOTFOUND 2 /* Key not found */ 25 #define HT_BUSY 3 /* Key already exist */ 26 #define HT_NOMEM 4 /* Out of memory */ 27 #define HT_IOVERFLOW 5 /* Index overflow */ 28 #define HT_INVALID 6 /* Invalid argument */ 29 30 #define HT_INITIAL_SIZE 256 31 32 /* ----------------------- hash table structures -----------------------------*/ 33 struct ht_ele { 34 void *key; 35 void *data; 36 }; 37 38 struct hashtable { 39 struct ht_ele **table; 40 unsigned int size; 41 unsigned int sizemask; 42 unsigned int used; 43 unsigned int collisions; 44 u_int32_t (*hashf)(void *key); 45 int (*key_compare)(void *key1, void *key2); 46 void (*key_destructor)(void *key); 47 void (*val_destructor)(void *obj); 48 }; 49 50 /* ----------------------------- Prototypes ----------------------------------*/ 51 int ht_init(struct hashtable *t); 52 int ht_move(struct hashtable *orig, struct hashtable *dest, unsigned int index); 53 int ht_expand(struct hashtable *t, size_t size); 54 int ht_add(struct hashtable *t, void *key, void *data); 55 int ht_replace(struct hashtable *t, void *key, void *data); 56 int ht_rm(struct hashtable *t, void *key); 57 int ht_destroy(struct hashtable *t); 58 int ht_free(struct hashtable *t, unsigned int index); 59 int ht_search(struct hashtable *t, void *key, unsigned int *found_index); 60 int ht_get_byindex(struct hashtable *t, unsigned int index); 61 int ht_resize(struct hashtable *t); 62 void **ht_get_array(struct hashtable *t); 63 64 /* provided destructors */ 65 void ht_destructor_free(void *obj); 66 #define ht_no_destructor NULL 67 68 /* provided compare functions */ 69 int ht_compare_ptr(void *key1, void *key2); 70 int ht_compare_string(void *key1, void *key2); 71 72 /* ------------------------ The hash functions ------------------------------ */ 73 u_int32_t djb_hash(unsigned char *buf, size_t len); 74 u_int32_t djb_hashR(unsigned char *buf, size_t len); 75 u_int32_t trivial_hash(unsigned char *buf, size_t len); 76 u_int32_t trivial_hashR(unsigned char *buf, size_t len); 77 u_int32_t ht_strong_hash(u_int8_t *k, u_int32_t length, u_int32_t initval); 78 u_int32_t __ht_strong_hash(u_int8_t *k, u_int32_t length, u_int32_t initval); 79 80 /* ----------------- hash functions for common data types ------------------- */ 81 u_int32_t ht_hash_string(void *key); 82 u_int32_t ht_hash_pointer(void *key); 83 84 /* ----------------------------- macros --------------------------------------*/ 85 #define ht_set_hash(t,f) ((t)->hashf = (f)) 86 #define ht_set_key_destructor(t,f) ((t)->key_destructor = (f)) 87 #define ht_set_val_destructor(t,f) ((t)->val_destructor = (f)) 88 #define ht_set_key_compare(t,f) ((t)->key_compare = (f)) 89 #define ht_collisions(t) ((t)->collisions) 90 #define ht_size(t) ((t)->size) 91 #define ht_used(t) ((t)->used) 92 #define ht_key(t, i) ((t)->table[(i)]->key) 93 #define ht_value(t, i) ((t)->table[(i)]->data) 94 95 #endif /* _AHT_H */ 96