blob: 7881fc64eeddf9b5695454080f7b780ac201d51b [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 *
17 * Author: bjorn.reese@systematic.dk
18 */
19
20#ifdef WIN32
21#include "win32config.h"
22#else
23#include "config.h"
24#endif
25
26#include <string.h>
27#include <libxml/hash.h>
28#include <libxml/xmlmemory.h>
29#include <libxml/parser.h>
30
31/*
32 * A single entry in the hash table
33 */
34typedef struct _xmlHashEntry xmlHashEntry;
35typedef xmlHashEntry *xmlHashEntryPtr;
36struct _xmlHashEntry {
37 struct _xmlHashEntry *next;
38 xmlChar *name;
39 xmlChar *name2;
40 xmlChar *name3;
41 void *payload;
42};
43
44/*
45 * The entire hash table
46 */
47struct _xmlHashTable {
48 struct _xmlHashEntry **table;
49 int size;
50 int nbElems;
51};
52
53/*
54 * xmlHashComputeKey:
55 * Calculate the hash key
56 */
57static unsigned long
58xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *string) {
59 unsigned long value = 0L;
60 char ch;
61
62 while ((ch = *string++) != 0) {
63 /* value *= 31; */
64 value += (unsigned long)ch;
65 }
66 return (value % table->size);
67}
68
69/**
70 * xmlHashCreate:
71 * @size: the size of the hash table
72 *
73 * Create a new xmlHashTablePtr.
74 *
75 * Returns the newly created object, or NULL if an error occured.
76 */
77xmlHashTablePtr
78xmlHashCreate(int size) {
79 xmlHashTablePtr table;
80
81 if (size <= 0)
82 size = 256;
83
84 table = xmlMalloc(sizeof(xmlHashTable));
85 if (table) {
86 table->size = size;
87 table->nbElems = 0;
88 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
89 if (table->table) {
90 memset(table->table, 0, size * sizeof(xmlHashEntry));
91 return(table);
92 }
93 xmlFree(table);
94 }
95 return(NULL);
96}
97
98/**
99 * xmlHashFree:
100 * @table: the hash table
101 * @f: the deallocator function for items in the hash
102 *
103 * Free the hash table and its contents. The userdata is
104 * deallocated with f if provided.
105 */
106void
107xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
108 int i;
109 xmlHashEntryPtr iter;
110 xmlHashEntryPtr next;
111
112 if (table == NULL)
113 return;
114 if (table->table) {
115 for(i = 0; i < table->size; i++) {
116 iter = table->table[i];
117 while (iter) {
118 next = iter->next;
119 if (iter->name)
120 xmlFree(iter->name);
121 if (iter->name2)
122 xmlFree(iter->name2);
123 if (iter->name3)
124 xmlFree(iter->name3);
125 if (f)
126 f(iter->payload, iter->name);
127 iter->payload = NULL;
128 xmlFree(iter);
129 iter = next;
130 }
131 table->table[i] = NULL;
132 }
133 xmlFree(table->table);
134 }
135 xmlFree(table);
136}
137
138/**
139 * xmlHashAddEntry:
140 * @table: the hash table
141 * @name: the name of the userdata
142 * @userdata: a pointer to the userdata
143 *
144 * Add the userdata to the hash table. This can later be retrieved
145 * by using the name. Duplicate names generate errors.
146 *
147 * Returns 0 the addition succeeded and -1 in case of error.
148 */
149int
150xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
151 return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
152}
153
154/**
155 * xmlHashAddEntry2:
156 * @table: the hash table
157 * @name: the name of the userdata
158 * @name2: a second name of the userdata
159 * @userdata: a pointer to the userdata
160 *
161 * Add the userdata to the hash table. This can later be retrieved
162 * by using the (name, name2) tuple. Duplicate tuples generate errors.
163 *
164 * Returns 0 the addition succeeded and -1 in case of error.
165 */
166int
167xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
168 const xmlChar *name2, void *userdata) {
169 return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
170}
171
172/**
173 * xmlHashUpdateEntry:
174 * @table: the hash table
175 * @name: the name of the userdata
176 * @userdata: a pointer to the userdata
177 * @f: the deallocator function for replaced item (if any)
178 *
179 * Add the userdata to the hash table. This can later be retrieved
180 * by using the name. Existing entry for this name will be removed
181 * and freed with @f if found.
182 *
183 * Returns 0 the addition succeeded and -1 in case of error.
184 */
185int
186xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
187 void *userdata, xmlHashDeallocator f) {
188 return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
189}
190
191/**
192 * xmlHashUpdateEntry2:
193 * @table: the hash table
194 * @name: the name of the userdata
195 * @name2: a second name of the userdata
196 * @userdata: a pointer to the userdata
197 * @f: the deallocator function for replaced item (if any)
198 *
199 * Add the userdata to the hash table. This can later be retrieved
200 * by using the (name, name2) tuple. Existing entry for this tuple will
201 * be removed and freed with @f if found.
202 *
203 * Returns 0 the addition succeeded and -1 in case of error.
204 */
205int
206xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
207 const xmlChar *name2, void *userdata,
208 xmlHashDeallocator f) {
209 return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
210}
211
212/**
213 * xmlHashLookup:
214 * @table: the hash table
215 * @name: the name of the userdata
216 *
217 * Find the userdata specified by the name.
218 *
219 * Returns the a pointer to the userdata
220 */
221void *
222xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
223 return(xmlHashLookup3(table, name, NULL, NULL));
224}
225
226/**
227 * xmlHashLookup2:
228 * @table: the hash table
229 * @name: the name of the userdata
230 * @name2: a second name of the userdata
231 *
232 * Find the userdata specified by the (name, name2) tuple.
233 *
234 * Returns the a pointer to the userdata
235 */
236void *
237xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
238 const xmlChar *name2) {
239 return(xmlHashLookup3(table, name, name2, NULL));
240}
241
242/**
243 * xmlHashAddEntry3:
244 * @table: the hash table
245 * @name: the name of the userdata
246 * @name2: a second name of the userdata
247 * @name3: a third name of the userdata
248 * @userdata: a pointer to the userdata
249 *
250 * Add the userdata to the hash table. This can later be retrieved
251 * by using the tuple (name, name2, name3). Duplicate entries generate
252 * errors.
253 *
254 * Returns 0 the addition succeeded and -1 in case of error.
255 */
256int
257xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
258 const xmlChar *name2, const xmlChar *name3,
259 void *userdata) {
260 unsigned long key;
261 xmlHashEntryPtr entry;
262 xmlHashEntryPtr insert;
263
264 if ((table == NULL) || name == NULL)
265 return(-1);
266
267 /*
268 * Check for duplicate and insertion location.
269 */
270 key = xmlHashComputeKey(table, name);
271 if (table->table[key] == NULL) {
272 insert = NULL;
273 } else {
274 for (insert = table->table[key]; insert->next != NULL;
275 insert = insert->next) {
276 if ((xmlStrEqual(insert->name, name)) &&
277 (xmlStrEqual(insert->name2, name2)) &&
278 (xmlStrEqual(insert->name3, name3)))
279 return(-1);
280 }
281 if ((xmlStrEqual(insert->name, name)) &&
282 (xmlStrEqual(insert->name2, name2)) &&
283 (xmlStrEqual(insert->name3, name3)))
284 return(-1);
285 }
286
287 entry = xmlMalloc(sizeof(xmlHashEntry));
288 if (entry == NULL)
289 return(-1);
290 entry->name = xmlStrdup(name);
291 entry->name2 = xmlStrdup(name2);
292 entry->name3 = xmlStrdup(name3);
293 entry->payload = userdata;
294 entry->next = NULL;
295
296
297 if (insert == NULL) {
298 table->table[key] = entry;
299 } else {
300 insert->next = entry;
301 }
302 table->nbElems++;
303 return(0);
304}
305
306/**
307 * xmlHashUpdateEntry3:
308 * @table: the hash table
309 * @name: the name of the userdata
310 * @name2: a second name of the userdata
311 * @name3: a third name of the userdata
312 * @userdata: a pointer to the userdata
313 * @f: the deallocator function for replaced item (if any)
314 *
315 * Add the userdata to the hash table. This can later be retrieved
316 * by using the tuple (name, name2, name3). Existing entry for this tuple
317 * will be removed and freed with @f if found.
318 *
319 * Returns 0 the addition succeeded and -1 in case of error.
320 */
321int
322xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
323 const xmlChar *name2, const xmlChar *name3,
324 void *userdata, xmlHashDeallocator f) {
325 unsigned long key;
326 xmlHashEntryPtr entry;
327 xmlHashEntryPtr insert;
328
329 if ((table == NULL) || name == NULL)
330 return(-1);
331
332 /*
333 * Check for duplicate and insertion location.
334 */
335 key = xmlHashComputeKey(table, name);
336 if (table->table[key] == NULL) {
337 insert = NULL;
338 } else {
339 for (insert = table->table[key]; insert->next != NULL;
340 insert = insert->next) {
341 if ((xmlStrEqual(insert->name, name)) &&
342 (xmlStrEqual(insert->name2, name2)) &&
343 (xmlStrEqual(insert->name3, name3))) {
344 if (f)
345 f(insert->payload, insert->name);
346 insert->payload = userdata;
347 return(0);
348 }
349 }
350 if ((xmlStrEqual(insert->name, name)) &&
351 (xmlStrEqual(insert->name2, name2)) &&
352 (xmlStrEqual(insert->name3, name3))) {
353 if (f)
354 f(insert->payload, insert->name);
355 insert->payload = userdata;
356 return(0);
357 }
358 }
359
360 entry = xmlMalloc(sizeof(xmlHashEntry));
361 if (entry == NULL)
362 return(-1);
363 entry->name = xmlStrdup(name);
364 entry->name2 = xmlStrdup(name2);
365 entry->name3 = xmlStrdup(name3);
366 entry->payload = userdata;
367 entry->next = NULL;
368 table->nbElems++;
369
370
371 if (insert == NULL) {
372 table->table[key] = entry;
373 } else {
374 insert->next = entry;
375 }
376 return(0);
377}
378
379/**
380 * xmlHashLookup:
381 * @table: the hash table
382 * @name: the name of the userdata
383 * @name2: a second name of the userdata
384 * @name3: a third name of the userdata
385 *
386 * Find the userdata specified by the (name, name2, name3) tuple.
387 *
388 * Returns the a pointer to the userdata
389 */
390void *
391xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
392 const xmlChar *name2, const xmlChar *name3) {
393 unsigned long key;
394 xmlHashEntryPtr entry;
395
396 if (table == NULL)
397 return(NULL);
398 if (name == NULL)
399 return(NULL);
400 key = xmlHashComputeKey(table, name);
401 for (entry = table->table[key]; entry != NULL; entry = entry->next) {
402 if ((xmlStrEqual(entry->name, name)) &&
403 (xmlStrEqual(entry->name2, name2)) &&
404 (xmlStrEqual(entry->name3, name3)))
405 return(entry->payload);
406 }
407 return(NULL);
408}
409
410/**
411 * xmlHashScan:
412 * @table: the hash table
413 * @f: the scanner function for items in the hash
414 * @data: extra data passed to f
415 *
416 * Scan the hash table and applied f to each value.
417 */
418void
419xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
420 int i;
421 xmlHashEntryPtr iter;
422 xmlHashEntryPtr next;
423
424 if (table == NULL)
425 return;
426 if (f == NULL)
427 return;
428
429 if (table->table) {
430 for(i = 0; i < table->size; i++) {
431 iter = table->table[i];
432 while (iter) {
433 next = iter->next;
434 if (f)
435 f(iter->payload, data, iter->name);
436 iter = next;
437 }
438 }
439 }
440}
441
442/**
443 * xmlHashScan3:
444 * @table: the hash table
445 * @name: the name of the userdata or NULL
446 * @name2: a second name of the userdata or NULL
447 * @name3: a third name of the userdata or NULL
448 * @f: the scanner function for items in the hash
449 * @data: extra data passed to f
450 *
451 * Scan the hash table and applied f to each value matching
452 * (name, name2, name3) tuple. If one of the names is null,
453 * the comparison is considered to match.
454 */
455void
456xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
457 const xmlChar *name2, const xmlChar *name3,
458 xmlHashScanner f, void *data) {
459 int i;
460 xmlHashEntryPtr iter;
461 xmlHashEntryPtr next;
462
463 if (table == NULL)
464 return;
465 if (f == NULL)
466 return;
467
468 if (table->table) {
469 for(i = 0; i < table->size; i++) {
470 iter = table->table[i];
471 while (iter) {
472 next = iter->next;
473 if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
474 ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
475 ((name3 == NULL) || (xmlStrEqual(name3, iter->name3)))) {
476 f(iter->payload, data, iter->name);
477 }
478 iter = next;
479 }
480 }
481 }
482}
483
484/**
485 * xmlHashCopy:
486 * @table: the hash table
487 * @f: the copier function for items in the hash
488 *
489 * Scan the hash table and applied f to each value.
490 *
491 * Returns the new table or NULL in case of error.
492 */
493xmlHashTablePtr
494xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
495 int i;
496 xmlHashEntryPtr iter;
497 xmlHashEntryPtr next;
498 xmlHashTablePtr ret;
499
500 if (table == NULL)
501 return(NULL);
502 if (f == NULL)
503 return(NULL);
504
505 ret = xmlHashCreate(table->size);
506 if (table->table) {
507 for(i = 0; i < table->size; i++) {
508 iter = table->table[i];
509 while (iter) {
510 next = iter->next;
511 xmlHashAddEntry3(ret, iter->name, iter->name2,
512 iter->name3, f(iter->payload, iter->name));
513 iter = next;
514 }
515 }
516 }
517 ret->nbElems = table->nbElems;
518 return(ret);
519}
520
521/**
522 * xmlHashSize:
523 * @table: the hash table
524 *
525 * Returns the number of elements in the hash table or
526 * -1 in case of error
527 */
528int
529xmlHashSize(xmlHashTablePtr table) {
530 if (table == NULL)
531 return(-1);
532 return(table->nbElems);
533}
534
535/**
536 * @table: the hash table
537 * @name: the name of the userdata
538 * @f: the deallocator function for removed item (if any)
539 *
540 * Find the userdata specified by the (name, name2, name3) tuple and remove
541 * it from the hash table. Existing userdata for this tuple will be removed
542 * and freed with @f.
543 *
544 * Returns 0 if the removal succeeded and -1 in case of error or not found.
545 */
546int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
547 xmlHashDeallocator f) {
548 return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
549}
550
551/**
552 * @table: the hash table
553 * @name: the name of the userdata
554 * @name2: a second name of the userdata
555 * @f: the deallocator function for removed item (if any)
556 *
557 * Find the userdata specified by the (name, name2, name3) tuple and remove
558 * it from the hash table. Existing userdata for this tuple will be removed
559 * and freed with @f.
560 *
561 * Returns 0 if the removal succeeded and -1 in case of error or not found.
562 */
563int xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
564 const xmlChar *name2, xmlHashDeallocator f) {
565 return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
566}
567
568/**
569 * @table: the hash table
570 * @name: the name of the userdata
571 * @name2: a second name of the userdata
572 * @name3: a third name of the userdata
573 * @f: the deallocator function for removed item (if any)
574 *
575 * Find the userdata specified by the (name, name2, name3) tuple and remove
576 * it from the hash table. Existing userdata for this tuple will be removed
577 * and freed with @f.
578 *
579 * Returns 0 if the removal succeeded and -1 in case of error or not found.
580 */
581int xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
582 const xmlChar *name2, const xmlChar *name3,
583 xmlHashDeallocator f) {
584 unsigned long key;
585 xmlHashEntryPtr entry;
586 xmlHashEntryPtr prev = NULL;
587
588 if (table == NULL || name == NULL)
589 return(-1);
590
591 key = xmlHashComputeKey(table, name);
592 if (table->table[key] == NULL) {
593 return(-1);
594 } else {
595 for (entry = table->table[key]; entry != NULL; entry = entry->next) {
596 if (xmlStrEqual(entry->name, name) &&
597 xmlStrEqual(entry->name2, name2) &&
598 xmlStrEqual(entry->name3, name3)) {
599 if(f)
600 f(entry->payload, entry->name);
601 entry->payload = NULL;
602 if(entry->name)
603 xmlFree(entry->name);
604 if(entry->name2)
605 xmlFree(entry->name2);
606 if(entry->name3)
607 xmlFree(entry->name3);
608 if(prev)
609 prev->next = entry->next;
610 else
611 table->table[key] = entry->next;
612 xmlFree(entry);
613 table->nbElems--;
614 return(0);
615 }
616 prev = entry;
617 }
618 return(-1);
619 }
620}