1 /*
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 #ifdef HAVE_STDINT_H
24 #include <stdint.h>
25 #else
26 #ifdef HAVE_INTTYPES_H
27 #include <inttypes.h>
28 #elif defined(WIN32)
29 typedef unsigned __int32 uint32_t;
30 #endif
31 #endif
32 #include <libxml/tree.h>
33 #include <libxml/dict.h>
34 #include <libxml/xmlmemory.h>
35 #include <libxml/xmlerror.h>
36 #include <libxml/globals.h>
37
38 /* #define DEBUG_GROW */
39 /* #define DICT_DEBUG_PATTERNS */
40
41 #define MAX_HASH_LEN 3
42 #define MIN_DICT_SIZE 128
43 #define MAX_DICT_HASH 8 * 2048
44 #define WITH_BIG_KEY
45
46 #ifdef WITH_BIG_KEY
47 #define xmlDictComputeKey(dict, name, len) \
48 (((dict)->size == MIN_DICT_SIZE) ? \
49 xmlDictComputeFastKey(name, len) : \
50 xmlDictComputeBigKey(name, len))
51
52 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \
53 (((prefix) == NULL) ? \
54 (xmlDictComputeKey(dict, name, len)) : \
55 (((dict)->size == MIN_DICT_SIZE) ? \
56 xmlDictComputeFastQKey(prefix, plen, name, len) : \
57 xmlDictComputeBigQKey(prefix, plen, name, len)))
58
59 #else /* !WITH_BIG_KEY */
60 #define xmlDictComputeKey(dict, name, len) \
61 xmlDictComputeFastKey(name, len)
62 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \
63 xmlDictComputeFastQKey(prefix, plen, name, len)
64 #endif /* WITH_BIG_KEY */
65
66 /*
67 * An entry in the dictionnary
68 */
69 typedef struct _xmlDictEntry xmlDictEntry;
70 typedef xmlDictEntry *xmlDictEntryPtr;
71 struct _xmlDictEntry {
72 struct _xmlDictEntry *next;
73 const xmlChar *name;
74 int len;
75 int valid;
76 unsigned long okey;
77 };
78
79 typedef struct _xmlDictStrings xmlDictStrings;
80 typedef xmlDictStrings *xmlDictStringsPtr;
81 struct _xmlDictStrings {
82 xmlDictStringsPtr next;
83 xmlChar *free;
84 xmlChar *end;
85 int size;
86 int nbStrings;
87 xmlChar array[1];
88 };
89 /*
90 * The entire dictionnary
91 */
92 struct _xmlDict {
93 int ref_counter;
94
95 struct _xmlDictEntry *dict;
96 int size;
97 int nbElems;
98 xmlDictStringsPtr strings;
99
100 struct _xmlDict *subdict;
101 };
102
103 /*
104 * A mutex for modifying the reference counter for shared
105 * dictionaries.
106 */
107 static xmlRMutexPtr xmlDictMutex = NULL;
108
109 /*
110 * Whether the dictionary mutex was initialized.
111 */
112 static int xmlDictInitialized = 0;
113
114 /**
115 * xmlInitializeDict:
116 *
117 * Do the dictionary mutex initialization.
118 * this function is not thread safe, initialization should
119 * preferably be done once at startup
120 */
xmlInitializeDict(void)121 static int xmlInitializeDict(void) {
122 if (xmlDictInitialized)
123 return(1);
124
125 if ((xmlDictMutex = xmlNewRMutex()) == NULL)
126 return(0);
127
128 xmlDictInitialized = 1;
129 return(1);
130 }
131
132 /**
133 * xmlDictCleanup:
134 *
135 * Free the dictionary mutex.
136 */
137 void
xmlDictCleanup(void)138 xmlDictCleanup(void) {
139 if (!xmlDictInitialized)
140 return;
141
142 xmlFreeRMutex(xmlDictMutex);
143
144 xmlDictInitialized = 0;
145 }
146
147 /*
148 * xmlDictAddString:
149 * @dict: the dictionnary
150 * @name: the name of the userdata
151 * @len: the length of the name, if -1 it is recomputed
152 *
153 * Add the string to the array[s]
154 *
155 * Returns the pointer of the local string, or NULL in case of error.
156 */
157 static const xmlChar *
xmlDictAddString(xmlDictPtr dict,const xmlChar * name,int namelen)158 xmlDictAddString(xmlDictPtr dict, const xmlChar *name, int namelen) {
159 xmlDictStringsPtr pool;
160 const xmlChar *ret;
161 int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
162
163 #ifdef DICT_DEBUG_PATTERNS
164 fprintf(stderr, "-");
165 #endif
166 pool = dict->strings;
167 while (pool != NULL) {
168 if (pool->end - pool->free > namelen)
169 goto found_pool;
170 if (pool->size > size) size = pool->size;
171 pool = pool->next;
172 }
173 /*
174 * Not found, need to allocate
175 */
176 if (pool == NULL) {
177 if (size == 0) size = 1000;
178 else size *= 4; /* exponential growth */
179 if (size < 4 * namelen)
180 size = 4 * namelen; /* just in case ! */
181 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
182 if (pool == NULL)
183 return(NULL);
184 pool->size = size;
185 pool->nbStrings = 0;
186 pool->free = &pool->array[0];
187 pool->end = &pool->array[size];
188 pool->next = dict->strings;
189 dict->strings = pool;
190 #ifdef DICT_DEBUG_PATTERNS
191 fprintf(stderr, "+");
192 #endif
193 }
194 found_pool:
195 ret = pool->free;
196 memcpy(pool->free, name, namelen);
197 pool->free += namelen;
198 *(pool->free++) = 0;
199 pool->nbStrings++;
200 return(ret);
201 }
202
203 /*
204 * xmlDictAddQString:
205 * @dict: the dictionnary
206 * @prefix: the prefix of the userdata
207 * @plen: the prefix length
208 * @name: the name of the userdata
209 * @len: the length of the name, if -1 it is recomputed
210 *
211 * Add the QName to the array[s]
212 *
213 * Returns the pointer of the local string, or NULL in case of error.
214 */
215 static const xmlChar *
xmlDictAddQString(xmlDictPtr dict,const xmlChar * prefix,int plen,const xmlChar * name,int namelen)216 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, int plen,
217 const xmlChar *name, int namelen)
218 {
219 xmlDictStringsPtr pool;
220 const xmlChar *ret;
221 int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
222
223 if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
224
225 #ifdef DICT_DEBUG_PATTERNS
226 fprintf(stderr, "=");
227 #endif
228 pool = dict->strings;
229 while (pool != NULL) {
230 if (pool->end - pool->free > namelen + plen + 1)
231 goto found_pool;
232 if (pool->size > size) size = pool->size;
233 pool = pool->next;
234 }
235 /*
236 * Not found, need to allocate
237 */
238 if (pool == NULL) {
239 if (size == 0) size = 1000;
240 else size *= 4; /* exponential growth */
241 if (size < 4 * (namelen + plen + 1))
242 size = 4 * (namelen + plen + 1); /* just in case ! */
243 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
244 if (pool == NULL)
245 return(NULL);
246 pool->size = size;
247 pool->nbStrings = 0;
248 pool->free = &pool->array[0];
249 pool->end = &pool->array[size];
250 pool->next = dict->strings;
251 dict->strings = pool;
252 #ifdef DICT_DEBUG_PATTERNS
253 fprintf(stderr, "+");
254 #endif
255 }
256 found_pool:
257 ret = pool->free;
258 memcpy(pool->free, prefix, plen);
259 pool->free += plen;
260 *(pool->free++) = ':';
261 memcpy(pool->free, name, namelen);
262 pool->free += namelen;
263 *(pool->free++) = 0;
264 pool->nbStrings++;
265 return(ret);
266 }
267
268 #ifdef WITH_BIG_KEY
269 /*
270 * xmlDictComputeBigKey:
271 *
272 * Calculate a hash key using a good hash function that works well for
273 * larger hash table sizes.
274 *
275 * Hash function by "One-at-a-Time Hash" see
276 * http://burtleburtle.net/bob/hash/doobs.html
277 */
278
279 static uint32_t
xmlDictComputeBigKey(const xmlChar * data,int namelen)280 xmlDictComputeBigKey(const xmlChar* data, int namelen) {
281 uint32_t hash;
282 int i;
283
284 if (namelen <= 0 || data == NULL) return(0);
285
286 hash = 0;
287
288 for (i = 0;i < namelen; i++) {
289 hash += data[i];
290 hash += (hash << 10);
291 hash ^= (hash >> 6);
292 }
293 hash += (hash << 3);
294 hash ^= (hash >> 11);
295 hash += (hash << 15);
296
297 return hash;
298 }
299
300 /*
301 * xmlDictComputeBigQKey:
302 *
303 * Calculate a hash key for two strings using a good hash function
304 * that works well for larger hash table sizes.
305 *
306 * Hash function by "One-at-a-Time Hash" see
307 * http://burtleburtle.net/bob/hash/doobs.html
308 *
309 * Neither of the two strings must be NULL.
310 */
311 static unsigned long
xmlDictComputeBigQKey(const xmlChar * prefix,int plen,const xmlChar * name,int len)312 xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
313 const xmlChar *name, int len)
314 {
315 uint32_t hash;
316 int i;
317
318 hash = 0;
319
320 for (i = 0;i < plen; i++) {
321 hash += prefix[i];
322 hash += (hash << 10);
323 hash ^= (hash >> 6);
324 }
325 hash += ':';
326 hash += (hash << 10);
327 hash ^= (hash >> 6);
328
329 for (i = 0;i < len; i++) {
330 hash += name[i];
331 hash += (hash << 10);
332 hash ^= (hash >> 6);
333 }
334 hash += (hash << 3);
335 hash ^= (hash >> 11);
336 hash += (hash << 15);
337
338 return hash;
339 }
340 #endif /* WITH_BIG_KEY */
341
342 /*
343 * xmlDictComputeFastKey:
344 *
345 * Calculate a hash key using a fast hash function that works well
346 * for low hash table fill.
347 */
348 static unsigned long
xmlDictComputeFastKey(const xmlChar * name,int namelen)349 xmlDictComputeFastKey(const xmlChar *name, int namelen) {
350 unsigned long value = 0L;
351
352 if (name == NULL) return(0);
353 value = *name;
354 value <<= 5;
355 if (namelen > 10) {
356 value += name[namelen - 1];
357 namelen = 10;
358 }
359 switch (namelen) {
360 case 10: value += name[9];
361 case 9: value += name[8];
362 case 8: value += name[7];
363 case 7: value += name[6];
364 case 6: value += name[5];
365 case 5: value += name[4];
366 case 4: value += name[3];
367 case 3: value += name[2];
368 case 2: value += name[1];
369 default: break;
370 }
371 return(value);
372 }
373
374 /*
375 * xmlDictComputeFastQKey:
376 *
377 * Calculate a hash key for two strings using a fast hash function
378 * that works well for low hash table fill.
379 *
380 * Neither of the two strings must be NULL.
381 */
382 static unsigned long
xmlDictComputeFastQKey(const xmlChar * prefix,int plen,const xmlChar * name,int len)383 xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
384 const xmlChar *name, int len)
385 {
386 unsigned long value = 0L;
387
388 if (plen == 0)
389 value += 30 * (unsigned long) ':';
390 else
391 value += 30 * (*prefix);
392
393 if (len > 10) {
394 value += name[len - (plen + 1 + 1)];
395 len = 10;
396 if (plen > 10)
397 plen = 10;
398 }
399 switch (plen) {
400 case 10: value += prefix[9];
401 case 9: value += prefix[8];
402 case 8: value += prefix[7];
403 case 7: value += prefix[6];
404 case 6: value += prefix[5];
405 case 5: value += prefix[4];
406 case 4: value += prefix[3];
407 case 3: value += prefix[2];
408 case 2: value += prefix[1];
409 case 1: value += prefix[0];
410 default: break;
411 }
412 len -= plen;
413 if (len > 0) {
414 value += (unsigned long) ':';
415 len--;
416 }
417 switch (len) {
418 case 10: value += name[9];
419 case 9: value += name[8];
420 case 8: value += name[7];
421 case 7: value += name[6];
422 case 6: value += name[5];
423 case 5: value += name[4];
424 case 4: value += name[3];
425 case 3: value += name[2];
426 case 2: value += name[1];
427 case 1: value += name[0];
428 default: break;
429 }
430 return(value);
431 }
432
433 /**
434 * xmlDictCreate:
435 *
436 * Create a new dictionary
437 *
438 * Returns the newly created dictionnary, or NULL if an error occured.
439 */
440 xmlDictPtr
xmlDictCreate(void)441 xmlDictCreate(void) {
442 xmlDictPtr dict;
443
444 if (!xmlDictInitialized)
445 if (!xmlInitializeDict())
446 return(NULL);
447
448 #ifdef DICT_DEBUG_PATTERNS
449 fprintf(stderr, "C");
450 #endif
451
452 dict = xmlMalloc(sizeof(xmlDict));
453 if (dict) {
454 dict->ref_counter = 1;
455
456 dict->size = MIN_DICT_SIZE;
457 dict->nbElems = 0;
458 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
459 dict->strings = NULL;
460 dict->subdict = NULL;
461 if (dict->dict) {
462 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
463 return(dict);
464 }
465 xmlFree(dict);
466 }
467 return(NULL);
468 }
469
470 /**
471 * xmlDictCreateSub:
472 * @sub: an existing dictionnary
473 *
474 * Create a new dictionary, inheriting strings from the read-only
475 * dictionnary @sub. On lookup, strings are first searched in the
476 * new dictionnary, then in @sub, and if not found are created in the
477 * new dictionnary.
478 *
479 * Returns the newly created dictionnary, or NULL if an error occured.
480 */
481 xmlDictPtr
xmlDictCreateSub(xmlDictPtr sub)482 xmlDictCreateSub(xmlDictPtr sub) {
483 xmlDictPtr dict = xmlDictCreate();
484
485 if ((dict != NULL) && (sub != NULL)) {
486 #ifdef DICT_DEBUG_PATTERNS
487 fprintf(stderr, "R");
488 #endif
489 dict->subdict = sub;
490 xmlDictReference(dict->subdict);
491 }
492 return(dict);
493 }
494
495 /**
496 * xmlDictReference:
497 * @dict: the dictionnary
498 *
499 * Increment the reference counter of a dictionary
500 *
501 * Returns 0 in case of success and -1 in case of error
502 */
503 int
xmlDictReference(xmlDictPtr dict)504 xmlDictReference(xmlDictPtr dict) {
505 if (!xmlDictInitialized)
506 if (!xmlInitializeDict())
507 return(-1);
508
509 if (dict == NULL) return -1;
510 xmlRMutexLock(xmlDictMutex);
511 dict->ref_counter++;
512 xmlRMutexUnlock(xmlDictMutex);
513 return(0);
514 }
515
516 /**
517 * xmlDictGrow:
518 * @dict: the dictionnary
519 * @size: the new size of the dictionnary
520 *
521 * resize the dictionnary
522 *
523 * Returns 0 in case of success, -1 in case of failure
524 */
525 static int
xmlDictGrow(xmlDictPtr dict,int size)526 xmlDictGrow(xmlDictPtr dict, int size) {
527 unsigned long key, okey;
528 int oldsize, i;
529 xmlDictEntryPtr iter, next;
530 struct _xmlDictEntry *olddict;
531 #ifdef DEBUG_GROW
532 unsigned long nbElem = 0;
533 #endif
534 int ret = 0;
535 int keep_keys = 1;
536
537 if (dict == NULL)
538 return(-1);
539 if (size < 8)
540 return(-1);
541 if (size > 8 * 2048)
542 return(-1);
543
544 #ifdef DICT_DEBUG_PATTERNS
545 fprintf(stderr, "*");
546 #endif
547
548 oldsize = dict->size;
549 olddict = dict->dict;
550 if (olddict == NULL)
551 return(-1);
552 if (oldsize == MIN_DICT_SIZE)
553 keep_keys = 0;
554
555 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
556 if (dict->dict == NULL) {
557 dict->dict = olddict;
558 return(-1);
559 }
560 memset(dict->dict, 0, size * sizeof(xmlDictEntry));
561 dict->size = size;
562
563 /* If the two loops are merged, there would be situations where
564 a new entry needs to allocated and data copied into it from
565 the main dict. It is nicer to run through the array twice, first
566 copying all the elements in the main array (less probability of
567 allocate) and then the rest, so we only free in the second loop.
568 */
569 for (i = 0; i < oldsize; i++) {
570 if (olddict[i].valid == 0)
571 continue;
572
573 if (keep_keys)
574 okey = olddict[i].okey;
575 else
576 okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
577 key = okey % dict->size;
578
579 if (dict->dict[key].valid == 0) {
580 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
581 dict->dict[key].next = NULL;
582 dict->dict[key].okey = okey;
583 } else {
584 xmlDictEntryPtr entry;
585
586 entry = xmlMalloc(sizeof(xmlDictEntry));
587 if (entry != NULL) {
588 entry->name = olddict[i].name;
589 entry->len = olddict[i].len;
590 entry->okey = okey;
591 entry->next = dict->dict[key].next;
592 entry->valid = 1;
593 dict->dict[key].next = entry;
594 } else {
595 /*
596 * we don't have much ways to alert from herei
597 * result is loosing an entry and unicity garantee
598 */
599 ret = -1;
600 }
601 }
602 #ifdef DEBUG_GROW
603 nbElem++;
604 #endif
605 }
606
607 for (i = 0; i < oldsize; i++) {
608 iter = olddict[i].next;
609 while (iter) {
610 next = iter->next;
611
612 /*
613 * put back the entry in the new dict
614 */
615
616 if (keep_keys)
617 okey = iter->okey;
618 else
619 okey = xmlDictComputeKey(dict, iter->name, iter->len);
620 key = okey % dict->size;
621 if (dict->dict[key].valid == 0) {
622 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
623 dict->dict[key].next = NULL;
624 dict->dict[key].valid = 1;
625 dict->dict[key].okey = okey;
626 xmlFree(iter);
627 } else {
628 iter->next = dict->dict[key].next;
629 iter->okey = okey;
630 dict->dict[key].next = iter;
631 }
632
633 #ifdef DEBUG_GROW
634 nbElem++;
635 #endif
636
637 iter = next;
638 }
639 }
640
641 xmlFree(olddict);
642
643 #ifdef DEBUG_GROW
644 xmlGenericError(xmlGenericErrorContext,
645 "xmlDictGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
646 #endif
647
648 return(ret);
649 }
650
651 /**
652 * xmlDictFree:
653 * @dict: the dictionnary
654 *
655 * Free the hash @dict and its contents. The userdata is
656 * deallocated with @f if provided.
657 */
658 void
xmlDictFree(xmlDictPtr dict)659 xmlDictFree(xmlDictPtr dict) {
660 int i;
661 xmlDictEntryPtr iter;
662 xmlDictEntryPtr next;
663 int inside_dict = 0;
664 xmlDictStringsPtr pool, nextp;
665
666 if (dict == NULL)
667 return;
668
669 if (!xmlDictInitialized)
670 if (!xmlInitializeDict())
671 return;
672
673 /* decrement the counter, it may be shared by a parser and docs */
674 xmlRMutexLock(xmlDictMutex);
675 dict->ref_counter--;
676 if (dict->ref_counter > 0) {
677 xmlRMutexUnlock(xmlDictMutex);
678 return;
679 }
680
681 xmlRMutexUnlock(xmlDictMutex);
682
683 if (dict->subdict != NULL) {
684 xmlDictFree(dict->subdict);
685 }
686
687 if (dict->dict) {
688 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
689 iter = &(dict->dict[i]);
690 if (iter->valid == 0)
691 continue;
692 inside_dict = 1;
693 while (iter) {
694 next = iter->next;
695 if (!inside_dict)
696 xmlFree(iter);
697 dict->nbElems--;
698 inside_dict = 0;
699 iter = next;
700 }
701 inside_dict = 0;
702 }
703 xmlFree(dict->dict);
704 }
705 pool = dict->strings;
706 while (pool != NULL) {
707 nextp = pool->next;
708 xmlFree(pool);
709 pool = nextp;
710 }
711 xmlFree(dict);
712 }
713
714 /**
715 * xmlDictLookup:
716 * @dict: the dictionnary
717 * @name: the name of the userdata
718 * @len: the length of the name, if -1 it is recomputed
719 *
720 * Add the @name to the dictionnary @dict if not present.
721 *
722 * Returns the internal copy of the name or NULL in case of internal error
723 */
724 const xmlChar *
xmlDictLookup(xmlDictPtr dict,const xmlChar * name,int len)725 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
726 unsigned long key, okey, nbi = 0;
727 xmlDictEntryPtr entry;
728 xmlDictEntryPtr insert;
729 const xmlChar *ret;
730
731 if ((dict == NULL) || (name == NULL))
732 return(NULL);
733
734 if (len < 0)
735 len = strlen((const char *) name);
736
737 /*
738 * Check for duplicate and insertion location.
739 */
740 okey = xmlDictComputeKey(dict, name, len);
741 key = okey % dict->size;
742 if (dict->dict[key].valid == 0) {
743 insert = NULL;
744 } else {
745 for (insert = &(dict->dict[key]); insert->next != NULL;
746 insert = insert->next) {
747 #ifdef __GNUC__
748 if ((insert->okey == okey) && (insert->len == len)) {
749 if (!memcmp(insert->name, name, len))
750 return(insert->name);
751 }
752 #else
753 if ((insert->okey == okey) && (insert->len == len) &&
754 (!xmlStrncmp(insert->name, name, len)))
755 return(insert->name);
756 #endif
757 nbi++;
758 }
759 #ifdef __GNUC__
760 if ((insert->okey == okey) && (insert->len == len)) {
761 if (!memcmp(insert->name, name, len))
762 return(insert->name);
763 }
764 #else
765 if ((insert->okey == okey) && (insert->len == len) &&
766 (!xmlStrncmp(insert->name, name, len)))
767 return(insert->name);
768 #endif
769 }
770
771 if (dict->subdict) {
772 unsigned long skey;
773
774 /* we cannot always reuse the same okey for the subdict */
775 if (((dict->size == MIN_DICT_SIZE) &&
776 (dict->subdict->size != MIN_DICT_SIZE)) ||
777 ((dict->size != MIN_DICT_SIZE) &&
778 (dict->subdict->size == MIN_DICT_SIZE)))
779 skey = xmlDictComputeKey(dict->subdict, name, len);
780 else
781 skey = okey;
782
783 key = skey % dict->subdict->size;
784 if (dict->subdict->dict[key].valid != 0) {
785 xmlDictEntryPtr tmp;
786
787 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
788 tmp = tmp->next) {
789 #ifdef __GNUC__
790 if ((tmp->okey == skey) && (tmp->len == len)) {
791 if (!memcmp(tmp->name, name, len))
792 return(tmp->name);
793 }
794 #else
795 if ((tmp->okey == skey) && (tmp->len == len) &&
796 (!xmlStrncmp(tmp->name, name, len)))
797 return(tmp->name);
798 #endif
799 nbi++;
800 }
801 #ifdef __GNUC__
802 if ((tmp->okey == skey) && (tmp->len == len)) {
803 if (!memcmp(tmp->name, name, len))
804 return(tmp->name);
805 }
806 #else
807 if ((tmp->okey == skey) && (tmp->len == len) &&
808 (!xmlStrncmp(tmp->name, name, len)))
809 return(tmp->name);
810 #endif
811 }
812 key = okey % dict->size;
813 }
814
815 ret = xmlDictAddString(dict, name, len);
816 if (ret == NULL)
817 return(NULL);
818 if (insert == NULL) {
819 entry = &(dict->dict[key]);
820 } else {
821 entry = xmlMalloc(sizeof(xmlDictEntry));
822 if (entry == NULL)
823 return(NULL);
824 }
825 entry->name = ret;
826 entry->len = len;
827 entry->next = NULL;
828 entry->valid = 1;
829 entry->okey = okey;
830
831
832 if (insert != NULL)
833 insert->next = entry;
834
835 dict->nbElems++;
836
837 if ((nbi > MAX_HASH_LEN) &&
838 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
839 if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
840 return(NULL);
841 }
842 /* Note that entry may have been freed at this point by xmlDictGrow */
843
844 return(ret);
845 }
846
847 /**
848 * xmlDictExists:
849 * @dict: the dictionnary
850 * @name: the name of the userdata
851 * @len: the length of the name, if -1 it is recomputed
852 *
853 * Check if the @name exists in the dictionnary @dict.
854 *
855 * Returns the internal copy of the name or NULL if not found.
856 */
857 const xmlChar *
xmlDictExists(xmlDictPtr dict,const xmlChar * name,int len)858 xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
859 unsigned long key, okey, nbi = 0;
860 xmlDictEntryPtr insert;
861
862 if ((dict == NULL) || (name == NULL))
863 return(NULL);
864
865 if (len < 0)
866 len = strlen((const char *) name);
867
868 /*
869 * Check for duplicate and insertion location.
870 */
871 okey = xmlDictComputeKey(dict, name, len);
872 key = okey % dict->size;
873 if (dict->dict[key].valid == 0) {
874 insert = NULL;
875 } else {
876 for (insert = &(dict->dict[key]); insert->next != NULL;
877 insert = insert->next) {
878 #ifdef __GNUC__
879 if ((insert->okey == okey) && (insert->len == len)) {
880 if (!memcmp(insert->name, name, len))
881 return(insert->name);
882 }
883 #else
884 if ((insert->okey == okey) && (insert->len == len) &&
885 (!xmlStrncmp(insert->name, name, len)))
886 return(insert->name);
887 #endif
888 nbi++;
889 }
890 #ifdef __GNUC__
891 if ((insert->okey == okey) && (insert->len == len)) {
892 if (!memcmp(insert->name, name, len))
893 return(insert->name);
894 }
895 #else
896 if ((insert->okey == okey) && (insert->len == len) &&
897 (!xmlStrncmp(insert->name, name, len)))
898 return(insert->name);
899 #endif
900 }
901
902 if (dict->subdict) {
903 unsigned long skey;
904
905 /* we cannot always reuse the same okey for the subdict */
906 if (((dict->size == MIN_DICT_SIZE) &&
907 (dict->subdict->size != MIN_DICT_SIZE)) ||
908 ((dict->size != MIN_DICT_SIZE) &&
909 (dict->subdict->size == MIN_DICT_SIZE)))
910 skey = xmlDictComputeKey(dict->subdict, name, len);
911 else
912 skey = okey;
913
914 key = skey % dict->subdict->size;
915 if (dict->subdict->dict[key].valid != 0) {
916 xmlDictEntryPtr tmp;
917
918 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
919 tmp = tmp->next) {
920 #ifdef __GNUC__
921 if ((tmp->okey == skey) && (tmp->len == len)) {
922 if (!memcmp(tmp->name, name, len))
923 return(tmp->name);
924 }
925 #else
926 if ((tmp->okey == skey) && (tmp->len == len) &&
927 (!xmlStrncmp(tmp->name, name, len)))
928 return(tmp->name);
929 #endif
930 nbi++;
931 }
932 #ifdef __GNUC__
933 if ((tmp->okey == skey) && (tmp->len == len)) {
934 if (!memcmp(tmp->name, name, len))
935 return(tmp->name);
936 }
937 #else
938 if ((tmp->okey == skey) && (tmp->len == len) &&
939 (!xmlStrncmp(tmp->name, name, len)))
940 return(tmp->name);
941 #endif
942 }
943 }
944
945 /* not found */
946 return(NULL);
947 }
948
949 /**
950 * xmlDictQLookup:
951 * @dict: the dictionnary
952 * @prefix: the prefix
953 * @name: the name
954 *
955 * Add the QName @prefix:@name to the hash @dict if not present.
956 *
957 * Returns the internal copy of the QName or NULL in case of internal error
958 */
959 const xmlChar *
xmlDictQLookup(xmlDictPtr dict,const xmlChar * prefix,const xmlChar * name)960 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
961 unsigned long okey, key, nbi = 0;
962 xmlDictEntryPtr entry;
963 xmlDictEntryPtr insert;
964 const xmlChar *ret;
965 int len, plen, l;
966
967 if ((dict == NULL) || (name == NULL))
968 return(NULL);
969 if (prefix == NULL)
970 return(xmlDictLookup(dict, name, -1));
971
972 l = len = strlen((const char *) name);
973 plen = strlen((const char *) prefix);
974 len += 1 + plen;
975
976 /*
977 * Check for duplicate and insertion location.
978 */
979 okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
980 key = okey % dict->size;
981 if (dict->dict[key].valid == 0) {
982 insert = NULL;
983 } else {
984 for (insert = &(dict->dict[key]); insert->next != NULL;
985 insert = insert->next) {
986 if ((insert->okey == okey) && (insert->len == len) &&
987 (xmlStrQEqual(prefix, name, insert->name)))
988 return(insert->name);
989 nbi++;
990 }
991 if ((insert->okey == okey) && (insert->len == len) &&
992 (xmlStrQEqual(prefix, name, insert->name)))
993 return(insert->name);
994 }
995
996 if (dict->subdict) {
997 unsigned long skey;
998
999 /* we cannot always reuse the same okey for the subdict */
1000 if (((dict->size == MIN_DICT_SIZE) &&
1001 (dict->subdict->size != MIN_DICT_SIZE)) ||
1002 ((dict->size != MIN_DICT_SIZE) &&
1003 (dict->subdict->size == MIN_DICT_SIZE)))
1004 skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1005 else
1006 skey = okey;
1007
1008 key = skey % dict->subdict->size;
1009 if (dict->subdict->dict[key].valid != 0) {
1010 xmlDictEntryPtr tmp;
1011 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1012 tmp = tmp->next) {
1013 if ((tmp->okey == skey) && (tmp->len == len) &&
1014 (xmlStrQEqual(prefix, name, tmp->name)))
1015 return(tmp->name);
1016 nbi++;
1017 }
1018 if ((tmp->okey == skey) && (tmp->len == len) &&
1019 (xmlStrQEqual(prefix, name, tmp->name)))
1020 return(tmp->name);
1021 }
1022 key = okey % dict->size;
1023 }
1024
1025 ret = xmlDictAddQString(dict, prefix, plen, name, l);
1026 if (ret == NULL)
1027 return(NULL);
1028 if (insert == NULL) {
1029 entry = &(dict->dict[key]);
1030 } else {
1031 entry = xmlMalloc(sizeof(xmlDictEntry));
1032 if (entry == NULL)
1033 return(NULL);
1034 }
1035 entry->name = ret;
1036 entry->len = len;
1037 entry->next = NULL;
1038 entry->valid = 1;
1039 entry->okey = okey;
1040
1041 if (insert != NULL)
1042 insert->next = entry;
1043
1044 dict->nbElems++;
1045
1046 if ((nbi > MAX_HASH_LEN) &&
1047 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1048 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1049 /* Note that entry may have been freed at this point by xmlDictGrow */
1050
1051 return(ret);
1052 }
1053
1054 /**
1055 * xmlDictOwns:
1056 * @dict: the dictionnary
1057 * @str: the string
1058 *
1059 * check if a string is owned by the disctionary
1060 *
1061 * Returns 1 if true, 0 if false and -1 in case of error
1062 * -1 in case of error
1063 */
1064 int
xmlDictOwns(xmlDictPtr dict,const xmlChar * str)1065 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1066 xmlDictStringsPtr pool;
1067
1068 if ((dict == NULL) || (str == NULL))
1069 return(-1);
1070 pool = dict->strings;
1071 while (pool != NULL) {
1072 if ((str >= &pool->array[0]) && (str <= pool->free))
1073 return(1);
1074 pool = pool->next;
1075 }
1076 if (dict->subdict)
1077 return(xmlDictOwns(dict->subdict, str));
1078 return(0);
1079 }
1080
1081 /**
1082 * xmlDictSize:
1083 * @dict: the dictionnary
1084 *
1085 * Query the number of elements installed in the hash @dict.
1086 *
1087 * Returns the number of elements in the dictionnary or
1088 * -1 in case of error
1089 */
1090 int
xmlDictSize(xmlDictPtr dict)1091 xmlDictSize(xmlDictPtr dict) {
1092 if (dict == NULL)
1093 return(-1);
1094 if (dict->subdict)
1095 return(dict->nbElems + dict->subdict->nbElems);
1096 return(dict->nbElems);
1097 }
1098
1099
1100 #define bottom_dict
1101 #include "elfgcchack.h"
1102