Function xmlHashGrow

ThirdParty/libxml2/vtklibxml2/hash.c:353–409

* 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. */

 * 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);
}