blob: ff06b01f219be971919d7013569c244cb1d73b06 [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>
Daniel Veillarde57ec792003-09-10 10:50:59 +000024#include <libxml/parser.h>
Owen Taylor3473f882001-02-23 17:55:21 +000025#include <libxml/hash.h>
26#include <libxml/xmlmemory.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
Daniel Veillarde57ec792003-09-10 10:50:59 +000086static unsigned long
87xmlHashComputeQKey(xmlHashTablePtr table,
Daniel Veillard8e36e6a2003-09-10 10:50:59 +000088 const xmlChar *prefix, const xmlChar *name,
89 const xmlChar *prefix2, const xmlChar *name2,
90 const xmlChar *prefix3, const xmlChar *name3) {
Daniel Veillarde57ec792003-09-10 10:50:59 +000091 unsigned long value = 0L;
92 char ch;
93
94 if (prefix != NULL)
95 value += 30 * (*prefix);
96 else
97 value += 30 * (*name);
98
99 if (prefix != NULL) {
100 while ((ch = *prefix++) != 0) {
101 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
102 }
103 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
104 }
105 if (name != NULL) {
106 while ((ch = *name++) != 0) {
107 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
108 }
109 }
110 if (prefix2 != NULL) {
111 while ((ch = *prefix2++) != 0) {
112 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
113 }
114 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
115 }
116 if (name2 != NULL) {
117 while ((ch = *name2++) != 0) {
118 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
119 }
120 }
121 if (prefix3 != NULL) {
122 while ((ch = *prefix3++) != 0) {
123 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
124 }
125 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
126 }
127 if (name3 != NULL) {
128 while ((ch = *name3++) != 0) {
129 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
130 }
131 }
132 return (value % table->size);
133}
134
Owen Taylor3473f882001-02-23 17:55:21 +0000135/**
136 * xmlHashCreate:
137 * @size: the size of the hash table
138 *
139 * Create a new xmlHashTablePtr.
140 *
141 * Returns the newly created object, or NULL if an error occured.
142 */
143xmlHashTablePtr
144xmlHashCreate(int size) {
145 xmlHashTablePtr table;
146
147 if (size <= 0)
148 size = 256;
149
150 table = xmlMalloc(sizeof(xmlHashTable));
151 if (table) {
152 table->size = size;
153 table->nbElems = 0;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000154 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
Owen Taylor3473f882001-02-23 17:55:21 +0000155 if (table->table) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000156 memset(table->table, 0, size * sizeof(xmlHashEntry));
Owen Taylor3473f882001-02-23 17:55:21 +0000157 return(table);
158 }
159 xmlFree(table);
160 }
161 return(NULL);
162}
163
164/**
Daniel Veillarda10efa82001-04-18 13:09:01 +0000165 * xmlHashGrow:
166 * @table: the hash table
167 * @size: the new size of the hash table
168 *
169 * resize the hash table
170 *
171 * Returns 0 in case of success, -1 in case of failure
172 */
Daniel Veillarddab4cb32001-04-20 13:03:48 +0000173static int
Daniel Veillarda10efa82001-04-18 13:09:01 +0000174xmlHashGrow(xmlHashTablePtr table, int size) {
175 unsigned long key;
176 int oldsize, i;
177 xmlHashEntryPtr iter, next;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000178 struct _xmlHashEntry *oldtable;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000179#ifdef DEBUG_GROW
180 unsigned long nbElem = 0;
181#endif
182
183 if (table == NULL)
184 return(-1);
185 if (size < 8)
186 return(-1);
187 if (size > 8 * 2048)
188 return(-1);
189
190 oldsize = table->size;
191 oldtable = table->table;
192 if (oldtable == NULL)
193 return(-1);
194
Daniel Veillardfdc91562002-07-01 21:52:03 +0000195 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
Daniel Veillarda10efa82001-04-18 13:09:01 +0000196 if (table->table == NULL) {
197 table->table = oldtable;
198 return(-1);
199 }
Daniel Veillardfdc91562002-07-01 21:52:03 +0000200 memset(table->table, 0, size * sizeof(xmlHashEntry));
Daniel Veillarda10efa82001-04-18 13:09:01 +0000201 table->size = size;
202
Daniel Veillardfdc91562002-07-01 21:52:03 +0000203 /* If the two loops are merged, there would be situations where
204 a new entry needs to allocated and data copied into it from
205 the main table. So instead, we run through the array twice, first
206 copying all the elements in the main array (where we can't get
207 conflicts) and then the rest, so we only free (and don't allocate)
208 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000209 for (i = 0; i < oldsize; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000210 if (oldtable[i].valid == 0)
211 continue;
212 key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
213 oldtable[i].name3);
214 memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
215 table->table[key].next = NULL;
216 }
217
218 for (i = 0; i < oldsize; i++) {
219 iter = oldtable[i].next;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000220 while (iter) {
221 next = iter->next;
222
223 /*
224 * put back the entry in the new table
225 */
226
227 key = xmlHashComputeKey(table, iter->name, iter->name2,
228 iter->name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000229 if (table->table[key].valid == 0) {
230 memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
231 table->table[key].next = NULL;
232 xmlFree(iter);
233 } else {
234 iter->next = table->table[key].next;
235 table->table[key].next = iter;
236 }
Daniel Veillarda10efa82001-04-18 13:09:01 +0000237
238#ifdef DEBUG_GROW
239 nbElem++;
240#endif
241
242 iter = next;
243 }
244 }
245
246 xmlFree(oldtable);
247
248#ifdef DEBUG_GROW
249 xmlGenericError(xmlGenericErrorContext,
250 "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
251#endif
252
253 return(0);
254}
255
256/**
Owen Taylor3473f882001-02-23 17:55:21 +0000257 * xmlHashFree:
258 * @table: the hash table
259 * @f: the deallocator function for items in the hash
260 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000261 * Free the hash @table and its contents. The userdata is
262 * deallocated with @f if provided.
Owen Taylor3473f882001-02-23 17:55:21 +0000263 */
264void
265xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
266 int i;
267 xmlHashEntryPtr iter;
268 xmlHashEntryPtr next;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000269 int inside_table = 0;
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000270 int nbElems;
Owen Taylor3473f882001-02-23 17:55:21 +0000271
272 if (table == NULL)
273 return;
274 if (table->table) {
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000275 nbElems = table->nbElems;
276 for(i = 0; (i < table->size) && (nbElems > 0); i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000277 iter = &(table->table[i]);
278 if (iter->valid == 0)
279 continue;
280 inside_table = 1;
Owen Taylor3473f882001-02-23 17:55:21 +0000281 while (iter) {
282 next = iter->next;
Daniel Veillarde991fe92003-10-29 11:18:37 +0000283 if ((f != NULL) && (iter->payload != NULL))
Daniel Veillarda10efa82001-04-18 13:09:01 +0000284 f(iter->payload, iter->name);
Owen Taylor3473f882001-02-23 17:55:21 +0000285 if (iter->name)
286 xmlFree(iter->name);
287 if (iter->name2)
288 xmlFree(iter->name2);
289 if (iter->name3)
290 xmlFree(iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000291 iter->payload = NULL;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000292 if (!inside_table)
293 xmlFree(iter);
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000294 nbElems--;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000295 inside_table = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000296 iter = next;
297 }
Daniel Veillardfdc91562002-07-01 21:52:03 +0000298 inside_table = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000299 }
300 xmlFree(table->table);
301 }
302 xmlFree(table);
303}
304
305/**
306 * xmlHashAddEntry:
307 * @table: the hash table
308 * @name: the name of the userdata
309 * @userdata: a pointer to the userdata
310 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000311 * Add the @userdata to the hash @table. This can later be retrieved
312 * by using the @name. Duplicate names generate errors.
Owen Taylor3473f882001-02-23 17:55:21 +0000313 *
314 * Returns 0 the addition succeeded and -1 in case of error.
315 */
316int
317xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
318 return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
319}
320
321/**
322 * xmlHashAddEntry2:
323 * @table: the hash table
324 * @name: the name of the userdata
325 * @name2: a second name of the userdata
326 * @userdata: a pointer to the userdata
327 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000328 * Add the @userdata to the hash @table. This can later be retrieved
329 * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
Owen Taylor3473f882001-02-23 17:55:21 +0000330 *
331 * Returns 0 the addition succeeded and -1 in case of error.
332 */
333int
334xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
335 const xmlChar *name2, void *userdata) {
336 return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
337}
338
339/**
340 * xmlHashUpdateEntry:
341 * @table: the hash table
342 * @name: the name of the userdata
343 * @userdata: a pointer to the userdata
344 * @f: the deallocator function for replaced item (if any)
345 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000346 * Add the @userdata to the hash @table. This can later be retrieved
347 * by using the @name. Existing entry for this @name will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000348 * and freed with @f if found.
349 *
350 * Returns 0 the addition succeeded and -1 in case of error.
351 */
352int
353xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
354 void *userdata, xmlHashDeallocator f) {
355 return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
356}
357
358/**
359 * xmlHashUpdateEntry2:
360 * @table: the hash table
361 * @name: the name of the userdata
362 * @name2: a second name of the userdata
363 * @userdata: a pointer to the userdata
364 * @f: the deallocator function for replaced item (if any)
365 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000366 * Add the @userdata to the hash @table. This can later be retrieved
367 * by using the (@name, @name2) tuple. Existing entry for this tuple will
Owen Taylor3473f882001-02-23 17:55:21 +0000368 * be removed and freed with @f if found.
369 *
370 * Returns 0 the addition succeeded and -1 in case of error.
371 */
372int
373xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
374 const xmlChar *name2, void *userdata,
375 xmlHashDeallocator f) {
376 return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
377}
378
379/**
380 * xmlHashLookup:
381 * @table: the hash table
382 * @name: the name of the userdata
383 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000384 * Find the userdata specified by the @name.
Owen Taylor3473f882001-02-23 17:55:21 +0000385 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000386 * Returns the pointer to the userdata
Owen Taylor3473f882001-02-23 17:55:21 +0000387 */
388void *
389xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
390 return(xmlHashLookup3(table, name, NULL, NULL));
391}
392
393/**
394 * xmlHashLookup2:
395 * @table: the hash table
396 * @name: the name of the userdata
397 * @name2: a second name of the userdata
398 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000399 * Find the userdata specified by the (@name, @name2) tuple.
Owen Taylor3473f882001-02-23 17:55:21 +0000400 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000401 * Returns the pointer to the userdata
Owen Taylor3473f882001-02-23 17:55:21 +0000402 */
403void *
404xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
405 const xmlChar *name2) {
406 return(xmlHashLookup3(table, name, name2, NULL));
407}
408
409/**
Daniel Veillarde57ec792003-09-10 10:50:59 +0000410 * xmlHashQLookup:
411 * @table: the hash table
412 * @prefix: the prefix of the userdata
413 * @name: the name of the userdata
414 *
415 * Find the userdata specified by the QName @prefix:@name/@name.
416 *
417 * Returns the pointer to the userdata
418 */
419void *
420xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,
421 const xmlChar *name) {
422 return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));
423}
424
425/**
Daniel Veillard7a02cfe2003-09-25 12:18:34 +0000426 * xmlHashQLookup2:
Daniel Veillarde57ec792003-09-10 10:50:59 +0000427 * @table: the hash table
428 * @prefix: the prefix of the userdata
429 * @name: the name of the userdata
Daniel Veillard092643b2003-09-25 14:29:29 +0000430 * @prefix2: the second prefix of the userdata
Daniel Veillarde57ec792003-09-10 10:50:59 +0000431 * @name2: a second name of the userdata
432 *
433 * Find the userdata specified by the QNames tuple
434 *
435 * Returns the pointer to the userdata
436 */
437void *
438xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,
439 const xmlChar *name, const xmlChar *prefix2,
440 const xmlChar *name2) {
441 return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
442}
443
444/**
Owen Taylor3473f882001-02-23 17:55:21 +0000445 * xmlHashAddEntry3:
446 * @table: the hash table
447 * @name: the name of the userdata
448 * @name2: a second name of the userdata
449 * @name3: a third name of the userdata
450 * @userdata: a pointer to the userdata
451 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000452 * Add the @userdata to the hash @table. This can later be retrieved
453 * by using the tuple (@name, @name2, @name3). Duplicate entries generate
Owen Taylor3473f882001-02-23 17:55:21 +0000454 * errors.
455 *
456 * Returns 0 the addition succeeded and -1 in case of error.
457 */
458int
459xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
460 const xmlChar *name2, const xmlChar *name3,
461 void *userdata) {
Daniel Veillarda10efa82001-04-18 13:09:01 +0000462 unsigned long key, len = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000463 xmlHashEntryPtr entry;
464 xmlHashEntryPtr insert;
465
466 if ((table == NULL) || name == NULL)
467 return(-1);
468
469 /*
470 * Check for duplicate and insertion location.
471 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000472 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000473 if (table->table[key].valid == 0) {
Owen Taylor3473f882001-02-23 17:55:21 +0000474 insert = NULL;
475 } else {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000476 for (insert = &(table->table[key]); insert->next != NULL;
Owen Taylor3473f882001-02-23 17:55:21 +0000477 insert = insert->next) {
478 if ((xmlStrEqual(insert->name, name)) &&
479 (xmlStrEqual(insert->name2, name2)) &&
480 (xmlStrEqual(insert->name3, name3)))
481 return(-1);
Daniel Veillarda10efa82001-04-18 13:09:01 +0000482 len++;
Owen Taylor3473f882001-02-23 17:55:21 +0000483 }
484 if ((xmlStrEqual(insert->name, name)) &&
485 (xmlStrEqual(insert->name2, name2)) &&
486 (xmlStrEqual(insert->name3, name3)))
487 return(-1);
488 }
489
Daniel Veillardfdc91562002-07-01 21:52:03 +0000490 if (insert == NULL) {
491 entry = &(table->table[key]);
492 } else {
493 entry = xmlMalloc(sizeof(xmlHashEntry));
494 if (entry == NULL)
495 return(-1);
496 }
497
Owen Taylor3473f882001-02-23 17:55:21 +0000498 entry->name = xmlStrdup(name);
499 entry->name2 = xmlStrdup(name2);
500 entry->name3 = xmlStrdup(name3);
501 entry->payload = userdata;
502 entry->next = NULL;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000503 entry->valid = 1;
Owen Taylor3473f882001-02-23 17:55:21 +0000504
505
Daniel Veillardfdc91562002-07-01 21:52:03 +0000506 if (insert != NULL)
Owen Taylor3473f882001-02-23 17:55:21 +0000507 insert->next = entry;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000508
Owen Taylor3473f882001-02-23 17:55:21 +0000509 table->nbElems++;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000510
511 if (len > MAX_HASH_LEN)
512 xmlHashGrow(table, MAX_HASH_LEN * table->size);
513
Owen Taylor3473f882001-02-23 17:55:21 +0000514 return(0);
515}
516
517/**
518 * xmlHashUpdateEntry3:
519 * @table: the hash table
520 * @name: the name of the userdata
521 * @name2: a second name of the userdata
522 * @name3: a third name of the userdata
523 * @userdata: a pointer to the userdata
524 * @f: the deallocator function for replaced item (if any)
525 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000526 * Add the @userdata to the hash @table. This can later be retrieved
527 * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
Owen Taylor3473f882001-02-23 17:55:21 +0000528 * will be removed and freed with @f if found.
529 *
530 * Returns 0 the addition succeeded and -1 in case of error.
531 */
532int
533xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
534 const xmlChar *name2, const xmlChar *name3,
535 void *userdata, xmlHashDeallocator f) {
536 unsigned long key;
537 xmlHashEntryPtr entry;
538 xmlHashEntryPtr insert;
539
540 if ((table == NULL) || name == NULL)
541 return(-1);
542
543 /*
544 * Check for duplicate and insertion location.
545 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000546 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000547 if (table->table[key].valid == 0) {
Owen Taylor3473f882001-02-23 17:55:21 +0000548 insert = NULL;
549 } else {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000550 for (insert = &(table->table[key]); insert->next != NULL;
Owen Taylor3473f882001-02-23 17:55:21 +0000551 insert = insert->next) {
552 if ((xmlStrEqual(insert->name, name)) &&
553 (xmlStrEqual(insert->name2, name2)) &&
554 (xmlStrEqual(insert->name3, name3))) {
555 if (f)
556 f(insert->payload, insert->name);
557 insert->payload = userdata;
558 return(0);
559 }
560 }
561 if ((xmlStrEqual(insert->name, name)) &&
562 (xmlStrEqual(insert->name2, name2)) &&
563 (xmlStrEqual(insert->name3, name3))) {
564 if (f)
565 f(insert->payload, insert->name);
566 insert->payload = userdata;
567 return(0);
568 }
569 }
570
Daniel Veillardfdc91562002-07-01 21:52:03 +0000571 if (insert == NULL) {
572 entry = &(table->table[key]);
573 } else {
574 entry = xmlMalloc(sizeof(xmlHashEntry));
575 if (entry == NULL)
576 return(-1);
577 }
578
Owen Taylor3473f882001-02-23 17:55:21 +0000579 entry->name = xmlStrdup(name);
580 entry->name2 = xmlStrdup(name2);
581 entry->name3 = xmlStrdup(name3);
582 entry->payload = userdata;
583 entry->next = NULL;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000584 entry->valid = 1;
Owen Taylor3473f882001-02-23 17:55:21 +0000585 table->nbElems++;
586
587
Daniel Veillardfdc91562002-07-01 21:52:03 +0000588 if (insert != NULL) {
Owen Taylor3473f882001-02-23 17:55:21 +0000589 insert->next = entry;
590 }
591 return(0);
592}
593
594/**
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000595 * xmlHashLookup3:
Owen Taylor3473f882001-02-23 17:55:21 +0000596 * @table: the hash table
597 * @name: the name of the userdata
598 * @name2: a second name of the userdata
599 * @name3: a third name of the userdata
600 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000601 * Find the userdata specified by the (@name, @name2, @name3) tuple.
Owen Taylor3473f882001-02-23 17:55:21 +0000602 *
603 * Returns the a pointer to the userdata
604 */
605void *
606xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
607 const xmlChar *name2, const xmlChar *name3) {
608 unsigned long key;
609 xmlHashEntryPtr entry;
610
611 if (table == NULL)
612 return(NULL);
613 if (name == NULL)
614 return(NULL);
Daniel Veillarda10efa82001-04-18 13:09:01 +0000615 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000616 if (table->table[key].valid == 0)
617 return(NULL);
618 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
Owen Taylor3473f882001-02-23 17:55:21 +0000619 if ((xmlStrEqual(entry->name, name)) &&
620 (xmlStrEqual(entry->name2, name2)) &&
621 (xmlStrEqual(entry->name3, name3)))
622 return(entry->payload);
623 }
624 return(NULL);
625}
626
Daniel Veillarde57ec792003-09-10 10:50:59 +0000627/**
628 * xmlHashQLookup3:
629 * @table: the hash table
630 * @prefix: the prefix of the userdata
631 * @name: the name of the userdata
632 * @prefix2: the second prefix of the userdata
633 * @name2: a second name of the userdata
634 * @prefix3: the third prefix of the userdata
635 * @name3: a third name of the userdata
636 *
637 * Find the userdata specified by the (@name, @name2, @name3) tuple.
638 *
639 * Returns the a pointer to the userdata
640 */
641void *
642xmlHashQLookup3(xmlHashTablePtr table,
643 const xmlChar *prefix, const xmlChar *name,
644 const xmlChar *prefix2, const xmlChar *name2,
645 const xmlChar *prefix3, const xmlChar *name3) {
646 unsigned long key;
647 xmlHashEntryPtr entry;
648
649 if (table == NULL)
650 return(NULL);
651 if (name == NULL)
652 return(NULL);
653 key = xmlHashComputeQKey(table, prefix, name, prefix2,
654 name2, prefix3, name3);
655 if (table->table[key].valid == 0)
656 return(NULL);
657 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
658 if ((xmlStrQEqual(prefix, name, entry->name)) &&
659 (xmlStrQEqual(prefix2, name2, entry->name2)) &&
660 (xmlStrQEqual(prefix3, name3, entry->name3)))
661 return(entry->payload);
662 }
663 return(NULL);
664}
665
Daniel Veillard153120c2002-06-18 07:58:35 +0000666typedef struct {
667 xmlHashScanner hashscanner;
668 void *data;
669} stubData;
670
671static void
672stubHashScannerFull (void *payload, void *data, const xmlChar *name,
Daniel Veillardaeb258a2002-09-13 14:48:12 +0000673 const xmlChar *name2 ATTRIBUTE_UNUSED,
674 const xmlChar *name3 ATTRIBUTE_UNUSED) {
Daniel Veillard153120c2002-06-18 07:58:35 +0000675 stubData *stubdata = (stubData *) data;
676 stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
677}
678
Daniel Veillard01c13b52002-12-10 15:19:08 +0000679/**
680 * xmlHashScan:
681 * @table: the hash table
682 * @f: the scanner function for items in the hash
683 * @data: extra data passed to f
684 *
685 * Scan the hash @table and applied @f to each value.
686 */
Owen Taylor3473f882001-02-23 17:55:21 +0000687void
688xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
Daniel Veillard153120c2002-06-18 07:58:35 +0000689 stubData stubdata;
690 stubdata.data = data;
691 stubdata.hashscanner = f;
692 xmlHashScanFull (table, stubHashScannerFull, &stubdata);
Thomas Broyere8126242001-07-22 03:54:15 +0000693}
694
695/**
696 * xmlHashScanFull:
697 * @table: the hash table
698 * @f: the scanner function for items in the hash
699 * @data: extra data passed to f
700 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000701 * Scan the hash @table and applied @f to each value.
Thomas Broyere8126242001-07-22 03:54:15 +0000702 */
703void
704xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
Owen Taylor3473f882001-02-23 17:55:21 +0000705 int i;
706 xmlHashEntryPtr iter;
707 xmlHashEntryPtr next;
708
709 if (table == NULL)
710 return;
711 if (f == NULL)
712 return;
713
714 if (table->table) {
715 for(i = 0; i < table->size; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000716 if (table->table[i].valid == 0)
717 continue;
718 iter = &(table->table[i]);
Owen Taylor3473f882001-02-23 17:55:21 +0000719 while (iter) {
720 next = iter->next;
Daniel Veillarde991fe92003-10-29 11:18:37 +0000721 if ((f != NULL) && (iter->payload != NULL))
Thomas Broyere8126242001-07-22 03:54:15 +0000722 f(iter->payload, data, iter->name,
723 iter->name2, iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000724 iter = next;
725 }
726 }
727 }
728}
729
730/**
731 * xmlHashScan3:
732 * @table: the hash table
733 * @name: the name of the userdata or NULL
734 * @name2: a second name of the userdata or NULL
735 * @name3: a third name of the userdata or NULL
736 * @f: the scanner function for items in the hash
737 * @data: extra data passed to f
738 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000739 * Scan the hash @table and applied @f to each value matching
740 * (@name, @name2, @name3) tuple. If one of the names is null,
Owen Taylor3473f882001-02-23 17:55:21 +0000741 * the comparison is considered to match.
742 */
743void
744xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
745 const xmlChar *name2, const xmlChar *name3,
746 xmlHashScanner f, void *data) {
Thomas Broyere8126242001-07-22 03:54:15 +0000747 xmlHashScanFull3 (table, name, name2, name3,
748 (xmlHashScannerFull) f, data);
749}
750
751/**
752 * xmlHashScanFull3:
753 * @table: the hash table
754 * @name: the name of the userdata or NULL
755 * @name2: a second name of the userdata or NULL
756 * @name3: a third name of the userdata or NULL
757 * @f: the scanner function for items in the hash
758 * @data: extra data passed to f
759 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000760 * Scan the hash @table and applied @f to each value matching
761 * (@name, @name2, @name3) tuple. If one of the names is null,
Thomas Broyere8126242001-07-22 03:54:15 +0000762 * the comparison is considered to match.
763 */
764void
765xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
766 const xmlChar *name2, const xmlChar *name3,
767 xmlHashScannerFull f, void *data) {
Owen Taylor3473f882001-02-23 17:55:21 +0000768 int i;
769 xmlHashEntryPtr iter;
770 xmlHashEntryPtr next;
771
772 if (table == NULL)
773 return;
774 if (f == NULL)
775 return;
776
777 if (table->table) {
778 for(i = 0; i < table->size; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000779 if (table->table[i].valid == 0)
780 continue;
781 iter = &(table->table[i]);
Owen Taylor3473f882001-02-23 17:55:21 +0000782 while (iter) {
783 next = iter->next;
784 if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
785 ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
Daniel Veillarde991fe92003-10-29 11:18:37 +0000786 ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&
787 (iter->payload != NULL)) {
Thomas Broyere8126242001-07-22 03:54:15 +0000788 f(iter->payload, data, iter->name,
789 iter->name2, iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000790 }
791 iter = next;
792 }
793 }
794 }
795}
796
797/**
798 * xmlHashCopy:
799 * @table: the hash table
800 * @f: the copier function for items in the hash
801 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000802 * Scan the hash @table and applied @f to each value.
Owen Taylor3473f882001-02-23 17:55:21 +0000803 *
804 * Returns the new table or NULL in case of error.
805 */
806xmlHashTablePtr
807xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
808 int i;
809 xmlHashEntryPtr iter;
810 xmlHashEntryPtr next;
811 xmlHashTablePtr ret;
812
813 if (table == NULL)
814 return(NULL);
815 if (f == NULL)
816 return(NULL);
817
818 ret = xmlHashCreate(table->size);
819 if (table->table) {
820 for(i = 0; i < table->size; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000821 if (table->table[i].valid == 0)
822 continue;
823 iter = &(table->table[i]);
Owen Taylor3473f882001-02-23 17:55:21 +0000824 while (iter) {
825 next = iter->next;
826 xmlHashAddEntry3(ret, iter->name, iter->name2,
827 iter->name3, f(iter->payload, iter->name));
828 iter = next;
829 }
830 }
831 }
832 ret->nbElems = table->nbElems;
833 return(ret);
834}
835
836/**
837 * xmlHashSize:
838 * @table: the hash table
839 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000840 * Query the number of elements installed in the hash @table.
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000841 *
Owen Taylor3473f882001-02-23 17:55:21 +0000842 * Returns the number of elements in the hash table or
843 * -1 in case of error
844 */
845int
846xmlHashSize(xmlHashTablePtr table) {
847 if (table == NULL)
848 return(-1);
849 return(table->nbElems);
850}
851
852/**
Daniel Veillardf69bb4b2001-05-19 13:24:56 +0000853 * xmlHashRemoveEntry:
Owen Taylor3473f882001-02-23 17:55:21 +0000854 * @table: the hash table
855 * @name: the name of the userdata
856 * @f: the deallocator function for removed item (if any)
857 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000858 * Find the userdata specified by the @name and remove
859 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000860 * and freed with @f.
861 *
862 * Returns 0 if the removal succeeded and -1 in case of error or not found.
863 */
864int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +0000865 xmlHashDeallocator f) {
866 return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
Owen Taylor3473f882001-02-23 17:55:21 +0000867}
868
869/**
Daniel Veillardf69bb4b2001-05-19 13:24:56 +0000870 * xmlHashRemoveEntry2:
Owen Taylor3473f882001-02-23 17:55:21 +0000871 * @table: the hash table
872 * @name: the name of the userdata
873 * @name2: a second name of the userdata
874 * @f: the deallocator function for removed item (if any)
875 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000876 * Find the userdata specified by the (@name, @name2) tuple and remove
877 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000878 * and freed with @f.
879 *
880 * Returns 0 if the removal succeeded and -1 in case of error or not found.
881 */
Daniel Veillard01c13b52002-12-10 15:19:08 +0000882int
883xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +0000884 const xmlChar *name2, xmlHashDeallocator f) {
885 return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
Owen Taylor3473f882001-02-23 17:55:21 +0000886}
887
888/**
Daniel Veillard01c13b52002-12-10 15:19:08 +0000889 * xmlHashRemoveEntry3:
Owen Taylor3473f882001-02-23 17:55:21 +0000890 * @table: the hash table
891 * @name: the name of the userdata
892 * @name2: a second name of the userdata
893 * @name3: a third name of the userdata
894 * @f: the deallocator function for removed item (if any)
895 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000896 * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
897 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000898 * and freed with @f.
899 *
900 * Returns 0 if the removal succeeded and -1 in case of error or not found.
901 */
Daniel Veillard01c13b52002-12-10 15:19:08 +0000902int
903xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +0000904 const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
905 unsigned long key;
906 xmlHashEntryPtr entry;
907 xmlHashEntryPtr prev = NULL;
Owen Taylor3473f882001-02-23 17:55:21 +0000908
Daniel Veillarda10efa82001-04-18 13:09:01 +0000909 if (table == NULL || name == NULL)
910 return(-1);
Owen Taylor3473f882001-02-23 17:55:21 +0000911
Daniel Veillarda10efa82001-04-18 13:09:01 +0000912 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000913 if (table->table[key].valid == 0) {
Daniel Veillarda10efa82001-04-18 13:09:01 +0000914 return(-1);
915 } else {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000916 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
Daniel Veillarda10efa82001-04-18 13:09:01 +0000917 if (xmlStrEqual(entry->name, name) &&
918 xmlStrEqual(entry->name2, name2) &&
919 xmlStrEqual(entry->name3, name3)) {
Daniel Veillarde991fe92003-10-29 11:18:37 +0000920 if ((f != NULL) && (entry->payload != NULL))
Daniel Veillarda10efa82001-04-18 13:09:01 +0000921 f(entry->payload, entry->name);
922 entry->payload = NULL;
923 if(entry->name)
924 xmlFree(entry->name);
925 if(entry->name2)
926 xmlFree(entry->name2);
927 if(entry->name3)
928 xmlFree(entry->name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000929 if(prev) {
Daniel Veillarda10efa82001-04-18 13:09:01 +0000930 prev->next = entry->next;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000931 xmlFree(entry);
932 } else {
933 if (entry->next == NULL) {
934 entry->valid = 0;
935 } else {
936 entry = entry->next;
937 memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
938 xmlFree(entry);
939 }
940 }
Daniel Veillarda10efa82001-04-18 13:09:01 +0000941 table->nbElems--;
942 return(0);
943 }
944 prev = entry;
945 }
946 return(-1);
947 }
Daniel Veillard9e7160d2001-03-18 23:17:47 +0000948}
949