Annotation of embedaddon/libxml2/hash.c, revision 1.1
1.1 ! misho 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"
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libxml2