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: */
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
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 *
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 *
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
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
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
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
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
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
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
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
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
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: }
702: xmlFree(dict->dict);
703: }
704: pool = dict->strings;
705: while (pool != NULL) {
706: nextp = pool->next;
707: xmlFree(pool);
708: pool = nextp;
709: }
710: xmlFree(dict);
711: }
712:
713: /**
714: * xmlDictLookup:
715: * @dict: the dictionnary
716: * @name: the name of the userdata
717: * @len: the length of the name, if -1 it is recomputed
718: *
719: * Add the @name to the dictionnary @dict if not present.
720: *
721: * Returns the internal copy of the name or NULL in case of internal error
722: */
723: const xmlChar *
724: xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
725: unsigned long key, okey, nbi = 0;
726: xmlDictEntryPtr entry;
727: xmlDictEntryPtr insert;
728: const xmlChar *ret;
729:
730: if ((dict == NULL) || (name == NULL))
731: return(NULL);
732:
733: if (len < 0)
734: len = strlen((const char *) name);
735:
736: /*
737: * Check for duplicate and insertion location.
738: */
739: okey = xmlDictComputeKey(dict, name, len);
740: key = okey % dict->size;
741: if (dict->dict[key].valid == 0) {
742: insert = NULL;
743: } else {
744: for (insert = &(dict->dict[key]); insert->next != NULL;
745: insert = insert->next) {
746: #ifdef __GNUC__
747: if ((insert->okey == okey) && (insert->len == len)) {
748: if (!memcmp(insert->name, name, len))
749: return(insert->name);
750: }
751: #else
752: if ((insert->okey == okey) && (insert->len == len) &&
753: (!xmlStrncmp(insert->name, name, len)))
754: return(insert->name);
755: #endif
756: nbi++;
757: }
758: #ifdef __GNUC__
759: if ((insert->okey == okey) && (insert->len == len)) {
760: if (!memcmp(insert->name, name, len))
761: return(insert->name);
762: }
763: #else
764: if ((insert->okey == okey) && (insert->len == len) &&
765: (!xmlStrncmp(insert->name, name, len)))
766: return(insert->name);
767: #endif
768: }
769:
770: if (dict->subdict) {
771: unsigned long skey;
772:
773: /* we cannot always reuse the same okey for the subdict */
774: if (((dict->size == MIN_DICT_SIZE) &&
775: (dict->subdict->size != MIN_DICT_SIZE)) ||
776: ((dict->size != MIN_DICT_SIZE) &&
777: (dict->subdict->size == MIN_DICT_SIZE)))
778: skey = xmlDictComputeKey(dict->subdict, name, len);
779: else
780: skey = okey;
781:
782: key = skey % dict->subdict->size;
783: if (dict->subdict->dict[key].valid != 0) {
784: xmlDictEntryPtr tmp;
785:
786: for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
787: tmp = tmp->next) {
788: #ifdef __GNUC__
789: if ((tmp->okey == skey) && (tmp->len == len)) {
790: if (!memcmp(tmp->name, name, len))
791: return(tmp->name);
792: }
793: #else
794: if ((tmp->okey == skey) && (tmp->len == len) &&
795: (!xmlStrncmp(tmp->name, name, len)))
796: return(tmp->name);
797: #endif
798: nbi++;
799: }
800: #ifdef __GNUC__
801: if ((tmp->okey == skey) && (tmp->len == len)) {
802: if (!memcmp(tmp->name, name, len))
803: return(tmp->name);
804: }
805: #else
806: if ((tmp->okey == skey) && (tmp->len == len) &&
807: (!xmlStrncmp(tmp->name, name, len)))
808: return(tmp->name);
809: #endif
810: }
811: key = okey % dict->size;
812: }
813:
814: ret = xmlDictAddString(dict, name, len);
815: if (ret == NULL)
816: return(NULL);
817: if (insert == NULL) {
818: entry = &(dict->dict[key]);
819: } else {
820: entry = xmlMalloc(sizeof(xmlDictEntry));
821: if (entry == NULL)
822: return(NULL);
823: }
824: entry->name = ret;
825: entry->len = len;
826: entry->next = NULL;
827: entry->valid = 1;
828: entry->okey = okey;
829:
830:
831: if (insert != NULL)
832: insert->next = entry;
833:
834: dict->nbElems++;
835:
836: if ((nbi > MAX_HASH_LEN) &&
837: (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
838: if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
839: return(NULL);
840: }
841: /* Note that entry may have been freed at this point by xmlDictGrow */
842:
843: return(ret);
844: }
845:
846: /**
847: * xmlDictExists:
848: * @dict: the dictionnary
849: * @name: the name of the userdata
850: * @len: the length of the name, if -1 it is recomputed
851: *
852: * Check if the @name exists in the dictionnary @dict.
853: *
854: * Returns the internal copy of the name or NULL if not found.
855: */
856: const xmlChar *
857: xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
858: unsigned long key, okey, nbi = 0;
859: xmlDictEntryPtr insert;
860:
861: if ((dict == NULL) || (name == NULL))
862: return(NULL);
863:
864: if (len < 0)
865: len = strlen((const char *) name);
866:
867: /*
868: * Check for duplicate and insertion location.
869: */
870: okey = xmlDictComputeKey(dict, name, len);
871: key = okey % dict->size;
872: if (dict->dict[key].valid == 0) {
873: insert = NULL;
874: } else {
875: for (insert = &(dict->dict[key]); insert->next != NULL;
876: insert = insert->next) {
877: #ifdef __GNUC__
878: if ((insert->okey == okey) && (insert->len == len)) {
879: if (!memcmp(insert->name, name, len))
880: return(insert->name);
881: }
882: #else
883: if ((insert->okey == okey) && (insert->len == len) &&
884: (!xmlStrncmp(insert->name, name, len)))
885: return(insert->name);
886: #endif
887: nbi++;
888: }
889: #ifdef __GNUC__
890: if ((insert->okey == okey) && (insert->len == len)) {
891: if (!memcmp(insert->name, name, len))
892: return(insert->name);
893: }
894: #else
895: if ((insert->okey == okey) && (insert->len == len) &&
896: (!xmlStrncmp(insert->name, name, len)))
897: return(insert->name);
898: #endif
899: }
900:
901: if (dict->subdict) {
902: unsigned long skey;
903:
904: /* we cannot always reuse the same okey for the subdict */
905: if (((dict->size == MIN_DICT_SIZE) &&
906: (dict->subdict->size != MIN_DICT_SIZE)) ||
907: ((dict->size != MIN_DICT_SIZE) &&
908: (dict->subdict->size == MIN_DICT_SIZE)))
909: skey = xmlDictComputeKey(dict->subdict, name, len);
910: else
911: skey = okey;
912:
913: key = skey % dict->subdict->size;
914: if (dict->subdict->dict[key].valid != 0) {
915: xmlDictEntryPtr tmp;
916:
917: for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
918: tmp = tmp->next) {
919: #ifdef __GNUC__
920: if ((tmp->okey == skey) && (tmp->len == len)) {
921: if (!memcmp(tmp->name, name, len))
922: return(tmp->name);
923: }
924: #else
925: if ((tmp->okey == skey) && (tmp->len == len) &&
926: (!xmlStrncmp(tmp->name, name, len)))
927: return(tmp->name);
928: #endif
929: nbi++;
930: }
931: #ifdef __GNUC__
932: if ((tmp->okey == skey) && (tmp->len == len)) {
933: if (!memcmp(tmp->name, name, len))
934: return(tmp->name);
935: }
936: #else
937: if ((tmp->okey == skey) && (tmp->len == len) &&
938: (!xmlStrncmp(tmp->name, name, len)))
939: return(tmp->name);
940: #endif
941: }
942: }
943:
944: /* not found */
945: return(NULL);
946: }
947:
948: /**
949: * xmlDictQLookup:
950: * @dict: the dictionnary
951: * @prefix: the prefix
952: * @name: the name
953: *
954: * Add the QName @prefix:@name to the hash @dict if not present.
955: *
956: * Returns the internal copy of the QName or NULL in case of internal error
957: */
958: const xmlChar *
959: xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
960: unsigned long okey, key, nbi = 0;
961: xmlDictEntryPtr entry;
962: xmlDictEntryPtr insert;
963: const xmlChar *ret;
964: int len, plen, l;
965:
966: if ((dict == NULL) || (name == NULL))
967: return(NULL);
968: if (prefix == NULL)
969: return(xmlDictLookup(dict, name, -1));
970:
971: l = len = strlen((const char *) name);
972: plen = strlen((const char *) prefix);
973: len += 1 + plen;
974:
975: /*
976: * Check for duplicate and insertion location.
977: */
978: okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
979: key = okey % dict->size;
980: if (dict->dict[key].valid == 0) {
981: insert = NULL;
982: } else {
983: for (insert = &(dict->dict[key]); insert->next != NULL;
984: insert = insert->next) {
985: if ((insert->okey == okey) && (insert->len == len) &&
986: (xmlStrQEqual(prefix, name, insert->name)))
987: return(insert->name);
988: nbi++;
989: }
990: if ((insert->okey == okey) && (insert->len == len) &&
991: (xmlStrQEqual(prefix, name, insert->name)))
992: return(insert->name);
993: }
994:
995: if (dict->subdict) {
996: unsigned long skey;
997:
998: /* we cannot always reuse the same okey for the subdict */
999: if (((dict->size == MIN_DICT_SIZE) &&
1000: (dict->subdict->size != MIN_DICT_SIZE)) ||
1001: ((dict->size != MIN_DICT_SIZE) &&
1002: (dict->subdict->size == MIN_DICT_SIZE)))
1003: skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1004: else
1005: skey = okey;
1006:
1007: key = skey % dict->subdict->size;
1008: if (dict->subdict->dict[key].valid != 0) {
1009: xmlDictEntryPtr tmp;
1010: for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1011: tmp = tmp->next) {
1012: if ((tmp->okey == skey) && (tmp->len == len) &&
1013: (xmlStrQEqual(prefix, name, tmp->name)))
1014: return(tmp->name);
1015: nbi++;
1016: }
1017: if ((tmp->okey == skey) && (tmp->len == len) &&
1018: (xmlStrQEqual(prefix, name, tmp->name)))
1019: return(tmp->name);
1020: }
1021: key = okey % dict->size;
1022: }
1023:
1024: ret = xmlDictAddQString(dict, prefix, plen, name, l);
1025: if (ret == NULL)
1026: return(NULL);
1027: if (insert == NULL) {
1028: entry = &(dict->dict[key]);
1029: } else {
1030: entry = xmlMalloc(sizeof(xmlDictEntry));
1031: if (entry == NULL)
1032: return(NULL);
1033: }
1034: entry->name = ret;
1035: entry->len = len;
1036: entry->next = NULL;
1037: entry->valid = 1;
1038: entry->okey = okey;
1039:
1040: if (insert != NULL)
1041: insert->next = entry;
1042:
1043: dict->nbElems++;
1044:
1045: if ((nbi > MAX_HASH_LEN) &&
1046: (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1047: xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1048: /* Note that entry may have been freed at this point by xmlDictGrow */
1049:
1050: return(ret);
1051: }
1052:
1053: /**
1054: * xmlDictOwns:
1055: * @dict: the dictionnary
1056: * @str: the string
1057: *
1058: * check if a string is owned by the disctionary
1059: *
1060: * Returns 1 if true, 0 if false and -1 in case of error
1061: * -1 in case of error
1062: */
1063: int
1064: xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1065: xmlDictStringsPtr pool;
1066:
1067: if ((dict == NULL) || (str == NULL))
1068: return(-1);
1069: pool = dict->strings;
1070: while (pool != NULL) {
1071: if ((str >= &pool->array[0]) && (str <= pool->free))
1072: return(1);
1073: pool = pool->next;
1074: }
1075: if (dict->subdict)
1076: return(xmlDictOwns(dict->subdict, str));
1077: return(0);
1078: }
1079:
1080: /**
1081: * xmlDictSize:
1082: * @dict: the dictionnary
1083: *
1084: * Query the number of elements installed in the hash @dict.
1085: *
1086: * Returns the number of elements in the dictionnary or
1087: * -1 in case of error
1088: */
1089: int
1090: xmlDictSize(xmlDictPtr dict) {
1091: if (dict == NULL)
1092: return(-1);
1093: if (dict->subdict)
1094: return(dict->nbElems + dict->subdict->nbElems);
1095: return(dict->nbElems);
1096: }
1097:
1098:
1099: #define bottom_dict
1100: #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