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