Annotation of XML/hash.c, revision 1.2
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) {
117: unsigned long key;
118: xmlHashEntryPtr entry;
119: xmlHashEntryPtr insert;
120:
121: if ((table == NULL) || name == NULL)
122: return(-1);
123:
124: /*
125: * Check for duplicate and insertion location.
126: */
127: key = xmlHashComputeKey(table, name);
128: if (table->table[key] == NULL) {
129: insert = NULL;
130: } else {
131: for (insert = table->table[key]; insert->next != NULL;
132: insert = insert->next) {
133: if (xmlStrEqual(insert->name, name))
134: return(-1);
135: }
136: if (xmlStrEqual(insert->name, name))
137: return(-1);
138: }
139:
140: entry = xmlMalloc(sizeof(xmlHashEntry));
141: if (entry == NULL)
142: return(-1);
143: entry->name = xmlStrdup(name);
144: entry->payload = userdata;
145: entry->next = NULL;
146:
147:
148: if (insert == NULL) {
149: table->table[key] = entry;
150: } else {
151: insert->next = entry;
152: }
153: return(0);
154: }
155:
156: /**
157: * xmlHashUpdateEntry:
158: * @table: the hash table
159: * @name: the name of the userdata
160: * @userdata: a pointer to the userdata
161: * @f: the deallocator function for replaced item (if any)
162: *
163: * Add the userdata to the hash table. This can later be retrieved
164: * by using the name. Existing entry for this name will be removed
165: * and freed with @f if found.
166: *
167: * Returns 0 the addition succeeded and -1 in case of error.
168: */
169: int
170: xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
171: void *userdata, xmlHashDeallocator f) {
172: unsigned long key;
173: xmlHashEntryPtr entry;
174: xmlHashEntryPtr insert;
175:
176: if ((table == NULL) || name == NULL)
177: return(-1);
178:
179: /*
180: * Check for duplicate and insertion location.
181: */
182: key = xmlHashComputeKey(table, name);
183: if (table->table[key] == NULL) {
184: insert = NULL;
185: } else {
186: for (insert = table->table[key]; insert->next != NULL;
187: insert = insert->next) {
188: if (xmlStrEqual(insert->name, name)) {
189: if (f)
190: f(insert->payload);
191: insert->payload = userdata;
192: return(0);
193: }
194: }
195: if (xmlStrEqual(insert->name, name)) {
196: if (f)
197: f(insert->payload);
198: insert->payload = userdata;
199: return(0);
200: }
201: }
202:
203: entry = xmlMalloc(sizeof(xmlHashEntry));
204: if (entry == NULL)
205: return(-1);
206: entry->name = xmlStrdup(name);
207: entry->payload = userdata;
208: entry->next = NULL;
209:
210:
211: if (insert == NULL) {
212: table->table[key] = entry;
213: } else {
214: insert->next = entry;
215: }
216: return(0);
217: }
218:
219: /**
220: * xmlHashLookup:
221: * @table: the hash table
222: * @name: the name of the userdata
223: *
224: * Find the userdata specified by the name.
225: *
226: * Returns the a pointer to the userdata
227: */
228: void *
229: xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
230: unsigned long key;
231: xmlHashEntryPtr entry;
232:
233: if (table == NULL)
234: return(NULL);
235: if (name == NULL)
236: return(NULL);
237: key = xmlHashComputeKey(table, name);
238: for (entry = table->table[key]; entry != NULL; entry = entry->next) {
239: if (xmlStrEqual(name, entry->name))
240: return(entry->payload);
241: }
242: return(NULL);
243: }
1.2 ! veillard 244:
! 245: /**
! 246: * xmlHashScan:
! 247: * @table: the hash table
! 248: * @f: the scanner function for items in the hash
! 249: * @data: extra data passed to f
! 250: *
! 251: * Scan the hash table and applied f to each value.
! 252: */
! 253: void
! 254: xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
! 255: int i;
! 256: xmlHashEntryPtr iter;
! 257: xmlHashEntryPtr next;
! 258:
! 259: if (table == NULL)
! 260: return;
! 261: if (f == NULL)
! 262: return;
! 263:
! 264: if (table->table) {
! 265: for(i = 0; i < table->size; i++) {
! 266: iter = table->table[i];
! 267: while (iter) {
! 268: next = iter->next;
! 269: if (f)
! 270: f(iter->payload, data);
! 271: iter = next;
! 272: }
! 273: }
! 274: }
! 275: }
! 276:
! 277: /**
! 278: * xmlHashCopy:
! 279: * @table: the hash table
! 280: * @f: the copier function for items in the hash
! 281: *
! 282: * Scan the hash table and applied f to each value.
! 283: *
! 284: * Returns the new table or NULL in case of error.
! 285: */
! 286: xmlHashTablePtr
! 287: xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
! 288: int i;
! 289: xmlHashEntryPtr iter;
! 290: xmlHashEntryPtr next;
! 291: xmlHashTablePtr ret;
! 292:
! 293: if (table == NULL)
! 294: return(NULL);
! 295: if (f == NULL)
! 296: return(NULL);
! 297:
! 298: ret = xmlHashCreate(table->size);
! 299: if (table->table) {
! 300: for(i = 0; i < table->size; i++) {
! 301: iter = table->table[i];
! 302: while (iter) {
! 303: next = iter->next;
! 304: xmlHashAddEntry(ret, iter->name, f(iter));
! 305: iter = next;
! 306: }
! 307: }
! 308: }
! 309: return(ret);
! 310: }
! 311:
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