summaryrefslogtreecommitdiffstats
path: root/libxml2/hash.c
diff options
context:
space:
mode:
authorWilliam Joye <wjoye@cfa.harvard.edu>2016-11-17 21:09:46 (GMT)
committerWilliam Joye <wjoye@cfa.harvard.edu>2016-11-17 21:09:46 (GMT)
commitfc7f7edd0b8011cb71573b15462ef83068d9e54b (patch)
tree459fb7d1a9611f563e3000386df5cb7cdf506916 /libxml2/hash.c
parent4f65b25b474bf534e40c3d3aa47d43e8457fcc9a (diff)
downloadblt-fc7f7edd0b8011cb71573b15462ef83068d9e54b.zip
blt-fc7f7edd0b8011cb71573b15462ef83068d9e54b.tar.gz
blt-fc7f7edd0b8011cb71573b15462ef83068d9e54b.tar.bz2
local fork libxml2
Diffstat (limited to 'libxml2/hash.c')
-rw-r--r--libxml2/hash.c1124
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"