1 /* 2 * hash.c: chained hash tables 3 * 4 * Reference: Your favorite introductory book on algorithms 5 * 6 * Copyright (C) 2000,2012 Bjorn Reese and Daniel Veillard. 7 * 8 * Permission to use, copy, modify, and distribute this software for any 9 * purpose with or without fee is hereby granted, provided that the above 10 * copyright notice and this permission notice appear in all copies. 11 * 12 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 13 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 14 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND 15 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER. 16 * 17 * Author: breese (at) users.sourceforge.net 18 */ 19 20 #define IN_LIBXML 21 #include "libxml.h" 22 23 #include <string.h> 24 #ifdef HAVE_STDLIB_H 25 #include <stdlib.h> 26 #endif 27 #ifdef HAVE_TIME_H 28 #include <time.h> 29 #endif 30 31 /* 32 * Following http://www.ocert.org/advisories/ocert-2011-003.html 33 * it seems that having hash randomization might be a good idea 34 * when using XML with untrusted data 35 */ 36 #if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME) 37 #define HASH_RANDOMIZATION 38 #endif 39 40 #include <libxml/parser.h> 41 #include <libxml/hash.h> 42 #include <libxml/xmlmemory.h> 43 #include <libxml/xmlerror.h> 44 #include <libxml/globals.h> 45 46 #define MAX_HASH_LEN 8 47 48 /* #define DEBUG_GROW */ 49 50 #ifdef HASH_RANDOMIZATION 51 static int hash_initialized = 0; 52 #endif 53 54 /* 55 * A single entry in the hash table 56 */ 57 typedef struct _xmlHashEntry xmlHashEntry; 58 typedef xmlHashEntry *xmlHashEntryPtr; 59 struct _xmlHashEntry { 60 struct _xmlHashEntry *next; 61 xmlChar *name; 62 xmlChar *name2; 63 xmlChar *name3; 64 void *payload; 65 int valid; 66 }; 67 68 /* 69 * The entire hash table 70 */ 71 struct _xmlHashTable { 72 struct _xmlHashEntry *table; 73 int size; 74 int nbElems; 75 xmlDictPtr dict; 76 #ifdef HASH_RANDOMIZATION 77 int random_seed; 78 #endif 79 }; 80 81 /* 82 * xmlHashComputeKey: 83 * Calculate the hash key 84 */ 85 static unsigned long 86 xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name, 87 const xmlChar *name2, const xmlChar *name3) { 88 unsigned long value = 0L; 89 char ch; 90 91 #ifdef HASH_RANDOMIZATION 92 value = table->random_seed; 93 #endif 94 if (name != NULL) { 95 value += 30 * (*name); 96 while ((ch = *name++) != 0) { 97 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); 98 } 99 } 100 if (name2 != NULL) { 101 while ((ch = *name2++) != 0) { 102 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); 103 } 104 } 105 if (name3 != NULL) { 106 while ((ch = *name3++) != 0) { 107 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); 108 } 109 } 110 return (value % table->size); 111 } 112 113 static unsigned long 114 xmlHashComputeQKey(xmlHashTablePtr table, 115 const xmlChar *prefix, const xmlChar *name, 116 const xmlChar *prefix2, const xmlChar *name2, 117 const xmlChar *prefix3, const xmlChar *name3) { 118 unsigned long value = 0L; 119 char ch; 120 121 #ifdef HASH_RANDOMIZATION 122 value = table->random_seed; 123 #endif 124 if (prefix != NULL) 125 value += 30 * (*prefix); 126 else 127 value += 30 * (*name); 128 129 if (prefix != NULL) { 130 while ((ch = *prefix++) != 0) { 131 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); 132 } 133 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':'); 134 } 135 if (name != NULL) { 136 while ((ch = *name++) != 0) { 137 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); 138 } 139 } 140 if (prefix2 != NULL) { 141 while ((ch = *prefix2++) != 0) { 142 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); 143 } 144 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':'); 145 } 146 if (name2 != NULL) { 147 while ((ch = *name2++) != 0) { 148 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); 149 } 150 } 151 if (prefix3 != NULL) { 152 while ((ch = *prefix3++) != 0) { 153 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); 154 } 155 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':'); 156 } 157 if (name3 != NULL) { 158 while ((ch = *name3++) != 0) { 159 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); 160 } 161 } 162 return (value % table->size); 163 } 164 165 /** 166 * xmlHashCreate: 167 * @size: the size of the hash table 168 * 169 * Create a new xmlHashTablePtr. 170 * 171 * Returns the newly created object, or NULL if an error occured. 172 */ 173 xmlHashTablePtr 174 xmlHashCreate(int size) { 175 xmlHashTablePtr table; 176 177 if (size <= 0) 178 size = 256; 179 180 table = xmlMalloc(sizeof(xmlHashTable)); 181 if (table) { 182 table->dict = NULL; 183 table->size = size; 184 table->nbElems = 0; 185 table->table = xmlMalloc(size * sizeof(xmlHashEntry)); 186 if (table->table) { 187 memset(table->table, 0, size * sizeof(xmlHashEntry)); 188 #ifdef HASH_RANDOMIZATION 189 if (!hash_initialized) { 190 srand(time(NULL)); 191 hash_initialized = 1; 192 } 193 table->random_seed = rand(); 194 #endif 195 return(table); 196 } 197 xmlFree(table); 198 } 199 return(NULL); 200 } 201 202 /** 203 * xmlHashCreateDict: 204 * @size: the size of the hash table 205 * @dict: a dictionary to use for the hash 206 * 207 * Create a new xmlHashTablePtr which will use @dict as the internal dictionary 208 * 209 * Returns the newly created object, or NULL if an error occured. 210 */ 211 xmlHashTablePtr 212 xmlHashCreateDict(int size, xmlDictPtr dict) { 213 xmlHashTablePtr table; 214 215 table = xmlHashCreate(size); 216 if (table != NULL) { 217 table->dict = dict; 218 xmlDictReference(dict); 219 } 220 return(table); 221 } 222 223 /** 224 * xmlHashGrow: 225 * @table: the hash table 226 * @size: the new size of the hash table 227 * 228 * resize the hash table 229 * 230 * Returns 0 in case of success, -1 in case of failure 231 */ 232 static int 233 xmlHashGrow(xmlHashTablePtr table, int size) { 234 unsigned long key; 235 int oldsize, i; 236 xmlHashEntryPtr iter, next; 237 struct _xmlHashEntry *oldtable; 238 #ifdef DEBUG_GROW 239 unsigned long nbElem = 0; 240 #endif 241 242 if (table == NULL) 243 return(-1); 244 if (size < 8) 245 return(-1); 246 if (size > 8 * 2048) 247 return(-1); 248 249 oldsize = table->size; 250 oldtable = table->table; 251 if (oldtable == NULL) 252 return(-1); 253 254 table->table = xmlMalloc(size * sizeof(xmlHashEntry)); 255 if (table->table == NULL) { 256 table->table = oldtable; 257 return(-1); 258 } 259 memset(table->table, 0, size * sizeof(xmlHashEntry)); 260 table->size = size; 261 262 /* If the two loops are merged, there would be situations where 263 a new entry needs to allocated and data copied into it from 264 the main table. So instead, we run through the array twice, first 265 copying all the elements in the main array (where we can't get 266 conflicts) and then the rest, so we only free (and don't allocate) 267 */ 268 for (i = 0; i < oldsize; i++) { 269 if (oldtable[i].valid == 0) 270 continue; 271 key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2, 272 oldtable[i].name3); 273 memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry)); 274 table->table[key].next = NULL; 275 } 276 277 for (i = 0; i < oldsize; i++) { 278 iter = oldtable[i].next; 279 while (iter) { 280 next = iter->next; 281 282 /* 283 * put back the entry in the new table 284 */ 285 286 key = xmlHashComputeKey(table, iter->name, iter->name2, 287 iter->name3); 288 if (table->table[key].valid == 0) { 289 memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry)); 290 table->table[key].next = NULL; 291 xmlFree(iter); 292 } else { 293 iter->next = table->table[key].next; 294 table->table[key].next = iter; 295 } 296 297 #ifdef DEBUG_GROW 298 nbElem++; 299 #endif 300 301 iter = next; 302 } 303 } 304 305 xmlFree(oldtable); 306 307 #ifdef DEBUG_GROW 308 xmlGenericError(xmlGenericErrorContext, 309 "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem); 310 #endif 311 312 return(0); 313 } 314 315 /** 316 * xmlHashFree: 317 * @table: the hash table 318 * @f: the deallocator function for items in the hash 319 * 320 * Free the hash @table and its contents. The userdata is 321 * deallocated with @f if provided. 322 */ 323 void 324 xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) { 325 int i; 326 xmlHashEntryPtr iter; 327 xmlHashEntryPtr next; 328 int inside_table = 0; 329 int nbElems; 330 331 if (table == NULL) 332 return; 333 if (table->table) { 334 nbElems = table->nbElems; 335 for(i = 0; (i < table->size) && (nbElems > 0); i++) { 336 iter = &(table->table[i]); 337 if (iter->valid == 0) 338 continue; 339 inside_table = 1; 340 while (iter) { 341 next = iter->next; 342 if ((f != NULL) && (iter->payload != NULL)) 343 f(iter->payload, iter->name); 344 if (table->dict == NULL) { 345 if (iter->name) 346 xmlFree(iter->name); 347 if (iter->name2) 348 xmlFree(iter->name2); 349 if (iter->name3) 350 xmlFree(iter->name3); 351 } 352 iter->payload = NULL; 353 if (!inside_table) 354 xmlFree(iter); 355 nbElems--; 356 inside_table = 0; 357 iter = next; 358 } 359 } 360 xmlFree(table->table); 361 } 362 if (table->dict) 363 xmlDictFree(table->dict); 364 xmlFree(table); 365 } 366 367 /** 368 * xmlHashAddEntry: 369 * @table: the hash table 370 * @name: the name of the userdata 371 * @userdata: a pointer to the userdata 372 * 373 * Add the @userdata to the hash @table. This can later be retrieved 374 * by using the @name. Duplicate names generate errors. 375 * 376 * Returns 0 the addition succeeded and -1 in case of error. 377 */ 378 int 379 xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) { 380 return(xmlHashAddEntry3(table, name, NULL, NULL, userdata)); 381 } 382 383 /** 384 * xmlHashAddEntry2: 385 * @table: the hash table 386 * @name: the name of the userdata 387 * @name2: a second name of the userdata 388 * @userdata: a pointer to the userdata 389 * 390 * Add the @userdata to the hash @table. This can later be retrieved 391 * by using the (@name, @name2) tuple. Duplicate tuples generate errors. 392 * 393 * Returns 0 the addition succeeded and -1 in case of error. 394 */ 395 int 396 xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name, 397 const xmlChar *name2, void *userdata) { 398 return(xmlHashAddEntry3(table, name, name2, NULL, userdata)); 399 } 400 401 /** 402 * xmlHashUpdateEntry: 403 * @table: the hash table 404 * @name: the name of the userdata 405 * @userdata: a pointer to the userdata 406 * @f: the deallocator function for replaced item (if any) 407 * 408 * Add the @userdata to the hash @table. This can later be retrieved 409 * by using the @name. Existing entry for this @name will be removed 410 * and freed with @f if found. 411 * 412 * Returns 0 the addition succeeded and -1 in case of error. 413 */ 414 int 415 xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name, 416 void *userdata, xmlHashDeallocator f) { 417 return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f)); 418 } 419 420 /** 421 * xmlHashUpdateEntry2: 422 * @table: the hash table 423 * @name: the name of the userdata 424 * @name2: a second name of the userdata 425 * @userdata: a pointer to the userdata 426 * @f: the deallocator function for replaced item (if any) 427 * 428 * Add the @userdata to the hash @table. This can later be retrieved 429 * by using the (@name, @name2) tuple. Existing entry for this tuple will 430 * be removed and freed with @f if found. 431 * 432 * Returns 0 the addition succeeded and -1 in case of error. 433 */ 434 int 435 xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name, 436 const xmlChar *name2, void *userdata, 437 xmlHashDeallocator f) { 438 return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f)); 439 } 440 441 /** 442 * xmlHashLookup: 443 * @table: the hash table 444 * @name: the name of the userdata 445 * 446 * Find the userdata specified by the @name. 447 * 448 * Returns the pointer to the userdata 449 */ 450 void * 451 xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) { 452 return(xmlHashLookup3(table, name, NULL, NULL)); 453 } 454 455 /** 456 * xmlHashLookup2: 457 * @table: the hash table 458 * @name: the name of the userdata 459 * @name2: a second name of the userdata 460 * 461 * Find the userdata specified by the (@name, @name2) tuple. 462 * 463 * Returns the pointer to the userdata 464 */ 465 void * 466 xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name, 467 const xmlChar *name2) { 468 return(xmlHashLookup3(table, name, name2, NULL)); 469 } 470 471 /** 472 * xmlHashQLookup: 473 * @table: the hash table 474 * @prefix: the prefix of the userdata 475 * @name: the name of the userdata 476 * 477 * Find the userdata specified by the QName @prefix:@name/@name. 478 * 479 * Returns the pointer to the userdata 480 */ 481 void * 482 xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix, 483 const xmlChar *name) { 484 return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL)); 485 } 486 487 /** 488 * xmlHashQLookup2: 489 * @table: the hash table 490 * @prefix: the prefix of the userdata 491 * @name: the name of the userdata 492 * @prefix2: the second prefix of the userdata 493 * @name2: a second name of the userdata 494 * 495 * Find the userdata specified by the QNames tuple 496 * 497 * Returns the pointer to the userdata 498 */ 499 void * 500 xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix, 501 const xmlChar *name, const xmlChar *prefix2, 502 const xmlChar *name2) { 503 return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL)); 504 } 505 506 /** 507 * xmlHashAddEntry3: 508 * @table: the hash table 509 * @name: the name of the userdata 510 * @name2: a second name of the userdata 511 * @name3: a third name of the userdata 512 * @userdata: a pointer to the userdata 513 * 514 * Add the @userdata to the hash @table. This can later be retrieved 515 * by using the tuple (@name, @name2, @name3). Duplicate entries generate 516 * errors. 517 * 518 * Returns 0 the addition succeeded and -1 in case of error. 519 */ 520 int 521 xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name, 522 const xmlChar *name2, const xmlChar *name3, 523 void *userdata) { 524 unsigned long key, len = 0; 525 xmlHashEntryPtr entry; 526 xmlHashEntryPtr insert; 527 528 if ((table == NULL) || (name == NULL)) 529 return(-1); 530 531 /* 532 * If using a dict internalize if needed 533 */ 534 if (table->dict) { 535 if (!xmlDictOwns(table->dict, name)) { 536 name = xmlDictLookup(table->dict, name, -1); 537 if (name == NULL) 538 return(-1); 539 } 540 if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) { 541 name2 = xmlDictLookup(table->dict, name2, -1); 542 if (name2 == NULL) 543 return(-1); 544 } 545 if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) { 546 name3 = xmlDictLookup(table->dict, name3, -1); 547 if (name3 == NULL) 548 return(-1); 549 } 550 } 551 552 /* 553 * Check for duplicate and insertion location. 554 */ 555 key = xmlHashComputeKey(table, name, name2, name3); 556 if (table->table[key].valid == 0) { 557 insert = NULL; 558 } else { 559 if (table->dict) { 560 for (insert = &(table->table[key]); insert->next != NULL; 561 insert = insert->next) { 562 if ((insert->name == name) && 563 (insert->name2 == name2) && 564 (insert->name3 == name3)) 565 return(-1); 566 len++; 567 } 568 if ((insert->name == name) && 569 (insert->name2 == name2) && 570 (insert->name3 == name3)) 571 return(-1); 572 } else { 573 for (insert = &(table->table[key]); insert->next != NULL; 574 insert = insert->next) { 575 if ((xmlStrEqual(insert->name, name)) && 576 (xmlStrEqual(insert->name2, name2)) && 577 (xmlStrEqual(insert->name3, name3))) 578 return(-1); 579 len++; 580 } 581 if ((xmlStrEqual(insert->name, name)) && 582 (xmlStrEqual(insert->name2, name2)) && 583 (xmlStrEqual(insert->name3, name3))) 584 return(-1); 585 } 586 } 587 588 if (insert == NULL) { 589 entry = &(table->table[key]); 590 } else { 591 entry = xmlMalloc(sizeof(xmlHashEntry)); 592 if (entry == NULL) 593 return(-1); 594 } 595 596 if (table->dict != NULL) { 597 entry->name = (xmlChar *) name; 598 entry->name2 = (xmlChar *) name2; 599 entry->name3 = (xmlChar *) name3; 600 } else { 601 entry->name = xmlStrdup(name); 602 entry->name2 = xmlStrdup(name2); 603 entry->name3 = xmlStrdup(name3); 604 } 605 entry->payload = userdata; 606 entry->next = NULL; 607 entry->valid = 1; 608 609 610 if (insert != NULL) 611 insert->next = entry; 612 613 table->nbElems++; 614 615 if (len > MAX_HASH_LEN) 616 xmlHashGrow(table, MAX_HASH_LEN * table->size); 617 618 return(0); 619 } 620 621 /** 622 * xmlHashUpdateEntry3: 623 * @table: the hash table 624 * @name: the name of the userdata 625 * @name2: a second name of the userdata 626 * @name3: a third name of the userdata 627 * @userdata: a pointer to the userdata 628 * @f: the deallocator function for replaced item (if any) 629 * 630 * Add the @userdata to the hash @table. This can later be retrieved 631 * by using the tuple (@name, @name2, @name3). Existing entry for this tuple 632 * will be removed and freed with @f if found. 633 * 634 * Returns 0 the addition succeeded and -1 in case of error. 635 */ 636 int 637 xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name, 638 const xmlChar *name2, const xmlChar *name3, 639 void *userdata, xmlHashDeallocator f) { 640 unsigned long key; 641 xmlHashEntryPtr entry; 642 xmlHashEntryPtr insert; 643 644 if ((table == NULL) || name == NULL) 645 return(-1); 646 647 /* 648 * If using a dict internalize if needed 649 */ 650 if (table->dict) { 651 if (!xmlDictOwns(table->dict, name)) { 652 name = xmlDictLookup(table->dict, name, -1); 653 if (name == NULL) 654 return(-1); 655 } 656 if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) { 657 name2 = xmlDictLookup(table->dict, name2, -1); 658 if (name2 == NULL) 659 return(-1); 660 } 661 if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) { 662 name3 = xmlDictLookup(table->dict, name3, -1); 663 if (name3 == NULL) 664 return(-1); 665 } 666 } 667 668 /* 669 * Check for duplicate and insertion location. 670 */ 671 key = xmlHashComputeKey(table, name, name2, name3); 672 if (table->table[key].valid == 0) { 673 insert = NULL; 674 } else { 675 if (table ->dict) { 676 for (insert = &(table->table[key]); insert->next != NULL; 677 insert = insert->next) { 678 if ((insert->name == name) && 679 (insert->name2 == name2) && 680 (insert->name3 == name3)) { 681 if (f) 682 f(insert->payload, insert->name); 683 insert->payload = userdata; 684 return(0); 685 } 686 } 687 if ((insert->name == name) && 688 (insert->name2 == name2) && 689 (insert->name3 == name3)) { 690 if (f) 691 f(insert->payload, insert->name); 692 insert->payload = userdata; 693 return(0); 694 } 695 } else { 696 for (insert = &(table->table[key]); insert->next != NULL; 697 insert = insert->next) { 698 if ((xmlStrEqual(insert->name, name)) && 699 (xmlStrEqual(insert->name2, name2)) && 700 (xmlStrEqual(insert->name3, name3))) { 701 if (f) 702 f(insert->payload, insert->name); 703 insert->payload = userdata; 704 return(0); 705 } 706 } 707 if ((xmlStrEqual(insert->name, name)) && 708 (xmlStrEqual(insert->name2, name2)) && 709 (xmlStrEqual(insert->name3, name3))) { 710 if (f) 711 f(insert->payload, insert->name); 712 insert->payload = userdata; 713 return(0); 714 } 715 } 716 } 717 718 if (insert == NULL) { 719 entry = &(table->table[key]); 720 } else { 721 entry = xmlMalloc(sizeof(xmlHashEntry)); 722 if (entry == NULL) 723 return(-1); 724 } 725 726 if (table->dict != NULL) { 727 entry->name = (xmlChar *) name; 728 entry->name2 = (xmlChar *) name2; 729 entry->name3 = (xmlChar *) name3; 730 } else { 731 entry->name = xmlStrdup(name); 732 entry->name2 = xmlStrdup(name2); 733 entry->name3 = xmlStrdup(name3); 734 } 735 entry->payload = userdata; 736 entry->next = NULL; 737 entry->valid = 1; 738 table->nbElems++; 739 740 741 if (insert != NULL) { 742 insert->next = entry; 743 } 744 return(0); 745 } 746 747 /** 748 * xmlHashLookup3: 749 * @table: the hash table 750 * @name: the name of the userdata 751 * @name2: a second name of the userdata 752 * @name3: a third name of the userdata 753 * 754 * Find the userdata specified by the (@name, @name2, @name3) tuple. 755 * 756 * Returns the a pointer to the userdata 757 */ 758 void * 759 xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name, 760 const xmlChar *name2, const xmlChar *name3) { 761 unsigned long key; 762 xmlHashEntryPtr entry; 763 764 if (table == NULL) 765 return(NULL); 766 if (name == NULL) 767 return(NULL); 768 key = xmlHashComputeKey(table, name, name2, name3); 769 if (table->table[key].valid == 0) 770 return(NULL); 771 if (table->dict) { 772 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { 773 if ((entry->name == name) && 774 (entry->name2 == name2) && 775 (entry->name3 == name3)) 776 return(entry->payload); 777 } 778 } 779 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { 780 if ((xmlStrEqual(entry->name, name)) && 781 (xmlStrEqual(entry->name2, name2)) && 782 (xmlStrEqual(entry->name3, name3))) 783 return(entry->payload); 784 } 785 return(NULL); 786 } 787 788 /** 789 * xmlHashQLookup3: 790 * @table: the hash table 791 * @prefix: the prefix of the userdata 792 * @name: the name of the userdata 793 * @prefix2: the second prefix of the userdata 794 * @name2: a second name of the userdata 795 * @prefix3: the third prefix of the userdata 796 * @name3: a third name of the userdata 797 * 798 * Find the userdata specified by the (@name, @name2, @name3) tuple. 799 * 800 * Returns the a pointer to the userdata 801 */ 802 void * 803 xmlHashQLookup3(xmlHashTablePtr table, 804 const xmlChar *prefix, const xmlChar *name, 805 const xmlChar *prefix2, const xmlChar *name2, 806 const xmlChar *prefix3, const xmlChar *name3) { 807 unsigned long key; 808 xmlHashEntryPtr entry; 809 810 if (table == NULL) 811 return(NULL); 812 if (name == NULL) 813 return(NULL); 814 key = xmlHashComputeQKey(table, prefix, name, prefix2, 815 name2, prefix3, name3); 816 if (table->table[key].valid == 0) 817 return(NULL); 818 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { 819 if ((xmlStrQEqual(prefix, name, entry->name)) && 820 (xmlStrQEqual(prefix2, name2, entry->name2)) && 821 (xmlStrQEqual(prefix3, name3, entry->name3))) 822 return(entry->payload); 823 } 824 return(NULL); 825 } 826 827 typedef struct { 828 xmlHashScanner hashscanner; 829 void *data; 830 } stubData; 831 832 static void 833 stubHashScannerFull (void *payload, void *data, const xmlChar *name, 834 const xmlChar *name2 ATTRIBUTE_UNUSED, 835 const xmlChar *name3 ATTRIBUTE_UNUSED) { 836 stubData *stubdata = (stubData *) data; 837 stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name); 838 } 839 840 /** 841 * xmlHashScan: 842 * @table: the hash table 843 * @f: the scanner function for items in the hash 844 * @data: extra data passed to f 845 * 846 * Scan the hash @table and applied @f to each value. 847 */ 848 void 849 xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) { 850 stubData stubdata; 851 stubdata.data = data; 852 stubdata.hashscanner = f; 853 xmlHashScanFull (table, stubHashScannerFull, &stubdata); 854 } 855 856 /** 857 * xmlHashScanFull: 858 * @table: the hash table 859 * @f: the scanner function for items in the hash 860 * @data: extra data passed to f 861 * 862 * Scan the hash @table and applied @f to each value. 863 */ 864 void 865 xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) { 866 int i, nb; 867 xmlHashEntryPtr iter; 868 xmlHashEntryPtr next; 869 870 if (table == NULL) 871 return; 872 if (f == NULL) 873 return; 874 875 if (table->table) { 876 for(i = 0; i < table->size; i++) { 877 if (table->table[i].valid == 0) 878 continue; 879 iter = &(table->table[i]); 880 while (iter) { 881 next = iter->next; 882 nb = table->nbElems; 883 if ((f != NULL) && (iter->payload != NULL)) 884 f(iter->payload, data, iter->name, 885 iter->name2, iter->name3); 886 if (nb != table->nbElems) { 887 /* table was modified by the callback, be careful */ 888 if (iter == &(table->table[i])) { 889 if (table->table[i].valid == 0) 890 iter = NULL; 891 if (table->table[i].next != next) 892 iter = &(table->table[i]); 893 } else 894 iter = next; 895 } else 896 iter = next; 897 } 898 } 899 } 900 } 901 902 /** 903 * xmlHashScan3: 904 * @table: the hash table 905 * @name: the name of the userdata or NULL 906 * @name2: a second name of the userdata or NULL 907 * @name3: a third name of the userdata or NULL 908 * @f: the scanner function for items in the hash 909 * @data: extra data passed to f 910 * 911 * Scan the hash @table and applied @f to each value matching 912 * (@name, @name2, @name3) tuple. If one of the names is null, 913 * the comparison is considered to match. 914 */ 915 void 916 xmlHashScan3(xmlHashTablePtr table, const xmlChar *name, 917 const xmlChar *name2, const xmlChar *name3, 918 xmlHashScanner f, void *data) { 919 xmlHashScanFull3 (table, name, name2, name3, 920 (xmlHashScannerFull) f, data); 921 } 922 923 /** 924 * xmlHashScanFull3: 925 * @table: the hash table 926 * @name: the name of the userdata or NULL 927 * @name2: a second name of the userdata or NULL 928 * @name3: a third name of the userdata or NULL 929 * @f: the scanner function for items in the hash 930 * @data: extra data passed to f 931 * 932 * Scan the hash @table and applied @f to each value matching 933 * (@name, @name2, @name3) tuple. If one of the names is null, 934 * the comparison is considered to match. 935 */ 936 void 937 xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name, 938 const xmlChar *name2, const xmlChar *name3, 939 xmlHashScannerFull f, void *data) { 940 int i; 941 xmlHashEntryPtr iter; 942 xmlHashEntryPtr next; 943 944 if (table == NULL) 945 return; 946 if (f == NULL) 947 return; 948 949 if (table->table) { 950 for(i = 0; i < table->size; i++) { 951 if (table->table[i].valid == 0) 952 continue; 953 iter = &(table->table[i]); 954 while (iter) { 955 next = iter->next; 956 if (((name == NULL) || (xmlStrEqual(name, iter->name))) && 957 ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) && 958 ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) && 959 (iter->payload != NULL)) { 960 f(iter->payload, data, iter->name, 961 iter->name2, iter->name3); 962 } 963 iter = next; 964 } 965 } 966 } 967 } 968 969 /** 970 * xmlHashCopy: 971 * @table: the hash table 972 * @f: the copier function for items in the hash 973 * 974 * Scan the hash @table and applied @f to each value. 975 * 976 * Returns the new table or NULL in case of error. 977 */ 978 xmlHashTablePtr 979 xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) { 980 int i; 981 xmlHashEntryPtr iter; 982 xmlHashEntryPtr next; 983 xmlHashTablePtr ret; 984 985 if (table == NULL) 986 return(NULL); 987 if (f == NULL) 988 return(NULL); 989 990 ret = xmlHashCreate(table->size); 991 if (table->table) { 992 for(i = 0; i < table->size; i++) { 993 if (table->table[i].valid == 0) 994 continue; 995 iter = &(table->table[i]); 996 while (iter) { 997 next = iter->next; 998 xmlHashAddEntry3(ret, iter->name, iter->name2, 999 iter->name3, f(iter->payload, iter->name)); 1000 iter = next; 1001 } 1002 } 1003 } 1004 ret->nbElems = table->nbElems; 1005 return(ret); 1006 } 1007 1008 /** 1009 * xmlHashSize: 1010 * @table: the hash table 1011 * 1012 * Query the number of elements installed in the hash @table. 1013 * 1014 * Returns the number of elements in the hash table or 1015 * -1 in case of error 1016 */ 1017 int 1018 xmlHashSize(xmlHashTablePtr table) { 1019 if (table == NULL) 1020 return(-1); 1021 return(table->nbElems); 1022 } 1023 1024 /** 1025 * xmlHashRemoveEntry: 1026 * @table: the hash table 1027 * @name: the name of the userdata 1028 * @f: the deallocator function for removed item (if any) 1029 * 1030 * Find the userdata specified by the @name and remove 1031 * it from the hash @table. Existing userdata for this tuple will be removed 1032 * and freed with @f. 1033 * 1034 * Returns 0 if the removal succeeded and -1 in case of error or not found. 1035 */ 1036 int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name, 1037 xmlHashDeallocator f) { 1038 return(xmlHashRemoveEntry3(table, name, NULL, NULL, f)); 1039 } 1040 1041 /** 1042 * xmlHashRemoveEntry2: 1043 * @table: the hash table 1044 * @name: the name of the userdata 1045 * @name2: a second name of the userdata 1046 * @f: the deallocator function for removed item (if any) 1047 * 1048 * Find the userdata specified by the (@name, @name2) tuple and remove 1049 * it from the hash @table. Existing userdata for this tuple will be removed 1050 * and freed with @f. 1051 * 1052 * Returns 0 if the removal succeeded and -1 in case of error or not found. 1053 */ 1054 int 1055 xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name, 1056 const xmlChar *name2, xmlHashDeallocator f) { 1057 return(xmlHashRemoveEntry3(table, name, name2, NULL, f)); 1058 } 1059 1060 /** 1061 * xmlHashRemoveEntry3: 1062 * @table: the hash table 1063 * @name: the name of the userdata 1064 * @name2: a second name of the userdata 1065 * @name3: a third name of the userdata 1066 * @f: the deallocator function for removed item (if any) 1067 * 1068 * Find the userdata specified by the (@name, @name2, @name3) tuple and remove 1069 * it from the hash @table. Existing userdata for this tuple will be removed 1070 * and freed with @f. 1071 * 1072 * Returns 0 if the removal succeeded and -1 in case of error or not found. 1073 */ 1074 int 1075 xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name, 1076 const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) { 1077 unsigned long key; 1078 xmlHashEntryPtr entry; 1079 xmlHashEntryPtr prev = NULL; 1080 1081 if (table == NULL || name == NULL) 1082 return(-1); 1083 1084 key = xmlHashComputeKey(table, name, name2, name3); 1085 if (table->table[key].valid == 0) { 1086 return(-1); 1087 } else { 1088 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { 1089 if (xmlStrEqual(entry->name, name) && 1090 xmlStrEqual(entry->name2, name2) && 1091 xmlStrEqual(entry->name3, name3)) { 1092 if ((f != NULL) && (entry->payload != NULL)) 1093 f(entry->payload, entry->name); 1094 entry->payload = NULL; 1095 if (table->dict == NULL) { 1096 if(entry->name) 1097 xmlFree(entry->name); 1098 if(entry->name2) 1099 xmlFree(entry->name2); 1100 if(entry->name3) 1101 xmlFree(entry->name3); 1102 } 1103 if(prev) { 1104 prev->next = entry->next; 1105 xmlFree(entry); 1106 } else { 1107 if (entry->next == NULL) { 1108 entry->valid = 0; 1109 } else { 1110 entry = entry->next; 1111 memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry)); 1112 xmlFree(entry); 1113 } 1114 } 1115 table->nbElems--; 1116 return(0); 1117 } 1118 prev = entry; 1119 } 1120 return(-1); 1121 } 1122 } 1123 1124 #define bottom_hash 1125 #include "elfgcchack.h" 1126