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