blob: dbf634e2efa08193aba99b275884a0ee1e7dc4d3 [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
Daniel Veillard34ce8be2002-03-18 19:37:11 +000020#define IN_LIBXML
Bjorn Reese70a9da52001-04-21 16:57:29 +000021#include "libxml.h"
Owen Taylor3473f882001-02-23 17:55:21 +000022
23#include <string.h>
24#include <libxml/hash.h>
25#include <libxml/xmlmemory.h>
26#include <libxml/parser.h>
Daniel Veillarda10efa82001-04-18 13:09:01 +000027#include <libxml/xmlerror.h>
Daniel Veillard3c01b1d2001-10-17 15:58:35 +000028#include <libxml/globals.h>
Daniel Veillarda10efa82001-04-18 13:09:01 +000029
30#define MAX_HASH_LEN 8
31
32/* #define DEBUG_GROW */
Owen Taylor3473f882001-02-23 17:55:21 +000033
34/*
35 * A single entry in the hash table
36 */
37typedef struct _xmlHashEntry xmlHashEntry;
38typedef xmlHashEntry *xmlHashEntryPtr;
39struct _xmlHashEntry {
40 struct _xmlHashEntry *next;
41 xmlChar *name;
42 xmlChar *name2;
43 xmlChar *name3;
44 void *payload;
Daniel Veillardfdc91562002-07-01 21:52:03 +000045 int valid;
Owen Taylor3473f882001-02-23 17:55:21 +000046};
47
48/*
49 * The entire hash table
50 */
51struct _xmlHashTable {
Daniel Veillardfdc91562002-07-01 21:52:03 +000052 struct _xmlHashEntry *table;
Owen Taylor3473f882001-02-23 17:55:21 +000053 int size;
54 int nbElems;
55};
56
57/*
58 * xmlHashComputeKey:
59 * Calculate the hash key
60 */
61static unsigned long
Daniel Veillarda10efa82001-04-18 13:09:01 +000062xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
63 const xmlChar *name2, const xmlChar *name3) {
Owen Taylor3473f882001-02-23 17:55:21 +000064 unsigned long value = 0L;
65 char ch;
66
Daniel Veillarda10efa82001-04-18 13:09:01 +000067 if (name != NULL) {
68 value += 30 * (*name);
69 while ((ch = *name++) != 0) {
Daniel Veillard5f7f9912002-06-17 17:03:00 +000070 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
Daniel Veillarda10efa82001-04-18 13:09:01 +000071 }
72 }
73 if (name2 != NULL) {
74 while ((ch = *name2++) != 0) {
Daniel Veillard5f7f9912002-06-17 17:03:00 +000075 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
Daniel Veillarda10efa82001-04-18 13:09:01 +000076 }
77 }
78 if (name3 != NULL) {
79 while ((ch = *name3++) != 0) {
Daniel Veillard5f7f9912002-06-17 17:03:00 +000080 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
Daniel Veillarda10efa82001-04-18 13:09:01 +000081 }
Owen Taylor3473f882001-02-23 17:55:21 +000082 }
83 return (value % table->size);
84}
85
86/**
87 * xmlHashCreate:
88 * @size: the size of the hash table
89 *
90 * Create a new xmlHashTablePtr.
91 *
92 * Returns the newly created object, or NULL if an error occured.
93 */
94xmlHashTablePtr
95xmlHashCreate(int size) {
96 xmlHashTablePtr table;
97
98 if (size <= 0)
99 size = 256;
100
101 table = xmlMalloc(sizeof(xmlHashTable));
102 if (table) {
103 table->size = size;
104 table->nbElems = 0;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000105 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
Owen Taylor3473f882001-02-23 17:55:21 +0000106 if (table->table) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000107 memset(table->table, 0, size * sizeof(xmlHashEntry));
Owen Taylor3473f882001-02-23 17:55:21 +0000108 return(table);
109 }
110 xmlFree(table);
111 }
112 return(NULL);
113}
114
115/**
Daniel Veillarda10efa82001-04-18 13:09:01 +0000116 * xmlHashGrow:
117 * @table: the hash table
118 * @size: the new size of the hash table
119 *
120 * resize the hash table
121 *
122 * Returns 0 in case of success, -1 in case of failure
123 */
Daniel Veillarddab4cb32001-04-20 13:03:48 +0000124static int
Daniel Veillarda10efa82001-04-18 13:09:01 +0000125xmlHashGrow(xmlHashTablePtr table, int size) {
126 unsigned long key;
127 int oldsize, i;
128 xmlHashEntryPtr iter, next;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000129 struct _xmlHashEntry *oldtable;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000130#ifdef DEBUG_GROW
131 unsigned long nbElem = 0;
132#endif
133
134 if (table == NULL)
135 return(-1);
136 if (size < 8)
137 return(-1);
138 if (size > 8 * 2048)
139 return(-1);
140
141 oldsize = table->size;
142 oldtable = table->table;
143 if (oldtable == NULL)
144 return(-1);
145
Daniel Veillardfdc91562002-07-01 21:52:03 +0000146 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
Daniel Veillarda10efa82001-04-18 13:09:01 +0000147 if (table->table == NULL) {
148 table->table = oldtable;
149 return(-1);
150 }
Daniel Veillardfdc91562002-07-01 21:52:03 +0000151 memset(table->table, 0, size * sizeof(xmlHashEntry));
Daniel Veillarda10efa82001-04-18 13:09:01 +0000152 table->size = size;
153
Daniel Veillardfdc91562002-07-01 21:52:03 +0000154 /* If the two loops are merged, there would be situations where
155 a new entry needs to allocated and data copied into it from
156 the main table. So instead, we run through the array twice, first
157 copying all the elements in the main array (where we can't get
158 conflicts) and then the rest, so we only free (and don't allocate)
159 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000160 for (i = 0; i < oldsize; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000161 if (oldtable[i].valid == 0)
162 continue;
163 key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
164 oldtable[i].name3);
165 memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
166 table->table[key].next = NULL;
167 }
168
169 for (i = 0; i < oldsize; i++) {
170 iter = oldtable[i].next;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000171 while (iter) {
172 next = iter->next;
173
174 /*
175 * put back the entry in the new table
176 */
177
178 key = xmlHashComputeKey(table, iter->name, iter->name2,
179 iter->name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000180 if (table->table[key].valid == 0) {
181 memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
182 table->table[key].next = NULL;
183 xmlFree(iter);
184 } else {
185 iter->next = table->table[key].next;
186 table->table[key].next = iter;
187 }
Daniel Veillarda10efa82001-04-18 13:09:01 +0000188
189#ifdef DEBUG_GROW
190 nbElem++;
191#endif
192
193 iter = next;
194 }
195 }
196
197 xmlFree(oldtable);
198
199#ifdef DEBUG_GROW
200 xmlGenericError(xmlGenericErrorContext,
201 "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
202#endif
203
204 return(0);
205}
206
207/**
Owen Taylor3473f882001-02-23 17:55:21 +0000208 * xmlHashFree:
209 * @table: the hash table
210 * @f: the deallocator function for items in the hash
211 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000212 * Free the hash @table and its contents. The userdata is
213 * deallocated with @f if provided.
Owen Taylor3473f882001-02-23 17:55:21 +0000214 */
215void
216xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
217 int i;
218 xmlHashEntryPtr iter;
219 xmlHashEntryPtr next;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000220 int inside_table = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000221
222 if (table == NULL)
223 return;
224 if (table->table) {
225 for(i = 0; i < table->size; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000226 iter = &(table->table[i]);
227 if (iter->valid == 0)
228 continue;
229 inside_table = 1;
Owen Taylor3473f882001-02-23 17:55:21 +0000230 while (iter) {
231 next = iter->next;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000232 if (f)
233 f(iter->payload, iter->name);
Owen Taylor3473f882001-02-23 17:55:21 +0000234 if (iter->name)
235 xmlFree(iter->name);
236 if (iter->name2)
237 xmlFree(iter->name2);
238 if (iter->name3)
239 xmlFree(iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000240 iter->payload = NULL;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000241 if (!inside_table)
242 xmlFree(iter);
243 inside_table = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000244 iter = next;
245 }
Daniel Veillardfdc91562002-07-01 21:52:03 +0000246 inside_table = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000247 }
248 xmlFree(table->table);
249 }
250 xmlFree(table);
251}
252
253/**
254 * xmlHashAddEntry:
255 * @table: the hash table
256 * @name: the name of the userdata
257 * @userdata: a pointer to the userdata
258 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000259 * Add the @userdata to the hash @table. This can later be retrieved
260 * by using the @name. Duplicate names generate errors.
Owen Taylor3473f882001-02-23 17:55:21 +0000261 *
262 * Returns 0 the addition succeeded and -1 in case of error.
263 */
264int
265xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
266 return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
267}
268
269/**
270 * xmlHashAddEntry2:
271 * @table: the hash table
272 * @name: the name of the userdata
273 * @name2: a second name of the userdata
274 * @userdata: a pointer to the userdata
275 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000276 * Add the @userdata to the hash @table. This can later be retrieved
277 * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
Owen Taylor3473f882001-02-23 17:55:21 +0000278 *
279 * Returns 0 the addition succeeded and -1 in case of error.
280 */
281int
282xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
283 const xmlChar *name2, void *userdata) {
284 return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
285}
286
287/**
288 * xmlHashUpdateEntry:
289 * @table: the hash table
290 * @name: the name of the userdata
291 * @userdata: a pointer to the userdata
292 * @f: the deallocator function for replaced item (if any)
293 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000294 * Add the @userdata to the hash @table. This can later be retrieved
295 * by using the @name. Existing entry for this @name will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000296 * and freed with @f if found.
297 *
298 * Returns 0 the addition succeeded and -1 in case of error.
299 */
300int
301xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
302 void *userdata, xmlHashDeallocator f) {
303 return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
304}
305
306/**
307 * xmlHashUpdateEntry2:
308 * @table: the hash table
309 * @name: the name of the userdata
310 * @name2: a second name of the userdata
311 * @userdata: a pointer to the userdata
312 * @f: the deallocator function for replaced item (if any)
313 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000314 * Add the @userdata to the hash @table. This can later be retrieved
315 * by using the (@name, @name2) tuple. Existing entry for this tuple will
Owen Taylor3473f882001-02-23 17:55:21 +0000316 * be removed and freed with @f if found.
317 *
318 * Returns 0 the addition succeeded and -1 in case of error.
319 */
320int
321xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
322 const xmlChar *name2, void *userdata,
323 xmlHashDeallocator f) {
324 return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
325}
326
327/**
328 * xmlHashLookup:
329 * @table: the hash table
330 * @name: the name of the userdata
331 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000332 * Find the userdata specified by the @name.
Owen Taylor3473f882001-02-23 17:55:21 +0000333 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000334 * Returns the pointer to the userdata
Owen Taylor3473f882001-02-23 17:55:21 +0000335 */
336void *
337xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
338 return(xmlHashLookup3(table, name, NULL, NULL));
339}
340
341/**
342 * xmlHashLookup2:
343 * @table: the hash table
344 * @name: the name of the userdata
345 * @name2: a second name of the userdata
346 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000347 * Find the userdata specified by the (@name, @name2) tuple.
Owen Taylor3473f882001-02-23 17:55:21 +0000348 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000349 * Returns the pointer to the userdata
Owen Taylor3473f882001-02-23 17:55:21 +0000350 */
351void *
352xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
353 const xmlChar *name2) {
354 return(xmlHashLookup3(table, name, name2, NULL));
355}
356
357/**
358 * xmlHashAddEntry3:
359 * @table: the hash table
360 * @name: the name of the userdata
361 * @name2: a second name of the userdata
362 * @name3: a third name of the userdata
363 * @userdata: a pointer to the userdata
364 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000365 * Add the @userdata to the hash @table. This can later be retrieved
366 * by using the tuple (@name, @name2, @name3). Duplicate entries generate
Owen Taylor3473f882001-02-23 17:55:21 +0000367 * errors.
368 *
369 * Returns 0 the addition succeeded and -1 in case of error.
370 */
371int
372xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
373 const xmlChar *name2, const xmlChar *name3,
374 void *userdata) {
Daniel Veillarda10efa82001-04-18 13:09:01 +0000375 unsigned long key, len = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000376 xmlHashEntryPtr entry;
377 xmlHashEntryPtr insert;
378
379 if ((table == NULL) || name == NULL)
380 return(-1);
381
382 /*
383 * Check for duplicate and insertion location.
384 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000385 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000386 if (table->table[key].valid == 0) {
Owen Taylor3473f882001-02-23 17:55:21 +0000387 insert = NULL;
388 } else {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000389 for (insert = &(table->table[key]); insert->next != NULL;
Owen Taylor3473f882001-02-23 17:55:21 +0000390 insert = insert->next) {
391 if ((xmlStrEqual(insert->name, name)) &&
392 (xmlStrEqual(insert->name2, name2)) &&
393 (xmlStrEqual(insert->name3, name3)))
394 return(-1);
Daniel Veillarda10efa82001-04-18 13:09:01 +0000395 len++;
Owen Taylor3473f882001-02-23 17:55:21 +0000396 }
397 if ((xmlStrEqual(insert->name, name)) &&
398 (xmlStrEqual(insert->name2, name2)) &&
399 (xmlStrEqual(insert->name3, name3)))
400 return(-1);
401 }
402
Daniel Veillardfdc91562002-07-01 21:52:03 +0000403 if (insert == NULL) {
404 entry = &(table->table[key]);
405 } else {
406 entry = xmlMalloc(sizeof(xmlHashEntry));
407 if (entry == NULL)
408 return(-1);
409 }
410
Owen Taylor3473f882001-02-23 17:55:21 +0000411 entry->name = xmlStrdup(name);
412 entry->name2 = xmlStrdup(name2);
413 entry->name3 = xmlStrdup(name3);
414 entry->payload = userdata;
415 entry->next = NULL;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000416 entry->valid = 1;
Owen Taylor3473f882001-02-23 17:55:21 +0000417
418
Daniel Veillardfdc91562002-07-01 21:52:03 +0000419 if (insert != NULL)
Owen Taylor3473f882001-02-23 17:55:21 +0000420 insert->next = entry;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000421
Owen Taylor3473f882001-02-23 17:55:21 +0000422 table->nbElems++;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000423
424 if (len > MAX_HASH_LEN)
425 xmlHashGrow(table, MAX_HASH_LEN * table->size);
426
Owen Taylor3473f882001-02-23 17:55:21 +0000427 return(0);
428}
429
430/**
431 * xmlHashUpdateEntry3:
432 * @table: the hash table
433 * @name: the name of the userdata
434 * @name2: a second name of the userdata
435 * @name3: a third name of the userdata
436 * @userdata: a pointer to the userdata
437 * @f: the deallocator function for replaced item (if any)
438 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000439 * Add the @userdata to the hash @table. This can later be retrieved
440 * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
Owen Taylor3473f882001-02-23 17:55:21 +0000441 * will be removed and freed with @f if found.
442 *
443 * Returns 0 the addition succeeded and -1 in case of error.
444 */
445int
446xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
447 const xmlChar *name2, const xmlChar *name3,
448 void *userdata, xmlHashDeallocator f) {
449 unsigned long key;
450 xmlHashEntryPtr entry;
451 xmlHashEntryPtr insert;
452
453 if ((table == NULL) || name == NULL)
454 return(-1);
455
456 /*
457 * Check for duplicate and insertion location.
458 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000459 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000460 if (table->table[key].valid == 0) {
Owen Taylor3473f882001-02-23 17:55:21 +0000461 insert = NULL;
462 } else {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000463 for (insert = &(table->table[key]); insert->next != NULL;
Owen Taylor3473f882001-02-23 17:55:21 +0000464 insert = insert->next) {
465 if ((xmlStrEqual(insert->name, name)) &&
466 (xmlStrEqual(insert->name2, name2)) &&
467 (xmlStrEqual(insert->name3, name3))) {
468 if (f)
469 f(insert->payload, insert->name);
470 insert->payload = userdata;
471 return(0);
472 }
473 }
474 if ((xmlStrEqual(insert->name, name)) &&
475 (xmlStrEqual(insert->name2, name2)) &&
476 (xmlStrEqual(insert->name3, name3))) {
477 if (f)
478 f(insert->payload, insert->name);
479 insert->payload = userdata;
480 return(0);
481 }
482 }
483
Daniel Veillardfdc91562002-07-01 21:52:03 +0000484 if (insert == NULL) {
485 entry = &(table->table[key]);
486 } else {
487 entry = xmlMalloc(sizeof(xmlHashEntry));
488 if (entry == NULL)
489 return(-1);
490 }
491
Owen Taylor3473f882001-02-23 17:55:21 +0000492 entry->name = xmlStrdup(name);
493 entry->name2 = xmlStrdup(name2);
494 entry->name3 = xmlStrdup(name3);
495 entry->payload = userdata;
496 entry->next = NULL;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000497 entry->valid = 1;
Owen Taylor3473f882001-02-23 17:55:21 +0000498 table->nbElems++;
499
500
Daniel Veillardfdc91562002-07-01 21:52:03 +0000501 if (insert != NULL) {
Owen Taylor3473f882001-02-23 17:55:21 +0000502 insert->next = entry;
503 }
504 return(0);
505}
506
507/**
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000508 * xmlHashLookup3:
Owen Taylor3473f882001-02-23 17:55:21 +0000509 * @table: the hash table
510 * @name: the name of the userdata
511 * @name2: a second name of the userdata
512 * @name3: a third name of the userdata
513 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000514 * Find the userdata specified by the (@name, @name2, @name3) tuple.
Owen Taylor3473f882001-02-23 17:55:21 +0000515 *
516 * Returns the a pointer to the userdata
517 */
518void *
519xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
520 const xmlChar *name2, const xmlChar *name3) {
521 unsigned long key;
522 xmlHashEntryPtr entry;
523
524 if (table == NULL)
525 return(NULL);
526 if (name == NULL)
527 return(NULL);
Daniel Veillarda10efa82001-04-18 13:09:01 +0000528 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000529 if (table->table[key].valid == 0)
530 return(NULL);
531 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
Owen Taylor3473f882001-02-23 17:55:21 +0000532 if ((xmlStrEqual(entry->name, name)) &&
533 (xmlStrEqual(entry->name2, name2)) &&
534 (xmlStrEqual(entry->name3, name3)))
535 return(entry->payload);
536 }
537 return(NULL);
538}
539
540/**
541 * xmlHashScan:
542 * @table: the hash table
543 * @f: the scanner function for items in the hash
544 * @data: extra data passed to f
545 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000546 * Scan the hash @table and applied @f to each value.
Owen Taylor3473f882001-02-23 17:55:21 +0000547 */
Daniel Veillard153120c2002-06-18 07:58:35 +0000548typedef struct {
549 xmlHashScanner hashscanner;
550 void *data;
551} stubData;
552
553static void
554stubHashScannerFull (void *payload, void *data, const xmlChar *name,
Daniel Veillardaeb258a2002-09-13 14:48:12 +0000555 const xmlChar *name2 ATTRIBUTE_UNUSED,
556 const xmlChar *name3 ATTRIBUTE_UNUSED) {
Daniel Veillard153120c2002-06-18 07:58:35 +0000557 stubData *stubdata = (stubData *) data;
558 stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
559}
560
Owen Taylor3473f882001-02-23 17:55:21 +0000561void
562xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
Daniel Veillard153120c2002-06-18 07:58:35 +0000563 stubData stubdata;
564 stubdata.data = data;
565 stubdata.hashscanner = f;
566 xmlHashScanFull (table, stubHashScannerFull, &stubdata);
Thomas Broyere8126242001-07-22 03:54:15 +0000567}
568
569/**
570 * xmlHashScanFull:
571 * @table: the hash table
572 * @f: the scanner function for items in the hash
573 * @data: extra data passed to f
574 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000575 * Scan the hash @table and applied @f to each value.
Thomas Broyere8126242001-07-22 03:54:15 +0000576 */
577void
578xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
Owen Taylor3473f882001-02-23 17:55:21 +0000579 int i;
580 xmlHashEntryPtr iter;
581 xmlHashEntryPtr next;
582
583 if (table == NULL)
584 return;
585 if (f == NULL)
586 return;
587
588 if (table->table) {
589 for(i = 0; i < table->size; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000590 if (table->table[i].valid == 0)
591 continue;
592 iter = &(table->table[i]);
Owen Taylor3473f882001-02-23 17:55:21 +0000593 while (iter) {
594 next = iter->next;
595 if (f)
Thomas Broyere8126242001-07-22 03:54:15 +0000596 f(iter->payload, data, iter->name,
597 iter->name2, iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000598 iter = next;
599 }
600 }
601 }
602}
603
604/**
605 * xmlHashScan3:
606 * @table: the hash table
607 * @name: the name of the userdata or NULL
608 * @name2: a second name of the userdata or NULL
609 * @name3: a third name of the userdata or NULL
610 * @f: the scanner function for items in the hash
611 * @data: extra data passed to f
612 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000613 * Scan the hash @table and applied @f to each value matching
614 * (@name, @name2, @name3) tuple. If one of the names is null,
Owen Taylor3473f882001-02-23 17:55:21 +0000615 * the comparison is considered to match.
616 */
617void
618xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
619 const xmlChar *name2, const xmlChar *name3,
620 xmlHashScanner f, void *data) {
Thomas Broyere8126242001-07-22 03:54:15 +0000621 xmlHashScanFull3 (table, name, name2, name3,
622 (xmlHashScannerFull) f, data);
623}
624
625/**
626 * xmlHashScanFull3:
627 * @table: the hash table
628 * @name: the name of the userdata or NULL
629 * @name2: a second name of the userdata or NULL
630 * @name3: a third name of the userdata or NULL
631 * @f: the scanner function for items in the hash
632 * @data: extra data passed to f
633 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000634 * Scan the hash @table and applied @f to each value matching
635 * (@name, @name2, @name3) tuple. If one of the names is null,
Thomas Broyere8126242001-07-22 03:54:15 +0000636 * the comparison is considered to match.
637 */
638void
639xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
640 const xmlChar *name2, const xmlChar *name3,
641 xmlHashScannerFull f, void *data) {
Owen Taylor3473f882001-02-23 17:55:21 +0000642 int i;
643 xmlHashEntryPtr iter;
644 xmlHashEntryPtr next;
645
646 if (table == NULL)
647 return;
648 if (f == NULL)
649 return;
650
651 if (table->table) {
652 for(i = 0; i < table->size; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000653 if (table->table[i].valid == 0)
654 continue;
655 iter = &(table->table[i]);
Owen Taylor3473f882001-02-23 17:55:21 +0000656 while (iter) {
657 next = iter->next;
658 if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
659 ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
660 ((name3 == NULL) || (xmlStrEqual(name3, iter->name3)))) {
Thomas Broyere8126242001-07-22 03:54:15 +0000661 f(iter->payload, data, iter->name,
662 iter->name2, iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000663 }
664 iter = next;
665 }
666 }
667 }
668}
669
670/**
671 * xmlHashCopy:
672 * @table: the hash table
673 * @f: the copier function for items in the hash
674 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000675 * Scan the hash @table and applied @f to each value.
Owen Taylor3473f882001-02-23 17:55:21 +0000676 *
677 * Returns the new table or NULL in case of error.
678 */
679xmlHashTablePtr
680xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
681 int i;
682 xmlHashEntryPtr iter;
683 xmlHashEntryPtr next;
684 xmlHashTablePtr ret;
685
686 if (table == NULL)
687 return(NULL);
688 if (f == NULL)
689 return(NULL);
690
691 ret = xmlHashCreate(table->size);
692 if (table->table) {
693 for(i = 0; i < table->size; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000694 if (table->table[i].valid == 0)
695 continue;
696 iter = &(table->table[i]);
Owen Taylor3473f882001-02-23 17:55:21 +0000697 while (iter) {
698 next = iter->next;
699 xmlHashAddEntry3(ret, iter->name, iter->name2,
700 iter->name3, f(iter->payload, iter->name));
701 iter = next;
702 }
703 }
704 }
705 ret->nbElems = table->nbElems;
706 return(ret);
707}
708
709/**
710 * xmlHashSize:
711 * @table: the hash table
712 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000713 * Query the number of elements installed in the hash @table.
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000714 *
Owen Taylor3473f882001-02-23 17:55:21 +0000715 * Returns the number of elements in the hash table or
716 * -1 in case of error
717 */
718int
719xmlHashSize(xmlHashTablePtr table) {
720 if (table == NULL)
721 return(-1);
722 return(table->nbElems);
723}
724
725/**
Daniel Veillardf69bb4b2001-05-19 13:24:56 +0000726 * xmlHashRemoveEntry:
Owen Taylor3473f882001-02-23 17:55:21 +0000727 * @table: the hash table
728 * @name: the name of the userdata
729 * @f: the deallocator function for removed item (if any)
730 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000731 * Find the userdata specified by the @name and remove
732 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000733 * and freed with @f.
734 *
735 * Returns 0 if the removal succeeded and -1 in case of error or not found.
736 */
737int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +0000738 xmlHashDeallocator f) {
739 return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
Owen Taylor3473f882001-02-23 17:55:21 +0000740}
741
742/**
Daniel Veillardf69bb4b2001-05-19 13:24:56 +0000743 * xmlHashRemoveEntry2:
Owen Taylor3473f882001-02-23 17:55:21 +0000744 * @table: the hash table
745 * @name: the name of the userdata
746 * @name2: a second name of the userdata
747 * @f: the deallocator function for removed item (if any)
748 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000749 * Find the userdata specified by the (@name, @name2) tuple and remove
750 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000751 * and freed with @f.
752 *
753 * Returns 0 if the removal succeeded and -1 in case of error or not found.
754 */
755int xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +0000756 const xmlChar *name2, xmlHashDeallocator f) {
757 return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
Owen Taylor3473f882001-02-23 17:55:21 +0000758}
759
760/**
Daniel Veillardf69bb4b2001-05-19 13:24:56 +0000761 * xmlHashRemoveEntry3
Owen Taylor3473f882001-02-23 17:55:21 +0000762 * @table: the hash table
763 * @name: the name of the userdata
764 * @name2: a second name of the userdata
765 * @name3: a third name of the userdata
766 * @f: the deallocator function for removed item (if any)
767 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000768 * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
769 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000770 * and freed with @f.
771 *
772 * Returns 0 if the removal succeeded and -1 in case of error or not found.
773 */
774int xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +0000775 const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
776 unsigned long key;
777 xmlHashEntryPtr entry;
778 xmlHashEntryPtr prev = NULL;
Owen Taylor3473f882001-02-23 17:55:21 +0000779
Daniel Veillarda10efa82001-04-18 13:09:01 +0000780 if (table == NULL || name == NULL)
781 return(-1);
Owen Taylor3473f882001-02-23 17:55:21 +0000782
Daniel Veillarda10efa82001-04-18 13:09:01 +0000783 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000784 if (table->table[key].valid == 0) {
Daniel Veillarda10efa82001-04-18 13:09:01 +0000785 return(-1);
786 } else {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000787 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
Daniel Veillarda10efa82001-04-18 13:09:01 +0000788 if (xmlStrEqual(entry->name, name) &&
789 xmlStrEqual(entry->name2, name2) &&
790 xmlStrEqual(entry->name3, name3)) {
791 if(f)
792 f(entry->payload, entry->name);
793 entry->payload = NULL;
794 if(entry->name)
795 xmlFree(entry->name);
796 if(entry->name2)
797 xmlFree(entry->name2);
798 if(entry->name3)
799 xmlFree(entry->name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000800 if(prev) {
Daniel Veillarda10efa82001-04-18 13:09:01 +0000801 prev->next = entry->next;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000802 xmlFree(entry);
803 } else {
804 if (entry->next == NULL) {
805 entry->valid = 0;
806 } else {
807 entry = entry->next;
808 memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
809 xmlFree(entry);
810 }
811 }
Daniel Veillarda10efa82001-04-18 13:09:01 +0000812 table->nbElems--;
813 return(0);
814 }
815 prev = entry;
816 }
817 return(-1);
818 }
Daniel Veillard9e7160d2001-03-18 23:17:47 +0000819}
820