blob: 33fdec8fe13595cfe591987ea51fa72349937b31 [file] [log] [blame]
Owen Taylor3473f882001-02-23 17:55:21 +00001/*
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 *
Bjorn Reese70a9da52001-04-21 16:57:29 +000017 * Author: breese@users.sourceforge.net
Owen Taylor3473f882001-02-23 17:55:21 +000018 */
19
Bjorn Reese70a9da52001-04-21 16:57:29 +000020#include "libxml.h"
Owen Taylor3473f882001-02-23 17:55:21 +000021
22#include <string.h>
23#include <libxml/hash.h>
24#include <libxml/xmlmemory.h>
25#include <libxml/parser.h>
Daniel Veillarda10efa82001-04-18 13:09:01 +000026#include <libxml/xmlerror.h>
Daniel Veillard3c01b1d2001-10-17 15:58:35 +000027#include <libxml/globals.h>
Daniel Veillarda10efa82001-04-18 13:09:01 +000028
29#define MAX_HASH_LEN 8
30
31/* #define DEBUG_GROW */
Owen Taylor3473f882001-02-23 17:55:21 +000032
33/*
34 * A single entry in the hash table
35 */
36typedef struct _xmlHashEntry xmlHashEntry;
37typedef xmlHashEntry *xmlHashEntryPtr;
38struct _xmlHashEntry {
39 struct _xmlHashEntry *next;
40 xmlChar *name;
41 xmlChar *name2;
42 xmlChar *name3;
43 void *payload;
44};
45
46/*
47 * The entire hash table
48 */
49struct _xmlHashTable {
50 struct _xmlHashEntry **table;
51 int size;
52 int nbElems;
53};
54
55/*
56 * xmlHashComputeKey:
57 * Calculate the hash key
58 */
59static unsigned long
Daniel Veillarda10efa82001-04-18 13:09:01 +000060xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
61 const xmlChar *name2, const xmlChar *name3) {
Owen Taylor3473f882001-02-23 17:55:21 +000062 unsigned long value = 0L;
63 char ch;
64
Daniel Veillarda10efa82001-04-18 13:09:01 +000065 if (name != NULL) {
66 value += 30 * (*name);
67 while ((ch = *name++) != 0) {
68 /* value *= 31; */
69 value += (unsigned long)ch;
70 }
71 }
72 if (name2 != NULL) {
73 while ((ch = *name2++) != 0) {
74 /* value *= 31; */
75 value += (unsigned long)ch;
76 }
77 }
78 if (name3 != NULL) {
79 while ((ch = *name3++) != 0) {
80 /* value *= 31; */
81 value += (unsigned long)ch;
82 }
Owen Taylor3473f882001-02-23 17:55:21 +000083 }
84 return (value % table->size);
85}
86
87/**
88 * xmlHashCreate:
89 * @size: the size of the hash table
90 *
91 * Create a new xmlHashTablePtr.
92 *
93 * Returns the newly created object, or NULL if an error occured.
94 */
95xmlHashTablePtr
96xmlHashCreate(int size) {
97 xmlHashTablePtr table;
98
99 if (size <= 0)
100 size = 256;
101
102 table = xmlMalloc(sizeof(xmlHashTable));
103 if (table) {
104 table->size = size;
105 table->nbElems = 0;
Daniel Veillard314cfa02002-01-14 17:58:01 +0000106 table->table = xmlMalloc(size * sizeof(xmlHashEntryPtr));
Owen Taylor3473f882001-02-23 17:55:21 +0000107 if (table->table) {
Daniel Veillard314cfa02002-01-14 17:58:01 +0000108 memset(table->table, 0, size * sizeof(xmlHashEntryPtr));
Owen Taylor3473f882001-02-23 17:55:21 +0000109 return(table);
110 }
111 xmlFree(table);
112 }
113 return(NULL);
114}
115
116/**
Daniel Veillarda10efa82001-04-18 13:09:01 +0000117 * xmlHashGrow:
118 * @table: the hash table
119 * @size: the new size of the hash table
120 *
121 * resize the hash table
122 *
123 * Returns 0 in case of success, -1 in case of failure
124 */
Daniel Veillarddab4cb32001-04-20 13:03:48 +0000125static int
Daniel Veillarda10efa82001-04-18 13:09:01 +0000126xmlHashGrow(xmlHashTablePtr table, int size) {
127 unsigned long key;
128 int oldsize, i;
129 xmlHashEntryPtr iter, next;
130 struct _xmlHashEntry **oldtable;
131#ifdef DEBUG_GROW
132 unsigned long nbElem = 0;
133#endif
134
135 if (table == NULL)
136 return(-1);
137 if (size < 8)
138 return(-1);
139 if (size > 8 * 2048)
140 return(-1);
141
142 oldsize = table->size;
143 oldtable = table->table;
144 if (oldtable == NULL)
145 return(-1);
146
Daniel Veillard314cfa02002-01-14 17:58:01 +0000147 table->table = xmlMalloc(size * sizeof(xmlHashEntryPtr));
Daniel Veillarda10efa82001-04-18 13:09:01 +0000148 if (table->table == NULL) {
149 table->table = oldtable;
150 return(-1);
151 }
Daniel Veillard314cfa02002-01-14 17:58:01 +0000152 memset(table->table, 0, size * sizeof(xmlHashEntryPtr));
Daniel Veillarda10efa82001-04-18 13:09:01 +0000153 table->size = size;
154
155 for (i = 0; i < oldsize; i++) {
156 iter = oldtable[i];
157 while (iter) {
158 next = iter->next;
159
160 /*
161 * put back the entry in the new table
162 */
163
164 key = xmlHashComputeKey(table, iter->name, iter->name2,
165 iter->name3);
166 iter->next = table->table[key];
167 table->table[key] = iter;
168
169#ifdef DEBUG_GROW
170 nbElem++;
171#endif
172
173 iter = next;
174 }
175 }
176
177 xmlFree(oldtable);
178
179#ifdef DEBUG_GROW
180 xmlGenericError(xmlGenericErrorContext,
181 "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
182#endif
183
184 return(0);
185}
186
187/**
Owen Taylor3473f882001-02-23 17:55:21 +0000188 * xmlHashFree:
189 * @table: the hash table
190 * @f: the deallocator function for items in the hash
191 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000192 * Free the hash @table and its contents. The userdata is
193 * deallocated with @f if provided.
Owen Taylor3473f882001-02-23 17:55:21 +0000194 */
195void
196xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
197 int i;
198 xmlHashEntryPtr iter;
199 xmlHashEntryPtr next;
200
201 if (table == NULL)
202 return;
203 if (table->table) {
204 for(i = 0; i < table->size; i++) {
205 iter = table->table[i];
206 while (iter) {
207 next = iter->next;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000208 if (f)
209 f(iter->payload, iter->name);
Owen Taylor3473f882001-02-23 17:55:21 +0000210 if (iter->name)
211 xmlFree(iter->name);
212 if (iter->name2)
213 xmlFree(iter->name2);
214 if (iter->name3)
215 xmlFree(iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000216 iter->payload = NULL;
217 xmlFree(iter);
218 iter = next;
219 }
220 table->table[i] = NULL;
221 }
222 xmlFree(table->table);
223 }
224 xmlFree(table);
225}
226
227/**
228 * xmlHashAddEntry:
229 * @table: the hash table
230 * @name: the name of the userdata
231 * @userdata: a pointer to the userdata
232 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000233 * Add the @userdata to the hash @table. This can later be retrieved
234 * by using the @name. Duplicate names generate errors.
Owen Taylor3473f882001-02-23 17:55:21 +0000235 *
236 * Returns 0 the addition succeeded and -1 in case of error.
237 */
238int
239xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
240 return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
241}
242
243/**
244 * xmlHashAddEntry2:
245 * @table: the hash table
246 * @name: the name of the userdata
247 * @name2: a second name of the userdata
248 * @userdata: a pointer to the userdata
249 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000250 * Add the @userdata to the hash @table. This can later be retrieved
251 * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
Owen Taylor3473f882001-02-23 17:55:21 +0000252 *
253 * Returns 0 the addition succeeded and -1 in case of error.
254 */
255int
256xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
257 const xmlChar *name2, void *userdata) {
258 return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
259}
260
261/**
262 * xmlHashUpdateEntry:
263 * @table: the hash table
264 * @name: the name of the userdata
265 * @userdata: a pointer to the userdata
266 * @f: the deallocator function for replaced item (if any)
267 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000268 * Add the @userdata to the hash @table. This can later be retrieved
269 * by using the @name. Existing entry for this @name will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000270 * and freed with @f if found.
271 *
272 * Returns 0 the addition succeeded and -1 in case of error.
273 */
274int
275xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
276 void *userdata, xmlHashDeallocator f) {
277 return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
278}
279
280/**
281 * xmlHashUpdateEntry2:
282 * @table: the hash table
283 * @name: the name of the userdata
284 * @name2: a second name of the userdata
285 * @userdata: a pointer to the userdata
286 * @f: the deallocator function for replaced item (if any)
287 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000288 * Add the @userdata to the hash @table. This can later be retrieved
289 * by using the (@name, @name2) tuple. Existing entry for this tuple will
Owen Taylor3473f882001-02-23 17:55:21 +0000290 * be removed and freed with @f if found.
291 *
292 * Returns 0 the addition succeeded and -1 in case of error.
293 */
294int
295xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
296 const xmlChar *name2, void *userdata,
297 xmlHashDeallocator f) {
298 return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
299}
300
301/**
302 * xmlHashLookup:
303 * @table: the hash table
304 * @name: the name of the userdata
305 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000306 * Find the userdata specified by the @name.
Owen Taylor3473f882001-02-23 17:55:21 +0000307 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000308 * Returns the pointer to the userdata
Owen Taylor3473f882001-02-23 17:55:21 +0000309 */
310void *
311xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
312 return(xmlHashLookup3(table, name, NULL, NULL));
313}
314
315/**
316 * xmlHashLookup2:
317 * @table: the hash table
318 * @name: the name of the userdata
319 * @name2: a second name of the userdata
320 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000321 * Find the userdata specified by the (@name, @name2) tuple.
Owen Taylor3473f882001-02-23 17:55:21 +0000322 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000323 * Returns the pointer to the userdata
Owen Taylor3473f882001-02-23 17:55:21 +0000324 */
325void *
326xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
327 const xmlChar *name2) {
328 return(xmlHashLookup3(table, name, name2, NULL));
329}
330
331/**
332 * xmlHashAddEntry3:
333 * @table: the hash table
334 * @name: the name of the userdata
335 * @name2: a second name of the userdata
336 * @name3: a third name of the userdata
337 * @userdata: a pointer to the userdata
338 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000339 * Add the @userdata to the hash @table. This can later be retrieved
340 * by using the tuple (@name, @name2, @name3). Duplicate entries generate
Owen Taylor3473f882001-02-23 17:55:21 +0000341 * errors.
342 *
343 * Returns 0 the addition succeeded and -1 in case of error.
344 */
345int
346xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
347 const xmlChar *name2, const xmlChar *name3,
348 void *userdata) {
Daniel Veillarda10efa82001-04-18 13:09:01 +0000349 unsigned long key, len = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000350 xmlHashEntryPtr entry;
351 xmlHashEntryPtr insert;
352
353 if ((table == NULL) || name == NULL)
354 return(-1);
355
356 /*
357 * Check for duplicate and insertion location.
358 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000359 key = xmlHashComputeKey(table, name, name2, name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000360 if (table->table[key] == NULL) {
361 insert = NULL;
362 } else {
363 for (insert = table->table[key]; insert->next != NULL;
364 insert = insert->next) {
365 if ((xmlStrEqual(insert->name, name)) &&
366 (xmlStrEqual(insert->name2, name2)) &&
367 (xmlStrEqual(insert->name3, name3)))
368 return(-1);
Daniel Veillarda10efa82001-04-18 13:09:01 +0000369 len++;
Owen Taylor3473f882001-02-23 17:55:21 +0000370 }
371 if ((xmlStrEqual(insert->name, name)) &&
372 (xmlStrEqual(insert->name2, name2)) &&
373 (xmlStrEqual(insert->name3, name3)))
374 return(-1);
375 }
376
377 entry = xmlMalloc(sizeof(xmlHashEntry));
378 if (entry == NULL)
379 return(-1);
380 entry->name = xmlStrdup(name);
381 entry->name2 = xmlStrdup(name2);
382 entry->name3 = xmlStrdup(name3);
383 entry->payload = userdata;
384 entry->next = NULL;
385
386
387 if (insert == NULL) {
388 table->table[key] = entry;
389 } else {
390 insert->next = entry;
391 }
392 table->nbElems++;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000393
394 if (len > MAX_HASH_LEN)
395 xmlHashGrow(table, MAX_HASH_LEN * table->size);
396
Owen Taylor3473f882001-02-23 17:55:21 +0000397 return(0);
398}
399
400/**
401 * xmlHashUpdateEntry3:
402 * @table: the hash table
403 * @name: the name of the userdata
404 * @name2: a second name of the userdata
405 * @name3: a third name of the userdata
406 * @userdata: a pointer to the userdata
407 * @f: the deallocator function for replaced item (if any)
408 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000409 * Add the @userdata to the hash @table. This can later be retrieved
410 * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
Owen Taylor3473f882001-02-23 17:55:21 +0000411 * will be removed and freed with @f if found.
412 *
413 * Returns 0 the addition succeeded and -1 in case of error.
414 */
415int
416xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
417 const xmlChar *name2, const xmlChar *name3,
418 void *userdata, xmlHashDeallocator f) {
419 unsigned long key;
420 xmlHashEntryPtr entry;
421 xmlHashEntryPtr insert;
422
423 if ((table == NULL) || name == NULL)
424 return(-1);
425
426 /*
427 * Check for duplicate and insertion location.
428 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000429 key = xmlHashComputeKey(table, name, name2, name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000430 if (table->table[key] == NULL) {
431 insert = NULL;
432 } else {
433 for (insert = table->table[key]; insert->next != NULL;
434 insert = insert->next) {
435 if ((xmlStrEqual(insert->name, name)) &&
436 (xmlStrEqual(insert->name2, name2)) &&
437 (xmlStrEqual(insert->name3, name3))) {
438 if (f)
439 f(insert->payload, insert->name);
440 insert->payload = userdata;
441 return(0);
442 }
443 }
444 if ((xmlStrEqual(insert->name, name)) &&
445 (xmlStrEqual(insert->name2, name2)) &&
446 (xmlStrEqual(insert->name3, name3))) {
447 if (f)
448 f(insert->payload, insert->name);
449 insert->payload = userdata;
450 return(0);
451 }
452 }
453
454 entry = xmlMalloc(sizeof(xmlHashEntry));
455 if (entry == NULL)
456 return(-1);
457 entry->name = xmlStrdup(name);
458 entry->name2 = xmlStrdup(name2);
459 entry->name3 = xmlStrdup(name3);
460 entry->payload = userdata;
461 entry->next = NULL;
462 table->nbElems++;
463
464
465 if (insert == NULL) {
466 table->table[key] = entry;
467 } else {
468 insert->next = entry;
469 }
470 return(0);
471}
472
473/**
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000474 * xmlHashLookup3:
Owen Taylor3473f882001-02-23 17:55:21 +0000475 * @table: the hash table
476 * @name: the name of the userdata
477 * @name2: a second name of the userdata
478 * @name3: a third name of the userdata
479 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000480 * Find the userdata specified by the (@name, @name2, @name3) tuple.
Owen Taylor3473f882001-02-23 17:55:21 +0000481 *
482 * Returns the a pointer to the userdata
483 */
484void *
485xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
486 const xmlChar *name2, const xmlChar *name3) {
487 unsigned long key;
488 xmlHashEntryPtr entry;
489
490 if (table == NULL)
491 return(NULL);
492 if (name == NULL)
493 return(NULL);
Daniel Veillarda10efa82001-04-18 13:09:01 +0000494 key = xmlHashComputeKey(table, name, name2, name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000495 for (entry = table->table[key]; entry != NULL; entry = entry->next) {
496 if ((xmlStrEqual(entry->name, name)) &&
497 (xmlStrEqual(entry->name2, name2)) &&
498 (xmlStrEqual(entry->name3, name3)))
499 return(entry->payload);
500 }
501 return(NULL);
502}
503
504/**
505 * xmlHashScan:
506 * @table: the hash table
507 * @f: the scanner function for items in the hash
508 * @data: extra data passed to f
509 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000510 * Scan the hash @table and applied @f to each value.
Owen Taylor3473f882001-02-23 17:55:21 +0000511 */
512void
513xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
Thomas Broyere8126242001-07-22 03:54:15 +0000514 xmlHashScanFull (table, (xmlHashScannerFull) f, data);
515}
516
517/**
518 * xmlHashScanFull:
519 * @table: the hash table
520 * @f: the scanner function for items in the hash
521 * @data: extra data passed to f
522 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000523 * Scan the hash @table and applied @f to each value.
Thomas Broyere8126242001-07-22 03:54:15 +0000524 */
525void
526xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
Owen Taylor3473f882001-02-23 17:55:21 +0000527 int i;
528 xmlHashEntryPtr iter;
529 xmlHashEntryPtr next;
530
531 if (table == NULL)
532 return;
533 if (f == NULL)
534 return;
535
536 if (table->table) {
537 for(i = 0; i < table->size; i++) {
538 iter = table->table[i];
539 while (iter) {
540 next = iter->next;
541 if (f)
Thomas Broyere8126242001-07-22 03:54:15 +0000542 f(iter->payload, data, iter->name,
543 iter->name2, iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000544 iter = next;
545 }
546 }
547 }
548}
549
550/**
551 * xmlHashScan3:
552 * @table: the hash table
553 * @name: the name of the userdata or NULL
554 * @name2: a second name of the userdata or NULL
555 * @name3: a third name of the userdata or NULL
556 * @f: the scanner function for items in the hash
557 * @data: extra data passed to f
558 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000559 * Scan the hash @table and applied @f to each value matching
560 * (@name, @name2, @name3) tuple. If one of the names is null,
Owen Taylor3473f882001-02-23 17:55:21 +0000561 * the comparison is considered to match.
562 */
563void
564xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
565 const xmlChar *name2, const xmlChar *name3,
566 xmlHashScanner f, void *data) {
Thomas Broyere8126242001-07-22 03:54:15 +0000567 xmlHashScanFull3 (table, name, name2, name3,
568 (xmlHashScannerFull) f, data);
569}
570
571/**
572 * xmlHashScanFull3:
573 * @table: the hash table
574 * @name: the name of the userdata or NULL
575 * @name2: a second name of the userdata or NULL
576 * @name3: a third name of the userdata or NULL
577 * @f: the scanner function for items in the hash
578 * @data: extra data passed to f
579 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000580 * Scan the hash @table and applied @f to each value matching
581 * (@name, @name2, @name3) tuple. If one of the names is null,
Thomas Broyere8126242001-07-22 03:54:15 +0000582 * the comparison is considered to match.
583 */
584void
585xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
586 const xmlChar *name2, const xmlChar *name3,
587 xmlHashScannerFull f, void *data) {
Owen Taylor3473f882001-02-23 17:55:21 +0000588 int i;
589 xmlHashEntryPtr iter;
590 xmlHashEntryPtr next;
591
592 if (table == NULL)
593 return;
594 if (f == NULL)
595 return;
596
597 if (table->table) {
598 for(i = 0; i < table->size; i++) {
599 iter = table->table[i];
600 while (iter) {
601 next = iter->next;
602 if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
603 ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
604 ((name3 == NULL) || (xmlStrEqual(name3, iter->name3)))) {
Thomas Broyere8126242001-07-22 03:54:15 +0000605 f(iter->payload, data, iter->name,
606 iter->name2, iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000607 }
608 iter = next;
609 }
610 }
611 }
612}
613
614/**
615 * xmlHashCopy:
616 * @table: the hash table
617 * @f: the copier function for items in the hash
618 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000619 * Scan the hash @table and applied @f to each value.
Owen Taylor3473f882001-02-23 17:55:21 +0000620 *
621 * Returns the new table or NULL in case of error.
622 */
623xmlHashTablePtr
624xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
625 int i;
626 xmlHashEntryPtr iter;
627 xmlHashEntryPtr next;
628 xmlHashTablePtr ret;
629
630 if (table == NULL)
631 return(NULL);
632 if (f == NULL)
633 return(NULL);
634
635 ret = xmlHashCreate(table->size);
636 if (table->table) {
637 for(i = 0; i < table->size; i++) {
638 iter = table->table[i];
639 while (iter) {
640 next = iter->next;
641 xmlHashAddEntry3(ret, iter->name, iter->name2,
642 iter->name3, f(iter->payload, iter->name));
643 iter = next;
644 }
645 }
646 }
647 ret->nbElems = table->nbElems;
648 return(ret);
649}
650
651/**
652 * xmlHashSize:
653 * @table: the hash table
654 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000655 * Query the number of elements installed in the hash @table.
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000656 *
Owen Taylor3473f882001-02-23 17:55:21 +0000657 * Returns the number of elements in the hash table or
658 * -1 in case of error
659 */
660int
661xmlHashSize(xmlHashTablePtr table) {
662 if (table == NULL)
663 return(-1);
664 return(table->nbElems);
665}
666
667/**
Daniel Veillardf69bb4b2001-05-19 13:24:56 +0000668 * xmlHashRemoveEntry:
Owen Taylor3473f882001-02-23 17:55:21 +0000669 * @table: the hash table
670 * @name: the name of the userdata
671 * @f: the deallocator function for removed item (if any)
672 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000673 * Find the userdata specified by the @name and remove
674 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000675 * and freed with @f.
676 *
677 * Returns 0 if the removal succeeded and -1 in case of error or not found.
678 */
679int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +0000680 xmlHashDeallocator f) {
681 return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
Owen Taylor3473f882001-02-23 17:55:21 +0000682}
683
684/**
Daniel Veillardf69bb4b2001-05-19 13:24:56 +0000685 * xmlHashRemoveEntry2:
Owen Taylor3473f882001-02-23 17:55:21 +0000686 * @table: the hash table
687 * @name: the name of the userdata
688 * @name2: a second name of the userdata
689 * @f: the deallocator function for removed item (if any)
690 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000691 * Find the userdata specified by the (@name, @name2) tuple and remove
692 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000693 * and freed with @f.
694 *
695 * Returns 0 if the removal succeeded and -1 in case of error or not found.
696 */
697int xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +0000698 const xmlChar *name2, xmlHashDeallocator f) {
699 return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
Owen Taylor3473f882001-02-23 17:55:21 +0000700}
701
702/**
Daniel Veillardf69bb4b2001-05-19 13:24:56 +0000703 * xmlHashRemoveEntry3
Owen Taylor3473f882001-02-23 17:55:21 +0000704 * @table: the hash table
705 * @name: the name of the userdata
706 * @name2: a second name of the userdata
707 * @name3: a third name of the userdata
708 * @f: the deallocator function for removed item (if any)
709 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000710 * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
711 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000712 * and freed with @f.
713 *
714 * Returns 0 if the removal succeeded and -1 in case of error or not found.
715 */
716int xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +0000717 const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
718 unsigned long key;
719 xmlHashEntryPtr entry;
720 xmlHashEntryPtr prev = NULL;
Owen Taylor3473f882001-02-23 17:55:21 +0000721
Daniel Veillarda10efa82001-04-18 13:09:01 +0000722 if (table == NULL || name == NULL)
723 return(-1);
Owen Taylor3473f882001-02-23 17:55:21 +0000724
Daniel Veillarda10efa82001-04-18 13:09:01 +0000725 key = xmlHashComputeKey(table, name, name2, name3);
726 if (table->table[key] == NULL) {
727 return(-1);
728 } else {
729 for (entry = table->table[key]; entry != NULL; entry = entry->next) {
730 if (xmlStrEqual(entry->name, name) &&
731 xmlStrEqual(entry->name2, name2) &&
732 xmlStrEqual(entry->name3, name3)) {
733 if(f)
734 f(entry->payload, entry->name);
735 entry->payload = NULL;
736 if(entry->name)
737 xmlFree(entry->name);
738 if(entry->name2)
739 xmlFree(entry->name2);
740 if(entry->name3)
741 xmlFree(entry->name3);
742 if(prev)
743 prev->next = entry->next;
744 else
745 table->table[key] = entry->next;
746 xmlFree(entry);
747 table->nbElems--;
748 return(0);
749 }
750 prev = entry;
751 }
752 return(-1);
753 }
Daniel Veillard9e7160d2001-03-18 23:17:47 +0000754}
755