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