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