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