0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc#include "cr_threads.h"

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc#include "cr_hash.h"

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc#include "cr_mem.h"

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc#include "cr_error.h"

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc#define CR_MAXUINT ((GLuint) 0xFFFFFFFF)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc#define CR_NUM_BUCKETS 1047

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxctypedef struct FreeElemRec {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc GLuint min;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc GLuint max;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc struct FreeElemRec *next;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc struct FreeElemRec *prev;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc} FreeElem;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxctypedef struct CRHashIdPoolRec {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc FreeElem *freeList;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc} CRHashIdPool;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxctypedef struct CRHashNode {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc unsigned long key;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc void *data;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc struct CRHashNode *next;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc} CRHashNode;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxcstruct CRHashTable {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc unsigned int num_elements;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc CRHashNode *buckets[CR_NUM_BUCKETS];

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc CRHashIdPool *idPool;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc#ifdef CHROMIUM_THREADSAFE

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc CRmutex mutex;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc#endif

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc};

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

82a2fc4751cef28c0bdc327d02012bf8796083b9James Carlson

82a2fc4751cef28c0bdc327d02012bf8796083b9James Carlsonstatic CRHashIdPool *crAllocHashIdPool( void )

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc{

82a2fc4751cef28c0bdc327d02012bf8796083b9James Carlson CRHashIdPool *pool = (CRHashIdPool *) crCalloc(sizeof(CRHashIdPool));

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc pool->freeList = (FreeElem *) crCalloc(sizeof(FreeElem));

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc pool->freeList->min = 1;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc pool->freeList->max = CR_MAXUINT;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc pool->freeList->next = NULL;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc pool->freeList->prev = NULL;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc return pool;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc}

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxcstatic void crFreeHashIdPool( CRHashIdPool *pool )

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc{

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf FreeElem *i, *next;

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf for (i = pool->freeList; i; i = next)

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf {

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf next = i->next;

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf crFree(i);

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf }

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf crFree(pool);

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf}

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zfstatic GLuint crHashIdPoolAllocBlock( CRHashIdPool *pool, GLuint count )

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc{

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc FreeElem *f;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc GLuint ret;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc CRASSERT(count > 0);

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc f = pool->freeList;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc while (f)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (f->max - f->min + 1 >= (GLuint) count)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* found a sufficiently large enough block */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc ret = f->min;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc f->min += count;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (f->min == f->max)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* remove this block from linked list */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (f == pool->freeList)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* remove from head */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc pool->freeList = pool->freeList->next;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc pool->freeList->prev = NULL;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc else

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* remove from elsewhere */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc f->prev->next = f->next;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc f->next->prev = f->prev;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc crFree(f);

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf

fb91fd8a302dfb13e250bbefb6a3970c2edc3ae3zf#ifdef DEBUG

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* make sure the IDs really are allocated */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc GLuint i;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc for (i = 0; i < count; i++)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc //CRASSERT(crHashIdPoolIsIdUsed(pool, ret + i));

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

a399b7655a1d835aa8606c2b29e4e777baac8635zf }

a399b7655a1d835aa8606c2b29e4e777baac8635zf#endif

a399b7655a1d835aa8606c2b29e4e777baac8635zf

a399b7655a1d835aa8606c2b29e4e777baac8635zf return ret;

a399b7655a1d835aa8606c2b29e4e777baac8635zf }

a399b7655a1d835aa8606c2b29e4e777baac8635zf else {

a399b7655a1d835aa8606c2b29e4e777baac8635zf f = f->next;

a399b7655a1d835aa8606c2b29e4e777baac8635zf }

a399b7655a1d835aa8606c2b29e4e777baac8635zf }

a399b7655a1d835aa8606c2b29e4e777baac8635zf

