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