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 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_array_list.h>
37 : #include <gl_linkedhash_list.h>
38 :
39 : #include <pdf-hash.h>
40 :
41 : #define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
42 :
43 : /* Compute a hash code for a NUL-terminated string starting at X,
44 : and return the hash code.
45 : The result is platform dependent: it depends on the size of the 'size_t'
46 : type and on the signedness of the 'char' type. */
47 : static size_t hash_pjw (const void *x);
48 :
49 : /* Returns true if both element string keys are equal */
50 : static bool elem_key_equal (const void *elt1, const void *elt2);
51 :
52 : /* Returns true if both string keys are equal */
53 : static bool key_equal (const void *key1, const void *key2);
54 :
55 : /* Returns 1 if str is only composed by numbers, 0 otherwise. */
56 : static int key_numeric_p (const char *str);
57 :
58 : /* Returns <0,=0,>0 if key1 is <,==, or > than key2 */
59 : static int key_numeric_cmp (const char *key1, const char *key2);
60 :
61 : /* Returns <0,=0,>0 if key1 is <,==, or > than key2 */
62 : static int key_compare (const void *key1, const void *key2);
63 :
64 : pdf_status_t
65 : pdf_hash_new (pdf_hash_key_dispose_fn_t dispose_key_fn, pdf_hash_t *table)
66 886 : {
67 : pdf_status_t st;
68 :
69 886 : st = PDF_OK;
70 :
71 886 : if (table != NULL)
72 : {
73 885 : table->elements = gl_list_nx_create_empty (GL_LINKEDHASH_LIST,
74 : elem_key_equal, hash_pjw,
75 : NULL, 0);
76 :
77 885 : if (table->elements != NULL)
78 : {
79 885 : table->keys = gl_list_nx_create_empty (GL_ARRAY_LIST, key_equal, NULL,
80 : dispose_key_fn, 0);
81 :
82 885 : if (table->keys == NULL)
83 : {
84 0 : st = PDF_ENOMEM;
85 : }
86 : }
87 : else
88 : {
89 0 : st = PDF_ENOMEM;
90 : }
91 : }
92 : else
93 : {
94 1 : st = PDF_EBADDATA;
95 : }
96 :
97 886 : return st;
98 : }
99 :
100 :
101 : pdf_status_t
102 : pdf_hash_destroy (pdf_hash_t table)
103 82 : {
104 : gl_list_iterator_t itr;
105 : const void *elt;
106 :
107 82 : if (table.elements != NULL && table.keys != NULL)
108 : {
109 164 : itr = gl_list_iterator ((gl_list_t)table.elements);
110 204 : while (gl_list_iterator_next (&itr, &elt, NULL))
111 : {
112 40 : if (((pdf_hash_element_t*)elt)->disp_fn != NULL)
113 : {
114 5 : ((pdf_hash_element_t*)elt)->
115 : disp_fn ((void*) ((pdf_hash_element_t*)elt)->value);
116 : }
117 40 : pdf_dealloc((pdf_hash_element_t*)elt);
118 : }
119 : gl_list_iterator_free (&itr);
120 :
121 82 : gl_list_free((gl_list_t)table.elements);
122 82 : gl_list_free((gl_list_t)table.keys);
123 : }
124 :
125 82 : return PDF_OK;
126 : }
127 :
128 :
129 : pdf_size_t
130 : pdf_hash_size (const pdf_hash_t table)
131 1 : {
132 2 : return (gl_list_size ((gl_list_t) table.keys));
133 : }
134 :
135 :
136 : pdf_bool_t
137 : pdf_hash_key_p (const pdf_hash_t table, const char *key)
138 16 : {
139 32 : if (gl_sortedlist_search ((gl_list_t) table.keys, key_compare,
140 : (const void*) key) != NULL)
141 : {
142 12 : return PDF_TRUE;
143 : }
144 :
145 4 : return PDF_FALSE;
146 : }
147 :
148 :
149 : pdf_status_t
150 : pdf_hash_rename (pdf_hash_t table, const char *key, const char *new_key)
151 4 : {
152 : pdf_status_t st;
153 : gl_list_node_t knode, vnode, tnode;
154 : pdf_hash_element_t elem, *updated;
155 :
156 4 : st = PDF_OK;
157 :
158 4 : if (key != NULL && new_key != NULL)
159 : {
160 4 : knode = gl_sortedlist_search ((gl_list_t) table.keys, key_compare, key);
161 2 : if (knode != NULL)
162 : {
163 : /* get the node from key and update its key*/
164 1 : elem.key = key;
165 1 : vnode = gl_list_search ((gl_list_t)table.elements, &elem);
166 2 : updated = (pdf_hash_element_t*)
167 : gl_list_node_value ((gl_list_t)table.elements, vnode);
168 1 : updated->key = new_key;
169 :
170 : /* update the lists */
171 2 : tnode = gl_list_nx_add_first ((gl_list_t) table.elements, updated);
172 1 : if (tnode != NULL)
173 : {
174 1 : gl_list_remove_node ((gl_list_t)table.elements, vnode);
175 :
176 2 : if (gl_sortedlist_nx_add ((gl_list_t)table.keys, key_compare, new_key)
177 : != NULL)
178 : {
179 1 : gl_sortedlist_remove ((gl_list_t)table.keys, key_compare, key);
180 : }
181 : else
182 : {
183 0 : gl_list_remove_node ((gl_list_t) table.elements, tnode);
184 0 : st = PDF_ENOMEM;
185 : }
186 : }
187 : else
188 : {
189 0 : st = PDF_ENOMEM;
190 : }
191 : }
192 : else
193 : {
194 1 : st = PDF_ERROR;
195 : }
196 : }
197 : else
198 : {
199 2 : st = PDF_EBADDATA;
200 : }
201 :
202 4 : return st;
203 :
204 : }
205 :
206 :
207 : pdf_status_t
208 : pdf_hash_add (pdf_hash_t table, const char *key, const void *element,
209 : pdf_hash_element_dispose_fn_t disp_fn)
210 43 : {
211 : pdf_status_t st;
212 : pdf_hash_element_t *newelt;
213 : gl_list_node_t tnode;
214 43 : st = PDF_OK;
215 :
216 43 : if (key != NULL && element != NULL)
217 : {
218 41 : newelt = pdf_alloc (sizeof (pdf_hash_element_t));
219 41 : if (newelt != NULL)
220 : {
221 41 : newelt->key = key;
222 41 : newelt->value = element;
223 41 : newelt->disp_fn = disp_fn;
224 82 : tnode = gl_list_nx_add_first ((gl_list_t) table.elements, newelt);
225 41 : if (tnode != NULL)
226 : {
227 82 : if (gl_sortedlist_nx_add ((gl_list_t) table.keys, key_compare, key)
228 : == NULL)
229 : {
230 0 : gl_list_remove_node ((gl_list_t) table.elements, tnode);
231 0 : st = PDF_ENOMEM;
232 : }
233 : }
234 : else
235 : {
236 0 : pdf_dealloc (newelt);
237 0 : st = PDF_ENOMEM;
238 : }
239 : }
240 : else
241 : {
242 0 : st = PDF_ENOMEM;
243 : }
244 : }
245 : else
246 : {
247 2 : st = PDF_EBADDATA;
248 : }
249 :
250 :
251 43 : return st;
252 :
253 : }
254 :
255 :
256 : pdf_status_t
257 : pdf_hash_remove (pdf_hash_t table, const char *key)
258 3 : {
259 : pdf_status_t st;
260 : pdf_hash_element_t elt;
261 : gl_list_node_t node;
262 :
263 3 : st = PDF_OK;
264 :
265 3 : if (key != NULL)
266 : {
267 2 : elt.key = key;
268 2 : node = gl_list_search ((gl_list_t)table.elements, &elt);
269 2 : if (node != NULL)
270 : {
271 : pdf_hash_element_t *removed;
272 2 : removed = (pdf_hash_element_t*)
273 : gl_list_node_value((gl_list_t)table.elements, node);
274 :
275 1 : if (removed->disp_fn != NULL)
276 : {
277 0 : removed->disp_fn (removed->value);
278 : }
279 :
280 1 : pdf_dealloc(removed);
281 1 : gl_list_remove_node ((gl_list_t)table.elements, node);
282 1 : gl_sortedlist_remove ((gl_list_t)table.keys, key_compare, key);
283 : }
284 : else
285 : {
286 1 : st = PDF_ERROR;
287 : }
288 : }
289 : else
290 : {
291 1 : st = PDF_EBADDATA;
292 : }
293 :
294 :
295 3 : return st;
296 :
297 : }
298 :
299 :
300 : pdf_status_t
301 : pdf_hash_get (const pdf_hash_t table, const char *key, const void **elem_pointer)
302 14 : {
303 : pdf_status_t st;
304 : gl_list_node_t node;
305 : pdf_hash_element_t elem, *searched;
306 :
307 14 : st = PDF_OK;
308 :
309 14 : if (key != NULL && elem_pointer != NULL)
310 : {
311 12 : elem.key = key;
312 12 : node = gl_list_search ((gl_list_t)table.elements, &elem);
313 12 : if (node != NULL)
314 : {
315 22 : searched = (pdf_hash_element_t*)
316 : gl_list_node_value ((gl_list_t)table.elements, node);
317 11 : *elem_pointer = searched->value;
318 : }
319 : else
320 : {
321 1 : st = PDF_ERROR;
322 : }
323 : }
324 : else
325 : {
326 2 : st = PDF_EBADDATA;
327 : }
328 :
329 14 : return st;
330 :
331 : }
332 :
333 :
334 : pdf_status_t
335 : pdf_hash_iterator_new (const pdf_hash_t table, pdf_hash_iterator_t *iterator)
336 5 : {
337 : pdf_status_t st;
338 :
339 5 : st = PDF_OK;
340 :
341 5 : if (iterator != NULL)
342 : {
343 8 : *((gl_list_iterator_t*)iterator->gl_itr) =
344 : gl_list_iterator ((gl_list_t)table.keys);
345 : }
346 : else
347 : {
348 1 : st = PDF_EBADDATA;
349 : }
350 :
351 5 : return st;
352 :
353 : }
354 :
355 :
356 : pdf_status_t
357 : pdf_hash_iterator_next (pdf_hash_iterator_t iterator, const char **key)
358 2 : {
359 : pdf_status_t st;
360 :
361 2 : st = PDF_OK;
362 :
363 2 : if (key != NULL)
364 : {
365 2 : if (!gl_list_iterator_next((gl_list_iterator_t*)iterator.gl_itr,
366 : (const void**)key, NULL))
367 : {
368 0 : st = PDF_ERROR;
369 : }
370 : }
371 : else
372 : {
373 1 : st = PDF_EBADDATA;
374 : }
375 :
376 2 : return st;
377 : }
378 :
379 :
380 : pdf_status_t
381 : pdf_hash_iterator_destroy (pdf_hash_iterator_t iterator)
382 4 : {
383 :
384 4 : if (iterator.gl_itr != NULL)
385 : {
386 4 : gl_list_iterator_free ((gl_list_iterator_t*)iterator.gl_itr);
387 : }
388 :
389 4 : return PDF_OK;
390 : }
391 :
392 :
393 :
394 :
395 :
396 : static size_t
397 : hash_pjw (const void *elt)
398 57 : {
399 : const pdf_hash_element_t *hashelem;
400 : const char *s;
401 57 : size_t h = 0;
402 :
403 57 : hashelem = (const pdf_hash_element_t*) elt;
404 :
405 285 : for (s = hashelem->key; *s; s++)
406 228 : h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
407 :
408 57 : return h;
409 : }
410 :
411 :
412 : void
413 : pdf_hash_element_dealloc_fn (const void * elt)
414 0 : {
415 0 : pdf_dealloc(elt);
416 0 : }
417 :
418 :
419 : void
420 : pdf_hash_key_dealloc_fn (const void * elt)
421 0 : {
422 0 : pdf_dealloc(elt);
423 0 : }
424 :
425 :
426 : static bool
427 : elem_key_equal (const void *elt1, const void *elt2)
428 13 : {
429 : const char *key1, *key2;
430 :
431 13 : key1 = ((pdf_hash_element_t*)elt1)->key;
432 13 : key2 = ((pdf_hash_element_t*)elt2)->key;
433 :
434 13 : return (!strcmp(key1,key2));
435 : }
436 :
437 :
438 : static bool
439 : key_equal (const void *key1, const void *key2)
440 0 : {
441 0 : return (!strcmp((const char*)key1,(const char*)key2));
442 : }
443 :
444 :
445 : static int
446 : key_numeric_p (const char *str)
447 : {
448 130 : if (str != NULL && *str != '\0')
449 : {
450 191 : while (*str != '\0')
451 : {
452 171 : if (*str < '0' || *str > '9')
453 : {
454 110 : return 0;
455 : }
456 61 : str++;
457 : }
458 :
459 20 : return 1;
460 : }
461 :
462 0 : return 0;
463 : }
464 :
465 :
466 : static int
467 : key_numeric_cmp (const char *key1, const char *key2)
468 : {
469 : unsigned int num1, num2;
470 : char *end_char;
471 :
472 : /* Note that no error checking is made here */
473 6 : num1 = (int) strtol (key1, &end_char, 10);
474 6 : num2 = (int) strtol (key2, &end_char, 10);
475 :
476 6 : if (num1 > num2)
477 : {
478 5 : return 1;
479 : }
480 1 : else if (num1 < num2)
481 : {
482 1 : return -1;
483 : }
484 0 : return 0;
485 : }
486 :
487 :
488 : static int
489 : key_compare (const void *key1, const void *key2)
490 65 : {
491 130 : if (key_numeric_p(key1))
492 : {
493 12 : if (key_numeric_p(key2))
494 : {
495 12 : return (key_numeric_cmp(key1, key2));
496 : }
497 : /* key2 is non-numeric so key1 > key2 */
498 0 : return 1;
499 : }
500 : /* key1 non-numeric */
501 118 : if (key_numeric_p(key2))
502 : {
503 8 : return -1;
504 : }
505 : /* both are non-numeric */
506 51 : return (strcmp((const char*)key1,(const char*)key2));
507 : }
508 :
509 :
510 : /* End of pdf-hash.c */
|
