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