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 } 324 xmlFree(table->table); 325 } 326 if (table->dict) 327 xmlDictFree(table->dict); 328 xmlFree(table); 329 } 330 331 /** 332 * xmlHashAddEntry: 333 * @table: the hash table 334 * @name: the name of the userdata 335 * @userdata: a pointer to the userdata 336 * 337 * Add the @userdata to the hash @table. This can later be retrieved 338 * by using the @name. Duplicate names generate errors. 339 * 340 * Returns 0 the addition succeeded and -1 in case of error. 341 */ 342 int 343 xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) { 344 return(xmlHashAddEntry3(table, name, NULL, NULL, userdata)); 345 } 346 347 /** 348 * xmlHashAddEntry2: 349 * @table: the hash table 350 * @name: the name of the userdata 351 * @name2: a second name of the userdata 352 * @userdata: a pointer to the userdata 353 * 354 * Add the @userdata to the hash @table. This can later be retrieved 355 * by using the (@name, @name2) tuple. Duplicate tuples generate errors. 356 * 357 * Returns 0 the addition succeeded and -1 in case of error. 358 */ 359 int 360 xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name, 361 const xmlChar *name2, void *userdata) { 362 return(xmlHashAddEntry3(table, name, name2, NULL, userdata)); 363 } 364 365 /** 366 * xmlHashUpdateEntry: 367 * @table: the hash table 368 * @name: the name of the userdata 369 * @userdata: a pointer to the userdata 370 * @f: the deallocator function for replaced item (if any) 371 * 372 * Add the @userdata to the hash @table. This can later be retrieved 373 * by using the @name. Existing entry for this @name will be removed 374 * and freed with @f if found. 375 * 376 * Returns 0 the addition succeeded and -1 in case of error. 377 */ 378 int 379 xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name, 380 void *userdata, xmlHashDeallocator f) { 381 return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f)); 382 } 383 384 /** 385 * xmlHashUpdateEntry2: 386 * @table: the hash table 387 * @name: the name of the userdata 388 * @name2: a second name of the userdata 389 * @userdata: a pointer to the userdata 390 * @f: the deallocator function for replaced item (if any) 391 * 392 * Add the @userdata to the hash @table. This can later be retrieved 393 * by using the (@name, @name2) tuple. Existing entry for this tuple will 394 * be removed and freed with @f if found. 395 * 396 * Returns 0 the addition succeeded and -1 in case of error. 397 */ 398 int 399 xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name, 400 const xmlChar *name2, void *userdata, 401 xmlHashDeallocator f) { 402 return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f)); 403 } 404 405 /** 406 * xmlHashLookup: 407 * @table: the hash table 408 * @name: the name of the userdata 409 * 410 * Find the userdata specified by the @name. 411 * 412 * Returns the pointer to the userdata 413 */ 414 void * 415 xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) { 416 return(xmlHashLookup3(table, name, NULL, NULL)); 417 } 418 419 /** 420 * xmlHashLookup2: 421 * @table: the hash table 422 * @name: the name of the userdata 423 * @name2: a second name of the userdata 424 * 425 * Find the userdata specified by the (@name, @name2) tuple. 426 * 427 * Returns the pointer to the userdata 428 */ 429 void * 430 xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name, 431 const xmlChar *name2) { 432 return(xmlHashLookup3(table, name, name2, NULL)); 433 } 434 435 /** 436 * xmlHashQLookup: 437 * @table: the hash table 438 * @prefix: the prefix of the userdata 439 * @name: the name of the userdata 440 * 441 * Find the userdata specified by the QName @prefix:@name/@name. 442 * 443 * Returns the pointer to the userdata 444 */ 445 void * 446 xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix, 447 const xmlChar *name) { 448 return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL)); 449 } 450 451 /** 452 * xmlHashQLookup2: 453 * @table: the hash table 454 * @prefix: the prefix of the userdata 455 * @name: the name of the userdata 456 * @prefix2: the second prefix of the userdata 457 * @name2: a second name of the userdata 458 * 459 * Find the userdata specified by the QNames tuple 460 * 461 * Returns the pointer to the userdata 462 */ 463 void * 464 xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix, 465 const xmlChar *name, const xmlChar *prefix2, 466 const xmlChar *name2) { 467 return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL)); 468 } 469 470 /** 471 * xmlHashAddEntry3: 472 * @table: the hash table 473 * @name: the name of the userdata 474 * @name2: a second name of the userdata 475 * @name3: a third name of the userdata 476 * @userdata: a pointer to the userdata 477 * 478 * Add the @userdata to the hash @table. This can later be retrieved 479 * by using the tuple (@name, @name2, @name3). Duplicate entries generate 480 * errors. 481 * 482 * Returns 0 the addition succeeded and -1 in case of error. 483 */ 484 int 485 xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name, 486 const xmlChar *name2, const xmlChar *name3, 487 void *userdata) { 488 unsigned long key, len = 0; 489 xmlHashEntryPtr entry; 490 xmlHashEntryPtr insert; 491 492 if ((table == NULL) || (name == NULL)) 493 return(-1); 494 495 /* 496 * If using a dict internalize if needed 497 */ 498 if (table->dict) { 499 if (!xmlDictOwns(table->dict, name)) { 500 name = xmlDictLookup(table->dict, name, -1); 501 if (name == NULL) 502 return(-1); 503 } 504 if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) { 505 name2 = xmlDictLookup(table->dict, name2, -1); 506 if (name2 == NULL) 507 return(-1); 508 } 509 if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) { 510 name3 = xmlDictLookup(table->dict, name3, -1); 511 if (name3 == NULL) 512 return(-1); 513 } 514 } 515 516 /* 517 * Check for duplicate and insertion location. 518 */ 519 key = xmlHashComputeKey(table, name, name2, name3); 520 if (table->table[key].valid == 0) { 521 insert = NULL; 522 } else { 523 if (table->dict) { 524 for (insert = &(table->table[key]); insert->next != NULL; 525 insert = insert->next) { 526 if ((insert->name == name) && 527 (insert->name2 == name2) && 528 (insert->name3 == name3)) 529 return(-1); 530 len++; 531 } 532 if ((insert->name == name) && 533 (insert->name2 == name2) && 534 (insert->name3 == name3)) 535 return(-1); 536 } else { 537 for (insert = &(table->table[key]); insert->next != NULL; 538 insert = insert->next) { 539 if ((xmlStrEqual(insert->name, name)) && 540 (xmlStrEqual(insert->name2, name2)) && 541 (xmlStrEqual(insert->name3, name3))) 542 return(-1); 543 len++; 544 } 545 if ((xmlStrEqual(insert->name, name)) && 546 (xmlStrEqual(insert->name2, name2)) && 547 (xmlStrEqual(insert->name3, name3))) 548 return(-1); 549 } 550 } 551 552 if (insert == NULL) { 553 entry = &(table->table[key]); 554 } else { 555 entry = xmlMalloc(sizeof(xmlHashEntry)); 556 if (entry == NULL) 557 return(-1); 558 } 559 560 if (table->dict != NULL) { 561 entry->name = (xmlChar *) name; 562 entry->name2 = (xmlChar *) name2; 563 entry->name3 = (xmlChar *) name3; 564 } else { 565 entry->name = xmlStrdup(name); 566 entry->name2 = xmlStrdup(name2); 567 entry->name3 = xmlStrdup(name3); 568 } 569 entry->payload = userdata; 570 entry->next = NULL; 571 entry->valid = 1; 572 573 574 if (insert != NULL) 575 insert->next = entry; 576 577 table->nbElems++; 578 579 if (len > MAX_HASH_LEN) 580 xmlHashGrow(table, MAX_HASH_LEN * table->size); 581 582 return(0); 583 } 584 585 /** 586 * xmlHashUpdateEntry3: 587 * @table: the hash table 588 * @name: the name of the userdata 589 * @name2: a second name of the userdata 590 * @name3: a third name of the userdata 591 * @userdata: a pointer to the userdata 592 * @f: the deallocator function for replaced item (if any) 593 * 594 * Add the @userdata to the hash @table. This can later be retrieved 595 * by using the tuple (@name, @name2, @name3). Existing entry for this tuple 596 * will be removed and freed with @f if found. 597 * 598 * Returns 0 the addition succeeded and -1 in case of error. 599 */ 600 int 601 xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name, 602 const xmlChar *name2, const xmlChar *name3, 603 void *userdata, xmlHashDeallocator f) { 604 unsigned long key; 605 xmlHashEntryPtr entry; 606 xmlHashEntryPtr insert; 607 608 if ((table == NULL) || name == NULL) 609 return(-1); 610 611 /* 612 * If using a dict internalize if needed 613 */ 614 if (table->dict) { 615 if (!xmlDictOwns(table->dict, name)) { 616 name = xmlDictLookup(table->dict, name, -1); 617 if (name == NULL) 618 return(-1); 619 } 620 if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) { 621 name2 = xmlDictLookup(table->dict, name2, -1); 622 if (name2 == NULL) 623 return(-1); 624 } 625 if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) { 626 name3 = xmlDictLookup(table->dict, name3, -1); 627 if (name3 == NULL) 628 return(-1); 629 } 630 } 631 632 /* 633 * Check for duplicate and insertion location. 634 */ 635 key = xmlHashComputeKey(table, name, name2, name3); 636 if (table->table[key].valid == 0) { 637 insert = NULL; 638 } else { 639 if (table ->dict) { 640 for (insert = &(table->table[key]); insert->next != NULL; 641 insert = insert->next) { 642 if ((insert->name == name) && 643 (insert->name2 == name2) && 644 (insert->name3 == name3)) { 645 if (f) 646 f(insert->payload, insert->name); 647 insert->payload = userdata; 648 return(0); 649 } 650 } 651 if ((insert->name == name) && 652 (insert->name2 == name2) && 653 (insert->name3 == name3)) { 654 if (f) 655 f(insert->payload, insert->name); 656 insert->payload = userdata; 657 return(0); 658 } 659 } else { 660 for (insert = &(table->table[key]); insert->next != NULL; 661 insert = insert->next) { 662 if ((xmlStrEqual(insert->name, name)) && 663 (xmlStrEqual(insert->name2, name2)) && 664 (xmlStrEqual(insert->name3, name3))) { 665 if (f) 666 f(insert->payload, insert->name); 667 insert->payload = userdata; 668 return(0); 669 } 670 } 671 if ((xmlStrEqual(insert->name, name)) && 672 (xmlStrEqual(insert->name2, name2)) && 673 (xmlStrEqual(insert->name3, name3))) { 674 if (f) 675 f(insert->payload, insert->name); 676 insert->payload = userdata; 677 return(0); 678 } 679 } 680 } 681 682 if (insert == NULL) { 683 entry = &(table->table[key]); 684 } else { 685 entry = xmlMalloc(sizeof(xmlHashEntry)); 686 if (entry == NULL) 687 return(-1); 688 } 689 690 if (table->dict != NULL) { 691 entry->name = (xmlChar *) name; 692 entry->name2 = (xmlChar *) name2; 693 entry->name3 = (xmlChar *) name3; 694 } else { 695 entry->name = xmlStrdup(name); 696 entry->name2 = xmlStrdup(name2); 697 entry->name3 = xmlStrdup(name3); 698 } 699 entry->payload = userdata; 700 entry->next = NULL; 701 entry->valid = 1; 702 table->nbElems++; 703 704 705 if (insert != NULL) { 706 insert->next = entry; 707 } 708 return(0); 709 } 710 711 /** 712 * xmlHashLookup3: 713 * @table: the hash table 714 * @name: the name of the userdata 715 * @name2: a second name of the userdata 716 * @name3: a third name of the userdata 717 * 718 * Find the userdata specified by the (@name, @name2, @name3) tuple. 719 * 720 * Returns the a pointer to the userdata 721 */ 722 void * 723 xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name, 724 const xmlChar *name2, const xmlChar *name3) { 725 unsigned long key; 726 xmlHashEntryPtr entry; 727 728 if (table == NULL) 729 return(NULL); 730 if (name == NULL) 731 return(NULL); 732 key = xmlHashComputeKey(table, name, name2, name3); 733 if (table->table[key].valid == 0) 734 return(NULL); 735 if (table->dict) { 736 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { 737 if ((entry->name == name) && 738 (entry->name2 == name2) && 739 (entry->name3 == name3)) 740 return(entry->payload); 741 } 742 } 743 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { 744 if ((xmlStrEqual(entry->name, name)) && 745 (xmlStrEqual(entry->name2, name2)) && 746 (xmlStrEqual(entry->name3, name3))) 747 return(entry->payload); 748 } 749 return(NULL); 750 } 751 752 /** 753 * xmlHashQLookup3: 754 * @table: the hash table 755 * @prefix: the prefix of the userdata 756 * @name: the name of the userdata 757 * @prefix2: the second prefix of the userdata 758 * @name2: a second name of the userdata 759 * @prefix3: the third prefix of the userdata 760 * @name3: a third name of the userdata 761 * 762 * Find the userdata specified by the (@name, @name2, @name3) tuple. 763 * 764 * Returns the a pointer to the userdata 765 */ 766 void * 767 xmlHashQLookup3(xmlHashTablePtr table, 768 const xmlChar *prefix, const xmlChar *name, 769 const xmlChar *prefix2, const xmlChar *name2, 770 const xmlChar *prefix3, const xmlChar *name3) { 771 unsigned long key; 772 xmlHashEntryPtr entry; 773 774 if (table == NULL) 775 return(NULL); 776 if (name == NULL) 777 return(NULL); 778 key = xmlHashComputeQKey(table, prefix, name, prefix2, 779 name2, prefix3, name3); 780 if (table->table[key].valid == 0) 781 return(NULL); 782 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { 783 if ((xmlStrQEqual(prefix, name, entry->name)) && 784 (xmlStrQEqual(prefix2, name2, entry->name2)) && 785 (xmlStrQEqual(prefix3, name3, entry->name3))) 786 return(entry->payload); 787 } 788 return(NULL); 789 } 790 791 typedef struct { 792 xmlHashScanner hashscanner; 793 void *data; 794 } stubData; 795 796 static void 797 stubHashScannerFull (void *payload, void *data, const xmlChar *name, 798 const xmlChar *name2 ATTRIBUTE_UNUSED, 799 const xmlChar *name3 ATTRIBUTE_UNUSED) { 800 stubData *stubdata = (stubData *) data; 801 stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name); 802 } 803 804 /** 805 * xmlHashScan: 806 * @table: the hash table 807 * @f: the scanner function for items in the hash 808 * @data: extra data passed to f 809 * 810 * Scan the hash @table and applied @f to each value. 811 */ 812 void 813 xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) { 814 stubData stubdata; 815 stubdata.data = data; 816 stubdata.hashscanner = f; 817 xmlHashScanFull (table, stubHashScannerFull, &stubdata); 818 } 819 820 /** 821 * xmlHashScanFull: 822 * @table: the hash table 823 * @f: the scanner function for items in the hash 824 * @data: extra data passed to f 825 * 826 * Scan the hash @table and applied @f to each value. 827 */ 828 void 829 xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) { 830 int i, nb; 831 xmlHashEntryPtr iter; 832 xmlHashEntryPtr next; 833 834 if (table == NULL) 835 return; 836 if (f == NULL) 837 return; 838 839 if (table->table) { 840 for(i = 0; i < table->size; i++) { 841 if (table->table[i].valid == 0) 842 continue; 843 iter = &(table->table[i]); 844 while (iter) { 845 next = iter->next; 846 nb = table->nbElems; 847 if ((f != NULL) && (iter->payload != NULL)) 848 f(iter->payload, data, iter->name, 849 iter->name2, iter->name3); 850 if (nb != table->nbElems) { 851 /* table was modified by the callback, be careful */ 852 if (iter == &(table->table[i])) { 853 if (table->table[i].valid == 0) 854 iter = NULL; 855 if (table->table[i].next != next) 856 iter = &(table->table[i]); 857 } else 858 iter = next; 859 } else 860 iter = next; 861 } 862 } 863 } 864 } 865 866 /** 867 * xmlHashScan3: 868 * @table: the hash table 869 * @name: the name of the userdata or NULL 870 * @name2: a second name of the userdata or NULL 871 * @name3: a third name of the userdata or NULL 872 * @f: the scanner function for items in the hash 873 * @data: extra data passed to f 874 * 875 * Scan the hash @table and applied @f to each value matching 876 * (@name, @name2, @name3) tuple. If one of the names is null, 877 * the comparison is considered to match. 878 */ 879 void 880 xmlHashScan3(xmlHashTablePtr table, const xmlChar *name, 881 const xmlChar *name2, const xmlChar *name3, 882 xmlHashScanner f, void *data) { 883 xmlHashScanFull3 (table, name, name2, name3, 884 (xmlHashScannerFull) f, data); 885 } 886 887 /** 888 * xmlHashScanFull3: 889 * @table: the hash table 890 * @name: the name of the userdata or NULL 891 * @name2: a second name of the userdata or NULL 892 * @name3: a third name of the userdata or NULL 893 * @f: the scanner function for items in the hash 894 * @data: extra data passed to f 895 * 896 * Scan the hash @table and applied @f to each value matching 897 * (@name, @name2, @name3) tuple. If one of the names is null, 898 * the comparison is considered to match. 899 */ 900 void 901 xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name, 902 const xmlChar *name2, const xmlChar *name3, 903 xmlHashScannerFull f, void *data) { 904 int i; 905 xmlHashEntryPtr iter; 906 xmlHashEntryPtr next; 907 908 if (table == NULL) 909 return; 910 if (f == NULL) 911 return; 912 913 if (table->table) { 914 for(i = 0; i < table->size; i++) { 915 if (table->table[i].valid == 0) 916 continue; 917 iter = &(table->table[i]); 918 while (iter) { 919 next = iter->next; 920 if (((name == NULL) || (xmlStrEqual(name, iter->name))) && 921 ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) && 922 ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) && 923 (iter->payload != NULL)) { 924 f(iter->payload, data, iter->name, 925 iter->name2, iter->name3); 926 } 927 iter = next; 928 } 929 } 930 } 931 } 932 933 /** 934 * xmlHashCopy: 935 * @table: the hash table 936 * @f: the copier function for items in the hash 937 * 938 * Scan the hash @table and applied @f to each value. 939 * 940 * Returns the new table or NULL in case of error. 941 */ 942 xmlHashTablePtr 943 xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) { 944 int i; 945 xmlHashEntryPtr iter; 946 xmlHashEntryPtr next; 947 xmlHashTablePtr ret; 948 949 if (table == NULL) 950 return(NULL); 951 if (f == NULL) 952 return(NULL); 953 954 ret = xmlHashCreate(table->size); 955 if (table->table) { 956 for(i = 0; i < table->size; i++) { 957 if (table->table[i].valid == 0) 958 continue; 959 iter = &(table->table[i]); 960 while (iter) { 961 next = iter->next; 962 xmlHashAddEntry3(ret, iter->name, iter->name2, 963 iter->name3, f(iter->payload, iter->name)); 964 iter = next; 965 } 966 } 967 } 968 ret->nbElems = table->nbElems; 969 return(ret); 970 } 971 972 /** 973 * xmlHashSize: 974 * @table: the hash table 975 * 976 * Query the number of elements installed in the hash @table. 977 * 978 * Returns the number of elements in the hash table or 979 * -1 in case of error 980 */ 981 int 982 xmlHashSize(xmlHashTablePtr table) { 983 if (table == NULL) 984 return(-1); 985 return(table->nbElems); 986 } 987 988 /** 989 * xmlHashRemoveEntry: 990 * @table: the hash table 991 * @name: the name of the userdata 992 * @f: the deallocator function for removed item (if any) 993 * 994 * Find the userdata specified by the @name and remove 995 * it from the hash @table. Existing userdata for this tuple will be removed 996 * and freed with @f. 997 * 998 * Returns 0 if the removal succeeded and -1 in case of error or not found. 999 */ 1000 int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name, 1001 xmlHashDeallocator f) { 1002 return(xmlHashRemoveEntry3(table, name, NULL, NULL, f)); 1003 } 1004 1005 /** 1006 * xmlHashRemoveEntry2: 1007 * @table: the hash table 1008 * @name: the name of the userdata 1009 * @name2: a second name of the userdata 1010 * @f: the deallocator function for removed item (if any) 1011 * 1012 * Find the userdata specified by the (@name, @name2) tuple and remove 1013 * it from the hash @table. Existing userdata for this tuple will be removed 1014 * and freed with @f. 1015 * 1016 * Returns 0 if the removal succeeded and -1 in case of error or not found. 1017 */ 1018 int 1019 xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name, 1020 const xmlChar *name2, xmlHashDeallocator f) { 1021 return(xmlHashRemoveEntry3(table, name, name2, NULL, f)); 1022 } 1023 1024 /** 1025 * xmlHashRemoveEntry3: 1026 * @table: the hash table 1027 * @name: the name of the userdata 1028 * @name2: a second name of the userdata 1029 * @name3: a third name of the userdata 1030 * @f: the deallocator function for removed item (if any) 1031 * 1032 * Find the userdata specified by the (@name, @name2, @name3) tuple and remove 1033 * it from the hash @table. Existing userdata for this tuple will be removed 1034 * and freed with @f. 1035 * 1036 * Returns 0 if the removal succeeded and -1 in case of error or not found. 1037 */ 1038 int 1039 xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name, 1040 const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) { 1041 unsigned long key; 1042 xmlHashEntryPtr entry; 1043 xmlHashEntryPtr prev = NULL; 1044 1045 if (table == NULL || name == NULL) 1046 return(-1); 1047 1048 key = xmlHashComputeKey(table, name, name2, name3); 1049 if (table->table[key].valid == 0) { 1050 return(-1); 1051 } else { 1052 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { 1053 if (xmlStrEqual(entry->name, name) && 1054 xmlStrEqual(entry->name2, name2) && 1055 xmlStrEqual(entry->name3, name3)) { 1056 if ((f != NULL) && (entry->payload != NULL)) 1057 f(entry->payload, entry->name); 1058 entry->payload = NULL; 1059 if (table->dict == NULL) { 1060 if(entry->name) 1061 xmlFree(entry->name); 1062 if(entry->name2) 1063 xmlFree(entry->name2); 1064 if(entry->name3) 1065 xmlFree(entry->name3); 1066 } 1067 if(prev) { 1068 prev->next = entry->next; 1069 xmlFree(entry); 1070 } else { 1071 if (entry->next == NULL) { 1072 entry->valid = 0; 1073 } else { 1074 entry = entry->next; 1075 memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry)); 1076 xmlFree(entry); 1077 } 1078 } 1079 table->nbElems--; 1080 return(0); 1081 } 1082 prev = entry; 1083 } 1084 return(-1); 1085 } 1086 } 1087 1088 #define bottom_hash 1089 #include "elfgcchack.h" 1090