Branch data Line data Source code
1 : : /* -*- mode: C -*-
2 : : *
3 : : * File: pdf-hash.c
4 : : * Date: Sat Apr 12 12:22:05 2008
5 : : *
6 : : * GNU PDF Library - Implementation file for the Hash module
7 : : *
8 : : */
9 : :
10 : : /* Copyright (C) 2008-2011 Free Software Foundation, Inc. */
11 : :
12 : : /* This program is free software: you can redistribute it and/or modify
13 : : * it under the terms of the GNU General Public License as published by
14 : : * the Free Software Foundation, either version 3 of the License, or
15 : : * (at your option) any later version.
16 : : *
17 : : * This program is distributed in the hope that it will be useful,
18 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 : : * GNU General Public License for more details.
21 : : *
22 : : * You should have received a copy of the GNU General Public License
23 : : * along with this program. If not, see <http://www.gnu.org/licenses/>.
24 : : */
25 : :
26 : : #include <config.h>
27 : :
28 : : #include <limits.h>
29 : : #include <stdio.h>
30 : : #include <stdlib.h>
31 : : #include <string.h>
32 : :
33 : : #include <pdf-global.h>
34 : : #include <pdf-error.h>
35 : : #include <pdf-alloc.h>
36 : : #include <gl_rbtreehash_list.h>
37 : :
38 : : #include <pdf-hash.h>
39 : :
40 : : #define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
41 : :
42 : : struct pdf_hash_element_s
43 : : {
44 : : const pdf_char_t *key;
45 : : const void *value;
46 : : pdf_hash_value_dispose_fn_t value_disp_fn;
47 : : };
48 : :
49 : : typedef struct pdf_hash_element_s pdf_hash_element_t;
50 : :
51 : : /* Returns <0,=0,>0 if key1 is <,==, or > than key2 */
52 : : static int hash_element_compare (const pdf_hash_element_t *elt1,
53 : : const pdf_hash_element_t *elt2);
54 : :
55 : : /* Returns true if both keys in the elements are equal */
56 : : static pdf_bool_t hash_element_equal (const pdf_hash_element_t *elt1,
57 : : const pdf_hash_element_t *elt2);
58 : :
59 : : /* Compute a hash code for a NUL-terminated string starting at X,
60 : : * and return the hash code.
61 : : * The result is platform dependent: it depends on the size of the 'size_t'
62 : : * type and on the signedness of the 'char' type. */
63 : : static pdf_size_t hash_element_pjw (const pdf_hash_element_t *elt);
64 : :
65 : : /* Dispose a hash element */
66 : : static void hash_element_dispose (pdf_hash_element_t *elt);
67 : :
68 : : /* Find a hash element by key in the hash table */
69 : : static pdf_hash_element_t *hash_search_key (const pdf_hash_t *table,
70 : : const pdf_char_t *key,
71 : : gl_list_node_t *p_node);
72 : :
73 : : pdf_hash_t *
74 : 809 : pdf_hash_new (pdf_error_t **error)
75 : : {
76 : : gl_list_t list;
77 : :
78 : 1618 : list = gl_list_nx_create_empty (GL_RBTREEHASH_LIST,
79 : : (gl_listelement_equals_fn) hash_element_equal,
80 : : (gl_listelement_hashcode_fn) hash_element_pjw,
81 : : (gl_listelement_dispose_fn) hash_element_dispose,
82 : : PDF_FALSE);
83 [ - + ]: 809 : if (list == NULL)
84 : 0 : pdf_set_error (error,
85 : : PDF_EDOMAIN_BASE_HASH,
86 : : PDF_ENOMEM,
87 : : "not enough memory: couldn't create new hash table");
88 : :
89 : 809 : return (pdf_hash_t *)list;
90 : : }
91 : :
92 : : void
93 : 809 : pdf_hash_destroy (pdf_hash_t *table)
94 : : {
95 [ + - ]: 809 : if (table != NULL)
96 : 809 : gl_list_free ((gl_list_t) table);
97 : 809 : }
98 : :
99 : : pdf_size_t
100 : 746 : pdf_hash_size (const pdf_hash_t *table)
101 : : {
102 [ + - ]: 1492 : return (table != NULL ?
103 : 746 : gl_list_size ((gl_list_t) table) :
104 : : 0);;
105 : : }
106 : :
107 : : pdf_bool_t
108 : 829 : pdf_hash_key_p (const pdf_hash_t *table,
109 : : const pdf_char_t *key)
110 : : {
111 [ - + ]: 829 : PDF_ASSERT_POINTER_RETURN_VAL (table, PDF_FALSE);
112 [ - + ]: 829 : PDF_ASSERT_POINTER_RETURN_VAL (key, PDF_FALSE);
113 : :
114 : 829 : return (hash_search_key (table, key, NULL) != NULL ?
115 : : PDF_TRUE : PDF_FALSE);
116 : : }
117 : :
118 : : pdf_bool_t
119 : 2 : pdf_hash_rename_key (pdf_hash_t *table,
120 : : const pdf_char_t *key,
121 : : const pdf_char_t *new_key,
122 : : pdf_error_t **error)
123 : : {
124 : : pdf_hash_element_t *elt;
125 : 2 : gl_list_node_t node = NULL;
126 : 2 : pdf_error_t *inner_error = NULL;
127 : :
128 [ - + ]: 2 : PDF_ASSERT_POINTER_RETURN_VAL (table, PDF_FALSE);
129 [ - + ]: 2 : PDF_ASSERT_POINTER_RETURN_VAL (key, PDF_FALSE);
130 [ - + ]: 2 : PDF_ASSERT_POINTER_RETURN_VAL (new_key, PDF_FALSE);
131 : :
132 : 2 : elt = hash_search_key (table, key, &node);
133 : :
134 : : /* If element not found, return */
135 [ + + ]: 2 : if (elt == NULL)
136 : 1 : return PDF_FALSE;
137 : :
138 : : /* Add the same element with the new key */
139 [ - + ]: 1 : if (!pdf_hash_add (table,
140 : : new_key,
141 : : elt->value,
142 : : elt->value_disp_fn,
143 : : &inner_error))
144 : : {
145 : 0 : pdf_propagate_error (error, inner_error);
146 : 0 : return PDF_FALSE;
147 : : }
148 : :
149 : : /* Remove the element with the old key */
150 : 1 : gl_list_remove_node ((gl_list_t) table, node);
151 : :
152 : 2 : return PDF_TRUE;
153 : : }
154 : :
155 : : static pdf_bool_t
156 : 852 : hash_add (pdf_hash_t *table,
157 : : const pdf_char_t *key,
158 : : const void *value,
159 : : pdf_hash_value_dispose_fn_t value_disp_fn,
160 : : pdf_bool_t allow_replace,
161 : : pdf_error_t **error)
162 : : {
163 : 852 : gl_list_node_t node = NULL;
164 : : pdf_hash_element_t *elt;
165 : : pdf_char_t *key_dup;
166 : :
167 : : /* Look for an element with same key */
168 [ + + ]: 852 : if (hash_search_key (table, key, &node))
169 : : {
170 : : /* Key already exists. */
171 [ + + ]: 2 : if (!allow_replace)
172 : : {
173 : 1 : pdf_set_error (error,
174 : : PDF_EDOMAIN_BASE_HASH,
175 : : PDF_EEXIST,
176 : : "key '%s' already exits, cannot add it again",
177 : : key);
178 : 1 : return PDF_FALSE;
179 : : }
180 : :
181 : : /* Remove the previous element */
182 : 1 : gl_list_remove_node ((gl_list_t) table, node);
183 : : }
184 : :
185 : : /* New hash table element */
186 : 851 : elt = pdf_alloc (sizeof (*elt));
187 : 851 : key_dup = strdup (key);
188 [ - + ]: 851 : if (elt == NULL || key_dup == NULL)
189 : : {
190 : 0 : pdf_set_error (error,
191 : : PDF_EDOMAIN_BASE_HASH,
192 : : PDF_ENOMEM,
193 : : "not enough memory: couldn't add new hash table item");
194 [ # # ]: 0 : if (elt)
195 : 0 : pdf_dealloc (elt);
196 [ # # ]: 0 : if (key_dup)
197 : 0 : pdf_dealloc (key_dup);
198 : 0 : return PDF_FALSE;
199 : : }
200 : :
201 : : /* Set new element contents */
202 : 851 : elt->key = key_dup;
203 : 851 : elt->value = value;
204 : 851 : elt->value_disp_fn = value_disp_fn;
205 : :
206 : : /* Add to the list */
207 [ - + ]: 851 : if (!gl_sortedlist_nx_add ((gl_list_t) table,
208 : : (gl_listelement_compar_fn) hash_element_compare,
209 : : elt))
210 : : {
211 : 0 : pdf_set_error (error,
212 : : PDF_EDOMAIN_BASE_HASH,
213 : : PDF_ENOMEM,
214 : : "not enough memory: "
215 : : "couldn't add new element to the hash table");
216 : 0 : hash_element_dispose (elt);
217 : 0 : return PDF_FALSE;
218 : : }
219 : :
220 : 852 : return PDF_TRUE;
221 : : }
222 : :
223 : : pdf_bool_t
224 : 848 : pdf_hash_add (pdf_hash_t *table,
225 : : const pdf_char_t *key,
226 : : const void *value,
227 : : pdf_hash_value_dispose_fn_t value_disp_fn,
228 : : pdf_error_t **error)
229 : : {
230 [ - + ]: 848 : PDF_ASSERT_POINTER_RETURN_VAL (table, PDF_FALSE);
231 [ - + ]: 848 : PDF_ASSERT_POINTER_RETURN_VAL (key, PDF_FALSE);
232 : :
233 : 848 : return hash_add (table, key, value, value_disp_fn, PDF_FALSE, error);
234 : : }
235 : :
236 : : pdf_bool_t
237 : 4 : pdf_hash_replace (pdf_hash_t *table,
238 : : const pdf_char_t *key,
239 : : const void *value,
240 : : pdf_hash_value_dispose_fn_t value_disp_fn,
241 : : pdf_error_t **error)
242 : : {
243 [ - + ]: 4 : PDF_ASSERT_POINTER_RETURN_VAL (table, PDF_FALSE);
244 [ - + ]: 4 : PDF_ASSERT_POINTER_RETURN_VAL (key, PDF_FALSE);
245 : :
246 : 4 : return hash_add (table, key, value, value_disp_fn, PDF_TRUE, error);
247 : : }
248 : :
249 : : pdf_bool_t
250 : 747 : pdf_hash_remove (pdf_hash_t *table,
251 : : const pdf_char_t *key)
252 : : {
253 : 747 : gl_list_node_t node = NULL;
254 : :
255 [ - + ]: 747 : PDF_ASSERT_POINTER_RETURN_VAL (table, PDF_FALSE);
256 [ - + ]: 747 : PDF_ASSERT_POINTER_RETURN_VAL (key, PDF_FALSE);
257 : :
258 [ + + ]: 747 : if (hash_search_key (table, key, &node))
259 : : {
260 : : /* Remove the element */
261 : 746 : gl_list_remove_node ((gl_list_t) table, node);
262 : 746 : return PDF_TRUE;
263 : : }
264 : :
265 : : /* Not found */
266 : 747 : return PDF_FALSE;
267 : : }
268 : :
269 : : const void *
270 : 177 : pdf_hash_get_value (const pdf_hash_t *table,
271 : : const pdf_char_t *key)
272 : : {
273 : : pdf_hash_element_t *elt;
274 : :
275 [ - + ]: 177 : PDF_ASSERT_POINTER_RETURN_VAL (table, NULL);
276 [ - + ]: 177 : PDF_ASSERT_POINTER_RETURN_VAL (key, NULL);
277 : :
278 : 177 : elt = hash_search_key (table, key, NULL);
279 : :
280 [ + + ]: 177 : return (elt != NULL ? elt->value : NULL);
281 : : }
282 : :
283 : : void
284 : 2 : pdf_hash_iterator_init (pdf_hash_iterator_t *itr,
285 : : const pdf_hash_t *table)
286 : : {
287 [ - + ]: 2 : PDF_ASSERT_POINTER_RETURN (itr);
288 [ - + ]: 2 : PDF_ASSERT_POINTER_RETURN (table);
289 : :
290 : 2 : *((gl_list_iterator_t *)itr) = gl_list_iterator ((gl_list_t) table);
291 : : }
292 : :
293 : : pdf_bool_t
294 : 2 : pdf_hash_iterator_next (pdf_hash_iterator_t *itr,
295 : : const pdf_char_t **key,
296 : : const void **value)
297 : : {
298 : : const pdf_hash_element_t *element;
299 : : gl_list_node_t node;
300 : :
301 [ - + ]: 2 : PDF_ASSERT_POINTER_RETURN_VAL (itr, PDF_FALSE);
302 : :
303 [ + + ]: 2 : if (!gl_list_iterator_next (((gl_list_iterator_t *) itr),
304 : : (const void **)&element,
305 : : &node))
306 : : {
307 [ + - ]: 1 : if (key)
308 : 1 : *key = NULL;
309 [ + - ]: 1 : if (value)
310 : 1 : *value = NULL;
311 : 1 : return PDF_FALSE;
312 : : }
313 : :
314 [ + - ]: 1 : if (key)
315 : 1 : *key = element->key;
316 [ + - ]: 1 : if (value)
317 : 1 : *value = element->value;
318 : 2 : return PDF_TRUE;
319 : : }
320 : :
321 : : void
322 : 2 : pdf_hash_iterator_deinit (pdf_hash_iterator_t *itr)
323 : : {
324 [ + - ]: 2 : if (itr)
325 : 2 : gl_list_iterator_free ((gl_list_iterator_t *) itr);
326 : 2 : }
327 : :
328 : : static pdf_hash_element_t *
329 : 2607 : hash_search_key (const pdf_hash_t *table,
330 : : const pdf_char_t *key,
331 : : gl_list_node_t *p_node)
332 : : {
333 : : gl_list_node_t node;
334 : : pdf_hash_element_t aux;
335 : :
336 : : /* Setup aux element in stack to use during search comparisons */
337 : 2607 : aux.key = key;
338 : 5214 : node = gl_sortedlist_search ((gl_list_t) table,
339 : : (gl_listelement_compar_fn) hash_element_compare,
340 : : (const void *) &aux);
341 [ + + ]: 2607 : if (p_node)
342 : 1601 : *p_node = node;
343 : :
344 [ + + ]: 3614 : return (pdf_hash_element_t *) (node != NULL ?
345 : 1007 : gl_list_node_value ((gl_list_t) table, node) :
346 : : NULL);
347 : : }
348 : :
349 : : static pdf_size_t
350 : 851 : hash_element_pjw (const pdf_hash_element_t *elt)
351 : : {
352 : : const pdf_char_t *s;
353 : 851 : pdf_size_t h = 0;
354 : :
355 [ + + ]: 4329 : for (s = elt->key; *s; s++)
356 : 3478 : h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
357 : :
358 : 851 : return h;
359 : : }
360 : :
361 : : static void
362 : 851 : hash_element_dispose (pdf_hash_element_t *elt)
363 : : {
364 [ + - ]: 851 : if (elt)
365 : : {
366 [ + - ]: 851 : if (elt->key)
367 : 851 : pdf_dealloc (elt->key);
368 [ + + ]: 851 : if (elt->value_disp_fn)
369 : 750 : elt->value_disp_fn (elt->value);
370 : 851 : pdf_dealloc (elt);
371 : : }
372 : 851 : }
373 : :
374 : : static int
375 : 1170 : hash_element_compare (const pdf_hash_element_t *elt1,
376 : : const pdf_hash_element_t *elt2)
377 : : {
378 : 1170 : return strcmp (elt1->key, elt2->key);
379 : : }
380 : :
381 : : static pdf_bool_t
382 : 0 : hash_element_equal (const pdf_hash_element_t *elt1,
383 : : const pdf_hash_element_t *elt2)
384 : : {
385 : 0 : return (hash_element_compare (elt1, elt2) == 0 ?
386 : : PDF_TRUE : PDF_FALSE);
387 : : }
388 : :
389 : : /* End of pdf-hash.c */
|
