diff options
author | William Joye <wjoye@cfa.harvard.edu> | 2016-10-19 18:26:52 (GMT) |
---|---|---|
committer | William Joye <wjoye@cfa.harvard.edu> | 2016-10-19 18:26:52 (GMT) |
commit | 818fd731f62993dc8aa5d07b82e1d1b2c04aae7d (patch) | |
tree | 41a61b0a1b18ed5ffeeb028e986b3586f9063628 /libxml2/hash.c | |
parent | d72feaf69933b069cff3c0cb20a5f5f03ecba77b (diff) | |
download | blt-818fd731f62993dc8aa5d07b82e1d1b2c04aae7d.zip blt-818fd731f62993dc8aa5d07b82e1d1b2c04aae7d.tar.gz blt-818fd731f62993dc8aa5d07b82e1d1b2c04aae7d.tar.bz2 |
update libxml2
Diffstat (limited to 'libxml2/hash.c')
-rw-r--r-- | libxml2/hash.c | 1124 |
1 files changed, 0 insertions, 1124 deletions
diff --git a/libxml2/hash.c b/libxml2/hash.c deleted file mode 100644 index f9a2017..0000000 --- a/libxml2/hash.c +++ /dev/null @@ -1,1124 +0,0 @@ -/* - * hash.c: chained hash tables - * - * Reference: Your favorite introductory book on algorithms - * - * Copyright (C) 2000,2012 Bjorn Reese and Daniel Veillard. - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED - * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF - * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND - * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER. - * - * Author: breese@users.sourceforge.net - */ - -#define IN_LIBXML -#include "libxml.h" - -#include <string.h> -#ifdef HAVE_STDLIB_H -#include <stdlib.h> -#endif -#ifdef HAVE_TIME_H -#include <time.h> -#endif - -/* - * Following http://www.ocert.org/advisories/ocert-2011-003.html - * it seems that having hash randomization might be a good idea - * when using XML with untrusted data - */ -#if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME) -#define HASH_RANDOMIZATION -#endif - -#include <libxml/parser.h> -#include <libxml/hash.h> -#include <libxml/xmlmemory.h> -#include <libxml/xmlerror.h> -#include <libxml/globals.h> - -#define MAX_HASH_LEN 8 - -/* #define DEBUG_GROW */ - -/* - * A single entry in the hash table - */ -typedef struct _xmlHashEntry xmlHashEntry; -typedef xmlHashEntry *xmlHashEntryPtr; -struct _xmlHashEntry { - struct _xmlHashEntry *next; - xmlChar *name; - xmlChar *name2; - xmlChar *name3; - void *payload; - int valid; -}; - -/* - * The entire hash table - */ -struct _xmlHashTable { - struct _xmlHashEntry *table; - int size; - int nbElems; - xmlDictPtr dict; -#ifdef HASH_RANDOMIZATION - int random_seed; -#endif -}; - -/* - * xmlHashComputeKey: - * Calculate the hash key - */ -static unsigned long -xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3) { - unsigned long value = 0L; - char ch; - -#ifdef HASH_RANDOMIZATION - value = table->random_seed; -#endif - if (name != NULL) { - value += 30 * (*name); - while ((ch = *name++) != 0) { - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); - } - } - value = value ^ ((value << 5) + (value >> 3)); - if (name2 != NULL) { - while ((ch = *name2++) != 0) { - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); - } - } - value = value ^ ((value << 5) + (value >> 3)); - if (name3 != NULL) { - while ((ch = *name3++) != 0) { - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); - } - } - return (value % table->size); -} - -static unsigned long -xmlHashComputeQKey(xmlHashTablePtr table, - const xmlChar *prefix, const xmlChar *name, - const xmlChar *prefix2, const xmlChar *name2, - const xmlChar *prefix3, const xmlChar *name3) { - unsigned long value = 0L; - char ch; - -#ifdef HASH_RANDOMIZATION - value = table->random_seed; -#endif - if (prefix != NULL) - value += 30 * (*prefix); - else - value += 30 * (*name); - - if (prefix != NULL) { - while ((ch = *prefix++) != 0) { - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); - } - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':'); - } - if (name != NULL) { - while ((ch = *name++) != 0) { - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); - } - } - value = value ^ ((value << 5) + (value >> 3)); - if (prefix2 != NULL) { - while ((ch = *prefix2++) != 0) { - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); - } - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':'); - } - if (name2 != NULL) { - while ((ch = *name2++) != 0) { - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); - } - } - value = value ^ ((value << 5) + (value >> 3)); - if (prefix3 != NULL) { - while ((ch = *prefix3++) != 0) { - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); - } - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':'); - } - if (name3 != NULL) { - while ((ch = *name3++) != 0) { - value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); - } - } - return (value % table->size); -} - -/** - * xmlHashCreate: - * @size: the size of the hash table - * - * Create a new xmlHashTablePtr. - * - * Returns the newly created object, or NULL if an error occured. - */ -xmlHashTablePtr -xmlHashCreate(int size) { - xmlHashTablePtr table; - - if (size <= 0) - size = 256; - - table = xmlMalloc(sizeof(xmlHashTable)); - if (table) { - table->dict = NULL; - table->size = size; - table->nbElems = 0; - table->table = xmlMalloc(size * sizeof(xmlHashEntry)); - if (table->table) { - memset(table->table, 0, size * sizeof(xmlHashEntry)); -#ifdef HASH_RANDOMIZATION - table->random_seed = __xmlRandom(); -#endif - return(table); - } - xmlFree(table); - } - return(NULL); -} - -/** - * xmlHashCreateDict: - * @size: the size of the hash table - * @dict: a dictionary to use for the hash - * - * Create a new xmlHashTablePtr which will use @dict as the internal dictionary - * - * Returns the newly created object, or NULL if an error occured. - */ -xmlHashTablePtr -xmlHashCreateDict(int size, xmlDictPtr dict) { - xmlHashTablePtr table; - - table = xmlHashCreate(size); - if (table != NULL) { - table->dict = dict; - xmlDictReference(dict); - } - return(table); -} - -/** - * xmlHashGrow: - * @table: the hash table - * @size: the new size of the hash table - * - * resize the hash table - * - * Returns 0 in case of success, -1 in case of failure - */ -static int -xmlHashGrow(xmlHashTablePtr table, int size) { - unsigned long key; - int oldsize, i; - xmlHashEntryPtr iter, next; - struct _xmlHashEntry *oldtable; -#ifdef DEBUG_GROW - unsigned long nbElem = 0; -#endif - - if (table == NULL) - return(-1); - if (size < 8) - return(-1); - if (size > 8 * 2048) - return(-1); - - oldsize = table->size; - oldtable = table->table; - if (oldtable == NULL) - return(-1); - - table->table = xmlMalloc(size * sizeof(xmlHashEntry)); - if (table->table == NULL) { - table->table = oldtable; - return(-1); - } - memset(table->table, 0, size * sizeof(xmlHashEntry)); - table->size = size; - - /* If the two loops are merged, there would be situations where - a new entry needs to allocated and data copied into it from - the main table. So instead, we run through the array twice, first - copying all the elements in the main array (where we can't get - conflicts) and then the rest, so we only free (and don't allocate) - */ - for (i = 0; i < oldsize; i++) { - if (oldtable[i].valid == 0) - continue; - key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2, - oldtable[i].name3); - memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry)); - table->table[key].next = NULL; - } - - for (i = 0; i < oldsize; i++) { - iter = oldtable[i].next; - while (iter) { - next = iter->next; - - /* - * put back the entry in the new table - */ - - key = xmlHashComputeKey(table, iter->name, iter->name2, - iter->name3); - if (table->table[key].valid == 0) { - memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry)); - table->table[key].next = NULL; - xmlFree(iter); - } else { - iter->next = table->table[key].next; - table->table[key].next = iter; - } - -#ifdef DEBUG_GROW - nbElem++; -#endif - - iter = next; - } - } - - xmlFree(oldtable); - -#ifdef DEBUG_GROW - xmlGenericError(xmlGenericErrorContext, - "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem); -#endif - - return(0); -} - -/** - * xmlHashFree: - * @table: the hash table - * @f: the deallocator function for items in the hash - * - * Free the hash @table and its contents. The userdata is - * deallocated with @f if provided. - */ -void -xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) { - int i; - xmlHashEntryPtr iter; - xmlHashEntryPtr next; - int inside_table = 0; - int nbElems; - - if (table == NULL) - return; - if (table->table) { - nbElems = table->nbElems; - for(i = 0; (i < table->size) && (nbElems > 0); i++) { - iter = &(table->table[i]); - if (iter->valid == 0) - continue; - inside_table = 1; - while (iter) { - next = iter->next; - if ((f != NULL) && (iter->payload != NULL)) - f(iter->payload, iter->name); - if (table->dict == NULL) { - if (iter->name) - xmlFree(iter->name); - if (iter->name2) - xmlFree(iter->name2); - if (iter->name3) - xmlFree(iter->name3); - } - iter->payload = NULL; - if (!inside_table) - xmlFree(iter); - nbElems--; - inside_table = 0; - iter = next; - } - } - xmlFree(table->table); - } - if (table->dict) - xmlDictFree(table->dict); - xmlFree(table); -} - -/** - * xmlHashAddEntry: - * @table: the hash table - * @name: the name of the userdata - * @userdata: a pointer to the userdata - * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the @name. Duplicate names generate errors. - * - * Returns 0 the addition succeeded and -1 in case of error. - */ -int -xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) { - return(xmlHashAddEntry3(table, name, NULL, NULL, userdata)); -} - -/** - * xmlHashAddEntry2: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @userdata: a pointer to the userdata - * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the (@name, @name2) tuple. Duplicate tuples generate errors. - * - * Returns 0 the addition succeeded and -1 in case of error. - */ -int -xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, void *userdata) { - return(xmlHashAddEntry3(table, name, name2, NULL, userdata)); -} - -/** - * xmlHashUpdateEntry: - * @table: the hash table - * @name: the name of the userdata - * @userdata: a pointer to the userdata - * @f: the deallocator function for replaced item (if any) - * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the @name. Existing entry for this @name will be removed - * and freed with @f if found. - * - * Returns 0 the addition succeeded and -1 in case of error. - */ -int -xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name, - void *userdata, xmlHashDeallocator f) { - return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f)); -} - -/** - * xmlHashUpdateEntry2: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @userdata: a pointer to the userdata - * @f: the deallocator function for replaced item (if any) - * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the (@name, @name2) tuple. Existing entry for this tuple will - * be removed and freed with @f if found. - * - * Returns 0 the addition succeeded and -1 in case of error. - */ -int -xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, void *userdata, - xmlHashDeallocator f) { - return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f)); -} - -/** - * xmlHashLookup: - * @table: the hash table - * @name: the name of the userdata - * - * Find the userdata specified by the @name. - * - * Returns the pointer to the userdata - */ -void * -xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) { - return(xmlHashLookup3(table, name, NULL, NULL)); -} - -/** - * xmlHashLookup2: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * - * Find the userdata specified by the (@name, @name2) tuple. - * - * Returns the pointer to the userdata - */ -void * -xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2) { - return(xmlHashLookup3(table, name, name2, NULL)); -} - -/** - * xmlHashQLookup: - * @table: the hash table - * @prefix: the prefix of the userdata - * @name: the name of the userdata - * - * Find the userdata specified by the QName @prefix:@name/@name. - * - * Returns the pointer to the userdata - */ -void * -xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix, - const xmlChar *name) { - return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL)); -} - -/** - * xmlHashQLookup2: - * @table: the hash table - * @prefix: the prefix of the userdata - * @name: the name of the userdata - * @prefix2: the second prefix of the userdata - * @name2: a second name of the userdata - * - * Find the userdata specified by the QNames tuple - * - * Returns the pointer to the userdata - */ -void * -xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix, - const xmlChar *name, const xmlChar *prefix2, - const xmlChar *name2) { - return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL)); -} - -/** - * xmlHashAddEntry3: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @name3: a third name of the userdata - * @userdata: a pointer to the userdata - * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the tuple (@name, @name2, @name3). Duplicate entries generate - * errors. - * - * Returns 0 the addition succeeded and -1 in case of error. - */ -int -xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3, - void *userdata) { - unsigned long key, len = 0; - xmlHashEntryPtr entry; - xmlHashEntryPtr insert; - - if ((table == NULL) || (name == NULL)) - return(-1); - - /* - * If using a dict internalize if needed - */ - if (table->dict) { - if (!xmlDictOwns(table->dict, name)) { - name = xmlDictLookup(table->dict, name, -1); - if (name == NULL) - return(-1); - } - if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) { - name2 = xmlDictLookup(table->dict, name2, -1); - if (name2 == NULL) - return(-1); - } - if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) { - name3 = xmlDictLookup(table->dict, name3, -1); - if (name3 == NULL) - return(-1); - } - } - - /* - * Check for duplicate and insertion location. - */ - key = xmlHashComputeKey(table, name, name2, name3); - if (table->table[key].valid == 0) { - insert = NULL; - } else { - if (table->dict) { - for (insert = &(table->table[key]); insert->next != NULL; - insert = insert->next) { - if ((insert->name == name) && - (insert->name2 == name2) && - (insert->name3 == name3)) - return(-1); - len++; - } - if ((insert->name == name) && - (insert->name2 == name2) && - (insert->name3 == name3)) - return(-1); - } else { - for (insert = &(table->table[key]); insert->next != NULL; - insert = insert->next) { - if ((xmlStrEqual(insert->name, name)) && - (xmlStrEqual(insert->name2, name2)) && - (xmlStrEqual(insert->name3, name3))) - return(-1); - len++; - } - if ((xmlStrEqual(insert->name, name)) && - (xmlStrEqual(insert->name2, name2)) && - (xmlStrEqual(insert->name3, name3))) - return(-1); - } - } - - if (insert == NULL) { - entry = &(table->table[key]); - } else { - entry = xmlMalloc(sizeof(xmlHashEntry)); - if (entry == NULL) - return(-1); - } - - if (table->dict != NULL) { - entry->name = (xmlChar *) name; - entry->name2 = (xmlChar *) name2; - entry->name3 = (xmlChar *) name3; - } else { - entry->name = xmlStrdup(name); - entry->name2 = xmlStrdup(name2); - entry->name3 = xmlStrdup(name3); - } - entry->payload = userdata; - entry->next = NULL; - entry->valid = 1; - - - if (insert != NULL) - insert->next = entry; - - table->nbElems++; - - if (len > MAX_HASH_LEN) - xmlHashGrow(table, MAX_HASH_LEN * table->size); - - return(0); -} - -/** - * xmlHashUpdateEntry3: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @name3: a third name of the userdata - * @userdata: a pointer to the userdata - * @f: the deallocator function for replaced item (if any) - * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the tuple (@name, @name2, @name3). Existing entry for this tuple - * will be removed and freed with @f if found. - * - * Returns 0 the addition succeeded and -1 in case of error. - */ -int -xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3, - void *userdata, xmlHashDeallocator f) { - unsigned long key; - xmlHashEntryPtr entry; - xmlHashEntryPtr insert; - - if ((table == NULL) || name == NULL) - return(-1); - - /* - * If using a dict internalize if needed - */ - if (table->dict) { - if (!xmlDictOwns(table->dict, name)) { - name = xmlDictLookup(table->dict, name, -1); - if (name == NULL) - return(-1); - } - if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) { - name2 = xmlDictLookup(table->dict, name2, -1); - if (name2 == NULL) - return(-1); - } - if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) { - name3 = xmlDictLookup(table->dict, name3, -1); - if (name3 == NULL) - return(-1); - } - } - - /* - * Check for duplicate and insertion location. - */ - key = xmlHashComputeKey(table, name, name2, name3); - if (table->table[key].valid == 0) { - insert = NULL; - } else { - if (table ->dict) { - for (insert = &(table->table[key]); insert->next != NULL; - insert = insert->next) { - if ((insert->name == name) && - (insert->name2 == name2) && - (insert->name3 == name3)) { - if (f) - f(insert->payload, insert->name); - insert->payload = userdata; - return(0); - } - } - if ((insert->name == name) && - (insert->name2 == name2) && - (insert->name3 == name3)) { - if (f) - f(insert->payload, insert->name); - insert->payload = userdata; - return(0); - } - } else { - for (insert = &(table->table[key]); insert->next != NULL; - insert = insert->next) { - if ((xmlStrEqual(insert->name, name)) && - (xmlStrEqual(insert->name2, name2)) && - (xmlStrEqual(insert->name3, name3))) { - if (f) - f(insert->payload, insert->name); - insert->payload = userdata; - return(0); - } - } - if ((xmlStrEqual(insert->name, name)) && - (xmlStrEqual(insert->name2, name2)) && - (xmlStrEqual(insert->name3, name3))) { - if (f) - f(insert->payload, insert->name); - insert->payload = userdata; - return(0); - } - } - } - - if (insert == NULL) { - entry = &(table->table[key]); - } else { - entry = xmlMalloc(sizeof(xmlHashEntry)); - if (entry == NULL) - return(-1); - } - - if (table->dict != NULL) { - entry->name = (xmlChar *) name; - entry->name2 = (xmlChar *) name2; - entry->name3 = (xmlChar *) name3; - } else { - entry->name = xmlStrdup(name); - entry->name2 = xmlStrdup(name2); - entry->name3 = xmlStrdup(name3); - } - entry->payload = userdata; - entry->next = NULL; - entry->valid = 1; - table->nbElems++; - - - if (insert != NULL) { - insert->next = entry; - } - return(0); -} - -/** - * xmlHashLookup3: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @name3: a third name of the userdata - * - * Find the userdata specified by the (@name, @name2, @name3) tuple. - * - * Returns the a pointer to the userdata - */ -void * -xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3) { - unsigned long key; - xmlHashEntryPtr entry; - - if (table == NULL) - return(NULL); - if (name == NULL) - return(NULL); - key = xmlHashComputeKey(table, name, name2, name3); - if (table->table[key].valid == 0) - return(NULL); - if (table->dict) { - for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { - if ((entry->name == name) && - (entry->name2 == name2) && - (entry->name3 == name3)) - return(entry->payload); - } - } - for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { - if ((xmlStrEqual(entry->name, name)) && - (xmlStrEqual(entry->name2, name2)) && - (xmlStrEqual(entry->name3, name3))) - return(entry->payload); - } - return(NULL); -} - -/** - * xmlHashQLookup3: - * @table: the hash table - * @prefix: the prefix of the userdata - * @name: the name of the userdata - * @prefix2: the second prefix of the userdata - * @name2: a second name of the userdata - * @prefix3: the third prefix of the userdata - * @name3: a third name of the userdata - * - * Find the userdata specified by the (@name, @name2, @name3) tuple. - * - * Returns the a pointer to the userdata - */ -void * -xmlHashQLookup3(xmlHashTablePtr table, - const xmlChar *prefix, const xmlChar *name, - const xmlChar *prefix2, const xmlChar *name2, - const xmlChar *prefix3, const xmlChar *name3) { - unsigned long key; - xmlHashEntryPtr entry; - - if (table == NULL) - return(NULL); - if (name == NULL) - return(NULL); - key = xmlHashComputeQKey(table, prefix, name, prefix2, - name2, prefix3, name3); - if (table->table[key].valid == 0) - return(NULL); - for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { - if ((xmlStrQEqual(prefix, name, entry->name)) && - (xmlStrQEqual(prefix2, name2, entry->name2)) && - (xmlStrQEqual(prefix3, name3, entry->name3))) - return(entry->payload); - } - return(NULL); -} - -typedef struct { - xmlHashScanner hashscanner; - void *data; -} stubData; - -static void -stubHashScannerFull (void *payload, void *data, const xmlChar *name, - const xmlChar *name2 ATTRIBUTE_UNUSED, - const xmlChar *name3 ATTRIBUTE_UNUSED) { - stubData *stubdata = (stubData *) data; - stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name); -} - -/** - * xmlHashScan: - * @table: the hash table - * @f: the scanner function for items in the hash - * @data: extra data passed to f - * - * Scan the hash @table and applied @f to each value. - */ -void -xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) { - stubData stubdata; - stubdata.data = data; - stubdata.hashscanner = f; - xmlHashScanFull (table, stubHashScannerFull, &stubdata); -} - -/** - * xmlHashScanFull: - * @table: the hash table - * @f: the scanner function for items in the hash - * @data: extra data passed to f - * - * Scan the hash @table and applied @f to each value. - */ -void -xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) { - int i, nb; - xmlHashEntryPtr iter; - xmlHashEntryPtr next; - - if (table == NULL) - return; - if (f == NULL) - return; - - if (table->table) { - for(i = 0; i < table->size; i++) { - if (table->table[i].valid == 0) - continue; - iter = &(table->table[i]); - while (iter) { - next = iter->next; - nb = table->nbElems; - if ((f != NULL) && (iter->payload != NULL)) - f(iter->payload, data, iter->name, - iter->name2, iter->name3); - if (nb != table->nbElems) { - /* table was modified by the callback, be careful */ - if (iter == &(table->table[i])) { - if (table->table[i].valid == 0) - iter = NULL; - if (table->table[i].next != next) - iter = &(table->table[i]); - } else - iter = next; - } else - iter = next; - } - } - } -} - -/** - * xmlHashScan3: - * @table: the hash table - * @name: the name of the userdata or NULL - * @name2: a second name of the userdata or NULL - * @name3: a third name of the userdata or NULL - * @f: the scanner function for items in the hash - * @data: extra data passed to f - * - * Scan the hash @table and applied @f to each value matching - * (@name, @name2, @name3) tuple. If one of the names is null, - * the comparison is considered to match. - */ -void -xmlHashScan3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3, - xmlHashScanner f, void *data) { - xmlHashScanFull3 (table, name, name2, name3, - (xmlHashScannerFull) f, data); -} - -/** - * xmlHashScanFull3: - * @table: the hash table - * @name: the name of the userdata or NULL - * @name2: a second name of the userdata or NULL - * @name3: a third name of the userdata or NULL - * @f: the scanner function for items in the hash - * @data: extra data passed to f - * - * Scan the hash @table and applied @f to each value matching - * (@name, @name2, @name3) tuple. If one of the names is null, - * the comparison is considered to match. - */ -void -xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3, - xmlHashScannerFull f, void *data) { - int i; - xmlHashEntryPtr iter; - xmlHashEntryPtr next; - - if (table == NULL) - return; - if (f == NULL) - return; - - if (table->table) { - for(i = 0; i < table->size; i++) { - if (table->table[i].valid == 0) - continue; - iter = &(table->table[i]); - while (iter) { - next = iter->next; - if (((name == NULL) || (xmlStrEqual(name, iter->name))) && - ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) && - ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) && - (iter->payload != NULL)) { - f(iter->payload, data, iter->name, - iter->name2, iter->name3); - } - iter = next; - } - } - } -} - -/** - * xmlHashCopy: - * @table: the hash table - * @f: the copier function for items in the hash - * - * Scan the hash @table and applied @f to each value. - * - * Returns the new table or NULL in case of error. - */ -xmlHashTablePtr -xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) { - int i; - xmlHashEntryPtr iter; - xmlHashEntryPtr next; - xmlHashTablePtr ret; - - if (table == NULL) - return(NULL); - if (f == NULL) - return(NULL); - - ret = xmlHashCreate(table->size); - if (ret == NULL) - return(NULL); - - if (table->table) { - for(i = 0; i < table->size; i++) { - if (table->table[i].valid == 0) - continue; - iter = &(table->table[i]); - while (iter) { - next = iter->next; - xmlHashAddEntry3(ret, iter->name, iter->name2, - iter->name3, f(iter->payload, iter->name)); - iter = next; - } - } - } - ret->nbElems = table->nbElems; - return(ret); -} - -/** - * xmlHashSize: - * @table: the hash table - * - * Query the number of elements installed in the hash @table. - * - * Returns the number of elements in the hash table or - * -1 in case of error - */ -int -xmlHashSize(xmlHashTablePtr table) { - if (table == NULL) - return(-1); - return(table->nbElems); -} - -/** - * xmlHashRemoveEntry: - * @table: the hash table - * @name: the name of the userdata - * @f: the deallocator function for removed item (if any) - * - * Find the userdata specified by the @name and remove - * it from the hash @table. Existing userdata for this tuple will be removed - * and freed with @f. - * - * Returns 0 if the removal succeeded and -1 in case of error or not found. - */ -int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name, - xmlHashDeallocator f) { - return(xmlHashRemoveEntry3(table, name, NULL, NULL, f)); -} - -/** - * xmlHashRemoveEntry2: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @f: the deallocator function for removed item (if any) - * - * Find the userdata specified by the (@name, @name2) tuple and remove - * it from the hash @table. Existing userdata for this tuple will be removed - * and freed with @f. - * - * Returns 0 if the removal succeeded and -1 in case of error or not found. - */ -int -xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, xmlHashDeallocator f) { - return(xmlHashRemoveEntry3(table, name, name2, NULL, f)); -} - -/** - * xmlHashRemoveEntry3: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @name3: a third name of the userdata - * @f: the deallocator function for removed item (if any) - * - * Find the userdata specified by the (@name, @name2, @name3) tuple and remove - * it from the hash @table. Existing userdata for this tuple will be removed - * and freed with @f. - * - * Returns 0 if the removal succeeded and -1 in case of error or not found. - */ -int -xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) { - unsigned long key; - xmlHashEntryPtr entry; - xmlHashEntryPtr prev = NULL; - - if (table == NULL || name == NULL) - return(-1); - - key = xmlHashComputeKey(table, name, name2, name3); - if (table->table[key].valid == 0) { - return(-1); - } else { - for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { - if (xmlStrEqual(entry->name, name) && - xmlStrEqual(entry->name2, name2) && - xmlStrEqual(entry->name3, name3)) { - if ((f != NULL) && (entry->payload != NULL)) - f(entry->payload, entry->name); - entry->payload = NULL; - if (table->dict == NULL) { - if(entry->name) - xmlFree(entry->name); - if(entry->name2) - xmlFree(entry->name2); - if(entry->name3) - xmlFree(entry->name3); - } - if(prev) { - prev->next = entry->next; - xmlFree(entry); - } else { - if (entry->next == NULL) { - entry->valid = 0; - } else { - entry = entry->next; - memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry)); - xmlFree(entry); - } - } - table->nbElems--; - return(0); - } - prev = entry; - } - return(-1); - } -} - -#define bottom_hash -#include "elfgcchack.h" |