hash.c revision ebc248f21b276416f76e20da3add001aff9fc30a
/* 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"
#define CR_NUM_BUCKETS 1047
typedef struct FreeElemRec {
struct FreeElemRec *next;
struct FreeElemRec *prev;
} FreeElem;
typedef struct CRHashIdPoolRec {
} CRHashIdPool;
typedef struct CRHashNode {
unsigned long key;
void *data;
struct CRHashNode *next;
} CRHashNode;
struct CRHashTable {
unsigned int num_elements;
#ifdef CHROMIUM_THREADSAFE
#endif
};
static CRHashIdPool *crAllocHashIdPool( void )
{
return pool;
}
{
{
crFree(i);
}
}
/*
* Allocate a block of <count> IDs. Return index of first one.
* Return 0 if we fail.
*/
{
FreeElem *f;
while (f)
{
{
/* found a sufficiently large enough block */
{
/* remove this block from linked list */
{
/* remove from head */
}
else
{
/* remove from elsewhere */
}
crFree(f);
}
#ifdef DEBUG
/* make sure the IDs really are allocated */
{
GLuint i;
for (i = 0; i < count; i++)
{
//CRASSERT(crHashIdPoolIsIdUsed(pool, ret + i));
}
}
#endif
return ret;
}
else {
f = f->next;
}
}
/* failed to find free block */
crDebug("crHashIdPoolAllocBlock failed");
return 0;
}
/*
* Free a block of <count> IDs starting at <first>.
*/
{
FreeElem *i;
/*********************************/
/* Add the name to the freeList */
/* Find the bracketing sequences */
{
/* EMPTY BODY */
}
/* j will always be valid */
if (!i) {
return;
}
return;
}
/* Case: j:(~,first-1) */
{
{
/* Collapse */
if (i->prev)
{
}
{
}
crFree(i);
}
return;
}
/* Case: j->next: (first+1, ~) */
{
{
/* Collapse */
if (i->prev)
{
}
{
}
crFree(i);
}
return;
}
/* Case: j: (first+1, ~) j->next: null */
{
return;
}
/* allocate a new FreeElem node */
/* Case: j: (~,first-(2+)) j->next: (first+(2+), ~) or null */
{
if (i->next)
{
}
return;
}
/* Case: j: (first+(2+), ~) */
/* Can only happen if j = t->freeList! */
{
return;
}
}
/*
* Mark the given Id as being allocated.
*/
{
FreeElem *f;
while (f)
{
{
/* found the block */
{
f->min++;
}
{
f->max--;
}
else
{
/* somewhere in the middle - split the block */
if (f->next)
}
return GL_TRUE;
}
f = f->next;
}
/* if we get here, the ID was already allocated - that's OK */
return GL_FALSE;
}
/*
* Determine if the given id is free. Return GL_TRUE if so.
*/
{
FreeElem *i;
/* First find which region it fits in */
{
/* EMPTY BODY */
}
if (i)
return GL_TRUE;
else
return GL_FALSE;
}
CRHashTable *crAllocHashtable( void )
{
int i;
hash->num_elements = 0;
for (i = 0 ; i < CR_NUM_BUCKETS ; i++)
{
}
#ifdef CHROMIUM_THREADSAFE
#endif
return hash;
}
{
int i;
if ( !hash) return;
#ifdef CHROMIUM_THREADSAFE
#endif
for ( i = 0; i < CR_NUM_BUCKETS; i++ )
{
while (entry)
{
/* Clear the key in case crHashtableDelete() is called
* from this callback.
*/
{
}
}
}
#ifdef CHROMIUM_THREADSAFE
#endif
}
void crHashtableLock(CRHashTable *h)
{
#ifdef CHROMIUM_THREADSAFE
crLockMutex(&h->mutex);
#endif
}
void crHashtableUnlock(CRHashTable *h)
{
#ifdef CHROMIUM_THREADSAFE
crUnlockMutex(&h->mutex);
#endif
}
{
int i;
if (!hash)
return;
#ifdef CHROMIUM_THREADSAFE
#endif
for (i = 0; i < CR_NUM_BUCKETS; i++)
{
while (entry)
{
/* save next ptr here, in case walkFunc deletes this entry */
}
}
}
#ifdef CHROMIUM_THREADSAFE
#endif
}
{
return key % CR_NUM_BUCKETS;
}
{
#ifdef CHROMIUM_THREADSAFE
crLockMutex(&h->mutex);
#endif
h->num_elements++;
#ifdef CHROMIUM_THREADSAFE
crUnlockMutex(&h->mutex);
#endif
}
{
#ifdef CHROMIUM_THREADSAFE
crLockMutex(&h->mutex);
#endif
#ifdef CHROMIUM_THREADSAFE
crUnlockMutex(&h->mutex);
#endif
return fAllocated;
}
{
int i;
#ifdef CHROMIUM_THREADSAFE
crLockMutex(&h->mutex);
#endif
#ifdef DEBUG_misha
for (i = 0; i < range; ++i)
{
}
#endif
#ifdef CHROMIUM_THREADSAFE
crUnlockMutex(&h->mutex);
#endif
return res;
}
{
#ifdef CHROMIUM_THREADSAFE
crLockMutex(&h->mutex);
#endif
{
break;
}
if ( !temp ) {
#ifdef CHROMIUM_THREADSAFE
crUnlockMutex(&h->mutex);
#endif
return; /* not an error */
}
if ( beftemp )
else
h->num_elements--;
}
#ifdef CHROMIUM_THREADSAFE
crUnlockMutex(&h->mutex);
#endif
}
void crHashtableDeleteBlock( CRHashTable *h, unsigned long key, GLsizei range, CRHashtableCallback deleteFunc )
{
/* XXX optimize someday */
GLuint i;
}
}
{
#ifdef CHROMIUM_THREADSAFE
#endif
{
break;
}
#ifdef CHROMIUM_THREADSAFE
#endif
if ( !temp )
{
return NULL;
}
}
{
#ifdef CHROMIUM_THREADSAFE
crLockMutex(&h->mutex);
#endif
{
break;
}
#ifdef CHROMIUM_THREADSAFE
crUnlockMutex(&h->mutex);
#endif
if ( !temp )
{
return;
}
#ifdef CHROMIUM_THREADSAFE
crLockMutex(&h->mutex);
#endif
{
}
#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.
*/
{
}
{
int i;
if (!pHash)
return rc;
#ifdef CHROMIUM_THREADSAFE
#endif
for (i = 0; i<CR_NUM_BUCKETS && !rc; i++)
{
while (entry)
{
if (pKey)
break;
}
}
}
#ifdef CHROMIUM_THREADSAFE
#endif
return rc;
}