blob: 2dd759d1358821e3143ed9991ef86eea5922da40 [file] [log] [blame]
Daniel Veillard2fdbd322003-08-18 12:15:38 +00001/*
2 * dict.c: dictionary of reusable strings, just used to avoid allocation
3 * and freeing operations.
4 *
5 * Copyright (C) 2003 Daniel Veillard.
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
12 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
13 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
14 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
15 *
16 * Author: daniel@veillard.com
17 */
18
19#define IN_LIBXML
20#include "libxml.h"
21
22#include <string.h>
23#include <libxml/tree.h>
24#include <libxml/dict.h>
25#include <libxml/xmlmemory.h>
26#include <libxml/xmlerror.h>
27#include <libxml/globals.h>
28
29#define MAX_HASH_LEN 4
30#define MIN_DICT_SIZE 128
31#define MAX_DICT_HASH 8 * 2048
32
33/* #define ALLOW_REMOVAL */
34/* #define DEBUG_GROW */
35
36/*
37 * An entry in the dictionnary
38 */
39typedef struct _xmlDictEntry xmlDictEntry;
40typedef xmlDictEntry *xmlDictEntryPtr;
41struct _xmlDictEntry {
42 struct _xmlDictEntry *next;
43 xmlChar *name;
44 int len;
45 int valid;
46};
47
48/*
49 * The entire dictionnary
50 */
51struct _xmlDict {
52 struct _xmlDictEntry *dict;
53 int size;
54 int nbElems;
55};
56
57/*
58 * xmlDictComputeKey:
59 * Calculate the hash key
60 */
61static unsigned long
62xmlDictComputeKey(xmlDictPtr dict, const xmlChar *name, int namelen) {
63 unsigned long value = 0L;
Daniel Veillard2fdbd322003-08-18 12:15:38 +000064
65 if (name == NULL) return(0);
66 value += 30 * (*name);
67 if (namelen > 10) {
68 value += name[namelen - 1];
69 namelen = 10;
70 }
71 switch (namelen) {
72 case 10: value += name[9];
73 case 9: value += name[8];
74 case 8: value += name[7];
75 case 7: value += name[6];
76 case 6: value += name[5];
77 case 5: value += name[4];
78 case 4: value += name[3];
79 case 3: value += name[2];
80 case 2: value += name[1];
81 case 1: value += name[0];
82 default: break;
83 }
84#if 0
85 while ((len++ < namelen) && ((ch = *name++) != 0)) {
86 value += (unsigned long)ch;
87 }
88#endif
89#if 0
90 while ((len++ < namelen) && ((ch = *name++) != 0)) {
91 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
92 }
93#endif
94 return (value % dict->size);
95}
96
97/**
98 * xmlDictCreate:
99 *
100 * Create a new dictionary
101 *
102 * Returns the newly created object, or NULL if an error occured.
103 */
104xmlDictPtr
105xmlDictCreate(void) {
106 xmlDictPtr dict;
107
108 dict = xmlMalloc(sizeof(xmlDict));
109 if (dict) {
110 dict->size = MIN_DICT_SIZE;
111 dict->nbElems = 0;
112 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
113 if (dict->dict) {
114 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
115 return(dict);
116 }
117 xmlFree(dict);
118 }
119 return(NULL);
120}
121
122/**
123 * xmlDictGrow:
124 * @dict: the dictionnary
125 * @size: the new size of the dictionnary
126 *
127 * resize the dictionnary
128 *
129 * Returns 0 in case of success, -1 in case of failure
130 */
131static int
132xmlDictGrow(xmlDictPtr dict, int size) {
133 unsigned long key;
134 int oldsize, i;
135 xmlDictEntryPtr iter, next;
136 struct _xmlDictEntry *olddict;
137#ifdef DEBUG_GROW
138 unsigned long nbElem = 0;
139#endif
140
141 if (dict == NULL)
142 return(-1);
143 if (size < 8)
144 return(-1);
145 if (size > 8 * 2048)
146 return(-1);
147
148 oldsize = dict->size;
149 olddict = dict->dict;
150 if (olddict == NULL)
151 return(-1);
152
153 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
154 if (dict->dict == NULL) {
155 dict->dict = olddict;
156 return(-1);
157 }
158 memset(dict->dict, 0, size * sizeof(xmlDictEntry));
159 dict->size = size;
160
161 /* If the two loops are merged, there would be situations where
162 a new entry needs to allocated and data copied into it from
163 the main dict. So instead, we run through the array twice, first
164 copying all the elements in the main array (where we can't get
165 conflicts) and then the rest, so we only free (and don't allocate)
166 */
167 for (i = 0; i < oldsize; i++) {
168 if (olddict[i].valid == 0)
169 continue;
170 key = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
171 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
172 dict->dict[key].next = NULL;
173#ifdef DEBUG_GROW
174 nbElem++;
175#endif
176 }
177
178 for (i = 0; i < oldsize; i++) {
179 iter = olddict[i].next;
180 while (iter) {
181 next = iter->next;
182
183 /*
184 * put back the entry in the new dict
185 */
186
187 key = xmlDictComputeKey(dict, iter->name, iter->len);
188 if (dict->dict[key].valid == 0) {
189 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
190 dict->dict[key].next = NULL;
191 dict->dict[key].valid = 1;
192 xmlFree(iter);
193 } else {
194 iter->next = dict->dict[key].next;
195 dict->dict[key].next = iter;
196 }
197
198#ifdef DEBUG_GROW
199 nbElem++;
200#endif
201
202 iter = next;
203 }
204 }
205
206 xmlFree(olddict);
207
208#ifdef DEBUG_GROW
209 xmlGenericError(xmlGenericErrorContext,
210 "xmlDictGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
211#endif
212
213 return(0);
214}
215
216/**
217 * xmlDictFree:
218 * @dict: the dictionnary
219 *
220 * Free the hash @dict and its contents. The userdata is
221 * deallocated with @f if provided.
222 */
223void
224xmlDictFree(xmlDictPtr dict) {
225 int i;
226 xmlDictEntryPtr iter;
227 xmlDictEntryPtr next;
228 int inside_dict = 0;
229
230 if (dict == NULL)
231 return;
232 if (dict->dict) {
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000233 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000234 iter = &(dict->dict[i]);
235 if (iter->valid == 0)
236 continue;
237 inside_dict = 1;
238 while (iter) {
239 next = iter->next;
240 if (iter->name)
241 xmlFree(iter->name);
242 if (!inside_dict)
243 xmlFree(iter);
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000244 dict->nbElems--;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000245 inside_dict = 0;
246 iter = next;
247 }
248 inside_dict = 0;
249 }
250 xmlFree(dict->dict);
251 }
252 xmlFree(dict);
253}
254
255/**
256 * xmlDictLookup:
257 * @dict: the dictionnary
258 * @name: the name of the userdata
259 * @len: the length of the name
260 *
261 * Add the @name to the hash @dict if not present.
262 *
263 * Returns the internal copy of the name or NULL in case of internal error
264 */
265const xmlChar *
266xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
267 unsigned long key, nbi = 0;
268 xmlDictEntryPtr entry;
269 xmlDictEntryPtr insert;
270 const xmlChar *ret;
271
272 if ((dict == NULL) || (name == NULL) || (len <= 0))
273 return(NULL);
274
275 /*
276 * Check for duplicate and insertion location.
277 */
278 key = xmlDictComputeKey(dict, name, len);
279 if (dict->dict[key].valid == 0) {
280 insert = NULL;
281 } else {
282 for (insert = &(dict->dict[key]); insert->next != NULL;
283 insert = insert->next) {
284 if ((insert->len == len) &&
285 (!xmlStrncmp(insert->name, name, len)))
286 return(insert->name);
287 nbi++;
288 }
289 if ((insert->len == len) &&
290 (!xmlStrncmp(insert->name, name, len)))
291 return(insert->name);
292 }
293
294 if (insert == NULL) {
295 entry = &(dict->dict[key]);
296 } else {
297 entry = xmlMalloc(sizeof(xmlDictEntry));
298 if (entry == NULL)
299 return(NULL);
300 }
301
302 ret = entry->name = xmlStrndup(name, len);
303 entry->len = len;
304 entry->next = NULL;
305 entry->valid = 1;
306
307
308 if (insert != NULL)
309 insert->next = entry;
310
311 dict->nbElems++;
312
313 if ((nbi > MAX_HASH_LEN) &&
314 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
315 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
316 /* Note that entry may have been freed at this point by xmlDictGrow */
317
318 return(ret);
319}
320
321/**
322 * xmlDictSize:
323 * @dict: the dictionnary
324 *
325 * Query the number of elements installed in the hash @dict.
326 *
327 * Returns the number of elements in the dictionnary or
328 * -1 in case of error
329 */
330int
331xmlDictSize(xmlDictPtr dict) {
332 if (dict == NULL)
333 return(-1);
334 return(dict->nbElems);
335}
336
337