PulkoMandy | 17fc759 | 2022-07-28 18:27:54 +0200 | [diff] [blame^] | 1 | /* |
| 2 | * Generic hash table routines. |
| 3 | * (c) Thomas Pornin 1998, 1999, 2000 |
| 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 | * 4. The name of the authors may not be used to endorse or promote |
| 14 | * products derived from this software without specific prior written |
| 15 | * permission. |
| 16 | * |
| 17 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR |
| 18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
| 19 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 20 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE |
| 21 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| 22 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT |
| 23 | * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR |
| 24 | * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, |
| 25 | * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE |
| 26 | * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, |
| 27 | * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 28 | * |
| 29 | */ |
| 30 | |
| 31 | #include <string.h> |
| 32 | #include "hash.h" |
| 33 | #include "mem.h" |
| 34 | |
| 35 | /* |
| 36 | * hash_string() is a sample hash function for strings |
| 37 | */ |
| 38 | int hash_string(char *s) |
| 39 | { |
| 40 | unsigned char h = 0; |
| 41 | |
| 42 | for (; *s; s ++) h ^= (unsigned char)(*s); |
| 43 | return ((int)h); |
| 44 | } |
| 45 | |
| 46 | /* |
| 47 | * struct hash_item is the basic data type to internally handle hash tables |
| 48 | */ |
| 49 | struct hash_item { |
| 50 | void *data; |
| 51 | struct hash_item *next; |
| 52 | }; |
| 53 | |
| 54 | /* |
| 55 | * This function adds an entry to the struct hash_item list |
| 56 | */ |
| 57 | static struct hash_item *add_entry(struct hash_item *blist, void *data) |
| 58 | { |
| 59 | struct hash_item *t = getmem(sizeof(struct hash_item)); |
| 60 | |
| 61 | t->data = data; |
| 62 | t->next = blist; |
| 63 | return t; |
| 64 | } |
| 65 | |
| 66 | /* |
| 67 | * This function finds a struct hash_item in a list, using the |
| 68 | * comparison function provided as cmpdata (*cmpdata() returns |
| 69 | * non-zero if the two parameters are to be considered identical). |
| 70 | * |
| 71 | * It returns 0 if the item is not found. |
| 72 | */ |
| 73 | static struct hash_item *get_entry(struct hash_item *blist, void *data, |
| 74 | int (*cmpdata)(void *, void *)) |
| 75 | { |
| 76 | while (blist) { |
| 77 | if ((*cmpdata)(data, blist->data)) return blist; |
| 78 | blist = blist->next; |
| 79 | } |
| 80 | return 0; |
| 81 | } |
| 82 | |
| 83 | /* |
| 84 | * This function acts like get_entry but deletes the found item, using |
| 85 | * the provided function deldata(); it returns 0 if the given data was |
| 86 | * not found. |
| 87 | */ |
| 88 | static struct hash_item *del_entry(struct hash_item *blist, void *data, |
| 89 | int (*cmpdata)(void *, void *), void (*deldata)(void *)) |
| 90 | { |
| 91 | struct hash_item *prev = 0, *save = blist; |
| 92 | |
| 93 | while (blist) { |
| 94 | if ((*cmpdata)(data, blist->data)) { |
| 95 | (*deldata)(blist->data); |
| 96 | if (prev) prev->next = blist->next; |
| 97 | if (save == blist) save = blist->next; |
| 98 | freemem(blist); |
| 99 | return save; |
| 100 | } |
| 101 | prev = blist; |
| 102 | blist = blist->next; |
| 103 | } |
| 104 | return 0; |
| 105 | } |
| 106 | |
| 107 | /* |
| 108 | * This function creates a new hashtable, with the hashing and comparison |
| 109 | * functions given as parameters |
| 110 | */ |
| 111 | struct HT *newHT(int n, int (*cmpdata)(void *, void *), int (*hash)(void *), |
| 112 | void (*deldata)(void *)) |
| 113 | { |
| 114 | struct HT *t = getmem(sizeof(struct HT)); |
| 115 | int i; |
| 116 | |
| 117 | t->lists = getmem(n * sizeof(struct hash_item *)); |
| 118 | for (i = 0; i < n; i ++) t->lists[i] = 0; |
| 119 | t->nb_lists = n; |
| 120 | t->cmpdata = cmpdata; |
| 121 | t->hash = hash; |
| 122 | t->deldata = deldata; |
| 123 | return t; |
| 124 | } |
| 125 | |
| 126 | /* |
| 127 | * This function adds a new entry in the hashtable ht; it returns 0 |
| 128 | * on success, or a pointer to the already present item otherwise. |
| 129 | */ |
| 130 | void *putHT(struct HT *ht, void *data) |
| 131 | { |
| 132 | int h; |
| 133 | struct hash_item *d; |
| 134 | |
| 135 | h = ((*(ht->hash))(data)) % ht->nb_lists; |
| 136 | if ((d = get_entry(ht->lists[h], data, ht->cmpdata))) |
| 137 | return d->data; |
| 138 | ht->lists[h] = add_entry(ht->lists[h], data); |
| 139 | return 0; |
| 140 | } |
| 141 | |
| 142 | /* |
| 143 | * This function adds a new entry in the hashtable ht, even if an equal |
| 144 | * entry is already there. Exercise caution ! |
| 145 | * The new entry will "hide" the old one, which means that the new will be |
| 146 | * found upon lookup/delete, not the old one. |
| 147 | */ |
| 148 | void *forceputHT(struct HT *ht, void *data) |
| 149 | { |
| 150 | int h; |
| 151 | |
| 152 | h = ((*(ht->hash))(data)) % ht->nb_lists; |
| 153 | ht->lists[h] = add_entry(ht->lists[h], data); |
| 154 | return 0; |
| 155 | } |
| 156 | |
| 157 | /* |
| 158 | * This function finds the entry corresponding to *data in the |
| 159 | * hashtable ht (using the comparison function given as argument |
| 160 | * to newHT) |
| 161 | */ |
| 162 | void *getHT(struct HT *ht, void *data) |
| 163 | { |
| 164 | int h; |
| 165 | struct hash_item *t; |
| 166 | |
| 167 | h = ((*(ht->hash))(data)) % ht->nb_lists; |
| 168 | if ((t = get_entry(ht->lists[h], data, ht->cmpdata)) == 0) |
| 169 | return 0; |
| 170 | return (t->data); |
| 171 | } |
| 172 | |
| 173 | /* |
| 174 | * This function finds and delete the entry corresponding to *data |
| 175 | * in the hashtable ht (using the comparison function given as |
| 176 | * argument to newHT). |
| 177 | */ |
| 178 | |
| 179 | int delHT(struct HT *ht, void *data) |
| 180 | { |
| 181 | int h; |
| 182 | |
| 183 | h = ((*(ht->hash))(data)) % ht->nb_lists; |
| 184 | ht->lists[h] = del_entry(ht->lists[h], data, ht->cmpdata, ht->deldata); |
| 185 | return 1; |
| 186 | } |
| 187 | |
| 188 | /* |
| 189 | * This function duplicates a given hash table; the data is not copied |
| 190 | */ |
| 191 | struct HT *copyHT(struct HT *ht) |
| 192 | { |
| 193 | struct HT *nht = newHT(ht->nb_lists, ht->cmpdata, ht->hash, |
| 194 | ht->deldata); |
| 195 | struct hash_item *t; |
| 196 | int i, j; |
| 197 | |
| 198 | for (i = 0; i < nht->nb_lists; i ++) { |
| 199 | j = 0; |
| 200 | t = ht->lists[i]; |
| 201 | while (t) { |
| 202 | t = t->next; |
| 203 | j ++; |
| 204 | } |
| 205 | if (j != 0) { |
| 206 | nht->lists[i] = getmem(j * sizeof(struct hash_item)); |
| 207 | mmv(nht->lists[i], ht->lists[i], |
| 208 | j * sizeof(struct hash_item)); |
| 209 | } |
| 210 | } |
| 211 | return nht; |
| 212 | } |
| 213 | |
| 214 | /* |
| 215 | * This function completely eradicates from memory a given hash table, |
| 216 | * releasing all objects |
| 217 | */ |
| 218 | void killHT(struct HT *ht) |
| 219 | { |
| 220 | int i; |
| 221 | struct hash_item *t, *n; |
| 222 | |
| 223 | for (i = 0; i < ht->nb_lists; i ++) for (t = ht->lists[i]; t;) { |
| 224 | n = t->next; |
| 225 | (*(ht->deldata))(t->data); |
| 226 | freemem(t); |
| 227 | t = n; |
| 228 | } |
| 229 | freemem(ht); |
| 230 | } |
| 231 | |
| 232 | /* |
| 233 | * This function stores a backup of the hash table, for context stacking |
| 234 | */ |
| 235 | void saveHT(struct HT *ht, void **buffer) |
| 236 | { |
| 237 | struct hash_item **b = (struct hash_item **)buffer; |
| 238 | int i; |
| 239 | |
| 240 | for (i = 0; i < ht->nb_lists; i ++) b[i] = ht->lists[i]; |
| 241 | } |
| 242 | |
| 243 | /* |
| 244 | * This function restores the saved state of the hash table. |
| 245 | * Do NOT use if some of the entries that were present before the backup |
| 246 | * have been removed (even temporarily). |
| 247 | */ |
| 248 | void restoreHT(struct HT *ht, void **buffer) |
| 249 | { |
| 250 | struct hash_item **b = (struct hash_item **)buffer; |
| 251 | int i; |
| 252 | |
| 253 | for (i = 0; i < ht->nb_lists; i ++) { |
| 254 | struct hash_item *t = ht->lists[i], *n; |
| 255 | |
| 256 | while (t != b[i]) { |
| 257 | n = t->next; |
| 258 | (*(ht->deldata))(t->data); |
| 259 | freemem(t); |
| 260 | t = n; |
| 261 | } |
| 262 | ht->lists[i] = b[i]; |
| 263 | } |
| 264 | } |
| 265 | |
| 266 | /* |
| 267 | * This function scans the whole table and calls the given function on |
| 268 | * each entry. |
| 269 | */ |
| 270 | void scanHT(struct HT *ht, void (*action)(void *)) |
| 271 | { |
| 272 | int i; |
| 273 | |
| 274 | for (i = 0; i < ht->nb_lists; i ++) { |
| 275 | struct hash_item *t = ht->lists[i]; |
| 276 | |
| 277 | while (t) { |
| 278 | (*action)(t->data); |
| 279 | t = t->next; |
| 280 | } |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | /* |
| 285 | * The two following fonctions are generic for storing structures |
| 286 | * uniquely identified by their name, which must be the first |
| 287 | * field of the structure. |
| 288 | */ |
| 289 | int hash_struct(void *m) |
| 290 | { |
| 291 | char *n = *(char **)m; |
| 292 | |
| 293 | return hash_string(n) & 127; |
| 294 | } |
| 295 | |
| 296 | int cmp_struct(void *m1, void *m2) |
| 297 | { |
| 298 | char *n1 = *(char **)m1, *n2 = *(char **)m2; |
| 299 | |
| 300 | return !strcmp(n1, n2); |
| 301 | } |