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) 29typedef 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 */ 69typedef struct _xmlDictEntry xmlDictEntry; 70typedef xmlDictEntry *xmlDictEntryPtr; 71struct _xmlDictEntry { 72 struct _xmlDictEntry *next; 73 const xmlChar *name; 74 int len; 75 int valid; 76 unsigned long okey; 77}; 78 79typedef struct _xmlDictStrings xmlDictStrings; 80typedef xmlDictStrings *xmlDictStringsPtr; 81struct _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 */ 92struct _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 */ 107static xmlRMutexPtr xmlDictMutex = NULL; 108 109/* 110 * Whether the dictionary mutex was initialized. 111 */ 112static 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 */ 121static 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 */ 137void 138xmlDictCleanup(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 */ 157static const xmlChar * 158xmlDictAddString(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 } 194found_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 */ 215static const xmlChar * 216xmlDictAddQString(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 } 256found_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 279static uint32_t 280xmlDictComputeBigKey(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 */ 311static unsigned long 312xmlDictComputeBigQKey(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 */ 348static unsigned long 349xmlDictComputeFastKey(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 */ 382static unsigned long 383xmlDictComputeFastQKey(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 */ 440xmlDictPtr 441xmlDictCreate(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 */ 481xmlDictPtr 482xmlDictCreateSub(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 */ 503int 504xmlDictReference(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 */ 525static int 526xmlDictGrow(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 */ 658void 659xmlDictFree(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 */ 723const xmlChar * 724xmlDictLookup(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 */ 856const xmlChar * 857xmlDictExists(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 */ 958const xmlChar * 959xmlDictQLookup(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 */ 1063int 1064xmlDictOwns(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 */ 1089int 1090xmlDictSize(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" 1101