Hash.c

/*
 * Copyright (C) 2008 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * Hash table.  The dominant calls are add and lookup, with removals
 * happening very infrequently.  We use probing, and don't worry much
 * about tombstone removal.
 */
#include "Dalvik.h"

#include <stdlib.h>

/* table load factor, i.e. how full can it get before we resize */
//#define LOAD_NUMER  3       // 75%
//#define LOAD_DENOM  4
#define LOAD_NUMER  5       // 62.5%
#define LOAD_DENOM  8
//#define LOAD_NUMER  1       // 50%
//#define LOAD_DENOM  2

/*
 * Compute the capacity needed for a table to hold "size" elements.
 */
size_t dvmHashSize(size_t size) {
    return (size * LOAD_DENOM) / LOAD_NUMER +1;
}


/*
 * Create and initialize a hash table.
 */
HashTable* dvmHashTableCreate(size_t initialSize, HashFreeFunc freeFunc)
{
    HashTable* pHashTable;

    assert(initialSize > 0);

    pHashTable = (HashTable*) malloc(sizeof(*pHashTable));
    if (pHashTable == NULL)
        return NULL;

    dvmInitMutex(&pHashTable->lock);

    pHashTable->tableSize = dexRoundUpPower2(initialSize);
    pHashTable->numEntries = pHashTable->numDeadEntries = 0;
    pHashTable->freeFunc = freeFunc;
    pHashTable->pEntries =
        (HashEntry*) malloc(pHashTable->tableSize * sizeof(HashEntry));
    if (pHashTable->pEntries == NULL) {
        free(pHashTable);
        return NULL;
    }

    memset(pHashTable->pEntries, 0, pHashTable->tableSize * sizeof(HashEntry));
    return pHashTable;
}

/*
 * Clear out all entries.
 */
void dvmHashTableClear(HashTable* pHashTable)
{
    HashEntry* pEnt;
    int i;

    pEnt = pHashTable->pEntries;
    for (i = 0; i < pHashTable->tableSize; i++, pEnt++) {
        if (pEnt->data == HASH_TOMBSTONE) {
            // nuke entry
            pEnt->data = NULL;
        } else if (pEnt->data != NULL) {
            // call free func then nuke entry
            if (pHashTable->freeFunc != NULL)
                (*pHashTable->freeFunc)(pEnt->data);
            pEnt->data = NULL;
        }
    }

    pHashTable->numEntries = 0;
    pHashTable->numDeadEntries = 0;
}

/*
 * Free the table.
 */
void dvmHashTableFree(HashTable* pHashTable)
{
    if (pHashTable == NULL)
        return;
    dvmHashTableClear(pHashTable);
    free(pHashTable->pEntries);
    free(pHashTable);
}

#ifndef NDEBUG
/*
 * Count up the number of tombstone entries in the hash table.
 */
static int countTombStones(HashTable* pHashTable)
{
    int i, count;

    for (count = i = 0; i < pHashTable->tableSize; i++) {
        if (pHashTable->pEntries[i].data == HASH_TOMBSTONE)
            count++;
    }
    return count;
}
#endif

/*
 * Resize a hash table.  We do this when adding an entry increased the
 * size of the table beyond its comfy limit.
 *
 * This essentially requires re-inserting all elements into the new storage.
 *
 * If multiple threads can access the hash table, the table's lock should
 * have been grabbed before issuing the "lookup+add" call that led to the
 * resize, so we don't have a synchronization problem here.
 */
