libxml2/hash.c

   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/hash.h>
  25 #include <libxml/xmlmemory.h>
  26 #include <libxml/parser.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 };
  56
  57 /*
  58  * xmlHashComputeKey:
  59  * Calculate the hash key
  60  */
  61 static unsigned long
  62 xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
  63                   const xmlChar *name2, const xmlChar *name3) {
  64     unsigned long value = 0L;
  65     char ch;
  66
  67     if (name != NULL) {
  68         value += 30 * (*name);
  69         while ((ch = *name++) != 0) {
  70             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
  71         }
  72     }
  73     if (name2 != NULL) {
  74         while ((ch = *name2++) != 0) {
  75             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
  76         }
  77     }
  78     if (name3 != NULL) {
  79         while ((ch = *name3++) != 0) {
  80             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
  81         }
  82     }
  83     return (value % table->size);
  84 }
  85
  86 /**
  87  * xmlHashCreate:
  88  * @size: the size of the hash table
  89  *
  90  * Create a new xmlHashTablePtr.
  91  *
  92  * Returns the newly created object, or NULL if an error occured.
  93  */
  94 xmlHashTablePtr
  95 xmlHashCreate(int size) {
  96     xmlHashTablePtr table;
  97
  98     if (size <= 0)
  99         size = 256;
 100
 101     table = xmlMalloc(sizeof(xmlHashTable));
 102     if (table) {
 103         table->size = size;
 104         table->nbElems = 0;
 105         table->table = xmlMalloc(size * sizeof(xmlHashEntry));
 106         if (table->table) {
 107             memset(table->table, 0, size * sizeof(xmlHashEntry));
 108             return(table);
 109         }
 110         xmlFree(table);
 111     }
 112     return(NULL);
 113 }
 114
 115 /**
 116  * xmlHashGrow:
 117  * @table: the hash table
 118  * @size: the new size of the hash table
 119  *
 120  * resize the hash table
 121  *
 122  * Returns 0 in case of success, -1 in case of failure
 123  */
 124 static int
 125 xmlHashGrow(xmlHashTablePtr table, int size) {
 126     unsigned long key;
 127     int oldsize, i;
 128     xmlHashEntryPtr iter, next;
 129     struct _xmlHashEntry *oldtable;
 130 #ifdef DEBUG_GROW
 131     unsigned long nbElem = 0;
 132 #endif
 133
 134     if (table == NULL)
 135         return(-1);
 136     if (size < 8)
 137         return(-1);
 138     if (size > 8 * 2048)
 139         return(-1);
 140
 141     oldsize = table->size;
 142     oldtable = table->table;
 143     if (oldtable == NULL)
 144         return(-1);
 145
 146     table->table = xmlMalloc(size * sizeof(xmlHashEntry));
 147     if (table->table == NULL) {
 148         table->table = oldtable;
 149         return(-1);
 150     }
 151     memset(table->table, 0, size * sizeof(xmlHashEntry));
 152     table->size = size;
 153
 154     /*  If the two loops are merged, there would be situations where
 155         a new entry needs to allocated and data copied into it from
 156         the main table. So instead, we run through the array twice, first
 157         copying all the elements in the main array (where we can't get
 158         conflicts) and then the rest, so we only free (and don't allocate)
 159     */
 160     for (i = 0; i < oldsize; i++) {
 161         if (oldtable[i].valid == 0)
 162             continue;
 163         key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
 164                                 oldtable[i].name3);
 165         memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
 166         table->table[key].next = NULL;
 167     }
 168
 169     for (i = 0; i < oldsize; i++) {
 170         iter = oldtable[i].next;
 171         while (iter) {
 172             next = iter->next;
 173
 174             /*
 175              * put back the entry in the new table
 176              */
 177
 178             key = xmlHashComputeKey(table, iter->name, iter->name2,
 179                                     iter->name3);
 180             if (table->table[key].valid == 0) {
 181                 memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
 182                 table->table[key].next = NULL;
 183                 xmlFree(iter);
 184             } else {
 185                 iter->next = table->table[key].next;
 186                 table->table[key].next = iter;
 187             }
 188
 189 #ifdef DEBUG_GROW
 190             nbElem++;
 191 #endif
 192
 193             iter = next;
 194         }
 195     }
 196
 197     xmlFree(oldtable);
 198
 199 #ifdef DEBUG_GROW
 200     xmlGenericError(xmlGenericErrorContext,
 201             "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
 202 #endif
 203
 204     return(0);
 205 }
 206
 207 /**
 208  * xmlHashFree:
 209  * @table: the hash table
 210  * @f:  the deallocator function for items in the hash
 211  *
 212  * Free the hash @table and its contents. The userdata is
 213  * deallocated with @f if provided.
 214  */
 215 void
 216 xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
 217     int i;
 218     xmlHashEntryPtr iter;
 219     xmlHashEntryPtr next;
 220     int inside_table = 0;
 221
 222     if (table == NULL)
 223         return;
 224     if (table->table) {
 225         for(i = 0; i < table->size; i++) {
 226             iter = &(table->table[i]);
 227             if (iter->valid == 0)
 228                 continue;
 229             inside_table = 1;
 230             while (iter) {
 231                 next = iter->next;
 232                 if (f)
 233                     f(iter->payload, iter->name);
 234                 if (iter->name)
 235                     xmlFree(iter->name);
 236                 if (iter->name2)
 237                     xmlFree(iter->name2);
 238                 if (iter->name3)
 239                     xmlFree(iter->name3);
 240                 iter->payload = NULL;
 241                 if (!inside_table)
 242                     xmlFree(iter);
 243                 inside_table = 0;
 244                 iter = next;
 245             }
 246             inside_table = 0;
 247         }
 248         xmlFree(table->table);
 249     }
 250     xmlFree(table);
 251 }
 252
 253 /**
 254  * xmlHashAddEntry:
 255  * @table: the hash table
 256  * @name: the name of the userdata
 257  * @userdata: a pointer to the userdata
 258  *
 259  * Add the @userdata to the hash @table. This can later be retrieved
 260  * by using the @name. Duplicate names generate errors.
 261  *
 262  * Returns 0 the addition succeeded and -1 in case of error.
 263  */
 264 int
 265 xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
 266     return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
 267 }
 268
 269 /**
 270  * xmlHashAddEntry2:
 271  * @table: the hash table
 272  * @name: the name of the userdata
 273  * @name2: a second name of the userdata
 274  * @userdata: a pointer to the userdata
 275  *
 276  * Add the @userdata to the hash @table. This can later be retrieved
 277  * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
 278  *
 279  * Returns 0 the addition succeeded and -1 in case of error.
 280  */
 281 int
 282 xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
 283                 const xmlChar *name2, void *userdata) {
 284     return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
 285 }
 286
 287 /**
 288  * xmlHashUpdateEntry:
 289  * @table: the hash table
 290  * @name: the name of the userdata
 291  * @userdata: a pointer to the userdata
 292  * @f: the deallocator function for replaced item (if any)
 293  *
 294  * Add the @userdata to the hash @table. This can later be retrieved
 295  * by using the @name. Existing entry for this @name will be removed
 296  * and freed with @f if found.
 297  *
 298  * Returns 0 the addition succeeded and -1 in case of error.
 299  */
 300 int
 301 xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
 302                    void *userdata, xmlHashDeallocator f) {
 303     return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
 304 }
 305
 306 /**
 307  * xmlHashUpdateEntry2:
 308  * @table: the hash table
 309  * @name: the name of the userdata
 310  * @name2: a second name of the userdata
 311  * @userdata: a pointer to the userdata
 312  * @f: the deallocator function for replaced item (if any)
 313  *
 314  * Add the @userdata to the hash @table. This can later be retrieved
 315  * by using the (@name, @name2) tuple. Existing entry for this tuple will
 316  * be removed and freed with @f if found.
 317  *
 318  * Returns 0 the addition succeeded and -1 in case of error.
 319  */
 320 int
 321 xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
 322                    const xmlChar *name2, void *userdata,
 323                    xmlHashDeallocator f) {
 324     return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
 325 }
 326
 327 /**
 328  * xmlHashLookup:
 329  * @table: the hash table
 330  * @name: the name of the userdata
 331  *
 332  * Find the userdata specified by the @name.
 333  *
 334  * Returns the pointer to the userdata
 335  */
 336 void *
 337 xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
 338     return(xmlHashLookup3(table, name, NULL, NULL));
 339 }
 340
 341 /**
 342  * xmlHashLookup2:
 343  * @table: the hash table
 344  * @name: the name of the userdata
 345  * @name2: a second name of the userdata
 346  *
 347  * Find the userdata specified by the (@name, @name2) tuple.
 348  *
 349  * Returns the pointer to the userdata
 350  */
 351 void *
 352 xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
 353               const xmlChar *name2) {
 354     return(xmlHashLookup3(table, name, name2, NULL));
 355 }
 356
 357 /**
 358  * xmlHashAddEntry3:
 359  * @table: the hash table
 360  * @name: the name of the userdata
 361  * @name2: a second name of the userdata
 362  * @name3: a third name of the userdata
 363  * @userdata: a pointer to the userdata
 364  *
 365  * Add the @userdata to the hash @table. This can later be retrieved
 366  * by using the tuple (@name, @name2, @name3). Duplicate entries generate
 367  * errors.
 368  *
 369  * Returns 0 the addition succeeded and -1 in case of error.
 370  */
 371 int
 372 xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
 373                  const xmlChar *name2, const xmlChar *name3,
 374                  void *userdata) {
 375     unsigned long key, len = 0;
 376     xmlHashEntryPtr entry;
 377     xmlHashEntryPtr insert;
 378
 379     if ((table == NULL) || name == NULL)
 380         return(-1);
 381
 382     /*
 383      * Check for duplicate and insertion location.
 384      */
 385     key = xmlHashComputeKey(table, name, name2, name3);
 386     if (table->table[key].valid == 0) {
 387         insert = NULL;
 388     } else {
 389         for (insert = &(table->table[key]); insert->next != NULL;
 390              insert = insert->next) {
 391             if ((xmlStrEqual(insert->name, name)) &&
 392                 (xmlStrEqual(insert->name2, name2)) &&
 393                 (xmlStrEqual(insert->name3, name3)))
 394                 return(-1);
 395             len++;
 396         }
 397         if ((xmlStrEqual(insert->name, name)) &&
 398             (xmlStrEqual(insert->name2, name2)) &&
 399             (xmlStrEqual(insert->name3, name3)))
 400             return(-1);
 401     }
 402
 403     if (insert == NULL) {
 404         entry = &(table->table[key]);
 405     } else {
 406         entry = xmlMalloc(sizeof(xmlHashEntry));
 407         if (entry == NULL)
 408              return(-1);
 409     }
 410
 411     entry->name = xmlStrdup(name);
 412     entry->name2 = xmlStrdup(name2);
 413     entry->name3 = xmlStrdup(name3);
 414     entry->payload = userdata;
 415     entry->next = NULL;
 416     entry->valid = 1;
 417
 418
 419     if (insert != NULL)
 420         insert->next = entry;
 421
 422     table->nbElems++;
 423
 424     if (len > MAX_HASH_LEN)
 425         xmlHashGrow(table, MAX_HASH_LEN * table->size);
 426
 427     return(0);
 428 }
 429
 430 /**
 431  * xmlHashUpdateEntry3:
 432  * @table: the hash table
 433  * @name: the name of the userdata
 434  * @name2: a second name of the userdata
 435  * @name3: a third name of the userdata
 436  * @userdata: a pointer to the userdata
 437  * @f: the deallocator function for replaced item (if any)
 438  *
 439  * Add the @userdata to the hash @table. This can later be retrieved
 440  * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
 441  * will be removed and freed with @f if found.
 442  *
 443  * Returns 0 the addition succeeded and -1 in case of error.
 444  */
 445 int
 446 xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
 447                    const xmlChar *name2, const xmlChar *name3,
 448                    void *userdata, xmlHashDeallocator f) {
 449     unsigned long key;
 450     xmlHashEntryPtr entry;
 451     xmlHashEntryPtr insert;
 452
 453     if ((table == NULL) || name == NULL)
 454         return(-1);
 455
 456     /*
 457      * Check for duplicate and insertion location.
 458      */
 459     key = xmlHashComputeKey(table, name, name2, name3);
 460     if (table->table[key].valid == 0) {
 461         insert = NULL;
 462     } else {
 463         for (insert = &(table->table[key]); insert->next != NULL;
 464              insert = insert->next) {
 465             if ((xmlStrEqual(insert->name, name)) &&
 466                 (xmlStrEqual(insert->name2, name2)) &&
 467                 (xmlStrEqual(insert->name3, name3))) {
 468                 if (f)
 469                     f(insert->payload, insert->name);
 470                 insert->payload = userdata;
 471                 return(0);
 472             }
 473         }
 474         if ((xmlStrEqual(insert->name, name)) &&
 475             (xmlStrEqual(insert->name2, name2)) &&
 476             (xmlStrEqual(insert->name3, name3))) {
 477             if (f)
 478                 f(insert->payload, insert->name);
 479             insert->payload = userdata;
 480             return(0);
 481         }
 482     }
 483
 484     if (insert == NULL) {
 485         entry =  &(table->table[key]);
 486     } else {
 487         entry = xmlMalloc(sizeof(xmlHashEntry));
 488         if (entry == NULL)
 489              return(-1);
 490     }
 491
 492     entry->name = xmlStrdup(name);
 493     entry->name2 = xmlStrdup(name2);
 494     entry->name3 = xmlStrdup(name3);
 495     entry->payload = userdata;
 496     entry->next = NULL;
 497     entry->valid = 1;
 498     table->nbElems++;
 499
 500
 501     if (insert != NULL) {
 502         insert->next = entry;
 503     }
 504     return(0);
 505 }
 506
 507 /**
 508  * xmlHashLookup3:
 509  * @table: the hash table
 510  * @name: the name of the userdata
 511  * @name2: a second name of the userdata
 512  * @name3: a third name of the userdata
 513  *
 514  * Find the userdata specified by the (@name, @name2, @name3) tuple.
 515  *
 516  * Returns the a pointer to the userdata
 517  */
 518 void *
 519 xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
 520                const xmlChar *name2, const xmlChar *name3) {
 521     unsigned long key;
 522     xmlHashEntryPtr entry;
 523
 524     if (table == NULL)
 525         return(NULL);
 526     if (name == NULL)
 527         return(NULL);
 528     key = xmlHashComputeKey(table, name, name2, name3);
 529     if (table->table[key].valid == 0)
 530         return(NULL);
 531     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
 532         if ((xmlStrEqual(entry->name, name)) &&
 533             (xmlStrEqual(entry->name2, name2)) &&
 534             (xmlStrEqual(entry->name3, name3)))
 535             return(entry->payload);
 536     }
 537     return(NULL);
 538 }
 539
 540 typedef struct {
 541     xmlHashScanner hashscanner;
 542     void *data;
 543 } stubData;
 544
 545 static void
 546 stubHashScannerFull (void *payload, void *data, const xmlChar *name,
 547                      const xmlChar *name2 ATTRIBUTE_UNUSED,
 548                      const xmlChar *name3 ATTRIBUTE_UNUSED) {
 549     stubData *stubdata = (stubData *) data;
 550     stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
 551 }
 552
 553 /**
 554  * xmlHashScan:
 555  * @table: the hash table
 556  * @f:  the scanner function for items in the hash
 557  * @data:  extra data passed to f
 558  *
 559  * Scan the hash @table and applied @f to each value.
 560  */
 561 void
 562 xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
 563     stubData stubdata;
 564     stubdata.data = data;
 565     stubdata.hashscanner = f;
 566     xmlHashScanFull (table, stubHashScannerFull, &stubdata);
 567 }
 568
 569 /**
 570  * xmlHashScanFull:
 571  * @table: the hash table
 572  * @f:  the scanner function for items in the hash
 573  * @data:  extra data passed to f
 574  *
 575  * Scan the hash @table and applied @f to each value.
 576  */
 577 void
 578 xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
 579     int i;
 580     xmlHashEntryPtr iter;
 581     xmlHashEntryPtr next;
 582
 583     if (table == NULL)
 584         return;
 585     if (f == NULL)
 586         return;
 587
 588     if (table->table) {
 589         for(i = 0; i < table->size; i++) {
 590             if (table->table[i].valid == 0)
 591                 continue;
 592             iter = &(table->table[i]);
 593             while (iter) {
 594                 next = iter->next;
 595                 if (f)
 596                     f(iter->payload, data, iter->name,
 597                       iter->name2, iter->name3);
 598                 iter = next;
 599             }
 600         }
 601     }
 602 }
 603
 604 /**
 605  * xmlHashScan3:
 606  * @table: the hash table
 607  * @name: the name of the userdata or NULL
 608  * @name2: a second name of the userdata or NULL
 609  * @name3: a third name of the userdata or NULL
 610  * @f:  the scanner function for items in the hash
 611  * @data:  extra data passed to f
 612  *
 613  * Scan the hash @table and applied @f to each value matching
 614  * (@name, @name2, @name3) tuple. If one of the names is null,
 615  * the comparison is considered to match.
 616  */
 617 void
 618 xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
 619              const xmlChar *name2, const xmlChar *name3,
 620              xmlHashScanner f, void *data) {
 621     xmlHashScanFull3 (table, name, name2, name3,
 622                       (xmlHashScannerFull) f, data);
 623 }
 624
 625 /**
 626  * xmlHashScanFull3:
 627  * @table: the hash table
 628  * @name: the name of the userdata or NULL
 629  * @name2: a second name of the userdata or NULL
 630  * @name3: a third name of the userdata or NULL
 631  * @f:  the scanner function for items in the hash
 632  * @data:  extra data passed to f
 633  *
 634  * Scan the hash @table and applied @f to each value matching
 635  * (@name, @name2, @name3) tuple. If one of the names is null,
 636  * the comparison is considered to match.
 637  */
 638 void
 639 xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
 640                  const xmlChar *name2, const xmlChar *name3,
 641                  xmlHashScannerFull f, void *data) {
 642     int i;
 643     xmlHashEntryPtr iter;
 644     xmlHashEntryPtr next;
 645
 646     if (table == NULL)
 647         return;
 648     if (f == NULL)
 649         return;
 650
 651     if (table->table) {
 652         for(i = 0; i < table->size; i++) {
 653             if (table->table[i].valid == 0)
 654                 continue;
 655             iter = &(table->table[i]);
 656             while (iter) {
 657                 next = iter->next;
 658                 if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
 659                     ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
 660                     ((name3 == NULL) || (xmlStrEqual(name3, iter->name3)))) {
 661                     f(iter->payload, data, iter->name,
 662                       iter->name2, iter->name3);
 663                 }
 664                 iter = next;
 665             }
 666         }
 667     }
 668 }
 669
 670 /**
 671  * xmlHashCopy:
 672  * @table: the hash table
 673  * @f:  the copier function for items in the hash
 674  *
 675  * Scan the hash @table and applied @f to each value.
 676  *
 677  * Returns the new table or NULL in case of error.
 678  */
 679 xmlHashTablePtr
 680 xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
 681     int i;
 682     xmlHashEntryPtr iter;
 683     xmlHashEntryPtr next;
 684     xmlHashTablePtr ret;
 685
 686     if (table == NULL)
 687         return(NULL);
 688     if (f == NULL)
 689         return(NULL);
 690
 691     ret = xmlHashCreate(table->size);
 692     if (table->table) {
 693         for(i = 0; i < table->size; i++) {
 694             if (table->table[i].valid == 0)
 695                 continue;
 696             iter = &(table->table[i]);
 697             while (iter) {
 698                 next = iter->next;
 699                 xmlHashAddEntry3(ret, iter->name, iter->name2,
 700                                  iter->name3, f(iter->payload, iter->name));
 701                 iter = next;
 702             }
 703         }
 704     }
 705     ret->nbElems = table->nbElems;
 706     return(ret);
 707 }
 708
 709 /**
 710  * xmlHashSize:
 711  * @table: the hash table
 712  *
 713  * Query the number of elements installed in the hash @table.
 714  *
 715  * Returns the number of elements in the hash table or
 716  * -1 in case of error
 717  */
 718 int
 719 xmlHashSize(xmlHashTablePtr table) {
 720     if (table == NULL)
 721         return(-1);
 722     return(table->nbElems);
 723 }
 724
 725 /**
 726  * xmlHashRemoveEntry:
 727  * @table: the hash table
 728  * @name: the name of the userdata
 729  * @f: the deallocator function for removed item (if any)
 730  *
 731  * Find the userdata specified by the @name and remove
 732  * it from the hash @table. Existing userdata for this tuple will be removed
 733  * and freed with @f.
 734  *
 735  * Returns 0 if the removal succeeded and -1 in case of error or not found.
 736  */
 737 int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
 738                        xmlHashDeallocator f) {
 739     return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
 740 }
 741
 742 /**
 743  * xmlHashRemoveEntry2:
 744  * @table: the hash table
 745  * @name: the name of the userdata
 746  * @name2: a second name of the userdata
 747  * @f: the deallocator function for removed item (if any)
 748  *
 749  * Find the userdata specified by the (@name, @name2) tuple and remove
 750  * it from the hash @table. Existing userdata for this tuple will be removed
 751  * and freed with @f.
 752  *
 753  * Returns 0 if the removal succeeded and -1 in case of error or not found.
 754  */
 755 int
 756 xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
 757                         const xmlChar *name2, xmlHashDeallocator f) {
 758     return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
 759 }
 760
 761 /**
 762  * xmlHashRemoveEntry3:
 763  * @table: the hash table
 764  * @name: the name of the userdata
 765  * @name2: a second name of the userdata
 766  * @name3: a third name of the userdata
 767  * @f: the deallocator function for removed item (if any)
 768  *
 769  * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
 770  * it from the hash @table. Existing userdata for this tuple will be removed
 771  * and freed with @f.
 772  *
 773  * Returns 0 if the removal succeeded and -1 in case of error or not found.
 774  */
 775 int
 776 xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
 777     const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
 778     unsigned long key;
 779     xmlHashEntryPtr entry;
 780     xmlHashEntryPtr prev = NULL;
 781
 782     if (table == NULL || name == NULL)
 783         return(-1);
 784
 785     key = xmlHashComputeKey(table, name, name2, name3);
 786     if (table->table[key].valid == 0) {
 787         return(-1);
 788     } else {
 789         for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
 790             if (xmlStrEqual(entry->name, name) &&
 791                     xmlStrEqual(entry->name2, name2) &&
 792                     xmlStrEqual(entry->name3, name3)) {
 793                 if(f)
 794                     f(entry->payload, entry->name);
 795                 entry->payload = NULL;
 796                 if(entry->name)
 797                     xmlFree(entry->name);
 798                 if(entry->name2)
 799                     xmlFree(entry->name2);
 800                 if(entry->name3)
 801                     xmlFree(entry->name3);
 802                 if(prev) {
 803                     prev->next = entry->next;
 804                     xmlFree(entry);
 805                 } else {
 806                     if (entry->next == NULL) {
 807                         entry->valid = 0;
 808                     } else {
 809                         entry = entry->next;
 810                         memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
 811                         xmlFree(entry);
 812                     }
 813                 }
 814                 table->nbElems--;
 815                 return(0);
 816             }
 817             prev = entry;
 818         }
 819         return(-1);
 820     }
 821 }
 822