dict.c revision 1b7783879f7122564e209c7124301e886079f393
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#include <libxml/tree.h> 24#include <libxml/dict.h> 25#include <libxml/xmlmemory.h> 26#include <libxml/xmlerror.h> 27#include <libxml/globals.h> 28 29#define MAX_HASH_LEN 4 30#define MIN_DICT_SIZE 128 31#define MAX_DICT_HASH 8 * 2048 32 33/* #define ALLOW_REMOVAL */ 34/* #define DEBUG_GROW */ 35 36/* 37 * An entry in the dictionnary 38 */ 39typedef struct _xmlDictEntry xmlDictEntry; 40typedef xmlDictEntry *xmlDictEntryPtr; 41struct _xmlDictEntry { 42 struct _xmlDictEntry *next; 43 const xmlChar *name; 44 int len; 45 int valid; 46}; 47 48typedef struct _xmlDictStrings xmlDictStrings; 49typedef xmlDictStrings *xmlDictStringsPtr; 50struct _xmlDictStrings { 51 xmlDictStringsPtr next; 52 xmlChar *free; 53 xmlChar *end; 54 int size; 55 int nbStrings; 56 xmlChar array[1]; 57}; 58/* 59 * The entire dictionnary 60 */ 61struct _xmlDict { 62 int ref_counter; 63 xmlRMutexPtr mutex; 64 65 struct _xmlDictEntry *dict; 66 int size; 67 int nbElems; 68 xmlDictStringsPtr strings; 69 70 struct _xmlDict *subdict; 71}; 72 73/* 74 * A mutex for modifying the reference counter for shared 75 * dictionaries. 76 */ 77static xmlRMutexPtr xmlDictMutex = NULL; 78 79/* 80 * Whether the dictionary mutex was initialized. 81 */ 82static int xmlDictInitialized = 0; 83 84/** 85 * xmlInitializeDict: 86 * 87 * Do the dictionary mutex initialization. 88 * this function is not thread safe, initialization should 89 * preferably be done once at startup 90 */ 91static int xmlInitializeDict(void) { 92 if (xmlDictInitialized) 93 return(1); 94 95 if ((xmlDictMutex = xmlNewRMutex()) == NULL) 96 return(0); 97 98 xmlDictInitialized = 1; 99 return(1); 100} 101 102/** 103 * xmlDictCleanup: 104 * 105 * Free the dictionary mutex. 106 */ 107void 108xmlDictCleanup(void) { 109 if (!xmlDictInitialized) 110 return; 111 112 xmlFreeRMutex(xmlDictMutex); 113 114 xmlDictInitialized = 0; 115} 116 117/* 118 * xmlDictAddString: 119 * @dict: the dictionnary 120 * @name: the name of the userdata 121 * @len: the length of the name, if -1 it is recomputed 122 * 123 * Add the string to the array[s] 124 * 125 * Returns the pointer of the local string, or NULL in case of error. 126 */ 127static const xmlChar * 128xmlDictAddString(xmlDictPtr dict, const xmlChar *name, int namelen) { 129 xmlDictStringsPtr pool; 130 const xmlChar *ret; 131 int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */ 132 133 pool = dict->strings; 134 while (pool != NULL) { 135 if (pool->end - pool->free > namelen) 136 goto found_pool; 137 if (pool->size > size) size = pool->size; 138 pool = pool->next; 139 } 140 /* 141 * Not found, need to allocate 142 */ 143 if (pool == NULL) { 144 if (size == 0) size = 1000; 145 else size *= 4; /* exponential growth */ 146 if (size < 4 * namelen) 147 size = 4 * namelen; /* just in case ! */ 148 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size); 149 if (pool == NULL) 150 return(NULL); 151 pool->size = size; 152 pool->nbStrings = 0; 153 pool->free = &pool->array[0]; 154 pool->end = &pool->array[size]; 155 pool->next = dict->strings; 156 dict->strings = pool; 157 } 158found_pool: 159 ret = pool->free; 160 memcpy(pool->free, name, namelen); 161 pool->free += namelen; 162 *(pool->free++) = 0; 163 return(ret); 164} 165 166/* 167 * xmlDictAddQString: 168 * @dict: the dictionnary 169 * @prefix: the prefix of the userdata 170 * @name: the name of the userdata 171 * @len: the length of the name, if -1 it is recomputed 172 * 173 * Add the QName to the array[s] 174 * 175 * Returns the pointer of the local string, or NULL in case of error. 176 */ 177static const xmlChar * 178xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, 179 const xmlChar *name, int namelen) 180{ 181 xmlDictStringsPtr pool; 182 const xmlChar *ret; 183 int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */ 184 int plen; 185 186 if (prefix == NULL) return(xmlDictAddString(dict, name, namelen)); 187 plen = xmlStrlen(prefix); 188 189 pool = dict->strings; 190 while (pool != NULL) { 191 if (pool->end - pool->free > namelen) 192 goto found_pool; 193 if (pool->size > size) size = pool->size; 194 pool = pool->next; 195 } 196 /* 197 * Not found, need to allocate 198 */ 199 if (pool == NULL) { 200 if (size == 0) size = 1000; 201 else size *= 4; /* exponential growth */ 202 if (size < 4 * namelen) 203 size = 4 * namelen; /* just in case ! */ 204 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size); 205 if (pool == NULL) 206 return(NULL); 207 pool->size = size; 208 pool->nbStrings = 0; 209 pool->free = &pool->array[0]; 210 pool->end = &pool->array[size]; 211 pool->next = dict->strings; 212 dict->strings = pool; 213 } 214found_pool: 215 ret = pool->free; 216 memcpy(pool->free, prefix, plen); 217 pool->free += plen; 218 *(pool->free++) = ':'; 219 namelen -= plen + 1; 220 memcpy(pool->free, name, namelen); 221 pool->free += namelen; 222 *(pool->free++) = 0; 223 return(ret); 224} 225 226/* 227 * xmlDictComputeKey: 228 * Calculate the hash key 229 */ 230static unsigned long 231xmlDictComputeKey(const xmlChar *name, int namelen) { 232 unsigned long value = 0L; 233 234 if (name == NULL) return(0); 235 value = *name; 236 value <<= 5; 237 if (namelen > 10) { 238 value += name[namelen - 1]; 239 namelen = 10; 240 } 241 switch (namelen) { 242 case 10: value += name[9]; 243 case 9: value += name[8]; 244 case 8: value += name[7]; 245 case 7: value += name[6]; 246 case 6: value += name[5]; 247 case 5: value += name[4]; 248 case 4: value += name[3]; 249 case 3: value += name[2]; 250 case 2: value += name[1]; 251 default: break; 252 } 253 return(value); 254} 255 256/* 257 * xmlDictComputeQKey: 258 * Calculate the hash key 259 */ 260static unsigned long 261xmlDictComputeQKey(const xmlChar *prefix, const xmlChar *name, int len) 262{ 263 unsigned long value = 0L; 264 int plen; 265 266 if (prefix == NULL) 267 return(xmlDictComputeKey(name, len)); 268 269 plen = xmlStrlen(prefix); 270 if (plen == 0) 271 value += 30 * (unsigned long) ':'; 272 else 273 value += 30 * (*prefix); 274 275 if (len > 10) { 276 value += name[len - (plen + 1 + 1)]; 277 len = 10; 278 if (plen > 10) 279 plen = 10; 280 } 281 switch (plen) { 282 case 10: value += prefix[9]; 283 case 9: value += prefix[8]; 284 case 8: value += prefix[7]; 285 case 7: value += prefix[6]; 286 case 6: value += prefix[5]; 287 case 5: value += prefix[4]; 288 case 4: value += prefix[3]; 289 case 3: value += prefix[2]; 290 case 2: value += prefix[1]; 291 case 1: value += prefix[0]; 292 default: break; 293 } 294 len -= plen; 295 if (len > 0) { 296 value += (unsigned long) ':'; 297 len--; 298 } 299 switch (len) { 300 case 10: value += name[9]; 301 case 9: value += name[8]; 302 case 8: value += name[7]; 303 case 7: value += name[6]; 304 case 6: value += name[5]; 305 case 5: value += name[4]; 306 case 4: value += name[3]; 307 case 3: value += name[2]; 308 case 2: value += name[1]; 309 case 1: value += name[0]; 310 default: break; 311 } 312 return(value); 313} 314 315/** 316 * xmlDictCreate: 317 * 318 * Create a new dictionary 319 * 320 * Returns the newly created dictionnary, or NULL if an error occured. 321 */ 322xmlDictPtr 323xmlDictCreate(void) { 324 xmlDictPtr dict; 325 326 if (!xmlDictInitialized) 327 if (!xmlInitializeDict()) 328 return(NULL); 329 330 dict = xmlMalloc(sizeof(xmlDict)); 331 if (dict) { 332 dict->ref_counter = 1; 333 334 dict->size = MIN_DICT_SIZE; 335 dict->nbElems = 0; 336 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry)); 337 dict->strings = NULL; 338 dict->subdict = NULL; 339 if (dict->dict) { 340 if ((dict->mutex = xmlNewRMutex()) != NULL) { 341 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry)); 342 return(dict); 343 } 344 xmlFree(dict->dict); 345 } 346 xmlFree(dict); 347 } 348 return(NULL); 349} 350 351/** 352 * xmlDictCreateSub: 353 * @sub: an existing dictionnary 354 * 355 * Create a new dictionary, inheriting strings from the read-only 356 * dictionnary @sub. On lookup, strings are first searched in the 357 * new dictionnary, then in @sub, and if not found are created in the 358 * new dictionnary. 359 * 360 * Returns the newly created dictionnary, or NULL if an error occured. 361 */ 362xmlDictPtr 363xmlDictCreateSub(xmlDictPtr sub) { 364 xmlDictPtr dict = xmlDictCreate(); 365 366 if ((dict != NULL) && (sub != NULL)) { 367 dict->subdict = sub; 368 xmlDictReference(dict->subdict); 369 } 370 return(dict); 371} 372 373/** 374 * xmlDictReference: 375 * @dict: the dictionnary 376 * 377 * Increment the reference counter of a dictionary 378 * 379 * Returns 0 in case of success and -1 in case of error 380 */ 381int 382xmlDictReference(xmlDictPtr dict) { 383 if (!xmlDictInitialized) 384 if (!xmlInitializeDict()) 385 return(-1); 386 387 if (dict == NULL) return -1; 388 xmlRMutexLock(xmlDictMutex); 389 dict->ref_counter++; 390 xmlRMutexUnlock(xmlDictMutex); 391 return(0); 392} 393 394/** 395 * xmlDictGrow: 396 * @dict: the dictionnary 397 * @size: the new size of the dictionnary 398 * 399 * resize the dictionnary 400 * 401 * Returns 0 in case of success, -1 in case of failure 402 */ 403static int 404xmlDictGrow(xmlDictPtr dict, int size) { 405 unsigned long key; 406 int oldsize, i; 407 xmlDictEntryPtr iter, next; 408 struct _xmlDictEntry *olddict; 409#ifdef DEBUG_GROW 410 unsigned long nbElem = 0; 411#endif 412 413 if (dict == NULL) 414 return(-1); 415 if (size < 8) 416 return(-1); 417 if (size > 8 * 2048) 418 return(-1); 419 420 oldsize = dict->size; 421 olddict = dict->dict; 422 if (olddict == NULL) 423 return(-1); 424 425 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry)); 426 if (dict->dict == NULL) { 427 dict->dict = olddict; 428 return(-1); 429 } 430 memset(dict->dict, 0, size * sizeof(xmlDictEntry)); 431 dict->size = size; 432 433 /* If the two loops are merged, there would be situations where 434 a new entry needs to allocated and data copied into it from 435 the main dict. So instead, we run through the array twice, first 436 copying all the elements in the main array (where we can't get 437 conflicts) and then the rest, so we only free (and don't allocate) 438 */ 439 for (i = 0; i < oldsize; i++) { 440 if (olddict[i].valid == 0) 441 continue; 442 key = xmlDictComputeKey(olddict[i].name, olddict[i].len) % dict->size; 443 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry)); 444 dict->dict[key].next = NULL; 445#ifdef DEBUG_GROW 446 nbElem++; 447#endif 448 } 449 450 for (i = 0; i < oldsize; i++) { 451 iter = olddict[i].next; 452 while (iter) { 453 next = iter->next; 454 455 /* 456 * put back the entry in the new dict 457 */ 458 459 key = xmlDictComputeKey(iter->name, iter->len) % dict->size; 460 if (dict->dict[key].valid == 0) { 461 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry)); 462 dict->dict[key].next = NULL; 463 dict->dict[key].valid = 1; 464 xmlFree(iter); 465 } else { 466 iter->next = dict->dict[key].next; 467 dict->dict[key].next = iter; 468 } 469 470#ifdef DEBUG_GROW 471 nbElem++; 472#endif 473 474 iter = next; 475 } 476 } 477 478 xmlFree(olddict); 479 480#ifdef DEBUG_GROW 481 xmlGenericError(xmlGenericErrorContext, 482 "xmlDictGrow : from %d to %d, %d elems\n", oldsize, size, nbElem); 483#endif 484 485 return(0); 486} 487 488/** 489 * xmlDictFree: 490 * @dict: the dictionnary 491 * 492 * Free the hash @dict and its contents. The userdata is 493 * deallocated with @f if provided. 494 */ 495void 496xmlDictFree(xmlDictPtr dict) { 497 int i; 498 xmlDictEntryPtr iter; 499 xmlDictEntryPtr next; 500 int inside_dict = 0; 501 xmlDictStringsPtr pool, nextp; 502 503 if (dict == NULL) 504 return; 505 506 if (!xmlDictInitialized) 507 if (!xmlInitializeDict()) 508 return; 509 510 /* decrement the counter, it may be shared by a parser and docs */ 511 xmlRMutexLock(xmlDictMutex); 512 dict->ref_counter--; 513 if (dict->ref_counter > 0) { 514 xmlRMutexUnlock(xmlDictMutex); 515 return; 516 } 517 518 xmlRMutexUnlock(xmlDictMutex); 519 520 if (dict->subdict != NULL) { 521 xmlDictFree(dict->subdict); 522 } 523 524 if (dict->dict) { 525 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) { 526 iter = &(dict->dict[i]); 527 if (iter->valid == 0) 528 continue; 529 inside_dict = 1; 530 while (iter) { 531 next = iter->next; 532 if (!inside_dict) 533 xmlFree(iter); 534 dict->nbElems--; 535 inside_dict = 0; 536 iter = next; 537 } 538 inside_dict = 0; 539 } 540 xmlFree(dict->dict); 541 } 542 pool = dict->strings; 543 while (pool != NULL) { 544 nextp = pool->next; 545 xmlFree(pool); 546 pool = nextp; 547 } 548 xmlFreeRMutex(dict->mutex); 549 xmlFree(dict); 550} 551 552/** 553 * xmlDictLookup: 554 * @dict: the dictionnary 555 * @name: the name of the userdata 556 * @len: the length of the name, if -1 it is recomputed 557 * 558 * Add the @name to the dictionnary @dict if not present. 559 * 560 * Returns the internal copy of the name or NULL in case of internal error 561 */ 562const xmlChar * 563xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) { 564 unsigned long key, okey, nbi = 0; 565 xmlDictEntryPtr entry; 566 xmlDictEntryPtr insert; 567 const xmlChar *ret; 568 569 if ((dict == NULL) || (name == NULL)) 570 return(NULL); 571 572 if (len < 0) 573 len = xmlStrlen(name); 574 575 /* 576 * Check for duplicate and insertion location. 577 */ 578 okey = xmlDictComputeKey(name, len); 579 key = okey % dict->size; 580 if (dict->dict[key].valid == 0) { 581 insert = NULL; 582 } else { 583 for (insert = &(dict->dict[key]); insert->next != NULL; 584 insert = insert->next) { 585#ifdef __GNUC__ 586 if (insert->len == len) { 587 if (!memcmp(insert->name, name, len)) 588 return(insert->name); 589 } 590#else 591 if ((insert->len == len) && 592 (!xmlStrncmp(insert->name, name, len))) 593 return(insert->name); 594#endif 595 nbi++; 596 } 597#ifdef __GNUC__ 598 if (insert->len == len) { 599 if (!memcmp(insert->name, name, len)) 600 return(insert->name); 601 } 602#else 603 if ((insert->len == len) && 604 (!xmlStrncmp(insert->name, name, len))) 605 return(insert->name); 606#endif 607 } 608 609 if (dict->subdict) { 610 key = okey % dict->subdict->size; 611 if (dict->subdict->dict[key].valid != 0) { 612 xmlDictEntryPtr tmp; 613 614 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; 615 tmp = tmp->next) { 616#ifdef __GNUC__ 617 if (tmp->len == len) { 618 if (!memcmp(tmp->name, name, len)) 619 return(tmp->name); 620 } 621#else 622 if ((tmp->len == len) && 623 (!xmlStrncmp(tmp->name, name, len))) 624 return(tmp->name); 625#endif 626 nbi++; 627 } 628#ifdef __GNUC__ 629 if (tmp->len == len) { 630 if (!memcmp(tmp->name, name, len)) 631 return(tmp->name); 632 } 633#else 634 if ((tmp->len == len) && 635 (!xmlStrncmp(tmp->name, name, len))) 636 return(tmp->name); 637#endif 638 } 639 key = okey % dict->size; 640 } 641 642 ret = xmlDictAddString(dict, name, len); 643 if (ret == NULL) 644 return(NULL); 645 if (insert == NULL) { 646 entry = &(dict->dict[key]); 647 } else { 648 entry = xmlMalloc(sizeof(xmlDictEntry)); 649 if (entry == NULL) 650 return(NULL); 651 } 652 entry->name = ret; 653 entry->len = len; 654 entry->next = NULL; 655 entry->valid = 1; 656 657 658 if (insert != NULL) 659 insert->next = entry; 660 661 dict->nbElems++; 662 663 if ((nbi > MAX_HASH_LEN) && 664 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) 665 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size); 666 /* Note that entry may have been freed at this point by xmlDictGrow */ 667 668 return(ret); 669} 670 671/** 672 * xmlDictExists: 673 * @dict: the dictionnary 674 * @name: the name of the userdata 675 * @len: the length of the name, if -1 it is recomputed 676 * 677 * Check if the @name exists in the dictionnary @dict. 678 * 679 * Returns the internal copy of the name or NULL if not found. 680 */ 681const xmlChar * 682xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) { 683 unsigned long key, okey, nbi = 0; 684 xmlDictEntryPtr insert; 685 686 if ((dict == NULL) || (name == NULL)) 687 return(NULL); 688 689 if (len < 0) 690 len = xmlStrlen(name); 691 692 /* 693 * Check for duplicate and insertion location. 694 */ 695 okey = xmlDictComputeKey(name, len); 696 key = okey % dict->size; 697 if (dict->dict[key].valid == 0) { 698 insert = NULL; 699 } else { 700 for (insert = &(dict->dict[key]); insert->next != NULL; 701 insert = insert->next) { 702#ifdef __GNUC__ 703 if (insert->len == len) { 704 if (!memcmp(insert->name, name, len)) 705 return(insert->name); 706 } 707#else 708 if ((insert->len == len) && 709 (!xmlStrncmp(insert->name, name, len))) 710 return(insert->name); 711#endif 712 nbi++; 713 } 714#ifdef __GNUC__ 715 if (insert->len == len) { 716 if (!memcmp(insert->name, name, len)) 717 return(insert->name); 718 } 719#else 720 if ((insert->len == len) && 721 (!xmlStrncmp(insert->name, name, len))) 722 return(insert->name); 723#endif 724 } 725 726 if (dict->subdict) { 727 key = okey % dict->subdict->size; 728 if (dict->subdict->dict[key].valid != 0) { 729 xmlDictEntryPtr tmp; 730 731 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; 732 tmp = tmp->next) { 733#ifdef __GNUC__ 734 if (tmp->len == len) { 735 if (!memcmp(tmp->name, name, len)) 736 return(tmp->name); 737 } 738#else 739 if ((tmp->len == len) && 740 (!xmlStrncmp(tmp->name, name, len))) 741 return(tmp->name); 742#endif 743 nbi++; 744 } 745#ifdef __GNUC__ 746 if (tmp->len == len) { 747 if (!memcmp(tmp->name, name, len)) 748 return(tmp->name); 749 } 750#else 751 if ((tmp->len == len) && 752 (!xmlStrncmp(tmp->name, name, len))) 753 return(tmp->name); 754#endif 755 } 756 key = okey % dict->size; 757 } 758 759 /* not found */ 760 return(NULL); 761} 762 763/** 764 * xmlDictQLookup: 765 * @dict: the dictionnary 766 * @prefix: the prefix 767 * @name: the name 768 * 769 * Add the QName @prefix:@name to the hash @dict if not present. 770 * 771 * Returns the internal copy of the QName or NULL in case of internal error 772 */ 773const xmlChar * 774xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) { 775 unsigned long okey, key, nbi = 0; 776 xmlDictEntryPtr entry; 777 xmlDictEntryPtr insert; 778 const xmlChar *ret; 779 int len; 780 781 if ((dict == NULL) || (name == NULL)) 782 return(NULL); 783 784 len = xmlStrlen(name); 785 if (prefix != NULL) 786 len += 1 + xmlStrlen(prefix); 787 788 /* 789 * Check for duplicate and insertion location. 790 */ 791 okey = xmlDictComputeQKey(prefix, name, len); 792 key = okey % dict->size; 793 if (dict->dict[key].valid == 0) { 794 insert = NULL; 795 } else { 796 for (insert = &(dict->dict[key]); insert->next != NULL; 797 insert = insert->next) { 798 if ((insert->len == len) && 799 (xmlStrQEqual(prefix, name, insert->name))) 800 return(insert->name); 801 nbi++; 802 } 803 if ((insert->len == len) && 804 (xmlStrQEqual(prefix, name, insert->name))) 805 return(insert->name); 806 } 807 808 if (dict->subdict) { 809 key = okey % dict->subdict->size; 810 if (dict->subdict->dict[key].valid != 0) { 811 xmlDictEntryPtr tmp; 812 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; 813 tmp = tmp->next) { 814 if ((tmp->len == len) && 815 (xmlStrQEqual(prefix, name, tmp->name))) 816 return(tmp->name); 817 nbi++; 818 } 819 if ((tmp->len == len) && 820 (xmlStrQEqual(prefix, name, tmp->name))) 821 return(tmp->name); 822 } 823 key = okey % dict->size; 824 } 825 826 ret = xmlDictAddQString(dict, prefix, name, len); 827 if (ret == NULL) 828 return(NULL); 829 if (insert == NULL) { 830 entry = &(dict->dict[key]); 831 } else { 832 entry = xmlMalloc(sizeof(xmlDictEntry)); 833 if (entry == NULL) 834 return(NULL); 835 } 836 entry->name = ret; 837 entry->len = len; 838 entry->next = NULL; 839 entry->valid = 1; 840 841 if (insert != NULL) 842 insert->next = entry; 843 844 dict->nbElems++; 845 846 if ((nbi > MAX_HASH_LEN) && 847 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) 848 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size); 849 /* Note that entry may have been freed at this point by xmlDictGrow */ 850 851 return(ret); 852} 853 854/** 855 * xmlDictOwns: 856 * @dict: the dictionnary 857 * @str: the string 858 * 859 * check if a string is owned by the disctionary 860 * 861 * Returns 1 if true, 0 if false and -1 in case of error 862 * -1 in case of error 863 */ 864int 865xmlDictOwns(xmlDictPtr dict, const xmlChar *str) { 866 xmlDictStringsPtr pool; 867 868 if ((dict == NULL) || (str == NULL)) 869 return(-1); 870 pool = dict->strings; 871 while (pool != NULL) { 872 if ((str >= &pool->array[0]) && (str <= pool->free)) 873 return(1); 874 pool = pool->next; 875 } 876 if (dict->subdict) 877 return(xmlDictOwns(dict->subdict, str)); 878 return(0); 879} 880 881/** 882 * xmlDictSize: 883 * @dict: the dictionnary 884 * 885 * Query the number of elements installed in the hash @dict. 886 * 887 * Returns the number of elements in the dictionnary or 888 * -1 in case of error 889 */ 890int 891xmlDictSize(xmlDictPtr dict) { 892 if (dict == NULL) 893 return(-1); 894 if (dict->subdict) 895 return(dict->nbElems + dict->subdict->nbElems); 896 return(dict->nbElems); 897} 898 899 900#define bottom_dict 901#include "elfgcchack.h" 902