1 /* Storing keys in hash tables, similar to Perl's associative arrays. 2 * 3 */ 4 #ifndef eslKEYHASH_INCLUDED 5 #define eslKEYHASH_INCLUDED 6 #include "esl_config.h" 7 8 #include <stdio.h> /* for FILE */ 9 10 /* ESL_KEYHASH: 11 * a dynamically resized hash structure; 12 * contains a hash table and associated data 13 * 14 * Each key string is associated with an index i = (0..nkeys-1). 15 * Key strings are stored in one array, in smem. 16 * Each key has an offset in this array, key_offset[i]. 17 * Thus key number <i> is at: smem + key_offset[i]. 18 * 19 * The keys are hashed, and stored in linked lists in 20 * a hashtable by their index i = (0..nkeys-1), with -1 21 * as a sentinel for end-of-list. 22 * 23 * hashtable[0..hashsize-1] = head of linked list; 24 * index of first elem in list (0..nkeys-1), 25 * or -1 if empty. 26 * nxt[0..nkeys-1] = next elem in list (0..nkeys-1), or -1 if none. 27 * 28 * Thus a typical loop, looking for a <key>: 29 * uint32_t val = jenkins_hash(key, kh->hashsize); 30 * for (i = kh->hashtable[val]; i != -1; i = kh->nxt[i]) 31 * if (strcmp(key, kh->smem + kh->key_offset[i]) == 0) found_it; 32 * 33 */ 34 typedef struct { 35 int *hashtable; /* hashtable[0..hashsize-1] = index of first elem, or -1 */ 36 uint32_t hashsize; /* size of the hash table */ 37 38 int *key_offset; /* key [idx=0..nkeys-1] starts at smem + key_offset[idx] */ 39 int *nxt; /* nxt [idx=0..nkeys-1], next "pointers" in hash table */ 40 int nkeys; /* number of keys stored */ 41 int kalloc; /* number of keys allocated for */ 42 43 char *smem; /* Array of memory for storing key strings (w/ \0's) */ 44 int salloc; /* current allocated size of <key_mem> */ 45 int sn; /* current used size of key strings, inclusive \0's */ 46 } ESL_KEYHASH; 47 48 extern ESL_KEYHASH *esl_keyhash_Create(void); 49 extern ESL_KEYHASH *esl_keyhash_CreateCustom(uint32_t hashsize, int kalloc, int salloc); 50 extern ESL_KEYHASH *esl_keyhash_Clone(const ESL_KEYHASH *kh); 51 extern char * esl_keyhash_Get(const ESL_KEYHASH *kh, int idx); 52 extern int esl_keyhash_GetNumber(const ESL_KEYHASH *kh); 53 extern size_t esl_keyhash_Sizeof(const ESL_KEYHASH *kh); 54 extern int esl_keyhash_Reuse(ESL_KEYHASH *kh); 55 extern void esl_keyhash_Destroy(ESL_KEYHASH *kh); 56 extern void esl_keyhash_Dump(FILE *fp, const ESL_KEYHASH *kh); 57 58 extern int esl_keyhash_Store ( ESL_KEYHASH *kh, const char *key, esl_pos_t n, int *ret_index); 59 extern int esl_keyhash_Lookup(const ESL_KEYHASH *kh, const char *key, esl_pos_t n, int *ret_index); 60 61 62 #endif /* eslKEYHASH_INCLUDED */ 63 64