third_party/libxml/src/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/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"