Lev Walkin | adfcde2 | 2017-11-05 22:45:54 -0800 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (c) 2002-2005 Lev Walkin <vlm@lionet.info>. All rights reserved. |
| 3 | * Copyright (c) 2001-2004 Netli, Inc. All rights reserved. |
| 4 | * |
| 5 | * Redistribution and use in source and binary forms, with or without |
| 6 | * modification, are permitted provided that the following conditions |
| 7 | * are met: |
| 8 | * 1. Redistributions of source code must retain the above copyright |
| 9 | * notice, this list of conditions and the following disclaimer. |
| 10 | * 2. Redistributions in binary form must reproduce the above copyright |
| 11 | * notice, this list of conditions and the following disclaimer in the |
| 12 | * documentation and/or other materials provided with the distribution. |
| 13 | * |
| 14 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND |
| 15 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 16 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 17 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
| 18 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| 19 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| 20 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 21 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| 22 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
| 23 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| 24 | * SUCH DAMAGE. |
| 25 | * |
| 26 | * $Id: genhash.h 447 2005-06-07 06:51:10Z vlm $ |
| 27 | */ |
| 28 | #ifndef __GENHASH_H__ |
| 29 | #define __GENHASH_H__ |
| 30 | |
| 31 | /* |
| 32 | * General purpose hashing framework. |
| 33 | * Refer to the corresponding .c source file for the detailed description. |
| 34 | * |
| 35 | * WARNING: Generally, functions don't allow NULL's to be passed |
| 36 | * as the genhash_t pointers, if not explicitly stated otherwise. |
| 37 | */ |
| 38 | |
| 39 | typedef struct genhash_s genhash_t; |
| 40 | |
| 41 | /* |
| 42 | * Create a new hash table |
| 43 | * keycmpf : function which returns 0 if keys are equal, else !0 |
| 44 | * keyhashf : function which computes the hash value of a key |
| 45 | * keydestroyf : function for destroying keys, can be NULL for no destructor |
| 46 | * valuedestroyf: function for destroying values, can be NULL for no destructor |
| 47 | */ |
| 48 | genhash_t *genhash_new( |
| 49 | int (*keycmpf) (const void *key1, const void *key2), |
| 50 | unsigned int (*keyhashf) (const void *key), |
| 51 | void (*keydestroyf) (void *key), |
| 52 | void (*valuedestroyf) (void *value)); |
| 53 | |
| 54 | /* |
| 55 | * Re-initialize genhash structure with new callback functions. |
| 56 | * (Rarely ever used). |
| 57 | */ |
| 58 | int genhash_reinit( |
| 59 | genhash_t *hash, |
| 60 | int (*keycmpf) (const void *key1, const void *key2), |
| 61 | unsigned int (*keyhashf) (const void *key), |
| 62 | void (*keydestroyf) (void *key), |
| 63 | void (*valuedestroyf) (void *value)); |
| 64 | |
| 65 | /* |
| 66 | * Initialize the LRU-driven elements count limiting |
| 67 | * and/or set a new Least Recently Used list size limit. |
| 68 | * If a new entry is being added to the hash, the least recently used entry |
| 69 | * (one at the bottom of the LRU list) will be automatically deleted. |
| 70 | * The deletion may be skipped if the hash is very small |
| 71 | * (currently, "small" means no longer than 4 entries). |
| 72 | * This function is immune to NULL argument. |
| 73 | * |
| 74 | * RETURN VALUES: |
| 75 | * The previous LRU limit, or -1/EINVAL when h is NULL. |
| 76 | * EXAMPLE: |
| 77 | * genhash_set_lru_limit(h, 1500); // Maximum 1500 entries in the hash |
| 78 | */ |
| 79 | int genhash_set_lru_limit(genhash_t *h, int new_lru_limit); |
| 80 | |
| 81 | /* |
| 82 | * Set the system-wide (!!!) limit on maximum number of buckets. |
| 83 | * If the value is 0, the hash is allowed to store only 4 elements inline |
| 84 | * (buckets allocation is suppressed). |
| 85 | * If the value is 1, the hash turns out into a linked list. |
| 86 | * The default limit is about 1M buckets. |
| 87 | * RETURN VALUES: |
| 88 | * The previous buckets number limit. |
| 89 | */ |
| 90 | int genhash_set_buckets_limit(int new_max_number_of_buckets); |
| 91 | |
| 92 | /* |
| 93 | * destroys a hash, freeing each key and/or value. |
| 94 | * Keys are always destroyed before values using the destructors |
| 95 | * specified upon hash creation. |
| 96 | * This function is immune to NULL argument. |
| 97 | */ |
| 98 | void genhash_destroy(genhash_t *h); |
| 99 | |
| 100 | /* |
| 101 | * Delete all elements from the hash, retaining the hash structure itself. |
| 102 | * Optionally, it may be told to invoke, or not invoke the corresponding |
| 103 | * key/value destructors. |
| 104 | * This function is immune to NULL argument. |
| 105 | * |
| 106 | * EXAMPLE: |
| 107 | * genhash_empty(h, 1, 1); // Remove all entries, invoking destructors |
| 108 | */ |
| 109 | void genhash_empty(genhash_t *h, int freekeys, int freevalues); |
| 110 | |
| 111 | /* |
| 112 | * Add, returns 0 on success, -1 on failure (ENOMEM). Note, you CAN add |
| 113 | * records with duplicate keys. No guarantees about order preservations. |
| 114 | * |
| 115 | * EXAMPLE: |
| 116 | * char *key_str = strdup("key"); |
| 117 | * char *val_str = strdup("arbitrary value"); |
| 118 | * if(genhash_add(h, key_str, val_str) != 0) { |
| 119 | * free(key_str); |
| 120 | * free(val_str); |
| 121 | * perror("genhash_add failed"); |
| 122 | * exit(EX_SOFTWARE); |
| 123 | * } |
| 124 | */ |
| 125 | int genhash_add(genhash_t *h, void *key, void *value); |
| 126 | |
| 127 | /* |
| 128 | * Add, but only if a mapping is not there already. |
| 129 | * RETURN VALUES: |
| 130 | * 0: Element added successfully. |
| 131 | * -1/EINVAL: Invalid arguments (key == NULL). |
| 132 | * -1/EEXIST: Duplicate entry is found. |
| 133 | * -1/ENOMEM: Memory allocation failed |
| 134 | */ |
| 135 | int genhash_addunique(genhash_t *h, void *key, void *value); |
| 136 | |
| 137 | /* |
| 138 | * Fetch - returns pointer to a value, NULL/ESRCH if not found |
| 139 | */ |
| 140 | void *genhash_get(genhash_t *h, const void *key); |
| 141 | |
| 142 | /* |
| 143 | * Delete - returns 0 on success, -1/ESRCH if not found. |
| 144 | * Keys are always destroyed before values using the destructors |
| 145 | * specified upon hash creation. |
| 146 | */ |
| 147 | int genhash_del(genhash_t *h, void *key); |
| 148 | |
| 149 | /* |
| 150 | * Return the number of elements in a hash. |
| 151 | * This function is immune to NULL argument. |
| 152 | */ |
| 153 | int genhash_count(genhash_t *h); |
| 154 | |
| 155 | /* |
| 156 | * External iterator structure for using with iterator-based walking functions. |
| 157 | * This declaration is NOT INTENDED TO BE USED BY AN APPLICATION DIRECTLY |
| 158 | * The pointer to the already allocated structure must be passed to |
| 159 | * genhash_iter*() functions. |
| 160 | */ |
| 161 | typedef struct genhash_iter_s { |
| 162 | genhash_t *hash_ptr; |
| 163 | union { |
| 164 | int item_number; |
| 165 | void *location; |
| 166 | } un; |
| 167 | int order_lru_first; |
| 168 | struct genhash_iter_s *iter_prev; |
| 169 | struct genhash_iter_s *iter_next; |
| 170 | } genhash_iter_t; |
| 171 | |
| 172 | /* |
| 173 | * Initialize the iterator for walking through the hash. |
| 174 | * The memory block to be used as iterator is provided by the (*iter) pointer. |
| 175 | * This memory must be allocated (possibly, on the stack) by the caller. |
| 176 | * OWNERSHIP: |
| 177 | * The initialized iterator must be disposed of by calling |
| 178 | * genhash_iter_done(). |
| 179 | * ORDER: |
| 180 | * By default, the elements are iterated in the "most recent first" order, |
| 181 | * use reverse_order to change that. For very small number of entries |
| 182 | * (currently, 4) the order may be IGNORED. |
| 183 | * RETURN VALUES: |
| 184 | * number of entries the hash had at the moment. |
| 185 | */ |
| 186 | int genhash_iter_init(genhash_iter_t *iter, |
| 187 | genhash_t *hash_to_use, int reverse_order); |
| 188 | |
| 189 | /* |
| 190 | * Returns the key and value of each element in optional (key) and (value), |
| 191 | * which must be passed as the pointers to pointers (hence these ***'s). |
| 192 | * OWNERSHIP: |
| 193 | * The key and value are pointers to the internally manageed locations. |
| 194 | * RETURN VALUES: |
| 195 | * 0 if no more elements will be returned, otherwise 1. |
| 196 | * EXAMPLE: |
| 197 | * key_type_t *key; // Pointer to key |
| 198 | * value_type_t *val; // Pointer to value |
| 199 | * genhash_iter_t iter; // Iterator structure |
| 200 | * genhash_iter_init(&iter, hash_ptr, 0); // Prepare iterator |
| 201 | * while(genhash_iter(&iter, &key, &val)) // Iterate over hash elements |
| 202 | * print_keyval(key, val); // Use key and value |
| 203 | * genhash_iter_done(&iter); // Done iterations. |
| 204 | */ |
| 205 | int genhash_iter(genhash_iter_t *iter, void */***/key, void */***/val); |
| 206 | |
| 207 | /* |
| 208 | * Dispose of the iterator. |
| 209 | * After this operations, the iterator contents unusable |
| 210 | * and shall not be accesed. (genhash_iter_init() is OK). |
| 211 | */ |
| 212 | void genhash_iter_done(genhash_iter_t *iter); |
| 213 | |
| 214 | |
| 215 | /****************************************************************************/ |
| 216 | |
| 217 | /* |
| 218 | * The following hashing and comparison functions are provided for |
| 219 | * you, or you may supply your own. |
| 220 | */ |
| 221 | unsigned int hashf_int (const void *key); /* Key is an int * */ |
| 222 | int cmpf_int (const void *key1, const void *key2); |
| 223 | |
| 224 | unsigned int hashf_void (const void *key); |
| 225 | int cmpf_void (const void *key1, const void *key2); |
| 226 | |
| 227 | unsigned int hashf_string (const void *key); |
| 228 | int cmpf_string (const void *key1, const void *key2); |
| 229 | |
| 230 | #endif /* __GENHASH_H__ */ |