1 /** 2 * @file 3 * Hash Table data structure 4 * 5 * @authors 6 * Copyright (C) 1996-2009 Michael R. Elkins <me@mutt.org> 7 * Copyright (C) 2017-2020 Richard Russon <rich@flatcap.org> 8 * 9 * @copyright 10 * This program is free software: you can redistribute it and/or modify it under 11 * the terms of the GNU General Public License as published by the Free Software 12 * Foundation, either version 2 of the License, or (at your option) any later 13 * version. 14 * 15 * This program is distributed in the hope that it will be useful, but WITHOUT 16 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 17 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 18 * details. 19 * 20 * You should have received a copy of the GNU General Public License along with 21 * this program. If not, see <http://www.gnu.org/licenses/>. 22 */ 23 24 #ifndef MUTT_LIB_HASH_H 25 #define MUTT_LIB_HASH_H 26 27 #include <stdbool.h> 28 #include <stdint.h> 29 #include <stdlib.h> 30 31 /** 32 * union HashKey - The data item stored in a HashElem 33 */ 34 union HashKey 35 { 36 const char *strkey; ///< String key 37 unsigned int intkey; ///< Integer key 38 }; 39 40 /** 41 * struct HashElem - The item stored in a Hash Table 42 */ 43 struct HashElem 44 { 45 int type; ///< Type of data stored in Hash Table, e.g. #DT_STRING 46 union HashKey key; ///< Key representing the data 47 void *data; ///< User-supplied data 48 struct HashElem *next; ///< Linked List 49 }; 50 51 /** 52 * @defgroup hash_hdata_free_api Hash Data Free API 53 * 54 * Prototype for Hash Destructor callback function 55 * 56 * @param type Hash Type 57 * @param obj Object to free 58 * @param data Data associated with the Hash 59 * 60 * **Contract** 61 * - @a obj is not NULL 62 */ 63 typedef void (*hash_hdata_free_t)(int type, void *obj, intptr_t data); 64 65 /** 66 * @defgroup hash_gen_hash_api Hash Generator API 67 * 68 * Prototype for a Key hashing function 69 * 70 * @param key Key to hash 71 * @param num_elems Number of elements in the Hash Table 72 * 73 * Turn a Key (a string or an integer) into a hash id. 74 * The hash id will be a number between 0 and (num_elems-1). 75 */ 76 typedef size_t (*hash_gen_hash_t)(union HashKey key, size_t num_elems); 77 78 /** 79 * @defgroup hash_cmp_key_api Hash Table Compare API 80 * 81 * Prototype for a function to compare two Hash keys 82 * 83 * @param a First key to compare 84 * @param b Second key to compare 85 * @retval -1 a precedes b 86 * @retval 0 a and b are identical 87 * @retval 1 b precedes a 88 * 89 * This works like `strcmp()`. 90 */ 91 typedef int (*hash_cmp_key_t)(union HashKey a, union HashKey b); 92 93 /** 94 * struct HashTable - A Hash Table 95 */ 96 struct HashTable 97 { 98 size_t num_elems; ///< Number of elements in the Hash Table 99 bool strdup_keys : 1; ///< if set, the key->strkey is strdup()'d 100 bool allow_dups : 1; ///< if set, duplicate keys are allowed 101 struct HashElem **table; ///< Array of Hash keys 102 hash_gen_hash_t gen_hash; ///< Function to generate hash id from the key 103 hash_cmp_key_t cmp_key; ///< Function to compare two Hash keys 104 intptr_t hdata; ///< Data to pass to the hdata_free() function 105 hash_hdata_free_t hdata_free; ///< Function to free a Hash element 106 }; 107 108 typedef uint8_t HashFlags; ///< Flags for mutt_hash_new(), e.g. #MUTT_HASH_STRCASECMP 109 #define MUTT_HASH_NO_FLAGS 0 ///< No flags are set 110 #define MUTT_HASH_STRCASECMP (1 << 0) ///< use strcasecmp() to compare keys 111 #define MUTT_HASH_STRDUP_KEYS (1 << 1) ///< make a copy of the keys 112 #define MUTT_HASH_ALLOW_DUPS (1 << 2) ///< allow duplicate keys to be inserted 113 114 void mutt_hash_delete (struct HashTable *table, const char *strkey, const void *data); 115 struct HashElem * mutt_hash_find_bucket (const struct HashTable *table, const char *strkey); 116 void * mutt_hash_find (const struct HashTable *table, const char *strkey); 117 struct HashElem * mutt_hash_find_elem (const struct HashTable *table, const char *strkey); 118 void mutt_hash_free (struct HashTable **ptr); 119 struct HashElem * mutt_hash_insert (struct HashTable *table, const char *strkey, void *data); 120 void mutt_hash_int_delete (struct HashTable *table, unsigned int intkey, const void *data); 121 void * mutt_hash_int_find (const struct HashTable *table, unsigned int intkey); 122 struct HashElem * mutt_hash_int_insert (struct HashTable *table, unsigned int intkey, void *data); 123 struct HashTable *mutt_hash_int_new (size_t num_elems, HashFlags flags); 124 struct HashTable *mutt_hash_new (size_t num_elems, HashFlags flags); 125 void mutt_hash_set_destructor(struct HashTable *table, hash_hdata_free_t fn, intptr_t fn_data); 126 struct HashElem * mutt_hash_typed_insert (struct HashTable *table, const char *strkey, int type, void *data); 127 128 /** 129 * struct HashWalkState - Cursor to iterate through a Hash Table 130 */ 131 struct HashWalkState 132 { 133 size_t index; ///< Current position in table 134 struct HashElem *last; ///< Current element in linked list 135 }; 136 137 struct HashElem *mutt_hash_walk(const struct HashTable *table, struct HashWalkState *state); 138 139 #endif /* MUTT_LIB_HASH_H */ 140