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