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