blob: e92a5a040b2d2602215ea4cf9d0acda57c40f926 [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;
Daniel Veillard316a5c32005-01-23 22:56:39 +000055 xmlDictPtr dict;
Owen Taylor3473f882001-02-23 17:55:21 +000056};
57
58/*
59 * xmlHashComputeKey:
60 * Calculate the hash key
61 */
62static unsigned long
Daniel Veillarda10efa82001-04-18 13:09:01 +000063xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
64 const xmlChar *name2, const xmlChar *name3) {
Owen Taylor3473f882001-02-23 17:55:21 +000065 unsigned long value = 0L;
66 char ch;
67
Daniel Veillarda10efa82001-04-18 13:09:01 +000068 if (name != NULL) {
69 value += 30 * (*name);
70 while ((ch = *name++) != 0) {
Daniel Veillard5f7f9912002-06-17 17:03:00 +000071 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
Daniel Veillarda10efa82001-04-18 13:09:01 +000072 }
73 }
74 if (name2 != NULL) {
75 while ((ch = *name2++) != 0) {
Daniel Veillard5f7f9912002-06-17 17:03:00 +000076 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
Daniel Veillarda10efa82001-04-18 13:09:01 +000077 }
78 }
79 if (name3 != NULL) {
80 while ((ch = *name3++) != 0) {
Daniel Veillard5f7f9912002-06-17 17:03:00 +000081 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
Daniel Veillarda10efa82001-04-18 13:09:01 +000082 }
Owen Taylor3473f882001-02-23 17:55:21 +000083 }
84 return (value % table->size);
85}
86
Daniel Veillarde57ec792003-09-10 10:50:59 +000087static unsigned long
88xmlHashComputeQKey(xmlHashTablePtr table,
Daniel Veillard8e36e6a2003-09-10 10:50:59 +000089 const xmlChar *prefix, const xmlChar *name,
90 const xmlChar *prefix2, const xmlChar *name2,
91 const xmlChar *prefix3, const xmlChar *name3) {
Daniel Veillarde57ec792003-09-10 10:50:59 +000092 unsigned long value = 0L;
93 char ch;
94
95 if (prefix != NULL)
96 value += 30 * (*prefix);
97 else
98 value += 30 * (*name);
99
100 if (prefix != NULL) {
101 while ((ch = *prefix++) != 0) {
102 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
103 }
104 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
105 }
106 if (name != NULL) {
107 while ((ch = *name++) != 0) {
108 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
109 }
110 }
111 if (prefix2 != NULL) {
112 while ((ch = *prefix2++) != 0) {
113 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
114 }
115 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
116 }
117 if (name2 != NULL) {
118 while ((ch = *name2++) != 0) {
119 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
120 }
121 }
122 if (prefix3 != NULL) {
123 while ((ch = *prefix3++) != 0) {
124 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
125 }
126 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
127 }
128 if (name3 != NULL) {
129 while ((ch = *name3++) != 0) {
130 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
131 }
132 }
133 return (value % table->size);
134}
135
Owen Taylor3473f882001-02-23 17:55:21 +0000136/**
137 * xmlHashCreate:
138 * @size: the size of the hash table
139 *
140 * Create a new xmlHashTablePtr.
141 *
142 * Returns the newly created object, or NULL if an error occured.
143 */
144xmlHashTablePtr
145xmlHashCreate(int size) {
146 xmlHashTablePtr table;
147
148 if (size <= 0)
149 size = 256;
150
151 table = xmlMalloc(sizeof(xmlHashTable));
152 if (table) {
Daniel Veillard316a5c32005-01-23 22:56:39 +0000153 table->dict = NULL;
Owen Taylor3473f882001-02-23 17:55:21 +0000154 table->size = size;
155 table->nbElems = 0;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000156 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
Owen Taylor3473f882001-02-23 17:55:21 +0000157 if (table->table) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000158 memset(table->table, 0, size * sizeof(xmlHashEntry));
Owen Taylor3473f882001-02-23 17:55:21 +0000159 return(table);
160 }
161 xmlFree(table);
162 }
163 return(NULL);
164}
165
166/**
Daniel Veillard316a5c32005-01-23 22:56:39 +0000167 * xmlHashCreateDict:
168 * @size: the size of the hash table
169 * @dict: a dictionary to use for the hash
170 *
171 * Create a new xmlHashTablePtr which will use @dict as the internal dictionary
172 *
173 * Returns the newly created object, or NULL if an error occured.
174 */
175xmlHashTablePtr
176xmlHashCreateDict(int size, xmlDictPtr dict) {
177 xmlHashTablePtr table;
178
179 table = xmlHashCreate(size);
180 if (table != NULL) {
181 table->dict = dict;
182 xmlDictReference(dict);
183 }
184 return(table);
185}
186
187/**
Daniel Veillarda10efa82001-04-18 13:09:01 +0000188 * xmlHashGrow:
189 * @table: the hash table
190 * @size: the new size of the hash table
191 *
192 * resize the hash table
193 *
194 * Returns 0 in case of success, -1 in case of failure
195 */
Daniel Veillarddab4cb32001-04-20 13:03:48 +0000196static int
Daniel Veillarda10efa82001-04-18 13:09:01 +0000197xmlHashGrow(xmlHashTablePtr table, int size) {
198 unsigned long key;
199 int oldsize, i;
200 xmlHashEntryPtr iter, next;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000201 struct _xmlHashEntry *oldtable;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000202#ifdef DEBUG_GROW
203 unsigned long nbElem = 0;
204#endif
205
206 if (table == NULL)
207 return(-1);
208 if (size < 8)
209 return(-1);
210 if (size > 8 * 2048)
211 return(-1);
212
213 oldsize = table->size;
214 oldtable = table->table;
215 if (oldtable == NULL)
216 return(-1);
217
Daniel Veillardfdc91562002-07-01 21:52:03 +0000218 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
Daniel Veillarda10efa82001-04-18 13:09:01 +0000219 if (table->table == NULL) {
220 table->table = oldtable;
221 return(-1);
222 }
Daniel Veillardfdc91562002-07-01 21:52:03 +0000223 memset(table->table, 0, size * sizeof(xmlHashEntry));
Daniel Veillarda10efa82001-04-18 13:09:01 +0000224 table->size = size;
225
Daniel Veillardfdc91562002-07-01 21:52:03 +0000226 /* If the two loops are merged, there would be situations where
227 a new entry needs to allocated and data copied into it from
228 the main table. So instead, we run through the array twice, first
229 copying all the elements in the main array (where we can't get
230 conflicts) and then the rest, so we only free (and don't allocate)
231 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000232 for (i = 0; i < oldsize; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000233 if (oldtable[i].valid == 0)
234 continue;
235 key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
236 oldtable[i].name3);
237 memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
238 table->table[key].next = NULL;
239 }
240
241 for (i = 0; i < oldsize; i++) {
242 iter = oldtable[i].next;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000243 while (iter) {
244 next = iter->next;
245
246 /*
247 * put back the entry in the new table
248 */
249
250 key = xmlHashComputeKey(table, iter->name, iter->name2,
251 iter->name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000252 if (table->table[key].valid == 0) {
253 memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
254 table->table[key].next = NULL;
255 xmlFree(iter);
256 } else {
257 iter->next = table->table[key].next;
258 table->table[key].next = iter;
259 }
Daniel Veillarda10efa82001-04-18 13:09:01 +0000260
261#ifdef DEBUG_GROW
262 nbElem++;
263#endif
264
265 iter = next;
266 }
267 }
268
269 xmlFree(oldtable);
270
271#ifdef DEBUG_GROW
272 xmlGenericError(xmlGenericErrorContext,
273 "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
274#endif
275
276 return(0);
277}
278
279/**
Owen Taylor3473f882001-02-23 17:55:21 +0000280 * xmlHashFree:
281 * @table: the hash table
282 * @f: the deallocator function for items in the hash
283 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000284 * Free the hash @table and its contents. The userdata is
285 * deallocated with @f if provided.
Owen Taylor3473f882001-02-23 17:55:21 +0000286 */
287void
288xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
289 int i;
290 xmlHashEntryPtr iter;
291 xmlHashEntryPtr next;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000292 int inside_table = 0;
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000293 int nbElems;
Owen Taylor3473f882001-02-23 17:55:21 +0000294
295 if (table == NULL)
296 return;
297 if (table->table) {
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000298 nbElems = table->nbElems;
299 for(i = 0; (i < table->size) && (nbElems > 0); i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000300 iter = &(table->table[i]);
301 if (iter->valid == 0)
302 continue;
303 inside_table = 1;
Owen Taylor3473f882001-02-23 17:55:21 +0000304 while (iter) {
305 next = iter->next;
Daniel Veillarde991fe92003-10-29 11:18:37 +0000306 if ((f != NULL) && (iter->payload != NULL))
Daniel Veillarda10efa82001-04-18 13:09:01 +0000307 f(iter->payload, iter->name);
Daniel Veillard316a5c32005-01-23 22:56:39 +0000308 if (table->dict == NULL) {
309 if (iter->name)
310 xmlFree(iter->name);
311 if (iter->name2)
312 xmlFree(iter->name2);
313 if (iter->name3)
314 xmlFree(iter->name3);
315 }
Owen Taylor3473f882001-02-23 17:55:21 +0000316 iter->payload = NULL;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000317 if (!inside_table)
318 xmlFree(iter);
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000319 nbElems--;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000320 inside_table = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000321 iter = next;
322 }
Daniel Veillardfdc91562002-07-01 21:52:03 +0000323 inside_table = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000324 }
325 xmlFree(table->table);
326 }
Daniel Veillard316a5c32005-01-23 22:56:39 +0000327 if (table->dict)
328 xmlDictFree(table->dict);
Owen Taylor3473f882001-02-23 17:55:21 +0000329 xmlFree(table);
330}
331
332/**
333 * xmlHashAddEntry:
334 * @table: the hash table
335 * @name: the name of the userdata
336 * @userdata: a pointer to the userdata
337 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000338 * Add the @userdata to the hash @table. This can later be retrieved
339 * by using the @name. Duplicate names generate errors.
Owen Taylor3473f882001-02-23 17:55:21 +0000340 *
341 * Returns 0 the addition succeeded and -1 in case of error.
342 */
343int
344xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
345 return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
346}
347
348/**
349 * xmlHashAddEntry2:
350 * @table: the hash table
351 * @name: the name of the userdata
352 * @name2: a second name of the userdata
353 * @userdata: a pointer to the userdata
354 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000355 * Add the @userdata to the hash @table. This can later be retrieved
356 * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
Owen Taylor3473f882001-02-23 17:55:21 +0000357 *
358 * Returns 0 the addition succeeded and -1 in case of error.
359 */
360int
361xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
362 const xmlChar *name2, void *userdata) {
363 return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
364}
365
366/**
367 * xmlHashUpdateEntry:
368 * @table: the hash table
369 * @name: the name of the userdata
370 * @userdata: a pointer to the userdata
371 * @f: the deallocator function for replaced item (if any)
372 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000373 * Add the @userdata to the hash @table. This can later be retrieved
374 * by using the @name. Existing entry for this @name will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000375 * and freed with @f if found.
376 *
377 * Returns 0 the addition succeeded and -1 in case of error.
378 */
379int
380xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
381 void *userdata, xmlHashDeallocator f) {
382 return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
383}
384
385/**
386 * xmlHashUpdateEntry2:
387 * @table: the hash table
388 * @name: the name of the userdata
389 * @name2: a second name of the userdata
390 * @userdata: a pointer to the userdata
391 * @f: the deallocator function for replaced item (if any)
392 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000393 * Add the @userdata to the hash @table. This can later be retrieved
394 * by using the (@name, @name2) tuple. Existing entry for this tuple will
Owen Taylor3473f882001-02-23 17:55:21 +0000395 * be removed and freed with @f if found.
396 *
397 * Returns 0 the addition succeeded and -1 in case of error.
398 */
399int
400xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
401 const xmlChar *name2, void *userdata,
402 xmlHashDeallocator f) {
403 return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
404}
405
406/**
407 * xmlHashLookup:
408 * @table: the hash table
409 * @name: the name of the userdata
410 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000411 * Find the userdata specified by the @name.
Owen Taylor3473f882001-02-23 17:55:21 +0000412 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000413 * Returns the pointer to the userdata
Owen Taylor3473f882001-02-23 17:55:21 +0000414 */
415void *
416xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
417 return(xmlHashLookup3(table, name, NULL, NULL));
418}
419
420/**
421 * xmlHashLookup2:
422 * @table: the hash table
423 * @name: the name of the userdata
424 * @name2: a second name of the userdata
425 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000426 * Find the userdata specified by the (@name, @name2) tuple.
Owen Taylor3473f882001-02-23 17:55:21 +0000427 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000428 * Returns the pointer to the userdata
Owen Taylor3473f882001-02-23 17:55:21 +0000429 */
430void *
431xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
432 const xmlChar *name2) {
433 return(xmlHashLookup3(table, name, name2, NULL));
434}
435
436/**
Daniel Veillarde57ec792003-09-10 10:50:59 +0000437 * xmlHashQLookup:
438 * @table: the hash table
439 * @prefix: the prefix of the userdata
440 * @name: the name of the userdata
441 *
442 * Find the userdata specified by the QName @prefix:@name/@name.
443 *
444 * Returns the pointer to the userdata
445 */
446void *
447xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,
448 const xmlChar *name) {
449 return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));
450}
451
452/**
Daniel Veillard7a02cfe2003-09-25 12:18:34 +0000453 * xmlHashQLookup2:
Daniel Veillarde57ec792003-09-10 10:50:59 +0000454 * @table: the hash table
455 * @prefix: the prefix of the userdata
456 * @name: the name of the userdata
Daniel Veillard092643b2003-09-25 14:29:29 +0000457 * @prefix2: the second prefix of the userdata
Daniel Veillarde57ec792003-09-10 10:50:59 +0000458 * @name2: a second name of the userdata
459 *
460 * Find the userdata specified by the QNames tuple
461 *
462 * Returns the pointer to the userdata
463 */
464void *
465xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,
466 const xmlChar *name, const xmlChar *prefix2,
467 const xmlChar *name2) {
468 return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
469}
470
471/**
Owen Taylor3473f882001-02-23 17:55:21 +0000472 * xmlHashAddEntry3:
473 * @table: the hash table
474 * @name: the name of the userdata
475 * @name2: a second name of the userdata
476 * @name3: a third name of the userdata
477 * @userdata: a pointer to the userdata
478 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000479 * Add the @userdata to the hash @table. This can later be retrieved
480 * by using the tuple (@name, @name2, @name3). Duplicate entries generate
Owen Taylor3473f882001-02-23 17:55:21 +0000481 * errors.
482 *
483 * Returns 0 the addition succeeded and -1 in case of error.
484 */
485int
486xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
487 const xmlChar *name2, const xmlChar *name3,
488 void *userdata) {
Daniel Veillarda10efa82001-04-18 13:09:01 +0000489 unsigned long key, len = 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000490 xmlHashEntryPtr entry;
491 xmlHashEntryPtr insert;
492
Daniel Veillard316a5c32005-01-23 22:56:39 +0000493 if ((table == NULL) || (name == NULL))
Owen Taylor3473f882001-02-23 17:55:21 +0000494 return(-1);
495
496 /*
Daniel Veillard316a5c32005-01-23 22:56:39 +0000497 * If using a dict internalize if needed
498 */
499 if (table->dict) {
500 if (!xmlDictOwns(table->dict, name)) {
501 name = xmlDictLookup(table->dict, name, -1);
502 if (name == NULL)
503 return(-1);
504 }
505 if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
506 name2 = xmlDictLookup(table->dict, name2, -1);
507 if (name2 == NULL)
508 return(-1);
509 }
510 if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
511 name3 = xmlDictLookup(table->dict, name3, -1);
512 if (name3 == NULL)
513 return(-1);
514 }
515 }
516
517 /*
Owen Taylor3473f882001-02-23 17:55:21 +0000518 * Check for duplicate and insertion location.
519 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000520 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000521 if (table->table[key].valid == 0) {
Owen Taylor3473f882001-02-23 17:55:21 +0000522 insert = NULL;
523 } else {
Daniel Veillard316a5c32005-01-23 22:56:39 +0000524 if (table->dict) {
525 for (insert = &(table->table[key]); insert->next != NULL;
526 insert = insert->next) {
527 if ((insert->name == name) &&
528 (insert->name2 == name2) &&
529 (insert->name3 == name3))
530 return(-1);
531 len++;
532 }
533 if ((insert->name == name) &&
534 (insert->name2 == name2) &&
535 (insert->name3 == name3))
536 return(-1);
537 } else {
538 for (insert = &(table->table[key]); insert->next != NULL;
539 insert = insert->next) {
540 if ((xmlStrEqual(insert->name, name)) &&
541 (xmlStrEqual(insert->name2, name2)) &&
542 (xmlStrEqual(insert->name3, name3)))
543 return(-1);
544 len++;
545 }
Owen Taylor3473f882001-02-23 17:55:21 +0000546 if ((xmlStrEqual(insert->name, name)) &&
547 (xmlStrEqual(insert->name2, name2)) &&
548 (xmlStrEqual(insert->name3, name3)))
549 return(-1);
550 }
Owen Taylor3473f882001-02-23 17:55:21 +0000551 }
552
Daniel Veillardfdc91562002-07-01 21:52:03 +0000553 if (insert == NULL) {
554 entry = &(table->table[key]);
555 } else {
556 entry = xmlMalloc(sizeof(xmlHashEntry));
557 if (entry == NULL)
558 return(-1);
559 }
560
Daniel Veillard316a5c32005-01-23 22:56:39 +0000561 if (table->dict != NULL) {
562 entry->name = (xmlChar *) name;
563 entry->name2 = (xmlChar *) name2;
564 entry->name3 = (xmlChar *) name3;
565 } else {
566 entry->name = xmlStrdup(name);
567 entry->name2 = xmlStrdup(name2);
568 entry->name3 = xmlStrdup(name3);
569 }
Owen Taylor3473f882001-02-23 17:55:21 +0000570 entry->payload = userdata;
571 entry->next = NULL;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000572 entry->valid = 1;
Owen Taylor3473f882001-02-23 17:55:21 +0000573
574
Daniel Veillardfdc91562002-07-01 21:52:03 +0000575 if (insert != NULL)
Owen Taylor3473f882001-02-23 17:55:21 +0000576 insert->next = entry;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000577
Owen Taylor3473f882001-02-23 17:55:21 +0000578 table->nbElems++;
Daniel Veillarda10efa82001-04-18 13:09:01 +0000579
580 if (len > MAX_HASH_LEN)
581 xmlHashGrow(table, MAX_HASH_LEN * table->size);
582
Owen Taylor3473f882001-02-23 17:55:21 +0000583 return(0);
584}
585
586/**
587 * xmlHashUpdateEntry3:
588 * @table: the hash table
589 * @name: the name of the userdata
590 * @name2: a second name of the userdata
591 * @name3: a third name of the userdata
592 * @userdata: a pointer to the userdata
593 * @f: the deallocator function for replaced item (if any)
594 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000595 * Add the @userdata to the hash @table. This can later be retrieved
596 * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
Owen Taylor3473f882001-02-23 17:55:21 +0000597 * will be removed and freed with @f if found.
598 *
599 * Returns 0 the addition succeeded and -1 in case of error.
600 */
601int
602xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
603 const xmlChar *name2, const xmlChar *name3,
604 void *userdata, xmlHashDeallocator f) {
605 unsigned long key;
606 xmlHashEntryPtr entry;
607 xmlHashEntryPtr insert;
608
609 if ((table == NULL) || name == NULL)
610 return(-1);
611
612 /*
Daniel Veillard316a5c32005-01-23 22:56:39 +0000613 * If using a dict internalize if needed
614 */
615 if (table->dict) {
616 if (!xmlDictOwns(table->dict, name)) {
617 name = xmlDictLookup(table->dict, name, -1);
618 if (name == NULL)
619 return(-1);
620 }
621 if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
622 name2 = xmlDictLookup(table->dict, name2, -1);
623 if (name2 == NULL)
624 return(-1);
625 }
626 if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
627 name3 = xmlDictLookup(table->dict, name3, -1);
628 if (name3 == NULL)
629 return(-1);
630 }
631 }
632
633 /*
Owen Taylor3473f882001-02-23 17:55:21 +0000634 * Check for duplicate and insertion location.
635 */
Daniel Veillarda10efa82001-04-18 13:09:01 +0000636 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000637 if (table->table[key].valid == 0) {
Owen Taylor3473f882001-02-23 17:55:21 +0000638 insert = NULL;
639 } else {
Daniel Veillard316a5c32005-01-23 22:56:39 +0000640 if (table ->dict) {
641 for (insert = &(table->table[key]); insert->next != NULL;
642 insert = insert->next) {
643 if ((insert->name == name) &&
644 (insert->name2 == name2) &&
645 (insert->name3 == name3)) {
646 if (f)
647 f(insert->payload, insert->name);
648 insert->payload = userdata;
649 return(0);
650 }
651 }
652 if ((insert->name == name) &&
653 (insert->name2 == name2) &&
654 (insert->name3 == name3)) {
655 if (f)
656 f(insert->payload, insert->name);
657 insert->payload = userdata;
658 return(0);
659 }
660 } else {
661 for (insert = &(table->table[key]); insert->next != NULL;
662 insert = insert->next) {
663 if ((xmlStrEqual(insert->name, name)) &&
664 (xmlStrEqual(insert->name2, name2)) &&
665 (xmlStrEqual(insert->name3, name3))) {
666 if (f)
667 f(insert->payload, insert->name);
668 insert->payload = userdata;
669 return(0);
670 }
671 }
Owen Taylor3473f882001-02-23 17:55:21 +0000672 if ((xmlStrEqual(insert->name, name)) &&
673 (xmlStrEqual(insert->name2, name2)) &&
674 (xmlStrEqual(insert->name3, name3))) {
675 if (f)
676 f(insert->payload, insert->name);
677 insert->payload = userdata;
678 return(0);
679 }
680 }
Owen Taylor3473f882001-02-23 17:55:21 +0000681 }
682
Daniel Veillardfdc91562002-07-01 21:52:03 +0000683 if (insert == NULL) {
684 entry = &(table->table[key]);
685 } else {
686 entry = xmlMalloc(sizeof(xmlHashEntry));
687 if (entry == NULL)
688 return(-1);
689 }
690
Daniel Veillard316a5c32005-01-23 22:56:39 +0000691 if (table->dict != NULL) {
692 entry->name = (xmlChar *) name;
693 entry->name2 = (xmlChar *) name2;
694 entry->name3 = (xmlChar *) name3;
695 } else {
696 entry->name = xmlStrdup(name);
697 entry->name2 = xmlStrdup(name2);
698 entry->name3 = xmlStrdup(name3);
699 }
Owen Taylor3473f882001-02-23 17:55:21 +0000700 entry->payload = userdata;
701 entry->next = NULL;
Daniel Veillardfdc91562002-07-01 21:52:03 +0000702 entry->valid = 1;
Owen Taylor3473f882001-02-23 17:55:21 +0000703 table->nbElems++;
704
705
Daniel Veillardfdc91562002-07-01 21:52:03 +0000706 if (insert != NULL) {
Owen Taylor3473f882001-02-23 17:55:21 +0000707 insert->next = entry;
708 }
709 return(0);
710}
711
712/**
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000713 * xmlHashLookup3:
Owen Taylor3473f882001-02-23 17:55:21 +0000714 * @table: the hash table
715 * @name: the name of the userdata
716 * @name2: a second name of the userdata
717 * @name3: a third name of the userdata
718 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000719 * Find the userdata specified by the (@name, @name2, @name3) tuple.
Owen Taylor3473f882001-02-23 17:55:21 +0000720 *
721 * Returns the a pointer to the userdata
722 */
723void *
724xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
725 const xmlChar *name2, const xmlChar *name3) {
726 unsigned long key;
727 xmlHashEntryPtr entry;
728
729 if (table == NULL)
730 return(NULL);
731 if (name == NULL)
732 return(NULL);
Daniel Veillarda10efa82001-04-18 13:09:01 +0000733 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +0000734 if (table->table[key].valid == 0)
735 return(NULL);
Daniel Veillard316a5c32005-01-23 22:56:39 +0000736 if (table->dict) {
737 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
738 if ((entry->name == name) &&
739 (entry->name2 == name2) &&
740 (entry->name3 == name3))
741 return(entry->payload);
742 }
743 }
Daniel Veillardfdc91562002-07-01 21:52:03 +0000744 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
Owen Taylor3473f882001-02-23 17:55:21 +0000745 if ((xmlStrEqual(entry->name, name)) &&
746 (xmlStrEqual(entry->name2, name2)) &&
747 (xmlStrEqual(entry->name3, name3)))
748 return(entry->payload);
749 }
750 return(NULL);
751}
752
Daniel Veillarde57ec792003-09-10 10:50:59 +0000753/**
754 * xmlHashQLookup3:
755 * @table: the hash table
756 * @prefix: the prefix of the userdata
757 * @name: the name of the userdata
758 * @prefix2: the second prefix of the userdata
759 * @name2: a second name of the userdata
760 * @prefix3: the third prefix of the userdata
761 * @name3: a third name of the userdata
762 *
763 * Find the userdata specified by the (@name, @name2, @name3) tuple.
764 *
765 * Returns the a pointer to the userdata
766 */
767void *
768xmlHashQLookup3(xmlHashTablePtr table,
769 const xmlChar *prefix, const xmlChar *name,
770 const xmlChar *prefix2, const xmlChar *name2,
771 const xmlChar *prefix3, const xmlChar *name3) {
772 unsigned long key;
773 xmlHashEntryPtr entry;
774
775 if (table == NULL)
776 return(NULL);
777 if (name == NULL)
778 return(NULL);
779 key = xmlHashComputeQKey(table, prefix, name, prefix2,
780 name2, prefix3, name3);
781 if (table->table[key].valid == 0)
782 return(NULL);
783 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
784 if ((xmlStrQEqual(prefix, name, entry->name)) &&
785 (xmlStrQEqual(prefix2, name2, entry->name2)) &&
786 (xmlStrQEqual(prefix3, name3, entry->name3)))
787 return(entry->payload);
788 }
789 return(NULL);
790}
791
Daniel Veillard153120c2002-06-18 07:58:35 +0000792typedef struct {
793 xmlHashScanner hashscanner;
794 void *data;
795} stubData;
796
797static void
798stubHashScannerFull (void *payload, void *data, const xmlChar *name,
Daniel Veillardaeb258a2002-09-13 14:48:12 +0000799 const xmlChar *name2 ATTRIBUTE_UNUSED,
800 const xmlChar *name3 ATTRIBUTE_UNUSED) {
Daniel Veillard153120c2002-06-18 07:58:35 +0000801 stubData *stubdata = (stubData *) data;
802 stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
803}
804
Daniel Veillard01c13b52002-12-10 15:19:08 +0000805/**
806 * xmlHashScan:
807 * @table: the hash table
808 * @f: the scanner function for items in the hash
809 * @data: extra data passed to f
810 *
811 * Scan the hash @table and applied @f to each value.
812 */
Owen Taylor3473f882001-02-23 17:55:21 +0000813void
814xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
Daniel Veillard153120c2002-06-18 07:58:35 +0000815 stubData stubdata;
816 stubdata.data = data;
817 stubdata.hashscanner = f;
818 xmlHashScanFull (table, stubHashScannerFull, &stubdata);
Thomas Broyere8126242001-07-22 03:54:15 +0000819}
820
821/**
822 * xmlHashScanFull:
823 * @table: the hash table
824 * @f: the scanner function for items in the hash
825 * @data: extra data passed to f
826 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000827 * Scan the hash @table and applied @f to each value.
Thomas Broyere8126242001-07-22 03:54:15 +0000828 */
829void
830xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
Owen Taylor3473f882001-02-23 17:55:21 +0000831 int i;
832 xmlHashEntryPtr iter;
833 xmlHashEntryPtr next;
834
835 if (table == NULL)
836 return;
837 if (f == NULL)
838 return;
839
840 if (table->table) {
841 for(i = 0; i < table->size; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000842 if (table->table[i].valid == 0)
843 continue;
844 iter = &(table->table[i]);
Owen Taylor3473f882001-02-23 17:55:21 +0000845 while (iter) {
846 next = iter->next;
Daniel Veillarde991fe92003-10-29 11:18:37 +0000847 if ((f != NULL) && (iter->payload != NULL))
Thomas Broyere8126242001-07-22 03:54:15 +0000848 f(iter->payload, data, iter->name,
849 iter->name2, iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000850 iter = next;
851 }
852 }
853 }
854}
855
856/**
857 * xmlHashScan3:
858 * @table: the hash table
859 * @name: the name of the userdata or NULL
860 * @name2: a second name of the userdata or NULL
861 * @name3: a third name of the userdata or NULL
862 * @f: the scanner function for items in the hash
863 * @data: extra data passed to f
864 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000865 * Scan the hash @table and applied @f to each value matching
866 * (@name, @name2, @name3) tuple. If one of the names is null,
Owen Taylor3473f882001-02-23 17:55:21 +0000867 * the comparison is considered to match.
868 */
869void
870xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
871 const xmlChar *name2, const xmlChar *name3,
872 xmlHashScanner f, void *data) {
Thomas Broyere8126242001-07-22 03:54:15 +0000873 xmlHashScanFull3 (table, name, name2, name3,
874 (xmlHashScannerFull) f, data);
875}
876
877/**
878 * xmlHashScanFull3:
879 * @table: the hash table
880 * @name: the name of the userdata or NULL
881 * @name2: a second name of the userdata or NULL
882 * @name3: a third name of the userdata or NULL
883 * @f: the scanner function for items in the hash
884 * @data: extra data passed to f
885 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000886 * Scan the hash @table and applied @f to each value matching
887 * (@name, @name2, @name3) tuple. If one of the names is null,
Thomas Broyere8126242001-07-22 03:54:15 +0000888 * the comparison is considered to match.
889 */
890void
891xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
892 const xmlChar *name2, const xmlChar *name3,
893 xmlHashScannerFull f, void *data) {
Owen Taylor3473f882001-02-23 17:55:21 +0000894 int i;
895 xmlHashEntryPtr iter;
896 xmlHashEntryPtr next;
897
898 if (table == NULL)
899 return;
900 if (f == NULL)
901 return;
902
903 if (table->table) {
904 for(i = 0; i < table->size; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000905 if (table->table[i].valid == 0)
906 continue;
907 iter = &(table->table[i]);
Owen Taylor3473f882001-02-23 17:55:21 +0000908 while (iter) {
909 next = iter->next;
910 if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
911 ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
Daniel Veillarde991fe92003-10-29 11:18:37 +0000912 ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&
913 (iter->payload != NULL)) {
Thomas Broyere8126242001-07-22 03:54:15 +0000914 f(iter->payload, data, iter->name,
915 iter->name2, iter->name3);
Owen Taylor3473f882001-02-23 17:55:21 +0000916 }
917 iter = next;
918 }
919 }
920 }
921}
922
923/**
924 * xmlHashCopy:
925 * @table: the hash table
926 * @f: the copier function for items in the hash
927 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000928 * Scan the hash @table and applied @f to each value.
Owen Taylor3473f882001-02-23 17:55:21 +0000929 *
930 * Returns the new table or NULL in case of error.
931 */
932xmlHashTablePtr
933xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
934 int i;
935 xmlHashEntryPtr iter;
936 xmlHashEntryPtr next;
937 xmlHashTablePtr ret;
938
939 if (table == NULL)
940 return(NULL);
941 if (f == NULL)
942 return(NULL);
943
944 ret = xmlHashCreate(table->size);
945 if (table->table) {
946 for(i = 0; i < table->size; i++) {
Daniel Veillardfdc91562002-07-01 21:52:03 +0000947 if (table->table[i].valid == 0)
948 continue;
949 iter = &(table->table[i]);
Owen Taylor3473f882001-02-23 17:55:21 +0000950 while (iter) {
951 next = iter->next;
952 xmlHashAddEntry3(ret, iter->name, iter->name2,
953 iter->name3, f(iter->payload, iter->name));
954 iter = next;
955 }
956 }
957 }
958 ret->nbElems = table->nbElems;
959 return(ret);
960}
961
962/**
963 * xmlHashSize:
964 * @table: the hash table
965 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000966 * Query the number of elements installed in the hash @table.
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000967 *
Owen Taylor3473f882001-02-23 17:55:21 +0000968 * Returns the number of elements in the hash table or
969 * -1 in case of error
970 */
971int
972xmlHashSize(xmlHashTablePtr table) {
973 if (table == NULL)
974 return(-1);
975 return(table->nbElems);
976}
977
978/**
Daniel Veillardf69bb4b2001-05-19 13:24:56 +0000979 * xmlHashRemoveEntry:
Owen Taylor3473f882001-02-23 17:55:21 +0000980 * @table: the hash table
981 * @name: the name of the userdata
982 * @f: the deallocator function for removed item (if any)
983 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +0000984 * Find the userdata specified by the @name and remove
985 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +0000986 * and freed with @f.
987 *
988 * Returns 0 if the removal succeeded and -1 in case of error or not found.
989 */
990int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +0000991 xmlHashDeallocator f) {
992 return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
Owen Taylor3473f882001-02-23 17:55:21 +0000993}
994
995/**
Daniel Veillardf69bb4b2001-05-19 13:24:56 +0000996 * xmlHashRemoveEntry2:
Owen Taylor3473f882001-02-23 17:55:21 +0000997 * @table: the hash table
998 * @name: the name of the userdata
999 * @name2: a second name of the userdata
1000 * @f: the deallocator function for removed item (if any)
1001 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +00001002 * Find the userdata specified by the (@name, @name2) tuple and remove
1003 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +00001004 * and freed with @f.
1005 *
1006 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1007 */
Daniel Veillard01c13b52002-12-10 15:19:08 +00001008int
1009xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +00001010 const xmlChar *name2, xmlHashDeallocator f) {
1011 return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
Owen Taylor3473f882001-02-23 17:55:21 +00001012}
1013
1014/**
Daniel Veillard01c13b52002-12-10 15:19:08 +00001015 * xmlHashRemoveEntry3:
Owen Taylor3473f882001-02-23 17:55:21 +00001016 * @table: the hash table
1017 * @name: the name of the userdata
1018 * @name2: a second name of the userdata
1019 * @name3: a third name of the userdata
1020 * @f: the deallocator function for removed item (if any)
1021 *
Daniel Veillardcbaf3992001-12-31 16:16:02 +00001022 * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
1023 * it from the hash @table. Existing userdata for this tuple will be removed
Owen Taylor3473f882001-02-23 17:55:21 +00001024 * and freed with @f.
1025 *
1026 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1027 */
Daniel Veillard01c13b52002-12-10 15:19:08 +00001028int
1029xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
Daniel Veillarda10efa82001-04-18 13:09:01 +00001030 const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
1031 unsigned long key;
1032 xmlHashEntryPtr entry;
1033 xmlHashEntryPtr prev = NULL;
Owen Taylor3473f882001-02-23 17:55:21 +00001034
Daniel Veillarda10efa82001-04-18 13:09:01 +00001035 if (table == NULL || name == NULL)
1036 return(-1);
Owen Taylor3473f882001-02-23 17:55:21 +00001037
Daniel Veillarda10efa82001-04-18 13:09:01 +00001038 key = xmlHashComputeKey(table, name, name2, name3);
Daniel Veillardfdc91562002-07-01 21:52:03 +00001039 if (table->table[key].valid == 0) {
Daniel Veillarda10efa82001-04-18 13:09:01 +00001040 return(-1);
1041 } else {
Daniel Veillardfdc91562002-07-01 21:52:03 +00001042 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
Daniel Veillarda10efa82001-04-18 13:09:01 +00001043 if (xmlStrEqual(entry->name, name) &&
1044 xmlStrEqual(entry->name2, name2) &&
1045 xmlStrEqual(entry->name3, name3)) {
Daniel Veillarde991fe92003-10-29 11:18:37 +00001046 if ((f != NULL) && (entry->payload != NULL))
Daniel Veillarda10efa82001-04-18 13:09:01 +00001047 f(entry->payload, entry->name);
1048 entry->payload = NULL;
Daniel Veillard316a5c32005-01-23 22:56:39 +00001049 if (table->dict == NULL) {
1050 if(entry->name)
1051 xmlFree(entry->name);
1052 if(entry->name2)
1053 xmlFree(entry->name2);
1054 if(entry->name3)
1055 xmlFree(entry->name3);
1056 }
Daniel Veillardfdc91562002-07-01 21:52:03 +00001057 if(prev) {
Daniel Veillarda10efa82001-04-18 13:09:01 +00001058 prev->next = entry->next;
Daniel Veillardfdc91562002-07-01 21:52:03 +00001059 xmlFree(entry);
1060 } else {
1061 if (entry->next == NULL) {
1062 entry->valid = 0;
1063 } else {
1064 entry = entry->next;
1065 memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
1066 xmlFree(entry);
1067 }
1068 }
Daniel Veillarda10efa82001-04-18 13:09:01 +00001069 table->nbElems--;
1070 return(0);
1071 }
1072 prev = entry;
1073 }
1074 return(-1);
1075 }
Daniel Veillard9e7160d2001-03-18 23:17:47 +00001076}
1077
Daniel Veillard5d4644e2005-04-01 13:11:58 +00001078#define bottom_hash
1079#include "elfgcchack.h"