OpenGL/util/hash.c

	hash.c revision bff361262f6f9bda1094fc5f754259b8e0404718
/* Copyright (c) 2001, Stanford University
 * All rights reserved
 *
 * See the file LICENSE.txt for information on redistributing this software.
 */

#include "cr_threads.h"
#include "cr_hash.h"
#include "cr_mem.h"
#include "cr_error.h"

#include <iprt/list.h>

#define CR_MAXUINT             ((GLuint) 0xFFFFFFFF)
#define CR_HASH_ID_MIN ((GLuint)1)
#define CR_HASH_ID_MAX CR_MAXUINT

#define CR_NUM_BUCKETS 1047

typedef struct FreeElemRec {
    RTLISTNODE Node;
    GLuint min;
    GLuint max;
} FreeElem;

struct CRHashIdPool {
    RTLISTNODE freeList;
    GLuint min;
    GLuint max;
};

typedef struct CRHashNode {
        unsigned long key;
        void *data;
        struct CRHashNode *next;
} CRHashNode;

struct CRHashTable {
        unsigned int num_elements;
        CRHashNode *buckets[CR_NUM_BUCKETS];
        CRHashIdPool   *idPool;
#ifdef CHROMIUM_THREADSAFE
    CRmutex mutex;
#endif
};


CRHashIdPool *crAllocHashIdPoolEx( GLuint min, GLuint max )
{
    CRHashIdPool *pool;
    FreeElem *elem;
    if (min < CR_HASH_ID_MIN || max > CR_HASH_ID_MAX || min >= max)
    {
        crWarning("invalid min man vals");
        return NULL;
    }
    pool = (CRHashIdPool *) crCalloc(sizeof(CRHashIdPool));
    elem = (FreeElem *) crCalloc(sizeof(FreeElem));
    RTListInit(&pool->freeList);
    elem->min = min;
    elem->max = max;
    RTListAppend(&pool->freeList, &elem->Node);
    pool->min = min;
    pool->max = max;
    return pool;
}

CRHashIdPool *crAllocHashIdPool( void )
{
    return crAllocHashIdPoolEx( CR_HASH_ID_MIN, CR_HASH_ID_MAX );
}

void crFreeHashIdPool( CRHashIdPool *pool )
{
    FreeElem *i, *next;
    RTListForEachSafe(&pool->freeList, i, next, FreeElem, Node)
    {
        crFree(i);
    }

    crFree(pool);
}

#ifdef DEBUG_misha
static void crHashIdPoolDbgCheckConsistency(CRHashIdPool *pool)
{
    FreeElem *i;
    GLuint min = 0;

    /* null is a special case, it is always treated as allocated */
    Assert(!crHashIdPoolIsIdFree(pool, 0));

    /* first ensure entries have correct values */
    RTListForEach(&pool->freeList, i, FreeElem, Node)
    {
        Assert(i->min >= pool->min);
        Assert(i->max <= pool->max);
        Assert(i->min < i->max);
    }

    /* now ensure entries do not intersect */
    /* and that they are sorted */
    RTListForEach(&pool->freeList, i, FreeElem, Node)
    {
        Assert(min < i->min);
        min = i->max;
    }
}

static void crHashIdPoolDbgCheckUsed( const CRHashIdPool *pool, GLuint start, GLuint count, GLboolean fUsed )
{
    GLuint i;
    CRASSERT(count);
    CRASSERT(start >= pool->min);
    CRASSERT(start + count <= pool->max);
    CRASSERT(start + count >  start);
    for (i = 0; i < count; ++i)
    {
        Assert(!fUsed == !!crHashIdPoolIsIdFree( pool, start + i ));
    }
}

# define CR_HASH_IDPOOL_DBG_CHECK_USED(_p, _start, _count, _used) do { \
        crHashIdPoolDbgCheckConsistency((_p)); \
        crHashIdPoolDbgCheckUsed( (_p), (_start), (_count), (_used) ); \
    } while (0)

# define CR_HASH_IDPOOL_DBG_CHECK_CONSISTENCY(_p) do { crHashIdPoolDbgCheckConsistency((_p)); } while (0)
#else
# define CR_HASH_IDPOOL_DBG_CHECK_USED(_p, _start, _count, _used) do { } while (0)
# define CR_HASH_IDPOOL_DBG_CHECK_CONSISTENCY(_p) do { } while (0)
#endif

/*
 * Allocate a block of <count> IDs.  Return index of first one.
 * Return 0 if we fail.
 */
