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 */
53typedef struct _xmlHashEntry xmlHashEntry;
54typedef xmlHashEntry *xmlHashEntryPtr;
55struct _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 */
67struct _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 */
81static unsigned long
82xmlHashComputeKey(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
111static unsigned long
112xmlHashComputeQKey(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 */
173xmlHashTablePtr
174xmlHashCreate(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 */
207xmlHashTablePtr
208xmlHashCreateDict(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 */
228static int
229xmlHashGrow(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 */
319void
320xmlHashFree(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 */
370void
371xmlHashDefaultDeallocator(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 */
386int
387xmlHashAddEntry(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 */
403int
404xmlHashAddEntry2(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 */
422int
423xmlHashUpdateEntry(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 */
442int
443xmlHashUpdateEntry2(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 */
458void *
459xmlHashLookup(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 */
473void *
474xmlHashLookup2(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 */
489void *
490xmlHashQLookup(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 */
507void *
508xmlHashQLookup2(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 */
528int
529xmlHashAddEntry3(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 */
644int
645xmlHashUpdateEntry3(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 */
766void *
767xmlHashLookup3(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 */
810void *
811xmlHashQLookup3(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
835typedef struct {
836    xmlHashScanner hashscanner;
837    void *data;
838} stubData;
839
840static void
841stubHashScannerFull (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 */
856void
857xmlHashScan(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 */
872void
873xmlHashScanFull(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 */
923void
924xmlHashScan3(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 */
947void
948xmlHashScanFull3(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 */
989xmlHashTablePtr
990xmlHashCopy(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 */
1031int
1032xmlHashSize(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 */
1050int 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 */
1068int
1069xmlHashRemoveEntry2(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 */
1088int
1089xmlHashRemoveEntry3(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