e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync/* Copyright (c) 2001, Stanford University
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * All rights reserved
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * See the file LICENSE.txt for information on redistributing this software.
8be5264d31d6a6ec949ff2285764c9af57298b52vboxsyncCRHashIdPool *crAllocHashIdPoolEx( GLuint min, GLuint max )
8be5264d31d6a6ec949ff2285764c9af57298b52vboxsync if (min < CR_HASH_ID_MIN || max > CR_HASH_ID_MAX || min >= max)
8be5264d31d6a6ec949ff2285764c9af57298b52vboxsync pool = (CRHashIdPool *) crCalloc(sizeof(CRHashIdPool));
8be5264d31d6a6ec949ff2285764c9af57298b52vboxsync return crAllocHashIdPoolEx( CR_HASH_ID_MIN, CR_HASH_ID_MAX );
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync RTListForEachSafe(&pool->freeList, i, next, FreeElem, Node)
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsyncstatic void crHashIdPoolDbgCheckConsistency(CRHashIdPool *pool)
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* null is a special case, it is always treated as allocated */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* first ensure entries have correct values */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* now ensure entries do not intersect */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* and that they are sorted */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsyncstatic void crHashIdPoolDbgCheckUsed( const CRHashIdPool *pool, GLuint start, GLuint count, GLboolean fUsed )
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync for (i = 0; i < count; ++i)
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync Assert(!fUsed == !!crHashIdPoolIsIdFree( pool, start + i ));
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync# define CR_HASH_IDPOOL_DBG_CHECK_USED(_p, _start, _count, _used) do { \
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync crHashIdPoolDbgCheckUsed( (_p), (_start), (_count), (_used) ); \
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync } while (0)
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync# define CR_HASH_IDPOOL_DBG_CHECK_CONSISTENCY(_p) do { crHashIdPoolDbgCheckConsistency((_p)); } while (0)
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync# define CR_HASH_IDPOOL_DBG_CHECK_USED(_p, _start, _count, _used) do { } while (0)
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync# define CR_HASH_IDPOOL_DBG_CHECK_CONSISTENCY(_p) do { } while (0)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Allocate a block of <count> IDs. Return index of first one.
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Return 0 if we fail.
e85b92d4df013df97a72864a412eb94eb3f70acevboxsyncGLuint crHashIdPoolAllocBlock( CRHashIdPool *pool, GLuint count )
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync RTListForEachSafe(&pool->freeList, f, next, FreeElem, Node)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* found a sufficiently large enough block */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, ret, count, GL_TRUE);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* failed to find free block */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Free a block of <count> IDs starting at <first>.
e85b92d4df013df97a72864a412eb94eb3f70acevboxsyncvoid crHashIdPoolFreeBlock( CRHashIdPool *pool, GLuint first, GLuint count )
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* null is a special case, it is always treated as allocated */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* the id list is sorted, first find a place to insert */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* we are here because first is > than prevEntry->max
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync * otherwise the previous loop iterations should handle that */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync FreeElem *elem = (FreeElem *) crCalloc(sizeof(FreeElem));
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, first, count, GL_FALSE);
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* now we have f->min <= last and f->max >= first,
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync * so we have either intersection */
4252e037570a3c8d943552edb7858c9889aaca1dvboxsync f->min = first; /* first is guaranteed not to touch any prev regions */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, first, count, GL_FALSE);
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync for (cur = RTListNodeGetNext(&f->Node, FreeElem, Node),
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync curNext = RT_FROM_MEMBER(cur->Node.pNext, FreeElem, Node);
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync !RTListNodeIsDummy(&pool->freeList, cur, FreeElem, Node);
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync curNext = RT_FROM_MEMBER((cur)->Node.pNext, FreeElem, Node) )
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, first, count, GL_FALSE);
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* we are here because either the list is empty or because all list rande elements have smaller values */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, first, count, GL_FALSE);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Mark the given Id as being allocated.
e85b92d4df013df97a72864a412eb94eb3f70acevboxsyncGLboolean crHashIdPoolAllocId( CRHashIdPool *pool, GLuint id )
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* null is a special case, it is always treated as allocated */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync// Assert(id != 2);
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync RTListForEachSafe(&pool->freeList, f, next, FreeElem, Node)
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync /* f->min <= id && f->max > id */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync FreeElem *elem = (FreeElem *) crCalloc(sizeof(FreeElem));
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* if we get here, the ID was already allocated - that's OK */
fc930724d0ba1ec3d2ae3f27c5c019e0e8d828e5vboxsync CR_HASH_IDPOOL_DBG_CHECK_USED(pool, id, 1, GL_TRUE);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Determine if the given id is free. Return GL_TRUE if so.
e85b92d4df013df97a72864a412eb94eb3f70acevboxsyncGLboolean crHashIdPoolIsIdFree( const CRHashIdPool *pool, GLuint id )
bff361262f6f9bda1094fc5f754259b8e0404718vboxsyncvoid crHashIdWalkKeys( CRHashIdPool *pool, CRHashIdWalkKeys walkFunc , void *data)
4252e037570a3c8d943552edb7858c9889aaca1dvboxsync walkFunc(prev->max+1, pool->max - prev->max, data);
8be5264d31d6a6ec949ff2285764c9af57298b52vboxsyncCRHashTable *crAllocHashtableEx( GLuint min, GLuint max )
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync CRHashTable *hash = (CRHashTable *) crCalloc( sizeof( CRHashTable )) ;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (i = 0 ; i < CR_NUM_BUCKETS ; i++)
8be5264d31d6a6ec949ff2285764c9af57298b52vboxsync return crAllocHashtableEx(CR_HASH_ID_MIN, CR_HASH_ID_MAX);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncvoid crFreeHashtable( CRHashTable *hash, CRHashtableCallback deleteFunc )
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if ( !hash) return;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for ( i = 0; i < CR_NUM_BUCKETS; i++ )
a71e6c1227f7f096f49c60514542b47e168c4ea4vboxsync /* Clear the key in case crHashtableDelete() is called
a71e6c1227f7f096f49c60514542b47e168c4ea4vboxsync * from this callback.
bf51ba1739a9eb4abd3bbf2fbeda16c90cdd2c19vboxsyncvoid crHashtableWalkUnlocked( CRHashTable *hash, CRHashtableWalkCallback walkFunc , void *dataPtr2)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (i = 0; i < CR_NUM_BUCKETS; i++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* save next ptr here, in case walkFunc deletes this entry */
bf51ba1739a9eb4abd3bbf2fbeda16c90cdd2c19vboxsyncvoid crHashtableWalk( CRHashTable *hash, CRHashtableWalkCallback walkFunc , void *dataPtr2)
bf51ba1739a9eb4abd3bbf2fbeda16c90cdd2c19vboxsync crHashtableWalkUnlocked(hash, walkFunc , dataPtr2);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncvoid crHashtableAdd( CRHashTable *h, unsigned long key, void *data )
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync CRHashNode *node = (CRHashNode *) crCalloc( sizeof( CRHashNode ) );
ebc248f21b276416f76e20da3add001aff9fc30avboxsyncGLboolean crHashtableAllocRegisterKey( CRHashTable *h, GLuint key)
bff361262f6f9bda1094fc5f754259b8e0404718vboxsyncvoid crHashtableWalkKeys( CRHashTable *h, CRHashIdWalkKeys walkFunc , void *data)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncGLuint crHashtableAllocKeys( CRHashTable *h, GLsizei range)
ebc248f21b276416f76e20da3add001aff9fc30avboxsync for (i = 0; i < range; ++i)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncvoid crHashtableDelete( CRHashTable *h, unsigned long key, CRHashtableCallback deleteFunc )
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for ( temp = h->buckets[index]; temp; temp = temp->next )
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncvoid crHashtableDeleteBlock( CRHashTable *h, unsigned long key, GLsizei range, CRHashtableCallback deleteFunc )
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* XXX optimize someday */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncvoid *crHashtableSearch( const CRHashTable *h, unsigned long key )
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for ( temp = h->buckets[index]; temp; temp = temp->next )
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncvoid crHashtableReplace( CRHashTable *h, unsigned long key, void *data,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for ( temp = h->buckets[index]; temp; temp = temp->next )
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncunsigned int crHashtableNumElements( const CRHashTable *h)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Determine if the given key is used. Return GL_TRUE if so.
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncGLboolean crHashtableIsKeyUsed( const CRHashTable *h, GLuint id )
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync return (GLboolean) !crHashIdPoolIsIdFree( h->idPool, id);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncGLboolean crHashtableGetDataKey(CRHashTable *pHash, void *pData, unsigned long *pKey)