A lock-free alternate implementation of java.util.concurrent.ConcurrentHashMap with primitive long keys, better scaling properties and generally lower costs. More...

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

[legend]

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

[legend]

Classes
class	CHM

class	IteratorLong
	A class which implements the Iterator and Enumeration interfaces, generified to the Long class and supporting a non-auto-boxing nextLong function. More...

class	NBHMLEntry

class	Prime

class	SnapshotE

class	SnapshotV

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

	NonBlockingHashMapLong (final boolean opt_for_space)
	Create a new NonBlockingHashMapLong, setting the space-for-speed tradeoff. More...

	NonBlockingHashMapLong (final int initial_sz)
	Create a new NonBlockingHashMapLong with initial room for the given number of elements, thus avoiding internal resizing operations to reach an appropriate size. More...

	NonBlockingHashMapLong (final int initial_sz, final boolean opt_for_space)
	Create a new NonBlockingHashMapLong, setting both the initial size and the space-for-speed tradeoff. More...

void	clear ()
	Removes all of the mappings from this map. More...

void	clear (boolean large)

NonBlockingHashMapLong< TypeV >	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 (long key)
	Tests if the key in the table. More...

boolean	containsKey (Object key)
	Auto-boxing version of containsKey(long). More...

boolean	containsValue (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< Long, TypeV > >	entrySet ()
	Returns a Set view of the mappings contained in this map. More...

final TypeV	get (long key)
	Returns the value to which the specified key is mapped, or. More...

TypeV	get (Object key)
	Auto-boxing version of get(long). More...

Enumeration< Long >	keys ()
	Returns an enumeration of the auto-boxed keys in this table. More...

Set< Long >	keySet ()
	Returns a Set view of the keys contained in this map; with care the keys may be iterated over without auto-boxing. More...

long[]	keySetLong ()
	Keys as a long array. More...

final void	print ()
	Verbose printout of table internals, useful for debugging. More...

TypeV	put (long key, TypeV val)
	Maps the specified key to the specified value in the table. More...

TypeV	put (Long key, TypeV val)
	Auto-boxing version of put. More...

TypeV	putIfAbsent (long key, TypeV val)
	Atomically, do a put if-and-only-if the key is not mapped. More...

TypeV	putIfAbsent (Long key, TypeV val)
	Auto-boxing version of putIfAbsent. More...

TypeV	remove (long key)
	Removes the key (and its corresponding value) from this map. More...

boolean	remove (long key, Object val)
	Atomically do a remove(long) if-and-only-if the key is mapped to a value which is `equals` to the given value. More...

TypeV	remove (Object key)
	Auto-boxing version of remove(long). More...

boolean	remove (Object key, Object Val)
	Auto-boxing version of remove(long,Object). More...

boolean	replace (long 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...

boolean	replace (Long key, TypeV oldValue, TypeV newValue)
	Auto-boxing version of replace. More...

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

TypeV	replace (Long key, TypeV Val)
	Auto-boxing version of replace. 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...

Collection< TypeV >	values ()
	Returns a Collection view of the values contained in this map. More...

Private Member Functions
final boolean	CAS (final long offset, final Object old, final Object nnn)

void	help_copy ()

void	initialize (final int initial_sz)

void	print2 ()

TypeV	putIfMatch (long 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 final int	hash (long h)

static void	print2_impl (final int i, final long K, final Object V)

static void	print_impl (final int i, final long K, final Object V)

static long	rawIndex (final long[] ary, final int idx)

static long	rawIndex (final Object[] ary, final int idx)

static int	reprobe_limit (int len)

Private Attributes
transient CHM	_chm

transient long	_last_resize_milli

final boolean	_opt_for_space

transient ConcurrentAutoTable	_reprobes = new ConcurrentAutoTable()

transient Object	_val_1

Static Private Attributes
static final long	_chm_offset = fieldOffset(NonBlockingHashMapLong.class, "_chm")

static final int	_Lbase = UNSAFE.arrayBaseOffset(long[].class)

static final int	_Lscale = UNSAFE.arrayIndexScale(long[].class)

static final int	_Obase = UNSAFE.arrayBaseOffset(Object[].class)

static final int	_Oscale = UNSAFE.arrayIndexScale(Object[].class)

static final long	_val_1_offset = fieldOffset(NonBlockingHashMapLong.class, "_val_1")

static final Object	MATCH_ANY = new Object()

static final int	MIN_SIZE =(1<<MIN_SIZE_LOG)

static final int	MIN_SIZE_LOG =4

static final long	NO_KEY = 0L

static final Object	NO_MATCH_OLD = new Object()

static final int	REPROBE_LIMIT =10

static final long	serialVersionUID = 1234123412341234124L

static final Prime	TOMBPRIME = new Prime(TOMBSTONE)

static final Object	TOMBSTONE = new Object()

Detailed Description

A lock-free alternate implementation of java.util.concurrent.ConcurrentHashMap with primitive long keys, better scaling properties and generally lower costs.

The use of

long

keys allows for faster compares and lower memory costs. The Map provides identical correctness properties as ConcurrentHashMap. All operations are non-blocking and multi-thread safe, including all update operations. {} scales substatially 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 Niagra box, 8-way Intel box and a 4-way Power box. The main benefit of this class over using plain {} with Long} keys is that it avoids the auto-boxing and unboxing costs. Since auto-boxing is automatic, it is easy to accidentally cause auto-boxing and negate the space and speed benefits. 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 re-probe 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 value.

Since: 1.5

Author: Cliff Click

Parameters

<TypeV> the type of mapped values

Definition at line 89 of file NonBlockingHashMapLong.java.

Constructor & Destructor Documentation

◆ NonBlockingHashMapLong() [1/4]

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

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

Definition at line 219 of file NonBlockingHashMapLong.java.

219 { this(MIN_SIZE,true); }

◆ NonBlockingHashMapLong() [2/4]

com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.NonBlockingHashMapLong ( final int initial_sz )

Create a new NonBlockingHashMapLong 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 226 of file NonBlockingHashMapLong.java.

226 { this(initial_sz,true); }

◆ NonBlockingHashMapLong() [3/4]

com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.NonBlockingHashMapLong ( final boolean opt_for_space )

Create a new NonBlockingHashMapLong, setting the space-for-speed tradeoff.

true

optimizes for space and is the default.

false

optimizes for speed and doubles space costs for roughly a 10% speed improvement.

Definition at line 232 of file NonBlockingHashMapLong.java.

232 { this(1,opt_for_space); }

◆ NonBlockingHashMapLong() [4/4]

com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.NonBlockingHashMapLong	(	final int	initial_sz,
		final boolean	opt_for_space
	)

Create a new NonBlockingHashMapLong, setting both the initial size and the space-for-speed tradeoff.

true

optimizes for space and is the default.

false

optimizes for speed and doubles space costs for roughly a 10% speed improvement.

Definition at line 238 of file NonBlockingHashMapLong.java.

                                                                                      {
     _opt_for_space = opt_for_space;
     initialize(initial_sz);
   }

Member Function Documentation

◆ CAS()

final boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.CAS	(	final long	offset,
		final Object	old,
		final Object	nnn
	)

private

Definition at line 119 of file NonBlockingHashMapLong.java.

                                                                                      {
     return UNSAFE.compareAndSwapObject(this, offset, old, nnn );
   }

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

Here is the caller graph for this function:

◆ clear() [1/2]

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

Removes all of the mappings from this map.

Definition at line 332 of file NonBlockingHashMapLong.java.

                       {         // Smack a new empty table down
     CHM newchm = new CHM(this,new ConcurrentAutoTable(),MIN_SIZE_LOG);
     while( !CAS(_chm_offset,_chm,newchm) ) { /*Spin until the clear works*/}
     CAS(_val_1_offset,_val_1,TOMBSTONE);
   }

Referenced by com.cliffc.aa.HM.HM9.T2.as_flow(), com.cliffc.aa.HM.HM.T2.as_flow(), com.cliffc.aa.util.BitSetSparse.clear(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.clone(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.entrySet(), com.cliffc.aa.tvar.UQNodes.intern(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.keySet(), com.cliffc.aa.HM.HM9.Apply.val(), com.cliffc.aa.HM.HM.Apply.val(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.values().

Here is the caller graph for this function:

◆ clear() [2/2]

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

Definition at line 338 of file NonBlockingHashMapLong.java.

                                    {         // Smack a new empty table down
     _chm.clear();
     CAS(_val_1_offset,_val_1,TOMBSTONE);
   }

◆ clone()

NonBlockingHashMapLong<TypeV> com.cliffc.aa.util.NonBlockingHashMapLong< 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 1290 of file NonBlockingHashMapLong.java.

                                                {
     try {
       // Must clone, to get the class right; NBHML might have been
       // extended so it would be wrong to just make a new NBHML.
       NonBlockingHashMapLong<TypeV> t = (NonBlockingHashMapLong<TypeV>) super.clone();
       // But I don't have an atomic clone operation - the underlying _kvs
       // structure is undergoing rapid change.  If I just clone the _kvs
       // field, the CHM in _kvs[0] won't be in sync.
       //
       // Wipe out the cloned array (it was shallow anyways).
       t.clear();
       // Now copy sanely
       for( long K : keySetLong() )
         t.put(K,get(K));
       return t;
     } catch (CloneNotSupportedException e) {
       // this shouldn't happen, since we are Cloneable
       throw new InternalError();
     }
   }

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

Here is the caller graph for this function:

◆ contains()

boolean com.cliffc.aa.util.NonBlockingHashMapLong< 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 268 of file NonBlockingHashMapLong.java.

268 { return containsValue(val); }

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.entrySet(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.keySet(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.values().

Here is the caller graph for this function:

◆ containsKey() [1/2]

boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.containsKey ( long key )

Tests if the key in the table.

Returns: true if the key is in the table

Definition at line 258 of file NonBlockingHashMapLong.java.

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

Referenced by com.cliffc.aa.tvar.TV2.find_dups(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.keySet().

Here is the caller graph for this function:

◆ containsKey() [2/2]

boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.containsKey ( Object key )

Auto-boxing version of containsKey(long).

Definition at line 386 of file NonBlockingHashMapLong.java.

386 { return (key instanceof Long) && containsKey(((Long) key).longValue()); }

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

Here is the caller graph for this function:

◆ containsValue()

boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.containsValue ( 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

val	value whose presence in this map is to be tested

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

Exceptions

NullPointerException if the specified value is null

Definition at line 349 of file NonBlockingHashMapLong.java.

                                              {
     if( val == null ) return false;
     if( val == _val_1 ) return true; // Key 0
     for( TypeV V : values() )
       if( V == val || V.equals(val) )
         return true;
     return false;
   }

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.contains(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.values().

Here is the caller graph for this function:

◆ elements()

Enumeration<TypeV> com.cliffc.aa.util.NonBlockingHashMapLong< 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 1102 of file NonBlockingHashMapLong.java.

1102 { return new SnapshotV(); }

◆ entrySet()

Set<Map.Entry<Long,TypeV> > com.cliffc.aa.util.NonBlockingHashMapLong< 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 org.jctools.maps.NonBlockingHashMap does not normally create or using java.util.Map.Entry objects so they will be created soley to support this iteration. Iterating using Map#keySet or Map#values will be more efficient. In addition, this version requires auto-boxing the keys.

Definition at line 1235 of file NonBlockingHashMapLong.java.

                                                {
     return new AbstractSet<Map.Entry<Long,TypeV>>() {
       public void    clear   (          ) {        NonBlockingHashMapLong.this.clear( ); }
       public int     size    (          ) { return NonBlockingHashMapLong.this.size ( ); }
       public boolean remove( final Object o ) {
         if (!(o instanceof Map.Entry)) return false;
         final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
         return NonBlockingHashMapLong.this.remove(e.getKey(), e.getValue());
       }
       public boolean contains(final Object o) {
         if (!(o instanceof Map.Entry)) return false;
         final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
         TypeV v = get(e.getKey());
         return v != null && v.equals(e.getValue());
       }
       public Iterator<Map.Entry<Long,TypeV>> iterator() { return new SnapshotE(); }
     };
   }

◆ get() [1/2]

final TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.get ( long 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==k

, then this method returns

v

; otherwise it returns

null

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

Exceptions

NullPointerException if the specified key is null

Definition at line 368 of file NonBlockingHashMapLong.java.

                                      {
     if( key == NO_KEY ) {
       final Object V = _val_1;
       return V == TOMBSTONE ? null : (TypeV)V;
     }
     final Object V = _chm.get_impl(key);
     assert !(V instanceof Prime); // Never return a Prime
     assert V != TOMBSTONE;
     return (TypeV)V;
   }

Referenced by com.cliffc.aa.HM.HM9.T2._as_flow(), com.cliffc.aa.HM.HM.T2._as_flow(), com.cliffc.aa.tvar.TV2._push_update(), com.cliffc.aa.tvar.UQNodes.addAll(), com.cliffc.aa.tvar.UQNodes.equals(), com.cliffc.aa.util.Util.hash_quality_check(), and com.cliffc.aa.type.Type< T extends Type< T >.Key.intern_meet_quality_check().

Here is the caller graph for this function:

◆ get() [2/2]

TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.get ( Object key )

Auto-boxing version of get(long).

Definition at line 380 of file NonBlockingHashMapLong.java.

380 { return (key instanceof Long) ? get (((Long)key).longValue()) : null; }

◆ hash()

static final int com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.hash ( long h )

staticprivate

Definition at line 416 of file NonBlockingHashMapLong.java.

                                         {
     h ^= (h>>>20) ^ (h>>>12);
     h ^= (h>>> 7) ^ (h>>> 4);
     h += h<<7; // smear low bits up high, for hashcodes that only differ by 1
     return (int)h;
   }

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

Here is the caller graph for this function:

◆ help_copy()

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

private

Definition at line 403 of file NonBlockingHashMapLong.java.

                             {
     // Read the top-level CHM only once.  We'll try to help this copy along,
     // even if it gets promoted out from under us (i.e., the copy completes
     // and another KVS becomes the top-level copy).
     CHM topchm = _chm;
     if( topchm._newchm == null ) return; // No copy in-progress
     topchm.help_copy_impl(false);
   }

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

Here is the caller graph for this function:

◆ initialize()

void com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.initialize ( final int initial_sz )

private

Definition at line 242 of file NonBlockingHashMapLong.java.

                                                   {
     if( initial_sz < 0 ) throw new IllegalArgumentException("initial_sz argument must be >= 0");
     int i;                      // Convert to next largest power-of-2
     for( i=MIN_SIZE_LOG; (1<<i) < initial_sz; i++ ) {/*empty*/}
     _chm = new CHM(this,new ConcurrentAutoTable(),i);
     _val_1 = TOMBSTONE;         // Always as-if deleted
     _last_resize_milli = System.currentTimeMillis();
   }

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.NonBlockingHashMapLong(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.readObject().

Here is the caller graph for this function:

◆ keys()

Enumeration<Long> com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.keys ( )

Returns an enumeration of the auto-boxed keys in this table.

Warning: this version will auto-box all returned keys.

Returns: an enumeration of the auto-boxed keys in this table

See also: keySet()

Definition at line 1152 of file NonBlockingHashMapLong.java.

1152 { return new IteratorLong(); }

◆ keySet()

Set<Long> com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.keySet ( )

Returns a Set view of the keys contained in this map; with care the keys may be iterated over without auto-boxing.

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 1168 of file NonBlockingHashMapLong.java.

                             {
     return new AbstractSet<Long> () {
       public void    clear   (          ) {        NonBlockingHashMapLong.this.clear   ( ); }
       public int     size    (          ) { return NonBlockingHashMapLong.this.size    ( ); }
       public boolean contains( Object k ) { return NonBlockingHashMapLong.this.containsKey(k); }
       public boolean remove  ( Object k ) { return NonBlockingHashMapLong.this.remove  (k) != null; }
       public IteratorLong iterator()    { return new IteratorLong(); }
     };
   }

Referenced by com.cliffc.aa.util.Util.hash_quality_check(), com.cliffc.aa.type.Type< T extends Type< T >.Key.intern_meet_quality_check(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.keySetLong(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.writeObject().

Here is the caller graph for this function:

◆ keySetLong()

long [] com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.keySetLong ( )

Keys as a long array.

Array may be zero-padded if keys are concurrently deleted.

Definition at line 1180 of file NonBlockingHashMapLong.java.

                              {
     long[] dom = new long[size()];
     IteratorLong i=(IteratorLong)keySet().iterator();
     int j=0;
     while( j < dom.length && i.hasNext() )
       dom[j++] = i.nextLong();
     return dom;
   }

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

Here is the caller graph for this function:

◆ print()

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

Verbose printout of table internals, useful for debugging.

Definition at line 171 of file NonBlockingHashMapLong.java.

                             {
     System.out.println("=========");
     print_impl(-99,NO_KEY,_val_1);
     _chm.print();
     System.out.println("=========");
   }

◆ print2()

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

private

Definition at line 184 of file NonBlockingHashMapLong.java.

                         {
     System.out.println("=========");
     print2_impl(-99,NO_KEY,_val_1);
     _chm.print();
     System.out.println("=========");
   }

◆ print2_impl()

static void com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.print2_impl	(	final int	i,
		final long	K,
		final Object	V
	)

staticprivate

Definition at line 190 of file NonBlockingHashMapLong.java.

                                                                              {
     if( V != null && Prime.unbox(V) != TOMBSTONE )
       print_impl(i,K,V);
   }

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

Here is the caller graph for this function:

◆ print_impl()

static void com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.print_impl	(	final int	i,
		final long	K,
		final Object	V
	)

staticprivate

Definition at line 177 of file NonBlockingHashMapLong.java.

                                                                             {
     String p = (V instanceof Prime) ? "prime_" : "";
     Object V2 = Prime.unbox(V);
     String VS = (V2 == TOMBSTONE) ? "tombstone" : V2.toString();
     System.out.println("["+i+"]=("+K+","+p+VS+")");
   }

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_impl().

Here is the caller graph for this function:

◆ put() [1/2]

TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.put	(	long	key,
		TypeV	val
	)

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

The value cannot be null.

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

Parameters

key	key with which the specified value is to be associated
val	value to be associated with the specified key

Returns: the previous value associated with key, or null if there was no mapping for key

Exceptions

NullPointerException if the specified value is null

Definition at line 278 of file NonBlockingHashMapLong.java.

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

Referenced by com.cliffc.aa.HM.HM9.T2._as_flow(), com.cliffc.aa.HM.HM.T2._as_flow(), com.cliffc.aa.tvar.UQNodes.add(), com.cliffc.aa.tvar.UQNodes.addAll(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.clone(), com.cliffc.aa.tvar.TV2.find_dups(), com.cliffc.aa.util.Util.hash_quality_check(), com.cliffc.aa.type.Type< T extends Type< T >.Key.intern_meet_quality_check(), com.cliffc.aa.tvar.UQNodes.make(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.readObject(), com.cliffc.aa.tvar.UQNodes.rename(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.NBHMLEntry.setValue(), and com.cliffc.aa.util.BitSetSparse.tset().

Here is the caller graph for this function:

◆ put() [2/2]

TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.put	(	Long	key,
		TypeV	val
	)

Auto-boxing version of put.

Definition at line 392 of file NonBlockingHashMapLong.java.

392 { return put(key.longValue(),val); }

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

Here is the caller graph for this function:

◆ putIfAbsent() [1/2]

TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.putIfAbsent	(	long	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

NullPointerException if the specified is value is null

Definition at line 286 of file NonBlockingHashMapLong.java.

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

Referenced by com.cliffc.aa.HM.HM9.T2.walk_types_in(), and com.cliffc.aa.HM.HM.T2.walk_types_in().

Here is the caller graph for this function:

◆ putIfAbsent() [2/2]

TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.putIfAbsent	(	Long	key,
		TypeV	val
	)

Auto-boxing version of putIfAbsent.

Definition at line 388 of file NonBlockingHashMapLong.java.

388 { return putIfAbsent( key.longValue(), val ); }

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

Here is the caller graph for this function:

◆ putIfMatch()

TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.putIfMatch	(	long	key,
		Object	newVal,
		Object	oldVal
	)

private

Definition at line 312 of file NonBlockingHashMapLong.java.

                                                                      {
     if (oldVal == null || newVal == null)  throw new NullPointerException();
     if( key == NO_KEY ) {
       Object curVal = _val_1;
       if( oldVal == NO_MATCH_OLD || // Do we care about expected-Value at all?
           curVal == oldVal ||       // No instant match already?
           (oldVal == MATCH_ANY && curVal != TOMBSTONE) ||
           oldVal.equals(curVal) ) { // Expensive equals check
         if( !CAS(_val_1_offset,curVal,newVal) ) // One shot CAS update attempt
           curVal = _val_1;                      // Failed; get failing witness
       }
       return curVal == TOMBSTONE ? null : (TypeV)curVal; // Return the last value present
     }
     final Object res = _chm.putIfMatch( key, newVal, oldVal );
     assert !(res instanceof Prime);
     assert res != null;
     return res == TOMBSTONE ? null : (TypeV)res;
   }

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.put(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.putIfAbsent(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.remove(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.SnapshotV.removeKey(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.replace().

Here is the caller graph for this function:

◆ rawIndex() [1/2]

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

staticprivate

Definition at line 108 of file NonBlockingHashMapLong.java.

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

◆ rawIndex() [2/2]

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

staticprivate

Definition at line 100 of file NonBlockingHashMapLong.java.

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

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

Here is the caller graph for this function:

◆ readObject()

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

private

Definition at line 1270 of file NonBlockingHashMapLong.java.

                                                                                                    {
     s.defaultReadObject();      // Read nothing
     initialize(MIN_SIZE);
     for (;;) {
       final long K = s.readLong();
       final TypeV V = (TypeV) s.readObject();
       if( K == NO_KEY && V == null ) break;
       put(K,V);               // Insert with an offical put
     }
   }

◆ remove() [1/4]

TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.remove ( long 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

Definition at line 292 of file NonBlockingHashMapLong.java.

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

Referenced by com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.entrySet(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.keySet(), and com.cliffc.aa.tvar.TV2.reset().

Here is the caller graph for this function:

◆ remove() [2/4]

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

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

Exceptions

NullPointerException if the specified value is null

Definition at line 297 of file NonBlockingHashMapLong.java.

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

◆ remove() [3/4]

TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.remove ( Object key )

Auto-boxing version of remove(long).

Definition at line 382 of file NonBlockingHashMapLong.java.

382 { return (key instanceof Long) ? remove (((Long)key).longValue()) : null; }

◆ remove() [4/4]

boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.remove	(	Object	key,
		Object	Val
	)

Auto-boxing version of remove(long,Object).

Definition at line 384 of file NonBlockingHashMapLong.java.

384 { return (key instanceof Long) && remove(((Long) key).longValue(), Val); }

◆ replace() [1/4]

boolean com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.replace	(	long	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

NullPointerException if the specified value is null

Definition at line 307 of file NonBlockingHashMapLong.java.

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

◆ replace() [2/4]

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

Auto-boxing version of replace.

Definition at line 394 of file NonBlockingHashMapLong.java.

                                                                      {
     return replace(key.longValue(), oldValue, newValue);
   }

◆ replace() [3/4]

TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.replace	(	long	key,
		TypeV	val
	)

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

Exceptions

NullPointerException if the specified value is null

Definition at line 302 of file NonBlockingHashMapLong.java.

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

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

Here is the caller graph for this function:

◆ replace() [4/4]

TypeV com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.replace	(	Long	key,
		TypeV	Val
	)

Auto-boxing version of replace.

Definition at line 390 of file NonBlockingHashMapLong.java.

390 { return replace(key.longValue(), Val); }

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

Here is the caller graph for this function:

◆ reprobe_limit()

static int com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.reprobe_limit ( int len )

staticprivate

Definition at line 210 of file NonBlockingHashMapLong.java.

                                               {
     return REPROBE_LIMIT + (len>>4);
   }

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

Here is the caller graph for this function:

◆ reprobes()

long com.cliffc.aa.util.NonBlockingHashMapLong< 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 202 of file NonBlockingHashMapLong.java.

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

◆ size()

int com.cliffc.aa.util.NonBlockingHashMapLong< 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 255 of file NonBlockingHashMapLong.java.

255 { return (_val_1==TOMBSTONE?0:1) + _chm.size(); }

Referenced by com.cliffc.aa.tvar.UQNodes.addAll(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.entrySet(), com.cliffc.aa.tvar.UQNodes.equals(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.keySet(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.keySetLong(), com.cliffc.aa.tvar.TV2.str(), com.cliffc.aa.tvar.TV2.union(), and com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.values().

Here is the caller graph for this function:

◆ values()

Collection<TypeV> com.cliffc.aa.util.NonBlockingHashMapLong< 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 1118 of file NonBlockingHashMapLong.java.

                                     {
     return new AbstractCollection<TypeV>() {
       public void    clear   (          ) {        NonBlockingHashMapLong.this.clear   ( ); }
       public int     size    (          ) { return NonBlockingHashMapLong.this.size    ( ); }
       public boolean contains( Object v ) { return NonBlockingHashMapLong.this.containsValue(v); }
       public Iterator<TypeV> iterator()   { return new SnapshotV(); }
     };
   }

Referenced by com.cliffc.aa.GVNGCM.add_flow(), com.cliffc.aa.tvar.UQNodes.addAll(), com.cliffc.aa.util.NonBlockingHashMapLong< TypeStruct >.containsValue(), com.cliffc.aa.tvar.TV2.str(), and com.cliffc.aa.tvar.TV2.union().

Here is the caller graph for this function:

◆ writeObject()

void com.cliffc.aa.util.NonBlockingHashMapLong< TypeV >.writeObject ( java.io.ObjectOutputStream s ) throws IOException

private

Definition at line 1256 of file NonBlockingHashMapLong.java.

                                                                              {
     s.defaultWriteObject();     // Write nothing
     for( long K : keySet() ) {
       final Object V = get(K);  // Do an official 'get'
       s.writeLong  (K);         // Write the <long,TypeV> pair
       s.writeObject(V);
     }
     s.writeLong(NO_KEY);        // Sentinel to indicate end-of-data
     s.writeObject(null);
   }