gnulib-local/lib/libxml/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             inside_table = 0;
 324         }
 325         xmlFree(table->table);
 326     }
 327     if (table->dict)
 328         xmlDictFree(table->dict);
 329     xmlFree(table);
 330 }
 331
 332 /**
 333  * xmlHashAddEntry:
 334  * @table: the hash table
 335  * @name: the name of the userdata
 336  * @userdata: a pointer to the userdata
 337  *
 338  * Add the @userdata to the hash @table. This can later be retrieved
 339  * by using the @name. Duplicate names generate errors.
 340  *
 341  * Returns 0 the addition succeeded and -1 in case of error.
 342  */
 343 int
 344 xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
 345     return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
 346 }
 347
 348 /**
 349  * xmlHashAddEntry2:
 350  * @table: the hash table
 351  * @name: the name of the userdata
 352  * @name2: a second name of the userdata
 353  * @userdata: a pointer to the userdata
 354  *
 355  * Add the @userdata to the hash @table. This can later be retrieved
 356  * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
 357  *
 358  * Returns 0 the addition succeeded and -1 in case of error.
 359  */
 360 int
 361 xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
 362                 const xmlChar *name2, void *userdata) {
 363     return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
 364 }
 365
 366 /**
 367  * xmlHashUpdateEntry:
 368  * @table: the hash table
 369  * @name: the name of the userdata
 370  * @userdata: a pointer to the userdata
 371  * @f: the deallocator function for replaced item (if any)
 372  *
 373  * Add the @userdata to the hash @table. This can later be retrieved
 374  * by using the @name. Existing entry for this @name will be removed
 375  * and freed with @f if found.
 376  *
 377  * Returns 0 the addition succeeded and -1 in case of error.
 378  */
 379 int
 380 xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
 381                    void *userdata, xmlHashDeallocator f) {
 382     return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
 383 }
 384
 385 /**
 386  * xmlHashUpdateEntry2:
 387  * @table: the hash table
 388  * @name: the name of the userdata
 389  * @name2: a second name of the userdata
 390  * @userdata: a pointer to the userdata
 391  * @f: the deallocator function for replaced item (if any)
 392  *
 393  * Add the @userdata to the hash @table. This can later be retrieved
 394  * by using the (@name, @name2) tuple. Existing entry for this tuple will
 395  * be removed and freed with @f if found.
 396  *
 397  * Returns 0 the addition succeeded and -1 in case of error.
 398  */
 399 int
 400 xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
 401                    const xmlChar *name2, void *userdata,
 402                    xmlHashDeallocator f) {
 403     return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
 404 }
 405
 406 /**
 407  * xmlHashLookup:
 408  * @table: the hash table
 409  * @name: the name of the userdata
 410  *
 411  * Find the userdata specified by the @name.
 412  *
 413  * Returns the pointer to the userdata
 414  */
 415 void *
 416 xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
 417     return(xmlHashLookup3(table, name, NULL, NULL));
 418 }
 419
 420 /**
 421  * xmlHashLookup2:
 422  * @table: the hash table
 423  * @name: the name of the userdata
 424  * @name2: a second name of the userdata
 425  *
 426  * Find the userdata specified by the (@name, @name2) tuple.
 427  *
 428  * Returns the pointer to the userdata
 429  */
 430 void *
 431 xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
 432               const xmlChar *name2) {
 433     return(xmlHashLookup3(table, name, name2, NULL));
 434 }
 435
 436 /**
 437  * xmlHashQLookup:
 438  * @table: the hash table
 439  * @prefix: the prefix of the userdata
 440  * @name: the name of the userdata
 441  *
 442  * Find the userdata specified by the QName @prefix:@name/@name.
 443  *
 444  * Returns the pointer to the userdata
 445  */
 446 void *
 447 xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,
 448                const xmlChar *name) {
 449     return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));
 450 }
 451
 452 /**
 453  * xmlHashQLookup2:
 454  * @table: the hash table
 455  * @prefix: the prefix of the userdata
 456  * @name: the name of the userdata
 457  * @prefix2: the second prefix of the userdata
 458  * @name2: a second name of the userdata
 459  *
 460  * Find the userdata specified by the QNames tuple
 461  *
 462  * Returns the pointer to the userdata
 463  */
 464 void *
 465 xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,
 466                 const xmlChar *name, const xmlChar *prefix2,
 467                 const xmlChar *name2) {
 468     return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
 469 }
 470
 471 /**
 472  * xmlHashAddEntry3:
 473  * @table: the hash table
 474  * @name: the name of the userdata
 475  * @name2: a second name of the userdata
 476  * @name3: a third name of the userdata
 477  * @userdata: a pointer to the userdata
 478  *
 479  * Add the @userdata to the hash @table. This can later be retrieved
 480  * by using the tuple (@name, @name2, @name3). Duplicate entries generate
 481  * errors.
 482  *
 483  * Returns 0 the addition succeeded and -1 in case of error.
 484  */
 485 int
 486 xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
 487                  const xmlChar *name2, const xmlChar *name3,
 488                  void *userdata) {
 489     unsigned long key, len = 0;
 490     xmlHashEntryPtr entry;
 491     xmlHashEntryPtr insert;
 492
 493     if ((table == NULL) || (name == NULL))
 494         return(-1);
 495
 496     /*
 497      * If using a dict internalize if needed
 498      */
 499     if (table->dict) {
 500         if (!xmlDictOwns(table->dict, name)) {
 501             name = xmlDictLookup(table->dict, name, -1);
 502             if (name == NULL)
 503                 return(-1);
 504         }
 505         if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
 506             name2 = xmlDictLookup(table->dict, name2, -1);
 507             if (name2 == NULL)
 508                 return(-1);
 509         }
 510         if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
 511             name3 = xmlDictLookup(table->dict, name3, -1);
 512             if (name3 == NULL)
 513                 return(-1);
 514         }
 515     }
 516
 517     /*
 518      * Check for duplicate and insertion location.
 519      */
 520     key = xmlHashComputeKey(table, name, name2, name3);
 521     if (table->table[key].valid == 0) {
 522         insert = NULL;
 523     } else {
 524         if (table->dict) {
 525             for (insert = &(table->table[key]); insert->next != NULL;
 526                  insert = insert->next) {
 527                 if ((insert->name == name) &&
 528                     (insert->name2 == name2) &&
 529                     (insert->name3 == name3))
 530                     return(-1);
 531                 len++;
 532             }
 533             if ((insert->name == name) &&
 534                 (insert->name2 == name2) &&
 535                 (insert->name3 == name3))
 536                 return(-1);
 537         } else {
 538             for (insert = &(table->table[key]); insert->next != NULL;
 539                  insert = insert->next) {
 540                 if ((xmlStrEqual(insert->name, name)) &&
 541                     (xmlStrEqual(insert->name2, name2)) &&
 542                     (xmlStrEqual(insert->name3, name3)))
 543                     return(-1);
 544                 len++;
 545             }
 546             if ((xmlStrEqual(insert->name, name)) &&
 547                 (xmlStrEqual(insert->name2, name2)) &&
 548                 (xmlStrEqual(insert->name3, name3)))
 549                 return(-1);
 550         }
 551     }
 552
 553     if (insert == NULL) {
 554         entry = &(table->table[key]);
 555     } else {
 556         entry = xmlMalloc(sizeof(xmlHashEntry));
 557         if (entry == NULL)
 558              return(-1);
 559     }
 560
 561     if (table->dict != NULL) {
 562         entry->name = (xmlChar *) name;
 563         entry->name2 = (xmlChar *) name2;
 564         entry->name3 = (xmlChar *) name3;
 565     } else {
 566         entry->name = xmlStrdup(name);
 567         entry->name2 = xmlStrdup(name2);
 568         entry->name3 = xmlStrdup(name3);
 569     }
 570     entry->payload = userdata;
 571     entry->next = NULL;
 572     entry->valid = 1;
 573
 574
 575     if (insert != NULL)
 576         insert->next = entry;
 577
 578     table->nbElems++;
 579
 580     if (len > MAX_HASH_LEN)
 581         xmlHashGrow(table, MAX_HASH_LEN * table->size);
 582
 583     return(0);
 584 }
 585
 586 /**
 587  * xmlHashUpdateEntry3:
 588  * @table: the hash table
 589  * @name: the name of the userdata
 590  * @name2: a second name of the userdata
 591  * @name3: a third name of the userdata
 592  * @userdata: a pointer to the userdata
 593  * @f: the deallocator function for replaced item (if any)
 594  *
 595  * Add the @userdata to the hash @table. This can later be retrieved
 596  * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
 597  * will be removed and freed with @f if found.
 598  *
 599  * Returns 0 the addition succeeded and -1 in case of error.
 600  */
 601 int
 602 xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
 603                    const xmlChar *name2, const xmlChar *name3,
 604                    void *userdata, xmlHashDeallocator f) {
 605     unsigned long key;
 606     xmlHashEntryPtr entry;
 607     xmlHashEntryPtr insert;
 608
 609     if ((table == NULL) || name == NULL)
 610         return(-1);
 611
 612     /*
 613      * If using a dict internalize if needed
 614      */
 615     if (table->dict) {
 616         if (!xmlDictOwns(table->dict, name)) {
 617             name = xmlDictLookup(table->dict, name, -1);
 618             if (name == NULL)
 619                 return(-1);
 620         }
 621         if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
 622             name2 = xmlDictLookup(table->dict, name2, -1);
 623             if (name2 == NULL)
 624                 return(-1);
 625         }
 626         if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
 627             name3 = xmlDictLookup(table->dict, name3, -1);
 628             if (name3 == NULL)
 629                 return(-1);
 630         }
 631     }
 632
 633     /*
 634      * Check for duplicate and insertion location.
 635      */
 636     key = xmlHashComputeKey(table, name, name2, name3);
 637     if (table->table[key].valid == 0) {
 638         insert = NULL;
 639     } else {
 640         if (table ->dict) {
 641             for (insert = &(table->table[key]); insert->next != NULL;
 642                  insert = insert->next) {
 643                 if ((insert->name == name) &&
 644                     (insert->name2 == name2) &&
 645                     (insert->name3 == name3)) {
 646                     if (f)
 647                         f(insert->payload, insert->name);
 648                     insert->payload = userdata;
 649                     return(0);
 650                 }
 651             }
 652             if ((insert->name == name) &&
 653                 (insert->name2 == name2) &&
 654                 (insert->name3 == name3)) {
 655                 if (f)
 656                     f(insert->payload, insert->name);
 657                 insert->payload = userdata;
 658                 return(0);
 659             }
 660         } else {
 661             for (insert = &(table->table[key]); insert->next != NULL;
 662                  insert = insert->next) {
 663                 if ((xmlStrEqual(insert->name, name)) &&
 664                     (xmlStrEqual(insert->name2, name2)) &&
 665                     (xmlStrEqual(insert->name3, name3))) {
 666                     if (f)
 667                         f(insert->payload, insert->name);
 668                     insert->payload = userdata;
 669                     return(0);
 670                 }
 671             }
 672             if ((xmlStrEqual(insert->name, name)) &&
 673                 (xmlStrEqual(insert->name2, name2)) &&
 674                 (xmlStrEqual(insert->name3, name3))) {
 675                 if (f)
 676                     f(insert->payload, insert->name);
 677                 insert->payload = userdata;
 678                 return(0);
 679             }
 680         }
 681     }
 682
 683     if (insert == NULL) {
 684         entry =  &(table->table[key]);
 685     } else {
 686         entry = xmlMalloc(sizeof(xmlHashEntry));
 687         if (entry == NULL)
 688              return(-1);
 689     }
 690
 691     if (table->dict != NULL) {
 692         entry->name = (xmlChar *) name;
 693         entry->name2 = (xmlChar *) name2;
 694         entry->name3 = (xmlChar *) name3;
 695     } else {
 696         entry->name = xmlStrdup(name);
 697         entry->name2 = xmlStrdup(name2);
 698         entry->name3 = xmlStrdup(name3);
 699     }
 700     entry->payload = userdata;
 701     entry->next = NULL;
 702     entry->valid = 1;
 703     table->nbElems++;
 704
 705
 706     if (insert != NULL) {
 707         insert->next = entry;
 708     }
 709     return(0);
 710 }
 711
 712 /**
 713  * xmlHashLookup3:
 714  * @table: the hash table
 715  * @name: the name of the userdata
 716  * @name2: a second name of the userdata
 717  * @name3: a third name of the userdata
 718  *
 719  * Find the userdata specified by the (@name, @name2, @name3) tuple.
 720  *
 721  * Returns the a pointer to the userdata
 722  */
 723 void *
 724 xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
 725                const xmlChar *name2, const xmlChar *name3) {
 726     unsigned long key;
 727     xmlHashEntryPtr entry;
 728
 729     if (table == NULL)
 730         return(NULL);
 731     if (name == NULL)
 732         return(NULL);
 733     key = xmlHashComputeKey(table, name, name2, name3);
 734     if (table->table[key].valid == 0)
 735         return(NULL);
 736     if (table->dict) {
 737         for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
 738             if ((entry->name == name) &&
 739                 (entry->name2 == name2) &&
 740                 (entry->name3 == name3))
 741                 return(entry->payload);
 742         }
 743     }
 744     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
 745         if ((xmlStrEqual(entry->name, name)) &&
 746             (xmlStrEqual(entry->name2, name2)) &&
 747             (xmlStrEqual(entry->name3, name3)))
 748             return(entry->payload);
 749     }
 750     return(NULL);
 751 }
 752
 753 /**
 754  * xmlHashQLookup3:
 755  * @table: the hash table
 756  * @prefix: the prefix of the userdata
 757  * @name: the name of the userdata
 758  * @prefix2: the second prefix of the userdata
 759  * @name2: a second name of the userdata
 760  * @prefix3: the third prefix of the userdata
 761  * @name3: a third name of the userdata
 762  *
 763  * Find the userdata specified by the (@name, @name2, @name3) tuple.
 764  *
 765  * Returns the a pointer to the userdata
 766  */
 767 void *
 768 xmlHashQLookup3(xmlHashTablePtr table,
 769                 const xmlChar *prefix, const xmlChar *name,
 770                 const xmlChar *prefix2, const xmlChar *name2,
 771                 const xmlChar *prefix3, const xmlChar *name3) {
 772     unsigned long key;
 773     xmlHashEntryPtr entry;
 774
 775     if (table == NULL)
 776         return(NULL);
 777     if (name == NULL)
 778         return(NULL);
 779     key = xmlHashComputeQKey(table, prefix, name, prefix2,
 780                              name2, prefix3, name3);
 781     if (table->table[key].valid == 0)
 782         return(NULL);
 783     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
 784         if ((xmlStrQEqual(prefix, name, entry->name)) &&
 785             (xmlStrQEqual(prefix2, name2, entry->name2)) &&
 786             (xmlStrQEqual(prefix3, name3, entry->name3)))
 787             return(entry->payload);
 788     }
 789     return(NULL);
 790 }
 791
 792 typedef struct {
 793     xmlHashScanner hashscanner;
 794     void *data;
 795 } stubData;
 796
 797 static void
 798 stubHashScannerFull (void *payload, void *data, const xmlChar *name,
 799                      const xmlChar *name2 ATTRIBUTE_UNUSED,
 800                      const xmlChar *name3 ATTRIBUTE_UNUSED) {
 801     stubData *stubdata = (stubData *) data;
 802     stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
 803 }
 804
 805 /**
 806  * xmlHashScan:
 807  * @table: the hash table
 808  * @f:  the scanner function for items in the hash
 809  * @data:  extra data passed to f
 810  *
 811  * Scan the hash @table and applied @f to each value.
 812  */
 813 void
 814 xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
 815     stubData stubdata;
 816     stubdata.data = data;
 817     stubdata.hashscanner = f;
 818     xmlHashScanFull (table, stubHashScannerFull, &stubdata);
 819 }
 820
 821 /**
 822  * xmlHashScanFull:
 823  * @table: the hash table
 824  * @f:  the scanner function for items in the hash
 825  * @data:  extra data passed to f
 826  *
 827  * Scan the hash @table and applied @f to each value.
 828  */
 829 void
 830 xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
 831     int i;
 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  */
 869 void
 870 xmlHashScan3(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  */
 890 void
 891 xmlHashScanFull3(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  */
 932 xmlHashTablePtr
 933 xmlHashCopy(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  */
 971 int
 972 xmlHashSize(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  */
 990 int 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  */
1008 int
1009 xmlHashRemoveEntry2(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  */
1028 int
1029 xmlHashRemoveEntry3(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"