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