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