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