static bool resizeHash(HashTable* pHashTable, int newSize)
{
    HashEntry* pNewEntries;
    int i;

    assert(countTombStones(pHashTable) == pHashTable->numDeadEntries);
    //LOGI("before: dead=%d\n", pHashTable->numDeadEntries);

    pNewEntries = (HashEntry*) calloc(newSize, sizeof(HashEntry));
    if (pNewEntries == NULL)
        return false;

    for (i = 0; i < pHashTable->tableSize; i++) {
        void* data = pHashTable->pEntries[i].data;
        if (data != NULL && data != HASH_TOMBSTONE) {
            int hashValue = pHashTable->pEntries[i].hashValue;
            int newIdx;

            /* probe for new spot, wrapping around */
            newIdx = hashValue & (newSize-1);
            while (pNewEntries[newIdx].data != NULL)
                newIdx = (newIdx + 1) & (newSize-1);

            pNewEntries[newIdx].hashValue = hashValue;
            pNewEntries[newIdx].data = data;
        }
    }

    free(pHashTable->pEntries);
    pHashTable->pEntries = pNewEntries;
    pHashTable->tableSize = newSize;
    pHashTable->numDeadEntries = 0;

    assert(countTombStones(pHashTable) == 0);
    return true;
}

/*
 * Look up an entry.
 *
 * We probe on collisions, wrapping around the table.
 */
void* dvmHashTableLookup(HashTable* pHashTable, u4 itemHash, void* item,
    HashCompareFunc cmpFunc, bool doAdd)
{
    HashEntry* pEntry;
    HashEntry* pEnd;
    void* result = NULL;

    assert(pHashTable->tableSize > 0);
    assert(item != HASH_TOMBSTONE);
    assert(item != NULL);

    /* jump to the first entry and probe for a match */
    pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)];
    pEnd = &pHashTable->pEntries[pHashTable->tableSize];
    while (pEntry->data != NULL) {
        if (pEntry->data != HASH_TOMBSTONE &&
            pEntry->hashValue == itemHash &&
            (*cmpFunc)(pEntry->data, item) == 0)
        {
            /* match */
            //LOGD("+++ match on entry %d\n", pEntry - pHashTable->pEntries);
            break;
        }

        pEntry++;
        if (pEntry == pEnd) {     /* wrap around to start */
            if (pHashTable->tableSize == 1)
                break;      /* edge case - single-entry table */
            pEntry = pHashTable->pEntries;
        }

        //LOGI("+++ look probing %d...\n", pEntry - pHashTable->pEntries);
    }

    if (pEntry->data == NULL) {
        if (doAdd) {
            pEntry->hashValue = itemHash;
            pEntry->data = item;
            pHashTable->numEntries++;

            /*
             * We've added an entry.  See if this brings us too close to full.
             */
            if ((pHashTable->numEntries+pHashTable->numDeadEntries) * LOAD_DENOM
                > pHashTable->tableSize * LOAD_NUMER)
            {
                if (!resizeHash(pHashTable, pHashTable->tableSize * 2)) {
                    /* don't really have a way to indicate failure */
                    LOGE("Dalvik hash resize failure\n");
                    dvmAbort();
                }
                /* note "pEntry" is now invalid */
            } else {
                //LOGW("okay %d/%d/%d\n",
                //    pHashTable->numEntries, pHashTable->tableSize,
                //    (pHashTable->tableSize * LOAD_NUMER) / LOAD_DENOM);
            }

            /* full table is bad -- search for nonexistent never halts */
            assert(pHashTable->numEntries < pHashTable->tableSize);
            result = item;
        } else {
            assert(result == NULL);
        }
    } else {
        result = pEntry->data;
    }

    return result;
}

/*
 * Remove an entry from the table.
 *
 * Does NOT invoke the "free" function on the item.
 */
bool dvmHashTableRemove(HashTable* pHashTable, u4 itemHash, void* item)
{
    HashEntry* pEntry;
    HashEntry* pEnd;

    assert(pHashTable->tableSize > 0);

    /* jump to the first entry and probe for a match */
    pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)];
    pEnd = &pHashTable->pEntries[pHashTable->tableSize];
    while (pEntry->data != NULL) {
        if (pEntry->data == item) {
            //LOGI("+++ stepping on entry %d\n", pEntry - pHashTable->pEntries);
            pEntry->data = HASH_TOMBSTONE;
            pHashTable->numEntries--;
            pHashTable->numDeadEntries++;
            return true;
        }

        pEntry++;
        if (pEntry == pEnd) {     /* wrap around to start */
            if (pHashTable->tableSize == 1)
                break;      /* edge case - single-entry table */
            pEntry = pHashTable->pEntries;
        }

        //LOGI("+++ del probing %d...\n", pEntry - pHashTable->pEntries);
    }

    return false;
}

