hash.c

Go to the documentation of this file.

/*
 * 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);
}
 
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);
}
 
xmlHashTablePtr
xmlHashCreateDict(int size, xmlDictPtr dict) {
    xmlHashTablePtr hash;
 
    hash = xmlHashCreate(size);
    if (hash != NULL) {
        hash->dict = dict;
        xmlDictReference(dict);
    }
    return(hash);
}
 
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);
}
 
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));
}
 
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);
}
 
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);
}
 
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);
}
 
void
xmlHashDefaultDeallocator(void *entry, const xmlChar *key ATTRIBUTE_UNUSED) {
    xmlFree(entry);
}
 
int
xmlHashAddEntry(xmlHashTablePtr hash, const xmlChar *key, void *payload) {
    return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload, NULL, 0));
}
 
int
xmlHashAddEntry2(xmlHashTablePtr hash, const xmlChar *key,
                 const xmlChar *key2, void *payload) {
    return(xmlHashUpdateInternal(hash, key, key2, NULL, payload, NULL, 0));
}
 
int
xmlHashAddEntry3(xmlHashTablePtr hash, const xmlChar *key,
                 const xmlChar *key2, const xmlChar *key3,
                 void *payload) {
    return(xmlHashUpdateInternal(hash, key, key2, key3, payload, NULL, 0));
}
 
int
xmlHashUpdateEntry(xmlHashTablePtr hash, const xmlChar *key,
                   void *payload, xmlHashDeallocator dealloc) {
    return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload,
                                 dealloc, 1));
}
 
int
xmlHashUpdateEntry2(xmlHashTablePtr hash, const xmlChar *key,
                   const xmlChar *key2, void *payload,
                   xmlHashDeallocator dealloc) {
    return(xmlHashUpdateInternal(hash, key, key2, NULL, payload,
                                 dealloc, 1));
}
 
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));
}
 
void *
xmlHashLookup(xmlHashTablePtr hash, const xmlChar *key) {
    return(xmlHashLookup3(hash, key, NULL, NULL));
}
 
void *
xmlHashLookup2(xmlHashTablePtr hash, const xmlChar *key,
              const xmlChar *key2) {
    return(xmlHashLookup3(hash, key, key2, NULL));
}
 
void *
xmlHashQLookup(xmlHashTablePtr hash, const xmlChar *prefix,
               const xmlChar *name) {
    return(xmlHashQLookup3(hash, prefix, name, NULL, NULL, NULL, NULL));
}
 
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));
}
 
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);
}
 
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);
}
 
void
xmlHashScan(xmlHashTablePtr hash, xmlHashScanner scan, void *data) {
    stubData sdata;
    sdata.data = data;
    sdata.scan = scan;
    xmlHashScanFull(hash, stubHashScannerFull, &sdata);
}
 
void
xmlHashScanFull(xmlHashTablePtr hash, xmlHashScannerFull scan, void *data) {
    const xmlHashEntry *entry, *end;
    xmlHashEntry old;
    unsigned i;
 
    if ((hash == NULL) || (hash->size == 0) || (scan == NULL))
        return;
 
    /*
     * We must handle the case that a scanned entry is removed when executing
     * the callback (xmlCleanSpecialAttr and possibly other places).
     *
     * Find the start of a probe sequence to avoid scanning entries twice if
     * a deletion happens.
     */
    entry = hash->table;
    end = &hash->table[hash->size];
    while (entry->hashValue != 0) {
        if (++entry >= end)
            entry = hash->table;
    }
 
    for (i = 0; i < hash->size; i++) {
        if ((entry->hashValue != 0) && (entry->payload != NULL)) {
            /*
             * Make sure to rescan after a possible deletion.
             */
            do {
                old = *entry;
                scan(entry->payload, data, entry->key, entry->key2, entry->key3);
            } while ((entry->hashValue != 0) &&
                     (entry->payload != NULL) &&
                     ((entry->key != old.key) ||
                      (entry->key2 != old.key2) ||
                      (entry->key3 != old.key3)));
        }
        if (++entry >= end)
            entry = hash->table;
    }
}
 
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);
}
 
void
xmlHashScanFull3(xmlHashTablePtr hash, const xmlChar *key,
                 const xmlChar *key2, const xmlChar *key3,
                 xmlHashScannerFull scan, void *data) {
    const xmlHashEntry *entry, *end;
    xmlHashEntry old;
    unsigned i;
 
    if ((hash == NULL) || (hash->size == 0) || (scan == NULL))
        return;
 
    /*
     * We must handle the case that a scanned entry is removed when executing
     * the callback (xmlCleanSpecialAttr and possibly other places).
     *
     * Find the start of a probe sequence to avoid scanning entries twice if
     * a deletion happens.
     */
    entry = hash->table;
    end = &hash->table[hash->size];
    while (entry->hashValue != 0) {
        if (++entry >= end)
            entry = hash->table;
    }
 
    for (i = 0; i < hash->size; i++) {
        if ((entry->hashValue != 0) && (entry->payload != NULL)) {
            /*
             * Make sure to rescan after a possible deletion.
             */
            do {
                if (((key != NULL) && (strcmp((const char *) key,
                                              (const char *) entry->key) != 0)) ||
                    ((key2 != NULL) && (!xmlFastStrEqual(key2, entry->key2))) ||
                    ((key3 != NULL) && (!xmlFastStrEqual(key3, entry->key3))))
                    break;
                old = *entry;
                scan(entry->payload, data, entry->key, entry->key2, entry->key3);
            } while ((entry->hashValue != 0) &&
                     (entry->payload != NULL) &&
                     ((entry->key != old.key) ||
                      (entry->key2 != old.key2) ||
                      (entry->key3 != old.key3)));
        }
        if (++entry >= end)
            entry = hash->table;
    }
}
 
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);
}
 
int
xmlHashSize(xmlHashTablePtr hash) {
    if (hash == NULL)
        return(-1);
    return(hash->nbElems);
}
 
int xmlHashRemoveEntry(xmlHashTablePtr hash, const xmlChar *key,
                       xmlHashDeallocator dealloc) {
    return(xmlHashRemoveEntry3(hash, key, NULL, NULL, dealloc));
}
 
int
xmlHashRemoveEntry2(xmlHashTablePtr hash, const xmlChar *key,
                    const xmlChar *key2, xmlHashDeallocator dealloc) {
    return(xmlHashRemoveEntry3(hash, key, key2, NULL, dealloc));
}
 
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);
}