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