aa
Classes | Public Member Functions | Static Public Attributes | Protected Member Functions | Static Package Functions | Static Package Attributes | Private Member Functions | Static Private Member Functions | Private Attributes | Static Private Attributes | List of all members
com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV > Class Template Reference

A lock-free alternate implementation of java.util.concurrent.ConcurrentHashMap with better scaling properties and generally lower costs to mutate the Map. More...

Inheritance diagram for com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >:
[legend]
Collaboration diagram for com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >:
[legend]

Classes

class  CHM
 
class  NBHMEntry
 
class  Prime
 
class  SnapshotE
 
class  SnapshotK
 
class  SnapshotV
 

Public Member Functions

 NonBlockingHashMap ()
 Create a new NonBlockingHashMap with default minimum size (currently set to 8 K/V pairs or roughly 84 bytes on a standard 32-bit JVM). More...
 
 NonBlockingHashMap (final int initial_sz)
 Create a new NonBlockingHashMap with initial room for the given number of elements, thus avoiding internal resizing operations to reach an appropriate size. More...
 
void clear ()
 Removes all of the mappings from this map. More...
 
Object clone ()
 Creates a shallow copy of this hashtable. More...
 
boolean contains (Object val)
 Legacy method testing if some key maps into the specified value in this table. More...
 
boolean containsKey (Object key)
 Tests if the key in the table using the equals method. More...
 
boolean containsValue (final Object val)
 Returns true if this Map maps one or more keys to the specified value. More...
 
Enumeration< TypeV > elements ()
 Returns an enumeration of the values in this table. More...
 
Set< Map.Entry< TypeK, TypeV > > entrySet ()
 Returns a Set view of the mappings contained in this map. More...
 
TypeV get (Object key)
 Returns the value to which the specified key is mapped, or. More...
 
TypeK getk (TypeK key)
 Returns the Key to which the specified key is mapped, or. More...
 
TypeK getKey ()
 
boolean isEmpty ()
 Returns size() == 0. More...
 
Enumeration< TypeK > keys ()
 Returns an enumeration of the keys in this table. More...
 
Set< TypeK > keySet ()
 Returns a Set view of the keys contained in this map. More...
 
final void print ()
 Verbose printout of table internals, useful for debugging. More...
 
TypeV put (TypeK key, TypeV val)
 Maps the specified key to the specified value in the table. More...
 
void putAll (Map<? extends TypeK, ? extends TypeV > m)
 Copies all of the mappings from the specified map to this one, replacing any existing mappings. More...
 
TypeV putIfAbsent (TypeK key, TypeV val)
 Atomically, do a put if-and-only-if the key is not mapped. More...
 
final TypeV putIfMatchAllowNull (Object key, Object newVal, Object oldVal)
 
Object[] raw_array ()
 
TypeV remove (Object key)
 Removes the key (and its corresponding value) from this map. More...
 
boolean remove (Object key, Object val)
 Atomically do a remove(Object) if-and-only-if the key is mapped to a value which is equals to the given value. More...
 
boolean replace (TypeK key, TypeV oldValue, TypeV newValue)
 Atomically do a put(key,newValue) if-and-only-if the key is mapped a value which is equals to oldValue. More...
 
TypeV replace (TypeK key, TypeV val)
 Atomically do a put(key,val) if-and-only-if the key is mapped to some value already. More...
 
long reprobes ()
 Get and clear the current count of reprobes. More...
 
int size ()
 Returns the number of key-value mappings in this map. More...
 
String toString ()
 Returns a string representation of this map. More...
 
Collection< TypeV > values ()
 Returns a Collection view of the values contained in this map. More...
 

Static Public Attributes

static final Object TOMBSTONE = new Object()
 

Protected Member Functions

final void initialize ()
 
void rehash ()
 

Static Package Functions

 [static initializer]
 

Static Package Attributes

static volatile int DUMMY_VOLATILE
 

Private Member Functions

boolean CAS_kvs (final Object[] oldkvs, final Object[] newkvs)
 
final Object[] help_copy (Object[] helper)
 
final void initialize (int initial_sz)
 
final void print (Object[] kvs)
 
final void print2 (Object[] kvs)
 
final TypeV putIfMatch (Object key, Object newVal, Object oldVal)
 
void readObject (java.io.ObjectInputStream s) throws IOException, ClassNotFoundException
 
void writeObject (java.io.ObjectOutputStream s) throws IOException
 

Static Private Member Functions

static Object _getKey (Object[] kvs)
 
static final boolean CAS_key (Object[] kvs, int idx, Object old, Object key)
 
static final boolean CAS_val (Object[] kvs, int idx, Object old, Object val)
 
static final CHM chm (Object[] kvs)
 
static Object get_impl (final NonBlockingHashMap topmap, final Object[] kvs, final Object key)
 
static final Object getk_impl (final NonBlockingHashMap topmap, final Object[] kvs, final Object key)
 
static int hash (final Object key)
 
static final int[] hashes (Object[] kvs)
 
static final Object key (Object[] kvs, int idx)
 
static boolean keyeq (Object K, Object key, int[] hashes, int hash, int fullhash)
 
static final int len (Object[] kvs)
 
static final Object putIfMatch (final NonBlockingHashMap topmap, final Object[] kvs, final Object key, final Object putval, final Object expVal)
 
static long rawIndex (final Object[] ary, final int idx)
 
static final int reprobe_limit (int len)
 
static final Object val (Object[] kvs, int idx)
 

Private Attributes

transient Object[] _kvs
 
transient long _last_resize_milli
 
transient ConcurrentAutoTable _reprobes = new ConcurrentAutoTable()
 

Static Private Attributes

static final long _kvs_offset
 
static final int _Obase = _unsafe.arrayBaseOffset(Object[].class)
 
static final int _Olog = _Oscale==4?2:(_Oscale==8?3:9999)
 
static final int _Oscale = _unsafe.arrayIndexScale(Object[].class)
 
static final Unsafe _unsafe = UtilUnsafe.getUnsafe()
 
static final Object MATCH_ANY = new Object()
 
static final int MIN_SIZE =(1<<MIN_SIZE_LOG)
 
static final int MIN_SIZE_LOG =3
 
static final Object NO_MATCH_OLD = new Object()
 
static final int REPROBE_LIMIT =10
 
static final long serialVersionUID = 1234123412341234123L
 
static final Prime TOMBPRIME = new Prime(TOMBSTONE)
 

Detailed Description

A lock-free alternate implementation of java.util.concurrent.ConcurrentHashMap with better scaling properties and generally lower costs to mutate the Map.

It provides identical correctness properties as ConcurrentHashMap. All operations are non-blocking and multi-thread safe, including all update operations. NonBlockingHashMap scales substantially better than java.util.concurrent.ConcurrentHashMap for high update rates, even with a large concurrency factor. Scaling is linear up to 768 CPUs on a 768-CPU Azul box, even with 100% updates or 100% reads or any fraction in-between. Linear scaling up to all cpus has been observed on a 32-way Sun US2 box, 32-way Sun Niagara box, 8-way Intel box and a 4-way Power box.

This class obeys the same functional specification as {}, and includes versions of methods corresponding to each method of Hashtable. However, even though all operations are thread-safe, operations do not entail locking and there is not any support for locking the entire table in a way that prevents all access. This class is fully interoperable with Hashtable in programs that rely on its thread safety but not on its synchronization details. Operations (including put) generally do not block, so may overlap with other update operations (including other puts and removes). Retrievals reflect the results of the most recently completed update operations holding upon their onset. For aggregate operations such as putAll, concurrent retrievals may reflect insertion or removal of only some entries. Similarly, Iterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration. They do not throw ConcurrentModificationException. However, iterators are designed to be used by only one thread at a time.

