1 #ifndef KHTABLE_H 2 #define KHTABLE_H 3 4 #include <stdlib.h> 5 #include <stdint.h> 6 #include <stdio.h> 7 8 // KHTable - Minimalistic hash table without deletion support 9 // This uses a block allocator for its entries, so it's quite fast! 10 11 /** 12 * Entry structure for KHTable. The datastructure stored in the hashtable 13 * should contain this in some form another, e.g. 14 * 15 * struct myStuff { 16 * KHTableEntry base; 17 * const char *key; 18 * size_t keyLen; 19 * int foo; 20 * int bar; 21 * }; 22 * 23 * The entry should contain the key and the key length, or at least have a way 24 * that it may be accessed (See Compare function below) 25 */ 26 typedef struct KHTableEntry { 27 struct KHTableEntry *next; 28 } KHTableEntry; 29 30 typedef struct { 31 // Compare two entries and see if they match 32 // The `item` is an entry previously returned via `Alloc`. 33 // s and n are the key data and length. h is the hash itself. 34 // This function is used when retrieving items from the table, and also when 35 // inserting new items - to check for duplicates. 36 // 37 // It is assumed that the `item` is part of a larger user structure, and that 38 // you have a way to retrieve the actual key/length from the item. 39 // 40 // Note that the hash is provided for convenience, in the event that the user 41 // structure also maintains the hash (rather than recomputing on demand). In 42 // this case, the hash can also be compared with the existing hash, and if 43 // they don't match, the actual string comparison can be bypassed. 44 // 45 // Should return 0 if the key matches, and nonzero otherwise 46 int (*Compare)(const KHTableEntry *item, const void *s, size_t n, uint32_t h); 47 48 // Retrieve the hash from the entry. This should extract the key and key length 49 // from the entry and return the hash. Note that you may also cache the hash 50 // value in the entry if you so desire. 51 uint32_t (*Hash)(const KHTableEntry *ent); 52 53 // Allocate memory for a new entry. This is called via KHTable_GetEntry, and 54 // should allocate enough memory for the entry and the encompassing user 55 // structure. 56 // 57 // The pointer passed is the `ctx` argument to KHTable_Init(). 58 // Note that there is no API to free an individual item. 59 KHTableEntry *(*Alloc)(void *); 60 61 // Print a textual representation of the entry to the given file. This is 62 // used when printing the hash table. This function can be NULL 63 void (*Print)(const KHTableEntry *ent, FILE *fp); 64 } KHTableProcs; 65 66 typedef struct KHTable { 67 // Context (`ctx`) - usually an allocator of some sort 68 void *alloc; 69 70 // Buckets for the table 71 KHTableEntry **buckets; 72 73 // Number of buckets 74 size_t numBuckets; 75 76 // Number of items 77 size_t numItems; 78 79 // Item handling functions 80 KHTableProcs procs; 81 } KHTable; 82 83 /** 84 * Initialize a new table. Procs contains the routines for the table itself. 85 * ctx is the allocator context passed to Alloc() 86 * estSize is the approximate size of the table. This is used to estimate how 87 * many buckets to initially create, and can help save on the number of rehashes. 88 * 89 * Note that currently there is no API to free individual elements. It is assumed 90 * that the allocator is a block allocator. 91 */ 92 void KHTable_Init(KHTable *table, const KHTableProcs *procs, void *ctx, size_t estSize); 93 94 /** 95 * Free the storage space used by the buckets array. This does not free your own 96 * entries 97 */ 98 void KHTable_Free(KHTable *table); 99 100 /** 101 * Resets the table but does not free the entries themselves 102 */ 103 void KHTable_Clear(KHTable *table); 104 105 /** 106 * Free individual items. This is passed both the `ctx` (as the context from 107 * KHTable_Init()), and the `arg` (for the current call). 108 * 109 * This function also has the effect of calling KHTable_Free() 110 */ 111 void KHTable_FreeEx(KHTable *table, void *arg, 112 void (*Free)(KHTableEntry *entry, void *ctx, void *arg)); 113 /** 114 * Get an entry from the hash table. 115 * s, n are the buffer and length of the key. hash must be provided and is the 116 * hashed value of the key. This should be consistent with whatever procs.Hash() 117 * will give for the key. 118 * 119 * isNew is an in/out parameter. If isNew is not NULL, a new entry will be created 120 * if it does not already exists; and isNew will be set to a nonzero value. 121 * 122 */ 123 KHTableEntry *KHTable_GetEntry(KHTable *table, const void *s, size_t n, uint32_t hash, int *isNew); 124 125 /** 126 * Dumps a textual representation of the hash table to the given output stream 127 */ 128 void KHTable_Dump(const KHTable *table, FILE *fp); 129 130 typedef struct { 131 KHTable *ht; 132 size_t curBucket; 133 KHTableEntry *cur; 134 } KHTableIterator; 135 136 void KHTableIter_Init(KHTable *ht, KHTableIterator *iter); 137 KHTableEntry *KHtableIter_Next(KHTableIterator *iter); 138 139 #endif