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