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@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 */ 37typedef struct _xmlHashEntry xmlHashEntry; 38typedef xmlHashEntry *xmlHashEntryPtr; 39struct _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 */ 51struct _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 */ 62static unsigned long 63xmlHashComputeKey(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 87static unsigned long 88xmlHashComputeQKey(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 */ 144xmlHashTablePtr 145xmlHashCreate(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 */ 175xmlHashTablePtr 176xmlHashCreateDict(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 */ 196static int 197xmlHashGrow(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 */ 287void 288xmlHashFree(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 */ 343int 344xmlHashAddEntry(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 */ 360int 361xmlHashAddEntry2(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 */ 379int 380xmlHashUpdateEntry(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 */ 399int 400xmlHashUpdateEntry2(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 */ 415void * 416xmlHashLookup(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 */ 430void * 431xmlHashLookup2(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 */ 446void * 447xmlHashQLookup(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 */ 464void * 465xmlHashQLookup2(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 */ 485int 486xmlHashAddEntry3(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 */ 601int 602xmlHashUpdateEntry3(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 */ 723void * 724xmlHashLookup3(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 */ 767void * 768xmlHashQLookup3(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 792typedef struct { 793 xmlHashScanner hashscanner; 794 void *data; 795} stubData; 796 797static void 798stubHashScannerFull (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 */ 813void 814xmlHashScan(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 */ 829void 830xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) { 831 int i; 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 if ((f != NULL) && (iter->payload != NULL)) 848 f(iter->payload, data, iter->name, 849 iter->name2, iter->name3); 850 iter = next; 851 } 852 } 853 } 854} 855 856/** 857 * xmlHashScan3: 858 * @table: the hash table 859 * @name: the name of the userdata or NULL 860 * @name2: a second name of the userdata or NULL 861 * @name3: a third name of the userdata or NULL 862 * @f: the scanner function for items in the hash 863 * @data: extra data passed to f 864 * 865 * Scan the hash @table and applied @f to each value matching 866 * (@name, @name2, @name3) tuple. If one of the names is null, 867 * the comparison is considered to match. 868 */ 869void 870xmlHashScan3(xmlHashTablePtr table, const xmlChar *name, 871 const xmlChar *name2, const xmlChar *name3, 872 xmlHashScanner f, void *data) { 873 xmlHashScanFull3 (table, name, name2, name3, 874 (xmlHashScannerFull) f, data); 875} 876 877/** 878 * xmlHashScanFull3: 879 * @table: the hash table 880 * @name: the name of the userdata or NULL 881 * @name2: a second name of the userdata or NULL 882 * @name3: a third name of the userdata or NULL 883 * @f: the scanner function for items in the hash 884 * @data: extra data passed to f 885 * 886 * Scan the hash @table and applied @f to each value matching 887 * (@name, @name2, @name3) tuple. If one of the names is null, 888 * the comparison is considered to match. 889 */ 890void 891xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name, 892 const xmlChar *name2, const xmlChar *name3, 893 xmlHashScannerFull f, void *data) { 894 int i; 895 xmlHashEntryPtr iter; 896 xmlHashEntryPtr next; 897 898 if (table == NULL) 899 return; 900 if (f == NULL) 901 return; 902 903 if (table->table) { 904 for(i = 0; i < table->size; i++) { 905 if (table->table[i].valid == 0) 906 continue; 907 iter = &(table->table[i]); 908 while (iter) { 909 next = iter->next; 910 if (((name == NULL) || (xmlStrEqual(name, iter->name))) && 911 ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) && 912 ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) && 913 (iter->payload != NULL)) { 914 f(iter->payload, data, iter->name, 915 iter->name2, iter->name3); 916 } 917 iter = next; 918 } 919 } 920 } 921} 922 923/** 924 * xmlHashCopy: 925 * @table: the hash table 926 * @f: the copier function for items in the hash 927 * 928 * Scan the hash @table and applied @f to each value. 929 * 930 * Returns the new table or NULL in case of error. 931 */ 932xmlHashTablePtr 933xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) { 934 int i; 935 xmlHashEntryPtr iter; 936 xmlHashEntryPtr next; 937 xmlHashTablePtr ret; 938 939 if (table == NULL) 940 return(NULL); 941 if (f == NULL) 942 return(NULL); 943 944 ret = xmlHashCreate(table->size); 945 if (table->table) { 946 for(i = 0; i < table->size; i++) { 947 if (table->table[i].valid == 0) 948 continue; 949 iter = &(table->table[i]); 950 while (iter) { 951 next = iter->next; 952 xmlHashAddEntry3(ret, iter->name, iter->name2, 953 iter->name3, f(iter->payload, iter->name)); 954 iter = next; 955 } 956 } 957 } 958 ret->nbElems = table->nbElems; 959 return(ret); 960} 961 962/** 963 * xmlHashSize: 964 * @table: the hash table 965 * 966 * Query the number of elements installed in the hash @table. 967 * 968 * Returns the number of elements in the hash table or 969 * -1 in case of error 970 */ 971int 972xmlHashSize(xmlHashTablePtr table) { 973 if (table == NULL) 974 return(-1); 975 return(table->nbElems); 976} 977 978/** 979 * xmlHashRemoveEntry: 980 * @table: the hash table 981 * @name: the name of the userdata 982 * @f: the deallocator function for removed item (if any) 983 * 984 * Find the userdata specified by the @name and remove 985 * it from the hash @table. Existing userdata for this tuple will be removed 986 * and freed with @f. 987 * 988 * Returns 0 if the removal succeeded and -1 in case of error or not found. 989 */ 990int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name, 991 xmlHashDeallocator f) { 992 return(xmlHashRemoveEntry3(table, name, NULL, NULL, f)); 993} 994 995/** 996 * xmlHashRemoveEntry2: 997 * @table: the hash table 998 * @name: the name of the userdata 999 * @name2: a second name of the userdata 1000 * @f: the deallocator function for removed item (if any) 1001 * 1002 * Find the userdata specified by the (@name, @name2) tuple and remove 1003 * it from the hash @table. Existing userdata for this tuple will be removed 1004 * and freed with @f. 1005 * 1006 * Returns 0 if the removal succeeded and -1 in case of error or not found. 1007 */ 1008int 1009xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name, 1010 const xmlChar *name2, xmlHashDeallocator f) { 1011 return(xmlHashRemoveEntry3(table, name, name2, NULL, f)); 1012} 1013 1014/** 1015 * xmlHashRemoveEntry3: 1016 * @table: the hash table 1017 * @name: the name of the userdata 1018 * @name2: a second name of the userdata 1019 * @name3: a third name of the userdata 1020 * @f: the deallocator function for removed item (if any) 1021 * 1022 * Find the userdata specified by the (@name, @name2, @name3) tuple and remove 1023 * it from the hash @table. Existing userdata for this tuple will be removed 1024 * and freed with @f. 1025 * 1026 * Returns 0 if the removal succeeded and -1 in case of error or not found. 1027 */ 1028int 1029xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name, 1030 const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) { 1031 unsigned long key; 1032 xmlHashEntryPtr entry; 1033 xmlHashEntryPtr prev = NULL; 1034 1035 if (table == NULL || name == NULL) 1036 return(-1); 1037 1038 key = xmlHashComputeKey(table, name, name2, name3); 1039 if (table->table[key].valid == 0) { 1040 return(-1); 1041 } else { 1042 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { 1043 if (xmlStrEqual(entry->name, name) && 1044 xmlStrEqual(entry->name2, name2) && 1045 xmlStrEqual(entry->name3, name3)) { 1046 if ((f != NULL) && (entry->payload != NULL)) 1047 f(entry->payload, entry->name); 1048 entry->payload = NULL; 1049 if (table->dict == NULL) { 1050 if(entry->name) 1051 xmlFree(entry->name); 1052 if(entry->name2) 1053 xmlFree(entry->name2); 1054 if(entry->name3) 1055 xmlFree(entry->name3); 1056 } 1057 if(prev) { 1058 prev->next = entry->next; 1059 xmlFree(entry); 1060 } else { 1061 if (entry->next == NULL) { 1062 entry->valid = 0; 1063 } else { 1064 entry = entry->next; 1065 memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry)); 1066 xmlFree(entry); 1067 } 1068 } 1069 table->nbElems--; 1070 return(0); 1071 } 1072 prev = entry; 1073 } 1074 return(-1); 1075 } 1076} 1077 1078#define bottom_hash 1079#include "elfgcchack.h" 1080