hashtab_defs.h (2261B)
1 #pragma once 2 3 #include <stddef.h> 4 5 /// Type for hash number (hash calculation result). 6 typedef size_t hash_T; 7 8 /// Hashtable item. 9 /// 10 /// Each item has a NUL terminated string key. 11 /// A key can appear only once in the table. 12 /// 13 /// A hash number is computed from the key for quick lookup. When the hashes 14 /// of two different keys point to the same entry an algorithm is used to 15 /// iterate over other entries in the table until the right one is found. 16 /// To make the iteration work removed keys are different from entries where a 17 /// key was never present. 18 /// 19 /// Note that this does not contain a pointer to the key and another pointer to 20 /// the value. Instead, it is assumed that the key is contained within the 21 /// value, so that you can get a pointer to the value subtracting an offset from 22 /// the pointer to the key. 23 /// This reduces the size of this item by 1/3. 24 typedef struct { 25 /// Cached hash number for hi_key. 26 hash_T hi_hash; 27 28 /// Item key. 29 /// 30 /// Possible values mean the following: 31 /// NULL : Item was never used. 32 /// HI_KEY_REMOVED : Item was removed. 33 /// (Any other pointer value) : Item is currently being used. 34 char *hi_key; 35 } hashitem_T; 36 37 enum { 38 /// Initial size for a hashtable. 39 /// Our items are relatively small and growing is expensive, thus start with 16. 40 /// Must be a power of 2. 41 /// This allows for storing 10 items (2/3 of 16) before a resize is needed. 42 HT_INIT_SIZE = 16, 43 }; 44 45 /// An array-based hashtable. 46 /// 47 /// Keys are NUL terminated strings. They cannot be repeated within a table. 48 /// Values are of any type. 49 /// 50 /// The hashtable grows to accommodate more entries when needed. 51 typedef struct { 52 hash_T ht_mask; ///< mask used for hash value 53 ///< (nr of items in array is "ht_mask" + 1) 54 size_t ht_used; ///< number of items used 55 size_t ht_filled; ///< number of items used or removed 56 int ht_changed; ///< incremented when adding or removing an item 57 int ht_locked; ///< counter for hash_lock() 58 hashitem_T *ht_array; ///< points to the array, allocated when it's 59 ///< not "ht_smallarray" 60 hashitem_T ht_smallarray[HT_INIT_SIZE]; ///< initial array 61 } hashtab_T;