2 * Copyright (C) 2000, Matias Atria
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 /* simple hash tables for MDVI */
24 struct _DviHashBucket {
31 static Ulong hash_string(DviHashKey key)
36 for(h = 0, p = (Uchar *)key; *p; p++) {
38 if((g = h & 0xf0000000L) != 0) {
47 static int hash_compare(DviHashKey k1, DviHashKey k2)
49 return strcmp((char *)k1, (char *)k2);
52 void mdvi_hash_init(DviHashTable *hash)
57 hash->hash_func = NULL;
58 hash->hash_comp = NULL;
59 hash->hash_free = NULL;
62 void mdvi_hash_create(DviHashTable *hash, int size)
67 hash->buckets = xnalloc(DviHashBucket *, size);
68 for(i = 0; i < size; i++)
69 hash->buckets[i] = NULL;
70 hash->hash_func = hash_string;
71 hash->hash_comp = hash_compare;
72 hash->hash_free = NULL;
76 static DviHashBucket *hash_find(DviHashTable *hash, DviHashKey key)
81 hval = (hash->hash_func(key) % hash->nbucks);
83 for(buck = hash->buckets[hval]; buck; buck = buck->next)
84 if(hash->hash_comp(buck->key, key) == 0)
89 /* Neither keys nor data are duplicated */
90 int mdvi_hash_add(DviHashTable *hash, DviHashKey key, void *data, int rep)
92 DviHashBucket *buck = NULL;
95 if(rep != MDVI_HASH_UNCHECKED) {
96 buck = hash_find(hash, key);
98 if(buck->data == data)
100 if(rep == MDVI_HASH_UNIQUE)
102 if(hash->hash_free != NULL)
103 hash->hash_free(buck->key, buck->data);
107 buck = xalloc(DviHashBucket);
108 buck->hvalue = hash->hash_func(key);
109 hval = (buck->hvalue % hash->nbucks);
110 buck->next = hash->buckets[hval];
111 hash->buckets[hval] = buck;
115 /* save key and data */
122 void *mdvi_hash_lookup(DviHashTable *hash, DviHashKey key)
124 DviHashBucket *buck = hash_find(hash, key);
126 return buck ? buck->data : NULL;
129 static DviHashBucket *hash_remove(DviHashTable *hash, DviHashKey key)
131 DviHashBucket *buck, *last;
134 hval = hash->hash_func(key);
135 hval %= hash->nbucks;
137 for(last = NULL, buck = hash->buckets[hval]; buck; buck = buck->next) {
138 if(hash->hash_comp(buck->key, key) == 0)
145 last->next = buck->next;
147 hash->buckets[hval] = buck->next;
152 void *mdvi_hash_remove(DviHashTable *hash, DviHashKey key)
154 DviHashBucket *buck = hash_remove(hash, key);
164 void *mdvi_hash_remove_ptr(DviHashTable *hash, DviHashKey key)
166 DviHashBucket *buck, *last;
170 hval = hash->hash_func(key);
171 hval %= hash->nbucks;
173 for(last = NULL, buck = hash->buckets[hval]; buck; buck = buck->next) {
181 last->next = buck->next;
183 hash->buckets[hval] = buck->next;
185 /* destroy the bucket */
191 int mdvi_hash_destroy_key(DviHashTable *hash, DviHashKey key)
193 DviHashBucket *buck = hash_remove(hash, key);
198 hash->hash_free(buck->key, buck->data);
203 void mdvi_hash_reset(DviHashTable *hash, int reuse)
208 /* remove all keys in the hash table */
209 for(i = 0; i < hash->nbucks; i++) {
210 for(; (buck = hash->buckets[i]); ) {
211 hash->buckets[i] = buck->next;
213 hash->hash_free(buck->key, buck->data);
218 if(!reuse && hash->buckets) {
219 mdvi_free(hash->buckets);
220 hash->buckets = NULL;
222 } /* otherwise, it is left empty, ready to be reused */