VirtualBox

source: vbox/trunk/src/libs/libxml2-2.9.2/hash.c@ 63360

Last change on this file since 63360 was 58072, checked in by vboxsync, 9 years ago

libxml 2.9.2 unmodified

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

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette