Inheritance diagram for com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM:

Collaboration diagram for com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM:

Public Member Functions
int	size ()

int	slots ()

Package Functions
	CHM (final NonBlockingHashMapLong nbhml, ConcurrentAutoTable size, final int logsize)

boolean	CAS_newchm (CHM newchm)

void	clear ()

Package Attributes
volatile long	_copyDone = 0

volatile long	_copyIdx = 0

final long[]	_keys

final NonBlockingHashMapLong	_nbhml

volatile CHM	_newchm

volatile long	_resizers

final Object[]	_vals

Private Member Functions
boolean	CAS_key (int idx, long old, long key)

boolean	CAS_val (int idx, Object old, Object val)

void	copy_check_and_promote (int workdone)

boolean	copy_slot (int idx)

CHM	copy_slot_and_check (int idx, Object should_help)

Object	get_impl (final long key)

void	help_copy_impl (final boolean copy_all)

void	print ()

void	print2 ()

Object	putIfMatch (final long key, final Object putval, final Object expVal)

CHM	resize ()

boolean	tableFull (int reprobe_cnt, int len)

Private Attributes
ConcurrentAutoTable	_size

ConcurrentAutoTable	_slots

Static Private Attributes
static final AtomicLongFieldUpdater< CHM >	_copyDoneUpdater

static final AtomicLongFieldUpdater< CHM >	_copyIdxUpdater

static final AtomicReferenceFieldUpdater< CHM, CHM >	_newchmUpdater

static final AtomicLongFieldUpdater< CHM >	_resizerUpdater

static volatile int	DUMMY_VOLATILE

Detailed Description

Definition at line 426 of file NonBlockingHashMapLong.java.

Constructor & Destructor Documentation

◆ CHM()

com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.CHM	(	final NonBlockingHashMapLong	nbhml,
		ConcurrentAutoTable	size,
		final int	logsize
	)

package

Definition at line 490 of file NonBlockingHashMapLong.java.

                                                                                            {
       _nbhml = nbhml;
       _size = size;
       _slots= new ConcurrentAutoTable();
       _keys = new long  [1<<logsize];
       _vals = new Object[1<<logsize];
     }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._keys, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._nbhml, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._size, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._slots, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._vals, and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.size().

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.resize().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Function Documentation

◆ CAS_key()

boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.CAS_key	(	int	idx,
		long	old,
		long	key
	)

private

