1 /*
2 * Copyright (C) 2000, Matias Atria
3 *
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.
8 *
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.
13 *
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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 */
18
19 #include <config.h>
20 #include "mdvi.h"
21
22 /* simple hash tables for MDVI */
23
24
25 struct _DviHashBucket {
26 DviHashBucket *next;
27 DviHashKey key;
28 Ulong hvalue;
29 void *data;
30 };
31
hash_string(DviHashKey key)32 static Ulong hash_string(DviHashKey key)
33 {
34 Uchar *p;
35 Ulong h, g;
36
37 for(h = 0, p = (Uchar *)key; *p; p++) {
38 h = (h << 4UL) + *p;
39 if((g = h & 0xf0000000L) != 0) {
40 h ^= (g >> 24UL);
41 h ^= g;
42 }
43 }
44
45 return h;
46 }
47
hash_compare(DviHashKey k1,DviHashKey k2)48 static int hash_compare(DviHashKey k1, DviHashKey k2)
49 {
50 return strcmp((char *)k1, (char *)k2);
51 }
52
mdvi_hash_init(DviHashTable * hash)53 void mdvi_hash_init(DviHashTable *hash)
54 {
55 hash->buckets = NULL;
56 hash->nbucks = 0;
57 hash->nkeys = 0;
58 hash->hash_func = NULL;
59 hash->hash_comp = NULL;
60 hash->hash_free = NULL;
61 }
62
mdvi_hash_create(DviHashTable * hash,int size)63 void mdvi_hash_create(DviHashTable *hash, int size)
64 {
65 int i;
66
67 hash->nbucks = size;
68 hash->buckets = xnalloc(DviHashBucket *, size);
69 for(i = 0; i < size; i++)
70 hash->buckets[i] = NULL;
71 hash->hash_func = hash_string;
72 hash->hash_comp = hash_compare;
73 hash->hash_free = NULL;
74 hash->nkeys = 0;
75 }
76
hash_find(DviHashTable * hash,DviHashKey key)77 static DviHashBucket *hash_find(DviHashTable *hash, DviHashKey key)
78 {
79 Ulong hval;
80 DviHashBucket *buck;
81
82 hval = (hash->hash_func(key) % hash->nbucks);
83
84 for(buck = hash->buckets[hval]; buck; buck = buck->next)
85 if(hash->hash_comp(buck->key, key) == 0)
86 break;
87 return buck;
88 }
89
90 /* Neither keys nor data are duplicated */
mdvi_hash_add(DviHashTable * hash,DviHashKey key,void * data,int rep)91 int mdvi_hash_add(DviHashTable *hash, DviHashKey key, void *data, int rep)
92 {
93 DviHashBucket *buck = NULL;
94 Ulong hval;
95
96 if(rep != MDVI_HASH_UNCHECKED) {
97 buck = hash_find(hash, key);
98 if(buck != NULL) {
99 if(buck->data == data)
100 return 0;
101 if(rep == MDVI_HASH_UNIQUE)
102 return -1;
103 if(hash->hash_free != NULL)
104 hash->hash_free(buck->key, buck->data);
105 }
106 }
107 if(buck == NULL) {
108 buck = xalloc(DviHashBucket);
109 buck->hvalue = hash->hash_func(key);
110 hval = (buck->hvalue % hash->nbucks);
111 buck->next = hash->buckets[hval];
112 hash->buckets[hval] = buck;
113 hash->nkeys++;
114 }
115
116 /* save key and data */
117 buck->key = key;
118 buck->data = data;
119
120 return 0;
121 }
122
mdvi_hash_lookup(DviHashTable * hash,DviHashKey key)123 void *mdvi_hash_lookup(DviHashTable *hash, DviHashKey key)
124 {
125 DviHashBucket *buck = hash_find(hash, key);
126
127 return buck ? buck->data : NULL;
128 }
129
hash_remove(DviHashTable * hash,DviHashKey key)130 static DviHashBucket *hash_remove(DviHashTable *hash, DviHashKey key)
131 {
132 DviHashBucket *buck, *last;
133 Ulong hval;
134
135 hval = hash->hash_func(key);
136 hval %= hash->nbucks;
137
138 for(last = NULL, buck = hash->buckets[hval]; buck; buck = buck->next) {
139 if(hash->hash_comp(buck->key, key) == 0)
140 break;
141 last = buck;
142 }
143 if(buck == NULL)
144 return NULL;
145 if(last)
146 last->next = buck->next;
147 else
148 hash->buckets[hval] = buck->next;
149 hash->nkeys--;
150 return buck;
151 }
152
mdvi_hash_remove(DviHashTable * hash,DviHashKey key)153 void *mdvi_hash_remove(DviHashTable *hash, DviHashKey key)
154 {
155 DviHashBucket *buck = hash_remove(hash, key);
156 void *data = NULL;
157
158 if(buck) {
159 data = buck->data;
160 mdvi_free(buck);
161 }
162 return data;
163 }
164
mdvi_hash_remove_ptr(DviHashTable * hash,DviHashKey key)165 void *mdvi_hash_remove_ptr(DviHashTable *hash, DviHashKey key)
166 {
167 DviHashBucket *buck, *last;
168 Ulong hval;
169 void *ptr;
170
171 hval = hash->hash_func(key);
172 hval %= hash->nbucks;
173
174 for(last = NULL, buck = hash->buckets[hval]; buck; buck = buck->next) {
175 if(buck->key == key)
176 break;
177 last = buck;
178 }
179 if(buck == NULL)
180 return NULL;
181 if(last)
182 last->next = buck->next;
183 else
184 hash->buckets[hval] = buck->next;
185 hash->nkeys--;
186 /* destroy the bucket */
187 ptr = buck->data;
188 mdvi_free(buck);
189 return ptr;
190 }
191
mdvi_hash_destroy_key(DviHashTable * hash,DviHashKey key)192 int mdvi_hash_destroy_key(DviHashTable *hash, DviHashKey key)
193 {
194 DviHashBucket *buck = hash_remove(hash, key);
195
196 if(buck == NULL)
197 return -1;
198 if(hash->hash_free)
199 hash->hash_free(buck->key, buck->data);
200 mdvi_free(buck);
201 return 0;
202 }
203
mdvi_hash_reset(DviHashTable * hash,int reuse)204 void mdvi_hash_reset(DviHashTable *hash, int reuse)
205 {
206 int i;
207 DviHashBucket *buck;
208
209 /* remove all keys in the hash table */
210 for(i = 0; i < hash->nbucks; i++) {
211 for(; (buck = hash->buckets[i]); ) {
212 hash->buckets[i] = buck->next;
213 if(hash->hash_free)
214 hash->hash_free(buck->key, buck->data);
215 mdvi_free(buck);
216 }
217 }
218 hash->nkeys = 0;
219 if(!reuse && hash->buckets) {
220 mdvi_free(hash->buckets);
221 hash->buckets = NULL;
222 hash->nbucks = 0;
223 } /* otherwise, it is left empty, ready to be reused */
224 }
225