1 /*
2 * hash.c: hash tables
3 *
4 * Hash table with open addressing, linear probing and
5 * Robin Hood reordering.
6 *
7 * See Copyright for the status of this software.
8 */
9
10 #define IN_LIBXML
11 #include "libxml.h"
12
13 #include <string.h>
14 #include <limits.h>
15
16 #include <libxml/parser.h>
17 #include <libxml/hash.h>
18 #include <libxml/dict.h>
19 #include <libxml/xmlmemory.h>
20 #include <libxml/xmlstring.h>
21
22 #include "private/dict.h"
23
24 #ifndef SIZE_MAX
25 #define SIZE_MAX ((size_t) -1)
26 #endif
27
28 #define MAX_FILL_NUM 7
29 #define MAX_FILL_DENOM 8
30 #define MIN_HASH_SIZE 8
31 #define MAX_HASH_SIZE (1u << 31)
32
33 /*
34 * A single entry in the hash table
35 */
36 typedef struct {
37 unsigned hashValue; /* 0 means unoccupied, occupied entries have the
38 * MAX_HASH_SIZE bit set to 1 */
39 xmlChar *key;
40 xmlChar *key2; /* TODO: Don't allocate possibly empty keys */
41 xmlChar *key3;
42 void *payload;
43 } xmlHashEntry;
44
45 /*
46 * The entire hash table
47 */
48 struct _xmlHashTable {
49 xmlHashEntry *table;
50 unsigned size; /* power of two */
51 unsigned nbElems;
52 xmlDictPtr dict;
53 unsigned randomSeed;
54 };
55
56 static int
57 xmlHashGrow(xmlHashTablePtr hash, unsigned size);
58
59 ATTRIBUTE_NO_SANITIZE_INTEGER
60 static unsigned
61 xmlHashValue(unsigned seed, const xmlChar *key, const xmlChar *key2,
62 const xmlChar *key3, size_t *lengths) {
63 unsigned h1, h2;
64 size_t i;
65
66 HASH_INIT(h1, h2, seed);
67
68 for (i = 0; key[i] != 0; i++) {
69 HASH_UPDATE(h1, h2, key[i]);
70 }
71 if (lengths)
72 lengths[0] = i;
73
74 HASH_UPDATE(h1, h2, 0);
75
76 if (key2 != NULL) {
77 for (i = 0; key2[i] != 0; i++) {
78 HASH_UPDATE(h1, h2, key2[i]);
79 }
80 if (lengths)
81 lengths[1] = i;
82 }
83
84 HASH_UPDATE(h1, h2, 0);
85
86 if (key3 != NULL) {
87 for (i = 0; key3[i] != 0; i++) {
88 HASH_UPDATE(h1, h2, key3[i]);
89 }
90 if (lengths)
91 lengths[2] = i;
92 }
93
94 HASH_FINISH(h1, h2);
95
96 return(h2);
97 }
98
99 ATTRIBUTE_NO_SANITIZE_INTEGER
100 static unsigned
101 xmlHashQNameValue(unsigned seed,
102 const xmlChar *prefix, const xmlChar *name,
103 const xmlChar *prefix2, const xmlChar *name2,
104 const xmlChar *prefix3, const xmlChar *name3) {
105 unsigned h1, h2, ch;
106
107 HASH_INIT(h1, h2, seed);
108
109 if (prefix != NULL) {
110 while ((ch = *prefix++) != 0) {
111 HASH_UPDATE(h1, h2, ch);
112 }
113 HASH_UPDATE(h1, h2, ':');
114 }
115 if (name != NULL) {
116 while ((ch = *name++) != 0) {
117 HASH_UPDATE(h1, h2, ch);
118 }
119 }
120 HASH_UPDATE(h1, h2, 0);
121 if (prefix2 != NULL) {
122 while ((ch = *prefix2++) != 0) {
123 HASH_UPDATE(h1, h2, ch);
124 }
125 HASH_UPDATE(h1, h2, ':');
126 }
127 if (name2 != NULL) {
128 while ((ch = *name2++) != 0) {
129 HASH_UPDATE(h1, h2, ch);
130 }
131 }
132 HASH_UPDATE(h1, h2, 0);
133 if (prefix3 != NULL) {
134 while ((ch = *prefix3++) != 0) {
135 HASH_UPDATE(h1, h2, ch);
136 }
137 HASH_UPDATE(h1, h2, ':');
138 }
139 if (name3 != NULL) {
140 while ((ch = *name3++) != 0) {
141 HASH_UPDATE(h1, h2, ch);
142 }
143 }
144
145 HASH_FINISH(h1, h2);
146
147 return(h2);
148 }
149
150 /**
151 * xmlHashCreate:
152 * @size: initial size of the hash table
153 *
154 * Create a new hash table. Set size to zero if the number of entries
155 * can't be estimated.
156 *
157 * Returns the newly created object, or NULL if a memory allocation failed.
158 */
159 xmlHashTablePtr
160 xmlHashCreate(int size) {
161 xmlHashTablePtr hash;
162
163 xmlInitParser();
164
165 hash = xmlMalloc(sizeof(*hash));
166 if (hash == NULL)
167 return(NULL);
168 hash->dict = NULL;
169 hash->size = 0;
170 hash->table = NULL;
171 hash->nbElems = 0;
172 hash->randomSeed = xmlRandom();
173 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
174 hash->randomSeed = 0;
175 #endif
176
177 /*
178 * Unless a larger size is passed, the backing table is created
179 * lazily with MIN_HASH_SIZE capacity. In practice, there are many
180 * hash tables which are never filled.
181 */
182 if (size > MIN_HASH_SIZE) {
183 unsigned newSize = MIN_HASH_SIZE * 2;
184
185 while ((newSize < (unsigned) size) && (newSize < MAX_HASH_SIZE))
186 newSize *= 2;
187
188 if (xmlHashGrow(hash, newSize) != 0) {
189 xmlFree(hash);
190 return(NULL);
191 }
192 }
193
194 return(hash);
195 }
196
197 /**
198 * xmlHashCreateDict:
199 * @size: the size of the hash table
200 * @dict: a dictionary to use for the hash
201 *
202 * Create a new hash table backed by a dictionary. This can reduce
203 * resource usage considerably if most keys passed to API functions
204 * originate from this dictionary.
205 *
206 * Returns the newly created object, or NULL if a memory allocation failed.
207 */
208 xmlHashTablePtr
209 xmlHashCreateDict(int size, xmlDictPtr dict) {
210 xmlHashTablePtr hash;
211
212 hash = xmlHashCreate(size);
213 if (hash != NULL) {
214 hash->dict = dict;
215 xmlDictReference(dict);
216 }
217 return(hash);
218 }
219
220 /**
221 * xmlHashFree:
222 * @hash: hash table
223 * @dealloc: deallocator function or NULL
224 *
225 * Free the hash and its contents. The payload is deallocated with
226 * @dealloc if provided.
227 */
228 void
229 xmlHashFree(xmlHashTablePtr hash, xmlHashDeallocator dealloc) {
230 if (hash == NULL)
231 return;
232
233 if (hash->table) {
234 const xmlHashEntry *end = &hash->table[hash->size];
235 const xmlHashEntry *entry;
236
237 for (entry = hash->table; entry < end; entry++) {
238 if (entry->hashValue == 0)
239 continue;
240 if ((dealloc != NULL) && (entry->payload != NULL))
241 dealloc(entry->payload, entry->key);
242 if (hash->dict == NULL) {
243 if (entry->key)
244 xmlFree(entry->key);
245 if (entry->key2)
246 xmlFree(entry->key2);
247 if (entry->key3)
248 xmlFree(entry->key3);
249 }
250 }
251
252 xmlFree(hash->table);
253 }
254
255 if (hash->dict)
256 xmlDictFree(hash->dict);
257
258 xmlFree(hash);
259 }
260
261 /**
262 * xmlFastStrEqual:
263 * @s1: string
264 * @s2: string
265 *
266 * Compare two strings for equality, allowing NULL values.
267 */
268 static int
269 xmlFastStrEqual(const xmlChar *s1, const xmlChar *s2) {
270 if (s1 == NULL)
271 return(s2 == NULL);
272 else
273 return((s2 != NULL) &&
274 (strcmp((const char *) s1, (const char *) s2) == 0));
275 }
276
277 /**
278 * xmlHashFindEntry:
279 * @hash: hash table, non-NULL, size > 0
280 * @key: first string key, non-NULL
281 * @key2: second string key
282 * @key3: third string key
283 * @hashValue: valid hash value of keys
284 * @pfound: result of search
285 *
286 * Try to find a matching hash table entry. If an entry was found, set
287 * @found to 1 and return the entry. Otherwise, set @found to 0 and return
288 * the location where a new entry should be inserted.
289 */
290 ATTRIBUTE_NO_SANITIZE_INTEGER
291 static xmlHashEntry *
292 xmlHashFindEntry(const xmlHashTable *hash, const xmlChar *key,
293 const xmlChar *key2, const xmlChar *key3,
294 unsigned hashValue, int *pfound) {
295 xmlHashEntry *entry;
296 unsigned mask, pos, displ;
297 int found = 0;
298
299 mask = hash->size - 1;
300 pos = hashValue & mask;
301 entry = &hash->table[pos];
302
303 if (entry->hashValue != 0) {
304 /*
305 * Robin hood hashing: abort if the displacement of the entry
306 * is smaller than the displacement of the key we look for.
307 * This also stops at the correct position when inserting.
308 */
309 displ = 0;
310 hashValue |= MAX_HASH_SIZE;
311
312 do {
313 if (entry->hashValue == hashValue) {
314 if (hash->dict) {
315 if ((entry->key == key) &&
316 (entry->key2 == key2) &&
317 (entry->key3 == key3)) {
318 found = 1;
319 break;
320 }
321 }
322 if ((strcmp((const char *) entry->key,
323 (const char *) key) == 0) &&
324 (xmlFastStrEqual(entry->key2, key2)) &&
325 (xmlFastStrEqual(entry->key3, key3))) {
326 found = 1;
327 break;
328 }
329 }
330
331 displ++;
332 pos++;
333 entry++;
334 if ((pos & mask) == 0)
335 entry = hash->table;
336 } while ((entry->hashValue != 0) &&
337 (((pos - entry->hashValue) & mask) >= displ));
338 }
339
340 *pfound = found;
341 return(entry);
342 }
343
344 /**
345 * xmlHashGrow:
346 * @hash: hash table
347 * @size: new size of the hash table
348 *
349 * Resize the hash table.
350 *
351 * Returns 0 in case of success, -1 if a memory allocation failed.
352 */
353 static int
354 xmlHashGrow(xmlHashTablePtr hash, unsigned size) {
355 const xmlHashEntry *oldentry, *oldend, *end;
356 xmlHashEntry *table;
357 unsigned oldsize, i;
358
359 /* Add 0 to avoid spurious -Wtype-limits warning on 64-bit GCC */
360 if ((size_t) size + 0 > SIZE_MAX / sizeof(table[0]))
361 return(-1);
362 table = xmlMalloc(size * sizeof(table[0]));
363 if (table == NULL)
364 return(-1);
365 memset(table, 0, size * sizeof(table[0]));
366
367 oldsize = hash->size;
368 if (oldsize == 0)
369 goto done;
370
371 oldend = &hash->table[oldsize];
372 end = &table[size];
373
374 /*
375 * Robin Hood sorting order is maintained if we
376 *
377 * - compute hash indices with modulo
378 * - resize by an integer factor
379 * - start to copy from the beginning of a probe sequence
380 */
381 oldentry = hash->table;
382 while (oldentry->hashValue != 0) {
383 if (++oldentry >= oldend)
384 oldentry = hash->table;
385 }
386
387 for (i = 0; i < oldsize; i++) {
388 if (oldentry->hashValue != 0) {
389 xmlHashEntry *entry = &table[oldentry->hashValue & (size - 1)];
390
391 while (entry->hashValue != 0) {
392 if (++entry >= end)
393 entry = table;
394 }
395 *entry = *oldentry;
396 }
397
398 if (++oldentry >= oldend)
399 oldentry = hash->table;
400 }
401
402 xmlFree(hash->table);
403
404 done:
405 hash->table = table;
406 hash->size = size;
407
408 return(0);
409 }
410
411 /**
412 * xmlHashUpdateInternal:
413 * @hash: hash table
414 * @key: first string key
415 * @key2: second string key
416 * @key3: third string key
417 * @payload: pointer to the payload
418 * @dealloc: deallocator function for replaced item or NULL
419 * @update: whether existing entries should be updated
420 *
421 * Internal function to add or update hash entries.
422 */
423 ATTRIBUTE_NO_SANITIZE_INTEGER
424 static int
425 xmlHashUpdateInternal(xmlHashTablePtr hash, const xmlChar *key,
426 const xmlChar *key2, const xmlChar *key3,
427 void *payload, xmlHashDeallocator dealloc, int update) {
428 xmlChar *copy, *copy2, *copy3;
429 xmlHashEntry *entry = NULL;
430 size_t lengths[3];
431 unsigned hashValue;
432 int found = 0;
433
434 if ((hash == NULL) || (key == NULL))
435 return(-1);
436
437 /*
438 * Check for an existing entry
439 */
440 hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, lengths);
441 if (hash->size > 0)
442 entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found);
443 if (found) {
444 if (update) {
445 if (dealloc)
446 dealloc(entry->payload, entry->key);
447 entry->payload = payload;
448 return(0);
449 } else {
450 /*
451 * xmlHashAddEntry found an existing entry.
452 *
453 * TODO: We should return a different error code here to
454 * distinguish from malloc failures.
455 */
456 return(-1);
457 }
458 }
459
460 /*
461 * Grow the hash table if needed
462 */
463 if (hash->nbElems + 1 > hash->size / MAX_FILL_DENOM * MAX_FILL_NUM) {
464 unsigned newSize, mask, displ, pos;
465
466 if (hash->size == 0) {
467 newSize = MIN_HASH_SIZE;
468 } else {
469 /* This guarantees that nbElems < INT_MAX */
470 if (hash->size >= MAX_HASH_SIZE)
471 return(-1);
472 newSize = hash->size * 2;
473 }
474 if (xmlHashGrow(hash, newSize) != 0)
475 return(-1);
476
477 /*
478 * Find new entry
479 */
480 mask = hash->size - 1;
481 displ = 0;
482 pos = hashValue & mask;
483 entry = &hash->table[pos];
484
485 if (entry->hashValue != 0) {
486 do {
487 displ++;
488 pos++;
489 entry++;
490 if ((pos & mask) == 0)
491 entry = hash->table;
492 } while ((entry->hashValue != 0) &&
493 ((pos - entry->hashValue) & mask) >= displ);
494 }
495 }
496
497 /*
498 * Copy keys
499 */
500 if (hash->dict != NULL) {
501 if (xmlDictOwns(hash->dict, key)) {
502 copy = (xmlChar *) key;
503 } else {
504 copy = (xmlChar *) xmlDictLookup(hash->dict, key, -1);
505 if (copy == NULL)
506 return(-1);
507 }
508
509 if ((key2 == NULL) || (xmlDictOwns(hash->dict, key2))) {
510 copy2 = (xmlChar *) key2;
511 } else {
512 copy2 = (xmlChar *) xmlDictLookup(hash->dict, key2, -1);
513 if (copy2 == NULL)
514 return(-1);
515 }
516 if ((key3 == NULL) || (xmlDictOwns(hash->dict, key3))) {
517 copy3 = (xmlChar *) key3;
518 } else {
519 copy3 = (xmlChar *) xmlDictLookup(hash->dict, key3, -1);
520 if (copy3 == NULL)
521 return(-1);
522 }
523 } else {
524 copy = xmlMalloc(lengths[0] + 1);
525 if (copy == NULL)
526 return(-1);
527 memcpy(copy, key, lengths[0] + 1);
528
529 if (key2 != NULL) {
530 copy2 = xmlMalloc(lengths[1] + 1);
531 if (copy2 == NULL) {
532 xmlFree(copy);
533 return(-1);
534 }
535 memcpy(copy2, key2, lengths[1] + 1);
536 } else {
537 copy2 = NULL;
538 }
539
540 if (key3 != NULL) {
541 copy3 = xmlMalloc(lengths[2] + 1);
542 if (copy3 == NULL) {
543 xmlFree(copy);
544 xmlFree(copy2);
545 return(-1);
546 }
547 memcpy(copy3, key3, lengths[2] + 1);
548 } else {
549 copy3 = NULL;
550 }
551 }
552
553 /*
554 * Shift the remainder of the probe sequence to the right
555 */
556 if (entry->hashValue != 0) {
557 const xmlHashEntry *end = &hash->table[hash->size];
558 const xmlHashEntry *cur = entry;
559
560 do {
561 cur++;
562 if (cur >= end)
563 cur = hash->table;
564 } while (cur->hashValue != 0);
565
566 if (cur < entry) {
567 /*
568 * If we traversed the end of the buffer, handle the part
569 * at the start of the buffer.
570 */
571 memmove(&hash->table[1], hash->table,
572 (char *) cur - (char *) hash->table);
573 cur = end - 1;
574 hash->table[0] = *cur;
575 }
576
577 memmove(&entry[1], entry, (char *) cur - (char *) entry);
578 }
579
580 /*
581 * Populate entry
582 */
583 entry->key = copy;
584 entry->key2 = copy2;
585 entry->key3 = copy3;
586 entry->payload = payload;
587 /* OR with MAX_HASH_SIZE to make sure that the value is non-zero */
588 entry->hashValue = hashValue | MAX_HASH_SIZE;
589
590 hash->nbElems++;
591
592 return(0);
593 }
594
595 /**
596 * xmlHashDefaultDeallocator:
597 * @entry: hash table entry
598 * @key: the entry's string key
599 *
600 * Free a hash table entry with xmlFree.
601 */
602 void
603 xmlHashDefaultDeallocator(void *entry, const xmlChar *key ATTRIBUTE_UNUSED) {
604 xmlFree(entry);
605 }
606
607 /**
608 * xmlHashAddEntry:
609 * @hash: hash table
610 * @key: string key
611 * @payload: pointer to the payload
612 *
613 * Add a hash table entry. If an entry with this key already exists,
614 * payload will not be updated and -1 is returned. This return value
615 * can't be distinguished from out-of-memory errors, so this function
616 * should be used with care.
617 *
618 * Returns 0 on success and -1 in case of error.
619 */
620 int
621 xmlHashAddEntry(xmlHashTablePtr hash, const xmlChar *key, void *payload) {
622 return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload, NULL, 0));
623 }
624
625 /**
626 * xmlHashAddEntry2:
627 * @hash: hash table
628 * @key: first string key
629 * @key2: second string key
630 * @payload: pointer to the payload
631 *
632 * Add a hash table entry with two strings as key.
633 *
634 * See xmlHashAddEntry.
635 *
636 * Returns 0 on success and -1 in case of error.
637 */
638 int
639 xmlHashAddEntry2(xmlHashTablePtr hash, const xmlChar *key,
640 const xmlChar *key2, void *payload) {
641 return(xmlHashUpdateInternal(hash, key, key2, NULL, payload, NULL, 0));
642 }
643
644 /**
645 * xmlHashAddEntry3:
646 * @hash: hash table
647 * @key: first string key
648 * @key2: second string key
649 * @key3: third string key
650 * @payload: pointer to the payload
651 *
652 * Add a hash table entry with three strings as key.
653 *
654 * See xmlHashAddEntry.
655 *
656 * Returns 0 on success and -1 in case of error.
657 */
658 int
659 xmlHashAddEntry3(xmlHashTablePtr hash, const xmlChar *key,
660 const xmlChar *key2, const xmlChar *key3,
661 void *payload) {
662 return(xmlHashUpdateInternal(hash, key, key2, key3, payload, NULL, 0));
663 }
664
665 /**
666 * xmlHashUpdateEntry:
667 * @hash: hash table
668 * @key: string key
669 * @payload: pointer to the payload
670 * @dealloc: deallocator function for replaced item or NULL
671 *
672 * Add a hash table entry. If an entry with this key already exists,
673 * the old payload will be freed and updated with the new value.
674 *
675 * Returns 0 in case of success, -1 if a memory allocation failed.
676 */
677 int
678 xmlHashUpdateEntry(xmlHashTablePtr hash, const xmlChar *key,
679 void *payload, xmlHashDeallocator dealloc) {
680 return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload,
681 dealloc, 1));
682 }
683
684 /**
685 * xmlHashUpdateEntry2:
686 * @hash: hash table
687 * @key: first string key
688 * @key2: second string key
689 * @payload: pointer to the payload
690 * @dealloc: deallocator function for replaced item or NULL
691 *
692 * Add a hash table entry with two strings as key.
693 *
694 * See xmlHashUpdateEntry.
695 *
696 * Returns 0 on success and -1 in case of error.
697 */
698 int
699 xmlHashUpdateEntry2(xmlHashTablePtr hash, const xmlChar *key,
700 const xmlChar *key2, void *payload,
701 xmlHashDeallocator dealloc) {
702 return(xmlHashUpdateInternal(hash, key, key2, NULL, payload,
703 dealloc, 1));
704 }
705
706 /**
707 * xmlHashUpdateEntry3:
708 * @hash: hash table
709 * @key: first string key
710 * @key2: second string key
711 * @key3: third string key
712 * @payload: pointer to the payload
713 * @dealloc: deallocator function for replaced item or NULL
714 *
715 * Add a hash table entry with three strings as key.
716 *
717 * See xmlHashUpdateEntry.
718 *
719 * Returns 0 on success and -1 in case of error.
720 */
721 int
722 xmlHashUpdateEntry3(xmlHashTablePtr hash, const xmlChar *key,
723 const xmlChar *key2, const xmlChar *key3,
724 void *payload, xmlHashDeallocator dealloc) {
725 return(xmlHashUpdateInternal(hash, key, key2, key3, payload,
726 dealloc, 1));
727 }
728
729 /**
730 * xmlHashLookup:
731 * @hash: hash table
732 * @key: string key
733 *
734 * Find the entry specified by @key.
735 *
736 * Returns a pointer to the payload or NULL if no entry was found.
737 */
738 void *
739 xmlHashLookup(xmlHashTablePtr hash, const xmlChar *key) {
740 return(xmlHashLookup3(hash, key, NULL, NULL));
741 }
742
743 /**
744 * xmlHashLookup2:
745 * @hash: hash table
746 * @key: first string key
747 * @key2: second string key
748 *
749 * Find the payload specified by the (@key, @key2) tuple.
750 *
751 * Returns a pointer to the payload or NULL if no entry was found.
752 */
753 void *
754 xmlHashLookup2(xmlHashTablePtr hash, const xmlChar *key,
755 const xmlChar *key2) {
756 return(xmlHashLookup3(hash, key, key2, NULL));
757 }
758
759 /**
760 * xmlHashQLookup:
761 * @hash: hash table
762 * @prefix: prefix of the string key
763 * @name: local name of the string key
764 *
765 * Find the payload specified by the QName @prefix:@name or @name.
766 *
767 * Returns a pointer to the payload or NULL if no entry was found.
768 */
769 void *
770 xmlHashQLookup(xmlHashTablePtr hash, const xmlChar *prefix,
771 const xmlChar *name) {
772 return(xmlHashQLookup3(hash, prefix, name, NULL, NULL, NULL, NULL));
773 }
774
775 /**
776 * xmlHashQLookup2:
777 * @hash: hash table
778 * @prefix: first prefix
779 * @name: first local name
780 * @prefix2: second prefix
781 * @name2: second local name
782 *
783 * Find the payload specified by the QNames tuple.
784 *
785 * Returns a pointer to the payload or NULL if no entry was found.
786 */
787 void *
788 xmlHashQLookup2(xmlHashTablePtr hash, const xmlChar *prefix,
789 const xmlChar *name, const xmlChar *prefix2,
790 const xmlChar *name2) {
791 return(xmlHashQLookup3(hash, prefix, name, prefix2, name2, NULL, NULL));
792 }
793
794 /**
795 * xmlHashLookup3:
796 * @hash: hash table
797 * @key: first string key
798 * @key2: second string key
799 * @key3: third string key
800 *
801 * Find the payload specified by the (@key, @key2, @key3) tuple.
802 *
803 * Returns a pointer to the payload or NULL if no entry was found.
804 */
805 void *
806 xmlHashLookup3(xmlHashTablePtr hash, const xmlChar *key,
807 const xmlChar *key2, const xmlChar *key3) {
808 const xmlHashEntry *entry;
809 unsigned hashValue;
810 int found;
811
812 if ((hash == NULL) || (hash->size == 0) || (key == NULL))
813 return(NULL);
814 hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, NULL);
815 entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found);
816 if (found)
817 return(entry->payload);
818 return(NULL);
819 }
820
821 /**
822 * xmlHashQLookup3:
823 * @hash: hash table
824 * @prefix: first prefix
825 * @name: first local name
826 * @prefix2: second prefix
827 * @name2: second local name
828 * @prefix3: third prefix
829 * @name3: third local name
830 *
831 * Find the payload specified by the QNames tuple.
832 *
833 * Returns a pointer to the payload or NULL if no entry was found.
834 */
835 ATTRIBUTE_NO_SANITIZE_INTEGER
836 void *
837 xmlHashQLookup3(xmlHashTablePtr hash,
838 const xmlChar *prefix, const xmlChar *name,
839 const xmlChar *prefix2, const xmlChar *name2,
840 const xmlChar *prefix3, const xmlChar *name3) {
841 const xmlHashEntry *entry;
842 unsigned hashValue, mask, pos, displ;
843
844 if ((hash == NULL) || (hash->size == 0) || (name == NULL))
845 return(NULL);
846
847 hashValue = xmlHashQNameValue(hash->randomSeed, prefix, name, prefix2,
848 name2, prefix3, name3);
849 mask = hash->size - 1;
850 pos = hashValue & mask;
851 entry = &hash->table[pos];
852
853 if (entry->hashValue != 0) {
854 displ = 0;
855 hashValue |= MAX_HASH_SIZE;
856
857 do {
858 if ((hashValue == entry->hashValue) &&
859 (xmlStrQEqual(prefix, name, entry->key)) &&
860 (xmlStrQEqual(prefix2, name2, entry->key2)) &&
861 (xmlStrQEqual(prefix3, name3, entry->key3)))
862 return(entry->payload);
863
864 displ++;
865 pos++;
866 entry++;
867 if ((pos & mask) == 0)
868 entry = hash->table;
869 } while ((entry->hashValue != 0) &&
870 (((pos - entry->hashValue) & mask) >= displ));
871 }
872
873 return(NULL);
874 }
875
876 typedef struct {
877 xmlHashScanner scan;
878 void *data;
879 } stubData;
880
881 static void
882 stubHashScannerFull(void *payload, void *data, const xmlChar *key,
883 const xmlChar *key2 ATTRIBUTE_UNUSED,
884 const xmlChar *key3 ATTRIBUTE_UNUSED) {
885 stubData *sdata = (stubData *) data;
886 sdata->scan(payload, sdata->data, key);
887 }
888
889 /**
890 * xmlHashScan:
891 * @hash: hash table
892 * @scan: scanner function for items in the hash
893 * @data: extra data passed to @scan
894 *
895 * Scan the hash @table and apply @scan to each value.
896 */
897 void
898 xmlHashScan(xmlHashTablePtr hash, xmlHashScanner scan, void *data) {
899 stubData sdata;
900 sdata.data = data;
901 sdata.scan = scan;
902 xmlHashScanFull(hash, stubHashScannerFull, &sdata);
903 }
904
905 /**
906 * xmlHashScanFull:
907 * @hash: hash table
908 * @scan: scanner function for items in the hash
909 * @data: extra data passed to @scan
910 *
911 * Scan the hash @table and apply @scan to each value.
912 */
913 void
914 xmlHashScanFull(xmlHashTablePtr hash, xmlHashScannerFull scan, void *data) {
915 const xmlHashEntry *entry, *end;
916 xmlHashEntry old;
917 unsigned i;
918
919 if ((hash == NULL) || (hash->size == 0) || (scan == NULL))
920 return;
921
922 /*
923 * We must handle the case that a scanned entry is removed when executing
924 * the callback (xmlCleanSpecialAttr and possibly other places).
925 *
926 * Find the start of a probe sequence to avoid scanning entries twice if
927 * a deletion happens.
928 */
929 entry = hash->table;
930 end = &hash->table[hash->size];
931 while (entry->hashValue != 0) {
932 if (++entry >= end)
933 entry = hash->table;
934 }
935
936 for (i = 0; i < hash->size; i++) {
937 if ((entry->hashValue != 0) && (entry->payload != NULL)) {
938 /*
939 * Make sure to rescan after a possible deletion.
940 */
941 do {
942 old = *entry;
943 scan(entry->payload, data, entry->key, entry->key2, entry->key3);
944 } while ((entry->hashValue != 0) &&
945 (entry->payload != NULL) &&
946 ((entry->key != old.key) ||
947 (entry->key2 != old.key2) ||
948 (entry->key3 != old.key3)));
949 }
950 if (++entry >= end)
951 entry = hash->table;
952 }
953 }
954
955 /**
956 * xmlHashScan3:
957 * @hash: hash table
958 * @key: first string key or NULL
959 * @key2: second string key or NULL
960 * @key3: third string key or NULL
961 * @scan: scanner function for items in the hash
962 * @data: extra data passed to @scan
963 *
964 * Scan the hash @table and apply @scan to each value matching
965 * (@key, @key2, @key3) tuple. If one of the keys is null,
966 * the comparison is considered to match.
967 */
968 void
969 xmlHashScan3(xmlHashTablePtr hash, const xmlChar *key,
970 const xmlChar *key2, const xmlChar *key3,
971 xmlHashScanner scan, void *data) {
972 stubData sdata;
973 sdata.data = data;
974 sdata.scan = scan;
975 xmlHashScanFull3(hash, key, key2, key3, stubHashScannerFull, &sdata);
976 }
977
978 /**
979 * xmlHashScanFull3:
980 * @hash: hash table
981 * @key: first string key or NULL
982 * @key2: second string key or NULL
983 * @key3: third string key or NULL
984 * @scan: scanner function for items in the hash
985 * @data: extra data passed to @scan
986 *
987 * Scan the hash @table and apply @scan to each value matching
988 * (@key, @key2, @key3) tuple. If one of the keys is null,
989 * the comparison is considered to match.
990 */
991 void
992 xmlHashScanFull3(xmlHashTablePtr hash, const xmlChar *key,
993 const xmlChar *key2, const xmlChar *key3,
994 xmlHashScannerFull scan, void *data) {
995 const xmlHashEntry *entry, *end;
996 xmlHashEntry old;
997 unsigned i;
998
999 if ((hash == NULL) || (hash->size == 0) || (scan == NULL))
1000 return;
1001
1002 /*
1003 * We must handle the case that a scanned entry is removed when executing
1004 * the callback (xmlCleanSpecialAttr and possibly other places).
1005 *
1006 * Find the start of a probe sequence to avoid scanning entries twice if
1007 * a deletion happens.
1008 */
1009 entry = hash->table;
1010 end = &hash->table[hash->size];
1011 while (entry->hashValue != 0) {
1012 if (++entry >= end)
1013 entry = hash->table;
1014 }
1015
1016 for (i = 0; i < hash->size; i++) {
1017 if ((entry->hashValue != 0) && (entry->payload != NULL)) {
1018 /*
1019 * Make sure to rescan after a possible deletion.
1020 */
1021 do {
1022 if (((key != NULL) && (strcmp((const char *) key,
1023 (const char *) entry->key) != 0)) ||
1024 ((key2 != NULL) && (!xmlFastStrEqual(key2, entry->key2))) ||
1025 ((key3 != NULL) && (!xmlFastStrEqual(key3, entry->key3))))
1026 break;
1027 old = *entry;
1028 scan(entry->payload, data, entry->key, entry->key2, entry->key3);
1029 } while ((entry->hashValue != 0) &&
1030 (entry->payload != NULL) &&
1031 ((entry->key != old.key) ||
1032 (entry->key2 != old.key2) ||
1033 (entry->key3 != old.key3)));
1034 }
1035 if (++entry >= end)
1036 entry = hash->table;
1037 }
1038 }
1039
1040 /**
1041 * xmlHashCopy:
1042 * @hash: hash table
1043 * @copy: copier function for items in the hash
1044 *
1045 * Copy the hash @table using @copy to copy payloads.
1046 *
1047 * Returns the new table or NULL if a memory allocation failed.
1048 */
1049 xmlHashTablePtr
1050 xmlHashCopy(xmlHashTablePtr hash, xmlHashCopier copy) {
1051 const xmlHashEntry *entry, *end;
1052 xmlHashTablePtr ret;
1053
1054 if ((hash == NULL) || (copy == NULL))
1055 return(NULL);
1056
1057 ret = xmlHashCreate(hash->size);
1058 if (ret == NULL)
1059 return(NULL);
1060
1061 if (hash->size == 0)
1062 return(ret);
1063
1064 end = &hash->table[hash->size];
1065
1066 for (entry = hash->table; entry < end; entry++) {
1067 if (entry->hashValue != 0)
1068 xmlHashAddEntry3(ret, entry->key, entry->key2, entry->key3,
1069 copy(entry->payload, entry->key));
1070 }
1071
1072 return(ret);
1073 }
1074
1075 /**
1076 * xmlHashSize:
1077 * @hash: hash table
1078 *
1079 * Query the number of elements in the hash table.
1080 *
1081 * Returns the number of elements in the hash table or
1082 * -1 in case of error.
1083 */
1084 int
1085 xmlHashSize(xmlHashTablePtr hash) {
1086 if (hash == NULL)
1087 return(-1);
1088 return(hash->nbElems);
1089 }
1090
1091 /**
1092 * xmlHashRemoveEntry:
1093 * @hash: hash table
1094 * @key: string key
1095 * @dealloc: deallocator function for removed item or NULL
1096 *
1097 * Find the entry specified by the @key and remove it from the hash table.
1098 * Payload will be freed with @dealloc.
1099 *
1100 * Returns 0 on success and -1 if no entry was found.
1101 */
1102 int xmlHashRemoveEntry(xmlHashTablePtr hash, const xmlChar *key,
1103 xmlHashDeallocator dealloc) {
1104 return(xmlHashRemoveEntry3(hash, key, NULL, NULL, dealloc));
1105 }
1106
1107 /**
1108 * xmlHashRemoveEntry2:
1109 * @hash: hash table
1110 * @key: first string key
1111 * @key2: second string key
1112 * @dealloc: deallocator function for removed item or NULL
1113 *
1114 * Remove an entry with two strings as key.
1115 *
1116 * See xmlHashRemoveEntry.
1117 *
1118 * Returns 0 on success and -1 in case of error.
1119 */
1120 int
1121 xmlHashRemoveEntry2(xmlHashTablePtr hash, const xmlChar *key,
1122 const xmlChar *key2, xmlHashDeallocator dealloc) {
1123 return(xmlHashRemoveEntry3(hash, key, key2, NULL, dealloc));
1124 }
1125
1126 /**
1127 * xmlHashRemoveEntry3:
1128 * @hash: hash table
1129 * @key: first string key
1130 * @key2: second string key
1131 * @key3: third string key
1132 * @dealloc: deallocator function for removed item or NULL
1133 *
1134 * Remove an entry with three strings as key.
1135 *
1136 * See xmlHashRemoveEntry.
1137 *
1138 * Returns 0 on success and -1 in case of error.
1139 */
1140 ATTRIBUTE_NO_SANITIZE_INTEGER
1141 int
1142 xmlHashRemoveEntry3(xmlHashTablePtr hash, const xmlChar *key,
1143 const xmlChar *key2, const xmlChar *key3,
1144 xmlHashDeallocator dealloc) {
1145 xmlHashEntry *entry, *cur, *next;
1146 unsigned hashValue, mask, pos, nextpos;
1147 int found;
1148
1149 if ((hash == NULL) || (hash->size == 0) || (key == NULL))
1150 return(-1);
1151
1152 hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, NULL);
1153 entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found);
1154 if (!found)
1155 return(-1);
1156
1157 if ((dealloc != NULL) && (entry->payload != NULL))
1158 dealloc(entry->payload, entry->key);
1159 if (hash->dict == NULL) {
1160 if (entry->key)
1161 xmlFree(entry->key);
1162 if (entry->key2)
1163 xmlFree(entry->key2);
1164 if (entry->key3)
1165 xmlFree(entry->key3);
1166 }
1167
1168 /*
1169 * Find end of probe sequence. Entries at their initial probe
1170 * position start a new sequence.
1171 */
1172 mask = hash->size - 1;
1173 pos = entry - hash->table;
1174 cur = entry;
1175
1176 while (1) {
1177 nextpos = pos + 1;
1178 next = cur + 1;
1179 if ((nextpos & mask) == 0)
1180 next = hash->table;
1181
1182 if ((next->hashValue == 0) ||
1183 (((next->hashValue - nextpos) & mask) == 0))
1184 break;
1185
1186 cur = next;
1187 pos = nextpos;
1188 }
1189
1190 /*
1191 * Backward shift
1192 */
1193 next = entry + 1;
1194
1195 if (cur < entry) {
1196 xmlHashEntry *end = &hash->table[hash->size];
1197
1198 memmove(entry, next, (char *) end - (char *) next);
1199 entry = hash->table;
1200 end[-1] = *entry;
1201 next = entry + 1;
1202 }
1203
1204 memmove(entry, next, (char *) cur - (char *) entry);
1205
1206 /*
1207 * Update entry
1208 */
1209 cur->hashValue = 0;
1210
1211 hash->nbElems--;
1212
1213 return(0);
1214 }
1215