Definition at line 479 of file NonBlockingHashMapLong.java.

                                                                {
       return UNSAFE.compareAndSwapLong  ( _keys, rawIndex(_keys, idx), old, key );
     }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._keys, and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.rawIndex().

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_slot(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.putIfMatch().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CAS_newchm()

boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.CAS_newchm ( CHM newchm )

package

Definition at line 458 of file NonBlockingHashMapLong.java.

                                      {
       return _newchmUpdater.compareAndSet(this,null,newchm);
     }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._newchmUpdater.

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.resize().

Here is the caller graph for this function:

◆ CAS_val()

boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.CAS_val	(	int	idx,
		Object	old,
		Object	val
	)

private

Definition at line 482 of file NonBlockingHashMapLong.java.

                                                                {
       return UNSAFE.compareAndSwapObject( _vals, rawIndex(_vals, idx), old, val );
     }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._vals, and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.rawIndex().

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_slot(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.putIfMatch().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clear()

void com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.clear ( )

package

Definition at line 498 of file NonBlockingHashMapLong.java.

                  {
       _size = new ConcurrentAutoTable();
       _slots= new ConcurrentAutoTable();
       Arrays.fill(_keys,0);
       Arrays.fill(_vals,null);
     }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._keys, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._size, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._slots, and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._vals.

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.clear().

Here is the caller graph for this function:

◆ copy_check_and_promote()

void com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_check_and_promote ( int workdone )

private

Definition at line 936 of file NonBlockingHashMapLong.java.

                                                         {
       int oldlen = _keys.length;
       // We made a slot unusable and so did some of the needed copy work
       long copyDone = _copyDone;
       long nowDone = copyDone+workdone;
       assert nowDone <= oldlen;
       if( workdone > 0 ) {
         while( !_copyDoneUpdater.compareAndSet(this,copyDone,nowDone) ) {
           copyDone = _copyDone;   // Reload, retry
           nowDone = copyDone+workdone;
           assert nowDone <= oldlen;
         }
       }
  
       // Check for copy being ALL done, and promote.  Note that we might have
       // nested in-progress copies and manage to finish a nested copy before
       // finishing the top-level copy.  We only promote top-level copies.
       if( nowDone == oldlen &&   // Ready to promote this table?
           _nbhml._chm == this && // Looking at the top-level table?
           // Attempt to promote
           _nbhml.CAS(_chm_offset,this,_newchm) ) {
         _nbhml._last_resize_milli = System.currentTimeMillis();  // Record resize time for next check
       }
     }

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_slot_and_check(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.help_copy_impl().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ copy_slot()

boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_slot ( int idx )

private

Definition at line 971 of file NonBlockingHashMapLong.java.

                                          {
       // Blindly set the key slot from NO_KEY to some key which hashes here,
       // to eagerly stop fresh put's from inserting new values in the old
       // table when the old table is mid-resize.  We don't need to act on the
       // results here, because our correctness stems from box'ing the Value
       // field.  Slamming the Key field is a minor speed optimization.
       long key;
       while( (key=_keys[idx]) == NO_KEY )
         CAS_key(idx, NO_KEY, (idx+_keys.length)/*a non-zero key which hashes here*/);
  
       // ---
       // Prevent new values from appearing in the old table.
       // Box what we see in the old table, to prevent further updates.
       Object oldval = _vals[idx]; // Read OLD table
       while( !(oldval instanceof Prime) ) {
         final Prime box = (oldval == null || oldval == TOMBSTONE) ? TOMBPRIME : new Prime(oldval);
         if( CAS_val(idx,oldval,box) ) { // CAS down a box'd version of oldval
           // If we made the Value slot hold a TOMBPRIME, then we both
           // prevented further updates here but also the (absent) oldval is
           // vaccuously available in the new table.  We return with true here:
           // any thread looking for a value for this key can correctly go
           // straight to the new table and skip looking in the old table.
           if( box == TOMBPRIME )
             return true;
           // Otherwise we boxed something, but it still needs to be
           // copied into the new table.
           oldval = box;         // Record updated oldval
           break;                // Break loop; oldval is now boxed by us
         }
         oldval = _vals[idx];    // Else try, try again
       }
       if( oldval == TOMBPRIME ) return false; // Copy already complete here!
  
       // ---
       // Copy the value into the new table, but only if we overwrite a null.
       // If another value is already in the new table, then somebody else
       // wrote something there and that write is happens-after any value that
       // appears in the old table.
       Object old_unboxed = ((Prime)oldval)._V;
       assert old_unboxed != TOMBSTONE;
       boolean copied_into_new = (_newchm.putIfMatch(key, old_unboxed, null) == null);
  
       // ---
       // Finally, now that any old value is exposed in the new table, we can
       // forever hide the old-table value by slapping a TOMBPRIME down.  This
       // will stop other threads from uselessly attempting to copy this slot
       // (i.e., it's a speed optimization not a correctness issue).
       while( oldval != TOMBPRIME && !CAS_val(idx,oldval,TOMBPRIME) )
         oldval = _vals[idx];
  
       return copied_into_new;
     } // end copy_slot

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_slot_and_check(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.help_copy_impl().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ copy_slot_and_check()

CHM com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_slot_and_check	(	int	idx,
		Object	should_help
	)

private

Definition at line 924 of file NonBlockingHashMapLong.java.

                                                                    {
       // We're only here because the caller saw a Prime, which implies a
       // table-copy is in progress.
       assert _newchm != null;
       if( copy_slot(idx) )      // Copy the desired slot
         copy_check_and_promote(1); // Record the slot copied
       // Generically help along any copy (except if called recursively from a helper)
       if( should_help != null ) _nbhml.help_copy();
       return _newchm;
     }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._nbhml, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._newchm, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_check_and_promote(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_slot(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.help_copy().

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.get_impl(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.putIfMatch().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_impl()

Object com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.get_impl ( final long key )

private

Definition at line 535 of file NonBlockingHashMapLong.java.

                                                {
       final int hash = hash(key);
       final int len     = _keys.length;
       int idx = (hash & (len-1)); // First key hash
  
       // Main spin/reprobe loop, looking for a Key hit
       int reprobe_cnt=0;
       while( true ) {
         final long   K = _keys[idx]; // Get key   before volatile read, could be NO_KEY
         final Object V = _vals[idx]; // Get value before volatile read, could be null or Tombstone or Prime
         if( K == NO_KEY ) return null; // A clear miss
  
         // Key-compare
         if( key == K ) {
           // Key hit!  Check for no table-copy-in-progress
           if( !(V instanceof Prime) ) { // No copy?
             if( V == TOMBSTONE) return null;
             // We need a volatile-read between reading a newly inserted Value
             // and returning the Value (so the user might end up reading the
             // stale Value contents).
             @SuppressWarnings("unused") final CHM newchm = _newchm; // VOLATILE READ before returning V
             return V;
           }
           // Key hit - but slot is (possibly partially) copied to the new table.
           // Finish the copy & retry in the new table.
           return copy_slot_and_check(idx,key).get_impl(key); // Retry in the new table
         }
         // get and put must have the same key lookup logic!  But only 'put'
         // needs to force a table-resize for a too-long key-reprobe sequence.
         // Check for too-many-reprobes on get.
         if( ++reprobe_cnt >= reprobe_limit(len) ) // too many probes
           return _newchm == null // Table copy in progress?
             ? null               // Nope!  A clear miss
             : copy_slot_and_check(idx,key).get_impl(key); // Retry in the new table
  
         idx = (idx+1)&(len-1);    // Reprobe by 1!  (could now prefetch)
       }
     }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._keys, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._newchm, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._vals, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_slot_and_check(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.get_impl(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.hash(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.NO_KEY, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.reprobe_limit(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.TOMBSTONE.

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.get(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.get_impl().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ help_copy_impl()

void com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.help_copy_impl ( final boolean copy_all )

private

Definition at line 861 of file NonBlockingHashMapLong.java.

                                                           {
       final CHM newchm = _newchm;
       assert newchm != null;    // Already checked by caller
       int oldlen = _keys.length; // Total amount to copy
       final int MIN_COPY_WORK = Math.min(oldlen,1024); // Limit per-thread work
  
       // ---
       int panic_start = -1;
       int copyidx=-9999;            // Fool javac to think it's initialized
       while( _copyDone < oldlen ) { // Still needing to copy?
         // Carve out a chunk of work.  The counter wraps around so every
         // thread eventually tries to copy every slot repeatedly.
  
         // We "panic" if we have tried TWICE to copy every slot - and it still
         // has not happened.  i.e., twice some thread somewhere claimed they
         // would copy 'slot X' (by bumping _copyIdx) but they never claimed to
         // have finished (by bumping _copyDone).  Our choices become limited:
         // we can wait for the work-claimers to finish (and become a blocking
         // algorithm) or do the copy work ourselves.  Tiny tables with huge
         // thread counts trying to copy the table often 'panic'.
         if( panic_start == -1 ) { // No panic?
           copyidx = (int)_copyIdx;
           while( copyidx < (oldlen<<1) && // 'panic' check
                  !_copyIdxUpdater.compareAndSet(this,copyidx,copyidx+MIN_COPY_WORK) )
             copyidx = (int)_copyIdx;     // Re-read
           if( !(copyidx < (oldlen<<1)) ) // Panic!
             panic_start = copyidx;       // Record where we started to panic-copy
         }
  
         // We now know what to copy.  Try to copy.
         int workdone = 0;
         for( int i=0; i<MIN_COPY_WORK; i++ )
           if( copy_slot((copyidx+i)&(oldlen-1)) ) // Made an oldtable slot go dead?
             workdone++;         // Yes!
         if( workdone > 0 )      // Report work-done occasionally
           copy_check_and_promote( workdone );// See if we can promote
         //for( int i=0; i<MIN_COPY_WORK; i++ )
         //  if( copy_slot((copyidx+i)&(oldlen-1)) ) // Made an oldtable slot go dead?
         //    copy_check_and_promote( 1 );// See if we can promote
  
         copyidx += MIN_COPY_WORK;
         // Uncomment these next 2 lines to turn on incremental table-copy.
         // Otherwise this thread continues to copy until it is all done.
         if( !copy_all && panic_start == -1 ) // No panic?
           return;               // Then done copying after doing MIN_COPY_WORK
       }
       // Extra promotion check, in case another thread finished all copying
       // then got stalled before promoting.
       copy_check_and_promote( 0 ); // See if we can promote
     }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._copyDone, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._copyIdx, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._copyIdxUpdater, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._keys, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._newchm, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_check_and_promote(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_slot().

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.help_copy(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.SnapshotV.SnapshotV().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ print()

void com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.print ( )

private

Definition at line 506 of file NonBlockingHashMapLong.java.

                          {
       for( int i=0; i<_keys.length; i++ ) {
         long K = _keys[i];
         if( K != NO_KEY )
           print_impl(i,K,_vals[i]);
       }
       CHM newchm = _newchm;     // New table, if any
       if( newchm != null ) {
         System.out.println("----");
         newchm.print();
       }
     }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._keys, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._newchm, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._vals, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.NO_KEY, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.print(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.print_impl().

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.print(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.print(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.print2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ print2()

void com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.print2 ( )

private

Definition at line 520 of file NonBlockingHashMapLong.java.

                            {
       for( int i=0; i<_keys.length; i++ ) {
         long K = _keys[i];
         if( K != NO_KEY )       // key is sane
           print2_impl(i,K,_vals[i]);
       }
       CHM newchm = _newchm;     // New table, if any
       if( newchm != null ) {
         System.out.println("----");
         newchm.print2();
       }
     }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._keys, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._newchm, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._vals, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.NO_KEY, com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.print2(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.print2_impl().

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.print2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ putIfMatch()

Object com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.putIfMatch	(	final long	key,
		final Object	putval,
		final Object	expVal
	)

private

Definition at line 581 of file NonBlockingHashMapLong.java.

                                                                                           {
       final int hash = hash(key);
       assert putval != null;
       assert !(putval instanceof Prime);
       assert !(expVal instanceof Prime);
       final int len      = _keys.length;
       int idx = (hash & (len-1)); // The first key
  
       // ---
       // Key-Claim stanza: spin till we can claim a Key (or force a resizing).
       int reprobe_cnt=0;
       long   K;
       Object V;
       while( true ) {           // Spin till we get a Key slot
         V = _vals[idx];         // Get old value
         K = _keys[idx];         // Get current key
         if( K == NO_KEY ) {     // Slot is free?
           // Found an empty Key slot - which means this Key has never been in
           // this table.  No need to put a Tombstone - the Key is not here!
           if( putval == TOMBSTONE ) return TOMBSTONE; // Not-now & never-been in this table
           if( expVal == MATCH_ANY ) return TOMBSTONE; // Will not match, even after K inserts
           // Claim the zero key-slot
           if( CAS_key(idx, NO_KEY, key) ) { // Claim slot for Key
             _slots.add(1);      // Raise key-slots-used count
             break;              // Got it!
           }
           // CAS to claim the key-slot failed.
           //
           // This re-read of the Key points out an annoying short-coming of Java
           // CAS.  Most hardware CAS's report back the existing value - so that
           // if you fail you have a *witness* - the value which caused the CAS
           // to fail.  The Java API turns this into a boolean destroying the
           // witness.  Re-reading does not recover the witness because another
           // thread can write over the memory after the CAS.  Hence we can be in
           // the unfortunate situation of having a CAS fail *for cause* but
           // having that cause removed by a later store.  This turns a
           // non-spurious-failure CAS (such as Azul has) into one that can
           // apparently spuriously fail - and we avoid apparent spurious failure
           // by not allowing Keys to ever change.
           K = _keys[idx];       // CAS failed, get updated value
           assert K != NO_KEY ;  // If keys[idx] is NO_KEY, CAS shoulda worked
         }
         // Key slot was not null, there exists a Key here
         if( K == key )
           break;                // Got it!
  
         // get and put must have the same key lookup logic!  Lest 'get' give
         // up looking too soon.
         //topmap._reprobes.add(1);
         if( ++reprobe_cnt >= reprobe_limit(len) ) {
           // We simply must have a new table to do a 'put'.  At this point a
           // 'get' will also go to the new table (if any).  We do not need
           // to claim a key slot (indeed, we cannot find a free one to claim!).
           final CHM newchm = resize();
           if( expVal != null ) _nbhml.help_copy(); // help along an existing copy
           return newchm.putIfMatch(key,putval,expVal);
         }
  
         idx = (idx+1)&(len-1); // Reprobe!
       } // End of spinning till we get a Key slot
  
       while ( true ) {              // Spin till we insert a value
         // ---
         // Found the proper Key slot, now update the matching Value slot.  We
         // never put a null, so Value slots monotonically move from null to
         // not-null (deleted Values use Tombstone).  Thus if 'V' is null we
         // fail this fast cutout and fall into the check for table-full.
         if( putval == V ) return V; // Fast cutout for no-change
  
         // See if we want to move to a new table (to avoid high average re-probe
         // counts).  We only check on the initial set of a Value from null to
         // not-null (i.e., once per key-insert).
         if( (V == null && tableFull(reprobe_cnt,len)) ||
             // Or we found a Prime: resize is already in progress.  The resize
             // call below will do a CAS on _newchm forcing the read.
             V instanceof Prime) {
           resize();               // Force the new table copy to start
           return copy_slot_and_check(idx,expVal).putIfMatch(key,putval,expVal);
         }
  
         // ---
         // We are finally prepared to update the existing table
         //assert !(V instanceof Prime); // always true, so IDE warnings if uncommented
  
         // Must match old, and we do not?  Then bail out now.  Note that either V
         // or expVal might be TOMBSTONE.  Also V can be null, if we've never
         // inserted a value before.  expVal can be null if we are called from
         // copy_slot.
  
         if( expVal != NO_MATCH_OLD && // Do we care about expected-Value at all?
             V != expVal &&            // No instant match already?
             (expVal != MATCH_ANY || V == TOMBSTONE || V == null) &&
             !(V==null && expVal == TOMBSTONE) &&    // Match on null/TOMBSTONE combo
             (expVal == null || !expVal.equals(V)) ) // Expensive equals check at the last
           return (V==null) ? TOMBSTONE : V;         // Do not update!
  
         // Actually change the Value in the Key,Value pair
         if( CAS_val(idx, V, putval ) ) break;
  
         // CAS failed
         // Because we have no witness, we do not know why it failed.
         // Indeed, by the time we look again the value under test might have flipped
         // a thousand times and now be the expected value (despite the CAS failing).
         // Check for the never-succeed condition of a Prime value and jump to any
         // nested table, or else just re-run.
  
         // We would not need this load at all if CAS returned the value on which
         // the CAS failed (AKA witness). The new CAS semantics are supported via
         // VarHandle in JDK9.
         V = _vals[idx];         // Get new value
  
         // If a Prime'd value got installed, we need to re-run the put on the
         // new table.  Otherwise we lost the CAS to another racing put.
         // Simply retry from the start.
         if( V instanceof Prime )
           return copy_slot_and_check(idx,expVal).putIfMatch(key,putval,expVal);
  
         // Simply retry from the start.
         // NOTE: need the fence, since otherwise '_vals[idx]' load could be hoisted
         // out of loop.
         int dummy = DUMMY_VOLATILE;
       }
  
       // CAS succeeded - we did the update!
       // Both normal put's and table-copy calls putIfMatch, but table-copy
       // does not (effectively) increase the number of live k/v pairs.
       if( expVal != null ) {
         // Adjust sizes - a striped counter
         if(  (V == null || V == TOMBSTONE) && putval != TOMBSTONE ) _size.add( 1);
         if( !(V == null || V == TOMBSTONE) && putval == TOMBSTONE ) _size.add(-1);
       }
  
       // We won; we know the update happened as expected.
       return (V==null && expVal!=null) ? TOMBSTONE : V;
     }

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.copy_slot(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.putIfMatch(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.putIfMatch().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ resize()

CHM com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.resize ( )

private

Definition at line 741 of file NonBlockingHashMapLong.java.

                          {
       // Check for resize already in progress, probably triggered by another thread
       CHM newchm = _newchm;     // VOLATILE READ
       if( newchm != null )      // See if resize is already in progress
         return newchm;          // Use the new table already
  
       // No copy in-progress, so start one.  First up: compute new table size.
       int oldlen = _keys.length; // Old count of K,V pairs allowed
       int sz = size();          // Get current table count of active K,V pairs
       int newsz = sz;           // First size estimate
  
       // Heuristic to determine new size.  We expect plenty of dead-slots-with-keys
       // and we need some decent padding to avoid endless reprobing.
       if( _nbhml._opt_for_space ) {
         // This heuristic leads to a much denser table with a higher reprobe rate
         if( sz >= (oldlen>>1) ) // If we are >50% full of keys then...
           newsz = oldlen<<1;    // Double size
       } else {
         if( sz >= (oldlen>>2) ) { // If we are >25% full of keys then...
           newsz = oldlen<<1;      // Double size
           if( sz >= (oldlen>>1) ) // If we are >50% full of keys then...
             newsz = oldlen<<2;    // Double double size
         }
       }
  
       // Last (re)size operation was very recent?  Then double again
       // despite having few live keys; slows down resize operations
       // for tables subject to a high key churn rate - but do not
       // forever grow the table.  If there is a high key churn rate
       // the table needs a steady state of rare same-size resize
       // operations to clean out the dead keys.
       long tm = System.currentTimeMillis();
       if( newsz <= oldlen &&    // New table would shrink or hold steady?
           tm <= _nbhml._last_resize_milli+10000)  // Recent resize (less than 10 sec ago)
         newsz = oldlen<<1;      // Double the existing size
  
       // Do not shrink, ever.  If we hit this size once, assume we
       // will again.
       if( newsz < oldlen ) newsz = oldlen;
  
       // Convert to power-of-2
       int log2;
       for( log2=MIN_SIZE_LOG; (1<<log2) < newsz; log2++ ) ; // Compute log2 of size
       long len = ((1L << log2) << 1) + 2;
       // prevent integer overflow - limit of 2^31 elements in a Java array
       // so here, 2^30 + 2 is the largest number of elements in the hash table
       if ((int)len!=len) {
         log2 = 30;
         len = (1L << log2) + 2;
         if (sz > ((len >> 2) + (len >> 1))) throw new RuntimeException("Table is full.");
       }
  
       // Now limit the number of threads actually allocating memory to a
       // handful - lest we have 750 threads all trying to allocate a giant
       // resized array.
       long r = _resizers;
       while( !_resizerUpdater.compareAndSet(this,r,r+1) )
         r = _resizers;
       // Size calculation: 2 words (K+V) per table entry, plus a handful.  We
       // guess at 64-bit pointers; 32-bit pointers screws up the size calc by
       // 2x but does not screw up the heuristic very much.
       long megs = ((((1L<<log2)<<1)+8)<<3/*word to bytes*/)>>20/*megs*/;
       if( r >= 2 && megs > 0 ) { // Already 2 guys trying; wait and see
         newchm = _newchm;        // Between dorking around, another thread did it
         if( newchm != null )     // See if resize is already in progress
           return newchm;         // Use the new table already
         // We could use a wait with timeout, so we'll wakeup as soon as the new table
         // is ready, or after the timeout in any case.
         //synchronized( this ) { wait(8*megs); }         // Timeout - we always wakeup
         // For now, sleep a tad and see if the 2 guys already trying to make
         // the table actually get around to making it happen.
         try { Thread.sleep(megs); } catch( Exception e ) { /*empty*/}
       }
       // Last check, since the 'new' below is expensive and there is a chance
       // that another thread slipped in a new thread while we ran the heuristic.
       newchm = _newchm;
       if( newchm != null )      // See if resize is already in progress
         return newchm;          // Use the new table already
  
       // New CHM - actually allocate the big arrays
       newchm = new CHM(_nbhml,_size,log2);
  
       // Another check after the slow allocation
       if( _newchm != null )     // See if resize is already in progress
         return _newchm;         // Use the new table already
  
       // The new table must be CAS'd in so only 1 winner amongst duplicate
       // racing resizing threads.  Extra CHM's will be GC'd.
       if( CAS_newchm( newchm ) ) { // NOW a resize-is-in-progress!
         //notifyAll();            // Wake up any sleepers
         //long nano = System.nanoTime();
         //System.out.println(" "+nano+" Resize from "+oldlen+" to "+(1<<log2)+" and had "+(_resizers-1)+" extras" );
         //System.out.print("["+log2);
       } else                    // CAS failed?
         newchm = _newchm;       // Reread new table
       return newchm;
     }

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.putIfMatch().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ size()

int com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.size ( )

Definition at line 432 of file NonBlockingHashMapLong.java.

432 { return (int)_size.get(); }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._size, and com.cliffc.aa.util.ConcurrentAutoTable.get().

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.CHM(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.resize(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.size().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ slots()

int com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.slots ( )

Definition at line 445 of file NonBlockingHashMapLong.java.

445 { return (int)_slots.get(); }

References com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM._slots, and com.cliffc.aa.util.ConcurrentAutoTable.get().

Here is the call graph for this function:

◆ tableFull()

boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CHM.tableFull	(	int	reprobe_cnt,
		int	len
	)

private

Definition at line 726 of file NonBlockingHashMapLong.java.

                                                           {
       return
         // Do the cheap check first: we allow some number of reprobes always
         reprobe_cnt >= REPROBE_LIMIT &&
         (reprobe_cnt >= reprobe_limit(len) ||
          // More expensive check: see if the table is > 1/2 full.
          _slots.estimate_get() >= (len>>1));
     }