--- /dev/null
+/* *****************************************************************************
+ * Copyright (c) 2007-2015 Alexis Naveros.
+ *
+ * Ecere Corporation has unlimited/unrestricted rights.
+ * *****************************************************************************/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+#include <math.h>
+
+#include "cpuconfig.h"
+#include "cc.h"
+#include "mm.h"
+#include "mmhash.h"
+
+
+////
+
+
+#include "mmhashinternal.h"
+
+
+////
+
+
+
+static void mmHashSetBounds( mmHashTable *table )
+{
+ table->lowcount = 0;
+ if( table->hashbits > table->minhashbits )
+ table->lowcount = table->hashsize / 5;
+ table->highcount = table->hashsize / 2;
+ return;
+}
+
+
+size_t mmHashRequiredSize( size_t entrysize, uint32_t hashbits, uint32_t pageshift )
+{
+ uint32_t entrycount;
+ uint32_t pagecount;
+ entrycount = 1 << hashbits;
+ pagecount = entrycount >> pageshift;
+ if( !( pagecount ) )
+ pagecount = 1;
+ return MM_HASH_ALIGN64( MM_HASH_SIZEOF_ALIGN16(mmHashTable) + ( entrycount * entrysize ) ) + ( pagecount * sizeof(mmHashPage) );
+}
+
+
+void mmHashInit( void *hashtable, mmHashAccess *access, size_t entrysize, uint32_t hashbits, uint32_t pageshift, uint32_t flags )
+{
+ uint32_t hashkey, pageindex;
+ void *entry;
+ mmHashTable *table;
+ mmHashPage *page;
+
+ table = hashtable;
+ table->status = MM_HASH_STATUS_NORMAL;
+ if( flags & MM_HASH_FLAGS_NO_COUNT )
+ table->status = MM_HASH_STATUS_UNKNOWN;
+ table->flags = flags;
+ table->entrysize = entrysize;
+ table->minhashbits = hashbits;
+ table->hashbits = hashbits;
+ table->hashsize = 1 << table->hashbits;
+ table->hashmask = table->hashsize - 1;
+ table->pageshift = pageshift;
+ table->pagecount = table->hashsize >> pageshift;
+ if( !( table->pagecount ) )
+ table->pagecount = 1;
+ table->pagemask = table->pagecount - 1;
+ table->page = MM_HASH_PAGELIST( table );
+#ifdef MM_ATOMIC_SUPPORT
+ mmAtomicWrite32( &table->entrycount, 0 );
+#else
+ mtMutexInit( &table->countmutex );
+ table->entrycount = 0;
+#endif
+ mmHashSetBounds( table );
+
+ /* Clear the table */
+ entry = MM_HASH_ENTRYLIST( table );
+ for( hashkey = 0 ; hashkey < table->hashsize ; hashkey++ )
+ {
+ access->clearentry( entry );
+ entry = ADDRESS( entry, entrysize );
+ }
+
+ /* Clear the lock pages */
+ page = table->page;
+#ifdef MM_ATOMIC_SUPPORT
+ for( pageindex = table->pagecount ; pageindex ; pageindex--, page++ )
+ {
+ mmAtomicLockInit32( &page->lock );
+ mmAtomicWriteP( &page->owner, 0 );
+ }
+ mmAtomicWrite32( &table->globallock, 0x0 );
+#else
+ for( pageindex = table->pagecount ; pageindex ; pageindex--, page++ )
+ {
+ mtMutexInit( &page->mutex );
+ page->owner = 0;
+ }
+ mtMutexInit( &table->globalmutex );
+#endif
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ table->entrycountmax = 0;
+ mmAtomicWriteL( &table->statentrycount, 0 );
+ mmAtomicWriteL( &table->accesscount, 0 );
+ mmAtomicWriteL( &table->collisioncount, 0 );
+ mmAtomicWriteL( &table->relocationcount, 0 );
+#endif
+
+ return;
+}
+
+
+int mmHashGetStatus( void *hashtable, int *rethashbits )
+{
+ mmHashTable *table;
+ table = hashtable;
+ if( rethashbits )
+ *rethashbits = table->hashbits;
+ return table->status;
+}
+
+
+
+////
+
+
+
+void *mmHashDirectFindEntry( void *hashtable, mmHashAccess *access, void *findentry )
+{
+ int cmpvalue;
+ uint32_t hashkey;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( findentry ) & table->hashmask;
+
+ /* Search the entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, findentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ return entry;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ return 0;
+}
+
+
+static int mmHashTryFindEntry( mmHashTable *table, mmHashAccess *access, void *findentry, void **retentry )
+{
+ uint32_t hashkey;
+ uint32_t pageindex, pagestart, pagefinal;
+ int cmpvalue, retvalue;
+ void *entry;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( findentry ) & table->hashmask;
+
+ /* Lock first page */
+ pagestart = hashkey >> table->pageshift;
+ pagefinal = pagestart;
+ if( !( MM_HASH_LOCK_TRY_READ( table, pagestart ) ) )
+ return MM_HASH_TRYAGAIN;
+
+ /* Search the entry */
+ entry = 0;
+ retvalue = MM_HASH_SUCCESS;
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ /* Lock new pages */
+ pageindex = hashkey >> table->pageshift;
+ if( pageindex != pagefinal )
+ {
+ if( !( MM_HASH_LOCK_TRY_READ( table, pageindex ) ) )
+ {
+ retvalue = MM_HASH_TRYAGAIN;
+ break;
+ }
+ pagefinal = pageindex;
+ }
+
+ /* Check for entry match */
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, findentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ {
+ retvalue = MM_HASH_FAILURE;
+ entry = 0;
+ break;
+ }
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ break;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ /* Unlock all pages */
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+ MM_HASH_LOCK_DONE_READ( table, pageindex );
+ if( pageindex == pagefinal )
+ break;
+ }
+
+ *retentry = entry;
+ return retvalue;
+}
+
+
+void *mmHashLockFindEntry( void *hashtable, mmHashAccess *access, void *findentry )
+{
+ int retvalue;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+ retvalue = mmHashTryFindEntry( table, access, findentry, &entry );
+ if( retvalue == MM_HASH_TRYAGAIN )
+ {
+ MM_HASH_GLOBAL_LOCK( table );
+ do
+ {
+ retvalue = mmHashTryFindEntry( table, access, findentry, &entry );
+ } while( retvalue == MM_HASH_TRYAGAIN );
+ MM_HASH_GLOBAL_UNLOCK( table );
+ }
+
+ return entry;
+}
+
+
+
+////
+
+
+
+void mmHashDirectListEntry( void *hashtable, mmHashAccess *access, void *listentry, void *opaque )
+{
+ int cmpvalue;
+ uint32_t hashkey;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( listentry ) & table->hashmask;
+
+ /* Search the entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrylist( opaque, entry, listentry );
+ if( cmpvalue == MM_HASH_ENTRYLIST_BREAK )
+ break;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ return;
+}
+
+
+static int mmHashTryListEntry( mmHashTable *table, mmHashAccess *access, void *listentry, void *opaque )
+{
+ uint32_t hashkey;
+ uint32_t pageindex, pagestart, pagefinal;
+ int cmpvalue, retvalue;
+ void *entry;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( listentry ) & table->hashmask;
+
+ /* Lock first page */
+ pagestart = hashkey >> table->pageshift;
+ pagefinal = pagestart;
+ if( !( MM_HASH_LOCK_TRY_READ( table, pagestart ) ) )
+ return MM_HASH_TRYAGAIN;
+
+ /* Search the entry */
+ entry = 0;
+ retvalue = MM_HASH_SUCCESS;
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ /* Lock new pages */
+ pageindex = hashkey >> table->pageshift;
+ if( pageindex != pagefinal )
+ {
+ if( !( MM_HASH_LOCK_TRY_READ( table, pageindex ) ) )
+ {
+ retvalue = MM_HASH_TRYAGAIN;
+ break;
+ }
+ pagefinal = pageindex;
+ }
+
+ /* Check for entry match */
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrylist( opaque, entry, listentry );
+ if( cmpvalue == MM_HASH_ENTRYLIST_BREAK )
+ break;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ /* Unlock all pages */
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+ MM_HASH_LOCK_DONE_READ( table, pageindex );
+ if( pageindex == pagefinal )
+ break;
+ }
+
+ return retvalue;
+}
+
+
+void mmHashLockListEntry( void *hashtable, mmHashAccess *access, void *listentry, void *opaque )
+{
+ int retvalue;
+ mmHashTable *table;
+
+ table = hashtable;
+ retvalue = mmHashTryListEntry( table, access, listentry, opaque );
+ if( retvalue == MM_HASH_TRYAGAIN )
+ {
+ MM_HASH_GLOBAL_LOCK( table );
+ do
+ {
+ retvalue = mmHashTryListEntry( table, access, listentry, opaque );
+ } while( retvalue == MM_HASH_TRYAGAIN );
+ MM_HASH_GLOBAL_UNLOCK( table );
+ }
+
+ return;
+}
+
+
+
+////
+
+
+
+int mmHashDirectReadEntry( void *hashtable, mmHashAccess *access, void *readentry )
+{
+ int cmpvalue;
+ uint32_t hashkey;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( readentry ) & table->hashmask;
+
+ /* Search the entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, readentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ memcpy( readentry, entry, table->entrysize );
+ return MM_HASH_SUCCESS;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ return MM_HASH_FAILURE;
+}
+
+
+static int mmHashTryReadEntry( mmHashTable *table, mmHashAccess *access, void *readentry )
+{
+ uint32_t hashkey;
+ uint32_t pageindex, pagestart, pagefinal;
+ int cmpvalue, retvalue;
+ void *entry;
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( readentry ) & table->hashmask;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Lock first page */
+ pagestart = hashkey >> table->pageshift;
+ pagefinal = pagestart;
+ if( !( MM_HASH_LOCK_TRY_READ( table, pagestart ) ) )
+ return MM_HASH_TRYAGAIN;
+
+ /* Search the entry */
+ entry = 0;
+ retvalue = MM_HASH_SUCCESS;
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ /* Lock new pages */
+ pageindex = hashkey >> table->pageshift;
+ if( pageindex != pagefinal )
+ {
+ if( !( MM_HASH_LOCK_TRY_READ( table, pageindex ) ) )
+ {
+ retvalue = MM_HASH_TRYAGAIN;
+ break;
+ }
+ pagefinal = pageindex;
+ }
+
+ /* Check for entry match */
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, readentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ {
+ retvalue = MM_HASH_FAILURE;
+ entry = 0;
+ break;
+ }
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ break;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ if( entry )
+ memcpy( readentry, entry, table->entrysize );
+
+ /* Unlock all pages */
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+ MM_HASH_LOCK_DONE_READ( table, pageindex );
+ if( pageindex == pagefinal )
+ break;
+ }
+
+ return retvalue;
+}
+
+
+int mmHashLockReadEntry( void *hashtable, mmHashAccess *access, void *readentry )
+{
+ int retvalue;
+ mmHashTable *table;
+
+ table = hashtable;
+ retvalue = mmHashTryReadEntry( table, access, readentry );
+ if( retvalue == MM_HASH_TRYAGAIN )
+ {
+ MM_HASH_GLOBAL_LOCK( table );
+ do
+ {
+ retvalue = mmHashTryReadEntry( table, access, readentry );
+ } while( retvalue == MM_HASH_TRYAGAIN );
+ MM_HASH_GLOBAL_UNLOCK( table );
+ }
+
+ return retvalue;
+}
+
+
+
+////
+
+
+
+int mmHashDirectCallEntry( void *hashtable, mmHashAccess *access, void *callentry, void (*callback)( void *opaque, void *entry, int newflag ), void *opaque, int addflag )
+{
+ int cmpvalue;
+ uint32_t hashkey, entrycount;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( callentry ) & table->hashmask;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Search an available entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, callentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ callback( opaque, entry, 0 );
+ return MM_HASH_SUCCESS;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ if( !( addflag ) )
+ return MM_HASH_FAILURE;
+
+ /* Store new entry */
+ memcpy( entry, callentry, table->entrysize );
+ callback( opaque, entry, 1 );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ return MM_HASH_SUCCESS;
+}
+
+
+static int mmHashTryCallEntry( mmHashTable *table, mmHashAccess *access, void *callentry, void (*callback)( void *opaque, void *entry, int newflag ), void *opaque, int addflag )
+{
+ uint32_t hashkey, entrycount;
+ uint32_t pageindex, pagestart, pagefinal;
+ int cmpvalue, retvalue;
+ void *entry;
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( callentry ) & table->hashmask;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Lock first page */
+ pagestart = hashkey >> table->pageshift;
+ pagefinal = pagestart;
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pagestart ) ) )
+ return MM_HASH_TRYAGAIN;
+
+ /* Search an available entry */
+ retvalue = MM_HASH_SUCCESS;
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ /* Lock new pages */
+ pageindex = hashkey >> table->pageshift;
+ if( pageindex != pagefinal )
+ {
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pageindex ) ) )
+ {
+ retvalue = MM_HASH_TRYAGAIN;
+ goto end;
+ }
+ pagefinal = pageindex;
+ }
+
+ /* Check for entry available */
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, callentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ callback( opaque, entry, 0 );
+ retvalue = MM_HASH_SUCCESS;
+ goto end;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ if( !( addflag ) )
+ {
+ retvalue = MM_HASH_FAILURE;
+ goto end;
+ }
+
+ /* Store new entry */
+ memcpy( entry, callentry, table->entrysize );
+ callback( opaque, entry, 1 );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ end:
+
+ /* Unlock all pages */
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+ MM_HASH_LOCK_DONE_WRITE( table, pageindex );
+ if( pageindex == pagefinal )
+ break;
+ }
+
+ return retvalue;
+}
+
+
+int mmHashLockCallEntry( void *hashtable, mmHashAccess *access, void *callentry, void (*callback)( void *opaque, void *entry, int newflag ), void *opaque, int addflag )
+{
+ int retvalue;
+ mmHashTable *table;
+
+ table = hashtable;
+ retvalue = mmHashTryCallEntry( table, access, callentry, callback, opaque, addflag );
+ if( retvalue == MM_HASH_TRYAGAIN )
+ {
+ MM_HASH_GLOBAL_LOCK( table );
+ do
+ {
+ retvalue = mmHashTryCallEntry( table, access, callentry, callback, opaque, addflag );
+ } while( retvalue == MM_HASH_TRYAGAIN );
+ MM_HASH_GLOBAL_UNLOCK( table );
+ }
+
+ return retvalue;
+}
+
+
+
+////
+
+
+
+int mmHashDirectReplaceEntry( void *hashtable, mmHashAccess *access, void *replaceentry, int addflag )
+{
+ int cmpvalue;
+ uint32_t hashkey, entrycount;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( replaceentry ) & table->hashmask;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Search an available entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, replaceentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ memcpy( entry, replaceentry, table->entrysize );
+ return MM_HASH_SUCCESS;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ if( !( addflag ) )
+ return MM_HASH_FAILURE;
+
+ /* Store new entry */
+ memcpy( entry, replaceentry, table->entrysize );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ return MM_HASH_SUCCESS;
+}
+
+
+static int mmHashTryReplaceEntry( mmHashTable *table, mmHashAccess *access, void *replaceentry, int addflag )
+{
+ uint32_t hashkey, entrycount;
+ uint32_t pageindex, pagestart, pagefinal;
+ int cmpvalue, retvalue;
+ void *entry;
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( replaceentry ) & table->hashmask;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Lock first page */
+ pagestart = hashkey >> table->pageshift;
+ pagefinal = pagestart;
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pagestart ) ) )
+ return MM_HASH_TRYAGAIN;
+
+ /* Search an available entry */
+ retvalue = MM_HASH_SUCCESS;
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ /* Lock new pages */
+ pageindex = hashkey >> table->pageshift;
+ if( pageindex != pagefinal )
+ {
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pageindex ) ) )
+ {
+ retvalue = MM_HASH_TRYAGAIN;
+ goto end;
+ }
+ pagefinal = pageindex;
+ }
+
+ /* Check for entry available */
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, replaceentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ memcpy( entry, replaceentry, table->entrysize );
+ retvalue = MM_HASH_SUCCESS;
+ goto end;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ if( !( addflag ) )
+ {
+ retvalue = MM_HASH_FAILURE;
+ goto end;
+ }
+
+ /* Store new entry */
+ memcpy( entry, replaceentry, table->entrysize );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ end:
+
+ /* Unlock all pages */
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+ MM_HASH_LOCK_DONE_WRITE( table, pageindex );
+ if( pageindex == pagefinal )
+ break;
+ }
+
+ return retvalue;
+}
+
+
+int mmHashLockReplaceEntry( void *hashtable, mmHashAccess *access, void *replaceentry, int addflag )
+{
+ int retvalue;
+ mmHashTable *table;
+
+ table = hashtable;
+ retvalue = mmHashTryReplaceEntry( table, access, replaceentry, addflag );
+ if( retvalue == MM_HASH_TRYAGAIN )
+ {
+ MM_HASH_GLOBAL_LOCK( table );
+ do
+ {
+ retvalue = mmHashTryReplaceEntry( table, access, replaceentry, addflag );
+ } while( retvalue == MM_HASH_TRYAGAIN );
+ MM_HASH_GLOBAL_UNLOCK( table );
+ }
+
+ return retvalue;
+}
+
+
+
+////
+
+
+
+int mmHashDirectAddEntry( void *hashtable, mmHashAccess *access, void *addentry, int nodupflag )
+{
+ int cmpvalue;
+ uint32_t hashkey, entrycount;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( addentry ) & table->hashmask;
+
+ /* Search an available entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ /* Do we allow duplicate entries? */
+ if( nodupflag )
+ {
+ cmpvalue = access->entrycmp( entry, addentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ return MM_HASH_FAILURE;
+ }
+ else
+ {
+ if( !( access->entryvalid( entry ) ) )
+ break;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ /* Store new entry */
+ memcpy( entry, addentry, table->entrysize );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ return MM_HASH_SUCCESS;
+}
+
+
+static int mmHashTryAddEntry( mmHashTable *table, mmHashAccess *access, void *addentry, int nodupflag )
+{
+ uint32_t hashkey, entrycount;
+ uint32_t pageindex, pagestart, pagefinal;
+ int cmpvalue, retvalue;
+ void *entry;
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( addentry ) & table->hashmask;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Lock first page */
+ pagestart = hashkey >> table->pageshift;
+ pagefinal = pagestart;
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pagestart ) ) )
+ return MM_HASH_TRYAGAIN;
+
+ /* Search an available entry */
+ retvalue = MM_HASH_SUCCESS;
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ /* Lock new pages */
+ pageindex = hashkey >> table->pageshift;
+ if( pageindex != pagefinal )
+ {
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pageindex ) ) )
+ {
+ retvalue = MM_HASH_TRYAGAIN;
+ goto end;
+ }
+ pagefinal = pageindex;
+ }
+
+ /* Check for entry available */
+ entry = MM_HASH_ENTRY( table, hashkey );
+ /* Do we allow duplicate entries? */
+ if( nodupflag )
+ {
+ cmpvalue = access->entrycmp( entry, addentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ retvalue = MM_HASH_FAILURE;
+ goto end;
+ }
+ }
+ else
+ {
+ if( !( access->entryvalid( entry ) ) )
+ break;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ /* Store new entry */
+ memcpy( entry, addentry, table->entrysize );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ end:
+
+ /* Unlock all pages */
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+ MM_HASH_LOCK_DONE_WRITE( table, pageindex );
+ if( pageindex == pagefinal )
+ break;
+ }
+
+ return retvalue;
+}
+
+
+
+int mmHashLockAddEntry( void *hashtable, mmHashAccess *access, void *addentry, int nodupflag )
+{
+ int retvalue;
+ mmHashTable *table;
+
+ table = hashtable;
+ retvalue = mmHashTryAddEntry( table, access, addentry, nodupflag );
+ if( retvalue == MM_HASH_TRYAGAIN )
+ {
+ MM_HASH_GLOBAL_LOCK( table );
+ do
+ {
+ retvalue = mmHashTryAddEntry( table, access, addentry, nodupflag );
+ } while( retvalue == MM_HASH_TRYAGAIN );
+ MM_HASH_GLOBAL_UNLOCK( table );
+ }
+
+ return retvalue;
+}
+
+
+
+////
+
+
+
+int mmHashDirectReadOrAddEntry( void *hashtable, mmHashAccess *access, void *readaddentry, int *retreadflag )
+{
+ int cmpvalue;
+ uint32_t hashkey, entrycount;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( readaddentry ) & table->hashmask;
+
+ /* Search an available entry */
+ *retreadflag = 0;
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, readaddentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ memcpy( readaddentry, entry, table->entrysize );
+ *retreadflag = 1;
+ return MM_HASH_SUCCESS;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ /* Store new entry */
+ memcpy( entry, readaddentry, table->entrysize );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ return MM_HASH_SUCCESS;
+}
+
+
+static int mmHashTryReadOrAddEntry( mmHashTable *table, mmHashAccess *access, void *readaddentry, int *retreadflag )
+{
+ uint32_t hashkey, entrycount;
+ uint32_t pageindex, pagestart, pagefinal;
+ int cmpvalue, retvalue;
+ void *entry;
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( readaddentry ) & table->hashmask;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Lock first page */
+ pagestart = hashkey >> table->pageshift;
+ pagefinal = pagestart;
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pagestart ) ) )
+ return MM_HASH_TRYAGAIN;
+
+ /* Search an available entry */
+ retvalue = MM_HASH_SUCCESS;
+ *retreadflag = 0;
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ /* Lock new pages */
+ pageindex = hashkey >> table->pageshift;
+ if( pageindex != pagefinal )
+ {
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pageindex ) ) )
+ {
+ retvalue = MM_HASH_TRYAGAIN;
+ goto end;
+ }
+ pagefinal = pageindex;
+ }
+
+ /* Check for entry available */
+ entry = MM_HASH_ENTRY( table, hashkey );
+
+ cmpvalue = access->entrycmp( entry, readaddentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ memcpy( readaddentry, entry, table->entrysize );
+ *retreadflag = 1;
+ goto end;
+ }
+
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ /* Store new entry */
+ memcpy( entry, readaddentry, table->entrysize );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ end:
+
+ /* Unlock all pages */
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+ MM_HASH_LOCK_DONE_WRITE( table, pageindex );
+ if( pageindex == pagefinal )
+ break;
+ }
+
+ return retvalue;
+}
+
+
+
+int mmHashLockReadOrAddEntry( void *hashtable, mmHashAccess *access, void *readaddentry, int *retreadflag )
+{
+ int retvalue;
+ mmHashTable *table;
+
+ table = hashtable;
+ retvalue = mmHashTryReadOrAddEntry( table, access, readaddentry, retreadflag );
+ if( retvalue == MM_HASH_TRYAGAIN )
+ {
+ MM_HASH_GLOBAL_LOCK( table );
+ do
+ {
+ retvalue = mmHashTryReadOrAddEntry( table, access, readaddentry, retreadflag );
+ } while( retvalue == MM_HASH_TRYAGAIN );
+ MM_HASH_GLOBAL_UNLOCK( table );
+ }
+
+ return retvalue;
+}
+
+
+
+////
+
+
+
+#define MM_ROBUST_DELETION
+
+
+int mmHashDirectDeleteEntry( void *hashtable, mmHashAccess *access, void *deleteentry, int readflag )
+{
+ int cmpvalue;
+ uint32_t hashkey, srckey, srcpos, targetpos, targetkey, entrycount;
+#ifdef MM_ROBUST_DELETION
+ uint32_t delbase;
+#else
+ int32_t halftablesize, distance;
+#endif
+ void *entry, *srcentry, *targetentry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( deleteentry ) & table->hashmask;
+
+ /* Search the entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, deleteentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ return MM_HASH_FAILURE;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ break;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ if( readflag )
+ memcpy( deleteentry, entry, table->entrysize );
+
+#ifdef MM_ROBUST_DELETION
+ for( delbase = hashkey ; ; )
+ {
+ delbase = ( delbase - 1 ) & table->hashmask;
+ if( !( access->entryvalid( MM_HASH_ENTRY( table, delbase ) ) ) )
+ break;
+ }
+ delbase = ( delbase + 1 ) & table->hashmask;
+#else
+ halftablesize = table->hashsize >> 1;
+#endif
+
+ /* Entry found, delete it */
+ for( ; ; )
+ {
+ /* Find replacement target */
+ targetkey = hashkey;
+ targetentry = 0;
+ for( srcpos = hashkey ; ; )
+ {
+ srcpos = ( srcpos + 1 ) & table->hashmask;
+
+ /* Try next entry */
+ srcentry = MM_HASH_ENTRY( table, srcpos );
+ if( !( access->entryvalid( srcentry ) ) )
+ break;
+ srckey = access->entrykey( srcentry ) & table->hashmask;
+
+#ifdef MM_ROBUST_DELETION
+ if( targetkey >= delbase )
+ {
+ if( ( srckey < delbase ) || ( srckey > targetkey ) )
+ continue;
+ }
+ else if( ( srckey > targetkey ) && ( srckey < delbase ) )
+ continue;
+ targetentry = srcentry;
+ targetkey = srckey;
+ targetpos = srcpos;
+#else
+ /* Check if moving the entry backwards is allowed without breaking chain */
+ distance = (int32_t)targetkey - (int32_t)srckey;
+ if( distance > halftablesize )
+ distance -= table->hashsize;
+ else if( distance < -halftablesize )
+ distance += table->hashsize;
+ if( distance >= 0 )
+ {
+ targetentry = srcentry;
+ targetkey = srckey;
+ targetpos = srcpos;
+ }
+#endif
+ }
+
+ /* No replacement found, just clear it */
+ entry = MM_HASH_ENTRY( table, hashkey );
+ if( !( targetentry ) )
+ {
+ access->clearentry( entry );
+ break;
+ }
+
+ /* Move entry in place and continue the repair process */
+ memcpy( entry, targetentry, table->entrysize );
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->relocationcount, 1 );
+#endif
+
+ hashkey = targetpos;
+ }
+
+ /* Decrement count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, -1 );
+ if( entrycount < table->lowcount )
+ table->status = MM_HASH_STATUS_MUSTSHRINK;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->statentrycount, -1 );
+#endif
+
+ return MM_HASH_SUCCESS;
+}
+
+
+static int mmHashTryDeleteEntry( mmHashTable *table, mmHashAccess *access, void *deleteentry, int readflag )
+{
+ uint32_t hashkey, srckey, srcpos, srcend, targetpos, targetkey, entrycount;
+ uint32_t pageindex, pagestart, pagefinal;
+#ifdef MM_ROBUST_DELETION
+ uint32_t delbase;
+#else
+ int32_t halftablesize, distance;
+#endif
+ int cmpvalue, retvalue;
+ void *entry, *srcentry, *targetentry;
+
+ /* Hash key of entry */
+ hashkey = access->entrykey( deleteentry ) & table->hashmask;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Lock first page */
+ pagestart = hashkey >> table->pageshift;
+ pagefinal = pagestart;
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pagestart ) ) )
+ return MM_HASH_TRYAGAIN;
+
+ /* Search the entry */
+ retvalue = MM_HASH_SUCCESS;
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ /* Lock new pages */
+ pageindex = hashkey >> table->pageshift;
+ if( pageindex != pagefinal )
+ {
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pageindex ) ) )
+ {
+ retvalue = MM_HASH_TRYAGAIN;
+ goto end;
+ }
+ pagefinal = pageindex;
+ }
+
+ /* Check for entry match */
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = access->entrycmp( entry, deleteentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ {
+ retvalue = MM_HASH_FAILURE;
+ goto end;
+ }
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ break;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ if( readflag )
+ memcpy( deleteentry, entry, table->entrysize );
+
+#ifdef MM_ROBUST_DELETION
+ for( delbase = hashkey ; ; )
+ {
+ delbase = ( delbase - 1 ) & table->hashmask;
+ if( !( access->entryvalid( MM_HASH_ENTRY( table, delbase ) ) ) )
+ break;
+ }
+ delbase = ( delbase + 1 ) & table->hashmask;
+#else
+ halftablesize = table->hashsize >> 1;
+#endif
+
+ /* Preemtively lock all pages in the stream before starting the operation */
+ for( srcend = hashkey ; ; )
+ {
+ srcend = ( srcend + 1 ) & table->hashmask;
+
+ /* Lock new pages */
+ pageindex = srcend >> table->pageshift;
+ if( pageindex != pagefinal )
+ {
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pageindex ) ) )
+ {
+ retvalue = MM_HASH_TRYAGAIN;
+ goto end;
+ }
+ pagefinal = pageindex;
+ }
+
+ /* Check for valid entry */
+ srcentry = MM_HASH_ENTRY( table, srcend );
+ if( !( access->entryvalid( srcentry ) ) )
+ break;
+ }
+
+ /* Entry found, delete it and reorder the hash stream of entries */
+ for( ; ; )
+ {
+ /* Find replacement target */
+ targetkey = hashkey;
+ targetentry = 0;
+ for( srcpos = hashkey ; ; )
+ {
+ srcpos = ( srcpos + 1 ) & table->hashmask;
+ srcentry = MM_HASH_ENTRY( table, srcpos );
+
+ /* Don't loop beyond the end of hash stream */
+ if( srcpos == srcend )
+ break;
+
+ /* Try next entry */
+ srckey = access->entrykey( srcentry ) & table->hashmask;
+
+#ifdef MM_ROBUST_DELETION
+ if( targetkey >= delbase )
+ {
+ if( ( srckey < delbase ) || ( srckey > targetkey ) )
+ continue;
+ }
+ else if( ( srckey > targetkey ) && ( srckey < delbase ) )
+ continue;
+ targetentry = srcentry;
+ targetkey = srckey;
+ targetpos = srcpos;
+#else
+ /* Check if moving the entry backwards is allowed without breaking chain */
+ distance = (int32_t)targetkey - (int32_t)srckey;
+ if( distance > halftablesize )
+ distance -= table->hashsize;
+ else if( distance < -halftablesize )
+ distance += table->hashsize;
+ if( distance >= 0 )
+ {
+ targetentry = srcentry;
+ targetkey = srckey;
+ targetpos = srcpos;
+ }
+#endif
+ }
+
+ /* No replacement found, just clear it */
+ entry = MM_HASH_ENTRY( table, hashkey );
+ if( !( targetentry ) )
+ {
+ access->clearentry( entry );
+ break;
+ }
+
+ /* Move entry in place and continue the repair process */
+ memcpy( entry, targetentry, table->entrysize );
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->relocationcount, 1 );
+#endif
+
+ hashkey = targetpos;
+ }
+
+ /* Decrement count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, -1 );
+ if( entrycount < table->lowcount )
+ table->status = MM_HASH_STATUS_MUSTSHRINK;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->statentrycount, -1 );
+#endif
+
+ end:
+
+ /* Unlock all pages */
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+ MM_HASH_LOCK_DONE_WRITE( table, pageindex );
+ if( pageindex == pagefinal )
+ break;
+ }
+
+ return retvalue;
+}
+
+
+int mmHashLockDeleteEntry( void *hashtable, mmHashAccess *access, void *deleteentry, int readflag )
+{
+ int retvalue;
+ mmHashTable *table;
+
+ table = hashtable;
+ retvalue = mmHashTryDeleteEntry( table, access, deleteentry, readflag );
+ if( retvalue == MM_HASH_TRYAGAIN )
+ {
+ MM_HASH_GLOBAL_LOCK( table );
+ do
+ {
+ retvalue = mmHashTryDeleteEntry( table, access, deleteentry, readflag );
+ } while( retvalue == MM_HASH_TRYAGAIN );
+ MM_HASH_GLOBAL_UNLOCK( table );
+ }
+
+ return retvalue;
+}
+
+
+
+////
+
+
+
+/* Must be called while NO other thread will ever access the table for writing */
+void mmHashResize( void *newtable, void *oldtable, mmHashAccess *access, uint32_t hashbits, uint32_t pageshift )
+{
+ uint32_t hashkey, hashpos, dstkey, dstpos, pageindex;
+ void *srcentry, *dstentry;
+ mmHashTable *dst, *src;
+ mmHashPage *page;
+
+ dst = newtable;
+ src = oldtable;
+ dst->status = MM_HASH_STATUS_NORMAL;
+ dst->flags = src->flags;
+ dst->entrysize = src->entrysize;
+ dst->minhashbits = src->minhashbits;
+ dst->hashbits = hashbits;
+ dst->hashsize = 1 << dst->hashbits;
+ dst->hashmask = dst->hashsize - 1;
+ dst->pageshift = pageshift;
+ dst->pagecount = dst->hashsize >> pageshift;
+ dst->pagemask = dst->pagecount - 1;
+ dst->page = MM_HASH_PAGELIST( dst );
+#ifdef MM_ATOMIC_SUPPORT
+ mmAtomicWrite32( &dst->entrycount, mmAtomicRead32( &src->entrycount ) );
+#else
+ dst->entrycount = src->entrycount;
+#endif
+ mmHashSetBounds( dst );
+
+ /* Clear the whole destination table */
+ dstentry = MM_HASH_ENTRYLIST( dst );
+ for( hashpos = 0 ; hashpos < dst->hashsize ; hashpos++ )
+ {
+ access->clearentry( dstentry );
+ dstentry = ADDRESS( dstentry, dst->entrysize );
+ }
+
+ /* Clear the lock pages */
+#ifdef MM_ATOMIC_SUPPORT
+ page = dst->page;
+ for( pageindex = 0 ; pageindex < dst->pagecount ; pageindex++, page++ )
+ {
+ mmAtomicLockInit32( &page->lock );
+ mmAtomicWriteP( &page->owner, (void *)0 );
+ }
+ mmAtomicWrite32( &dst->globallock, 0x0 );
+#else
+ page = src->page;
+ for( pageindex = src->pagecount ; pageindex ; pageindex--, page++ )
+ mtMutexDestroy( &page->mutex );
+ mtMutexDestroy( &src->globalmutex );
+ page = dst->page;
+ for( pageindex = dst->pagecount ; pageindex ; pageindex--, page++ )
+ {
+ mtMutexInit( &page->mutex );
+ page->owner = 0;
+ }
+ mtMutexInit( &dst->globalmutex );
+#endif
+
+ /* Move all entries from the src table to the dst table */
+ srcentry = MM_HASH_ENTRYLIST( src );
+ for( hashpos = 0 ; hashpos < src->hashsize ; hashpos++ )
+ {
+ hashkey = access->entrykey( srcentry );
+ dstkey = hashkey & dst->hashmask;
+
+ /* Search an empty spot in the destination table */
+ for( dstpos = dstkey ; ; dstpos = ( dstpos + 1 ) & dst->hashmask )
+ {
+ dstentry = MM_HASH_ENTRY( dst, dstpos );
+ if( !( access->entryvalid( dstentry ) ) )
+ break;
+ }
+
+ /* Copy entry from src table to dst table */
+ memcpy( dstentry, srcentry, src->entrysize );
+ srcentry = ADDRESS( srcentry, src->entrysize );
+ }
+
+ return;
+}
+
+
+
+////
+
+
+static int mmHashLockRangeTry( mmHashTable *table, mmHashAccess *access, mmHashLock *hashlock, mmHashLockRange *lockrange, uint32_t hashkey )
+{
+ int newcount;
+ uint32_t srckey;
+ uint32_t pageindex, pagestart, pagefinal;
+ void *srcentry;
+
+ /* Lock first page */
+ pagestart = hashkey >> table->pageshift;
+ pagefinal = pagestart;
+#ifdef MM_ATOMIC_SUPPORT
+ if( mmAtomicReadP( &table->page[pagestart].owner ) != (void *)hashlock )
+ {
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pagestart ) ) )
+ return MM_HASH_TRYAGAIN;
+ }
+ mmAtomicWriteP( &table->page[pagestart].owner, (void *)hashlock );
+#else
+ if( table->page[pagestart].owner != (void *)hashlock )
+ {
+ if( !( MM_HASH_LOCK_TRY_WRITE( table, pagestart ) ) )
+ return MM_HASH_TRYAGAIN;
+ }
+ table->page[pagestart].owner = hashlock;
+#endif
+
+ /* Lock all pages in stream */
+ newcount = hashlock->newcount;
+ for( srckey = hashkey ; ; )
+ {
+ srckey = ( srckey + 1 ) & table->hashmask;
+
+ /* Lock new pages */
+ pageindex = srckey >> table->pageshift;
+ if( pageindex != pagefinal )
+ {
+#ifdef MM_ATOMIC_SUPPORT
+ if( mmAtomicReadP( &table->page[pageindex].owner ) != (void *)hashlock )
+ {
+ if( MM_HASH_LOCK_TRY_WRITE( table, pageindex ) )
+ {
+ mmAtomicWriteP( &table->page[pageindex].owner, (void *)hashlock );
+ continue;
+ }
+ /* Failed, unlock all pages */
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+ mmAtomicWriteP( &table->page[pageindex].owner, (void *)0 );
+ MM_HASH_LOCK_DONE_WRITE( table, pageindex );
+ if( pageindex == pagefinal )
+ break;
+ }
+ return MM_HASH_TRYAGAIN;
+ }
+#else
+ if( table->page[pageindex].owner != (void *)hashlock )
+ {
+ if( MM_HASH_LOCK_TRY_WRITE( table, pageindex ) )
+ {
+ table->page[pageindex].owner = (void *)hashlock;
+ continue;
+ }
+ /* Failed, unlock all pages */
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+ table->page[pageindex].owner = 0;
+ MM_HASH_LOCK_DONE_WRITE( table, pageindex );
+ if( pageindex == pagefinal )
+ break;
+ }
+ return MM_HASH_TRYAGAIN;
+ }
+#endif
+ pagefinal = pageindex;
+ }
+
+ /* Check for valid entry */
+ srcentry = MM_HASH_ENTRY( table, srckey );
+ if( !( access->entryvalid( srcentry ) ) )
+ {
+ if( --newcount <= 0 )
+ break;
+ }
+ }
+
+ /* Store lock pagestart and pagefinal */
+ lockrange->pagestart = pagestart;
+ lockrange->pagefinal = pagefinal;
+
+ return MM_HASH_SUCCESS;
+}
+
+
+static void mmHashLockReleaseAll( mmHashTable *table, mmHashLock *hashlock )
+{
+ uint32_t pageindex, pagestart, pagefinal;
+ mmHashLockRange *lockrange;
+
+ for( lockrange = hashlock->rangelist ; lockrange ; lockrange = lockrange->next )
+ {
+ if( lockrange->pagestart == ~(uint32_t)0x0 )
+ continue;
+ pagestart = lockrange->pagestart;
+ pagefinal = lockrange->pagefinal;
+ for( pageindex = pagestart ; ; pageindex = ( pageindex + 1 ) & table->pagemask )
+ {
+#ifdef MM_ATOMIC_SUPPORT
+ if( mmAtomicReadP( &table->page[pageindex].owner ) == (void *)hashlock )
+ {
+ mmAtomicWriteP( &table->page[pageindex].owner, (void *)0 );
+ mmAtomicLockDoneWrite32( &table->page[pageindex].lock );
+ }
+#else
+ if( table->page[pageindex].owner == (void *)hashlock )
+ {
+ table->page[pageindex].owner = (void *)0;
+ MM_HASH_LOCK_DONE_WRITE( table, pageindex );
+ }
+#endif
+ if( pageindex == pagefinal )
+ break;
+ }
+ }
+
+ for( lockrange = hashlock->rangelist ; lockrange ; lockrange = lockrange->next )
+ {
+ lockrange->pagestart = ~0x0;
+ lockrange->pagefinal = ~0x0;
+ }
+
+ return;
+}
+
+
+static int mmHashLockApplyAll( mmHashTable *table, mmHashAccess *access, mmHashLock *hashlock )
+{
+ mmHashLockRange *lockrange, *lockrangenext;
+
+ for( lockrange = hashlock->rangelist ; lockrange ; lockrange = lockrangenext )
+ {
+ lockrangenext = lockrange->next;
+ if( mmHashLockRangeTry( table, access, hashlock, lockrange, lockrange->hashkey ) == MM_HASH_TRYAGAIN )
+ {
+ /* Failure, release all locks */
+ mmHashLockReleaseAll( table, hashlock );
+ return MM_HASH_TRYAGAIN;
+ }
+ }
+
+ return MM_HASH_SUCCESS;
+}
+
+
+
+////
+
+
+
+void mmHashLockInit( mmHashLock *hashlock, int newcount )
+{
+ memset( hashlock, 0, sizeof(mmHashLock) );
+ hashlock->newcount = newcount;
+ return;
+}
+
+void mmHashLockAdd( void *hashtable, mmHashAccess *access, void *entry, mmHashLock *hashlock, mmHashLockRange *lockrange )
+{
+ uint32_t hashkey;
+ mmHashTable *table;
+
+ /* Hash key of entry */
+ table = hashtable;
+ hashkey = access->entrykey( entry ) & table->hashmask;
+
+ lockrange->hashkey = hashkey;
+ lockrange->pagestart = ~0x0;
+ lockrange->pagefinal = ~0x0;
+ lockrange->next = hashlock->rangelist;
+ hashlock->rangelist = lockrange;
+
+ return;
+}
+
+void mmHashLockAcquire( void *hashtable, mmHashAccess *access, mmHashLock *hashlock )
+{
+ int status;
+ mmHashTable *table;
+
+ table = hashtable;
+ status = mmHashLockApplyAll( table, access, hashlock );
+ if( status == MM_HASH_TRYAGAIN )
+ {
+ MM_HASH_GLOBAL_LOCK( table );
+ do
+ {
+ status = mmHashLockApplyAll( table, access, hashlock );
+ } while( status == MM_HASH_TRYAGAIN );
+ MM_HASH_GLOBAL_UNLOCK( table );
+ }
+
+ return;
+}
+
+void mmHashLockRelease( void *hashtable, mmHashLock *hashlock )
+{
+ mmHashTable *table;
+
+ table = hashtable;
+ mmHashLockReleaseAll( table, hashlock );
+
+ return;
+}
+
+
+////
+
+
+void mmHashGlobalLockEnable( void *hashtable )
+{
+ uint32_t pageindex;
+ mmHashTable *table;
+
+ table = hashtable;
+ MM_HASH_GLOBAL_LOCK( table );
+ for( pageindex = 0 ; pageindex < table->pagecount ; pageindex++ )
+ MM_HASH_LOCK_TRY_WRITE( table, pageindex );
+
+ return;
+}
+
+
+void mmHashGlobalLockDisable( void *hashtable )
+{
+ uint32_t pageindex;
+ mmHashTable *table;
+
+ table = hashtable;
+ for( pageindex = 0 ; pageindex < table->pagecount ; pageindex++ )
+ MM_HASH_LOCK_DONE_WRITE( table, pageindex );
+ MM_HASH_GLOBAL_UNLOCK( table );
+
+ return;
+}
+
+
+////
+
+
+
+void mmHashDirectDebugDuplicate( void *hashtable, mmHashAccess *access, void (*callback)( void *opaque, void *entry0, void *entry1 ), void *opaque )
+{
+ uint32_t hashbase, hashkey;
+ void *baseentry, *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+ for( hashbase = 0 ; hashbase < table->hashsize ; hashbase++ )
+ {
+ baseentry = MM_HASH_ENTRY( table, hashbase );
+ for( hashkey = hashbase ; ; )
+ {
+ hashkey = ( hashkey + 1 ) & table->hashmask;
+ entry = MM_HASH_ENTRY( table, hashkey );
+ if( !( access->entryvalid( entry ) ) )
+ break;
+ if( access->entrycmp( entry, baseentry ) )
+ callback( opaque, entry, baseentry );
+ }
+ }
+
+ return;
+}
+
+
+void mmHashDirectDebugPages( void *hashtable )
+{
+ uint32_t pageindex;
+ mmHashTable *table;
+ mmHashPage *page;
+
+ table = hashtable;
+
+#ifdef MM_ATOMIC_SUPPORT
+ page = table->page;
+ for( pageindex = 0 ; pageindex < table->pagecount ; pageindex++, page++ )
+ {
+ if( ( page->lock.v.value ) || mmAtomicReadP( &page->owner ) )
+ printf( "Page[%d] = 0x%x ; %p\n", pageindex, page->lock.v.value, mmAtomicReadP( &page->owner ) );
+ }
+ fflush( stdout );
+#endif
+
+ return;
+}
+
+
+
+void mmHashStatistics( void *hashtable, long *accesscount, long *collisioncount, long *relocationcount, long *entrycount, long *entrycountmax, long *hashsizemax )
+{
+ mmHashTable *table;
+
+ table = hashtable;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ *accesscount = mmAtomicReadL( &table->accesscount );
+ *collisioncount = mmAtomicReadL( &table->collisioncount );
+ *relocationcount = mmAtomicReadL( &table->relocationcount );
+ *entrycount = mmAtomicReadL( &table->statentrycount );
+ *entrycountmax = table->entrycountmax;
+ *hashsizemax = 1 << table->hashbits;
+#else
+ *accesscount = 0;
+ *collisioncount = 0;
+ *relocationcount = 0;
+ *entrycount = 0;
+ *entrycountmax = 0;
+ *hashsizemax = 1 << table->hashbits;
+#endif
+
+ return;
+}
+
--- /dev/null
+/* *****************************************************************************
+ * Copyright (c) 2007-2015 Alexis Naveros.
+ *
+ * Ecere Corporation has unlimited/unrestricted rights.
+ * *****************************************************************************/
+
+/*
+
+Input preprocessor symbols
+
+#define HASH_CLEARENTRY SomeFunction
+#define HASH_ENTRYVALID SomeFunction
+#define HASH_ENTRYKEY SomeFunction
+#define HASH_ENTRYCMP SomeFunction
+#define HASH_ENTRYLIST SomeFunction
+
+#define HASH_DECLARE_DIRECTFINDENTRY MyFunctionFindEntry
+#define HASH_DECLARE_DIRECTLISTENTRY MyFunctionListEntry
+#define HASH_DECLARE_DIRECTREADENTRY MyFunctionReadEntry
+#define HASH_DECLARE_DIRECTCALLENTRY MyFunctionCallEntry
+#define HASH_DECLARE_DIRECTREPLACEENTRY MyFunctionReplaceEntry
+#define HASH_DECLARE_DIRECTADDENTRY MyFunctionAddEntry
+#define HASH_DECLARE_DIRECTREADORADDENTRY MyFunctionReadOrAddFindEntry
+#define HASH_DECLARE_DIRECTDELETEENTRY MyFunctionDeleteEntry
+
+*/
+
+#include "mmhashinternal.h"
+
+
+////
+
+
+#ifdef HASH_DECLARE_DIRECTFINDENTRY
+
+void *HASH_DECLARE_DIRECTFINDENTRY( void *hashtable, void *findentry )
+{
+ int cmpvalue;
+ uint32_t hashkey;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = HASH_ENTRYKEY( findentry ) & table->hashmask;
+
+ /* Search the entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = HASH_ENTRYCMP( entry, findentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ return entry;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ return 0;
+}
+
+#endif
+
+
+#ifdef HASH_DECLARE_DIRECTLISTENTRY
+
+void HASH_DECLARE_DIRECTLISTENTRY( void *hashtable, void *listentry, void *opaque )
+{
+ int cmpvalue;
+ uint32_t hashkey;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = HASH_ENTRYKEY( listentry ) & table->hashmask;
+
+ /* Search the entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = HASH_ENTRYLIST( opaque, entry, listentry );
+ if( cmpvalue == MM_HASH_ENTRYLIST_BREAK )
+ break;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ return;
+}
+
+#endif
+
+
+#ifdef HASH_DECLARE_DIRECTREADENTRY
+
+int HASH_DECLARE_DIRECTREADENTRY( void *hashtable, void *readentry )
+{
+ int cmpvalue;
+ uint32_t hashkey;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = HASH_ENTRYKEY( readentry ) & table->hashmask;
+
+ /* Search the entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = HASH_ENTRYCMP( entry, readentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ memcpy( readentry, entry, table->entrysize );
+ return MM_HASH_SUCCESS;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ return MM_HASH_FAILURE;
+}
+
+#endif
+
+
+#ifdef HASH_DECLARE_DIRECTCALLENTRY
+
+int HASH_DECLARE_DIRECTCALLENTRY( void *hashtable, void *callentry, void (*callback)( void *opaque, void *entry, int newflag ), void *opaque, int addflag )
+{
+ int cmpvalue;
+ uint32_t hashkey, entrycount;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+ /* Hash key of entry */
+ hashkey = HASH_ENTRYKEY( callentry ) & table->hashmask;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Search an available entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = HASH_ENTRYCMP( entry, callentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ callback( opaque, entry, 0 );
+ return MM_HASH_SUCCESS;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ if( !( addflag ) )
+ return MM_HASH_FAILURE;
+
+ /* Store new entry */
+ memcpy( entry, callentry, table->entrysize );
+ callback( opaque, entry, 1 );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ return MM_HASH_SUCCESS;
+}
+
+#endif
+
+
+#ifdef HASH_DECLARE_DIRECTREPLACEENTRY
+
+int HASH_DECLARE_DIRECTREPLACEENTRY( void *hashtable, void *replaceentry, int addflag )
+{
+ int cmpvalue;
+ uint32_t hashkey, entrycount;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+ /* Hash key of entry */
+ hashkey = HASH_ENTRYKEY( replaceentry ) & table->hashmask;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Search an available entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = HASH_ENTRYCMP( entry, replaceentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ memcpy( entry, replaceentry, table->entrysize );
+ return MM_HASH_SUCCESS;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ if( !( addflag ) )
+ return MM_HASH_FAILURE;
+
+ /* Store new entry */
+ memcpy( entry, replaceentry, table->entrysize );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ return MM_HASH_SUCCESS;
+}
+
+#endif
+
+
+#ifdef HASH_DECLARE_DIRECTADDENTRY
+
+int HASH_DECLARE_DIRECTADDENTRY( void *hashtable, void *addentry, int nodupflag )
+{
+ int cmpvalue;
+ uint32_t hashkey, entrycount;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = HASH_ENTRYKEY( addentry ) & table->hashmask;
+
+ /* Search an available entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ /* Do we allow duplicate entries? */
+ if( nodupflag )
+ {
+ cmpvalue = HASH_ENTRYCMP( entry, addentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ return MM_HASH_FAILURE;
+ }
+ else
+ {
+ if( !( HASH_ENTRYVALID( entry ) ) )
+ break;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ /* Store new entry */
+ memcpy( entry, addentry, table->entrysize );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ return MM_HASH_SUCCESS;
+}
+
+#endif
+
+
+#ifdef HASH_DECLARE_DIRECTREADORADDENTRY
+
+int HASH_DECLARE_DIRECTREADORADDENTRY( void *hashtable, void *readaddentry, int *retreadflag )
+{
+ int cmpvalue;
+ uint32_t hashkey, entrycount;
+ void *entry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = HASH_ENTRYKEY( readaddentry ) & table->hashmask;
+
+ /* Search an available entry */
+ *retreadflag = 0;
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = HASH_ENTRYCMP( entry, readaddentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ break;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ {
+ memcpy( readaddentry, entry, table->entrysize );
+ *retreadflag = 1;
+ return MM_HASH_SUCCESS;
+ }
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ /* Store new entry */
+ memcpy( entry, readaddentry, table->entrysize );
+
+ /* Increment count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, 1 );
+ if( entrycount >= table->highcount )
+ table->status = MM_HASH_STATUS_MUSTGROW;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ int statentrycount = mmAtomicAddReadL( &table->statentrycount, 1 );
+ if( statentrycount > table->entrycountmax )
+ table->entrycountmax = statentrycount;
+#endif
+
+ return MM_HASH_SUCCESS;
+}
+
+#endif
+
+
+#ifdef HASH_DECLARE_DIRECTDELETEENTRY
+
+int HASH_DECLARE_DIRECTDELETEENTRY( void *hashtable, void *deleteentry, int readflag )
+{
+ int cmpvalue;
+ uint32_t hashkey, srckey, srcpos, targetpos, targetkey, entrycount;
+ uint32_t delbase;
+ void *entry, *srcentry, *targetentry;
+ mmHashTable *table;
+
+ table = hashtable;
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->accesscount, 1 );
+#endif
+
+ /* Hash key of entry */
+ hashkey = HASH_ENTRYKEY( deleteentry ) & table->hashmask;
+
+ /* Search the entry */
+ for( ; ; hashkey = ( hashkey + 1 ) & table->hashmask )
+ {
+ entry = MM_HASH_ENTRY( table, hashkey );
+ cmpvalue = HASH_ENTRYCMP( entry, deleteentry );
+ if( cmpvalue == MM_HASH_ENTRYCMP_INVALID )
+ return MM_HASH_FAILURE;
+ else if( cmpvalue == MM_HASH_ENTRYCMP_FOUND )
+ break;
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->collisioncount, 1 );
+#endif
+ }
+
+ if( readflag )
+ memcpy( deleteentry, entry, table->entrysize );
+
+ for( delbase = hashkey ; ; )
+ {
+ delbase = ( delbase - 1 ) & table->hashmask;
+ if( !( HASH_ENTRYVALID( MM_HASH_ENTRY( table, delbase ) ) ) )
+ break;
+ }
+ delbase = ( delbase + 1 ) & table->hashmask;
+
+ /* Entry found, delete it */
+ for( ; ; )
+ {
+ /* Find replacement target */
+ targetkey = hashkey;
+ targetentry = 0;
+ for( srcpos = hashkey ; ; )
+ {
+ srcpos = ( srcpos + 1 ) & table->hashmask;
+
+ /* Try next entry */
+ srcentry = MM_HASH_ENTRY( table, srcpos );
+ if( !( HASH_ENTRYVALID( srcentry ) ) )
+ break;
+ srckey = HASH_ENTRYKEY( srcentry ) & table->hashmask;
+
+ if( targetkey >= delbase )
+ {
+ if( ( srckey < delbase ) || ( srckey > targetkey ) )
+ continue;
+ }
+ else if( ( srckey > targetkey ) && ( srckey < delbase ) )
+ continue;
+ targetentry = srcentry;
+ targetkey = srckey;
+ targetpos = srcpos;
+ }
+
+ /* No replacement found, just clear it */
+ entry = MM_HASH_ENTRY( table, hashkey );
+ if( !( targetentry ) )
+ {
+ HASH_CLEARENTRY( entry );
+ break;
+ }
+
+ /* Move entry in place and continue the repair process */
+ memcpy( entry, targetentry, table->entrysize );
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->relocationcount, 1 );
+#endif
+
+ hashkey = targetpos;
+ }
+
+ /* Decrement count of entries in table */
+ if( !( table->flags & MM_HASH_FLAGS_NO_COUNT ) )
+ {
+ entrycount = MM_HASH_ENTRYCOUNT_ADD_READ( table, -1 );
+ if( entrycount < table->lowcount )
+ table->status = MM_HASH_STATUS_MUSTSHRINK;
+ }
+
+#ifdef MM_HASH_DEBUG_STATISTICS
+ mmAtomicAddL( &table->statentrycount, -1 );
+#endif
+
+ return MM_HASH_SUCCESS;
+}
+
+#endif
+
+
+////
+
+
Ecere Software / sdk / commitdiff