Very full tables, or tables with high reprobe rates may trigger an internal resize operation to move into a larger table. Resizing is not terribly expensive, but it is not free either; during resize operations table throughput may drop somewhat. All threads that visit the table during a resize will 'help' the resizing but will still be allowed to complete their operation before the resize is finished (i.e., a simple 'get' operation on a million-entry table undergoing resizing will not need to block until the entire million entries are copied).

This class and its views and iterators implement all of the optional methods of the Map and Iterator interfaces.

Like Hashtable but unlike HashMap, this class does not allow null to be used as a key or value.

Since
1.5
Author
Cliff Click
Parameters
<TypeK>the type of keys maintained by this map
<TypeV>the type of mapped values

Definition at line 73 of file NonBlockingHashMap.java.

Constructor & Destructor Documentation

◆ NonBlockingHashMap() [1/2]

com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.NonBlockingHashMap ( )

Create a new NonBlockingHashMap with default minimum size (currently set to 8 K/V pairs or roughly 84 bytes on a standard 32-bit JVM).

Definition at line 251 of file NonBlockingHashMap.java.

251 { this(MIN_SIZE); }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.clear().

Here is the caller graph for this function:

◆ NonBlockingHashMap() [2/2]

com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.NonBlockingHashMap ( final int  initial_sz)

Create a new NonBlockingHashMap with initial room for the given number of elements, thus avoiding internal resizing operations to reach an appropriate size.

Large numbers here when used with a small count of elements will sacrifice space for a small amount of time gained. The initial size will be rounded up internally to the next larger power of 2.

Definition at line 258 of file NonBlockingHashMap.java.

258 { initialize(initial_sz); }

Member Function Documentation

◆ [static initializer]()

com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.[static initializer]
staticpackage

◆ _getKey()

static Object com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >._getKey ( Object[]  kvs)
staticprivate

Definition at line 478 of file NonBlockingHashMap.java.

