| /* |
| * hash.c: hash tables |
| * |
| * Hash table with open addressing, linear probing and |
| * Robin Hood reordering. |
| * |
| * See Copyright for the status of this software. |
| */ |
| |
| #define IN_LIBXML |
| #include "libxml.h" |
| |
| #include <string.h> |
| #include <limits.h> |
| |
| #include <libxml/parser.h> |
| #include <libxml/hash.h> |
| #include <libxml/dict.h> |
| #include <libxml/xmlmemory.h> |
| #include <libxml/xmlstring.h> |
| |
| #include "private/dict.h" |
| |
| #ifndef SIZE_MAX |
| #define SIZE_MAX ((size_t) -1) |
| #endif |
| |
| #define MAX_FILL_NUM 7 |
| #define MAX_FILL_DENOM 8 |
| #define MIN_HASH_SIZE 8 |
| #define MAX_HASH_SIZE (1u << 31) |
| |
| /* |
| * A single entry in the hash table |
| */ |
| typedef struct { |
| unsigned hashValue; /* 0 means unoccupied, occupied entries have the |
| * MAX_HASH_SIZE bit set to 1 */ |
| xmlChar *key; |
| xmlChar *key2; /* TODO: Don't allocate possibly empty keys */ |
| xmlChar *key3; |
| void *payload; |
| } xmlHashEntry; |
| |
| /* |
| * The entire hash table |
| */ |
| struct _xmlHashTable { |
| xmlHashEntry *table; |
| unsigned size; /* power of two */ |
| unsigned nbElems; |
| xmlDictPtr dict; |
| unsigned randomSeed; |
| }; |
| |
| static int |
| xmlHashGrow(xmlHashTablePtr hash, unsigned size); |
| |
| ATTRIBUTE_NO_SANITIZE_INTEGER |
| static unsigned |
| xmlHashValue(unsigned seed, const xmlChar *key, const xmlChar *key2, |
| const xmlChar *key3, size_t *lengths) { |
| unsigned h1, h2; |
| size_t i; |
| |
| HASH_INIT(h1, h2, seed); |
| |
| for (i = 0; key[i] != 0; i++) { |
| HASH_UPDATE(h1, h2, key[i]); |
| } |
| if (lengths) |
| lengths[0] = i; |
| |
| HASH_UPDATE(h1, h2, 0); |
| |
| if (key2 != NULL) { |
| for (i = 0; key2[i] != 0; i++) { |
| HASH_UPDATE(h1, h2, key2[i]); |
| } |
| if (lengths) |
| lengths[1] = i; |
| } |
| |
| HASH_UPDATE(h1, h2, 0); |
| |
| if (key3 != NULL) { |
| for (i = 0; key3[i] != 0; i++) { |
| HASH_UPDATE(h1, h2, key3[i]); |
| } |
| if (lengths) |
| lengths[2] = i; |
| } |
| |
| HASH_FINISH(h1, h2); |
| |
| return(h2); |
| } |
| |
| ATTRIBUTE_NO_SANITIZE_INTEGER |
| static unsigned |
| xmlHashQNameValue(unsigned seed, |
| const xmlChar *prefix, const xmlChar *name, |
| const xmlChar *prefix2, const xmlChar *name2, |
| const xmlChar *prefix3, const xmlChar *name3) { |
| unsigned h1, h2, ch; |
| |
| HASH_INIT(h1, h2, seed); |
| |
| if (prefix != NULL) { |
| while ((ch = *prefix++) != 0) { |
| HASH_UPDATE(h1, h2, ch); |
| } |
| HASH_UPDATE(h1, h2, ':'); |
| } |
| if (name != NULL) { |
| while ((ch = *name++) != 0) { |
| HASH_UPDATE(h1, h2, ch); |
| } |
| } |
| HASH_UPDATE(h1, h2, 0); |
| if (prefix2 != NULL) { |
| while ((ch = *prefix2++) != 0) { |
| HASH_UPDATE(h1, h2, ch); |
| } |
| HASH_UPDATE(h1, h2, ':'); |
| } |
| if (name2 != NULL) { |
| while ((ch = *name2++) != 0) { |
| HASH_UPDATE(h1, h2, ch); |
| } |
| } |
| HASH_UPDATE(h1, h2, 0); |
| if (prefix3 != NULL) { |
| while ((ch = *prefix3++) != 0) { |
| HASH_UPDATE(h1, h2, ch); |
| } |
| HASH_UPDATE(h1, h2, ':'); |
| } |
| if (name3 != NULL) { |
| while ((ch = *name3++) != 0) { |
| HASH_UPDATE(h1, h2, ch); |
| } |
| } |
| |
| HASH_FINISH(h1, h2); |
| |
| return(h2); |
| } |
| |
| /** |
| * xmlHashCreate: |
| * @size: initial size of the hash table |
| * |
| * Create a new hash table. Set size to zero if the number of entries |
| * can't be estimated. |
| * |
| * Returns the newly created object, or NULL if a memory allocation failed. |
| */ |
| xmlHashTablePtr |
| xmlHashCreate(int size) { |
| xmlHashTablePtr hash; |
| |
| xmlInitParser(); |
| |
| hash = xmlMalloc(sizeof(*hash)); |
| if (hash == NULL) |
| return(NULL); |
| hash->dict = NULL; |
| hash->size = 0; |
| hash->table = NULL; |
| hash->nbElems = 0; |
| hash->randomSeed = xmlRandom(); |
| #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION |
| hash->randomSeed = 0; |
| #endif |
| |
| /* |
| * Unless a larger size is passed, the backing table is created |
| * lazily with MIN_HASH_SIZE capacity. In practice, there are many |
| * hash tables which are never filled. |
| */ |
| if (size > MIN_HASH_SIZE) { |
| unsigned newSize = MIN_HASH_SIZE * 2; |
| |
| while ((newSize < (unsigned) size) && (newSize < MAX_HASH_SIZE)) |
| newSize *= 2; |
| |
| if (xmlHashGrow(hash, newSize) != 0) { |
| xmlFree(hash); |
| return(NULL); |
| } |
| } |
| |
| return(hash); |
| } |
| |
| /** |
| * xmlHashCreateDict: |
| * @size: the size of the hash table |
| * @dict: a dictionary to use for the hash |
| * |
| * Create a new hash table backed by a dictionary. This can reduce |
| * resource usage considerably if most keys passed to API functions |
| * originate from this dictionary. |
| * |
| * Returns the newly created object, or NULL if a memory allocation failed. |
| */ |
| xmlHashTablePtr |
| xmlHashCreateDict(int size, xmlDictPtr dict) { |
| xmlHashTablePtr hash; |
| |
| hash = xmlHashCreate(size); |
| if (hash != NULL) { |
| hash->dict = dict; |
| xmlDictReference(dict); |
| } |
| return(hash); |
| } |
| |
| /** |
| * xmlHashFree: |
| * @hash: hash table |
| * @dealloc: deallocator function or NULL |
| * |
| * Free the hash and its contents. The payload is deallocated with |
| * @dealloc if provided. |
| */ |
| void |
| xmlHashFree(xmlHashTablePtr hash, xmlHashDeallocator dealloc) { |
| if (hash == NULL) |
| return; |
| |
| if (hash->table) { |
| const xmlHashEntry *end = &hash->table[hash->size]; |
| const xmlHashEntry *entry; |
| |
| for (entry = hash->table; entry < end; entry++) { |
| if (entry->hashValue == 0) |
| continue; |
| if ((dealloc != NULL) && (entry->payload != NULL)) |
| dealloc(entry->payload, entry->key); |
| if (hash->dict == NULL) { |
| if (entry->key) |
| xmlFree(entry->key); |
| if (entry->key2) |
| xmlFree(entry->key2); |
| if (entry->key3) |
| xmlFree(entry->key3); |
| } |
| } |
| |
| xmlFree(hash->table); |
| } |
| |
| if (hash->dict) |
| xmlDictFree(hash->dict); |
| |
| xmlFree(hash); |
| } |
| |
| /** |
| * xmlFastStrEqual: |
| * @s1: string |
| * @s2: string |
| * |
| * Compare two strings for equality, allowing NULL values. |
| */ |
| static int |
| xmlFastStrEqual(const xmlChar *s1, const xmlChar *s2) { |
| if (s1 == NULL) |
| return(s2 == NULL); |
| else |
| return((s2 != NULL) && |
| (strcmp((const char *) s1, (const char *) s2) == 0)); |
| } |
| |
| /** |
| * xmlHashFindEntry: |
| * @hash: hash table, non-NULL, size > 0 |
| * @key: first string key, non-NULL |
| * @key2: second string key |
| * @key3: third string key |
| * @hashValue: valid hash value of keys |
| * @pfound: result of search |
| * |
| * Try to find a matching hash table entry. If an entry was found, set |
| * @found to 1 and return the entry. Otherwise, set @found to 0 and return |
| * the location where a new entry should be inserted. |
| */ |
| ATTRIBUTE_NO_SANITIZE_INTEGER |
| static xmlHashEntry * |
| xmlHashFindEntry(const xmlHashTable *hash, const xmlChar *key, |
| const xmlChar *key2, const xmlChar *key3, |
| unsigned hashValue, int *pfound) { |
| xmlHashEntry *entry; |
| unsigned mask, pos, displ; |
| int found = 0; |
| |
| mask = hash->size - 1; |
| pos = hashValue & mask; |
| entry = &hash->table[pos]; |
| |
| if (entry->hashValue != 0) { |
| /* |
| * Robin hood hashing: abort if the displacement of the entry |
| * is smaller than the displacement of the key we look for. |
| * This also stops at the correct position when inserting. |
| */ |
| displ = 0; |
| hashValue |= MAX_HASH_SIZE; |
| |
| do { |
| if (entry->hashValue == hashValue) { |
| if (hash->dict) { |
| if ((entry->key == key) && |
| (entry->key2 == key2) && |
| (entry->key3 == key3)) { |
| found = 1; |
| break; |
| } |
| } |
| if ((strcmp((const char *) entry->key, |
| (const char *) key) == 0) && |
| (xmlFastStrEqual(entry->key2, key2)) && |
| (xmlFastStrEqual(entry->key3, key3))) { |
| found = 1; |
| break; |
| } |
| } |
| |
| displ++; |
| pos++; |
| entry++; |
| if ((pos & mask) == 0) |
| entry = hash->table; |
| } while ((entry->hashValue != 0) && |
| (((pos - entry->hashValue) & mask) >= displ)); |
| } |
| |
| *pfound = found; |
| return(entry); |
| } |
| |
| /** |
| * xmlHashGrow: |
| * @hash: hash table |
| * @size: new size of the hash table |
| * |
| * Resize the hash table. |
| * |
| * Returns 0 in case of success, -1 if a memory allocation failed. |
| */ |
| static int |
| xmlHashGrow(xmlHashTablePtr hash, unsigned size) { |
| const xmlHashEntry *oldentry, *oldend, *end; |
| xmlHashEntry *table; |
| unsigned oldsize, i; |
| |
| /* Add 0 to avoid spurious -Wtype-limits warning on 64-bit GCC */ |
| if ((size_t) size + 0 > SIZE_MAX / sizeof(table[0])) |
| return(-1); |
| table = xmlMalloc(size * sizeof(table[0])); |
| if (table == NULL) |
| return(-1); |
| memset(table, 0, size * sizeof(table[0])); |
| |
| oldsize = hash->size; |
| if (oldsize == 0) |
| goto done; |
| |
| oldend = &hash->table[oldsize]; |
| end = &table[size]; |
| |
| /* |
| * Robin Hood sorting order is maintained if we |
| * |
| * - compute hash indices with modulo |
| * - resize by an integer factor |
| * - start to copy from the beginning of a probe sequence |
| */ |
| oldentry = hash->table; |
| while (oldentry->hashValue != 0) { |
| if (++oldentry >= oldend) |
| oldentry = hash->table; |
| } |
| |
| for (i = 0; i < oldsize; i++) { |
| if (oldentry->hashValue != 0) { |
| xmlHashEntry *entry = &table[oldentry->hashValue & (size - 1)]; |
| |
| while (entry->hashValue != 0) { |
| if (++entry >= end) |
| entry = table; |
| } |
| *entry = *oldentry; |
| } |
| |
| if (++oldentry >= oldend) |
| oldentry = hash->table; |
| } |
| |
| xmlFree(hash->table); |
| |
| done: |
| hash->table = table; |
| hash->size = size; |
| |
| return(0); |
| } |
| |
| /** |
| * xmlHashUpdateInternal: |
| * @hash: hash table |
| * @key: first string key |
| * @key2: second string key |
| * @key3: third string key |
| * @payload: pointer to the payload |
| * @dealloc: deallocator function for replaced item or NULL |
| * @update: whether existing entries should be updated |
| * |
| * Internal function to add or update hash entries. |
| */ |
| ATTRIBUTE_NO_SANITIZE_INTEGER |
| static int |
| xmlHashUpdateInternal(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2, const xmlChar *key3, |
| void *payload, xmlHashDeallocator dealloc, int update) { |
| xmlChar *copy, *copy2, *copy3; |
| xmlHashEntry *entry = NULL; |
| size_t lengths[3]; |
| unsigned hashValue; |
| int found = 0; |
| |
| if ((hash == NULL) || (key == NULL)) |
| return(-1); |
| |
| /* |
| * Check for an existing entry |
| */ |
| hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, lengths); |
| if (hash->size > 0) |
| entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); |
| if (found) { |
| if (update) { |
| if (dealloc) |
| dealloc(entry->payload, entry->key); |
| entry->payload = payload; |
| return(0); |
| } else { |
| /* |
| * xmlHashAddEntry found an existing entry. |
| * |
| * TODO: We should return a different error code here to |
| * distinguish from malloc failures. |
| */ |
| return(-1); |
| } |
| } |
| |
| /* |
| * Grow the hash table if needed |
| */ |
| if (hash->nbElems + 1 > hash->size / MAX_FILL_DENOM * MAX_FILL_NUM) { |
| unsigned newSize, mask, displ, pos; |
| |
| if (hash->size == 0) { |
| newSize = MIN_HASH_SIZE; |
| } else { |
| /* This guarantees that nbElems < INT_MAX */ |
| if (hash->size >= MAX_HASH_SIZE) |
| return(-1); |
| newSize = hash->size * 2; |
| } |
| if (xmlHashGrow(hash, newSize) != 0) |
| return(-1); |
| |
| /* |
| * Find new entry |
| */ |
| mask = hash->size - 1; |
| displ = 0; |
| pos = hashValue & mask; |
| entry = &hash->table[pos]; |
| |
| if (entry->hashValue != 0) { |
| do { |
| displ++; |
| pos++; |
| entry++; |
| if ((pos & mask) == 0) |
| entry = hash->table; |
| } while ((entry->hashValue != 0) && |
| ((pos - entry->hashValue) & mask) >= displ); |
| } |
| } |
| |
| /* |
| * Copy keys |
| */ |
| if (hash->dict != NULL) { |
| if (xmlDictOwns(hash->dict, key)) { |
| copy = (xmlChar *) key; |
| } else { |
| copy = (xmlChar *) xmlDictLookup(hash->dict, key, -1); |
| if (copy == NULL) |
| return(-1); |
| } |
| |
| if ((key2 == NULL) || (xmlDictOwns(hash->dict, key2))) { |
| copy2 = (xmlChar *) key2; |
| } else { |
| copy2 = (xmlChar *) xmlDictLookup(hash->dict, key2, -1); |
| if (copy2 == NULL) |
| return(-1); |
| } |
| if ((key3 == NULL) || (xmlDictOwns(hash->dict, key3))) { |
| copy3 = (xmlChar *) key3; |
| } else { |
| copy3 = (xmlChar *) xmlDictLookup(hash->dict, key3, -1); |
| if (copy3 == NULL) |
| return(-1); |
| } |
| } else { |
| copy = xmlMalloc(lengths[0] + 1); |
| if (copy == NULL) |
| return(-1); |
| memcpy(copy, key, lengths[0] + 1); |
| |
| if (key2 != NULL) { |
| copy2 = xmlMalloc(lengths[1] + 1); |
| if (copy2 == NULL) { |
| xmlFree(copy); |
| return(-1); |
| } |
| memcpy(copy2, key2, lengths[1] + 1); |
| } else { |
| copy2 = NULL; |
| } |
| |
| if (key3 != NULL) { |
| copy3 = xmlMalloc(lengths[2] + 1); |
| if (copy3 == NULL) { |
| xmlFree(copy); |
| xmlFree(copy2); |
| return(-1); |
| } |
| memcpy(copy3, key3, lengths[2] + 1); |
| } else { |
| copy3 = NULL; |
| } |
| } |
| |
| /* |
| * Shift the remainder of the probe sequence to the right |
| */ |
| if (entry->hashValue != 0) { |
| const xmlHashEntry *end = &hash->table[hash->size]; |
| const xmlHashEntry *cur = entry; |
| |
| do { |
| cur++; |
| if (cur >= end) |
| cur = hash->table; |
| } while (cur->hashValue != 0); |
| |
| if (cur < entry) { |
| /* |
| * If we traversed the end of the buffer, handle the part |
| * at the start of the buffer. |
| */ |
| memmove(&hash->table[1], hash->table, |
| (char *) cur - (char *) hash->table); |
| cur = end - 1; |
| hash->table[0] = *cur; |
| } |
| |
| memmove(&entry[1], entry, (char *) cur - (char *) entry); |
| } |
| |
| /* |
| * Populate entry |
| */ |
| entry->key = copy; |
| entry->key2 = copy2; |
| entry->key3 = copy3; |
| entry->payload = payload; |
| /* OR with MAX_HASH_SIZE to make sure that the value is non-zero */ |
| entry->hashValue = hashValue | MAX_HASH_SIZE; |
| |
| hash->nbElems++; |
| |
| return(0); |
| } |
| |
| /** |
| * xmlHashDefaultDeallocator: |
| * @entry: hash table entry |
| * @key: the entry's string key |
| * |
| * Free a hash table entry with xmlFree. |
| */ |
| void |
| xmlHashDefaultDeallocator(void *entry, const xmlChar *key ATTRIBUTE_UNUSED) { |
| xmlFree(entry); |
| } |
| |
| /** |
| * xmlHashAddEntry: |
| * @hash: hash table |
| * @key: string key |
| * @payload: pointer to the payload |
| * |
| * Add a hash table entry. If an entry with this key already exists, |
| * payload will not be updated and -1 is returned. This return value |
| * can't be distinguished from out-of-memory errors, so this function |
| * should be used with care. |
| * |
| * Returns 0 on success and -1 in case of error. |
| */ |
| int |
| xmlHashAddEntry(xmlHashTablePtr hash, const xmlChar *key, void *payload) { |
| return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload, NULL, 0)); |
| } |
| |
| /** |
| * xmlHashAddEntry2: |
| * @hash: hash table |
| * @key: first string key |
| * @key2: second string key |
| * @payload: pointer to the payload |
| * |
| * Add a hash table entry with two strings as key. |
| * |
| * See xmlHashAddEntry. |
| * |
| * Returns 0 on success and -1 in case of error. |
| */ |
| int |
| xmlHashAddEntry2(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2, void *payload) { |
| return(xmlHashUpdateInternal(hash, key, key2, NULL, payload, NULL, 0)); |
| } |
| |
| /** |
| * xmlHashAddEntry3: |
| * @hash: hash table |
| * @key: first string key |
| * @key2: second string key |
| * @key3: third string key |
| * @payload: pointer to the payload |
| * |
| * Add a hash table entry with three strings as key. |
| * |
| * See xmlHashAddEntry. |
| * |
| * Returns 0 on success and -1 in case of error. |
| */ |
| int |
| xmlHashAddEntry3(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2, const xmlChar *key3, |
| void *payload) { |
| return(xmlHashUpdateInternal(hash, key, key2, key3, payload, NULL, 0)); |
| } |
| |
| /** |
| * xmlHashUpdateEntry: |
| * @hash: hash table |
| * @key: string key |
| * @payload: pointer to the payload |
| * @dealloc: deallocator function for replaced item or NULL |
| * |
| * Add a hash table entry. If an entry with this key already exists, |
| * the old payload will be freed and updated with the new value. |
| * |
| * Returns 0 in case of success, -1 if a memory allocation failed. |
| */ |
| int |
| xmlHashUpdateEntry(xmlHashTablePtr hash, const xmlChar *key, |
| void *payload, xmlHashDeallocator dealloc) { |
| return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload, |
| dealloc, 1)); |
| } |
| |
| /** |
| * xmlHashUpdateEntry2: |
| * @hash: hash table |
| * @key: first string key |
| * @key2: second string key |
| * @payload: pointer to the payload |
| * @dealloc: deallocator function for replaced item or NULL |
| * |
| * Add a hash table entry with two strings as key. |
| * |
| * See xmlHashUpdateEntry. |
| * |
| * Returns 0 on success and -1 in case of error. |
| */ |
| int |
| xmlHashUpdateEntry2(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2, void *payload, |
| xmlHashDeallocator dealloc) { |
| return(xmlHashUpdateInternal(hash, key, key2, NULL, payload, |
| dealloc, 1)); |
| } |
| |
| /** |
| * xmlHashUpdateEntry3: |
| * @hash: hash table |
| * @key: first string key |
| * @key2: second string key |
| * @key3: third string key |
| * @payload: pointer to the payload |
| * @dealloc: deallocator function for replaced item or NULL |
| * |
| * Add a hash table entry with three strings as key. |
| * |
| * See xmlHashUpdateEntry. |
| * |
| * Returns 0 on success and -1 in case of error. |
| */ |
| int |
| xmlHashUpdateEntry3(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2, const xmlChar *key3, |
| void *payload, xmlHashDeallocator dealloc) { |
| return(xmlHashUpdateInternal(hash, key, key2, key3, payload, |
| dealloc, 1)); |
| } |
| |
| /** |
| * xmlHashLookup: |
| * @hash: hash table |
| * @key: string key |
| * |
| * Find the entry specified by @key. |
| * |
| * Returns a pointer to the payload or NULL if no entry was found. |
| */ |
| void * |
| xmlHashLookup(xmlHashTablePtr hash, const xmlChar *key) { |
| return(xmlHashLookup3(hash, key, NULL, NULL)); |
| } |
| |
| /** |
| * xmlHashLookup2: |
| * @hash: hash table |
| * @key: first string key |
| * @key2: second string key |
| * |
| * Find the payload specified by the (@key, @key2) tuple. |
| * |
| * Returns a pointer to the payload or NULL if no entry was found. |
| */ |
| void * |
| xmlHashLookup2(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2) { |
| return(xmlHashLookup3(hash, key, key2, NULL)); |
| } |
| |
| /** |
| * xmlHashQLookup: |
| * @hash: hash table |
| * @prefix: prefix of the string key |
| * @name: local name of the string key |
| * |
| * Find the payload specified by the QName @prefix:@name or @name. |
| * |
| * Returns a pointer to the payload or NULL if no entry was found. |
| */ |
| void * |
| xmlHashQLookup(xmlHashTablePtr hash, const xmlChar *prefix, |
| const xmlChar *name) { |
| return(xmlHashQLookup3(hash, prefix, name, NULL, NULL, NULL, NULL)); |
| } |
| |
| /** |
| * xmlHashQLookup2: |
| * @hash: hash table |
| * @prefix: first prefix |
| * @name: first local name |
| * @prefix2: second prefix |
| * @name2: second local name |
| * |
| * Find the payload specified by the QNames tuple. |
| * |
| * Returns a pointer to the payload or NULL if no entry was found. |
| */ |
| void * |
| xmlHashQLookup2(xmlHashTablePtr hash, const xmlChar *prefix, |
| const xmlChar *name, const xmlChar *prefix2, |
| const xmlChar *name2) { |
| return(xmlHashQLookup3(hash, prefix, name, prefix2, name2, NULL, NULL)); |
| } |
| |
| /** |
| * xmlHashLookup3: |
| * @hash: hash table |
| * @key: first string key |
| * @key2: second string key |
| * @key3: third string key |
| * |
| * Find the payload specified by the (@key, @key2, @key3) tuple. |
| * |
| * Returns a pointer to the payload or NULL if no entry was found. |
| */ |
| void * |
| xmlHashLookup3(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2, const xmlChar *key3) { |
| const xmlHashEntry *entry; |
| unsigned hashValue; |
| int found; |
| |
| if ((hash == NULL) || (hash->size == 0) || (key == NULL)) |
| return(NULL); |
| hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, NULL); |
| entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); |
| if (found) |
| return(entry->payload); |
| return(NULL); |
| } |
| |
| /** |
| * xmlHashQLookup3: |
| * @hash: hash table |
| * @prefix: first prefix |
| * @name: first local name |
| * @prefix2: second prefix |
| * @name2: second local name |
| * @prefix3: third prefix |
| * @name3: third local name |
| * |
| * Find the payload specified by the QNames tuple. |
| * |
| * Returns a pointer to the payload or NULL if no entry was found. |
| */ |
| ATTRIBUTE_NO_SANITIZE_INTEGER |
| void * |
| xmlHashQLookup3(xmlHashTablePtr hash, |
| const xmlChar *prefix, const xmlChar *name, |
| const xmlChar *prefix2, const xmlChar *name2, |
| const xmlChar *prefix3, const xmlChar *name3) { |
| const xmlHashEntry *entry; |
| unsigned hashValue, mask, pos, displ; |
| |
| if ((hash == NULL) || (hash->size == 0) || (name == NULL)) |
| return(NULL); |
| |
| hashValue = xmlHashQNameValue(hash->randomSeed, prefix, name, prefix2, |
| name2, prefix3, name3); |
| mask = hash->size - 1; |
| pos = hashValue & mask; |
| entry = &hash->table[pos]; |
| |
| if (entry->hashValue != 0) { |
| displ = 0; |
| hashValue |= MAX_HASH_SIZE; |
| |
| do { |
| if ((hashValue == entry->hashValue) && |
| (xmlStrQEqual(prefix, name, entry->key)) && |
| (xmlStrQEqual(prefix2, name2, entry->key2)) && |
| (xmlStrQEqual(prefix3, name3, entry->key3))) |
| return(entry->payload); |
| |
| displ++; |
| pos++; |
| entry++; |
| if ((pos & mask) == 0) |
| entry = hash->table; |
| } while ((entry->hashValue != 0) && |
| (((pos - entry->hashValue) & mask) >= displ)); |
| } |
| |
| return(NULL); |
| } |
| |
| typedef struct { |
| xmlHashScanner scan; |
| void *data; |
| } stubData; |
| |
| static void |
| stubHashScannerFull(void *payload, void *data, const xmlChar *key, |
| const xmlChar *key2 ATTRIBUTE_UNUSED, |
| const xmlChar *key3 ATTRIBUTE_UNUSED) { |
| stubData *sdata = (stubData *) data; |
| sdata->scan(payload, sdata->data, key); |
| } |
| |
| /** |
| * xmlHashScan: |
| * @hash: hash table |
| * @scan: scanner function for items in the hash |
| * @data: extra data passed to @scan |
| * |
| * Scan the hash @table and apply @scan to each value. |
| */ |
| void |
| xmlHashScan(xmlHashTablePtr hash, xmlHashScanner scan, void *data) { |
| stubData sdata; |
| sdata.data = data; |
| sdata.scan = scan; |
| xmlHashScanFull(hash, stubHashScannerFull, &sdata); |
| } |
| |
| /** |
| * xmlHashScanFull: |
| * @hash: hash table |
| * @scan: scanner function for items in the hash |
| * @data: extra data passed to @scan |
| * |
| * Scan the hash @table and apply @scan to each value. |
| */ |
| void |
| xmlHashScanFull(xmlHashTablePtr hash, xmlHashScannerFull scan, void *data) { |
| const xmlHashEntry *entry, *end; |
| |
| if ((hash == NULL) || (hash->size == 0) || (scan == NULL)) |
| return; |
| |
| end = &hash->table[hash->size]; |
| |
| for (entry = hash->table; entry < end; entry++) { |
| if ((entry->hashValue != 0) && (entry->payload != NULL)) |
| scan(entry->payload, data, entry->key, entry->key2, entry->key3); |
| } |
| } |
| |
| /** |
| * xmlHashScan3: |
| * @hash: hash table |
| * @key: first string key or NULL |
| * @key2: second string key or NULL |
| * @key3: third string key or NULL |
| * @scan: scanner function for items in the hash |
| * @data: extra data passed to @scan |
| * |
| * Scan the hash @table and apply @scan to each value matching |
| * (@key, @key2, @key3) tuple. If one of the keys is null, |
| * the comparison is considered to match. |
| */ |
| void |
| xmlHashScan3(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2, const xmlChar *key3, |
| xmlHashScanner scan, void *data) { |
| stubData sdata; |
| sdata.data = data; |
| sdata.scan = scan; |
| xmlHashScanFull3(hash, key, key2, key3, stubHashScannerFull, &sdata); |
| } |
| |
| /** |
| * xmlHashScanFull3: |
| * @hash: hash table |
| * @key: first string key or NULL |
| * @key2: second string key or NULL |
| * @key3: third string key or NULL |
| * @scan: scanner function for items in the hash |
| * @data: extra data passed to @scan |
| * |
| * Scan the hash @table and apply @scan to each value matching |
| * (@key, @key2, @key3) tuple. If one of the keys is null, |
| * the comparison is considered to match. |
| */ |
| void |
| xmlHashScanFull3(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2, const xmlChar *key3, |
| xmlHashScannerFull scan, void *data) { |
| const xmlHashEntry *entry, *end; |
| |
| if ((hash == NULL) || (hash->size == 0) || (scan == NULL)) |
| return; |
| |
| end = &hash->table[hash->size]; |
| |
| for (entry = hash->table; entry < end; entry++) { |
| if (entry->hashValue == 0) |
| continue; |
| if (((key == NULL) || |
| (strcmp((const char *) key, (const char *) entry->key) == 0)) && |
| ((key2 == NULL) || (xmlFastStrEqual(key2, entry->key2))) && |
| ((key3 == NULL) || (xmlFastStrEqual(key3, entry->key3))) && |
| (entry->payload != NULL)) { |
| scan(entry->payload, data, entry->key, entry->key2, entry->key3); |
| } |
| } |
| } |
| |
| /** |
| * xmlHashCopy: |
| * @hash: hash table |
| * @copy: copier function for items in the hash |
| * |
| * Copy the hash @table using @copy to copy payloads. |
| * |
| * Returns the new table or NULL if a memory allocation failed. |
| */ |
| xmlHashTablePtr |
| xmlHashCopy(xmlHashTablePtr hash, xmlHashCopier copy) { |
| const xmlHashEntry *entry, *end; |
| xmlHashTablePtr ret; |
| |
| if ((hash == NULL) || (copy == NULL)) |
| return(NULL); |
| |
| ret = xmlHashCreate(hash->size); |
| if (ret == NULL) |
| return(NULL); |
| |
| if (hash->size == 0) |
| return(ret); |
| |
| end = &hash->table[hash->size]; |
| |
| for (entry = hash->table; entry < end; entry++) { |
| if (entry->hashValue != 0) |
| xmlHashAddEntry3(ret, entry->key, entry->key2, entry->key3, |
| copy(entry->payload, entry->key)); |
| } |
| |
| return(ret); |
| } |
| |
| /** |
| * xmlHashSize: |
| * @hash: hash table |
| * |
| * Query the number of elements in the hash table. |
| * |
| * Returns the number of elements in the hash table or |
| * -1 in case of error. |
| */ |
| int |
| xmlHashSize(xmlHashTablePtr hash) { |
| if (hash == NULL) |
| return(-1); |
| return(hash->nbElems); |
| } |
| |
| /** |
| * xmlHashRemoveEntry: |
| * @hash: hash table |
| * @key: string key |
| * @dealloc: deallocator function for removed item or NULL |
| * |
| * Find the entry specified by the @key and remove it from the hash table. |
| * Payload will be freed with @dealloc. |
| * |
| * Returns 0 on success and -1 if no entry was found. |
| */ |
| int xmlHashRemoveEntry(xmlHashTablePtr hash, const xmlChar *key, |
| xmlHashDeallocator dealloc) { |
| return(xmlHashRemoveEntry3(hash, key, NULL, NULL, dealloc)); |
| } |
| |
| /** |
| * xmlHashRemoveEntry2: |
| * @hash: hash table |
| * @key: first string key |
| * @key2: second string key |
| * @dealloc: deallocator function for removed item or NULL |
| * |
| * Remove an entry with two strings as key. |
| * |
| * See xmlHashRemoveEntry. |
| * |
| * Returns 0 on success and -1 in case of error. |
| */ |
| int |
| xmlHashRemoveEntry2(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2, xmlHashDeallocator dealloc) { |
| return(xmlHashRemoveEntry3(hash, key, key2, NULL, dealloc)); |
| } |
| |
| /** |
| * xmlHashRemoveEntry3: |
| * @hash: hash table |
| * @key: first string key |
| * @key2: second string key |
| * @key3: third string key |
| * @dealloc: deallocator function for removed item or NULL |
| * |
| * Remove an entry with three strings as key. |
| * |
| * See xmlHashRemoveEntry. |
| * |
| * Returns 0 on success and -1 in case of error. |
| */ |
| ATTRIBUTE_NO_SANITIZE_INTEGER |
| int |
| xmlHashRemoveEntry3(xmlHashTablePtr hash, const xmlChar *key, |
| const xmlChar *key2, const xmlChar *key3, |
| xmlHashDeallocator dealloc) { |
| xmlHashEntry *entry, *cur, *next; |
| unsigned hashValue, mask, pos, nextpos; |
| int found; |
| |
| if ((hash == NULL) || (hash->size == 0) || (key == NULL)) |
| return(-1); |
| |
| hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, NULL); |
| entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); |
| if (!found) |
| return(-1); |
| |
| if ((dealloc != NULL) && (entry->payload != NULL)) |
| dealloc(entry->payload, entry->key); |
| if (hash->dict == NULL) { |
| if (entry->key) |
| xmlFree(entry->key); |
| if (entry->key2) |
| xmlFree(entry->key2); |
| if (entry->key3) |
| xmlFree(entry->key3); |
| } |
| |
| /* |
| * Find end of probe sequence. Entries at their initial probe |
| * position start a new sequence. |
| */ |
| mask = hash->size - 1; |
| pos = entry - hash->table; |
| cur = entry; |
| |
| while (1) { |
| nextpos = pos + 1; |
| next = cur + 1; |
| if ((nextpos & mask) == 0) |
| next = hash->table; |
| |
| if ((next->hashValue == 0) || |
| (((next->hashValue - nextpos) & mask) == 0)) |
| break; |
| |
| cur = next; |
| pos = nextpos; |
| } |
| |
| /* |
| * Backward shift |
| */ |
| next = entry + 1; |
| |
| if (cur < entry) { |
| xmlHashEntry *end = &hash->table[hash->size]; |
| |
| memmove(entry, next, (char *) end - (char *) next); |
| entry = hash->table; |
| end[-1] = *entry; |
| next = entry + 1; |
| } |
| |
| memmove(entry, next, (char *) cur - (char *) entry); |
| |
| /* |
| * Update entry |
| */ |
| cur->hashValue = 0; |
| |
| hash->nbElems--; |
| |
| return(0); |
| } |
| |