GLuint crHashIdPoolAllocBlock( CRHashIdPool *pool, GLuint count )
{
    FreeElem *f, *next;
    GLuint ret;

    CRASSERT(count > 0);
    RTListForEachSafe(&pool->freeList, f, next, FreeElem, Node)
    {
        Assert(f->max > f->min);
        if (f->max - f->min >= (GLuint) count)
        {
            /* found a sufficiently large enough block */
            ret = f->min;
            f->min += count;
            if (f->min == f->max)
            {
                RTListNodeRemove(&f->Node);
                crFree(f);
            }

            CR_HASH_IDPOOL_DBG_CHECK_USED(pool, ret, count, GL_TRUE);
            return ret;
        }
    }

    /* failed to find free block */
    crWarning("crHashIdPoolAllocBlock failed");
    CR_HASH_IDPOOL_DBG_CHECK_CONSISTENCY(pool);
    return 0;
}


/*
 * Free a block of <count> IDs starting at <first>.
 */
void crHashIdPoolFreeBlock( CRHashIdPool *pool, GLuint first, GLuint count )
{
    FreeElem *f;
    GLuint last;
    GLuint newMax;
    FreeElem *cur, *curNext;

    /* null is a special case, it is always treated as allocated */
    if (!first)
    {
        Assert(!crHashIdPoolIsIdFree(pool, 0));
        ++first;
        --count;
        if (!count)
            return;
    }

    last = first + count;
    CRASSERT(count > 0);
    CRASSERT(last > first);
    CRASSERT(first >= pool->min);
    CRASSERT(last <= pool->max);

    /* the id list is sorted, first find a place to insert */
    RTListForEach(&pool->freeList, f, FreeElem, Node)
    {
        Assert(f->max > f->min);

        if (f->max < first)
            continue;

        if (f->min > last)
        {
            /* we are here because first is > than prevEntry->max
             * otherwise the previous loop iterations should handle that */
            FreeElem *elem = (FreeElem *) crCalloc(sizeof(FreeElem));
            elem->min = first;
            elem->max = last;
            RTListNodeInsertBefore(&f->Node, &elem->Node);
            CR_HASH_IDPOOL_DBG_CHECK_USED(pool, first, count, GL_FALSE);
            return;
        }

        /* now we have f->min <= last and f->max >= first,
         * so we have either intersection */

        if (f->min > first)
            f->min = first; /* first is guarantied not to touch any prev regions */

        newMax = last;

        if (f->max >= last)
        {
            CR_HASH_IDPOOL_DBG_CHECK_USED(pool, first, count, GL_FALSE);
            return;
        }

        for (cur = RTListNodeGetNext(&f->Node, FreeElem, Node),
                curNext = RT_FROM_MEMBER(cur->Node.pNext, FreeElem, Node);
             !RTListNodeIsDummy(&pool->freeList, cur, FreeElem, Node);
             cur = curNext,
                     curNext = RT_FROM_MEMBER((cur)->Node.pNext, FreeElem, Node) )
        {
            if (cur->min > last)
                break;

            newMax = cur->max;
            RTListNodeRemove(&cur->Node);
            crFree(cur);

            if (newMax >= last)
                break;
        }

        f->max = newMax;
        CR_HASH_IDPOOL_DBG_CHECK_USED(pool, first, count, GL_FALSE);
        return;
    }

    /* we are here because either the list is empty or because all list rande elements have smaller values */
    f = (FreeElem *) crCalloc(sizeof(FreeElem));
    f->min = first;
    f->max = last;
    RTListAppend(&pool->freeList, &f->Node);
    CR_HASH_IDPOOL_DBG_CHECK_USED(pool, first, count, GL_FALSE);
}


/*
 * Mark the given Id as being allocated.
 */
GLboolean crHashIdPoolAllocId( CRHashIdPool *pool, GLuint id )
{
    FreeElem *f, *next;

    if (!id)
    {
        /* null is a special case, it is always treated as allocated */
        Assert(!crHashIdPoolIsIdFree(pool, 0));
        return GL_FALSE;
    }

//    Assert(id != 2);

    RTListForEachSafe(&pool->freeList, f, next, FreeElem, Node)
    {
        if (f->max <= id)
            continue;
        if (f->min > id)
        {
            CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
            return GL_FALSE;
        }

        /* f->min <= id && f->max > id */
        if (id > f->min)
        {
            if (id + 1 < f->max)
            {
                FreeElem *elem = (FreeElem *) crCalloc(sizeof(FreeElem));
                elem->min = id + 1;
                elem->max = f->max;
                RTListNodeInsertAfter(&f->Node, &elem->Node);
            }
            f->max = id;

            CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
        }
        else
        {
            Assert(id == f->min);
            if (id + 1 < f->max)
            {
                f->min = id + 1;
                CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
            }
            else
            {
                RTListNodeRemove(&f->Node);
                crFree(f);
                CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
            }
        }

        CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
        return GL_TRUE;
    }

    /* if we get here, the ID was already allocated - that's OK */
    CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
    return GL_FALSE;
}


