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