| /* |
| * Generic hash table routines. |
| * (c) Thomas Pornin 1998, 1999, 2000 |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 4. The name of the authors may not be used to endorse or promote |
| * products derived from this software without specific prior written |
| * permission. |
| * |
| * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
| * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE |
| * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT |
| * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR |
| * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, |
| * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE |
| * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, |
| * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| * |
| */ |
| |
| #include <string.h> |
| #include "hash.h" |
| #include "mem.h" |
| |
| /* |
| * hash_string() is a sample hash function for strings |
| */ |
| int hash_string(char *s) |
| { |
| unsigned char h = 0; |
| |
| for (; *s; s ++) h ^= (unsigned char)(*s); |
| return ((int)h); |
| } |
| |
| /* |
| * struct hash_item is the basic data type to internally handle hash tables |
| */ |
| struct hash_item { |
| void *data; |
| struct hash_item *next; |
| }; |
| |
| /* |
| * This function adds an entry to the struct hash_item list |
| */ |
| static struct hash_item *add_entry(struct hash_item *blist, void *data) |
| { |
| struct hash_item *t = getmem(sizeof(struct hash_item)); |
| |
| t->data = data; |
| t->next = blist; |
| return t; |
| } |
| |
| /* |
| * This function finds a struct hash_item in a list, using the |
| * comparison function provided as cmpdata (*cmpdata() returns |
| * non-zero if the two parameters are to be considered identical). |
| * |
| * It returns 0 if the item is not found. |
| */ |
| static struct hash_item *get_entry(struct hash_item *blist, void *data, |
| int (*cmpdata)(void *, void *)) |
| { |
| while (blist) { |
| if ((*cmpdata)(data, blist->data)) return blist; |
| blist = blist->next; |
| } |
| return 0; |
| } |
| |
| /* |
| * This function acts like get_entry but deletes the found item, using |
| * the provided function deldata(); it returns 0 if the given data was |
| * not found. |
| */ |
| static struct hash_item *del_entry(struct hash_item *blist, void *data, |
| int (*cmpdata)(void *, void *), void (*deldata)(void *)) |
| { |
| struct hash_item *prev = 0, *save = blist; |
| |
| while (blist) { |
| if ((*cmpdata)(data, blist->data)) { |
| (*deldata)(blist->data); |
| if (prev) prev->next = blist->next; |
| if (save == blist) save = blist->next; |
| freemem(blist); |
| return save; |
| } |
| prev = blist; |
| blist = blist->next; |
| } |
| return 0; |
| } |
| |
| /* |
| * This function creates a new hashtable, with the hashing and comparison |
| * functions given as parameters |
| */ |
| struct HT *newHT(int n, int (*cmpdata)(void *, void *), int (*hash)(void *), |
| void (*deldata)(void *)) |
| { |
| struct HT *t = getmem(sizeof(struct HT)); |
| int i; |
| |
| t->lists = getmem(n * sizeof(struct hash_item *)); |
| for (i = 0; i < n; i ++) t->lists[i] = 0; |
| t->nb_lists = n; |
| t->cmpdata = cmpdata; |
| t->hash = hash; |
| t->deldata = deldata; |
| return t; |
| } |
| |
| /* |
| * This function adds a new entry in the hashtable ht; it returns 0 |
| * on success, or a pointer to the already present item otherwise. |
| */ |
| void *putHT(struct HT *ht, void *data) |
| { |
| int h; |
| struct hash_item *d; |
| |
| h = ((*(ht->hash))(data)) % ht->nb_lists; |
| if ((d = get_entry(ht->lists[h], data, ht->cmpdata))) |
| return d->data; |
| ht->lists[h] = add_entry(ht->lists[h], data); |
| return 0; |
| } |
| |
| /* |
| * This function adds a new entry in the hashtable ht, even if an equal |
| * entry is already there. Exercise caution ! |
| * The new entry will "hide" the old one, which means that the new will be |
| * found upon lookup/delete, not the old one. |
| */ |
| void *forceputHT(struct HT *ht, void *data) |
| { |
| int h; |
| |
| h = ((*(ht->hash))(data)) % ht->nb_lists; |
| ht->lists[h] = add_entry(ht->lists[h], data); |
| return 0; |
| } |
| |
| /* |
| * This function finds the entry corresponding to *data in the |
| * hashtable ht (using the comparison function given as argument |
| * to newHT) |
| */ |
| void *getHT(struct HT *ht, void *data) |
| { |
| int h; |
| struct hash_item *t; |
| |
| h = ((*(ht->hash))(data)) % ht->nb_lists; |
| if ((t = get_entry(ht->lists[h], data, ht->cmpdata)) == 0) |
| return 0; |
| return (t->data); |
| } |
| |
| /* |
| * This function finds and delete the entry corresponding to *data |
| * in the hashtable ht (using the comparison function given as |
| * argument to newHT). |
| */ |
| |
| int delHT(struct HT *ht, void *data) |
| { |
| int h; |
| |
| h = ((*(ht->hash))(data)) % ht->nb_lists; |
| ht->lists[h] = del_entry(ht->lists[h], data, ht->cmpdata, ht->deldata); |
| return 1; |
| } |
| |
| /* |
| * This function duplicates a given hash table; the data is not copied |
| */ |
| struct HT *copyHT(struct HT *ht) |
| { |
| struct HT *nht = newHT(ht->nb_lists, ht->cmpdata, ht->hash, |
| ht->deldata); |
| struct hash_item *t; |
| int i, j; |
| |
| for (i = 0; i < nht->nb_lists; i ++) { |
| j = 0; |
| t = ht->lists[i]; |
| while (t) { |
| t = t->next; |
| j ++; |
| } |
| if (j != 0) { |
| nht->lists[i] = getmem(j * sizeof(struct hash_item)); |
| mmv(nht->lists[i], ht->lists[i], |
| j * sizeof(struct hash_item)); |
| } |
| } |
| return nht; |
| } |
| |
| /* |
| * This function completely eradicates from memory a given hash table, |
| * releasing all objects |
| */ |
| void killHT(struct HT *ht) |
| { |
| int i; |
| struct hash_item *t, *n; |
| |
| for (i = 0; i < ht->nb_lists; i ++) for (t = ht->lists[i]; t;) { |
| n = t->next; |
| (*(ht->deldata))(t->data); |
| freemem(t); |
| t = n; |
| } |
| freemem(ht); |
| } |
| |
| /* |
| * This function stores a backup of the hash table, for context stacking |
| */ |
| void saveHT(struct HT *ht, void **buffer) |
| { |
| struct hash_item **b = (struct hash_item **)buffer; |
| int i; |
| |
| for (i = 0; i < ht->nb_lists; i ++) b[i] = ht->lists[i]; |
| } |
| |
| /* |
| * This function restores the saved state of the hash table. |
| * Do NOT use if some of the entries that were present before the backup |
| * have been removed (even temporarily). |
| */ |
| void restoreHT(struct HT *ht, void **buffer) |
| { |
| struct hash_item **b = (struct hash_item **)buffer; |
| int i; |
| |
| for (i = 0; i < ht->nb_lists; i ++) { |
| struct hash_item *t = ht->lists[i], *n; |
| |
| while (t != b[i]) { |
| n = t->next; |
| (*(ht->deldata))(t->data); |
| freemem(t); |
| t = n; |
| } |
| ht->lists[i] = b[i]; |
| } |
| } |
| |
| /* |
| * This function scans the whole table and calls the given function on |
| * each entry. |
| */ |
| void scanHT(struct HT *ht, void (*action)(void *)) |
| { |
| int i; |
| |
| for (i = 0; i < ht->nb_lists; i ++) { |
| struct hash_item *t = ht->lists[i]; |
| |
| while (t) { |
| (*action)(t->data); |
| t = t->next; |
| } |
| } |
| } |
| |
| /* |
| * The two following fonctions are generic for storing structures |
| * uniquely identified by their name, which must be the first |
| * field of the structure. |
| */ |
| int hash_struct(void *m) |
| { |
| char *n = *(char **)m; |
| |
| return hash_string(n) & 127; |
| } |
| |
| int cmp_struct(void *m1, void *m2) |
| { |
| char *n1 = *(char **)m1, *n2 = *(char **)m2; |
| |
| return !strcmp(n1, n2); |
| } |