/*
 * Determine if the given id is free.  Return GL_TRUE if so.
 */
GLboolean crHashIdPoolIsIdFree( const CRHashIdPool *pool, GLuint id )
{
    FreeElem *f;
    CRASSERT(id <= pool->max);

    RTListForEach(&pool->freeList, f, FreeElem, Node)
    {
        if (f->max <= id)
            continue;
        if (f->min > id)
            return GL_FALSE;
        return GL_TRUE;
    }
    return GL_FALSE;
}

void crHashIdWalkKeys( CRHashIdPool *pool, CRHashIdWalkKeys walkFunc , void *data)
{
    FreeElem *prev = NULL, *f;

    RTListForEach(&pool->freeList, f, FreeElem, Node)
    {
        if (prev)
        {
            Assert(prev->max < (f->min - 1));
            walkFunc(prev->max+1, f->min - 1, data);
        }

        prev = f;
    }

    Assert(prev->max <= pool->max);

    if (prev->max < pool->max)
    {
        walkFunc(prev->max+1, pool->max, data);
    }
}

CRHashTable *crAllocHashtableEx( GLuint min, GLuint max )
{
    int i;
    CRHashTable *hash = (CRHashTable *) crCalloc( sizeof( CRHashTable )) ;
    hash->num_elements = 0;
    for (i = 0 ; i < CR_NUM_BUCKETS ; i++)
    {
        hash->buckets[i] = NULL;
    }
    hash->idPool = crAllocHashIdPoolEx( min, max );
#ifdef CHROMIUM_THREADSAFE
    crInitMutex(&hash->mutex);
#endif
    return hash;
}

CRHashTable *crAllocHashtable( void )
{
    return crAllocHashtableEx(CR_HASH_ID_MIN, CR_HASH_ID_MAX);
}

void crFreeHashtable( CRHashTable *hash, CRHashtableCallback deleteFunc )
{
    int i;
    CRHashNode *entry, *next;

    if ( !hash) return;

#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&hash->mutex);
#endif

    for ( i = 0; i < CR_NUM_BUCKETS; i++ )
    {
        entry = hash->buckets[i];
        while (entry)
        {
            next = entry->next;
            /* Clear the key in case crHashtableDelete() is called
             * from this callback.
             */
            entry->key = 0;
            if (deleteFunc && entry->data)
            {
                (*deleteFunc)(entry->data);
            }
            crFree(entry);
            entry = next;

        }
    }
    crFreeHashIdPool( hash->idPool );

#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&hash->mutex);
    crFreeMutex(&hash->mutex);
#endif

    crFree( hash );
}

void crHashtableLock(CRHashTable *h)
{
#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&h->mutex);
#endif
}

void crHashtableUnlock(CRHashTable *h)
{
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&h->mutex);
#endif
}

void crHashtableWalkUnlocked( CRHashTable *hash, CRHashtableWalkCallback walkFunc , void *dataPtr2)
{
    int i;
    CRHashNode *entry, *next;

    for (i = 0; i < CR_NUM_BUCKETS; i++)
    {
        entry = hash->buckets[i];
        while (entry)
        {
            /* save next ptr here, in case walkFunc deletes this entry */
            next = entry->next;
            if (entry->data && walkFunc) {
                (*walkFunc)( entry->key, entry->data, dataPtr2 );
            }
            entry = next;
        }
    }
}

void crHashtableWalk( CRHashTable *hash, CRHashtableWalkCallback walkFunc , void *dataPtr2)
{
    if (!hash)
        return;

#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&hash->mutex);
#endif
    crHashtableWalkUnlocked(hash, walkFunc , dataPtr2);
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&hash->mutex);
#endif
}

static unsigned int crHash( unsigned long key )
{
    return key % CR_NUM_BUCKETS;
}

void crHashtableAdd( CRHashTable *h, unsigned long key, void *data )
{
    CRHashNode *node = (CRHashNode *) crCalloc( sizeof( CRHashNode ) );
#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&h->mutex);
#endif
    node->key = key;
    node->data = data;
    node->next = h->buckets[crHash( key )];
    h->buckets[ crHash( key ) ] = node;
    h->num_elements++;
    crHashIdPoolAllocId (h->idPool, key);
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&h->mutex);
#endif
}