/*
 * Scan every entry in the hash table and evaluate it with the specified
 * indirect function call. If the function returns 1, remove the entry from 
 * the table. 
 *
 * Does NOT invoke the "free" function on the item.
 *
 * Returning values other than 0 or 1 will abort the routine.
 */
int dvmHashForeachRemove(HashTable* pHashTable, HashForeachRemoveFunc func)
{
    int i, val;

    for (i = 0; i < pHashTable->tableSize; i++) {
        HashEntry* pEnt = &pHashTable->pEntries[i];

        if (pEnt->data != NULL && pEnt->data != HASH_TOMBSTONE) {
            val = (*func)(pEnt->data);
            if (val == 1) {
                pEnt->data = HASH_TOMBSTONE;
                pHashTable->numEntries--;
                pHashTable->numDeadEntries++;
            }
            else if (val != 0) {
                return val;
            }
        }
    }
    return 0;
}


/*
 * Execute a function on every entry in the hash table.
 *
 * If "func" returns a nonzero value, terminate early and return the value.
 */
int dvmHashForeach(HashTable* pHashTable, HashForeachFunc func, void* arg)
{
    int i, val;

    for (i = 0; i < pHashTable->tableSize; i++) {
        HashEntry* pEnt = &pHashTable->pEntries[i];

        if (pEnt->data != NULL && pEnt->data != HASH_TOMBSTONE) {
            val = (*func)(pEnt->data, arg);
            if (val != 0)
                return val;
        }
    }

    return 0;
}


/*
 * Look up an entry, counting the number of times we have to probe.
 *
 * Returns -1 if the entry wasn't found.
 */
static int countProbes(HashTable* pHashTable, u4 itemHash, const void* item,
    HashCompareFunc cmpFunc)
{
    HashEntry* pEntry;
    HashEntry* pEnd;
    int count = 0;

    assert(pHashTable->tableSize > 0);
    assert(item != HASH_TOMBSTONE);
    assert(item != NULL);

    /* jump to the first entry and probe for a match */
    pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)];
    pEnd = &pHashTable->pEntries[pHashTable->tableSize];
    while (pEntry->data != NULL) {
        if (pEntry->data != HASH_TOMBSTONE &&
            pEntry->hashValue == itemHash &&
            (*cmpFunc)(pEntry->data, item) == 0)
        {
            /* match */
            break;
        }

        pEntry++;
        if (pEntry == pEnd) {     /* wrap around to start */
            if (pHashTable->tableSize == 1)
                break;      /* edge case - single-entry table */
            pEntry = pHashTable->pEntries;
        }

        count++;
    }
    if (pEntry->data == NULL)
        return -1;

    return count;
}

/*
 * Evaluate the amount of probing required for the specified hash table.
 *
 * We do this by running through all entries in the hash table, computing
 * the hash value and then doing a lookup.
 *
 * The caller should lock the table before calling here.
 */
void dvmHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc,
    HashCompareFunc cmpFunc)
{
    int numEntries, minProbe, maxProbe, totalProbe;
    HashIter iter;

    numEntries = maxProbe = totalProbe = 0;
    minProbe = 65536*32767;

    for (dvmHashIterBegin(pHashTable, &iter); !dvmHashIterDone(&iter);
        dvmHashIterNext(&iter))
    {
        const void* data = (const void*)dvmHashIterData(&iter);
        int count;
            
        count = countProbes(pHashTable, (*calcFunc)(data), data, cmpFunc);

        numEntries++;

        if (count < minProbe)
            minProbe = count;
        if (count > maxProbe)
            maxProbe = count;
        totalProbe += count;
    }

    LOGI("Probe: min=%d max=%d, total=%d in %d (%d), avg=%.3f\n",
        minProbe, maxProbe, totalProbe, numEntries, pHashTable->tableSize,
        (float) totalProbe / (float) numEntries);
}