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