Annotation of embedaddon/libxml2/dict.c, revision 1.1
1.1 ! misho 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