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