blob: 56c5dfb0e68d470cf5e61ed2686acef33512f0e0 [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;
Daniel Veillard81514ba2003-09-16 23:17:26 +000043 const xmlChar *name;
Daniel Veillard2fdbd322003-08-18 12:15:38 +000044 int len;
45 int valid;
46};
47
Daniel Veillard81514ba2003-09-16 23:17:26 +000048typedef struct _xmlDictStrings xmlDictStrings;
49typedef xmlDictStrings *xmlDictStringsPtr;
50struct _xmlDictStrings {
51 xmlDictStringsPtr next;
52 xmlChar *free;
53 xmlChar *end;
54 int size;
55 int nbStrings;
56 xmlChar array[1];
57};
Daniel Veillard2fdbd322003-08-18 12:15:38 +000058/*
59 * The entire dictionnary
60 */
61struct _xmlDict {
Daniel Veillarde96a2a42003-09-24 21:23:56 +000062 int ref_counter;
63
Daniel Veillard2fdbd322003-08-18 12:15:38 +000064 struct _xmlDictEntry *dict;
65 int size;
66 int nbElems;
Daniel Veillard81514ba2003-09-16 23:17:26 +000067 xmlDictStringsPtr strings;
Daniel Veillard4773df22004-01-23 13:15:13 +000068
69 struct _xmlDict *subdict;
Daniel Veillard2fdbd322003-08-18 12:15:38 +000070};
71
72/*
Daniel Veillard81514ba2003-09-16 23:17:26 +000073 * xmlDictAddString:
74 * @dict: the dictionnary
75 * @name: the name of the userdata
76 * @len: the length of the name, if -1 it is recomputed
77 *
78 * Add the string to the array[s]
79 *
80 * Returns the pointer of the local string, or NULL in case of error.
81 */
82static const xmlChar *
83xmlDictAddString(xmlDictPtr dict, const xmlChar *name, int namelen) {
84 xmlDictStringsPtr pool;
85 const xmlChar *ret;
86 int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
87
88 pool = dict->strings;
89 while (pool != NULL) {
90 if (pool->end - pool->free > namelen)
91 goto found_pool;
92 if (pool->size > size) size = pool->size;
93 pool = pool->next;
94 }
95 /*
96 * Not found, need to allocate
97 */
98 if (pool == NULL) {
99 if (size == 0) size = 1000;
100 else size *= 4; /* exponential growth */
101 if (size < 4 * namelen)
102 size = 4 * namelen; /* just in case ! */
103 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
104 if (pool == NULL)
105 return(NULL);
106 pool->size = size;
107 pool->nbStrings = 0;
108 pool->free = &pool->array[0];
109 pool->end = &pool->array[size];
110 pool->next = dict->strings;
111 dict->strings = pool;
112 }
113found_pool:
114 ret = pool->free;
115 memcpy(pool->free, name, namelen);
116 pool->free += namelen;
117 *(pool->free++) = 0;
118 return(ret);
119}
120
121/*
Daniel Veillarde72c5082003-09-19 12:44:05 +0000122 * xmlDictAddQString:
123 * @dict: the dictionnary
124 * @prefix: the prefix of the userdata
125 * @name: the name of the userdata
126 * @len: the length of the name, if -1 it is recomputed
127 *
128 * Add the QName to the array[s]
129 *
130 * Returns the pointer of the local string, or NULL in case of error.
131 */
132static const xmlChar *
133xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix,
134 const xmlChar *name, int namelen)
135{
136 xmlDictStringsPtr pool;
137 const xmlChar *ret;
138 int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
139 int plen;
140
141 if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
142 plen = xmlStrlen(prefix);
143
144 pool = dict->strings;
145 while (pool != NULL) {
146 if (pool->end - pool->free > namelen)
147 goto found_pool;
148 if (pool->size > size) size = pool->size;
149 pool = pool->next;
150 }
151 /*
152 * Not found, need to allocate
153 */
154 if (pool == NULL) {
155 if (size == 0) size = 1000;
156 else size *= 4; /* exponential growth */
157 if (size < 4 * namelen)
158 size = 4 * namelen; /* just in case ! */
159 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
160 if (pool == NULL)
161 return(NULL);
162 pool->size = size;
163 pool->nbStrings = 0;
164 pool->free = &pool->array[0];
165 pool->end = &pool->array[size];
166 pool->next = dict->strings;
167 dict->strings = pool;
168 }
169found_pool:
170 ret = pool->free;
171 memcpy(pool->free, prefix, plen);
172 pool->free += plen;
173 *(pool->free++) = ':';
174 namelen -= plen + 1;
175 memcpy(pool->free, name, namelen);
176 pool->free += namelen;
177 *(pool->free++) = 0;
178 return(ret);
179}
180
181/*
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000182 * xmlDictComputeKey:
183 * Calculate the hash key
184 */
185static unsigned long
Daniel Veillard4773df22004-01-23 13:15:13 +0000186xmlDictComputeKey(const xmlChar *name, int namelen) {
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000187 unsigned long value = 0L;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000188
189 if (name == NULL) return(0);
Daniel Veillard4773df22004-01-23 13:15:13 +0000190 value = *name;
191 value <<= 5;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000192 if (namelen > 10) {
193 value += name[namelen - 1];
194 namelen = 10;
195 }
196 switch (namelen) {
197 case 10: value += name[9];
198 case 9: value += name[8];
199 case 8: value += name[7];
200 case 7: value += name[6];
201 case 6: value += name[5];
202 case 5: value += name[4];
203 case 4: value += name[3];
204 case 3: value += name[2];
205 case 2: value += name[1];
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000206 default: break;
207 }
Daniel Veillard4773df22004-01-23 13:15:13 +0000208 return(value);
Daniel Veillarde72c5082003-09-19 12:44:05 +0000209}
210
211/*
212 * xmlDictComputeQKey:
213 * Calculate the hash key
214 */
215static unsigned long
Daniel Veillard4773df22004-01-23 13:15:13 +0000216xmlDictComputeQKey(const xmlChar *prefix, const xmlChar *name, int len)
Daniel Veillarde72c5082003-09-19 12:44:05 +0000217{
218 unsigned long value = 0L;
219 int plen;
220
221 if (prefix == NULL)
Daniel Veillard4773df22004-01-23 13:15:13 +0000222 return(xmlDictComputeKey(name, len));
Daniel Veillarde72c5082003-09-19 12:44:05 +0000223
224 plen = xmlStrlen(prefix);
225 if (plen == 0)
226 value += 30 * (unsigned long) ':';
227 else
228 value += 30 * (*prefix);
229
230 if (len > 10) {
231 value += name[len - (plen + 1 + 1)];
232 len = 10;
233 if (plen > 10)
234 plen = 10;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000235 }
Daniel Veillarde72c5082003-09-19 12:44:05 +0000236 switch (plen) {
237 case 10: value += prefix[9];
238 case 9: value += prefix[8];
239 case 8: value += prefix[7];
240 case 7: value += prefix[6];
241 case 6: value += prefix[5];
242 case 5: value += prefix[4];
243 case 4: value += prefix[3];
244 case 3: value += prefix[2];
245 case 2: value += prefix[1];
246 case 1: value += prefix[0];
247 default: break;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000248 }
Daniel Veillarde72c5082003-09-19 12:44:05 +0000249 len -= plen;
250 if (len > 0) {
251 value += (unsigned long) ':';
252 len--;
253 }
254 switch (len) {
255 case 10: value += name[9];
256 case 9: value += name[8];
257 case 8: value += name[7];
258 case 7: value += name[6];
259 case 6: value += name[5];
260 case 5: value += name[4];
261 case 4: value += name[3];
262 case 3: value += name[2];
263 case 2: value += name[1];
264 case 1: value += name[0];
265 default: break;
266 }
Daniel Veillard4773df22004-01-23 13:15:13 +0000267 return(value);
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000268}
269
270/**
271 * xmlDictCreate:
272 *
273 * Create a new dictionary
274 *
Daniel Veillard4773df22004-01-23 13:15:13 +0000275 * Returns the newly created dictionnary, or NULL if an error occured.
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000276 */
277xmlDictPtr
278xmlDictCreate(void) {
279 xmlDictPtr dict;
280
281 dict = xmlMalloc(sizeof(xmlDict));
282 if (dict) {
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000283 dict->ref_counter = 1;
284
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000285 dict->size = MIN_DICT_SIZE;
286 dict->nbElems = 0;
287 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
Daniel Veillard81514ba2003-09-16 23:17:26 +0000288 dict->strings = NULL;
Daniel Veillard4773df22004-01-23 13:15:13 +0000289 dict->subdict = NULL;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000290 if (dict->dict) {
291 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
292 return(dict);
293 }
294 xmlFree(dict);
295 }
296 return(NULL);
297}
298
299/**
Daniel Veillard4773df22004-01-23 13:15:13 +0000300 * xmlDictCreateSub:
301 * @sub: an existing dictionnary
302 *
303 * Create a new dictionary, inheriting strings from the read-only
304 * dictionnary @sub. On lookup, strings are first searched in the
305 * new dictionnary, then in @sub, and if not found are created in the
306 * new dictionnary.
307 *
308 * Returns the newly created dictionnary, or NULL if an error occured.
309 */
310xmlDictPtr
311xmlDictCreateSub(xmlDictPtr sub) {
312 xmlDictPtr dict = xmlDictCreate();
313
314 if ((dict != NULL) && (sub != NULL)) {
315 dict->subdict = sub;
316 xmlDictReference(dict->subdict);
317 }
318 return(dict);
319}
320
321/**
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000322 * xmlDictReference:
323 * @dict: the dictionnary
324 *
325 * Increment the reference counter of a dictionary
326 *
327 * Returns 0 in case of success and -1 in case of error
328 */
329int
330xmlDictReference(xmlDictPtr dict) {
331 if (dict == NULL) return -1;
332 dict->ref_counter++;
333 return(0);
334}
335
336/**
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000337 * xmlDictGrow:
338 * @dict: the dictionnary
339 * @size: the new size of the dictionnary
340 *
341 * resize the dictionnary
342 *
343 * Returns 0 in case of success, -1 in case of failure
344 */
345static int
346xmlDictGrow(xmlDictPtr dict, int size) {
347 unsigned long key;
348 int oldsize, i;
349 xmlDictEntryPtr iter, next;
350 struct _xmlDictEntry *olddict;
351#ifdef DEBUG_GROW
352 unsigned long nbElem = 0;
353#endif
354
355 if (dict == NULL)
356 return(-1);
357 if (size < 8)
358 return(-1);
359 if (size > 8 * 2048)
360 return(-1);
361
362 oldsize = dict->size;
363 olddict = dict->dict;
364 if (olddict == NULL)
365 return(-1);
366
367 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
368 if (dict->dict == NULL) {
369 dict->dict = olddict;
370 return(-1);
371 }
372 memset(dict->dict, 0, size * sizeof(xmlDictEntry));
373 dict->size = size;
374
375 /* If the two loops are merged, there would be situations where
376 a new entry needs to allocated and data copied into it from
377 the main dict. So instead, we run through the array twice, first
378 copying all the elements in the main array (where we can't get
379 conflicts) and then the rest, so we only free (and don't allocate)
380 */
381 for (i = 0; i < oldsize; i++) {
382 if (olddict[i].valid == 0)
383 continue;
Daniel Veillard4773df22004-01-23 13:15:13 +0000384 key = xmlDictComputeKey(olddict[i].name, olddict[i].len) % dict->size;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000385 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
386 dict->dict[key].next = NULL;
387#ifdef DEBUG_GROW
388 nbElem++;
389#endif
390 }
391
392 for (i = 0; i < oldsize; i++) {
393 iter = olddict[i].next;
394 while (iter) {
395 next = iter->next;
396
397 /*
398 * put back the entry in the new dict
399 */
400
Daniel Veillard4773df22004-01-23 13:15:13 +0000401 key = xmlDictComputeKey(iter->name, iter->len) % dict->size;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000402 if (dict->dict[key].valid == 0) {
403 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
404 dict->dict[key].next = NULL;
405 dict->dict[key].valid = 1;
406 xmlFree(iter);
407 } else {
408 iter->next = dict->dict[key].next;
409 dict->dict[key].next = iter;
410 }
411
412#ifdef DEBUG_GROW
413 nbElem++;
414#endif
415
416 iter = next;
417 }
418 }
419
420 xmlFree(olddict);
421
422#ifdef DEBUG_GROW
423 xmlGenericError(xmlGenericErrorContext,
424 "xmlDictGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
425#endif
426
427 return(0);
428}
429
430/**
431 * xmlDictFree:
432 * @dict: the dictionnary
433 *
434 * Free the hash @dict and its contents. The userdata is
435 * deallocated with @f if provided.
436 */
437void
438xmlDictFree(xmlDictPtr dict) {
439 int i;
440 xmlDictEntryPtr iter;
441 xmlDictEntryPtr next;
442 int inside_dict = 0;
Daniel Veillard81514ba2003-09-16 23:17:26 +0000443 xmlDictStringsPtr pool, nextp;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000444
445 if (dict == NULL)
446 return;
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000447
448 /* decrement the counter, it may be shared by a parser and docs */
449 dict->ref_counter--;
450 if (dict->ref_counter > 0) return;
451
Daniel Veillard4773df22004-01-23 13:15:13 +0000452 if (dict->subdict != NULL) {
453 xmlDictFree(dict->subdict);
454 }
455
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000456 if (dict->dict) {
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000457 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000458 iter = &(dict->dict[i]);
459 if (iter->valid == 0)
460 continue;
461 inside_dict = 1;
462 while (iter) {
463 next = iter->next;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000464 if (!inside_dict)
465 xmlFree(iter);
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000466 dict->nbElems--;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000467 inside_dict = 0;
468 iter = next;
469 }
470 inside_dict = 0;
471 }
472 xmlFree(dict->dict);
473 }
Daniel Veillard81514ba2003-09-16 23:17:26 +0000474 pool = dict->strings;
475 while (pool != NULL) {
476 nextp = pool->next;
477 xmlFree(pool);
478 pool = nextp;
479 }
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000480 xmlFree(dict);
481}
482
483/**
484 * xmlDictLookup:
485 * @dict: the dictionnary
486 * @name: the name of the userdata
Daniel Veillard0fb18932003-09-07 09:14:37 +0000487 * @len: the length of the name, if -1 it is recomputed
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000488 *
489 * Add the @name to the hash @dict if not present.
490 *
491 * Returns the internal copy of the name or NULL in case of internal error
492 */
493const xmlChar *
494xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
Daniel Veillard4773df22004-01-23 13:15:13 +0000495 unsigned long key, okey, nbi = 0;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000496 xmlDictEntryPtr entry;
497 xmlDictEntryPtr insert;
498 const xmlChar *ret;
499
Daniel Veillard0fb18932003-09-07 09:14:37 +0000500 if ((dict == NULL) || (name == NULL))
501 return(NULL);
502
503 if (len < 0)
504 len = xmlStrlen(name);
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000505
506 /*
507 * Check for duplicate and insertion location.
508 */
Daniel Veillard4773df22004-01-23 13:15:13 +0000509 okey = xmlDictComputeKey(name, len);
510 key = okey % dict->size;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000511 if (dict->dict[key].valid == 0) {
512 insert = NULL;
513 } else {
514 for (insert = &(dict->dict[key]); insert->next != NULL;
515 insert = insert->next) {
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000516#ifdef __GNUC__
517 if (insert->len == len) {
Daniel Veillard4773df22004-01-23 13:15:13 +0000518 if (!memcmp(insert->name, name, len))
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000519 return(insert->name);
520 }
521#else
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000522 if ((insert->len == len) &&
523 (!xmlStrncmp(insert->name, name, len)))
524 return(insert->name);
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000525#endif
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000526 nbi++;
527 }
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000528#ifdef __GNUC__
529 if (insert->len == len) {
Daniel Veillard4773df22004-01-23 13:15:13 +0000530 if (!memcmp(insert->name, name, len))
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000531 return(insert->name);
532 }
533#else
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000534 if ((insert->len == len) &&
535 (!xmlStrncmp(insert->name, name, len)))
536 return(insert->name);
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000537#endif
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000538 }
539
Daniel Veillard4773df22004-01-23 13:15:13 +0000540 if (dict->subdict) {
541 key = okey % dict->subdict->size;
542 if (dict->subdict->dict[key].valid != 0) {
543 xmlDictEntryPtr tmp;
544
545 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
546 tmp = tmp->next) {
547#ifdef __GNUC__
548 if (tmp->len == len) {
549 if (!memcmp(tmp->name, name, len))
550 return(tmp->name);
551 }
552#else
553 if ((tmp->len == len) &&
554 (!xmlStrncmp(tmp->name, name, len)))
555 return(tmp->name);
556#endif
557 nbi++;
558 }
559#ifdef __GNUC__
560 if (tmp->len == len) {
561 if (!memcmp(tmp->name, name, len))
562 return(tmp->name);
563 }
564#else
565 if ((tmp->len == len) &&
566 (!xmlStrncmp(tmp->name, name, len)))
567 return(tmp->name);
568#endif
569 }
570 key = okey % dict->size;
571 }
572
Daniel Veillard81514ba2003-09-16 23:17:26 +0000573 ret = xmlDictAddString(dict, name, len);
574 if (ret == NULL)
575 return(NULL);
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000576 if (insert == NULL) {
577 entry = &(dict->dict[key]);
578 } else {
579 entry = xmlMalloc(sizeof(xmlDictEntry));
580 if (entry == NULL)
581 return(NULL);
582 }
Daniel Veillard81514ba2003-09-16 23:17:26 +0000583 entry->name = ret;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000584 entry->len = len;
585 entry->next = NULL;
586 entry->valid = 1;
587
588
589 if (insert != NULL)
590 insert->next = entry;
591
592 dict->nbElems++;
593
594 if ((nbi > MAX_HASH_LEN) &&
595 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
596 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
597 /* Note that entry may have been freed at this point by xmlDictGrow */
598
599 return(ret);
600}
601
602/**
Daniel Veillarde72c5082003-09-19 12:44:05 +0000603 * xmlDictQLookup:
604 * @dict: the dictionnary
605 * @prefix: the prefix
606 * @name: the name
607 *
608 * Add the QName @prefix:@name to the hash @dict if not present.
609 *
610 * Returns the internal copy of the QName or NULL in case of internal error
611 */
612const xmlChar *
613xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
Daniel Veillard4773df22004-01-23 13:15:13 +0000614 unsigned long okey, key, nbi = 0;
Daniel Veillarde72c5082003-09-19 12:44:05 +0000615 xmlDictEntryPtr entry;
616 xmlDictEntryPtr insert;
617 const xmlChar *ret;
618 int len;
619
620 if ((dict == NULL) || (name == NULL))
621 return(NULL);
622
623 len = xmlStrlen(name);
624 if (prefix != NULL)
625 len += 1 + xmlStrlen(prefix);
626
627 /*
628 * Check for duplicate and insertion location.
629 */
Daniel Veillard4773df22004-01-23 13:15:13 +0000630 okey = xmlDictComputeQKey(prefix, name, len);
631 key = okey % dict->size;
Daniel Veillarde72c5082003-09-19 12:44:05 +0000632 if (dict->dict[key].valid == 0) {
633 insert = NULL;
634 } else {
635 for (insert = &(dict->dict[key]); insert->next != NULL;
636 insert = insert->next) {
637 if ((insert->len == len) &&
638 (xmlStrQEqual(prefix, name, insert->name)))
639 return(insert->name);
640 nbi++;
641 }
642 if ((insert->len == len) &&
643 (xmlStrQEqual(prefix, name, insert->name)))
644 return(insert->name);
645 }
646
Daniel Veillard4773df22004-01-23 13:15:13 +0000647 if (dict->subdict) {
648 key = okey % dict->subdict->size;
649 if (dict->subdict->dict[key].valid != 0) {
650 xmlDictEntryPtr tmp;
651 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
652 tmp = tmp->next) {
653 if ((tmp->len == len) &&
654 (xmlStrQEqual(prefix, name, tmp->name)))
655 return(tmp->name);
656 nbi++;
657 }
658 if ((tmp->len == len) &&
659 (xmlStrQEqual(prefix, name, tmp->name)))
660 return(tmp->name);
661 }
662 key = okey % dict->size;
663 }
664
Daniel Veillarde72c5082003-09-19 12:44:05 +0000665 ret = xmlDictAddQString(dict, prefix, name, len);
666 if (ret == NULL)
667 return(NULL);
668 if (insert == NULL) {
669 entry = &(dict->dict[key]);
670 } else {
671 entry = xmlMalloc(sizeof(xmlDictEntry));
672 if (entry == NULL)
673 return(NULL);
674 }
675 entry->name = ret;
676 entry->len = len;
677 entry->next = NULL;
678 entry->valid = 1;
679
680 if (insert != NULL)
681 insert->next = entry;
682
683 dict->nbElems++;
684
685 if ((nbi > MAX_HASH_LEN) &&
686 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
687 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
688 /* Note that entry may have been freed at this point by xmlDictGrow */
689
690 return(ret);
691}
692
693/**
Daniel Veillard81514ba2003-09-16 23:17:26 +0000694 * xmlDictOwns:
695 * @dict: the dictionnary
696 * @str: the string
697 *
698 * check if a string is owned by the disctionary
699 *
700 * Returns 1 if true, 0 if false and -1 in case of error
701 * -1 in case of error
702 */
703int
704xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
705 xmlDictStringsPtr pool;
706
707 if ((dict == NULL) || (str == NULL))
708 return(-1);
709 pool = dict->strings;
710 while (pool != NULL) {
William M. Brackbf5cf212004-08-31 06:47:17 +0000711 if ((str >= &pool->array[0]) && (str <= pool->free))
Daniel Veillard81514ba2003-09-16 23:17:26 +0000712 return(1);
713 pool = pool->next;
714 }
Daniel Veillard4773df22004-01-23 13:15:13 +0000715 if (dict->subdict)
716 return(xmlDictOwns(dict->subdict, str));
Daniel Veillard81514ba2003-09-16 23:17:26 +0000717 return(0);
718}
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000719
Daniel Veillard81514ba2003-09-16 23:17:26 +0000720/**
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000721 * xmlDictSize:
722 * @dict: the dictionnary
723 *
724 * Query the number of elements installed in the hash @dict.
725 *
726 * Returns the number of elements in the dictionnary or
727 * -1 in case of error
728 */
729int
730xmlDictSize(xmlDictPtr dict) {
731 if (dict == NULL)
732 return(-1);
Daniel Veillard4773df22004-01-23 13:15:13 +0000733 if (dict->subdict)
734 return(dict->nbElems + dict->subdict->nbElems);
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000735 return(dict->nbElems);
736}
737
738