1 /*
2 Copyright (C) 2003 Cedric Cellier, Dominique Lavault
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 */
18 #include "hash.h"
19 #include "stack.h"
20 #include "memspool.h"
21 #include "log.h"
22 #include <assert.h>
23 #include <stdio.h>
24 #include <string.h>
25
26 typedef struct {
27 unsigned key;
28 void* value;
29 unsigned next; /* 0 if last, 1 if vaccant */
30 } entry;
31
32 typedef struct {
33 unsigned first; /* first and next are indices cause realloc may relocate the entries */
34 } hash_line;
35
36 struct s_gltv_hash {
37 entry* entries;
38 unsigned nb_used_entries;
39 unsigned nb_lines;
40 unsigned nb_usable_entries;
41 unsigned next_free_entry; /* index of the next free entry in entries */
42 unsigned full_until; /* index of the first entry which usage might be vaccant */
43 char flag;
44 unsigned read_next;
45 gltv_stack *removed; /* indexes of thet lasts removed entries */
46 hash_line lines[0]; /* GCC specific */
47 };
48
49 typedef struct s_gltv_hash hash;
50
gltv_hash_new(unsigned total,unsigned per_line,int flag)51 GLTV_HASH gltv_hash_new(unsigned total, unsigned per_line, int flag) {
52 unsigned nb_lines, i;
53 entry *entries;
54 hash *this_hash;
55 assert(total && per_line);
56 nb_lines = (3*(total/per_line))>>1;
57 this_hash = gltv_memspool_alloc(sizeof(hash)+nb_lines*sizeof(hash_line));
58 if (!this_hash) return 0;
59 entries = gltv_memspool_alloc(total*sizeof(entry));
60 if (!entries) {
61 gltv_memspool_unregister(this_hash);
62 return 0;
63 }
64 if (!(this_hash->removed = gltv_stack_new(1+(total>>3), flag&GLTV_HASH_OPT_SPEED)) ) {
65 gltv_memspool_unregister(entries);
66 gltv_memspool_unregister(this_hash);
67 return 0;
68 }
69 this_hash->nb_lines = nb_lines;
70 this_hash->entries = entries;
71 this_hash->nb_usable_entries = total;
72 /* the 0th entry is unusable in practice because when next=0 it means : last entry.
73 * the 1st entry is unusable also because we tag vaccant entries with next=1 */
74 this_hash->nb_used_entries = 2;
75 this_hash->next_free_entry = 2;
76 this_hash->full_until = 2;
77 this_hash->flag = flag;
78 for (i=0; i<nb_lines; i++) {
79 this_hash->lines[i].first = 0;
80 }
81 return (GLTV_HASH)this_hash;
82 }
83
gltv_hash_del(GLTV_HASH h)84 void gltv_hash_del(GLTV_HASH h) {
85 gltv_memspool_unregister(h->entries);
86 gltv_stack_del(h->removed);
87 gltv_memspool_unregister(h);
88 }
89
hash_func(GLTV_HASH hash,unsigned key)90 static unsigned hash_func(GLTV_HASH hash, unsigned key) {
91 unsigned index = 0;
92 unsigned c;
93 if (hash->flag & GLTV_HASH_STRKEYS) {
94 char *str = (char*)key;
95 c = 0;
96 while (str[c]!='\0') { /* we could limit c to, say, 10 chars, but if the string is a full pathname, it wont be smart. in the opposite direction, same problem */
97 index += 31 + str[c++];
98 }
99 } else {
100 unsigned k = key;
101 for (c=0; c<4; c++) {
102 index += 31 + (k&0xFF);
103 k >>= 8;
104 }
105 }
106 index %= hash->nb_lines;
107 return index;
108 }
109
keysMatch(GLTV_HASH hash,unsigned k1,unsigned k2)110 int keysMatch(GLTV_HASH hash, unsigned k1, unsigned k2) {
111 if (hash->flag & GLTV_HASH_STRKEYS)
112 return 0==strcmp((char*)k1, (char*)k2);
113 else
114 return k1==k2;
115 }
116
resize(hash * h,unsigned nb_entries)117 static void resize(hash *h, unsigned nb_entries) {
118 /* resizing if for entries, not lines */
119 entry *ptr;
120 assert(h->next_free_entry<=nb_entries);
121 ptr = (entry*) gltv_memspool_realloc(h->entries, nb_entries*sizeof(entry));
122 if (!ptr) gltv_log_fatal("hash:resize : can't resize");
123 h->entries = ptr;
124 h->nb_usable_entries = nb_entries;
125 }
126
gltv_hash_put(GLTV_HASH h,unsigned key,void * value)127 void gltv_hash_put(GLTV_HASH h, unsigned key, void *value) {
128 unsigned line = hash_func(h, key);
129 unsigned *eptr_location, eptr, old_next;
130 start:
131 eptr_location = &h->lines[line].first;
132 while ( (eptr = *eptr_location) !=0) {
133 assert(eptr!=1);
134 if (keysMatch(h, h->entries[eptr].key, key)) { /* update */
135 h->entries[eptr].value = value;
136 h->entries[eptr].key = key;
137 return;
138 }
139 eptr_location = &h->entries[eptr].next;
140 }
141 /* insert */
142 if (h->next_free_entry < h->nb_usable_entries) {
143 /* some space left at the end */
144 eptr = h->next_free_entry;
145 if (h->full_until == h->next_free_entry) h->full_until ++;
146 h->next_free_entry ++;
147 } else {
148 /* no easy space */
149 /* try to use the stack of removed entries to store vacant locations. */
150 if (gltv_stack_size(h->removed)) {
151 eptr = (unsigned) gltv_stack_pop(h->removed);
152 assert(h->entries[eptr].next==1);
153 } else {
154 /* otherwise parse everything to find vacant entries
155 * (this assumes that we MARK removed entries) */
156 if (h->nb_used_entries == h->nb_usable_entries) {
157 /* no need for parsing, resize the hash */
158 resize(h, (h->nb_usable_entries*3)>>1);
159 /* some new space left at the end
160 * but eptr_location, beeing a pointer, must be discarded
161 * so let's start over */
162 goto start;
163 } else {
164 assert((h->flag&GLTV_HASH_OPT_SPEED) == 0);
165 /* we have a hint from where to parse */
166 for (eptr=h->full_until; eptr<h->nb_usable_entries; eptr++)
167 if (1 == (int)h->entries[eptr].next) {
168 h->full_until = eptr;
169 break;
170 }
171 assert(eptr<h->nb_usable_entries);
172 }
173 }
174 }
175 /* common ending for the insert cases */
176 old_next = *eptr_location;
177 *eptr_location = eptr;
178 h->entries[eptr].next = old_next;
179 h->entries[eptr].key = key;
180 h->entries[eptr].value = value;
181 h->nb_used_entries++;
182 }
183
gltv_hash_get(GLTV_HASH h,unsigned key,void ** value)184 char gltv_hash_get(GLTV_HASH h, unsigned key, void **value) {
185 unsigned line = hash_func(h, key);
186 unsigned eptr = h->lines[line].first;
187 while ( eptr != 0) {
188 if (keysMatch(h, h->entries[eptr].key, key)) {
189 *value = h->entries[eptr].value;
190 return 1;
191 }
192 eptr = h->entries[eptr].next;
193 }
194 /* asking for an inexistent key */
195 return 0;
196 }
197
gltv_hash_remove(GLTV_HASH h,unsigned key)198 char gltv_hash_remove(GLTV_HASH h, unsigned key) {
199 unsigned line = hash_func(h, key);
200 unsigned eptr = h->lines[line].first;
201 unsigned old_eptr = 0;
202 while ( eptr != 0) {
203 if (keysMatch(h, h->entries[eptr].key, key)) {
204 gltv_stack_push(h->removed, (void*)eptr);
205 if (0 != old_eptr)
206 h->entries[old_eptr].next = h->entries[eptr].next;
207 else
208 h->lines[line].first = h->entries[eptr].next;
209 if (eptr < h->full_until)
210 h->full_until = eptr;
211 h->entries[eptr].next=1; /* tag as vaccant */
212 h->nb_used_entries--;
213 return 1;
214 }
215 old_eptr = eptr;
216 eptr = h->entries[eptr].next;
217 }
218 return 0;
219 }
220
gltv_hash_size(GLTV_HASH h)221 unsigned gltv_hash_size(GLTV_HASH h) {
222 return h->nb_used_entries -2;
223 }
224
gltv_hash_reset(GLTV_HASH h)225 void gltv_hash_reset(GLTV_HASH h) {
226 h->read_next = 2;
227 }
228
gltv_hash_each(GLTV_HASH h,unsigned * key,void ** value)229 char gltv_hash_each(GLTV_HASH h, unsigned *key, void **value) {
230 unsigned i;
231 for (i=h->read_next; i<h->next_free_entry; i++) {
232 if (1 != h->entries[i].next) {
233 *key = h->entries[i].key;
234 *value = h->entries[i].value;
235 h->read_next = i+1;
236 return 1;
237 }
238 }
239 return 0;
240 }
241
gltv_hash_compact(GLTV_HASH h)242 void gltv_hash_compact(GLTV_HASH h) {
243 unsigned i, line;
244 for (i=h->full_until; i<h->next_free_entry; i++) {
245 if (h->entries[i].next==1) {
246 /* replace this entry with the last entry used */
247 unsigned ii, eptr;
248 unsigned *eptr_location;
249 for (ii=h->next_free_entry-1; ii>i; ii--)
250 if (h->entries[ii].next!=1) break;
251 if (ii==i) goto near_end;
252 line = hash_func(h, h->entries[ii].key);
253 eptr_location = &h->lines[line].first;
254 while ( (eptr=*eptr_location) != ii && eptr != 0) {
255 eptr_location = &h->entries[eptr].next;
256 eptr = *eptr_location;
257 }
258 assert(eptr==ii); /* So, we could simplify the while clause */
259 *eptr_location = i;
260 h->entries[i].key = h->entries[ii].key;
261 h->entries[i].value = h->entries[ii].value;
262 h->entries[i].next = h->entries[ii].next;
263 near_end:
264 h->next_free_entry = ii;
265 }
266 }
267 h->full_until = h->next_free_entry;
268 resize(h, h->nb_used_entries);
269 }
270
271