a399b7655a1d835aa8606c2b29e4e777baac8635zf /* failed to find free block */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc crDebug("crHashIdPoolAllocBlock failed");

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc return 0;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc}

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxcstatic void crHashIdPoolFreeBlock( CRHashIdPool *pool, GLuint first, GLuint count )

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc{

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc FreeElem *i;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc FreeElem *newelem;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

82a2fc4751cef28c0bdc327d02012bf8796083b9James Carlson /*********************************/

82a2fc4751cef28c0bdc327d02012bf8796083b9James Carlson /* Add the name to the freeList */

82a2fc4751cef28c0bdc327d02012bf8796083b9James Carlson /* Find the bracketing sequences */

82a2fc4751cef28c0bdc327d02012bf8796083b9James Carlson

82a2fc4751cef28c0bdc327d02012bf8796083b9James Carlson for (i = pool->freeList; i && i->next && i->next->min < first; i = i->next)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* EMPTY BODY */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* j will always be valid */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (!i) {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc return;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (!i->next && i->max == first) {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc return;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* Case: j:(~,first-1) */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (i->max + 1 == first)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->max += count;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (i->next && i->max+1 >= i->next->min)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* Collapse */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->next->min = i->min;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->next->prev = i->prev;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (i->prev)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->prev->next = i->next;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (i == pool->freeList)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc pool->freeList = i->next;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc crFree(i);

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc return;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* Case: j->next: (first+1, ~) */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (i->next && i->next->min - count == first)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->next->min -= count;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (i->max + 1 >= i->next->min)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* Collapse */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->next->min = i->min;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->next->prev = i->prev;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (i->prev)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->prev->next = i->next;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (i == pool->freeList)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc pool->freeList = i->next;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc crFree(i);

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc return;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* Case: j: (first+1, ~) j->next: null */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (!i->next && i->min - count == first)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->min -= count;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc return;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* allocate a new FreeElem node */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc newelem = (FreeElem *) crCalloc(sizeof(FreeElem));

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc newelem->min = first;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc newelem->max = first + count - 1;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* Case: j: (~,first-(2+)) j->next: (first+(2+), ~) or null */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (first > i->max)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc newelem->prev = i;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc newelem->next = i->next;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (i->next)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->next->prev = newelem;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->next = newelem;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc return;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* Case: j: (first+(2+), ~) */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc /* Can only happen if j = t->freeList! */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (i == pool->freeList && i->min > first)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc newelem->next = i;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc newelem->prev = i->prev;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc i->prev = newelem;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc pool->freeList = newelem;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc return;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc}

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxcstatic void crHashIdPoolAllocId( CRHashIdPool *pool, GLuint id )

239e91abc172c1397b1e94869c5d0e8ab67bfc22hx{

239e91abc172c1397b1e94869c5d0e8ab67bfc22hx FreeElem *f;

239e91abc172c1397b1e94869c5d0e8ab67bfc22hx

239e91abc172c1397b1e94869c5d0e8ab67bfc22hx f = pool->freeList;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc while (f)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (id >= f->min && id <= f->max)

82a2fc4751cef28c0bdc327d02012bf8796083b9James Carlson {

82a2fc4751cef28c0bdc327d02012bf8796083b9James Carlson /* found the block */

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc if (id == f->min)

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc {

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc f->min++;

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc }

0ba2cbe97e0678a691742f98d2532caed0a2c4aaxc else if (id == f->max)

{

f->max--;

}

else

{

/* somewhere in the middle - split the block */

FreeElem *newelem = (FreeElem *) crCalloc(sizeof(FreeElem));

newelem->min = id + 1;

newelem->max = f->max;

f->max = id - 1;

newelem->next = f->next;

if (f->next)

f->next->prev = newelem;

newelem->prev = f;

f->next = newelem;

}

return;

}

f = f->next;

}

/* if we get here, the ID was already allocated - that's OK */

}

static GLboolean crHashIdPoolIsIdFree( const CRHashIdPool *pool, GLuint id )

{

FreeElem *i;

/* First find which region it fits in */

for (i = pool->freeList; i && !(i->min <= id && id <= i->max); i=i->next)

{

/* EMPTY BODY */

}

if (i)

return GL_TRUE;

else

return GL_FALSE;

}

CRHashTable *crAllocHashtable( void )

{

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 = crAllocHashIdPool();

#ifdef CHROMIUM_THREADSAFE

crInitMutex(&hash->mutex);

#endif

return hash;

}

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

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 crHashtableWalk( CRHashTable *hash, CRHashtableWalkCallback walkFunc , void *dataPtr2)

{

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)

{

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

}

}

#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

}

GLuint crHashtableAllocKeys( CRHashTable *h, GLsizei range)

{

GLuint res;

int i;

#ifdef CHROMIUM_THREADSAFE

crLockMutex(&h->mutex);

#endif

res = crHashIdPoolAllocBlock (h->idPool, range);

#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 ) {

#ifdef CHROMIUM_THREADSAFE

crUnlockMutex(&h->mutex);

#endif

return; /* not an error */

}

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;

}

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;

}