hash.c revision 6da9a3ab01fd6e1c285c7c2a79ac831390e03bb4
/* 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_HASH_ID_MAX CR_MAXUINT
#define CR_NUM_BUCKETS 1047
typedef struct FreeElemRec {
} FreeElem;
struct CRHashIdPool {
};
typedef struct CRHashNode {
unsigned long key;
void *data;
struct CRHashNode *next;
} CRHashNode;
struct CRHashTable {
unsigned int num_elements;
#ifdef CHROMIUM_THREADSAFE
#endif
};
CRHashIdPool *crAllocHashIdPool( void )
{
return pool;
}
{
{
crFree(i);
}
}
#ifdef DEBUG_misha
{
FreeElem *i;
/* null is a special case, it is always treated as allocated */
/* first ensure entries have correct values */
{
}
/* now ensure entries do not intersect */
/* and that they are sorted */
{
}
}
static void crHashIdPoolDbgCheckUsed( const CRHashIdPool *pool, GLuint start, GLuint count, GLboolean fUsed )
{
GLuint i;
for (i = 0; i < count; ++i)
{
}
}
} while (0)
# define CR_HASH_IDPOOL_DBG_CHECK_CONSISTENCY(_p) do { crHashIdPoolDbgCheckConsistency((_p)); } while (0)
#else
# 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.
*/
{
{
{
/* found a sufficiently large enough block */
{
RTListNodeRemove(&f->Node);
crFree(f);
}
return ret;
}
}
/* failed to find free block */
crWarning("crHashIdPoolAllocBlock failed");
return 0;
}
/*
* Free a block of <count> IDs starting at <first>.
*/
{
FreeElem *f;
/* null is a special case, it is always treated as allocated */
if (!first)
{
++first;
--count;
if (!count)
return;
}
/* the id list is sorted, first find a place to insert */
{
continue;
{
/* we are here because first is > than prevEntry->max
* otherwise the previous loop iterations should handle that */
return;
}
/* now we have f->min <= last and f->max >= first,
* so we have either intersection */
{
return;
}
{
break;
break;
}
return;
}
/* we are here because either the list is empty or because all list rande elements have smaller values */
}
/*
* Mark the given Id as being allocated.
*/
{
if (!id)
{
/* null is a special case, it is always treated as allocated */
return GL_FALSE;
}
// Assert(id != 2);
{
continue;
{
return GL_FALSE;
}
/* f->min <= id && f->max > id */
{
{
}
}
else
{
{
}
else
{
RTListNodeRemove(&f->Node);
crFree(f);
}
}
return GL_TRUE;
}
/* 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 *f;
{
continue;
return GL_FALSE;
return GL_TRUE;
}
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;
}