GLboolean crHashtableAllocRegisterKey( CRHashTable *h,  GLuint key)
{
    GLboolean fAllocated;
#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&h->mutex);
#endif
    fAllocated = crHashIdPoolAllocId (h->idPool, key);
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&h->mutex);
#endif
    return fAllocated;
}

void crHashtableWalkKeys( CRHashTable *h, CRHashIdWalkKeys walkFunc , void *data)
{
#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&h->mutex);
#endif
    crHashIdWalkKeys(h->idPool, walkFunc , data);
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&h->mutex);
#endif
}

GLuint crHashtableAllocKeys( CRHashTable *h,  GLsizei range)
{
    GLuint res;
    int i;

#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&h->mutex);
#endif
    res = crHashIdPoolAllocBlock (h->idPool, range);
#ifdef DEBUG_misha
    Assert(res);
    for (i = 0; i < range; ++i)
    {
        void *search = crHashtableSearch( h, res+i );
        Assert(!search);
    }
#endif
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&h->mutex);
#endif
    return res;
}

void crHashtableDelete( CRHashTable *h, unsigned long key, CRHashtableCallback deleteFunc )
{
    unsigned int index = crHash( key );
    CRHashNode *temp, *beftemp = NULL;

#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&h->mutex);
#endif
    for ( temp = h->buckets[index]; temp; temp = temp->next )
    {
        if ( temp->key == key )
            break;
        beftemp = temp;
    }
    if ( temp )
    {
        if ( beftemp )
            beftemp->next = temp->next;
        else
            h->buckets[index] = temp->next;
        h->num_elements--;
        if (temp->data && deleteFunc) {
            (*deleteFunc)( temp->data );
        }

        crFree( temp );
    }

    crHashIdPoolFreeBlock( h->idPool, key, 1 );
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&h->mutex);
#endif
}

void crHashtableDeleteBlock( CRHashTable *h, unsigned long key, GLsizei range, CRHashtableCallback deleteFunc )
{
    /* XXX optimize someday */
    GLuint i;
    for (i = 0; i < (GLuint)range; i++) {
        crHashtableDelete( h, key, deleteFunc );
    }
}

void *crHashtableSearch( const CRHashTable *h, unsigned long key )
{
    unsigned int index = crHash( key );
    CRHashNode *temp;
#ifdef CHROMIUM_THREADSAFE
    crLockMutex((CRmutex *)&h->mutex);
#endif
    for ( temp = h->buckets[index]; temp; temp = temp->next )
    {
        if ( temp->key == key )
            break;
    }
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex((CRmutex *)&h->mutex);
#endif
    if ( !temp )
    {
        return NULL;
    }
    return temp->data;
}

void crHashtableReplace( CRHashTable *h, unsigned long key, void *data,
                         CRHashtableCallback deleteFunc)
{
    unsigned int index = crHash( key );
    CRHashNode *temp;
#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&h->mutex);
#endif
    for ( temp = h->buckets[index]; temp; temp = temp->next )
    {
        if ( temp->key == key )
            break;
    }
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&h->mutex);
#endif
    if ( !temp )
    {
        crHashtableAdd( h, key, data );
        return;
    }
#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&h->mutex);
#endif
    if ( temp->data && deleteFunc )
    {
        (*deleteFunc)( temp->data );
    }
    temp->data = data;
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&h->mutex);
#endif
}

unsigned int crHashtableNumElements( const CRHashTable *h)
{
    if (h)
        return h->num_elements;
    else
        return 0;
}

/*
 * Determine if the given key is used.  Return GL_TRUE if so.
 */
GLboolean crHashtableIsKeyUsed( const CRHashTable *h, GLuint id )
{
    return (GLboolean) !crHashIdPoolIsIdFree( h->idPool, id);
}

GLboolean crHashtableGetDataKey(CRHashTable *pHash, void *pData, unsigned long *pKey)
{
    int i;
    CRHashNode *entry;
    GLboolean rc = GL_FALSE;

    if (!pHash)
        return rc;

#ifdef CHROMIUM_THREADSAFE
    crLockMutex(&pHash->mutex);
#endif
    for (i = 0; i<CR_NUM_BUCKETS && !rc; i++)
    {
        entry = pHash->buckets[i];
        while (entry)
        {
            if (entry->data == pData) {
                if (pKey)
                    *pKey = entry->key;
                rc = GL_TRUE;
                break;
            }
            entry = entry->next;
        }
    }
#ifdef CHROMIUM_THREADSAFE
    crUnlockMutex(&pHash->mutex);
#endif

    return rc;
}