2 * hash.c: chained hash tables
4 * Reference: Your favorite introductory book on algorithms
6 * Copyright (C) 2000,2012 Bjorn Reese and Daniel Veillard.
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.
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.
17 * Author: breese@users.sourceforge.net
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
36 #if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME)
37 #define HASH_RANDOMIZATION
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>
46 #define MAX_HASH_LEN 8
48 /* #define DEBUG_GROW */
51 * A single entry in the hash table
53 typedef struct _xmlHashEntry xmlHashEntry
;
54 typedef xmlHashEntry
*xmlHashEntryPtr
;
55 struct _xmlHashEntry
{
56 struct _xmlHashEntry
*next
;
65 * The entire hash table
67 struct _xmlHashTable
{
68 struct _xmlHashEntry
*table
;
72 #ifdef HASH_RANDOMIZATION
79 * Calculate the hash key
82 xmlHashComputeKey(xmlHashTablePtr table
, const xmlChar
*name
,
83 const xmlChar
*name2
, const xmlChar
*name3
) {
84 unsigned long value
= 0L;
87 #ifdef HASH_RANDOMIZATION
88 value
= table
->random_seed
;
91 value
+= 30 * (*name
);
92 while ((ch
= *name
++) != 0) {
93 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)ch
);
97 while ((ch
= *name2
++) != 0) {
98 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)ch
);
102 while ((ch
= *name3
++) != 0) {
103 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)ch
);
106 return (value
% table
->size
);
110 xmlHashComputeQKey(xmlHashTablePtr table
,
111 const xmlChar
*prefix
, const xmlChar
*name
,
112 const xmlChar
*prefix2
, const xmlChar
*name2
,
113 const xmlChar
*prefix3
, const xmlChar
*name3
) {
114 unsigned long value
= 0L;
117 #ifdef HASH_RANDOMIZATION
118 value
= table
->random_seed
;
121 value
+= 30 * (*prefix
);
123 value
+= 30 * (*name
);
125 if (prefix
!= NULL
) {
126 while ((ch
= *prefix
++) != 0) {
127 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)ch
);
129 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)':');
132 while ((ch
= *name
++) != 0) {
133 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)ch
);
136 if (prefix2
!= NULL
) {
137 while ((ch
= *prefix2
++) != 0) {
138 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)ch
);
140 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)':');
143 while ((ch
= *name2
++) != 0) {
144 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)ch
);
147 if (prefix3
!= NULL
) {
148 while ((ch
= *prefix3
++) != 0) {
149 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)ch
);
151 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)':');
154 while ((ch
= *name3
++) != 0) {
155 value
= value
^ ((value
<< 5) + (value
>> 3) + (unsigned long)ch
);
158 return (value
% table
->size
);
163 * @size: the size of the hash table
165 * Create a new xmlHashTablePtr.
167 * Returns the newly created object, or NULL if an error occured.
170 xmlHashCreate(int size
) {
171 xmlHashTablePtr table
;
176 table
= xmlMalloc(sizeof(xmlHashTable
));
181 table
->table
= xmlMalloc(size
* sizeof(xmlHashEntry
));
183 memset(table
->table
, 0, size
* sizeof(xmlHashEntry
));
184 #ifdef HASH_RANDOMIZATION
185 table
->random_seed
= __xmlRandom();
196 * @size: the size of the hash table
197 * @dict: a dictionary to use for the hash
199 * Create a new xmlHashTablePtr which will use @dict as the internal dictionary
201 * Returns the newly created object, or NULL if an error occured.
204 xmlHashCreateDict(int size
, xmlDictPtr dict
) {
205 xmlHashTablePtr table
;
207 table
= xmlHashCreate(size
);
210 xmlDictReference(dict
);
217 * @table: the hash table
218 * @size: the new size of the hash table
220 * resize the hash table
222 * Returns 0 in case of success, -1 in case of failure
225 xmlHashGrow(xmlHashTablePtr table
, int size
) {
228 xmlHashEntryPtr iter
, next
;
229 struct _xmlHashEntry
*oldtable
;
231 unsigned long nbElem
= 0;
241 oldsize
= table
->size
;
242 oldtable
= table
->table
;
243 if (oldtable
== NULL
)
246 table
->table
= xmlMalloc(size
* sizeof(xmlHashEntry
));
247 if (table
->table
== NULL
) {
248 table
->table
= oldtable
;
251 memset(table
->table
, 0, size
* sizeof(xmlHashEntry
));
254 /* If the two loops are merged, there would be situations where
255 a new entry needs to allocated and data copied into it from
256 the main table. So instead, we run through the array twice, first
257 copying all the elements in the main array (where we can't get
258 conflicts) and then the rest, so we only free (and don't allocate)
260 for (i
= 0; i
< oldsize
; i
++) {
261 if (oldtable
[i
].valid
== 0)
263 key
= xmlHashComputeKey(table
, oldtable
[i
].name
, oldtable
[i
].name2
,
265 memcpy(&(table
->table
[key
]), &(oldtable
[i
]), sizeof(xmlHashEntry
));
266 table
->table
[key
].next
= NULL
;
269 for (i
= 0; i
< oldsize
; i
++) {
270 iter
= oldtable
[i
].next
;
275 * put back the entry in the new table
278 key
= xmlHashComputeKey(table
, iter
->name
, iter
->name2
,
280 if (table
->table
[key
].valid
== 0) {
281 memcpy(&(table
->table
[key
]), iter
, sizeof(xmlHashEntry
));
282 table
->table
[key
].next
= NULL
;
285 iter
->next
= table
->table
[key
].next
;
286 table
->table
[key
].next
= iter
;
300 xmlGenericError(xmlGenericErrorContext
,
301 "xmlHashGrow : from %d to %d, %d elems\n", oldsize
, size
, nbElem
);
309 * @table: the hash table
310 * @f: the deallocator function for items in the hash
312 * Free the hash @table and its contents. The userdata is
313 * deallocated with @f if provided.
316 xmlHashFree(xmlHashTablePtr table
, xmlHashDeallocator f
) {
318 xmlHashEntryPtr iter
;
319 xmlHashEntryPtr next
;
320 int inside_table
= 0;
326 nbElems
= table
->nbElems
;
327 for(i
= 0; (i
< table
->size
) && (nbElems
> 0); i
++) {
328 iter
= &(table
->table
[i
]);
329 if (iter
->valid
== 0)
334 if ((f
!= NULL
) && (iter
->payload
!= NULL
))
335 f(iter
->payload
, iter
->name
);
336 if (table
->dict
== NULL
) {
340 xmlFree(iter
->name2
);
342 xmlFree(iter
->name3
);
344 iter
->payload
= NULL
;
352 xmlFree(table
->table
);
355 xmlDictFree(table
->dict
);
361 * @table: the hash table
362 * @name: the name of the userdata
363 * @userdata: a pointer to the userdata
365 * Add the @userdata to the hash @table. This can later be retrieved
366 * by using the @name. Duplicate names generate errors.
368 * Returns 0 the addition succeeded and -1 in case of error.
371 xmlHashAddEntry(xmlHashTablePtr table
, const xmlChar
*name
, void *userdata
) {
372 return(xmlHashAddEntry3(table
, name
, NULL
, NULL
, userdata
));
377 * @table: the hash table
378 * @name: the name of the userdata
379 * @name2: a second name of the userdata
380 * @userdata: a pointer to the userdata
382 * Add the @userdata to the hash @table. This can later be retrieved
383 * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
385 * Returns 0 the addition succeeded and -1 in case of error.
388 xmlHashAddEntry2(xmlHashTablePtr table
, const xmlChar
*name
,
389 const xmlChar
*name2
, void *userdata
) {
390 return(xmlHashAddEntry3(table
, name
, name2
, NULL
, userdata
));
394 * xmlHashUpdateEntry:
395 * @table: the hash table
396 * @name: the name of the userdata
397 * @userdata: a pointer to the userdata
398 * @f: the deallocator function for replaced item (if any)
400 * Add the @userdata to the hash @table. This can later be retrieved
401 * by using the @name. Existing entry for this @name will be removed
402 * and freed with @f if found.
404 * Returns 0 the addition succeeded and -1 in case of error.
407 xmlHashUpdateEntry(xmlHashTablePtr table
, const xmlChar
*name
,
408 void *userdata
, xmlHashDeallocator f
) {
409 return(xmlHashUpdateEntry3(table
, name
, NULL
, NULL
, userdata
, f
));
413 * xmlHashUpdateEntry2:
414 * @table: the hash table
415 * @name: the name of the userdata
416 * @name2: a second name of the userdata
417 * @userdata: a pointer to the userdata
418 * @f: the deallocator function for replaced item (if any)
420 * Add the @userdata to the hash @table. This can later be retrieved
421 * by using the (@name, @name2) tuple. Existing entry for this tuple will
422 * be removed and freed with @f if found.
424 * Returns 0 the addition succeeded and -1 in case of error.
427 xmlHashUpdateEntry2(xmlHashTablePtr table
, const xmlChar
*name
,
428 const xmlChar
*name2
, void *userdata
,
429 xmlHashDeallocator f
) {
430 return(xmlHashUpdateEntry3(table
, name
, name2
, NULL
, userdata
, f
));
435 * @table: the hash table
436 * @name: the name of the userdata
438 * Find the userdata specified by the @name.
440 * Returns the pointer to the userdata
443 xmlHashLookup(xmlHashTablePtr table
, const xmlChar
*name
) {
444 return(xmlHashLookup3(table
, name
, NULL
, NULL
));
449 * @table: the hash table
450 * @name: the name of the userdata
451 * @name2: a second name of the userdata
453 * Find the userdata specified by the (@name, @name2) tuple.
455 * Returns the pointer to the userdata
458 xmlHashLookup2(xmlHashTablePtr table
, const xmlChar
*name
,
459 const xmlChar
*name2
) {
460 return(xmlHashLookup3(table
, name
, name2
, NULL
));
465 * @table: the hash table
466 * @prefix: the prefix of the userdata
467 * @name: the name of the userdata
469 * Find the userdata specified by the QName @prefix:@name/@name.
471 * Returns the pointer to the userdata
474 xmlHashQLookup(xmlHashTablePtr table
, const xmlChar
*prefix
,
475 const xmlChar
*name
) {
476 return(xmlHashQLookup3(table
, prefix
, name
, NULL
, NULL
, NULL
, NULL
));
481 * @table: the hash table
482 * @prefix: the prefix of the userdata
483 * @name: the name of the userdata
484 * @prefix2: the second prefix of the userdata
485 * @name2: a second name of the userdata
487 * Find the userdata specified by the QNames tuple
489 * Returns the pointer to the userdata
492 xmlHashQLookup2(xmlHashTablePtr table
, const xmlChar
*prefix
,
493 const xmlChar
*name
, const xmlChar
*prefix2
,
494 const xmlChar
*name2
) {
495 return(xmlHashQLookup3(table
, prefix
, name
, prefix2
, name2
, NULL
, NULL
));
500 * @table: the hash table
501 * @name: the name of the userdata
502 * @name2: a second name of the userdata
503 * @name3: a third name of the userdata
504 * @userdata: a pointer to the userdata
506 * Add the @userdata to the hash @table. This can later be retrieved
507 * by using the tuple (@name, @name2, @name3). Duplicate entries generate
510 * Returns 0 the addition succeeded and -1 in case of error.
513 xmlHashAddEntry3(xmlHashTablePtr table
, const xmlChar
*name
,
514 const xmlChar
*name2
, const xmlChar
*name3
,
516 unsigned long key
, len
= 0;
517 xmlHashEntryPtr entry
;
518 xmlHashEntryPtr insert
;
520 if ((table
== NULL
) || (name
== NULL
))
524 * If using a dict internalize if needed
527 if (!xmlDictOwns(table
->dict
, name
)) {
528 name
= xmlDictLookup(table
->dict
, name
, -1);
532 if ((name2
!= NULL
) && (!xmlDictOwns(table
->dict
, name2
))) {
533 name2
= xmlDictLookup(table
->dict
, name2
, -1);
537 if ((name3
!= NULL
) && (!xmlDictOwns(table
->dict
, name3
))) {
538 name3
= xmlDictLookup(table
->dict
, name3
, -1);
545 * Check for duplicate and insertion location.
547 key
= xmlHashComputeKey(table
, name
, name2
, name3
);
548 if (table
->table
[key
].valid
== 0) {
552 for (insert
= &(table
->table
[key
]); insert
->next
!= NULL
;
553 insert
= insert
->next
) {
554 if ((insert
->name
== name
) &&
555 (insert
->name2
== name2
) &&
556 (insert
->name3
== name3
))
560 if ((insert
->name
== name
) &&
561 (insert
->name2
== name2
) &&
562 (insert
->name3
== name3
))
565 for (insert
= &(table
->table
[key
]); insert
->next
!= NULL
;
566 insert
= insert
->next
) {
567 if ((xmlStrEqual(insert
->name
, name
)) &&
568 (xmlStrEqual(insert
->name2
, name2
)) &&
569 (xmlStrEqual(insert
->name3
, name3
)))
573 if ((xmlStrEqual(insert
->name
, name
)) &&
574 (xmlStrEqual(insert
->name2
, name2
)) &&
575 (xmlStrEqual(insert
->name3
, name3
)))
580 if (insert
== NULL
) {
581 entry
= &(table
->table
[key
]);
583 entry
= xmlMalloc(sizeof(xmlHashEntry
));
588 if (table
->dict
!= NULL
) {
589 entry
->name
= (xmlChar
*) name
;
590 entry
->name2
= (xmlChar
*) name2
;
591 entry
->name3
= (xmlChar
*) name3
;
593 entry
->name
= xmlStrdup(name
);
594 entry
->name2
= xmlStrdup(name2
);
595 entry
->name3
= xmlStrdup(name3
);
597 entry
->payload
= userdata
;
603 insert
->next
= entry
;
607 if (len
> MAX_HASH_LEN
)
608 xmlHashGrow(table
, MAX_HASH_LEN
* table
->size
);
614 * xmlHashUpdateEntry3:
615 * @table: the hash table
616 * @name: the name of the userdata
617 * @name2: a second name of the userdata
618 * @name3: a third name of the userdata
619 * @userdata: a pointer to the userdata
620 * @f: the deallocator function for replaced item (if any)
622 * Add the @userdata to the hash @table. This can later be retrieved
623 * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
624 * will be removed and freed with @f if found.
626 * Returns 0 the addition succeeded and -1 in case of error.
629 xmlHashUpdateEntry3(xmlHashTablePtr table
, const xmlChar
*name
,
630 const xmlChar
*name2
, const xmlChar
*name3
,
631 void *userdata
, xmlHashDeallocator f
) {
633 xmlHashEntryPtr entry
;
634 xmlHashEntryPtr insert
;
636 if ((table
== NULL
) || name
== NULL
)
640 * If using a dict internalize if needed
643 if (!xmlDictOwns(table
->dict
, name
)) {
644 name
= xmlDictLookup(table
->dict
, name
, -1);
648 if ((name2
!= NULL
) && (!xmlDictOwns(table
->dict
, name2
))) {
649 name2
= xmlDictLookup(table
->dict
, name2
, -1);
653 if ((name3
!= NULL
) && (!xmlDictOwns(table
->dict
, name3
))) {
654 name3
= xmlDictLookup(table
->dict
, name3
, -1);
661 * Check for duplicate and insertion location.
663 key
= xmlHashComputeKey(table
, name
, name2
, name3
);
664 if (table
->table
[key
].valid
== 0) {
668 for (insert
= &(table
->table
[key
]); insert
->next
!= NULL
;
669 insert
= insert
->next
) {
670 if ((insert
->name
== name
) &&
671 (insert
->name2
== name2
) &&
672 (insert
->name3
== name3
)) {
674 f(insert
->payload
, insert
->name
);
675 insert
->payload
= userdata
;
679 if ((insert
->name
== name
) &&
680 (insert
->name2
== name2
) &&
681 (insert
->name3
== name3
)) {
683 f(insert
->payload
, insert
->name
);
684 insert
->payload
= userdata
;
688 for (insert
= &(table
->table
[key
]); insert
->next
!= NULL
;
689 insert
= insert
->next
) {
690 if ((xmlStrEqual(insert
->name
, name
)) &&
691 (xmlStrEqual(insert
->name2
, name2
)) &&
692 (xmlStrEqual(insert
->name3
, name3
))) {
694 f(insert
->payload
, insert
->name
);
695 insert
->payload
= userdata
;
699 if ((xmlStrEqual(insert
->name
, name
)) &&
700 (xmlStrEqual(insert
->name2
, name2
)) &&
701 (xmlStrEqual(insert
->name3
, name3
))) {
703 f(insert
->payload
, insert
->name
);
704 insert
->payload
= userdata
;
710 if (insert
== NULL
) {
711 entry
= &(table
->table
[key
]);
713 entry
= xmlMalloc(sizeof(xmlHashEntry
));
718 if (table
->dict
!= NULL
) {
719 entry
->name
= (xmlChar
*) name
;
720 entry
->name2
= (xmlChar
*) name2
;
721 entry
->name3
= (xmlChar
*) name3
;
723 entry
->name
= xmlStrdup(name
);
724 entry
->name2
= xmlStrdup(name2
);
725 entry
->name3
= xmlStrdup(name3
);
727 entry
->payload
= userdata
;
733 if (insert
!= NULL
) {
734 insert
->next
= entry
;
741 * @table: the hash table
742 * @name: the name of the userdata
743 * @name2: a second name of the userdata
744 * @name3: a third name of the userdata
746 * Find the userdata specified by the (@name, @name2, @name3) tuple.
748 * Returns the a pointer to the userdata
751 xmlHashLookup3(xmlHashTablePtr table
, const xmlChar
*name
,
752 const xmlChar
*name2
, const xmlChar
*name3
) {
754 xmlHashEntryPtr entry
;
760 key
= xmlHashComputeKey(table
, name
, name2
, name3
);
761 if (table
->table
[key
].valid
== 0)
764 for (entry
= &(table
->table
[key
]); entry
!= NULL
; entry
= entry
->next
) {
765 if ((entry
->name
== name
) &&
766 (entry
->name2
== name2
) &&
767 (entry
->name3
== name3
))
768 return(entry
->payload
);
771 for (entry
= &(table
->table
[key
]); entry
!= NULL
; entry
= entry
->next
) {
772 if ((xmlStrEqual(entry
->name
, name
)) &&
773 (xmlStrEqual(entry
->name2
, name2
)) &&
774 (xmlStrEqual(entry
->name3
, name3
)))
775 return(entry
->payload
);
782 * @table: the hash table
783 * @prefix: the prefix of the userdata
784 * @name: the name of the userdata
785 * @prefix2: the second prefix of the userdata
786 * @name2: a second name of the userdata
787 * @prefix3: the third prefix of the userdata
788 * @name3: a third name of the userdata
790 * Find the userdata specified by the (@name, @name2, @name3) tuple.
792 * Returns the a pointer to the userdata
795 xmlHashQLookup3(xmlHashTablePtr table
,
796 const xmlChar
*prefix
, const xmlChar
*name
,
797 const xmlChar
*prefix2
, const xmlChar
*name2
,
798 const xmlChar
*prefix3
, const xmlChar
*name3
) {
800 xmlHashEntryPtr entry
;
806 key
= xmlHashComputeQKey(table
, prefix
, name
, prefix2
,
807 name2
, prefix3
, name3
);
808 if (table
->table
[key
].valid
== 0)
810 for (entry
= &(table
->table
[key
]); entry
!= NULL
; entry
= entry
->next
) {
811 if ((xmlStrQEqual(prefix
, name
, entry
->name
)) &&
812 (xmlStrQEqual(prefix2
, name2
, entry
->name2
)) &&
813 (xmlStrQEqual(prefix3
, name3
, entry
->name3
)))
814 return(entry
->payload
);
820 xmlHashScanner hashscanner
;
825 stubHashScannerFull (void *payload
, void *data
, const xmlChar
*name
,
826 const xmlChar
*name2 ATTRIBUTE_UNUSED
,
827 const xmlChar
*name3 ATTRIBUTE_UNUSED
) {
828 stubData
*stubdata
= (stubData
*) data
;
829 stubdata
->hashscanner (payload
, stubdata
->data
, (xmlChar
*) name
);
834 * @table: the hash table
835 * @f: the scanner function for items in the hash
836 * @data: extra data passed to f
838 * Scan the hash @table and applied @f to each value.
841 xmlHashScan(xmlHashTablePtr table
, xmlHashScanner f
, void *data
) {
843 stubdata
.data
= data
;
844 stubdata
.hashscanner
= f
;
845 xmlHashScanFull (table
, stubHashScannerFull
, &stubdata
);
850 * @table: the hash table
851 * @f: the scanner function for items in the hash
852 * @data: extra data passed to f
854 * Scan the hash @table and applied @f to each value.
857 xmlHashScanFull(xmlHashTablePtr table
, xmlHashScannerFull f
, void *data
) {
859 xmlHashEntryPtr iter
;
860 xmlHashEntryPtr next
;
868 for(i
= 0; i
< table
->size
; i
++) {
869 if (table
->table
[i
].valid
== 0)
871 iter
= &(table
->table
[i
]);
875 if ((f
!= NULL
) && (iter
->payload
!= NULL
))
876 f(iter
->payload
, data
, iter
->name
,
877 iter
->name2
, iter
->name3
);
878 if (nb
!= table
->nbElems
) {
879 /* table was modified by the callback, be careful */
880 if (iter
== &(table
->table
[i
])) {
881 if (table
->table
[i
].valid
== 0)
883 if (table
->table
[i
].next
!= next
)
884 iter
= &(table
->table
[i
]);
896 * @table: the hash table
897 * @name: the name of the userdata or NULL
898 * @name2: a second name of the userdata or NULL
899 * @name3: a third name of the userdata or NULL
900 * @f: the scanner function for items in the hash
901 * @data: extra data passed to f
903 * Scan the hash @table and applied @f to each value matching
904 * (@name, @name2, @name3) tuple. If one of the names is null,
905 * the comparison is considered to match.
908 xmlHashScan3(xmlHashTablePtr table
, const xmlChar
*name
,
909 const xmlChar
*name2
, const xmlChar
*name3
,
910 xmlHashScanner f
, void *data
) {
911 xmlHashScanFull3 (table
, name
, name2
, name3
,
912 (xmlHashScannerFull
) f
, data
);
917 * @table: the hash table
918 * @name: the name of the userdata or NULL
919 * @name2: a second name of the userdata or NULL
920 * @name3: a third name of the userdata or NULL
921 * @f: the scanner function for items in the hash
922 * @data: extra data passed to f
924 * Scan the hash @table and applied @f to each value matching
925 * (@name, @name2, @name3) tuple. If one of the names is null,
926 * the comparison is considered to match.
929 xmlHashScanFull3(xmlHashTablePtr table
, const xmlChar
*name
,
930 const xmlChar
*name2
, const xmlChar
*name3
,
931 xmlHashScannerFull f
, void *data
) {
933 xmlHashEntryPtr iter
;
934 xmlHashEntryPtr next
;
942 for(i
= 0; i
< table
->size
; i
++) {
943 if (table
->table
[i
].valid
== 0)
945 iter
= &(table
->table
[i
]);
948 if (((name
== NULL
) || (xmlStrEqual(name
, iter
->name
))) &&
949 ((name2
== NULL
) || (xmlStrEqual(name2
, iter
->name2
))) &&
950 ((name3
== NULL
) || (xmlStrEqual(name3
, iter
->name3
))) &&
951 (iter
->payload
!= NULL
)) {
952 f(iter
->payload
, data
, iter
->name
,
953 iter
->name2
, iter
->name3
);
963 * @table: the hash table
964 * @f: the copier function for items in the hash
966 * Scan the hash @table and applied @f to each value.
968 * Returns the new table or NULL in case of error.
971 xmlHashCopy(xmlHashTablePtr table
, xmlHashCopier f
) {
973 xmlHashEntryPtr iter
;
974 xmlHashEntryPtr next
;
982 ret
= xmlHashCreate(table
->size
);
984 for(i
= 0; i
< table
->size
; i
++) {
985 if (table
->table
[i
].valid
== 0)
987 iter
= &(table
->table
[i
]);
990 xmlHashAddEntry3(ret
, iter
->name
, iter
->name2
,
991 iter
->name3
, f(iter
->payload
, iter
->name
));
996 ret
->nbElems
= table
->nbElems
;
1002 * @table: the hash table
1004 * Query the number of elements installed in the hash @table.
1006 * Returns the number of elements in the hash table or
1007 * -1 in case of error
1010 xmlHashSize(xmlHashTablePtr table
) {
1013 return(table
->nbElems
);
1017 * xmlHashRemoveEntry:
1018 * @table: the hash table
1019 * @name: the name of the userdata
1020 * @f: the deallocator function for removed item (if any)
1022 * Find the userdata specified by the @name and remove
1023 * it from the hash @table. Existing userdata for this tuple will be removed
1024 * and freed with @f.
1026 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1028 int xmlHashRemoveEntry(xmlHashTablePtr table
, const xmlChar
*name
,
1029 xmlHashDeallocator f
) {
1030 return(xmlHashRemoveEntry3(table
, name
, NULL
, NULL
, f
));
1034 * xmlHashRemoveEntry2:
1035 * @table: the hash table
1036 * @name: the name of the userdata
1037 * @name2: a second name of the userdata
1038 * @f: the deallocator function for removed item (if any)
1040 * Find the userdata specified by the (@name, @name2) tuple and remove
1041 * it from the hash @table. Existing userdata for this tuple will be removed
1042 * and freed with @f.
1044 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1047 xmlHashRemoveEntry2(xmlHashTablePtr table
, const xmlChar
*name
,
1048 const xmlChar
*name2
, xmlHashDeallocator f
) {
1049 return(xmlHashRemoveEntry3(table
, name
, name2
, NULL
, f
));
1053 * xmlHashRemoveEntry3:
1054 * @table: the hash table
1055 * @name: the name of the userdata
1056 * @name2: a second name of the userdata
1057 * @name3: a third name of the userdata
1058 * @f: the deallocator function for removed item (if any)
1060 * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
1061 * it from the hash @table. Existing userdata for this tuple will be removed
1062 * and freed with @f.
1064 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1067 xmlHashRemoveEntry3(xmlHashTablePtr table
, const xmlChar
*name
,
1068 const xmlChar
*name2
, const xmlChar
*name3
, xmlHashDeallocator f
) {
1070 xmlHashEntryPtr entry
;
1071 xmlHashEntryPtr prev
= NULL
;
1073 if (table
== NULL
|| name
== NULL
)
1076 key
= xmlHashComputeKey(table
, name
, name2
, name3
);
1077 if (table
->table
[key
].valid
== 0) {
1080 for (entry
= &(table
->table
[key
]); entry
!= NULL
; entry
= entry
->next
) {
1081 if (xmlStrEqual(entry
->name
, name
) &&
1082 xmlStrEqual(entry
->name2
, name2
) &&
1083 xmlStrEqual(entry
->name3
, name3
)) {
1084 if ((f
!= NULL
) && (entry
->payload
!= NULL
))
1085 f(entry
->payload
, entry
->name
);
1086 entry
->payload
= NULL
;
1087 if (table
->dict
== NULL
) {
1089 xmlFree(entry
->name
);
1091 xmlFree(entry
->name2
);
1093 xmlFree(entry
->name3
);
1096 prev
->next
= entry
->next
;
1099 if (entry
->next
== NULL
) {
1102 entry
= entry
->next
;
1103 memcpy(&(table
->table
[key
]), entry
, sizeof(xmlHashEntry
));
1117 #include "elfgcchack.h"