1/*
2 * hash.c: chained hash tables
3 *
4 * Reference: Your favorite introductory book on algorithms
5 *
6 * Copyright (C) 2000,2012 Bjorn Reese and Daniel Veillard.
7 *
8 * Permission to use, copy, modify, and distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice appear in all copies.
11 *
12 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
13 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
14 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
15 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
16 *
17 * Author: breese@users.sourceforge.net
18 */
19
20#define IN_LIBXML
21#include "libxml.h"
22
23#include <string.h>
24#ifdef HAVE_STDLIB_H
25#include <stdlib.h>
26#endif
27#ifdef HAVE_TIME_H
28#include <time.h>
29#endif
30
31/*
32 * Following http://www.ocert.org/advisories/ocert-2011-003.html
33 * it seems that having hash randomization might be a good idea
34 * when using XML with untrusted data
35 */
36#if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME)
37#define HASH_RANDOMIZATION
38#endif
39
40#include <libxml/parser.h>
41#include <libxml/hash.h>
42#include <libxml/xmlmemory.h>
43#include <libxml/xmlerror.h>
44#include <libxml/globals.h>
45
46#define MAX_HASH_LEN 8
47
48/* #define DEBUG_GROW */
49
50/*
51 * A single entry in the hash table
52 */
53typedef struct _xmlHashEntry xmlHashEntry;
54typedef xmlHashEntry *xmlHashEntryPtr;
55struct _xmlHashEntry {
56 struct _xmlHashEntry *next;
57 xmlChar *name;
58 xmlChar *name2;
59 xmlChar *name3;
60 void *payload;
61 int valid;
62};
63
64/*
65 * The entire hash table
66 */
67struct _xmlHashTable {
68 struct _xmlHashEntry *table;
69 int size;
70 int nbElems;
71 xmlDictPtr dict;
72#ifdef HASH_RANDOMIZATION
73 int random_seed;
74#endif
75};
76
77/*
78 * xmlHashComputeKey:
79 * Calculate the hash key
80 */
81static unsigned long
82xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
83 const xmlChar *name2, const xmlChar *name3) {
84 unsigned long value = 0L;
85 char ch;
86
87#ifdef HASH_RANDOMIZATION
88 value = table->random_seed;
89#endif
90 if (name != NULL) {
91 value += 30 * (*name);
92 while ((ch = *name++) != 0) {
93 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
94 }
95 }
96 value = value ^ ((value << 5) + (value >> 3));
97 if (name2 != NULL) {
98 while ((ch = *name2++) != 0) {
99 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
100 }
101 }
102 value = value ^ ((value << 5) + (value >> 3));
103 if (name3 != NULL) {
104 while ((ch = *name3++) != 0) {
105 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
106 }
107 }
108 return (value % table->size);
109}
110
111static unsigned long
112xmlHashComputeQKey(xmlHashTablePtr table,
113 const xmlChar *prefix, const xmlChar *name,
114 const xmlChar *prefix2, const xmlChar *name2,
115 const xmlChar *prefix3, const xmlChar *name3) {
116 unsigned long value = 0L;
117 char ch;
118
119#ifdef HASH_RANDOMIZATION
120 value = table->random_seed;
121#endif
122 if (prefix != NULL)
123 value += 30 * (*prefix);
124 else
125 value += 30 * (*name);
126
127 if (prefix != NULL) {
128 while ((ch = *prefix++) != 0) {
129 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
130 }
131 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
132 }
133 if (name != NULL) {
134 while ((ch = *name++) != 0) {
135 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
136 }
137 }
138 value = value ^ ((value << 5) + (value >> 3));
139 if (prefix2 != NULL) {
140 while ((ch = *prefix2++) != 0) {
141 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
142 }
143 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
144 }
145 if (name2 != NULL) {
146 while ((ch = *name2++) != 0) {
147 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
148 }
149 }
150 value = value ^ ((value << 5) + (value >> 3));
151 if (prefix3 != NULL) {
152 while ((ch = *prefix3++) != 0) {
153 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
154 }
155 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
156 }
157 if (name3 != NULL) {
158 while ((ch = *name3++) != 0) {
159 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
160 }
161 }
162 return (value % table->size);
163}
164
165/**
166 * xmlHashCreate:
167 * @size: the size of the hash table
168 *
169 * Create a new xmlHashTablePtr.
170 *
171 * Returns the newly created object, or NULL if an error occurred.
172 */
173xmlHashTablePtr
174xmlHashCreate(int size) {
175 xmlHashTablePtr table;
176
177 if (size <= 0)
178 size = 256;
179
180 table = xmlMalloc(sizeof(xmlHashTable));
181 if (table) {
182 table->dict = NULL;
183 table->size = size;
184 table->nbElems = 0;
185 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
186 if (table->table) {
187 memset(table->table, 0, size * sizeof(xmlHashEntry));
188#ifdef HASH_RANDOMIZATION
189 table->random_seed = __xmlRandom();
190#endif
191 return(table);
192 }
193 xmlFree(table);
194 }
195 return(NULL);
196}
197
198/**
199 * xmlHashCreateDict:
200 * @size: the size of the hash table
201 * @dict: a dictionary to use for the hash
202 *
203 * Create a new xmlHashTablePtr which will use @dict as the internal dictionary
204 *
205 * Returns the newly created object, or NULL if an error occurred.
206 */
207xmlHashTablePtr
208xmlHashCreateDict(int size, xmlDictPtr dict) {
209 xmlHashTablePtr table;
210
211 table = xmlHashCreate(size);
212 if (table != NULL) {
213 table->dict = dict;
214 xmlDictReference(dict);
215 }
216 return(table);
217}
218
219/**
220 * xmlHashGrow:
221 * @table: the hash table
222 * @size: the new size of the hash table
223 *
224 * resize the hash table
225 *
226 * Returns 0 in case of success, -1 in case of failure
227 */
228static int
229xmlHashGrow(xmlHashTablePtr table, int size) {
230 unsigned long key;
231 int oldsize, i;
232 xmlHashEntryPtr iter, next;
233 struct _xmlHashEntry *oldtable;
234#ifdef DEBUG_GROW
235 unsigned long nbElem = 0;
236#endif
237
238 if (table == NULL)
239 return(-1);
240 if (size < 8)
241 return(-1);
242 if (size > 8 * 2048)
243 return(-1);
244
245 oldsize = table->size;
246 oldtable = table->table;
247 if (oldtable == NULL)
248 return(-1);
249
250 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
251 if (table->table == NULL) {
252 table->table = oldtable;
253 return(-1);
254 }
255 memset(table->table, 0, size * sizeof(xmlHashEntry));
256 table->size = size;
257
258 /* If the two loops are merged, there would be situations where
259 a new entry needs to allocated and data copied into it from
260 the main table. So instead, we run through the array twice, first
261 copying all the elements in the main array (where we can't get
262 conflicts) and then the rest, so we only free (and don't allocate)
263 */
264 for (i = 0; i < oldsize; i++) {
265 if (oldtable[i].valid == 0)
266 continue;
267 key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
268 oldtable[i].name3);
269 memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
270 table->table[key].next = NULL;
271 }
272
273 for (i = 0; i < oldsize; i++) {
274 iter = oldtable[i].next;
275 while (iter) {
276 next = iter->next;
277
278 /*
279 * put back the entry in the new table
280 */
281
282 key = xmlHashComputeKey(table, iter->name, iter->name2,
283 iter->name3);
284 if (table->table[key].valid == 0) {
285 memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
286 table->table[key].next = NULL;
287 xmlFree(iter);
288 } else {
289 iter->next = table->table[key].next;
290 table->table[key].next = iter;
291 }
292
293#ifdef DEBUG_GROW
294 nbElem++;
295#endif
296
297 iter = next;
298 }
299 }
300
301 xmlFree(oldtable);
302
303#ifdef DEBUG_GROW
304 xmlGenericError(xmlGenericErrorContext,
305 "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
306#endif
307
308 return(0);
309}
310
311/**
312 * xmlHashFree:
313 * @table: the hash table
314 * @f: the deallocator function for items in the hash
315 *
316 * Free the hash @table and its contents. The userdata is
317 * deallocated with @f if provided.
318 */
319void
320xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
321 int i;
322 xmlHashEntryPtr iter;
323 xmlHashEntryPtr next;
324 int inside_table = 0;
325 int nbElems;
326
327 if (table == NULL)
328 return;
329 if (table->table) {
330 nbElems = table->nbElems;
331 for(i = 0; (i < table->size) && (nbElems > 0); i++) {
332 iter = &(table->table[i]);
333 if (iter->valid == 0)
334 continue;
335 inside_table = 1;
336 while (iter) {
337 next = iter->next;
338 if ((f != NULL) && (iter->payload != NULL))
339 f(iter->payload, iter->name);
340 if (table->dict == NULL) {
341 if (iter->name)
342 xmlFree(iter->name);
343 if (iter->name2)
344 xmlFree(iter->name2);
345 if (iter->name3)
346 xmlFree(iter->name3);
347 }
348 iter->payload = NULL;
349 if (!inside_table)
350 xmlFree(iter);
351 nbElems--;
352 inside_table = 0;
353 iter = next;
354 }
355 }
356 xmlFree(table->table);
357 }
358 if (table->dict)
359 xmlDictFree(table->dict);
360 xmlFree(table);
361}
362
363/**
364 * xmlHashDefaultDeallocator:
365 * @entry: the hash table entry
366 * @name: the entry's name
367 *
368 * Free a hash table entry with xmlFree.
369 */
370void
371xmlHashDefaultDeallocator(void *entry, const xmlChar *name ATTRIBUTE_UNUSED) {
372 xmlFree(entry);
373}
374
375/**
376 * xmlHashAddEntry:
377 * @table: the hash table
378 * @name: the name of the userdata
379 * @userdata: a pointer to the userdata
380 *
381 * Add the @userdata to the hash @table. This can later be retrieved
382 * by using the @name. Duplicate names generate errors.
383 *
384 * Returns 0 the addition succeeded and -1 in case of error.
385 */
386int
387xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
388 return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
389}
390
391/**
392 * xmlHashAddEntry2:
393 * @table: the hash table
394 * @name: the name of the userdata
395 * @name2: a second name of the userdata
396 * @userdata: a pointer to the userdata
397 *
398 * Add the @userdata to the hash @table. This can later be retrieved
399 * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
400 *
401 * Returns 0 the addition succeeded and -1 in case of error.
402 */
403int
404xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
405 const xmlChar *name2, void *userdata) {
406 return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
407}
408
409/**
410 * xmlHashUpdateEntry:
411 * @table: the hash table
412 * @name: the name of the userdata
413 * @userdata: a pointer to the userdata
414 * @f: the deallocator function for replaced item (if any)
415 *
416 * Add the @userdata to the hash @table. This can later be retrieved
417 * by using the @name. Existing entry for this @name will be removed
418 * and freed with @f if found.
419 *
420 * Returns 0 the addition succeeded and -1 in case of error.
421 */
422int
423xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
424 void *userdata, xmlHashDeallocator f) {
425 return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
426}
427
428/**
429 * xmlHashUpdateEntry2:
430 * @table: the hash table
431 * @name: the name of the userdata
432 * @name2: a second name of the userdata
433 * @userdata: a pointer to the userdata
434 * @f: the deallocator function for replaced item (if any)
435 *
436 * Add the @userdata to the hash @table. This can later be retrieved
437 * by using the (@name, @name2) tuple. Existing entry for this tuple will
438 * be removed and freed with @f if found.
439 *
440 * Returns 0 the addition succeeded and -1 in case of error.
441 */
442int
443xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
444 const xmlChar *name2, void *userdata,
445 xmlHashDeallocator f) {
446 return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
447}
448
449/**
450 * xmlHashLookup:
451 * @table: the hash table
452 * @name: the name of the userdata
453 *
454 * Find the userdata specified by the @name.
455 *
456 * Returns the pointer to the userdata
457 */
458void *
459xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
460 return(xmlHashLookup3(table, name, NULL, NULL));
461}
462
463/**
464 * xmlHashLookup2:
465 * @table: the hash table
466 * @name: the name of the userdata
467 * @name2: a second name of the userdata
468 *
469 * Find the userdata specified by the (@name, @name2) tuple.
470 *
471 * Returns the pointer to the userdata
472 */
473void *
474xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
475 const xmlChar *name2) {
476 return(xmlHashLookup3(table, name, name2, NULL));
477}
478
479/**
480 * xmlHashQLookup:
481 * @table: the hash table
482 * @prefix: the prefix of the userdata
483 * @name: the name of the userdata
484 *
485 * Find the userdata specified by the QName @prefix:@name/@name.
486 *
487 * Returns the pointer to the userdata
488 */
489void *
490xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,
491 const xmlChar *name) {
492 return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));
493}
494
495/**
496 * xmlHashQLookup2:
497 * @table: the hash table
498 * @prefix: the prefix of the userdata
499 * @name: the name of the userdata
500 * @prefix2: the second prefix of the userdata
501 * @name2: a second name of the userdata
502 *
503 * Find the userdata specified by the QNames tuple
504 *
505 * Returns the pointer to the userdata
506 */
507void *
508xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,
509 const xmlChar *name, const xmlChar *prefix2,
510 const xmlChar *name2) {
511 return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
512}
513
514/**
515 * xmlHashAddEntry3:
516 * @table: the hash table
517 * @name: the name of the userdata
518 * @name2: a second name of the userdata
519 * @name3: a third name of the userdata
520 * @userdata: a pointer to the userdata
521 *
522 * Add the @userdata to the hash @table. This can later be retrieved
523 * by using the tuple (@name, @name2, @name3). Duplicate entries generate
524 * errors.
525 *
526 * Returns 0 the addition succeeded and -1 in case of error.
527 */
528int
529xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
530 const xmlChar *name2, const xmlChar *name3,
531 void *userdata) {
532 unsigned long key, len = 0;
533 xmlHashEntryPtr entry;
534 xmlHashEntryPtr insert;
535
536 if ((table == NULL) || (name == NULL))
537 return(-1);
538
539 /*
540 * If using a dict internalize if needed
541 */
542 if (table->dict) {
543 if (!xmlDictOwns(table->dict, name)) {
544 name = xmlDictLookup(table->dict, name, -1);
545 if (name == NULL)
546 return(-1);
547 }
548 if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
549 name2 = xmlDictLookup(table->dict, name2, -1);
550 if (name2 == NULL)
551 return(-1);
552 }
553 if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
554 name3 = xmlDictLookup(table->dict, name3, -1);
555 if (name3 == NULL)
556 return(-1);
557 }
558 }
559
560 /*
561 * Check for duplicate and insertion location.
562 */
563 key = xmlHashComputeKey(table, name, name2, name3);
564 if (table->table[key].valid == 0) {
565 insert = NULL;
566 } else {
567 if (table->dict) {
568 for (insert = &(table->table[key]); insert->next != NULL;
569 insert = insert->next) {
570 if ((insert->name == name) &&
571 (insert->name2 == name2) &&
572 (insert->name3 == name3))
573 return(-1);
574 len++;
575 }
576 if ((insert->name == name) &&
577 (insert->name2 == name2) &&
578 (insert->name3 == name3))
579 return(-1);
580 } else {
581 for (insert = &(table->table[key]); insert->next != NULL;
582 insert = insert->next) {
583 if ((xmlStrEqual(insert->name, name)) &&
584 (xmlStrEqual(insert->name2, name2)) &&
585 (xmlStrEqual(insert->name3, name3)))
586 return(-1);
587 len++;
588 }
589 if ((xmlStrEqual(insert->name, name)) &&
590 (xmlStrEqual(insert->name2, name2)) &&
591 (xmlStrEqual(insert->name3, name3)))
592 return(-1);
593 }
594 }
595
596 if (insert == NULL) {
597 entry = &(table->table[key]);
598 } else {
599 entry = xmlMalloc(sizeof(xmlHashEntry));
600 if (entry == NULL)
601 return(-1);
602 }
603
604 if (table->dict != NULL) {
605 entry->name = (xmlChar *) name;
606 entry->name2 = (xmlChar *) name2;
607 entry->name3 = (xmlChar *) name3;
608 } else {
609 entry->name = xmlStrdup(name);
610 entry->name2 = xmlStrdup(name2);
611 entry->name3 = xmlStrdup(name3);
612 }
613 entry->payload = userdata;
614 entry->next = NULL;
615 entry->valid = 1;
616
617
618 if (insert != NULL)
619 insert->next = entry;
620
621 table->nbElems++;
622
623 if (len > MAX_HASH_LEN)
624 xmlHashGrow(table, MAX_HASH_LEN * table->size);
625
626 return(0);
627}
628
629/**
630 * xmlHashUpdateEntry3:
631 * @table: the hash table
632 * @name: the name of the userdata
633 * @name2: a second name of the userdata
634 * @name3: a third name of the userdata
635 * @userdata: a pointer to the userdata
636 * @f: the deallocator function for replaced item (if any)
637 *
638 * Add the @userdata to the hash @table. This can later be retrieved
639 * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
640 * will be removed and freed with @f if found.
641 *
642 * Returns 0 the addition succeeded and -1 in case of error.
643 */
644int
645xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
646 const xmlChar *name2, const xmlChar *name3,
647 void *userdata, xmlHashDeallocator f) {
648 unsigned long key;
649 xmlHashEntryPtr entry;
650 xmlHashEntryPtr insert;
651
652 if ((table == NULL) || name == NULL)
653 return(-1);
654
655 /*
656 * If using a dict internalize if needed
657 */
658 if (table->dict) {
659 if (!xmlDictOwns(table->dict, name)) {
660 name = xmlDictLookup(table->dict, name, -1);
661 if (name == NULL)
662 return(-1);
663 }
664 if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
665 name2 = xmlDictLookup(table->dict, name2, -1);
666 if (name2 == NULL)
667 return(-1);
668 }
669 if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
670 name3 = xmlDictLookup(table->dict, name3, -1);
671 if (name3 == NULL)
672 return(-1);
673 }
674 }
675
676 /*
677 * Check for duplicate and insertion location.
678 */
679 key = xmlHashComputeKey(table, name, name2, name3);
680 if (table->table[key].valid == 0) {
681 insert = NULL;
682 } else {
683 if (table ->dict) {
684 for (insert = &(table->table[key]); insert->next != NULL;
685 insert = insert->next) {
686 if ((insert->name == name) &&
687 (insert->name2 == name2) &&
688 (insert->name3 == name3)) {
689 if (f)
690 f(insert->payload, insert->name);
691 insert->payload = userdata;
692 return(0);
693 }
694 }
695 if ((insert->name == name) &&
696 (insert->name2 == name2) &&
697 (insert->name3 == name3)) {
698 if (f)
699 f(insert->payload, insert->name);
700 insert->payload = userdata;
701 return(0);
702 }
703 } else {
704 for (insert = &(table->table[key]); insert->next != NULL;
705 insert = insert->next) {
706 if ((xmlStrEqual(insert->name, name)) &&
707 (xmlStrEqual(insert->name2, name2)) &&
708 (xmlStrEqual(insert->name3, name3))) {
709 if (f)
710 f(insert->payload, insert->name);
711 insert->payload = userdata;
712 return(0);
713 }
714 }
715 if ((xmlStrEqual(insert->name, name)) &&
716 (xmlStrEqual(insert->name2, name2)) &&
717 (xmlStrEqual(insert->name3, name3))) {
718 if (f)
719 f(insert->payload, insert->name);
720 insert->payload = userdata;
721 return(0);
722 }
723 }
724 }
725
726 if (insert == NULL) {
727 entry = &(table->table[key]);
728 } else {
729 entry = xmlMalloc(sizeof(xmlHashEntry));
730 if (entry == NULL)
731 return(-1);
732 }
733
734 if (table->dict != NULL) {
735 entry->name = (xmlChar *) name;
736 entry->name2 = (xmlChar *) name2;
737 entry->name3 = (xmlChar *) name3;
738 } else {
739 entry->name = xmlStrdup(name);
740 entry->name2 = xmlStrdup(name2);
741 entry->name3 = xmlStrdup(name3);
742 }
743 entry->payload = userdata;
744 entry->next = NULL;
745 entry->valid = 1;
746 table->nbElems++;
747
748
749 if (insert != NULL) {
750 insert->next = entry;
751 }
752 return(0);
753}
754
755/**
756 * xmlHashLookup3:
757 * @table: the hash table
758 * @name: the name of the userdata
759 * @name2: a second name of the userdata
760 * @name3: a third name of the userdata
761 *
762 * Find the userdata specified by the (@name, @name2, @name3) tuple.
763 *
764 * Returns the a pointer to the userdata
765 */
766void *
767xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
768 const xmlChar *name2, const xmlChar *name3) {
769 unsigned long key;
770 xmlHashEntryPtr entry;
771
772 if (table == NULL)
773 return(NULL);
774 if (name == NULL)
775 return(NULL);
776 key = xmlHashComputeKey(table, name, name2, name3);
777 if (table->table[key].valid == 0)
778 return(NULL);
779 if (table->dict) {
780 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
781 if ((entry->name == name) &&
782 (entry->name2 == name2) &&
783 (entry->name3 == name3))
784 return(entry->payload);
785 }
786 }
787 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
788 if ((xmlStrEqual(entry->name, name)) &&
789 (xmlStrEqual(entry->name2, name2)) &&
790 (xmlStrEqual(entry->name3, name3)))
791 return(entry->payload);
792 }
793 return(NULL);
794}
795
796/**
797 * xmlHashQLookup3:
798 * @table: the hash table
799 * @prefix: the prefix of the userdata
800 * @name: the name of the userdata
801 * @prefix2: the second prefix of the userdata
802 * @name2: a second name of the userdata
803 * @prefix3: the third prefix of the userdata
804 * @name3: a third name of the userdata
805 *
806 * Find the userdata specified by the (@name, @name2, @name3) tuple.
807 *
808 * Returns the a pointer to the userdata
809 */
810void *
811xmlHashQLookup3(xmlHashTablePtr table,
812 const xmlChar *prefix, const xmlChar *name,
813 const xmlChar *prefix2, const xmlChar *name2,
814 const xmlChar *prefix3, const xmlChar *name3) {
815 unsigned long key;
816 xmlHashEntryPtr entry;
817
818 if (table == NULL)
819 return(NULL);
820 if (name == NULL)
821 return(NULL);
822 key = xmlHashComputeQKey(table, prefix, name, prefix2,
823 name2, prefix3, name3);
824 if (table->table[key].valid == 0)
825 return(NULL);
826 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
827 if ((xmlStrQEqual(prefix, name, entry->name)) &&
828 (xmlStrQEqual(prefix2, name2, entry->name2)) &&
829 (xmlStrQEqual(prefix3, name3, entry->name3)))
830 return(entry->payload);
831 }
832 return(NULL);
833}
834
835typedef struct {
836 xmlHashScanner hashscanner;
837 void *data;
838} stubData;
839
840static void
841stubHashScannerFull (void *payload, void *data, const xmlChar *name,
842 const xmlChar *name2 ATTRIBUTE_UNUSED,
843 const xmlChar *name3 ATTRIBUTE_UNUSED) {
844 stubData *stubdata = (stubData *) data;
845 stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
846}
847
848/**
849 * xmlHashScan:
850 * @table: the hash table
851 * @f: the scanner function for items in the hash
852 * @data: extra data passed to f
853 *
854 * Scan the hash @table and applied @f to each value.
855 */
856void
857xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
858 stubData stubdata;
859 stubdata.data = data;
860 stubdata.hashscanner = f;
861 xmlHashScanFull (table, stubHashScannerFull, &stubdata);
862}
863
864/**
865 * xmlHashScanFull:
866 * @table: the hash table
867 * @f: the scanner function for items in the hash
868 * @data: extra data passed to f
869 *
870 * Scan the hash @table and applied @f to each value.
871 */
872void
873xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
874 int i, nb;
875 xmlHashEntryPtr iter;
876 xmlHashEntryPtr next;
877
878 if (table == NULL)
879 return;
880 if (f == NULL)
881 return;
882
883 if (table->table) {
884 for(i = 0; i < table->size; i++) {
885 if (table->table[i].valid == 0)
886 continue;
887 iter = &(table->table[i]);
888 while (iter) {
889 next = iter->next;
890 nb = table->nbElems;
891 if ((f != NULL) && (iter->payload != NULL))
892 f(iter->payload, data, iter->name,
893 iter->name2, iter->name3);
894 if (nb != table->nbElems) {
895 /* table was modified by the callback, be careful */
896 if (iter == &(table->table[i])) {
897 if (table->table[i].valid == 0)
898 iter = NULL;
899 if (table->table[i].next != next)
900 iter = &(table->table[i]);
901 } else
902 iter = next;
903 } else
904 iter = next;
905 }
906 }
907 }
908}
909
910/**
911 * xmlHashScan3:
912 * @table: the hash table
913 * @name: the name of the userdata or NULL
914 * @name2: a second name of the userdata or NULL
915 * @name3: a third name of the userdata or NULL
916 * @f: the scanner function for items in the hash
917 * @data: extra data passed to f
918 *
919 * Scan the hash @table and applied @f to each value matching
920 * (@name, @name2, @name3) tuple. If one of the names is null,
921 * the comparison is considered to match.
922 */
923void
924xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
925 const xmlChar *name2, const xmlChar *name3,
926 xmlHashScanner f, void *data) {
927 stubData stubdata;
928 stubdata.data = data;
929 stubdata.hashscanner = f;
930 xmlHashScanFull3(table, name, name2, name3, stubHashScannerFull,
931 &stubdata);
932}
933
934/**
935 * xmlHashScanFull3:
936 * @table: the hash table
937 * @name: the name of the userdata or NULL
938 * @name2: a second name of the userdata or NULL
939 * @name3: a third name of the userdata or NULL
940 * @f: the scanner function for items in the hash
941 * @data: extra data passed to f
942 *
943 * Scan the hash @table and applied @f to each value matching
944 * (@name, @name2, @name3) tuple. If one of the names is null,
945 * the comparison is considered to match.
946 */
947void
948xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
949 const xmlChar *name2, const xmlChar *name3,
950 xmlHashScannerFull f, void *data) {
951 int i;
952 xmlHashEntryPtr iter;
953 xmlHashEntryPtr next;
954
955 if (table == NULL)
956 return;
957 if (f == NULL)
958 return;
959
960 if (table->table) {
961 for(i = 0; i < table->size; i++) {
962 if (table->table[i].valid == 0)
963 continue;
964 iter = &(table->table[i]);
965 while (iter) {
966 next = iter->next;
967 if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
968 ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
969 ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&
970 (iter->payload != NULL)) {
971 f(iter->payload, data, iter->name,
972 iter->name2, iter->name3);
973 }
974 iter = next;
975 }
976 }
977 }
978}
979
980/**
981 * xmlHashCopy:
982 * @table: the hash table
983 * @f: the copier function for items in the hash
984 *
985 * Scan the hash @table and applied @f to each value.
986 *
987 * Returns the new table or NULL in case of error.
988 */
989xmlHashTablePtr
990xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
991 int i;
992 xmlHashEntryPtr iter;
993 xmlHashEntryPtr next;
994 xmlHashTablePtr ret;
995
996 if (table == NULL)
997 return(NULL);
998 if (f == NULL)
999 return(NULL);
1000
1001 ret = xmlHashCreate(table->size);
1002 if (ret == NULL)
1003 return(NULL);
1004
1005 if (table->table) {
1006 for(i = 0; i < table->size; i++) {
1007 if (table->table[i].valid == 0)
1008 continue;
1009 iter = &(table->table[i]);
1010 while (iter) {
1011 next = iter->next;
1012 xmlHashAddEntry3(ret, iter->name, iter->name2,
1013 iter->name3, f(iter->payload, iter->name));
1014 iter = next;
1015 }
1016 }
1017 }
1018 ret->nbElems = table->nbElems;
1019 return(ret);
1020}
1021
1022/**
1023 * xmlHashSize:
1024 * @table: the hash table
1025 *
1026 * Query the number of elements installed in the hash @table.
1027 *
1028 * Returns the number of elements in the hash table or
1029 * -1 in case of error
1030 */
1031int
1032xmlHashSize(xmlHashTablePtr table) {
1033 if (table == NULL)
1034 return(-1);
1035 return(table->nbElems);
1036}
1037
1038/**
1039 * xmlHashRemoveEntry:
1040 * @table: the hash table
1041 * @name: the name of the userdata
1042 * @f: the deallocator function for removed item (if any)
1043 *
1044 * Find the userdata specified by the @name and remove
1045 * it from the hash @table. Existing userdata for this tuple will be removed
1046 * and freed with @f.
1047 *
1048 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1049 */
1050int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
1051 xmlHashDeallocator f) {
1052 return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
1053}
1054
1055/**
1056 * xmlHashRemoveEntry2:
1057 * @table: the hash table
1058 * @name: the name of the userdata
1059 * @name2: a second name of the userdata
1060 * @f: the deallocator function for removed item (if any)
1061 *
1062 * Find the userdata specified by the (@name, @name2) tuple and remove
1063 * it from the hash @table. Existing userdata for this tuple will be removed
1064 * and freed with @f.
1065 *
1066 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1067 */
1068int
1069xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
1070 const xmlChar *name2, xmlHashDeallocator f) {
1071 return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
1072}
1073
1074/**
1075 * xmlHashRemoveEntry3:
1076 * @table: the hash table
1077 * @name: the name of the userdata
1078 * @name2: a second name of the userdata
1079 * @name3: a third name of the userdata
1080 * @f: the deallocator function for removed item (if any)
1081 *
1082 * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
1083 * it from the hash @table. Existing userdata for this tuple will be removed
1084 * and freed with @f.
1085 *
1086 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1087 */
1088int
1089xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
1090 const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
1091 unsigned long key;
1092 xmlHashEntryPtr entry;
1093 xmlHashEntryPtr prev = NULL;
1094
1095 if (table == NULL || name == NULL)
1096 return(-1);
1097
1098 key = xmlHashComputeKey(table, name, name2, name3);
1099 if (table->table[key].valid == 0) {
1100 return(-1);
1101 } else {
1102 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
1103 if (xmlStrEqual(entry->name, name) &&
1104 xmlStrEqual(entry->name2, name2) &&
1105 xmlStrEqual(entry->name3, name3)) {
1106 if ((f != NULL) && (entry->payload != NULL))
1107 f(entry->payload, entry->name);
1108 entry->payload = NULL;
1109 if (table->dict == NULL) {
1110 if(entry->name)
1111 xmlFree(entry->name);
1112 if(entry->name2)
1113 xmlFree(entry->name2);
1114 if(entry->name3)
1115 xmlFree(entry->name3);
1116 }
1117 if(prev) {
1118 prev->next = entry->next;
1119 xmlFree(entry);
1120 } else {
1121 if (entry->next == NULL) {
1122 entry->valid = 0;
1123 } else {
1124 entry = entry->next;
1125 memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
1126 xmlFree(entry);
1127 }
1128 }
1129 table->nbElems--;
1130 return(0);
1131 }
1132 prev = entry;
1133 }
1134 return(-1);
1135 }
1136}
1137
1138#define bottom_hash
1139#include "elfgcchack.h"
1140