• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 occurred.
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 occurred.
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  * xmlHashDefaultDeallocator:
365  * @entry: the hash table entry
366  * @name: the entry's name
367  *
368  * Free a hash table entry with xmlFree.
369  */
370 void
xmlHashDefaultDeallocator(void * entry,const xmlChar * name ATTRIBUTE_UNUSED)371 xmlHashDefaultDeallocator(void *entry, const xmlChar *name ATTRIBUTE_UNUSED) {
372     xmlFree(entry);
373 }
374 
375 /**
376  * xmlHashAddEntry:
377  * @table: the hash table
378  * @name: the name of the userdata
379  * @userdata: a pointer to the userdata
380  *
381  * Add the @userdata to the hash @table. This can later be retrieved
382  * by using the @name. Duplicate names generate errors.
383  *
384  * Returns 0 the addition succeeded and -1 in case of error.
385  */
386 int
xmlHashAddEntry(xmlHashTablePtr table,const xmlChar * name,void * userdata)387 xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
388     return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
389 }
390 
391 /**
392  * xmlHashAddEntry2:
393  * @table: the hash table
394  * @name: the name of the userdata
395  * @name2: a second name of the userdata
396  * @userdata: a pointer to the userdata
397  *
398  * Add the @userdata to the hash @table. This can later be retrieved
399  * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
400  *
401  * Returns 0 the addition succeeded and -1 in case of error.
402  */
403 int
xmlHashAddEntry2(xmlHashTablePtr table,const xmlChar * name,const xmlChar * name2,void * userdata)404 xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
405 	        const xmlChar *name2, void *userdata) {
406     return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
407 }
408 
409 /**
410  * xmlHashUpdateEntry:
411  * @table: the hash table
412  * @name: the name of the userdata
413  * @userdata: a pointer to the userdata
414  * @f: the deallocator function for replaced item (if any)
415  *
416  * Add the @userdata to the hash @table. This can later be retrieved
417  * by using the @name. Existing entry for this @name will be removed
418  * and freed with @f if found.
419  *
420  * Returns 0 the addition succeeded and -1 in case of error.
421  */
422 int
xmlHashUpdateEntry(xmlHashTablePtr table,const xmlChar * name,void * userdata,xmlHashDeallocator f)423 xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
424 	           void *userdata, xmlHashDeallocator f) {
425     return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
426 }
427 
428 /**
429  * xmlHashUpdateEntry2:
430  * @table: the hash table
431  * @name: the name of the userdata
432  * @name2: a second name of the userdata
433  * @userdata: a pointer to the userdata
434  * @f: the deallocator function for replaced item (if any)
435  *
436  * Add the @userdata to the hash @table. This can later be retrieved
437  * by using the (@name, @name2) tuple. Existing entry for this tuple will
438  * be removed and freed with @f if found.
439  *
440  * Returns 0 the addition succeeded and -1 in case of error.
441  */
442 int
xmlHashUpdateEntry2(xmlHashTablePtr table,const xmlChar * name,const xmlChar * name2,void * userdata,xmlHashDeallocator f)443 xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
444 	           const xmlChar *name2, void *userdata,
445 		   xmlHashDeallocator f) {
446     return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
447 }
448 
449 /**
450  * xmlHashLookup:
451  * @table: the hash table
452  * @name: the name of the userdata
453  *
454  * Find the userdata specified by the @name.
455  *
456  * Returns the pointer to the userdata
457  */
458 void *
xmlHashLookup(xmlHashTablePtr table,const xmlChar * name)459 xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
460     return(xmlHashLookup3(table, name, NULL, NULL));
461 }
462 
463 /**
464  * xmlHashLookup2:
465  * @table: the hash table
466  * @name: the name of the userdata
467  * @name2: a second name of the userdata
468  *
469  * Find the userdata specified by the (@name, @name2) tuple.
470  *
471  * Returns the pointer to the userdata
472  */
473 void *
xmlHashLookup2(xmlHashTablePtr table,const xmlChar * name,const xmlChar * name2)474 xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
475 	      const xmlChar *name2) {
476     return(xmlHashLookup3(table, name, name2, NULL));
477 }
478 
479 /**
480  * xmlHashQLookup:
481  * @table: the hash table
482  * @prefix: the prefix of the userdata
483  * @name: the name of the userdata
484  *
485  * Find the userdata specified by the QName @prefix:@name/@name.
486  *
487  * Returns the pointer to the userdata
488  */
489 void *
xmlHashQLookup(xmlHashTablePtr table,const xmlChar * prefix,const xmlChar * name)490 xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,
491                const xmlChar *name) {
492     return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));
493 }
494 
495 /**
496  * xmlHashQLookup2:
497  * @table: the hash table
498  * @prefix: the prefix of the userdata
499  * @name: the name of the userdata
500  * @prefix2: the second prefix of the userdata
501  * @name2: a second name of the userdata
502  *
503  * Find the userdata specified by the QNames tuple
504  *
505  * Returns the pointer to the userdata
506  */
507 void *
xmlHashQLookup2(xmlHashTablePtr table,const xmlChar * prefix,const xmlChar * name,const xmlChar * prefix2,const xmlChar * name2)508 xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,
509                 const xmlChar *name, const xmlChar *prefix2,
510 	        const xmlChar *name2) {
511     return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
512 }
513 
514 /**
515  * xmlHashAddEntry3:
516  * @table: the hash table
517  * @name: the name of the userdata
518  * @name2: a second name of the userdata
519  * @name3: a third name of the userdata
520  * @userdata: a pointer to the userdata
521  *
522  * Add the @userdata to the hash @table. This can later be retrieved
523  * by using the tuple (@name, @name2, @name3). Duplicate entries generate
524  * errors.
525  *
526  * Returns 0 the addition succeeded and -1 in case of error.
527  */
528 int
xmlHashAddEntry3(xmlHashTablePtr table,const xmlChar * name,const xmlChar * name2,const xmlChar * name3,void * userdata)529 xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
530 	         const xmlChar *name2, const xmlChar *name3,
531 		 void *userdata) {
532     unsigned long key, len = 0;
533     xmlHashEntryPtr entry;
534     xmlHashEntryPtr insert;
535 
536     if ((table == NULL) || (name == NULL))
537 	return(-1);
538 
539     /*
540      * If using a dict internalize if needed
541      */
542     if (table->dict) {
543         if (!xmlDictOwns(table->dict, name)) {
544 	    name = xmlDictLookup(table->dict, name, -1);
545 	    if (name == NULL)
546 	        return(-1);
547 	}
548         if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
549 	    name2 = xmlDictLookup(table->dict, name2, -1);
550 	    if (name2 == NULL)
551 	        return(-1);
552 	}
553         if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
554 	    name3 = xmlDictLookup(table->dict, name3, -1);
555 	    if (name3 == NULL)
556 	        return(-1);
557 	}
558     }
559 
560     /*
561      * Check for duplicate and insertion location.
562      */
563     key = xmlHashComputeKey(table, name, name2, name3);
564     if (table->table[key].valid == 0) {
565 	insert = NULL;
566     } else {
567         if (table->dict) {
568 	    for (insert = &(table->table[key]); insert->next != NULL;
569 		 insert = insert->next) {
570 		if ((insert->name == name) &&
571 		    (insert->name2 == name2) &&
572 		    (insert->name3 == name3))
573 		    return(-1);
574 		len++;
575 	    }
576 	    if ((insert->name == name) &&
577 		(insert->name2 == name2) &&
578 		(insert->name3 == name3))
579 		return(-1);
580 	} else {
581 	    for (insert = &(table->table[key]); insert->next != NULL;
582 		 insert = insert->next) {
583 		if ((xmlStrEqual(insert->name, name)) &&
584 		    (xmlStrEqual(insert->name2, name2)) &&
585 		    (xmlStrEqual(insert->name3, name3)))
586 		    return(-1);
587 		len++;
588 	    }
589 	    if ((xmlStrEqual(insert->name, name)) &&
590 		(xmlStrEqual(insert->name2, name2)) &&
591 		(xmlStrEqual(insert->name3, name3)))
592 		return(-1);
593 	}
594     }
595 
596     if (insert == NULL) {
597 	entry = &(table->table[key]);
598     } else {
599 	entry = xmlMalloc(sizeof(xmlHashEntry));
600 	if (entry == NULL)
601 	     return(-1);
602     }
603 
604     if (table->dict != NULL) {
605         entry->name = (xmlChar *) name;
606         entry->name2 = (xmlChar *) name2;
607         entry->name3 = (xmlChar *) name3;
608     } else {
609 	entry->name = xmlStrdup(name);
610 	entry->name2 = xmlStrdup(name2);
611 	entry->name3 = xmlStrdup(name3);
612     }
613     entry->payload = userdata;
614     entry->next = NULL;
615     entry->valid = 1;
616 
617 
618     if (insert != NULL)
619 	insert->next = entry;
620 
621     table->nbElems++;
622 
623     if (len > MAX_HASH_LEN)
624 	xmlHashGrow(table, MAX_HASH_LEN * table->size);
625 
626     return(0);
627 }
628 
629 /**
630  * xmlHashUpdateEntry3:
631  * @table: the hash table
632  * @name: the name of the userdata
633  * @name2: a second name of the userdata
634  * @name3: a third name of the userdata
635  * @userdata: a pointer to the userdata
636  * @f: the deallocator function for replaced item (if any)
637  *
638  * Add the @userdata to the hash @table. This can later be retrieved
639  * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
640  * will be removed and freed with @f if found.
641  *
642  * Returns 0 the addition succeeded and -1 in case of error.
643  */
644 int
xmlHashUpdateEntry3(xmlHashTablePtr table,const xmlChar * name,const xmlChar * name2,const xmlChar * name3,void * userdata,xmlHashDeallocator f)645 xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
646 	           const xmlChar *name2, const xmlChar *name3,
647 		   void *userdata, xmlHashDeallocator f) {
648     unsigned long key;
649     xmlHashEntryPtr entry;
650     xmlHashEntryPtr insert;
651 
652     if ((table == NULL) || name == NULL)
653 	return(-1);
654 
655     /*
656      * If using a dict internalize if needed
657      */
658     if (table->dict) {
659         if (!xmlDictOwns(table->dict, name)) {
660 	    name = xmlDictLookup(table->dict, name, -1);
661 	    if (name == NULL)
662 	        return(-1);
663 	}
664         if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
665 	    name2 = xmlDictLookup(table->dict, name2, -1);
666 	    if (name2 == NULL)
667 	        return(-1);
668 	}
669         if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
670 	    name3 = xmlDictLookup(table->dict, name3, -1);
671 	    if (name3 == NULL)
672 	        return(-1);
673 	}
674     }
675 
676     /*
677      * Check for duplicate and insertion location.
678      */
679     key = xmlHashComputeKey(table, name, name2, name3);
680     if (table->table[key].valid == 0) {
681 	insert = NULL;
682     } else {
683         if (table ->dict) {
684 	    for (insert = &(table->table[key]); insert->next != NULL;
685 		 insert = insert->next) {
686 		if ((insert->name == name) &&
687 		    (insert->name2 == name2) &&
688 		    (insert->name3 == name3)) {
689 		    if (f)
690 			f(insert->payload, insert->name);
691 		    insert->payload = userdata;
692 		    return(0);
693 		}
694 	    }
695 	    if ((insert->name == name) &&
696 		(insert->name2 == name2) &&
697 		(insert->name3 == name3)) {
698 		if (f)
699 		    f(insert->payload, insert->name);
700 		insert->payload = userdata;
701 		return(0);
702 	    }
703 	} else {
704 	    for (insert = &(table->table[key]); insert->next != NULL;
705 		 insert = insert->next) {
706 		if ((xmlStrEqual(insert->name, name)) &&
707 		    (xmlStrEqual(insert->name2, name2)) &&
708 		    (xmlStrEqual(insert->name3, name3))) {
709 		    if (f)
710 			f(insert->payload, insert->name);
711 		    insert->payload = userdata;
712 		    return(0);
713 		}
714 	    }
715 	    if ((xmlStrEqual(insert->name, name)) &&
716 		(xmlStrEqual(insert->name2, name2)) &&
717 		(xmlStrEqual(insert->name3, name3))) {
718 		if (f)
719 		    f(insert->payload, insert->name);
720 		insert->payload = userdata;
721 		return(0);
722 	    }
723 	}
724     }
725 
726     if (insert == NULL) {
727 	entry =  &(table->table[key]);
728     } else {
729 	entry = xmlMalloc(sizeof(xmlHashEntry));
730 	if (entry == NULL)
731 	     return(-1);
732     }
733 
734     if (table->dict != NULL) {
735         entry->name = (xmlChar *) name;
736         entry->name2 = (xmlChar *) name2;
737         entry->name3 = (xmlChar *) name3;
738     } else {
739 	entry->name = xmlStrdup(name);
740 	entry->name2 = xmlStrdup(name2);
741 	entry->name3 = xmlStrdup(name3);
742     }
743     entry->payload = userdata;
744     entry->next = NULL;
745     entry->valid = 1;
746     table->nbElems++;
747 
748 
749     if (insert != NULL) {
750 	insert->next = entry;
751     }
752     return(0);
753 }
754 
755 /**
756  * xmlHashLookup3:
757  * @table: the hash table
758  * @name: the name of the userdata
759  * @name2: a second name of the userdata
760  * @name3: a third name of the userdata
761  *
762  * Find the userdata specified by the (@name, @name2, @name3) tuple.
763  *
764  * Returns the a pointer to the userdata
765  */
766 void *
xmlHashLookup3(xmlHashTablePtr table,const xmlChar * name,const xmlChar * name2,const xmlChar * name3)767 xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
768 	       const xmlChar *name2, const xmlChar *name3) {
769     unsigned long key;
770     xmlHashEntryPtr entry;
771 
772     if (table == NULL)
773 	return(NULL);
774     if (name == NULL)
775 	return(NULL);
776     key = xmlHashComputeKey(table, name, name2, name3);
777     if (table->table[key].valid == 0)
778 	return(NULL);
779     if (table->dict) {
780 	for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
781 	    if ((entry->name == name) &&
782 		(entry->name2 == name2) &&
783 		(entry->name3 == name3))
784 		return(entry->payload);
785 	}
786     }
787     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
788 	if ((xmlStrEqual(entry->name, name)) &&
789 	    (xmlStrEqual(entry->name2, name2)) &&
790 	    (xmlStrEqual(entry->name3, name3)))
791 	    return(entry->payload);
792     }
793     return(NULL);
794 }
795 
796 /**
797  * xmlHashQLookup3:
798  * @table: the hash table
799  * @prefix: the prefix of the userdata
800  * @name: the name of the userdata
801  * @prefix2: the second prefix of the userdata
802  * @name2: a second name of the userdata
803  * @prefix3: the third prefix of the userdata
804  * @name3: a third name of the userdata
805  *
806  * Find the userdata specified by the (@name, @name2, @name3) tuple.
807  *
808  * Returns the a pointer to the userdata
809  */
810 void *
xmlHashQLookup3(xmlHashTablePtr table,const xmlChar * prefix,const xmlChar * name,const xmlChar * prefix2,const xmlChar * name2,const xmlChar * prefix3,const xmlChar * name3)811 xmlHashQLookup3(xmlHashTablePtr table,
812                 const xmlChar *prefix, const xmlChar *name,
813 		const xmlChar *prefix2, const xmlChar *name2,
814 		const xmlChar *prefix3, const xmlChar *name3) {
815     unsigned long key;
816     xmlHashEntryPtr entry;
817 
818     if (table == NULL)
819 	return(NULL);
820     if (name == NULL)
821 	return(NULL);
822     key = xmlHashComputeQKey(table, prefix, name, prefix2,
823                              name2, prefix3, name3);
824     if (table->table[key].valid == 0)
825 	return(NULL);
826     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
827 	if ((xmlStrQEqual(prefix, name, entry->name)) &&
828 	    (xmlStrQEqual(prefix2, name2, entry->name2)) &&
829 	    (xmlStrQEqual(prefix3, name3, entry->name3)))
830 	    return(entry->payload);
831     }
832     return(NULL);
833 }
834 
835 typedef struct {
836     xmlHashScanner hashscanner;
837     void *data;
838 } stubData;
839 
840 static void
stubHashScannerFull(void * payload,void * data,const xmlChar * name,const xmlChar * name2 ATTRIBUTE_UNUSED,const xmlChar * name3 ATTRIBUTE_UNUSED)841 stubHashScannerFull (void *payload, void *data, const xmlChar *name,
842                      const xmlChar *name2 ATTRIBUTE_UNUSED,
843 		     const xmlChar *name3 ATTRIBUTE_UNUSED) {
844     stubData *stubdata = (stubData *) data;
845     stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
846 }
847 
848 /**
849  * xmlHashScan:
850  * @table: the hash table
851  * @f:  the scanner function for items in the hash
852  * @data:  extra data passed to f
853  *
854  * Scan the hash @table and applied @f to each value.
855  */
856 void
xmlHashScan(xmlHashTablePtr table,xmlHashScanner f,void * data)857 xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
858     stubData stubdata;
859     stubdata.data = data;
860     stubdata.hashscanner = f;
861     xmlHashScanFull (table, stubHashScannerFull, &stubdata);
862 }
863 
864 /**
865  * xmlHashScanFull:
866  * @table: the hash table
867  * @f:  the scanner function for items in the hash
868  * @data:  extra data passed to f
869  *
870  * Scan the hash @table and applied @f to each value.
871  */
872 void
xmlHashScanFull(xmlHashTablePtr table,xmlHashScannerFull f,void * data)873 xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
874     int i, nb;
875     xmlHashEntryPtr iter;
876     xmlHashEntryPtr next;
877 
878     if (table == NULL)
879 	return;
880     if (f == NULL)
881 	return;
882 
883     if (table->table) {
884 	for(i = 0; i < table->size; i++) {
885 	    if (table->table[i].valid == 0)
886 		continue;
887 	    iter = &(table->table[i]);
888 	    while (iter) {
889 		next = iter->next;
890                 nb = table->nbElems;
891 		if ((f != NULL) && (iter->payload != NULL))
892 		    f(iter->payload, data, iter->name,
893 		      iter->name2, iter->name3);
894                 if (nb != table->nbElems) {
895                     /* table was modified by the callback, be careful */
896                     if (iter == &(table->table[i])) {
897                         if (table->table[i].valid == 0)
898                             iter = NULL;
899                         if (table->table[i].next != next)
900 			    iter = &(table->table[i]);
901                     } else
902 		        iter = next;
903                 } else
904 		    iter = next;
905 	    }
906 	}
907     }
908 }
909 
910 /**
911  * xmlHashScan3:
912  * @table: the hash table
913  * @name: the name of the userdata or NULL
914  * @name2: a second name of the userdata or NULL
915  * @name3: a third name of the userdata or NULL
916  * @f:  the scanner function for items in the hash
917  * @data:  extra data passed to f
918  *
919  * Scan the hash @table and applied @f to each value matching
920  * (@name, @name2, @name3) tuple. If one of the names is null,
921  * the comparison is considered to match.
922  */
923 void
xmlHashScan3(xmlHashTablePtr table,const xmlChar * name,const xmlChar * name2,const xmlChar * name3,xmlHashScanner f,void * data)924 xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
925 	     const xmlChar *name2, const xmlChar *name3,
926 	     xmlHashScanner f, void *data) {
927     stubData stubdata;
928     stubdata.data = data;
929     stubdata.hashscanner = f;
930     xmlHashScanFull3(table, name, name2, name3, stubHashScannerFull,
931                      &stubdata);
932 }
933 
934 /**
935  * xmlHashScanFull3:
936  * @table: the hash table
937  * @name: the name of the userdata or NULL
938  * @name2: a second name of the userdata or NULL
939  * @name3: a third name of the userdata or NULL
940  * @f:  the scanner function for items in the hash
941  * @data:  extra data passed to f
942  *
943  * Scan the hash @table and applied @f to each value matching
944  * (@name, @name2, @name3) tuple. If one of the names is null,
945  * the comparison is considered to match.
946  */
947 void
xmlHashScanFull3(xmlHashTablePtr table,const xmlChar * name,const xmlChar * name2,const xmlChar * name3,xmlHashScannerFull f,void * data)948 xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
949 		 const xmlChar *name2, const xmlChar *name3,
950 		 xmlHashScannerFull f, void *data) {
951     int i;
952     xmlHashEntryPtr iter;
953     xmlHashEntryPtr next;
954 
955     if (table == NULL)
956 	return;
957     if (f == NULL)
958 	return;
959 
960     if (table->table) {
961 	for(i = 0; i < table->size; i++) {
962 	    if (table->table[i].valid == 0)
963 		continue;
964 	    iter = &(table->table[i]);
965 	    while (iter) {
966 		next = iter->next;
967 		if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
968 		    ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
969 		    ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&
970 		    (iter->payload != NULL)) {
971 		    f(iter->payload, data, iter->name,
972 		      iter->name2, iter->name3);
973 		}
974 		iter = next;
975 	    }
976 	}
977     }
978 }
979 
980 /**
981  * xmlHashCopy:
982  * @table: the hash table
983  * @f:  the copier function for items in the hash
984  *
985  * Scan the hash @table and applied @f to each value.
986  *
987  * Returns the new table or NULL in case of error.
988  */
989 xmlHashTablePtr
xmlHashCopy(xmlHashTablePtr table,xmlHashCopier f)990 xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
991     int i;
992     xmlHashEntryPtr iter;
993     xmlHashEntryPtr next;
994     xmlHashTablePtr ret;
995 
996     if (table == NULL)
997 	return(NULL);
998     if (f == NULL)
999 	return(NULL);
1000 
1001     ret = xmlHashCreate(table->size);
1002     if (ret == NULL)
1003         return(NULL);
1004 
1005     if (table->table) {
1006 	for(i = 0; i < table->size; i++) {
1007 	    if (table->table[i].valid == 0)
1008 		continue;
1009 	    iter = &(table->table[i]);
1010 	    while (iter) {
1011 		next = iter->next;
1012 		xmlHashAddEntry3(ret, iter->name, iter->name2,
1013 			         iter->name3, f(iter->payload, iter->name));
1014 		iter = next;
1015 	    }
1016 	}
1017     }
1018     ret->nbElems = table->nbElems;
1019     return(ret);
1020 }
1021 
1022 /**
1023  * xmlHashSize:
1024  * @table: the hash table
1025  *
1026  * Query the number of elements installed in the hash @table.
1027  *
1028  * Returns the number of elements in the hash table or
1029  * -1 in case of error
1030  */
1031 int
xmlHashSize(xmlHashTablePtr table)1032 xmlHashSize(xmlHashTablePtr table) {
1033     if (table == NULL)
1034 	return(-1);
1035     return(table->nbElems);
1036 }
1037 
1038 /**
1039  * xmlHashRemoveEntry:
1040  * @table: the hash table
1041  * @name: the name of the userdata
1042  * @f: the deallocator function for removed item (if any)
1043  *
1044  * Find the userdata specified by the @name and remove
1045  * it from the hash @table. Existing userdata for this tuple will be removed
1046  * and freed with @f.
1047  *
1048  * Returns 0 if the removal succeeded and -1 in case of error or not found.
1049  */
xmlHashRemoveEntry(xmlHashTablePtr table,const xmlChar * name,xmlHashDeallocator f)1050 int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
1051 		       xmlHashDeallocator f) {
1052     return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
1053 }
1054 
1055 /**
1056  * xmlHashRemoveEntry2:
1057  * @table: the hash table
1058  * @name: the name of the userdata
1059  * @name2: a second name of the userdata
1060  * @f: the deallocator function for removed item (if any)
1061  *
1062  * Find the userdata specified by the (@name, @name2) tuple and remove
1063  * it from the hash @table. Existing userdata for this tuple will be removed
1064  * and freed with @f.
1065  *
1066  * Returns 0 if the removal succeeded and -1 in case of error or not found.
1067  */
1068 int
xmlHashRemoveEntry2(xmlHashTablePtr table,const xmlChar * name,const xmlChar * name2,xmlHashDeallocator f)1069 xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
1070 			const xmlChar *name2, xmlHashDeallocator f) {
1071     return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
1072 }
1073 
1074 /**
1075  * xmlHashRemoveEntry3:
1076  * @table: the hash table
1077  * @name: the name of the userdata
1078  * @name2: a second name of the userdata
1079  * @name3: a third name of the userdata
1080  * @f: the deallocator function for removed item (if any)
1081  *
1082  * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
1083  * it from the hash @table. Existing userdata for this tuple will be removed
1084  * and freed with @f.
1085  *
1086  * Returns 0 if the removal succeeded and -1 in case of error or not found.
1087  */
1088 int
xmlHashRemoveEntry3(xmlHashTablePtr table,const xmlChar * name,const xmlChar * name2,const xmlChar * name3,xmlHashDeallocator f)1089 xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
1090     const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
1091     unsigned long key;
1092     xmlHashEntryPtr entry;
1093     xmlHashEntryPtr prev = NULL;
1094 
1095     if (table == NULL || name == NULL)
1096         return(-1);
1097 
1098     key = xmlHashComputeKey(table, name, name2, name3);
1099     if (table->table[key].valid == 0) {
1100         return(-1);
1101     } else {
1102         for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
1103             if (xmlStrEqual(entry->name, name) &&
1104                     xmlStrEqual(entry->name2, name2) &&
1105                     xmlStrEqual(entry->name3, name3)) {
1106                 if ((f != NULL) && (entry->payload != NULL))
1107                     f(entry->payload, entry->name);
1108                 entry->payload = NULL;
1109 		if (table->dict == NULL) {
1110 		    if(entry->name)
1111 			xmlFree(entry->name);
1112 		    if(entry->name2)
1113 			xmlFree(entry->name2);
1114 		    if(entry->name3)
1115 			xmlFree(entry->name3);
1116 		}
1117                 if(prev) {
1118                     prev->next = entry->next;
1119 		    xmlFree(entry);
1120 		} else {
1121 		    if (entry->next == NULL) {
1122 			entry->valid = 0;
1123 		    } else {
1124 			entry = entry->next;
1125 			memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
1126 			xmlFree(entry);
1127 		    }
1128 		}
1129                 table->nbElems--;
1130                 return(0);
1131             }
1132             prev = entry;
1133         }
1134         return(-1);
1135     }
1136 }
1137 
1138 #define bottom_hash
1139 #include "elfgcchack.h"
1140