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