478  {
479  for( int i=0; i<len(kvs); i++ ) {
480  Object key = key(kvs,i);
481  Object val = val(kvs,i);
482  Object U = Prime.unbox(val);
483  if( key != null && key != TOMBSTONE && // key is sane
484  val != null && U != TOMBSTONE ) // val is sane
485  return key;
486  }
487  Object[] newkvs = chm(kvs)._newkvs; // New table, if any
488  return newkvs == null ? null : _getKey(newkvs);
489  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >._getKey(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getKey().

Here is the caller graph for this function:

◆ CAS_key()

static final boolean com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CAS_key ( Object[]  kvs,
int  idx,
Object  old,
Object  key 
)
staticprivate

Definition at line 174 of file NonBlockingHashMap.java.

174  {
175  return _unsafe.compareAndSwapObject( kvs, rawIndex(kvs,(idx<<1)+2), old, key );
176  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_slot(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch().

Here is the caller graph for this function:

◆ CAS_kvs()

boolean com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CAS_kvs ( final Object[]  oldkvs,
final Object[]  newkvs 
)
private

Definition at line 101 of file NonBlockingHashMap.java.

101  {
102  return _unsafe.compareAndSwapObject(this, _kvs_offset, oldkvs, newkvs );
103  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.clear(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_check_and_promote().

Here is the caller graph for this function:

◆ CAS_val()

static final boolean com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CAS_val ( Object[]  kvs,
int  idx,
Object  old,
Object  val 
)
staticprivate

Definition at line 177 of file NonBlockingHashMap.java.

177  {
178  return _unsafe.compareAndSwapObject( kvs, rawIndex(kvs,(idx<<1)+3), old, val );
179  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_slot(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch().

Here is the caller graph for this function:

◆ chm()

static final CHM com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.chm ( Object[]  kvs)
staticprivate

Definition at line 135 of file NonBlockingHashMap.java.

135 { return (CHM )kvs[0]; }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >._getKey(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_check_and_promote(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_slot_and_check(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.help_copy(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.help_copy_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print2(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.resize(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.size(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.SnapshotV.SnapshotV().

Here is the caller graph for this function:

◆ clear()

void com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.clear ( )

Removes all of the mappings from this map.

Definition at line 381 of file NonBlockingHashMap.java.

381  { // Smack a new empty table down
382  Object[] newkvs = new NonBlockingHashMap(MIN_SIZE)._kvs;
383  while( !CAS_kvs(_kvs,newkvs) ) // Spin until the clear works
384  ;
385  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.clone(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.entrySet(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.keySet(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.values().

Here is the caller graph for this function:

◆ clone()

Object com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.clone ( )

Creates a shallow copy of this hashtable.

All the structure of the hashtable itself is copied, but the keys and values are not cloned. This is a relatively expensive operation.

Returns
a clone of the hashtable.

Definition at line 417 of file NonBlockingHashMap.java.

417  {
418  try {
419  // Must clone, to get the class right; NBHM might have been
420  // extended so it would be wrong to just make a new NBHM.
421  NonBlockingHashMap<TypeK,TypeV> t = (NonBlockingHashMap<TypeK,TypeV>) super.clone();
422  // But I don't have an atomic clone operation - the underlying _kvs
423  // structure is undergoing rapid change. If I just clone the _kvs
424  // field, the CHM in _kvs[0] won't be in sync.
425  //
426  // Wipe out the cloned array (it was shallow anyways).
427  t.clear();
428  // Now copy sanely
429  for( TypeK K : keySet() ) {
430  final TypeV V = get(K); // Do an official 'get'
431  t.put(K,V);
432  }
433  return t;
434  } catch (CloneNotSupportedException e) {
435  // this shouldn't happen, since we are Cloneable
436  throw new InternalError();
437  }
438  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.clone().

Here is the caller graph for this function:

◆ contains()

boolean com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.contains ( Object  val)

Legacy method testing if some key maps into the specified value in this table.

This method is identical in functionality to {}, and exists solely to ensure full compatibility with class java.util.Hashtable}, which supported this method prior to introduction of the Java Collections framework. val a value to search for true if this map maps one or more keys to the specified value NullPointerException if the specified value is null

Definition at line 298 of file NonBlockingHashMap.java.

298 { return containsValue(val); }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.entrySet(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.keySet(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.values().

Here is the caller graph for this function:

◆ containsKey()

boolean com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.containsKey ( Object  key)

Tests if the key in the table using the equals method.

Returns
true if the key is in the table using the equals method
Exceptions
NullPointerExceptionif the specified key is null

Definition at line 288 of file NonBlockingHashMap.java.

288 { return get(key) != null; }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.keySet().

Here is the caller graph for this function:

◆ containsValue()

boolean com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.containsValue ( final Object  val)

Returns true if this Map maps one or more keys to the specified value.

Note: This method requires a full internal traversal of the hash table and is much slower than containsKey.

Parameters
valvalue whose presence in this map is to be tested
Returns
true if this map maps one or more keys to the specified value
Exceptions
NullPointerExceptionif the specified value is null

Definition at line 394 of file NonBlockingHashMap.java.

394  {
395  if( val == null ) throw new NullPointerException();
396  for( TypeV V : values() )
397  if( V == val || V.equals(val) )
398  return true;
399  return false;
400  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.contains(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.values().

Here is the caller graph for this function:

◆ elements()

Enumeration<TypeV> com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.elements ( )

Returns an enumeration of the values in this table.

Returns
an enumeration of the values in this table
See also
values()

Definition at line 1248 of file NonBlockingHashMap.java.

1248 { return new SnapshotV(); }

◆ entrySet()

Set<Map.Entry<TypeK,TypeV> > com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.entrySet ( )

Returns a Set view of the mappings contained in this map.

The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

Warning: the iterator associated with this Set requires the creation of java.util.Map.Entry objects with each iteration. The NonBlockingHashMap does not normally create or using java.util.Map.Entry objects so they will be created soley to support this iteration. Iterating using keySet or {} will be more efficient.

Definition at line 1358 of file NonBlockingHashMap.java.

1358  {
1359  return new AbstractSet<Map.Entry<TypeK,TypeV>>() {
1360  @Override public void clear ( ) { NonBlockingHashMap.this.clear( ); }
1361  @Override public int size ( ) { return NonBlockingHashMap.this.size ( ); }
1362  @Override public boolean remove( final Object o ) {
1363  if( !(o instanceof Map.Entry)) return false;
1364  final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1365  return NonBlockingHashMap.this.remove(e.getKey(), e.getValue());
1366  }
1367  @Override public boolean contains(final Object o) {
1368  if( !(o instanceof Map.Entry)) return false;
1369  final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1370  TypeV v = get(e.getKey());
1371  return v.equals(e.getValue());
1372  }
1373  @Override public Iterator<Map.Entry<TypeK,TypeV>> iterator() { return new SnapshotE(); }
1374  };
1375  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.toString().

Here is the caller graph for this function:

◆ get()

TypeV com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.get ( Object  key)

Returns the value to which the specified key is mapped, or.

null

if this map contains no mapping for the key.

More formally, if this map contains a mapping from a key

k

to a value

v

such that

key.equals(k)

, then this method returns

v

; otherwise it returns

null

. (There can be at most one such mapping.)

Exceptions
NullPointerExceptionif the specified key is null

Definition at line 524 of file NonBlockingHashMap.java.

524  {
525  final Object V = get_impl(this,_kvs,key);
526  assert !(V instanceof Prime); // Never return a Prime
527  assert V != TOMBSTONE;
528  return (TypeV)V;
529  }

◆ get_impl()

static Object com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.get_impl ( final NonBlockingHashMap< TypeK, TypeV >  topmap,
final Object[]  kvs,
final Object  key 
)
staticprivate

Definition at line 531 of file NonBlockingHashMap.java.

531  {
532  final int fullhash= hash (key); // throws NullPointerException if key is null
533  final int len = len (kvs); // Count of key/value pairs, reads kvs.length
534  final CHM chm = chm (kvs); // The CHM, for a volatile read below; reads slot 0 of kvs
535  final int[] hashes=hashes(kvs); // The memoized hashes; reads slot 1 of kvs
536 
537  int idx = fullhash & (len-1); // First key hash
538 
539  // Main spin/reprobe loop, looking for a Key hit
540  int reprobe_cnt=0;
541  while( true ) {
542  // Probe table. Each read of 'val' probably misses in cache in a big
543  // table; hopefully the read of 'key' then hits in cache.
544  final Object K = key(kvs,idx); // Get key before volatile read, could be null
545  final Object V = val(kvs,idx); // Get value before volatile read, could be null or Tombstone or Prime
546  if( K == null ) return null; // A clear miss
547 
548  // We need a volatile-read here to preserve happens-before semantics on
549  // newly inserted Keys. If the Key body was written just before inserting
550  // into the table a Key-compare here might read the uninitialized Key body.
551  // Annoyingly this means we have to volatile-read before EACH key compare.
552  // .
553  // We also need a volatile-read between reading a newly inserted Value
554  // and returning the Value (so the user might end up reading the stale
555  // Value contents). Same problem as with keys - and the one volatile
556  // read covers both.
557  final Object[] newkvs = chm._newkvs; // VOLATILE READ before key compare
558 
559  // Key-compare
560  if( keyeq(K,key,hashes,idx,fullhash) ) {
561  // Key hit! Check for no table-copy-in-progress
562  if( !(V instanceof Prime) ) // No copy?
563  return (V == TOMBSTONE) ? null : V; // Return the value
564  // Key hit - but slot is (possibly partially) copied to the new table.
565  // Finish the copy & retry in the new table.
566  return get_impl(topmap,chm.copy_slot_and_check(topmap,kvs,idx,key),key); // Retry in the new table
567  }
568  // get and put must have the same key lookup logic! But only 'put'
569  // needs to force a table-resize for a too-long key-reprobe sequence.
570  // Check for too-many-reprobes on get - and flip to the new table.
571  if( ++reprobe_cnt >= reprobe_limit(len) || // too many probes
572  K == TOMBSTONE ) // found a TOMBSTONE key, means no more keys in this table
573  return newkvs == null ? null : get_impl(topmap,topmap.help_copy(newkvs),key); // Retry in the new table
574 
575  idx = (idx+1)&(len-1); // Reprobe by 1! (could now prefetch)
576  }
577  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl().

Here is the caller graph for this function:

◆ getk()

TypeK com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.getk ( TypeK  key)

Returns the Key to which the specified key is mapped, or.

null

if this map contains no mapping for the key.

Exceptions
NullPointerExceptionif the specified key is null

Definition at line 585 of file NonBlockingHashMap.java.

585  {
586  return (TypeK)getk_impl(this,_kvs,key);
587  }

◆ getk_impl()

static final Object com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.getk_impl ( final NonBlockingHashMap< TypeK, TypeV >  topmap,
final Object[]  kvs,
final Object  key 
)
staticprivate

Definition at line 589 of file NonBlockingHashMap.java.

589  {
590  final int fullhash= hash (key); // throws NullPointerException if key is null
591  final int len = len (kvs); // Count of key/value pairs, reads kvs.length
592  final CHM chm = chm (kvs); // The CHM, for a volatile read below; reads slot 0 of kvs
593  final int[] hashes=hashes(kvs); // The memoized hashes; reads slot 1 of kvs
594 
595  int idx = fullhash & (len-1); // First key hash
596 
597  // Main spin/reprobe loop, looking for a Key hit
598  int reprobe_cnt=0;
599  while( true ) {
600  // Probe table.
601  final Object K = key(kvs,idx); // Get key before volatile read, could be null
602  if( K == null ) return null; // A clear miss
603 
604  // We need a volatile-read here to preserve happens-before semantics on
605  // newly inserted Keys. If the Key body was written just before inserting
606  // into the table a Key-compare here might read the uninitialized Key body.
607  // Annoyingly this means we have to volatile-read before EACH key compare.
608  // .
609  // We also need a volatile-read between reading a newly inserted Value
610  // and returning the Value (so the user might end up reading the stale
611  // Value contents). Same problem as with keys - and the one volatile
612  // read covers both.
613  final Object[] newkvs = chm._newkvs; // VOLATILE READ before key compare
614 
615  // Key-compare
616  if( keyeq(K,key,hashes,idx,fullhash) )
617  return K; // Return existing Key!
618 
619  // get and put must have the same key lookup logic! But only 'put'
620  // needs to force a table-resize for a too-long key-reprobe sequence.
621  // Check for too-many-reprobes on get - and flip to the new table.
622  if( ++reprobe_cnt >= reprobe_limit(len) || // too many probes
623  K == TOMBSTONE ) { // found a TOMBSTONE key, means no more keys in this table
624  return newkvs == null ? null : getk_impl(topmap,topmap.help_copy(newkvs),key); // Retry in the new table
625  }
626 
627  idx = (idx+1)&(len-1); // Reprobe by 1! (could now prefetch)
628  }
629  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk_impl().

Here is the caller graph for this function:

◆ getKey()

TypeK com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.getKey ( )

Definition at line 477 of file NonBlockingHashMap.java.

477 { return (TypeK)_getKey(_kvs); }

◆ hash()

static int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.hash ( final Object  key)
staticprivate

Definition at line 114 of file NonBlockingHashMap.java.

114  {
115  int h = key.hashCode(); // The real hashCode call
116  h ^= (h>>>20) ^ (h>>>12);
117  h ^= (h>>> 7) ^ (h>>> 4);
118  return h;
119  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.keyeq(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch().

Here is the caller graph for this function:

◆ hashes()

static final int [] com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.hashes ( Object[]  kvs)
staticprivate

Definition at line 136 of file NonBlockingHashMap.java.

136 { return (int[])kvs[1]; }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.keyeq(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch().

Here is the caller graph for this function:

◆ help_copy()

final Object [] com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.help_copy ( Object[]  helper)
private

Definition at line 788 of file NonBlockingHashMap.java.

788  {
789  // Read the top-level KVS only once. We'll try to help this copy along,
790  // even if it gets promoted out from under us (i.e., the copy completes
791  // and another KVS becomes the top-level copy).
792  Object[] topkvs = _kvs;
793  CHM topchm = chm(topkvs);
794  if( topchm._newkvs == null ) return helper; // No copy in-progress
795  topchm.help_copy_impl(this,topkvs,false);
796  return helper;
797  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_slot_and_check(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk_impl(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch().

Here is the caller graph for this function:

◆ initialize() [1/2]

final void com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.initialize ( )
protected

Definition at line 271 of file NonBlockingHashMap.java.

271 { initialize(MIN_SIZE); }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.initialize(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.NonBlockingHashMap(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.readObject().

Here is the caller graph for this function:

◆ initialize() [2/2]

final void com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.initialize ( int  initial_sz)
private

Definition at line 259 of file NonBlockingHashMap.java.

259  {
260  if( initial_sz < 0 ) throw new IllegalArgumentException();
261  int i; // Convert to next largest power-of-2
262  if( initial_sz > 1024*1024 ) initial_sz = 1024*1024;
263  for( i=MIN_SIZE_LOG; (1<<i) < (initial_sz<<2); i++ ) ;
264  // Double size for K,V pairs, add 1 for CHM and 1 for hashes
265  _kvs = new Object[((1<<i)<<1)+2];
266  _kvs[0] = new CHM(new ConcurrentAutoTable()); // CHM in slot 0
267  _kvs[1] = new int[1<<i]; // Matching hash entries
268  _last_resize_milli = System.currentTimeMillis();
269  }

◆ isEmpty()

boolean com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.isEmpty ( )

Returns size() == 0.

Returns
size() == 0

Definition at line 282 of file NonBlockingHashMap.java.

282 { return size() == 0; }

◆ key()

static final Object com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.key ( Object[]  kvs,
int  idx 
)
staticprivate

Definition at line 172 of file NonBlockingHashMap.java.

172 { return kvs[(idx<<1)+2]; }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >._getKey(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.CAS_key(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.containsKey(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_slot(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.hash(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.SnapshotV.key(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.keyeq(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print2(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.put(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfAbsent(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatchAllowNull(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.remove(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.replace(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.toString().

Here is the caller graph for this function:

◆ keyeq()

static boolean com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.keyeq ( Object  K,
Object  key,
int[]  hashes,
int  hash,
int  fullhash 
)
staticprivate

Definition at line 495 of file NonBlockingHashMap.java.

495  {
496  return
497  K==key || // Either keys match exactly OR
498  // hash exists and matches? hash can be zero during the install of a
499  // new key/value pair.
500  ((hashes[hash] == 0 || hashes[hash] == fullhash) &&
501  // Do not call the users' "equals()" call with a Tombstone, as this can
502  // surprise poorly written "equals()" calls that throw exceptions
503  // instead of simply returning false.
504  K != TOMBSTONE && // Do not call users' equals call with a Tombstone
505  // Do the match the hard way - with the users' key being the loop-
506  // invariant "this" pointer. I could have flipped the order of
507  // operands (since equals is commutative), but I'm making mega-morphic
508  // v-calls in a reprobing loop and nailing down the 'this' argument
509  // gives both the JIT and the hardware a chance to prefetch the call target.
510  key.equals(K)); // Finally do the hard match
511  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk_impl(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch().

Here is the caller graph for this function:

◆ keys()

Enumeration<TypeK> com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.keys ( )

Returns an enumeration of the keys in this table.

Returns
an enumeration of the keys in this table
See also
keySet()

Definition at line 1289 of file NonBlockingHashMap.java.

1289 { return new SnapshotK(); }

◆ keySet()

Set<TypeK> com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.keySet ( )

Returns a Set view of the keys contained in this map.

The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

Definition at line 1305 of file NonBlockingHashMap.java.

1305  {
1306  return new AbstractSet<TypeK> () {
1307  @Override public void clear ( ) { NonBlockingHashMap.this.clear ( ); }
1308  @Override public int size ( ) { return NonBlockingHashMap.this.size ( ); }
1309  @Override public boolean contains( Object k ) { return NonBlockingHashMap.this.containsKey(k); }
1310  @Override public boolean remove ( Object k ) { return NonBlockingHashMap.this.remove (k) != null; }
1311  @Override public Iterator<TypeK> iterator() { return new SnapshotK(); }
1312  };
1313  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.clone(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.writeObject().

Here is the caller graph for this function:

◆ len()

static final int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.len ( Object[]  kvs)
staticprivate

Definition at line 138 of file NonBlockingHashMap.java.

138 { return (kvs.length-2)>>1; }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >._getKey(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_check_and_promote(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk_impl(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.help_copy_impl(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.SnapshotV.length(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print2(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.reprobe_limit(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.resize(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.tableFull().

Here is the caller graph for this function:

◆ print() [1/2]

final void com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.print ( )

Verbose printout of table internals, useful for debugging.


Definition at line 184 of file NonBlockingHashMap.java.

184  {
185  System.out.println("=========");
186  print2(_kvs);
187  System.out.println("=========");
188  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print().

Here is the caller graph for this function:

◆ print() [2/2]

final void com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.print ( Object[]  kvs)
private

Definition at line 190 of file NonBlockingHashMap.java.

190  {
191  for( int i=0; i<len(kvs); i++ ) {
192  Object K = key(kvs,i);
193  if( K != null ) {
194  String KS = (K == TOMBSTONE) ? "XXX" : K.toString();
195  Object V = val(kvs,i);
196  Object U = Prime.unbox(V);
197  String p = (V==U) ? "" : "prime_";
198  String US = (U == TOMBSTONE) ? "tombstone" : U.toString();
199  System.out.println(""+i+" ("+KS+","+p+US+")");
200  }
201  }
202  Object[] newkvs = chm(kvs)._newkvs; // New table, if any
203  if( newkvs != null ) {
204  System.out.println("----");
205  print(newkvs);
206  }
207  }

◆ print2()

final void com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.print2 ( Object[]  kvs)
private

Definition at line 209 of file NonBlockingHashMap.java.

209  {
210  for( int i=0; i<len(kvs); i++ ) {
211  Object key = key(kvs,i);
212  Object val = val(kvs,i);
213  Object U = Prime.unbox(val);
214  if( key != null && key != TOMBSTONE && // key is sane
215  val != null && U != TOMBSTONE ) { // val is sane
216  String p = (val==U) ? "" : "prime_";
217  System.out.println(""+i+" ("+key+","+p+val+")");
218  }
219  }
220  Object[] newkvs = chm(kvs)._newkvs; // New table, if any
221  if( newkvs != null ) {
222  System.out.println("----");
223  print2(newkvs);
224  }
225  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print2().

Here is the caller graph for this function:

◆ put()

TypeV com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.put ( TypeK  key,
TypeV  val 
)

Maps the specified key to the specified value in the table.

Neither key nor value can be null.

The value can be retrieved by calling get with a key that is equal to the original key.

Parameters
keykey with which the specified value is to be associated
valvalue to be associated with the specified key
Returns
the previous value associated with key, or null if there was no mapping for key
Exceptions
NullPointerExceptionif the specified key or value is null

Definition at line 310 of file NonBlockingHashMap.java.

310 { return putIfMatch( key, val, NO_MATCH_OLD); }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.clone(), com.cliffc.aa.tvar.TV2.make(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putAll(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.readObject(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.NBHMEntry.setValue().

Here is the caller graph for this function:

◆ putAll()

void com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.putAll ( Map<? extends TypeK, ? extends TypeV >  m)

Copies all of the mappings from the specified map to this one, replacing any existing mappings.

Parameters
mmappings to be stored in this map

Definition at line 374 of file NonBlockingHashMap.java.

374  {
375  for (Map.Entry<? extends TypeK, ? extends TypeV> e : m.entrySet())
376  put(e.getKey(), e.getValue());
377  }

◆ putIfAbsent()

TypeV com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.putIfAbsent ( TypeK  key,
TypeV  val 
)

Atomically, do a put if-and-only-if the key is not mapped.

Useful to ensure that only a single mapping for the key exists, even if many threads are trying to create the mapping in parallel.

Returns
the previous value associated with the specified key, or null if there was no mapping for the key
Exceptions
NullPointerExceptionif the specified key or value is null

Definition at line 318 of file NonBlockingHashMap.java.

318 { return putIfMatch( key, val, TOMBSTONE ); }

◆ putIfMatch() [1/2]

static final Object com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.putIfMatch ( final NonBlockingHashMap< TypeK, TypeV >  topmap,
final Object[]  kvs,
final Object  key,
final Object  putval,
final Object  expVal 
)
staticprivate

Definition at line 638 of file NonBlockingHashMap.java.

638  {
639  assert putval != null;
640  assert !(putval instanceof Prime);
641  assert !(expVal instanceof Prime);
642  final int fullhash = hash (key); // throws NullPointerException if key null
643  final int len = len (kvs); // Count of key/value pairs, reads kvs.length
644  final CHM chm = chm (kvs); // Reads kvs[0]
645  final int[] hashes = hashes(kvs); // Reads kvs[1], read before kvs[0]
646  int idx = fullhash & (len-1);
647 
648  // ---
649  // Key-Claim stanza: spin till we can claim a Key (or force a resizing).
650  int reprobe_cnt=0;
651  Object K=null, V=null;
652  Object[] newkvs=null;
653  while( true ) { // Spin till we get a Key slot
654  V = val(kvs,idx); // Get old value (before volatile read below!)
655  K = key(kvs,idx); // Get current key
656  if( K == null ) { // Slot is free?
657  // Found an empty Key slot - which means this Key has never been in
658  // this table. No need to put a Tombstone - the Key is not here!
659  if( putval == TOMBSTONE ) return putval; // Not-now & never-been in this table
660  if( expVal == MATCH_ANY ) return null; // Will not match, even after K inserts
661  // Claim the null key-slot
662  if( CAS_key(kvs,idx, null, key ) ) { // Claim slot for Key
663  chm._slots.add(1); // Raise key-slots-used count
664  hashes[idx] = fullhash; // Memoize fullhash
665  break; // Got it!
666  }
667  // CAS to claim the key-slot failed.
668  //
669  // This re-read of the Key points out an annoying short-coming of Java
670  // CAS. Most hardware CAS's report back the existing value - so that
671  // if you fail you have a *witness* - the value which caused the CAS to
672  // fail. The Java API turns this into a boolean destroying the
673  // witness. Re-reading does not recover the witness because another
674  // thread can write over the memory after the CAS. Hence we can be in
675  // the unfortunate situation of having a CAS fail *for cause* but
676  // having that cause removed by a later store. This turns a
677  // non-spurious-failure CAS (such as Azul has) into one that can
678  // apparently spuriously fail - and we avoid apparent spurious failure
679  // by not allowing Keys to ever change.
680 
681  // Volatile read, to force loads of K to retry despite JIT, otherwise
682  // it is legal to e.g. haul the load of "K = key(kvs,idx);" outside of
683  // this loop (since failed CAS ops have no memory ordering semantics).
684  int dummy = DUMMY_VOLATILE;
685  continue;
686  }
687  // Key slot was not null, there exists a Key here
688 
689  // We need a volatile-read here to preserve happens-before semantics on
690  // newly inserted Keys. If the Key body was written just before inserting
691  // into the table a Key-compare here might read the uninitialized Key body.
692  // Annoyingly this means we have to volatile-read before EACH key compare.
693  newkvs = chm._newkvs; // VOLATILE READ before key compare
694 
695  if( keyeq(K,key,hashes,idx,fullhash) )
696  break; // Got it!
697 
698  // get and put must have the same key lookup logic! Lest 'get' give
699  // up looking too soon.
700  //topmap._reprobes.add(1);
701  if( ++reprobe_cnt >= reprobe_limit(len) || // too many probes or
702  K == TOMBSTONE ) { // found a TOMBSTONE key, means no more keys
703  // We simply must have a new table to do a 'put'. At this point a
704  // 'get' will also go to the new table (if any). We do not need
705  // to claim a key slot (indeed, we cannot find a free one to claim!).
706  newkvs = chm.resize(topmap,kvs);
707  if( expVal != null ) topmap.help_copy(newkvs); // help along an existing copy
708  return putIfMatch(topmap,newkvs,key,putval,expVal);
709  }
710 
711  idx = (idx+1)&(len-1); // Reprobe!
712  } // End of spinning till we get a Key slot
713 
714  // ---
715  // Found the proper Key slot, now update the matching Value slot. We
716  // never put a null, so Value slots monotonically move from null to
717  // not-null (deleted Values use Tombstone). Thus if 'V' is null we
718  // fail this fast cutout and fall into the check for table-full.
719  if( putval == V ) return V; // Fast cutout for no-change
720 
721  // See if we want to move to a new table (to avoid high average re-probe
722  // counts). We only check on the initial set of a Value from null to
723  // not-null (i.e., once per key-insert). Of course we got a 'free' check
724  // of newkvs once per key-compare (not really free, but paid-for by the
725  // time we get here).
726  if( newkvs == null && // New table-copy already spotted?
727  // Once per fresh key-insert check the hard way
728  ((V == null && chm.tableFull(reprobe_cnt,len)) ||
729  // Or we found a Prime, but the JMM allowed reordering such that we
730  // did not spot the new table (very rare race here: the writing
731  // thread did a CAS of _newkvs then a store of a Prime. This thread
732  // reads the Prime, then reads _newkvs - but the read of Prime was so
733  // delayed (or the read of _newkvs was so accelerated) that they
734  // swapped and we still read a null _newkvs. The resize call below
735  // will do a CAS on _newkvs forcing the read.
736  V instanceof Prime) )
737  newkvs = chm.resize(topmap,kvs); // Force the new table copy to start
738  // See if we are moving to a new table.
739  // If so, copy our slot and retry in the new table.
740  if( newkvs != null )
741  return putIfMatch(topmap,chm.copy_slot_and_check(topmap,kvs,idx,expVal),key,putval,expVal);
742 
743  // ---
744  // We are finally prepared to update the existing table
745  assert !(V instanceof Prime);
746 
747  // Must match old, and we do not? Then bail out now. Note that either V
748  // or expVal might be TOMBSTONE. Also V can be null, if we've never
749  // inserted a value before. expVal can be null if we are called from
750  // copy_slot.
751 
752  if( expVal != NO_MATCH_OLD && // Do we care about expected-Value at all?
753  V != expVal && // No instant match already?
754  (expVal != MATCH_ANY || V == TOMBSTONE || V == null) &&
755  !(V==null && expVal == TOMBSTONE) && // Match on null/TOMBSTONE combo
756  (expVal == null || !expVal.equals(V)) ) // Expensive equals check at the last
757  return V; // Do not update!
758 
759  // Actually change the Value in the Key,Value pair
760  if( CAS_val(kvs, idx, V, putval ) ) {
761  // CAS succeeded - we did the update!
762  // Both normal put's and table-copy calls putIfMatch, but table-copy
763  // does not (effectively) increase the number of live k/v pairs.
764  if( expVal != null ) {
765  // Adjust sizes - a striped counter
766  if( (V == null || V == TOMBSTONE) && putval != TOMBSTONE ) chm._size.add( 1);
767  if( !(V == null || V == TOMBSTONE) && putval == TOMBSTONE ) chm._size.add(-1);
768  }
769  } else { // Else CAS failed
770  V = val(kvs,idx); // Get new value
771  // If a Prime'd value got installed, we need to re-run the put on the
772  // new table. Otherwise we lost the CAS to another racing put.
773  // Simply retry from the start.
774  if( V instanceof Prime )
775  return putIfMatch(topmap,chm.copy_slot_and_check(topmap,kvs,idx,expVal),key,putval,expVal);
776  }
777  // Win or lose the CAS, we are done. If we won then we know the update
778  // happened as expected. If we lost, it means "we won but another thread
779  // immediately stomped our update with no chance of a reader reading".
780  return (V==null && expVal!=null) ? TOMBSTONE : V;
781  }

◆ putIfMatch() [2/2]

final TypeV com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.putIfMatch ( Object  key,
Object  newVal,
Object  oldVal 
)
private

Definition at line 361 of file NonBlockingHashMap.java.

361  {
362  if (oldVal == null || newVal == null) throw new NullPointerException();
363  final Object res = putIfMatch( this, _kvs, key, newVal, oldVal );
364  assert !(res instanceof Prime);
365  assert res != null;
366  return res == TOMBSTONE ? null : (TypeV)res;
367  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_slot(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.put(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfAbsent(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatchAllowNull(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.remove(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.SnapshotV.remove(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.replace().

Here is the caller graph for this function:

◆ putIfMatchAllowNull()

final TypeV com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.putIfMatchAllowNull ( Object  key,
Object  newVal,
Object  oldVal 
)

Definition at line 351 of file NonBlockingHashMap.java.

351  {
352  if( oldVal == null ) oldVal = TOMBSTONE;
353  if( newVal == null ) newVal = TOMBSTONE;
354  final TypeV res = (TypeV)putIfMatch( this, _kvs, key, newVal, oldVal );
355  assert !(res instanceof Prime);
356  //assert res != null;
357  return res == TOMBSTONE ? null : res;
358  }

◆ raw_array()

Object [] com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.raw_array ( )

Definition at line 1243 of file NonBlockingHashMap.java.

1243 { return new SnapshotV()._sskvs; }

◆ rawIndex()

static long com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.rawIndex ( final Object[]  ary,
final int  idx 
)
staticprivate

Definition at line 86 of file NonBlockingHashMap.java.

86  {
87  assert idx >= 0 && idx < ary.length;
88  // Note the long-math requirement, to handle arrays of more than 2^31 bytes
89  // - or 2^28 - or about 268M - 8-byte pointer elements.
90  return _Obase + ((long)idx << _Olog);
91  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.CAS_key(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.CAS_val().

Here is the caller graph for this function:

◆ readObject()

void com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.readObject ( java.io.ObjectInputStream  s) throws IOException, ClassNotFoundException
private

Definition at line 1393 of file NonBlockingHashMap.java.

1393  {
1394  s.defaultReadObject(); // Read nothing
1395  initialize(MIN_SIZE);
1396  for(;;) {
1397  final TypeK K = (TypeK) s.readObject();
1398  final TypeV V = (TypeV) s.readObject();
1399  if( K == null ) break;
1400  put(K,V); // Insert with an offical put
1401  }
1402  }

◆ rehash()

void com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.rehash ( )
protected

Definition at line 405 of file NonBlockingHashMap.java.

405  {
406  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.resize().

Here is the caller graph for this function:

◆ remove() [1/2]

TypeV com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.remove ( Object  key)

Removes the key (and its corresponding value) from this map.

This method does nothing if the key is not in the map.

Returns
the previous value associated with key, or null if there was no mapping for key
Exceptions
NullPointerExceptionif the specified key is null

Definition at line 326 of file NonBlockingHashMap.java.

326 { return putIfMatch( key,TOMBSTONE, NO_MATCH_OLD); }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.entrySet(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.keySet().

Here is the caller graph for this function:

◆ remove() [2/2]

boolean com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.remove ( Object  key,
Object  val 
)

Atomically do a remove(Object) if-and-only-if the key is mapped to a value which is equals to the given value.

Exceptions
NullPointerExceptionif the specified key or value is null

Definition at line 331 of file NonBlockingHashMap.java.

331 { return putIfMatch( key,TOMBSTONE, val ) == val; }

◆ replace() [1/2]

boolean com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.replace ( TypeK  key,
TypeV  oldValue,
TypeV  newValue 
)

Atomically do a put(key,newValue) if-and-only-if the key is mapped a value which is equals to oldValue.

Exceptions
NullPointerExceptionif the specified key or value is null

Definition at line 341 of file NonBlockingHashMap.java.

341  {
342  return putIfMatch( key, newValue, oldValue ) == oldValue;
343  }

◆ replace() [2/2]

TypeV com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.replace ( TypeK  key,
TypeV  val 
)

Atomically do a put(key,val) if-and-only-if the key is mapped to some value already.

Exceptions
NullPointerExceptionif the specified key or value is null

Definition at line 336 of file NonBlockingHashMap.java.

336 { return putIfMatch( key, val,MATCH_ANY ); }

◆ reprobe_limit()

static final int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.reprobe_limit ( int  len)
staticprivate

Definition at line 242 of file NonBlockingHashMap.java.

242  {
243  return REPROBE_LIMIT + (len>>4);
244  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.tableFull().

Here is the caller graph for this function:

◆ reprobes()

long com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.reprobes ( )

Get and clear the current count of reprobes.

Reprobes happen on key collisions, and a high reprobe rate may indicate a poor hash function or weaknesses in the table resizing function.

Returns
the count of reprobes since the last call to reprobes or since the table was created.

Definition at line 234 of file NonBlockingHashMap.java.

234 { long r = _reprobes.get(); _reprobes = new ConcurrentAutoTable(); return r; }

◆ size()

int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.size ( )

Returns the number of key-value mappings in this map.

Returns
the number of key-value mappings in this map

Definition at line 278 of file NonBlockingHashMap.java.

278 { return chm(_kvs).size(); }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.entrySet(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.isEmpty(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.keySet(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.values().

Here is the caller graph for this function:

◆ toString()

String com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.toString ( )

Returns a string representation of this map.

The string representation consists of a list of key-value mappings in the order returned by the map's entrySet view's iterator, enclosed in braces ("{}"). Adjacent mappings are separated by the characters ", " (comma and space). Each key-value mapping is rendered as the key followed by an equals sign ("=") followed by the associated value. Keys and values are converted to strings as by String#valueOf(Object).

Returns
a string representation of this map

Definition at line 453 of file NonBlockingHashMap.java.

453  {
454  Iterator<Entry<TypeK,TypeV>> i = entrySet().iterator();
455  if( !i.hasNext())
456  return "{}";
457 
458  StringBuilder sb = new StringBuilder();
459  sb.append('{');
460  for (;;) {
461  Entry<TypeK,TypeV> e = i.next();
462  TypeK key = e.getKey();
463  TypeV value = e.getValue();
464  sb.append(key == this ? "(this Map)" : key);
465  sb.append('=');
466  sb.append(value == this ? "(this Map)" : value);
467  if( !i.hasNext())
468  return sb.append('}').toString();
469  sb.append(", ");
470  }
471  }

◆ val()

static final Object com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.val ( Object[]  kvs,
int  idx 
)
staticprivate

Definition at line 173 of file NonBlockingHashMap.java.

173 { return kvs[(idx<<1)+3]; }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >._getKey(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.CAS_val(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.contains(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.containsValue(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_slot(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print2(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.put(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfAbsent(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.remove(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.replace(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.NBHMEntry.setValue(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.SnapshotV.val().

Here is the caller graph for this function:

◆ values()

Collection<TypeV> com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.values ( )

Returns a Collection view of the values contained in this map.

The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

Definition at line 1265 of file NonBlockingHashMap.java.

1265  {
1266  return new AbstractCollection<TypeV>() {
1267  @Override public void clear ( ) { NonBlockingHashMap.this.clear ( ); }
1268  @Override public int size ( ) { return NonBlockingHashMap.this.size ( ); }
1269  @Override public boolean contains( Object v ) { return NonBlockingHashMap.this.containsValue(v); }
1270  @Override public Iterator<TypeV> iterator() { return new SnapshotV(); }
1271  };
1272  }

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.containsValue().

Here is the caller graph for this function:

◆ writeObject()

void com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.writeObject ( java.io.ObjectOutputStream  s) throws IOException
private

Definition at line 1379 of file NonBlockingHashMap.java.

1379  {
1380  s.defaultWriteObject(); // Nothing to write
1381  for( Object K : keySet() ) {
1382  final Object V = get(K); // Do an official 'get'
1383  s.writeObject(K); // Write the <TypeK,TypeV> pair
1384  s.writeObject(V);
1385  }
1386  s.writeObject(null); // Sentinel to indicate end-of-data
1387  s.writeObject(null);
1388  }

Member Data Documentation

◆ _kvs

transient Object [] com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >._kvs
private

Definition at line 134 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.clear(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_check_and_promote(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getKey(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.help_copy(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.initialize(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatchAllowNull(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.size(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.SnapshotV.SnapshotV().

◆ _kvs_offset

final long com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >._kvs_offset
staticprivate

Definition at line 94 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.CAS_kvs().

◆ _last_resize_milli

transient long com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >._last_resize_milli
private

Definition at line 141 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_check_and_promote(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.initialize(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.resize().

◆ _Obase

final int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >._Obase = _unsafe.arrayBaseOffset(Object[].class)
staticprivate

Definition at line 83 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.rawIndex().

◆ _Olog

final int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >._Olog = _Oscale==4?2:(_Oscale==8?3:9999)
staticprivate

Definition at line 85 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.rawIndex().

◆ _Oscale

final int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >._Oscale = _unsafe.arrayIndexScale(Object[].class)
staticprivate

Definition at line 84 of file NonBlockingHashMap.java.

◆ _reprobes

transient ConcurrentAutoTable com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >._reprobes = new ConcurrentAutoTable()
private

Definition at line 228 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.reprobes().

◆ _unsafe

final Unsafe com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >._unsafe = UtilUnsafe.getUnsafe()
staticprivate

Definition at line 82 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.CAS_key(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.CAS_kvs(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.CAS_val().

◆ DUMMY_VOLATILE

volatile int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.DUMMY_VOLATILE
staticpackage

Definition at line 637 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch().

◆ MATCH_ANY

final Object com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.MATCH_ANY = new Object()
staticprivate

Definition at line 155 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.replace().

◆ MIN_SIZE

final int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.MIN_SIZE =(1<<MIN_SIZE_LOG)
staticprivate

Definition at line 147 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.clear(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.initialize(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.NonBlockingHashMap(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.readObject().

◆ MIN_SIZE_LOG

final int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.MIN_SIZE_LOG =3
staticprivate

Definition at line 146 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.initialize(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.resize().

◆ NO_MATCH_OLD

final Object com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.NO_MATCH_OLD = new Object()
staticprivate

Definition at line 152 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.put(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch(), and com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.remove().

◆ REPROBE_LIMIT

final int com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.REPROBE_LIMIT =10
staticprivate

Definition at line 79 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.reprobe_limit(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.tableFull().

◆ serialVersionUID

final long com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.serialVersionUID = 1234123412341234123L
staticprivate

Definition at line 77 of file NonBlockingHashMap.java.

◆ TOMBPRIME

final Prime com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.TOMBPRIME = new Prime(TOMBSTONE)
staticprivate

Definition at line 163 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_slot().

◆ TOMBSTONE

final Object com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.TOMBSTONE = new Object()
static

Definition at line 158 of file NonBlockingHashMap.java.

Referenced by com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >._getKey(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.CHM< TypeK, TypeV >.copy_slot(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.get_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.getk_impl(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.keyeq(), com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.SnapshotV.next(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.print2(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfAbsent(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatch(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.putIfMatchAllowNull(), com.cliffc.aa.util.NonBlockingHashMap< com.cliffc.aa.type.Type.Key, com.cliffc.aa.type.Type >.remove(), and com.cliffc.aa.util.NonBlockingHashMap< TypeK, TypeV >.SnapshotV.remove().

The documentation for this class was generated from the following file:
com.cliffc.aa.util.NonBlockingHashMap.val
static final Object val(Object[] kvs, int idx)
Definition: NonBlockingHashMap.java:173
com.cliffc.aa.util.NonBlockingHashMap._unsafe
static final Unsafe _unsafe
Definition: NonBlockingHashMap.java:82
com.cliffc.aa.util.NonBlockingHashMap._getKey
static Object _getKey(Object[] kvs)
Definition: NonBlockingHashMap.java:478
com.cliffc.aa.util.NonBlockingHashMap.keyeq
static boolean keyeq(Object K, Object key, int[] hashes, int hash, int fullhash)
Definition: NonBlockingHashMap.java:495
com.cliffc.aa.util.NonBlockingHashMap.contains
boolean contains(Object val)
Legacy method testing if some key maps into the specified value in this table.
Definition: NonBlockingHashMap.java:298
com.cliffc.aa.util.NonBlockingHashMap.CHM.tableFull
final boolean tableFull(int reprobe_cnt, int len)
Definition: NonBlockingHashMap.java:870
com.cliffc.aa.util.NonBlockingHashMap.CHM.size
int size()
Definition: NonBlockingHashMap.java:805
com.cliffc.aa.util.NonBlockingHashMap.len
static final int len(Object[] kvs)
Definition: NonBlockingHashMap.java:138
com.cliffc.aa.util.NonBlockingHashMap.values
Collection< TypeV > values()
Returns a Collection view of the values contained in this map.
Definition: NonBlockingHashMap.java:1265
com.cliffc.aa.util.ConcurrentAutoTable.add
void add(long x)
Add the given value to current counter value.
Definition: ConcurrentAutoTable.java:30
com.cliffc.aa.util.NonBlockingHashMap.CAS_kvs
boolean CAS_kvs(final Object[] oldkvs, final Object[] newkvs)
Definition: NonBlockingHashMap.java:101
com.cliffc.aa.util.NonBlockingHashMap.NonBlockingHashMap
NonBlockingHashMap()
Create a new NonBlockingHashMap with default minimum size (currently set to 8 K/V pairs or roughly 84...
Definition: NonBlockingHashMap.java:251
com.cliffc.aa.util.NonBlockingHashMap._Olog
static final int _Olog
Definition: NonBlockingHashMap.java:85
com.cliffc.aa.util.NonBlockingHashMap.reprobe_limit
static final int reprobe_limit(int len)
Definition: NonBlockingHashMap.java:242
com.cliffc.aa.util.NonBlockingHashMap.rawIndex
static long rawIndex(final Object[] ary, final int idx)
Definition: NonBlockingHashMap.java:86
com.cliffc.aa.util.NonBlockingHashMap.DUMMY_VOLATILE
static volatile int DUMMY_VOLATILE
Definition: NonBlockingHashMap.java:637
com.cliffc.aa.util.NonBlockingHashMap.entrySet
Set< Map.Entry< TypeK, TypeV > > entrySet()
Returns a Set view of the mappings contained in this map.
Definition: NonBlockingHashMap.java:1358
com.cliffc.aa.util.NonBlockingHashMap.key
static final Object key(Object[] kvs, int idx)
Definition: NonBlockingHashMap.java:172
com.cliffc.aa.util.NonBlockingHashMap.print
final void print()
Verbose printout of table internals, useful for debugging.
Definition: NonBlockingHashMap.java:184
com.cliffc.aa.util.NonBlockingHashMap.CHM.resize
final Object[] resize(NonBlockingHashMap topmap, Object[] kvs)
Definition: NonBlockingHashMap.java:885
com.cliffc.aa.util.NonBlockingHashMap.CHM._size
final ConcurrentAutoTable _size
Definition: NonBlockingHashMap.java:804
com.cliffc.aa.util.NonBlockingHashMap.MIN_SIZE_LOG
static final int MIN_SIZE_LOG
Definition: NonBlockingHashMap.java:146
com.cliffc.aa.util.NonBlockingHashMap.TOMBSTONE
static final Object TOMBSTONE
Definition: NonBlockingHashMap.java:158
com.cliffc.aa.util.NonBlockingHashMap.REPROBE_LIMIT
static final int REPROBE_LIMIT
Definition: NonBlockingHashMap.java:79
com.cliffc.aa.util.NonBlockingHashMap.containsValue
boolean containsValue(final Object val)
Returns true if this Map maps one or more keys to the specified value.
Definition: NonBlockingHashMap.java:394
com.cliffc.aa.util.NonBlockingHashMap._kvs
transient Object[] _kvs
Definition: NonBlockingHashMap.java:134
com.cliffc.aa.util.NonBlockingHashMap.NO_MATCH_OLD
static final Object NO_MATCH_OLD
Definition: NonBlockingHashMap.java:152
com.cliffc.aa.util.NonBlockingHashMap.keySet
Set< TypeK > keySet()
Returns a Set view of the keys contained in this map.
Definition: NonBlockingHashMap.java:1305
com.cliffc.aa.util.NonBlockingHashMap.put
TypeV put(TypeK key, TypeV val)
Maps the specified key to the specified value in the table.
Definition: NonBlockingHashMap.java:310
com.cliffc.aa.util.NonBlockingHashMap.CHM.copy_slot_and_check
final Object[] copy_slot_and_check(NonBlockingHashMap topmap, Object[] oldkvs, int idx, Object should_help)
Definition: NonBlockingHashMap.java:1066
com.cliffc.aa.util.NonBlockingHashMap._last_resize_milli
transient long _last_resize_milli
Definition: NonBlockingHashMap.java:141
com.cliffc.aa.util.NonBlockingHashMap.putIfMatch
final TypeV putIfMatch(Object key, Object newVal, Object oldVal)
Definition: NonBlockingHashMap.java:361
com.cliffc.aa.util.NonBlockingHashMap._kvs_offset
static final long _kvs_offset
Definition: NonBlockingHashMap.java:94
com.cliffc.aa.util.NonBlockingHashMap._reprobes
transient ConcurrentAutoTable _reprobes
Definition: NonBlockingHashMap.java:228
com.cliffc.aa.util.NonBlockingHashMap.initialize
final void initialize()
Definition: NonBlockingHashMap.java:271
com.cliffc.aa.util.NonBlockingHashMap.CHM._slots
final ConcurrentAutoTable _slots
Definition: NonBlockingHashMap.java:817
com.cliffc.aa.util.NonBlockingHashMap.clear
void clear()
Removes all of the mappings from this map.
Definition: NonBlockingHashMap.java:381
com.cliffc.aa.util.NonBlockingHashMap._Obase
static final int _Obase
Definition: NonBlockingHashMap.java:83
com.cliffc.aa.util.NonBlockingHashMap.hashes
static final int[] hashes(Object[] kvs)
Definition: NonBlockingHashMap.java:136
com.cliffc.aa.util.NonBlockingHashMap.size
int size()
Returns the number of key-value mappings in this map.
Definition: NonBlockingHashMap.java:278
com.cliffc.aa.util.NonBlockingHashMap.get_impl
static Object get_impl(final NonBlockingHashMap topmap, final Object[] kvs, final Object key)
Definition: NonBlockingHashMap.java:531
com.cliffc.aa.util.NonBlockingHashMap.CAS_val
static final boolean CAS_val(Object[] kvs, int idx, Object old, Object val)
Definition: NonBlockingHashMap.java:177
com.cliffc.aa.util.NonBlockingHashMap.chm
static final CHM chm(Object[] kvs)
Definition: NonBlockingHashMap.java:135
com.cliffc.aa.util.NonBlockingHashMap.hash
static int hash(final Object key)
Definition: NonBlockingHashMap.java:114
com.cliffc.aa.util.NonBlockingHashMap.CAS_key
static final boolean CAS_key(Object[] kvs, int idx, Object old, Object key)
Definition: NonBlockingHashMap.java:174
com.cliffc.aa.util.ConcurrentAutoTable.get
long get()
Current value of the counter.
Definition: ConcurrentAutoTable.java:50
com.cliffc.aa.util.NonBlockingHashMap.print2
final void print2(Object[] kvs)
Definition: NonBlockingHashMap.java:209
com.cliffc.aa.util.NonBlockingHashMap.CHM._newkvs
volatile Object[] _newkvs
Definition: NonBlockingHashMap.java:827
com.cliffc.aa.util.NonBlockingHashMap.MIN_SIZE
static final int MIN_SIZE
Definition: NonBlockingHashMap.java:147
com.cliffc.aa.util.NonBlockingHashMap.MATCH_ANY
static final Object MATCH_ANY
Definition: NonBlockingHashMap.java:155
com.cliffc.aa.util.NonBlockingHashMap.getk_impl
static final Object getk_impl(final NonBlockingHashMap topmap, final Object[] kvs, final Object key)
Definition: NonBlockingHashMap.java:589