Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4680 | right-hear | 1 | #include "fitz.h" |
2 | |||
3 | /* |
||
4 | Simple hashtable with open adressing linear probe. |
||
5 | Unlike text book examples, removing entries works |
||
6 | correctly in this implementation, so it wont start |
||
7 | exhibiting bad behaviour if entries are inserted |
||
8 | and removed frequently. |
||
9 | */ |
||
10 | |||
11 | enum { MAX_KEY_LEN = 48 }; |
||
12 | typedef struct fz_hash_entry_s fz_hash_entry; |
||
13 | |||
14 | struct fz_hash_entry_s |
||
15 | { |
||
16 | unsigned char key[MAX_KEY_LEN]; |
||
17 | void *val; |
||
18 | }; |
||
19 | |||
20 | struct fz_hash_table_s |
||
21 | { |
||
22 | int keylen; |
||
23 | int size; |
||
24 | int load; |
||
25 | fz_hash_entry *ents; |
||
26 | }; |
||
27 | |||
28 | static unsigned hash(unsigned char *s, int len) |
||
29 | { |
||
30 | unsigned val = 0; |
||
31 | int i; |
||
32 | for (i = 0; i < len; i++) |
||
33 | { |
||
34 | val += s[i]; |
||
35 | val += (val << 10); |
||
36 | val ^= (val >> 6); |
||
37 | } |
||
38 | val += (val << 3); |
||
39 | val ^= (val >> 11); |
||
40 | val += (val << 15); |
||
41 | return val; |
||
42 | } |
||
43 | |||
44 | fz_hash_table * |
||
45 | fz_new_hash_table(int initialsize, int keylen) |
||
46 | { |
||
47 | fz_hash_table *table; |
||
48 | |||
49 | assert(keylen <= MAX_KEY_LEN); |
||
50 | |||
51 | table = fz_malloc(sizeof(fz_hash_table)); |
||
52 | table->keylen = keylen; |
||
53 | table->size = initialsize; |
||
54 | table->load = 0; |
||
55 | table->ents = fz_calloc(table->size, sizeof(fz_hash_entry)); |
||
56 | memset(table->ents, 0, sizeof(fz_hash_entry) * table->size); |
||
57 | |||
58 | return table; |
||
59 | } |
||
60 | |||
61 | void |
||
62 | fz_empty_hash(fz_hash_table *table) |
||
63 | { |
||
64 | table->load = 0; |
||
65 | memset(table->ents, 0, sizeof(fz_hash_entry) * table->size); |
||
66 | } |
||
67 | |||
68 | int |
||
69 | fz_hash_len(fz_hash_table *table) |
||
70 | { |
||
71 | return table->size; |
||
72 | } |
||
73 | |||
74 | void * |
||
75 | fz_hash_get_key(fz_hash_table *table, int idx) |
||
76 | { |
||
77 | return table->ents[idx].key; |
||
78 | } |
||
79 | |||
80 | void * |
||
81 | fz_hash_get_val(fz_hash_table *table, int idx) |
||
82 | { |
||
83 | return table->ents[idx].val; |
||
84 | } |
||
85 | |||
86 | void |
||
87 | fz_free_hash(fz_hash_table *table) |
||
88 | { |
||
89 | fz_free(table->ents); |
||
90 | fz_free(table); |
||
91 | } |
||
92 | |||
93 | static void |
||
94 | fz_resize_hash(fz_hash_table *table, int newsize) |
||
95 | { |
||
96 | fz_hash_entry *oldents = table->ents; |
||
97 | int oldsize = table->size; |
||
98 | int oldload = table->load; |
||
99 | int i; |
||
100 | |||
101 | if (newsize < oldload * 8 / 10) |
||
102 | { |
||
103 | fz_throw("assert: resize hash too small"); |
||
104 | return; |
||
105 | } |
||
106 | |||
107 | table->ents = fz_calloc(newsize, sizeof(fz_hash_entry)); |
||
108 | memset(table->ents, 0, sizeof(fz_hash_entry) * newsize); |
||
109 | table->size = newsize; |
||
110 | table->load = 0; |
||
111 | |||
112 | for (i = 0; i < oldsize; i++) |
||
113 | { |
||
114 | if (oldents[i].val) |
||
115 | { |
||
116 | fz_hash_insert(table, oldents[i].key, oldents[i].val); |
||
117 | } |
||
118 | } |
||
119 | |||
120 | fz_free(oldents); |
||
121 | } |
||
122 | |||
123 | void * |
||
124 | fz_hash_find(fz_hash_table *table, void *key) |
||
125 | { |
||
126 | fz_hash_entry *ents = table->ents; |
||
127 | unsigned size = table->size; |
||
128 | unsigned pos = hash(key, table->keylen) % size; |
||
129 | |||
130 | while (1) |
||
131 | { |
||
132 | if (!ents[pos].val) |
||
133 | return NULL; |
||
134 | |||
135 | if (memcmp(key, ents[pos].key, table->keylen) == 0) |
||
136 | return ents[pos].val; |
||
137 | |||
138 | pos = (pos + 1) % size; |
||
139 | } |
||
140 | } |
||
141 | |||
142 | void |
||
143 | fz_hash_insert(fz_hash_table *table, void *key, void *val) |
||
144 | { |
||
145 | fz_hash_entry *ents; |
||
146 | unsigned size; |
||
147 | unsigned pos; |
||
148 | |||
149 | if (table->load > table->size * 8 / 10) |
||
150 | { |
||
151 | fz_resize_hash(table, table->size * 2); |
||
152 | } |
||
153 | |||
154 | ents = table->ents; |
||
155 | size = table->size; |
||
156 | pos = hash(key, table->keylen) % size; |
||
157 | |||
158 | while (1) |
||
159 | { |
||
160 | if (!ents[pos].val) |
||
161 | { |
||
162 | memcpy(ents[pos].key, key, table->keylen); |
||
163 | ents[pos].val = val; |
||
164 | table->load ++; |
||
165 | return; |
||
166 | } |
||
167 | |||
168 | if (memcmp(key, ents[pos].key, table->keylen) == 0) |
||
169 | fz_warn("assert: overwrite hash slot"); |
||
170 | |||
171 | pos = (pos + 1) % size; |
||
172 | } |
||
173 | } |
||
174 | |||
175 | void |
||
176 | fz_hash_remove(fz_hash_table *table, void *key) |
||
177 | { |
||
178 | fz_hash_entry *ents = table->ents; |
||
179 | unsigned size = table->size; |
||
180 | unsigned pos = hash(key, table->keylen) % size; |
||
181 | unsigned hole, look, code; |
||
182 | |||
183 | while (1) |
||
184 | { |
||
185 | if (!ents[pos].val) |
||
186 | { |
||
187 | fz_warn("assert: remove inexistant hash entry"); |
||
188 | return; |
||
189 | } |
||
190 | |||
191 | if (memcmp(key, ents[pos].key, table->keylen) == 0) |
||
192 | { |
||
193 | ents[pos].val = NULL; |
||
194 | |||
195 | hole = pos; |
||
196 | look = (hole + 1) % size; |
||
197 | |||
198 | while (ents[look].val) |
||
199 | { |
||
200 | code = hash(ents[look].key, table->keylen) % size; |
||
201 | if ((code <= hole && hole < look) || |
||
202 | (look < code && code <= hole) || |
||
203 | (hole < look && look < code)) |
||
204 | { |
||
205 | ents[hole] = ents[look]; |
||
206 | ents[look].val = NULL; |
||
207 | hole = look; |
||
208 | } |
||
209 | |||
210 | look = (look + 1) % size; |
||
211 | } |
||
212 | |||
213 | table->load --; |
||
214 | |||
215 | return; |
||
216 | } |
||
217 | |||
218 | pos = (pos + 1) % size; |
||
219 | } |
||
220 | } |
||
221 | |||
222 | void |
||
223 | fz_debug_hash(fz_hash_table *table) |
||
224 | { |
||
225 | int i, k; |
||
226 | |||
227 | printf("cache load %d / %d\n", table->load, table->size); |
||
228 | |||
229 | for (i = 0; i < table->size; i++) |
||
230 | { |
||
231 | if (!table->ents[i].val) |
||
232 | printf("table % 4d: empty\n", i); |
||
233 | else |
||
234 | { |
||
235 | printf("table % 4d: key=", i); |
||
236 | for (k = 0; k < MAX_KEY_LEN; k++) |
||
237 | printf("%02x", ((char*)table->ents[i].key)[k]); |
||
238 | printf(" val=$%p\n", table->ents[i].val); |
||
239 | } |
||
240 | } |
||
241 | }>>>>=>>>=>>>=>><>><>><>> |