diff options
Diffstat (limited to 'src/main/java')
| -rw-r--r-- | src/main/java/com/seaofnodes/simple/lexer/Lexer.java | 228 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/AbstractEntry.java | 63 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/Ary.java | 367 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/AryInt.java | 203 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/BitSetSparse.java | 39 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/ConcurrentAutoTable.java | 229 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/IBitSet.java | 164 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/IHashMap.java | 32 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/NonBlockingHashMap.java | 1446 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/NonBlockingHashMapLong.java | 1367 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/SB.java | 80 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/Util.java | 207 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/UtilUnsafe.java | 55 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/VBitSet.java | 27 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/util/Work.java | 79 |
15 files changed, 4586 insertions, 0 deletions
diff --git a/src/main/java/com/seaofnodes/simple/lexer/Lexer.java b/src/main/java/com/seaofnodes/simple/lexer/Lexer.java new file mode 100644 index 00000000..06c8f28a --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/lexer/Lexer.java @@ -0,0 +1,228 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ +package com.seaofnodes.simple.lexer; + +import com.seaofnodes.util.AryInt; +import com.seaofnodes.util.SB; + +import java.text.NumberFormat; +import java.text.ParsePosition; + +public class Lexer { + private final String _srcName; // Source for error messages; usually a file name + private final byte[] _buf; + private int _x; // Parser index + private int _lastNWS; // Index of last non-white-space char + private final AryInt _lines; // char offset of each line + + private final NumberFormat _nf; + private final ParsePosition _pp; + private final String _str; + + public Lexer(String srcName, String source) + { + _srcName = srcName; + _buf = source.getBytes(); + _x = 0; + + // Set fields strictly for Java number parsing + _nf = NumberFormat.getInstance(); + _nf.setGroupingUsed(false); + _pp = new ParsePosition(0); + _str = source; // Keep a complete string copy for java number parsing + _lines = new AryInt();// + _lines.push(0); // Line 0 at offset 0 + } + + // Skip WS, return true&skip if match, false & do not skip if miss. + public boolean peek( char c ) { return peek1(skipWS(),c); } + public boolean peek_noWS( char c ) { return peek1(_x >= _buf.length ? -1 : _buf[_x],c); } + // Already skipped WS & have character; + // return true & skip if a match, false& do not skip if a miss. + public boolean peek1( byte c0, char c ) { + assert c0==-1 || c0== _buf[_x]; + if( c0!=c ) return false; + _x++; // Skip peeked character + return true; + } + // Already skipped WS & have character; + // return true&skip if match, false & do not skip if miss. + public boolean peek2( byte c0, String s2 ) { + if( c0 != s2.charAt(0) ) return false; + if( _x+1 >= _buf.length || _buf[_x+1] != s2.charAt(1) ) return false; + _x+=2; // Skip peeked characters + return true; + } + public boolean peek( String s ) { + if( !peek(s.charAt(0)) ) return false; + if( !peek_noWS(s.charAt(1)) ) { _x--; return false; } + return true; + } + // Peek 'c' and NOT followed by 'no' + public boolean peek_not( char c, char no ) { + byte c0 = skipWS(); + if( c0 != c || (_x+1 < _buf.length && _buf[_x+1] == no) ) return false; + _x++; + return true; + } + // Match any of these, and return the match or null + public String peek(String[] toks) { + for( String tok : toks ) if( peek1(tok) ) return tok; + return null; + } + public boolean peek1(String tok) { + for( int i=0; i<tok.length(); i++ ) + if( _x+i >= _buf.length || _buf[_x+i] != tok.charAt(i) ) + return false; + return true; + } + + + /** Advance parse pointer to the first non-whitespace character, and return + * that character, -1 otherwise. */ + public byte skipWS() { + int oldx = _x; + while( _x < _buf.length ) { + byte c = _buf[_x]; + if( c=='/' && _x+1 < _buf.length && _buf[_x+1]=='/' ) { skipEOL() ; continue; } + if( c=='/' && _x+1 < _buf.length && _buf[_x+1]=='*' ) { skipBlock(); continue; } + if( c=='\n' && _x+1 > _lines.last() ) _lines.push(_x+1); + if( !isWS(c) ) { + if( oldx-1 > _lastNWS && !isWS(_buf[oldx-1]) ) _lastNWS = oldx-1; + return c; + } + _x++; + } + return -1; + } + public void skipEOL () { while( _x < _buf.length && _buf[_x] != '\n' ) _x++; } + public void skipBlock() { throw new UnsupportedOperationException("Block comments not yet implemented"); } + // Advance parse pointer to next WS. Used for parser syntax error recovery. + public void skipNonWS() { + while( _x < _buf.length && !isWS(_buf[_x]) ) _x++; + } + + /** Return true if `c` passes a test */ + public static boolean isWS (byte c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; } + public static boolean isAlpha0(byte c) { return ('a'<=c && c <= 'z') || ('A'<=c && c <= 'Z') || (c=='_'); } + public static boolean isAlpha1(byte c) { return isAlpha0(c) || ('0'<=c && c <= '9'); } + public static boolean isJava (byte c) { return isAlpha1(c) || (c=='$') || (c=='.'); } + public static boolean isDigit (byte c) { return '0' <= c && c <= '9'; } + + public String token() { skipWS(); return token0(); } + // Lexical tokens. Any alpha, followed by any alphanumerics is a alpha- + // token; alpha-tokens end with WS or any operator character. Any collection + // of the classic operator characters are a token, except that they will break + // un-ambiguously. + public String token0() { + if( _x >= _buf.length ) return null; + byte c=_buf[_x]; int x = _x; + if( isOp0(c) || (c=='_' && _x+1 < _buf.length && isOp0(_buf[_x+1])) ) + while( _x < _buf.length && isOp1(_buf[_x]) ) _x++; + else if( isAlpha0(c) ) + while( _x < _buf.length && isAlpha1(_buf[_x]) ) _x++; + else return null; // Not a token; specifically excludes e.g. all bytes >= 128, or most bytes < 32 + if( (c==':' || c==',') && _x-x==1 ) // Disallow bare ':' as a token; ambiguous with ?: and type annotations; same for ',' + { _x=x; return null; } // Unwind, not a token + if( c=='-' && _x-x>2 && _buf[x+1]=='>' ) // Disallow leading "->", confusing with function parameter list end; eg "not={x->!x}" + _x=x+2; // Just return the "->" + return new String(_buf,x,_x-x); + } + public boolean isOp(String s) { + if( s==null || s.isEmpty() ) return false; + byte c = (byte)s.charAt(0); + if( !isOp0(c) && (c!='_' || !isOp0((byte)s.charAt(1))) ) return false; + for( int i=1; i<s.length(); i++ ) + if( !isOp1((byte)s.charAt(i)) ) return false; + return true; + } + + // Parse a number; WS already skipped and sitting at a digit. Relies on + // Javas number parsing. + public Number number() { + _pp.setIndex(_x); + Number n = _nf.parse(_str,_pp); + _x = _pp.getIndex(); + if( n instanceof Long ) { + if( _buf[_x-1]=='.' ) _x--; // Java default parser allows "1." as an integer; pushback the '.' + } + return n; + } + + public int field_number() { + byte c = _buf[_x]; + if( !isDigit(c) ) return -1; + _x++; + int sum = c-'0'; + while( _x < _buf.length && isDigit(c=_buf[_x]) ) { + _x++; + sum = sum*10+c-'0'; + } + return sum; + } + + /** Parse a String; _x is at '"'. + * str = [.\%]* // String contents; \t\n\r\% standard escapes + * str = %[num]?[.num]?fact // Percent escape embeds a 'fact' in a string; "name=%name\n" + */ + public String string() { + int oldx = ++_x; + byte c; + while( (c=_buf[_x++]) != '"' ) { + if( c=='%' ) throw new UnsupportedOperationException("Not implemented"); + if( c=='\\' ) throw new UnsupportedOperationException("Not implemented"); + if( _x == _buf.length ) return null; + } + return new String(_buf,oldx,_x-oldx-1).intern(); + } + + public static boolean isOp0(byte c) { return "!#$%*+-=<>^[]~/&|".indexOf(c) != -1; } + public static boolean isOp1(byte c) { return isOp0(c) || ":?_{}".indexOf(c) != -1; } + + public String errLocMsg(String s) { + if( s.charAt(0)=='\n' ) return s; + // find line start + int a=_x; + while( a > 0 && _buf[a-1] != '\n' ) --a; + if( _buf[a]=='\r' ) a++; // do not include leading \n or \n\r + // find line end + int b=_x; + while( b < _buf.length && _buf[b] != '\n' ) b++; + if( b < _buf.length ) b--; // do not include trailing \n or \n\r + // Find line number. Bin-search returns the insertion-point, which is the NEXT + // line unless _x is exactly a line start. + int line = _lines.binary_search(_x); // Find zero-based line insertion point + if( line == _lines._len || _lines.at(line)>_x ) line--; + // error message using 1-based line + SB sb = new SB().p(_srcName).p(':').p(line+1).p(':').p(s).nl(); + sb.p(new String(_buf,a,b-a)).nl(); + int line_start = a; + for( int i=line_start; i<_x; i++ ) + sb.p(' '); + return sb.p('^').nl().toString(); + } + + @Override public String toString() { return new String(_buf,_x,_buf.length-_x); } + @Override public boolean equals(Object loc) { + if( this==loc ) return true; + if( !(loc instanceof Lexer p) ) return false; + return _x==p._x && _srcName.equals(p._srcName); + } + @Override public int hashCode() { + return _srcName.hashCode()+_x; + } +} diff --git a/src/main/java/com/seaofnodes/util/AbstractEntry.java b/src/main/java/com/seaofnodes/util/AbstractEntry.java new file mode 100644 index 00000000..616fb9d0 --- /dev/null +++ b/src/main/java/com/seaofnodes/util/AbstractEntry.java @@ -0,0 +1,63 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import java.util.Map; + +/** + * A simple implementation of {@link java.util.Map.Entry}. + * Does not implement {@link java.util.Map.Entry#setValue}, that is done by users of the class. + * + * @author Cliff Click + * @param <TypeK> the type of keys maintained by this map + * @param <TypeV> the type of mapped values + */ + +abstract class AbstractEntry<TypeK,TypeV> implements Map.Entry<TypeK,TypeV> { + /** Strongly typed key */ + protected final TypeK _key; + /** Strongly typed value */ + protected TypeV _val; + + public AbstractEntry(final TypeK key, final TypeV val) { _key = key; _val = val; } + public AbstractEntry(final Map.Entry<TypeK,TypeV> e ) { _key = e.getKey(); _val = e.getValue(); } + /** Return "key=val" string */ + public String toString() { return _key + "=" + _val; } + /** Return key */ + public TypeK getKey () { return _key; } + /** Return val */ + public TypeV getValue() { return _val; } + + /** Equal if the underlying key & value are equal */ + public boolean equals(final Object o) { + if (!(o instanceof Map.Entry)) return false; + final Map.Entry e = (Map.Entry)o; + return eq(_key, e.getKey()) && eq(_val, e.getValue()); + } + + /** Compute <code>"key.hashCode() ^ val.hashCode()"</code> */ + public int hashCode() { + return + ((_key == null) ? 0 : _key.hashCode()) ^ + ((_val == null) ? 0 : _val.hashCode()); + } + + private static boolean eq(final Object o1, final Object o2) { + return (o1 == null ? o2 == null : o1.equals(o2)); + } +} diff --git a/src/main/java/com/seaofnodes/util/Ary.java b/src/main/java/com/seaofnodes/util/Ary.java new file mode 100644 index 00000000..36654a7f --- /dev/null +++ b/src/main/java/com/seaofnodes/util/Ary.java @@ -0,0 +1,367 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import java.lang.reflect.Array; +import java.util.*; +import java.util.function.Function; +import java.util.function.Predicate; + +// ArrayList with saner syntax +public class Ary<E> implements Iterable<E> { + public E[] _es; + public int _len; + public Ary(E[] es) { this(es,es.length); } + public Ary(E[] es, int len) { if( es.length==0 ) es=Arrays.copyOf(es,1); _es=es; _len=len; } + @SuppressWarnings("unchecked") + public Ary(Class<E> clazz) { this((E[]) Array.newInstance(clazz, 1),0); } + + /** @return list is empty */ + public boolean isEmpty() { return _len==0; } + /** @return active list length */ + public int len() { return _len; } + /** @param i element index + * @return element being returned; throws if OOB + * @exception ArrayIndexOutOfBoundsException if !(0 <= i < _len) + */ + public E at( int i ) { + range_check(i); + return _es[i]; + } + /** @param i element index + * @return element being returned, or null if OOB */ + public E atX( int i ) { + return i < _len ? _es[i] : null; + } + /** @return last element */ + public E last( ) { + range_check(0); + return _es[_len-1]; + } + public void last(int i) { + range_check(i); + E tmp = _es[i]; + _es[i] = _es[_len-1]; + _es[_len-1] = tmp; + } + + /** @return remove and return last element */ + public E pop( ) { + range_check(0); + return _es[--_len]; + } + + /** Add element in amortized constant time + * @param e Element to add at end of list + * @return 'this' for flow-coding */ + public Ary<E> add( E e ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + _es[_len++] = e; + return this; + } + + /** Add element in amortized constant time + * @param e Element to add at end of list + **/ + public E push( E e ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + return (_es[_len++] = e); + } + + /** Slow, linear-time, element insert. Preserves order. + * @param i index to insert at, between 0 and _len inclusive. + * @param e Element to insert + */ + public void insert( int i, E e ) { + if( i < 0 || i>_len ) + throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + System.arraycopy(_es,i,_es,i+1,(_len++)-i); + _es[i] = e; + } + + /** Fast, constant-time, element removal. Does not preserve order + * @param i element to be removed + * @return element removed */ + public E del( int i ) { + range_check(i); + E tmp = _es[i]; + _es[i]=_es[--_len]; + return tmp; + } + + /** Element removal, using '=='. Does not preserve order. + * @param e element to be removed + * @return element removed */ + public E del( E e ) { + for( int i=0; i<_len; i++ ) { + E tmp = _es[i]; + if( tmp==e ) { + _es[i]=_es[--_len]; + return tmp; + } + } + return null; + } + + /** Slow, linear-time, element removal. Preserves order. + * @param i element to be removed + * @return element removed */ + public E remove( int i ) { + range_check(i); + E e = _es[i]; + System.arraycopy(_es,i+1,_es,i,(--_len)-i); + return e; + } + + /** Remove all elements */ + public void clear( ) { _len=0; } + + public void fill( E e ) { Arrays.fill(_es,0,_len,e); } + + /** Extend and set. null fills as needed and does not throw AIOOBE. + * @param i element to set + * @param e value to set + * @return old value + */ + public E setX( int i, E e ) { + if( i >= _len ) Arrays.fill(_es,_len,_es.length,null); + while( i>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + if( i >= _len ) _len = i+1; + return (_es[i] = e); + } + + /** Clear element. Does nothing if element is OOB, since these are clear by + * default. + * @param i element to clear + */ + public void clear( int i ) { if( i<_len ) _es[i]=null; } + + /** Set existing element + * @param i element to set + * @param e value to set + * @return old value + * @exception AIOOBE if !(0 <= i < _len) + */ + public E set( int i, E e ) { + range_check(i); + E old = _es[i]; + _es[i] = e; + return old; + } + + // Increment length, revealing the E behind the _len, or null + public E inc_len( ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + return _es[_len++]; + } + public Ary<E> set_len( int len ) { + if( len > _len ) + while( len>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + _len = len; + while( _es.length > (len<<1) ) // Shrink if hugely too large + _es = Arrays.copyOf(_es,_es.length>>1); + Arrays.fill(_es,len,_es.length,null); + return this; + } + + /** @param c Collection to be added */ + public Ary<E> addAll( Collection<? extends E> c ) { if( c!=null ) for( E e : c ) add(e); return this; } + + /** @param es Array to be added */ + public <F extends E> Ary<E> addAll( F[] es ) { + if( es==null || es.length==0 ) return this; + while( _len+es.length > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + System.arraycopy(es,0,_es,_len,es.length); + _len += es.length; + return this; + } + + /** @param c Collection to be added */ + public Ary<E> addAll( Ary<? extends E> c ) { + if( c==null || c._len==0 ) return this; + while( _len+c._len > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + System.arraycopy(c._es,0,_es,_len,c._len); + _len += c._len; + return this; + } + + /** @return compact array version */ + public E[] asAry() { return Arrays.copyOf(_es,_len); } + + /** @param f function to apply to each element. Updates in-place. */ + public Ary<E> map_update( Function<E,E> f ) { for( int i = 0; i<_len; i++ ) _es[i] = f.apply(_es[i]); return this; } + /** @param P filter out elements failing to pass the predicate; updates in + * place and shuffles list. + * @return this, for flow-coding */ + public Ary<E> filter_update( Predicate<E> P ) { + for( int i=0; i<_len; i++ ) + if( !P.test(_es[i]) ) + del(i--); + return this; + } + /** Sorts in-place + * @param c Comparator to sort by */ + public void sort_update(Comparator<? super E> c ) { Arrays.sort(_es, 0, _len, c); } + /** Find the first matching element using ==, or -1 if none. Note that + * most del calls shuffle the list, so the first element might be random. + * @param e Element to find + * @return index of first matching element, or -1 if none */ + public int find( E e ) { + for( int i=0; i<_len; i++ ) if( _es[i]==e ) return i; + return -1; + } + /** Find the first element matching predicate P, or -1 if none. Note that + * most del calls shuffle the list, so the first element might be random. + * @param P Predicate to match + * @return index of first matching element, or -1 if none */ + public int find( Predicate<E> P ) { + for( int i=0; i<_len; i++ ) if( P.test(_es[i]) ) return i; + return -1; + } + /** Find and replace the first matching element using ==. + * @param old Element to find + * @param nnn Element replacing old + * @return true if replacement happened */ + public boolean replace( E old, E nnn ) { + for( int i=0; i<_len; i++ ) if( _es[i]==old ) { _es[i]=nnn; return true; } + return false; + } + + + /** Merge-Or. Merge 2 sorted Arys, tossing out duplicates. Return a new + * sorted Ary with the merged list. Undefined if the original arrays are + * not sorted. Error if they are not of the same type. Elements must + * implement Comparable. + * @param a0 Sorted Ary to merge + * @param a1 Sorted Ary to merge + * @return A new sorted merged Ary + */ + public static <X extends Comparable<X>> Ary<X> merge_or( Ary<X> a0, Ary<X> a1 ) { + int i=0, j=0; + Ary<X> res = new Ary<>(Arrays.copyOf(a0._es,a0._len+a1._len),0); + + while( i<a0._len && j<a1._len ) { + X x = a0._es[i]; + X y = a1._es[j]; + int cmp = x.compareTo(y); + if( cmp<0 ) { res.add(x); i++; } + else if( cmp>0 ) { res.add(y); j++; } + else { res.add(x); i++; j++; } + } + while( i<a0._len ) res.add(a0._es[i++]); + while( j<a1._len ) res.add(a1._es[j++]); + return res; + } + + /** Merge-Or. Merge two sorted Arys, tossing out duplicates and elements not + * passing the filter. Return a new sorted Ary with the merged list. + * Undefined if the original arrays are not sorted. Error if they are not + * of the same type. Elements must implement Comparable. + * @param a0 Sorted Ary to merge + * @param a1 Sorted Ary to merge + * @param cmpr Comparator + * @param filter Predicate, null means no filter + * @return A new sorted merged Ary + */ + public static <X> Ary<X> merge_or( Ary<X> a0, Ary<X> a1, Comparator<X> cmpr, Predicate<X> filter) { + int i=0, j=0; + Ary<X> res = new Ary<>(Arrays.copyOf(a0._es,a0._len+a1._len),0); + + while( i<a0._len && j<a1._len ) { + X x = a0._es[i]; if( !filter.test(x) ) { i++; continue; } + X y = a1._es[j]; if( !filter.test(y) ) { j++; continue; } + int cmp = cmpr.compare(x,y); + if( cmp<0 ) { res.add(x); i++; } + else if( cmp>0 ) { res.add(y); j++; } + else { res.add(x); i++; j++; } + } + while( i<a0._len ) if( filter.test(a0._es[i++]) ) res.add(a0._es[i-1]); + while( j<a1._len ) if( filter.test(a1._es[j++]) ) res.add(a1._es[j-1]); + return res; + } + + + /** Merge-And. Merge 2 sorted Arys, keeping only duplicates. Return a new + * sorted Ary with the merged list. Undefined if the original arrays are + * not sorted. Error if they are not of the same type. Elements must + * implement Comparable. + * @param a0 Sorted Ary to merge + * @param a1 Sorted Ary to merge + * @return A new sorted merged Ary + */ + public static <X extends Comparable<X>> Ary<X> merge_and( Ary<X> a0, Ary<X> a1 ) { + int i=0, j=0; + Ary<X> res = new Ary<>(Arrays.copyOf(a0._es,Math.min(a0._len,a1._len)),0); + while( i<a0._len && j<a1._len ) { + X x = a0._es[i]; + X y = a1._es[j]; + int cmp = x.compareTo(y); + if( cmp<0 ) { i++; } + else if( cmp>0 ) { j++; } + else { res.add(x); i++; j++; } + } + return res; + } + + /** @return an iterator */ + @Override public Iterator<E> iterator() { return new Iter(); } + private class Iter implements Iterator<E> { + int _i=0; + @Override public boolean hasNext() { return _i<_len; } + @Override public E next() { return _es[_i++]; } + } + + @Override public String toString() { + SB sb = new SB().p('{'); + for( int i=0; i<_len; i++ ) { + if( i>0 ) sb.p(','); + if( _es[i] != null ) sb.p(_es[i].toString()); + } + return sb.p('}').toString(); + } + + private void range_check( int i ) { + if( i < 0 || i>=_len ) + throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + } + + // Note that the hashCode() and equals() are not invariant to changes in the + // underlying array. If the hashCode() is used (e.g., inserting into a + // HashMap) and the then the array changes, the hashCode() will change also. + @Override public boolean equals( Object o ) { + if( this==o ) return true; + if( !(o instanceof Ary ary) ) return false; + if( _len != ary._len ) return false; + if( _es == ary._es ) return true; + for( int i=0; i<_len; i++ ) + if( !(_es[i]==null ? (ary._es[i] == null) : _es[i].equals(ary._es[i])) ) + return false; + return true; + } + @Override public int hashCode( ) { + int sum=_len; + for( int i=0; i<_len; i++ ) + sum += _es[i]==null ? 0 : _es[i].hashCode(); + return sum; + } + + public Ary<E> deepCopy() { + return new Ary<>(_es.clone(),_len); + } +} diff --git a/src/main/java/com/seaofnodes/util/AryInt.java b/src/main/java/com/seaofnodes/util/AryInt.java new file mode 100644 index 00000000..000f4809 --- /dev/null +++ b/src/main/java/com/seaofnodes/util/AryInt.java @@ -0,0 +1,203 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import java.util.Arrays; +import java.util.Collection; +import java.util.function.IntUnaryOperator; + +// ArrayList with saner syntax +public class AryInt { + public int[] _es; + public int _len; + public AryInt(int[] es) { this(es,es.length); } + public AryInt(int[] es, int len) { _es=es; _len=len; } + public AryInt() { this(new int[1],0); } + + /** @return list is empty */ + public boolean isEmpty() { return _len==0; } + /** @return active list length */ + public int len() { return _len; } + /** @param i element index + * @return element being returned; throws if OOB */ + public int at( int i ) { + range_check(i); + return _es[i]; + } + /** @param i element index + * @return element being returned, or 0 if OOB */ + public int atX( int i ) { + return i < _len ? _es[i] : 0; + } + /** @return last element */ + public int last( ) { + range_check(0); + return _es[_len-1]; + } + + /** @return remove and return last element */ + public int pop( ) { + range_check(0); + return _es[--_len]; + } + + /** Add element in amortized constant time + * @param e element to add at end of list + * @return 'this' for flow-coding */ + public AryInt push( int e ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + _es[_len++] = e; + return this; + } + + /** Slow, linear-time, element insert. Preserves order. + * @param i index to insert at, between 0 and _len inclusive. + * @param e intlement to insert + */ + public void insert( int i, int e ) { + if( i < 0 || i>_len ) + throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + System.arraycopy(_es,i,_es,i+1,(_len++)-i); + _es[i] = e; + } + + /** Fast, constant-time, element removal. Does not preserve order + * @param i element to be removed + * @return element removed */ + public int del( int i ) { + range_check(i); + int tmp = _es[i]; + _es[i]=_es[--_len]; + return tmp; + } + + /** Slow, linear-time, element removal. Preserves order. + * @param i element to be removed + * @return element removed */ + public int remove( int i ) { + range_check(i); + int e = _es[i]; + System.arraycopy(_es,i+1,_es,i,(--_len)-i); + return e; + } + + /** Remove all elements */ + public void clear( ) { Arrays.fill(_es,0,_len,0); _len=0; } + + // Extend and set + public int setX( int i, int e ) { + while( i>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + if( i >= _len ) _len = i+1; + return (_es[i] = e); + } + + public int set( int i, int e ) { + range_check(i); + return (_es[i] = e); + } + + public AryInt set_as( int e ) { _es[0] = e; _len=1; return this; } + public AryInt set_len( int len ) { + if( len > _len ) + while( len>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + _len = len; + while( _es.length > (len<<1) ) // Shrink if hugely too large + _es = Arrays.copyOf(_es,_es.length>>1); + return this; + } + + /** @param c Collection to be added */ + public AryInt addAll( Collection<? extends Integer> c ) { for( int e : c ) push(e); return this; } + + /** @param es Array to be added */ + public AryInt addAll( int[] es ) { + if( es.length==0 ) return this; + while( _len+es.length > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + System.arraycopy(es,0,_es,_len,es.length); + _len += es.length; + return this; + } + + public AryInt map_update( IntUnaryOperator f ) { for( int i = 0; i<_len; i++ ) _es[i] = f.applyAsInt(_es[i]); return this; } + + /** @return compact array version, using the internal base array where possible. */ + public int[] asAry() { return _len==_es.length ? _es : Arrays.copyOf(_es,_len); } + + /** Sorts in-place */ + public void sort_update() { Arrays.sort(_es, 0, _len); } + /** Find the first matching element using ==, or -1 if none. Note that + * most del calls shuffle the list, so the first element might be random. + * @param e intlement to find + * @return index of first matching element, or -1 if none */ + public int find( int e ) { + for( int i=0; i<_len; i++ ) if( _es[i]==e ) return i; + return -1; + } + + @Override public String toString() { + SB sb = new SB().p('['); + for( int i=0; i<_len; i++ ) + sb.p(_es[i]).p(','); + return sb.unchar().p(']').toString(); + } + + private void range_check( int i ) { + if( i < 0 || i>=_len ) + throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + } + + // Binary search sorted _es. Returns insertion point. + // Undefined results if _es is not sorted. + public int binary_search( int e ) { + int lo=0, hi=_len-1; + while( lo <= hi ) { + int mid = (hi + lo) >>> 1; // midpoint, rounded down + int mval = _es[mid]; + if( e==mval ) { + // If dups, get to the first. + while( mid>0 && e==_es[mid-1] ) mid--; + return mid; + } + if( e >mval ) lo = mid+1; + else hi = mid-1; + } + return lo; + } + + // Note that the hashCode() and equals() are not invariant to changes in the + // underlying array. If the hashCode() is used (e.g., inserting into a + // HashMap) and the then the array changes, the hashCode() will change also. + @Override public boolean equals( Object o ) { + if( this==o ) return true; + if( !(o instanceof AryInt) ) return false; + AryInt ary = (AryInt)o; + if( _len != ary._len ) return false; + if( _es == ary._es ) return true; + for( int i=0; i<_len; i++ ) + if( _es[i] != ary._es[i] ) + return false; + return true; + } + @Override public int hashCode( ) { + int sum=_len; + for( int i=0; i<_len; i++ ) + sum += _es[i]; + return sum; + } +} diff --git a/src/main/java/com/seaofnodes/util/BitSetSparse.java b/src/main/java/com/seaofnodes/util/BitSetSparse.java new file mode 100644 index 00000000..75438c3f --- /dev/null +++ b/src/main/java/com/seaofnodes/util/BitSetSparse.java @@ -0,0 +1,39 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +// Simple sparse bitset, with a test-and-set. +public class BitSetSparse { + NonBlockingHashMapLong<String> _set = new NonBlockingHashMapLong<>(); + public boolean tset(int b0, int b1) { return tset(((long)b0<<32)|b1); } + public boolean clr (int b0, int b1) { return clr (((long)b0<<32)|b1); } + public boolean tset(long b) { return _set.put(b,"")!=null; } + public boolean clr (long b) { return _set.remove(b)!=null; } + public boolean test(long b) { return _set.get(b)!=null; } + public BitSetSparse clear() { _set.clear(true); return this; } + public int size() { return _set.size(); } + public int cardinality() { return _set.size(); } + @Override public String toString() { + if( _set.size()==0 ) return "[]"; + SB sb = new SB().p('['); + for( long i : _set.keySetLong() ) + if( i >= (1L<<32) ) sb.p('(').p(i>>32).p(',').p(i&0xFFFFFFFFL).p(')').p(','); + else sb.p(i).p(','); + return sb.unchar().p(']').toString(); + } +} diff --git a/src/main/java/com/seaofnodes/util/ConcurrentAutoTable.java b/src/main/java/com/seaofnodes/util/ConcurrentAutoTable.java new file mode 100644 index 00000000..061255be --- /dev/null +++ b/src/main/java/com/seaofnodes/util/ConcurrentAutoTable.java @@ -0,0 +1,229 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import java.io.Serializable; +import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; +import java.util.Arrays; + +import sun.misc.Unsafe; + +/** + * An auto-resizing table of {@code longs}, supporting low-contention CAS + * operations. Updates are done with CAS's to no particular table element. + * The intent is to support highly scalable counters, r/w locks, and other + * structures where the updates are associative, loss-free (no-brainer), and + * otherwise happen at such a high volume that the cache contention for + * CAS'ing a single word is unacceptable. + * + * @since 1.5 + * @author Cliff Click + */ +public class ConcurrentAutoTable implements Serializable { + + // --- public interface --- + + /** + * Add the given value to current counter value. Concurrent updates will + * not be lost, but addAndGet or getAndAdd are not implemented because the + * total counter value (i.e., {@link #get}) is not atomically updated. + * Updates are striped across an array of counters to avoid cache contention + * and has been tested with performance scaling linearly up to 768 CPUs. + */ + public void add( long x ) { add_if( x); } + /** {@link #add} with -1 */ + public void decrement() { add_if(-1L); } + /** {@link #add} with +1 */ + public void increment() { add_if( 1L); } + + /** Atomically set the sum of the striped counters to specified value. + * Rather more expensive than a simple store, in order to remain atomic. + */ + public void set( long x ) { + CAT newcat = new CAT(null,4,x); + // Spin until CAS works + while( !CAS_cat(_cat,newcat) ) {/*empty*/} + } + + /** + * Not-atomic clear + */ + public void clear() { Arrays.fill(_cat._t,0); } + /** + * Current value of the counter. Since other threads are updating furiously + * the value is only approximate, but it includes all counts made by the + * current thread. Requires a pass over the internally striped counters. + */ + public long get() { return _cat.sum(); } + /** Same as {@link #get}, included for completeness. */ + public int intValue() { return (int)_cat.sum(); } + /** Same as {@link #get}, included for completeness. */ + public long longValue() { return _cat.sum(); } + + /** + * A cheaper {@link #get}. Updated only once/millisecond, but as fast as a + * simple load instruction when not updating. + */ + public long estimate_get( ) { return _cat.estimate_sum(); } + + /** + * Return the counter's {@code long} value converted to a string. + */ + public String toString() { return _cat.toString(); } + + /** + * A more verbose print than {@link #toString}, showing internal structure. + * Useful for debugging. + */ + public void print() { _cat.print(); } + + /** + * Return the internal counter striping factor. Useful for diagnosing + * performance problems. + */ + public int internal_size() { return _cat._t.length; } + + // Only add 'x' to some slot in table, hinted at by 'hash'. The sum can + // overflow. Value is CAS'd so no counts are lost. The CAS is retried until + // it succeeds. Returned value is the old value. + private long add_if( long x ) { return _cat.add_if(x,hash(),this); } + + // The underlying array of concurrently updated long counters + private volatile CAT _cat = new CAT(null,1/*Start Small, Think Big!*/,0L); + private static AtomicReferenceFieldUpdater<ConcurrentAutoTable,CAT> _catUpdater = + AtomicReferenceFieldUpdater.newUpdater(ConcurrentAutoTable.class,CAT.class, "_cat"); + private boolean CAS_cat( CAT oldcat, CAT newcat ) { return _catUpdater.compareAndSet(this,oldcat,newcat); } + + // Hash spreader + private static int hash() { + //int h = (int)Thread.currentThread().getId(); + int h = System.identityHashCode(Thread.currentThread()); + return h<<3; // Pad out cache lines. The goal is to avoid cache-line contention + } + + // --- CAT ----------------------------------------------------------------- + private static class CAT implements Serializable { + + // Unsafe crud: get a function which will CAS arrays + private static final Unsafe _unsafe = UtilUnsafe.getUnsafe(); + private static final int _Lbase = _unsafe.arrayBaseOffset(long[].class); + private static final int _Lscale = _unsafe.arrayIndexScale(long[].class); + private static long rawIndex(long[] ary, int i) { + assert i >= 0 && i < ary.length; + return _Lbase + i * _Lscale; + } + private static boolean CAS( long[] A, int idx, long old, long nnn ) { + return _unsafe.compareAndSwapLong( A, rawIndex(A,idx), old, nnn ); + } + + //volatile long _resizers; // count of threads attempting a resize + //static private final AtomicLongFieldUpdater<CAT> _resizerUpdater = + // AtomicLongFieldUpdater.newUpdater(CAT.class, "_resizers"); + + private final CAT _next; + private volatile long _fuzzy_sum_cache; + private volatile long _fuzzy_time; + private static final int MAX_SPIN=1; + private final long[] _t; // Power-of-2 array of longs + + CAT( CAT next, int sz, long init ) { + _next = next; + _t = new long[sz]; + _t[0] = init; + } + + // Only add 'x' to some slot in table, hinted at by 'hash'. The sum can + // overflow. Value is CAS'd so no counts are lost. The CAS is attempted + // ONCE. + public long add_if( long x, int hash, ConcurrentAutoTable master ) { + final long[] t = _t; + final int idx = hash & (t.length-1); + // Peel loop; try once fast + long old = t[idx]; + final boolean ok = CAS( t, idx, old, old+x ); + if( ok ) return old; // Got it + // Try harder + int cnt=0; + while( true ) { + old = t[idx]; + if( CAS( t, idx, old, old+x ) ) break; // Got it! + cnt++; + } + if( cnt < MAX_SPIN ) return old; // Allowable spin loop count + if( t.length >= 1024*1024 ) return old; // too big already + + // Too much contention; double array size in an effort to reduce contention + //long r = _resizers; + //final int newbytes = (t.length<<1)<<3/*word to bytes*/; + //while( !_resizerUpdater.compareAndSet(this,r,r+newbytes) ) + // r = _resizers; + //r += newbytes; + if( master._cat != this ) return old; // Already doubled, don't bother + //if( (r>>17) != 0 ) { // Already too much allocation attempts? + // // We could use a wait with timeout, so we'll wakeup as soon as the new + // // table is ready, or after the timeout in any case. Annoyingly, this + // // breaks the non-blocking property - so for now we just briefly sleep. + // //synchronized( this ) { wait(8*megs); } // Timeout - we always wakeup + // try { Thread.sleep(r>>17); } catch( InterruptedException e ) { } + // if( master._cat != this ) return old; + //} + + CAT newcat = new CAT(this,t.length*2,0); + // Take 1 stab at updating the CAT with the new larger size. If this + // fails, we assume some other thread already expanded the CAT - so we + // do not need to retry until it succeeds. + while( master._cat == this && !master.CAS_cat(this,newcat) ) {/*empty*/} + return old; + } + + + // Return the current sum of all things in the table. Writers can be + // updating the table furiously, so the sum is only locally accurate. + public long sum( ) { + long sum = _next == null ? 0 : _next.sum(); // Recursively get cached sum + final long[] t = _t; + for( long cnt : t ) sum += cnt; + return sum; + } + + // Fast fuzzy version. Used a cached value until it gets old, then re-up + // the cache. + public long estimate_sum( ) { + // For short tables, just do the work + if( _t.length <= 64 ) return sum(); + // For bigger tables, periodically freshen a cached value + long millis = System.currentTimeMillis(); + if( _fuzzy_time != millis ) { // Time marches on? + _fuzzy_sum_cache = sum(); // Get sum the hard way + _fuzzy_time = millis; // Indicate freshness of cached value + } + return _fuzzy_sum_cache; // Return cached sum + } + + public String toString( ) { return Long.toString(sum()); } + + public void print() { + long[] t = _t; + System.out.print("["+t[0]); + for( int i=1; i<t.length; i++ ) + System.out.print(","+t[i]); + System.out.print("]"); + if( _next != null ) _next.print(); + } + } +} diff --git a/src/main/java/com/seaofnodes/util/IBitSet.java b/src/main/java/com/seaofnodes/util/IBitSet.java new file mode 100644 index 00000000..d0d97585 --- /dev/null +++ b/src/main/java/com/seaofnodes/util/IBitSet.java @@ -0,0 +1,164 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import java.util.Iterator; + +// Standard bit-set but supports the notion of an 'infinite extension' of 1. +// i.e. all bits past the end are either 0 or 1. +// Supports update-in-place, mutable, NOT hash-consed +public class IBitSet implements Iterable<Integer> { + private boolean _sign; // false=infinite zeros, true=infinite ones + private final AryInt _bits = new AryInt(); + + // Since mutable, please do not mutate these + public static final IBitSet EMPTY = new IBitSet(); + public static final IBitSet FULL = new IBitSet().flip(); + + private static int idx (int i) { return i>>5; } + private static int mask(int i) { return 1<<(i&31); } + + // Test; returns the value + public boolean tst(int idx) { return _sign != _tst(idx); } + private boolean _tst(int idx) { return (_bits.atX(idx(idx)) & mask(idx)) != 0; } + + // Test and set; returns the old value + public boolean set(int idx) { return _sign ? !_clr(idx) : _set(idx); } + public boolean clr(int idx) { return _sign ? !_set(idx) : _clr(idx); } + + private boolean _set(int idx) { + int widx = idx (idx); + int mask = mask(idx); + int bits = _bits.atX(widx); + _bits.setX(widx, bits | mask); + return (bits&mask)!=0; + } + private boolean _clr(int idx) { + int widx = idx (idx); + int mask = mask(idx); + int bits = _bits.atX(widx); + _bits.setX(widx, bits & ~mask); + while( _bits._len>0 && _bits.last()==0 ) _bits.pop(); // Shrink + return (bits&mask)!=0; + } + // Constant-time, invert all bits + public IBitSet flip() { _sign=!_sign; return this; } + + public int bitCount() { + assert !_sign; // Infinite if sign is set + int sum=0; + for( int i=0; i<_bits._len; i++ ) + sum += Integer.bitCount(_bits._es[i]); + return sum; + } + public int max( ) { + assert !_sign; // Infinite if sign is set + if( _bits._len==0 ) return 0; + return (31 - Integer.numberOfLeadingZeros(_bits.last()))+((_bits._len-1)<<5); + } + + private int wd(int x) { return _bits._es[x]; } + private int xd(int x) { + int b = _bits.atX(x); // zero extend if off end + return _sign ? ~b : b;// adjust for sign + } + + public IBitSet clear() { + _sign=false; + _bits.clear(); + return this; + } + + // OR-into-this + public IBitSet or( IBitSet bs ) { + _sign |= bs._sign; + for( int i=0; i<bs._bits._len; i++ ) + _bits.setX(i,_bits.atX(i)|bs.wd(i)); + return this; + } + // SUBTRACT-from-this + public void subtract( IBitSet bs ) { + for( int i=0; i<bs._bits._len; i++ ) + _bits.setX(i,_bits.atX(i)&~bs.wd(i)); + } + // True if set is empty. The flipped set is never empty. + public boolean is_empty() { return _bits._len==0 && !_sign; } + + // False if any bits in common + public boolean disjoint( IBitSet bs ) { + if( is_empty() ) return true; // Empty set must be disjoint + if( bs.is_empty() ) return true; // Empty set must be disjoint + if( _sign && bs._sign ) return false; // Both extensions are set + IBitSet min = this; + if( _bits._len > bs._bits._len ) { min=bs; bs=this; } // max in bs + if( min._sign && min._bits._len < bs._bits._len ) return false; // Extension in min overlaps last bits in max + for( int i=0; i<min._bits._len; i++ ) + if( (min.wd(i)&bs.wd(i))!= 0 ) + return false; + return true; + } + + // Does 'this' subset 'bs'? + // True if all bits in common: "bs== this.OR (bs)". + public boolean subsetsX( IBitSet bs ) { + assert !bs.is_empty(); // Undefined + int max=Math.max(_bits._len,bs._bits._len); + for( int i=0; i<max; i++ ) + if( (xd(i)|bs.xd(i)) != bs.xd(i) ) // All bits in common + return false; + return true; + } + + @Override public String toString() { return toString(new SB()).toString(); } + public SB toString(SB sb) { + if( _bits._len==0 ) return sb.p(_sign?"[...]":"[]"); + int x = -1; // No range-in-process + sb.p('['); + for( int i=0; i<_bits._len*32+1; i++ ) { + if( tst(i) ) { + if( x==-1 ) x=i; // Start a range + } else { + if( x!=-1 ) { // End a range + if( x+1==i ) sb.p(x).p(','); + else if( x+2==i ) sb.p(x).p(',').p(i-1).p(','); + else sb.p(x).p("...").p(i-1).p(','); + x = -1; + } + } + } + if( x != -1 ) sb.p(x).p("...,"); // Close open range + return sb.unchar().p(']'); + } + + /** @return an iterator */ + @Override public Iterator<Integer> iterator() { return new Iter(); } + private class Iter implements Iterator<Integer> { + int _i=-1; + @Override public boolean hasNext() { + int idx; + while( (idx=idx(++_i)) < _bits._len ) + if( (_bits._es[idx]&mask(_i)) != 0 ) + return true; + return false; + } + @Override public Integer next() { + if( idx(_i) < _bits._len ) return _i; + throw new java.util.NoSuchElementException(); + } + } +} diff --git a/src/main/java/com/seaofnodes/util/IHashMap.java b/src/main/java/com/seaofnodes/util/IHashMap.java new file mode 100644 index 00000000..0663c473 --- /dev/null +++ b/src/main/java/com/seaofnodes/util/IHashMap.java @@ -0,0 +1,32 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import java.util.Set; + +@SuppressWarnings("unchecked") +public class IHashMap { + private final NonBlockingHashMap _map = new NonBlockingHashMap(); + public <T> T put(T kv) { _map.put(kv,kv); return kv; } + public <T> T put(T k, T v) { _map.put(k,v); return v; } + public <T> T get(T key) { return (T)_map.get(key); } + public void remove(Object key) { _map.remove(key); } + public void clear() { _map.clear(true); } + public boolean isEmpty() { return _map.isEmpty(); } + public <T> Set<T> keySet() { return _map.keySet(); } +} diff --git a/src/main/java/com/seaofnodes/util/NonBlockingHashMap.java b/src/main/java/com/seaofnodes/util/NonBlockingHashMap.java new file mode 100644 index 00000000..b2ff5b70 --- /dev/null +++ b/src/main/java/com/seaofnodes/util/NonBlockingHashMap.java @@ -0,0 +1,1446 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import sun.misc.Unsafe; + +import java.io.IOException; +import java.io.Serializable; +import java.lang.reflect.Field; +import java.util.*; +import java.util.concurrent.ConcurrentMap; +import java.util.concurrent.atomic.AtomicLongFieldUpdater; +import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; + +/* + * Written by Cliff Click and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +/** + * A lock-free alternate implementation of {@link 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. {@link NonBlockingHashMap} scales substantially better than + * {@link 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 {@link + * java.util.Hashtable}, and includes versions of methods corresponding to + * each method of <tt>Hashtable</tt>. However, even though all operations are + * thread-safe, operations do <em>not</em> entail locking and there is + * <em>not</em> any support for locking the entire table in a way that + * prevents all access. This class is fully interoperable with + * <tt>Hashtable</tt> in programs that rely on its thread safety but not on + * its synchronization details. + * + * <p> Operations (including <tt>put</tt>) generally do not block, so may + * overlap with other update operations (including other <tt>puts</tt> and + * <tt>removes</tt>). Retrievals reflect the results of the most recently + * <em>completed</em> update operations holding upon their onset. For + * aggregate operations such as <tt>putAll</tt>, 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 + * <em>not</em> throw {@link ConcurrentModificationException}. However, + * iterators are designed to be used by only one thread at a time. + * + * <p> 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). + * + * <p>This class and its views and iterators implement all of the + * <em>optional</em> methods of the {@link Map} and {@link Iterator} + * interfaces. + * + * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class + * does <em>not</em> allow <tt>null</tt> to be used as a key or value. + * + * + * @since 1.5 + * @author Cliff Click + * @param <TypeK> the type of keys maintained by this map + * @param <TypeV> the type of mapped values + */ + +public class NonBlockingHashMap<TypeK, TypeV> + extends AbstractMap<TypeK, TypeV> + implements ConcurrentMap<TypeK, TypeV>, Cloneable, Serializable { + + private static final long serialVersionUID = 1234123412341234123L; + + private static final int REPROBE_LIMIT=10; // Too many reprobes then force a table-resize + + // --- Bits to allow Unsafe access to arrays + private static final Unsafe _unsafe = UtilUnsafe.getUnsafe(); + private static final int _Obase = _unsafe.arrayBaseOffset(Object[].class); + private static final int _Oscale = _unsafe.arrayIndexScale(Object[].class); + private static final int _Olog = _Oscale==4?2:(_Oscale==8?3:9999); + private static long rawIndex(final Object[] ary, final int idx) { + 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 << _Olog); + } + + // --- Setup to use Unsafe + private static final long _kvs_offset; + static { // <clinit> + Field f = null; + try { f = NonBlockingHashMap.class.getDeclaredField("_kvs"); } + catch( java.lang.NoSuchFieldException e ) { throw new RuntimeException(e); } + _kvs_offset = _unsafe.objectFieldOffset(f); + } + private boolean CAS_kvs( final Object[] oldkvs, final Object[] newkvs ) { + return _unsafe.compareAndSwapObject(this, _kvs_offset, oldkvs, newkvs ); + } + + // --- Adding a 'prime' bit onto Values via wrapping with a junk wrapper class + private static final class Prime { + final Object _V; + Prime( Object V ) { _V = V; } + static Object unbox( Object V ) { return V instanceof Prime ? ((Prime)V)._V : V; } + } + + // --- hash ---------------------------------------------------------------- + // Helper function to spread lousy hashCodes + private static int hash( final Object key) { + int h = key.hashCode(); // The real hashCode call + h ^= (h>>>20) ^ (h>>>12); + h ^= (h>>> 7) ^ (h>>> 4); + return h; + } + + + + // --- The Hash Table -------------------- + // Slot 0 is always used for a 'CHM' entry below to hold the interesting + // bits of the hash table. Slot 1 holds full hashes as an array of ints. + // Slots {2,3}, {4,5}, etc hold {Key,Value} pairs. The entire hash table + // can be atomically replaced by CASing the _kvs field. + // + // Why is CHM buried inside the _kvs Object array, instead of the other way + // around? The CHM info is used during resize events and updates, but not + // during standard 'get' operations. I assume 'get' is much more frequent + // than 'put'. 'get' can skip the extra indirection of skipping through the + // CHM to reach the _kvs array. + private transient Object[] _kvs; + private static CHM chm ( Object[] kvs) { return (CHM )kvs[0]; } + private static int[] hashes( Object[] kvs) { return (int[])kvs[1]; } + // Number of K,V pairs in the table + private static int len( Object[] kvs) { return (kvs.length-2)>>1; } + + // Time since last resize + private transient long _last_resize_milli; + + // --- Minimum table size ---------------- + // Pick size 4 K/V pairs, which turns into (4*2+2)*4+12 = 54 bytes on a + // standard 32-bit HotSpot, and (4*2+2)*8+12 = 92 bytes on 64-bit JVM. + private static final int MIN_SIZE_LOG=2; // + private static final int MIN_SIZE=(1<<MIN_SIZE_LOG); // Must be power of 2 + + // --- Sentinels ------------------------- + // No-Match-Old - putIfMatch does updates only if it matches the old value, + // and NO_MATCH_OLD basically counts as a wildcard match. + private static final Object NO_MATCH_OLD = new Object(); // Sentinel + // Match-Any-not-null - putIfMatch does updates only if it find a real old + // value. + private static final Object MATCH_ANY = new Object(); // Sentinel + // This K/V pair has been deleted (but the Key slot is forever claimed). + // The same Key can be reinserted with a new value later. + public static final Object TOMBSTONE = new Object(); + // Prime'd or box'd version of TOMBSTONE. This K/V pair was deleted, then a + // table resize started. The K/V pair has been marked so that no new + // updates can happen to the old table (and since the K/V pair was deleted + // nothing was copied to the new table). + private static final Prime TOMBPRIME = new Prime(TOMBSTONE); + + // --- key,val ------------------------------------------------------------- + // Access K,V for a given idx + // + // Note that these are static, so that the caller is forced to read the _kvs + // field only once, and share that read across all key/val calls - lest the + // _kvs field move out from under us and back-to-back key & val calls refer + // to different _kvs arrays. + private static Object key( Object[] kvs, int idx) { return kvs[(idx<<1)+2]; } + private static Object val( Object[] kvs, int idx) { return kvs[(idx<<1)+3]; } + private static boolean CAS_key( Object[] kvs, int idx, Object old, Object key ) { + return _unsafe.compareAndSwapObject( kvs, rawIndex(kvs,(idx<<1)+2), old, key ); + } + private static boolean CAS_val( Object[] kvs, int idx, Object old, Object val ) { + return _unsafe.compareAndSwapObject( kvs, rawIndex(kvs,(idx<<1)+3), old, val ); + } + + + // --- dump ---------------------------------------------------------------- + /** Verbose printout of table internals, useful for debugging. */ + public final void print() { + System.out.println("========="); + print2(_kvs); + System.out.println("========="); + } + // print the entire state of the table + private void print( Object[] kvs ) { + for( int i=0; i<len(kvs); i++ ) { + Object K = key(kvs,i); + if( K != null ) { + String KS = (K == TOMBSTONE) ? "XXX" : K.toString(); + Object V = val(kvs,i); + Object U = Prime.unbox(V); + String p = (V==U) ? "" : "prime_"; + String US = (U == TOMBSTONE) ? "tombstone" : U.toString(); + System.out.println(""+i+" ("+KS+","+p+US+")"); + } + } + Object[] newkvs = chm(kvs)._newkvs; // New table, if any + if( newkvs != null ) { + System.out.println("----"); + print(newkvs); + } + } + // print only the live values, broken down by the table they are in + private final void print2( Object[] kvs) { + for( int i=0; i<len(kvs); i++ ) { + Object key = key(kvs,i); + Object val = val(kvs,i); + Object U = Prime.unbox(val); + if( key != null && key != TOMBSTONE && // key is sane + val != null && U != TOMBSTONE ) { // val is sane + String p = (val==U) ? "" : "prime_"; + System.out.println(""+i+" ("+key+","+p+val+")"); + } + } + Object[] newkvs = chm(kvs)._newkvs; // New table, if any + if( newkvs != null ) { + System.out.println("----"); + print2(newkvs); + } + } + + // Count of reprobes + private transient AryInt _reprobes = null; + + /** 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. + * @return the count of reprobes since the last call to {@link #reprobes} + * or since the table was created. */ + public AryInt reprobes() { return _reprobes==null ? (_reprobes = new AryInt()) : _reprobes; } + public int len() { return len(_kvs); } + private void record( int ps ) { if( _reprobes!=null ) _record(ps); } + private void _record( int ps ) { _reprobes.setX(ps,_reprobes.atX(ps)+1); } + + + // --- reprobe_limit ----------------------------------------------------- + // Heuristic to decide if we have reprobed toooo many times. Running over + // the reprobe limit on a 'get' call acts as a 'miss'; on a 'put' call it + // can trigger a table resize. Several places must have exact agreement on + // what the reprobe_limit is, so we share it here. + private static int reprobe_limit( int len ) { + return REPROBE_LIMIT + (len>>4); + } + + // --- NonBlockingHashMap -------------------------------------------------- + // Constructors + + /** 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). */ + public NonBlockingHashMap( ) { this(MIN_SIZE); } + + /** 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. */ + public NonBlockingHashMap( final int initial_sz ) { initialize(initial_sz); } + private void initialize( int initial_sz ) { + if( initial_sz < 0 ) throw new IllegalArgumentException(); + int i; // Convert to next largest power-of-2 + if( initial_sz > 1024*1024 ) initial_sz = 1024*1024; + for( i=MIN_SIZE_LOG; (1<<i) < initial_sz; i++ ) ; + // Double size for K,V pairs, add 1 for CHM and 1 for hashes + _kvs = new Object[((1<<i)<<1)+2]; + _kvs[0] = new CHM(new ConcurrentAutoTable()); // CHM in slot 0 + _kvs[1] = new int[1<<i]; // Matching hash entries + _last_resize_milli = System.currentTimeMillis(); + } + // Version for subclassed readObject calls, to be called after the defaultReadObject + protected final void initialize() { initialize(MIN_SIZE); } + + // --- wrappers ------------------------------------------------------------ + + /** Returns the number of key-value mappings in this map. + * @return the number of key-value mappings in this map */ + @Override + public int size ( ) { return chm(_kvs).size(); } + /** Returns <tt>size() == 0</tt>. + * @return <tt>size() == 0</tt> */ + @Override + public boolean isEmpty ( ) { return size() == 0; } + + /** Tests if the key in the table using the <tt>equals</tt> method. + * @return <tt>true</tt> if the key is in the table using the <tt>equals</tt> method + * @throws NullPointerException if the specified key is null */ + @Override + public boolean containsKey( Object key ) { return get(key) != null; } + + /** Legacy method testing if some key maps into the specified value in this + * table. This method is identical in functionality to {@link + * #containsValue}, and exists solely to ensure full compatibility with + * class {@link java.util.Hashtable}, which supported this method prior to + * introduction of the Java Collections framework. + * @param val a value to search for + * @return <tt>true</tt> if this map maps one or more keys to the specified value + * @throws NullPointerException if the specified value is null */ + public boolean contains ( Object val ) { return containsValue(val); } + + /** Maps the specified key to the specified value in the table. Neither key + * nor value can be null. + * <p> The value can be retrieved by calling {@link #get} with a key that is + * equal to the original key. + * @param key key with which the specified value is to be associated + * @param val value to be associated with the specified key + * @return the previous value associated with <tt>key</tt>, or + * <tt>null</tt> if there was no mapping for <tt>key</tt> + * @throws NullPointerException if the specified key or value is null */ + @Override + public TypeV put ( TypeK key, TypeV val ) { return putIfMatch( key, val, NO_MATCH_OLD); } + + /** Atomically, do a {@link #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. + * @return the previous value associated with the specified key, + * or <tt>null</tt> if there was no mapping for the key + * @throws NullPointerException if the specified key or value is null */ + public TypeV putIfAbsent( TypeK key, TypeV val ) { return putIfMatch( key, val, TOMBSTONE ); } + + /** Removes the key (and its corresponding value) from this map. + * This method does nothing if the key is not in the map. + * @return the previous value associated with <tt>key</tt>, or + * <tt>null</tt> if there was no mapping for <tt>key</tt> + * @throws NullPointerException if the specified key is null */ + @Override + public TypeV remove ( Object key ) { return putIfMatch( key,TOMBSTONE, NO_MATCH_OLD); } + + /** Atomically do a {@link #remove(Object)} if-and-only-if the key is mapped + * to a value which is <code>equals</code> to the given value. + * @throws NullPointerException if the specified key or value is null */ + public boolean remove ( Object key,Object val ) { return putIfMatch( key,TOMBSTONE, val ) == val; } + + /** Atomically do a <code>put(key,val)</code> if-and-only-if the key is + * mapped to some value already. + * @throws NullPointerException if the specified key or value is null */ + public TypeV replace ( TypeK key, TypeV val ) { return putIfMatch( key, val,MATCH_ANY ); } + + /** Atomically do a <code>put(key,newValue)</code> if-and-only-if the key is + * mapped a value which is <code>equals</code> to <code>oldValue</code>. + * @throws NullPointerException if the specified key or value is null */ + public boolean replace ( TypeK key, TypeV oldValue, TypeV newValue ) { + return putIfMatch( key, newValue, oldValue ) == oldValue; + } + + + // Atomically replace newVal for oldVal, returning the value that existed + // there before. If oldVal is the returned value, then newVal was inserted, + // otherwise not. A null oldVal means the key does not exist (only insert if + // missing); a null newVal means to remove the key. + @SuppressWarnings("unchecked") + public final TypeV putIfMatchAllowNull( Object key, Object newVal, Object oldVal ) { + if( oldVal == null ) oldVal = TOMBSTONE; + if( newVal == null ) newVal = TOMBSTONE; + final TypeV res = (TypeV)putIfMatch( this, _kvs, key, newVal, oldVal ); + assert !(res instanceof Prime); + //assert res != null; + return res == TOMBSTONE ? null : res; + } + + @SuppressWarnings("unchecked") + private final TypeV putIfMatch( Object key, Object newVal, Object oldVal ) { + if (oldVal == null || newVal == null) throw new NullPointerException(); + final Object res = putIfMatch( this, _kvs, key, newVal, oldVal ); + assert !(res instanceof Prime); + assert res != null; + return res == TOMBSTONE ? null : (TypeV)res; + } + + + /** Copies all of the mappings from the specified map to this one, replacing + * any existing mappings. + * @param m mappings to be stored in this map */ + @Override + public void putAll(Map<? extends TypeK, ? extends TypeV> m) { + for (Map.Entry<? extends TypeK, ? extends TypeV> e : m.entrySet()) + put(e.getKey(), e.getValue()); + } + + /** Removes all of the mappings from this map. */ + @Override + public void clear() { // Smack a new empty table down + Object[] newkvs = new NonBlockingHashMap(MIN_SIZE)._kvs; + while( !CAS_kvs(_kvs,newkvs) ) // Spin until the clear works + ; + } + // Non-atomic clear, preserving existing large arrays + public void clear(boolean large) { // Smack a new empty table down + for( int i=2; i<_kvs.length; i++ ) _kvs[i]=null; + Arrays.fill(hashes(_kvs),0); + chm(_kvs).clear(); + } + + /** Returns <tt>true</tt> if this Map maps one or more keys to the specified + * value. <em>Note</em>: This method requires a full internal traversal of the + * hash table and is much slower than {@link #containsKey}. + * @param val value whose presence in this map is to be tested + * @return <tt>true</tt> if this map maps one or more keys to the specified value + * @throws NullPointerException if the specified value is null */ + @Override + public boolean containsValue( final Object val ) { + if( val == null ) throw new NullPointerException(); + for( TypeV V : values() ) + if( V == val || V.equals(val) ) + return true; + return false; + } + + // This function is supposed to do something for Hashtable, and the JCK + // tests hang until it gets called... by somebody ... for some reason, + // any reason.... + protected void rehash() { + } + + /** + * 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. + * + * @return a clone of the hashtable. + */ + @SuppressWarnings("unchecked") + @Override + public Object clone() { + try { + // Must clone, to get the class right; NBHM might have been + // extended, so it would be wrong to just make a new NBHM. + NonBlockingHashMap<TypeK,TypeV> t = (NonBlockingHashMap<TypeK,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( TypeK K : keySet() ) { + final TypeV V = get(K); // Do an official 'get' + t.put(K,V); + } + return t; + } catch (CloneNotSupportedException e) { + // this shouldn't happen, since we are Cloneable + throw new InternalError(); + } + } + + /** + * 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 <tt>entrySet</tt> view's iterator, enclosed in braces + * (<tt>"{}"</tt>). Adjacent mappings are separated by the characters + * <tt>", "</tt> (comma and space). Each key-value mapping is rendered as + * the key followed by an equals sign (<tt>"="</tt>) followed by the + * associated value. Keys and values are converted to strings as by + * {@link String#valueOf(Object)}. + * + * @return a string representation of this map + */ + @Override + public String toString() { + Iterator<Entry<TypeK,TypeV>> i = entrySet().iterator(); + if( !i.hasNext()) + return "{}"; + + StringBuilder sb = new StringBuilder(); + sb.append('{'); + for (;;) { + Entry<TypeK,TypeV> e = i.next(); + TypeK key = e.getKey(); + TypeV value = e.getValue(); + sb.append(key == this ? "(this Map)" : key); + sb.append('='); + sb.append(value == this ? "(this Map)" : value); + if( !i.hasNext()) + return sb.append('}').toString(); + sb.append(", "); + } + } + + // Get *any* valid Key. Useful for making worklists out of a hashtable - the + // hashtable can remove dup work. Repeated calls probably return the same + // Key, so only useful if keys are removed after calling. + @SuppressWarnings("unchecked") + public TypeK getKey() { return (TypeK)_getKey(_kvs); } + private static Object _getKey(Object[] kvs) { + for( int i=0; i<len(kvs); i++ ) { + Object key = key(kvs,i); + Object val = val(kvs,i); + Object U = Prime.unbox(val); + if( key != null && key != TOMBSTONE && // key is sane + val != null && U != TOMBSTONE ) // val is sane + return key; + } + Object[] newkvs = chm(kvs)._newkvs; // New table, if any + return newkvs == null ? null : _getKey(newkvs); + } + + // --- keyeq --------------------------------------------------------------- + // Check for key equality. Try direct pointer compare first, then see if + // the hashes are unequal (fast negative test) and finally do the full-on + // 'equals' v-call. + private static boolean keyeq( Object K, Object key, int[] hashes, int hash, int fullhash ) { + return + K==key || // Either keys match exactly OR + // hash exists and matches? hash can be zero during the install of a + // new key/value pair. + ((hashes[hash] == 0 || hashes[hash] == fullhash) && + // Do not call the users' "equals()" call with a Tombstone, as this can + // surprise poorly written "equals()" calls that throw exceptions + // instead of simply returning false. + K != TOMBSTONE && // Do not call users' equals call with a Tombstone + // Do the match the hard way - with the users' key being the loop- + // invariant "this" pointer. I could have flipped the order of + // operands (since equals is commutative), but I'm making mega-morphic + // v-calls in a reprobing loop and nailing down the 'this' argument + // gives both the JIT and the hardware a chance to prefetch the call target. + key.equals(K)); // Finally do the hard match + } + + // --- get ----------------------------------------------------------------- + /** Returns the value to which the specified key is mapped, or {@code null} + * if this map contains no mapping for the key. + * <p>More formally, if this map contains a mapping from a key {@code k} to + * a value {@code v} such that {@code key.equals(k)}, then this method + * returns {@code v}; otherwise it returns {@code null}. (There can be at + * most one such mapping.) + * @throws NullPointerException if the specified key is null */ + // Never returns a Prime nor a Tombstone. + @SuppressWarnings("unchecked") + @Override + public TypeV get( Object key ) { + final Object V = get_impl(this,_kvs,key); + assert !(V instanceof Prime); // Never return a Prime + assert V != TOMBSTONE; + return (TypeV)V; + } + + private static Object get_impl( final NonBlockingHashMap topmap, final Object[] kvs, final Object key ) { + final int fullhash= hash (key); // throws NullPointerException if key is null + final int len = len (kvs); // Count of key/value pairs, reads kvs.length + final CHM chm = chm (kvs); // The CHM, for a volatile read below; reads slot 0 of kvs + final int[] hashes=hashes(kvs); // The memoized hashes; reads slot 1 of kvs + + int idx = fullhash & (len-1); // First key hash + + // Main spin/reprobe loop, looking for a Key hit + int reprobe_cnt=0; + try { + while( true ) { + // Probe table. Each read of 'val' probably misses in cache in a big + // table; hopefully the read of 'key' then hits in cache. + final Object K = key(kvs,idx); // Get key before volatile read, could be null + final Object V = val(kvs,idx); // Get value before volatile read, could be null or Tombstone or Prime + if( K == null ) return null; // A clear miss + + // We need a volatile-read here to preserve happens-before semantics on + // newly inserted Keys. If the Key body was written just before inserting + // into the table a Key-compare here might read the uninitialized Key body. + // Annoyingly this means we have to volatile-read before EACH key compare. + // . + // We also need a volatile-read between reading a newly inserted Value + // and returning the Value (so the user might end up reading the stale + // Value contents). Same problem as with keys - and the one volatile + // read covers both. + final Object[] newkvs = chm._newkvs; // VOLATILE READ before key compare + + // Key-compare + if( keyeq(K,key,hashes,idx,fullhash) ) { + // Key hit! Check for no table-copy-in-progress + if( !(V instanceof Prime) ) // No copy? + return (V == TOMBSTONE) ? null : V; // Return the value + // Key hit - but slot is (possibly partially) copied to the new table. + // Finish the copy & retry in the new table. + return get_impl(topmap,chm.copy_slot_and_check(topmap,kvs,idx,key),key); // Retry in the new table + } + // get and put must have the same key lookup logic! But only 'put' + // needs to force a table-resize for a too-long key-reprobe sequence. + // Check for too-many-reprobes on get - and flip to the new table. + if( ++reprobe_cnt >= reprobe_limit(len) || // too many probes + K == TOMBSTONE ) // found a TOMBSTONE key, means no more keys in this table + return newkvs == null ? null : get_impl(topmap,topmap.help_copy(newkvs),key); // Retry in the new table + + idx = (idx+((fullhash>>16)|1))&(len-1); // Divergent reprobe chain + } + } finally { + topmap.record(reprobe_cnt); + } + } + + // --- getk ----------------------------------------------------------------- + /** Returns the Key to which the specified key is mapped, or {@code null} + * if this map contains no mapping for the key. + * @throws NullPointerException if the specified key is null */ + // Never returns a Prime nor a Tombstone. + @SuppressWarnings("unchecked") + public TypeK getk( TypeK key ) { + return (TypeK)getk_impl(this,_kvs,key); + } + + private static final Object getk_impl( final NonBlockingHashMap topmap, final Object[] kvs, final Object key ) { + final int fullhash= hash (key); // throws NullPointerException if key is null + final int len = len (kvs); // Count of key/value pairs, reads kvs.length + final CHM chm = chm (kvs); // The CHM, for a volatile read below; reads slot 0 of kvs + final int[] hashes=hashes(kvs); // The memoized hashes; reads slot 1 of kvs + + int idx = fullhash & (len-1); // First key hash + + // Main spin/reprobe loop, looking for a Key hit + int reprobe_cnt=0; + try { + while( true ) { + // Probe table. + final Object K = key(kvs,idx); // Get key before volatile read, could be null + if( K == null ) return null; // A clear miss + + // We need a volatile-read here to preserve happens-before semantics on + // newly inserted Keys. If the Key body was written just before inserting + // into the table a Key-compare here might read the uninitialized Key body. + // Annoyingly this means we have to volatile-read before EACH key compare. + // . + // We also need a volatile-read between reading a newly inserted Value + // and returning the Value (so the user might end up reading the stale + // Value contents). Same problem as with keys - and the one volatile + // read covers both. + final Object[] newkvs = chm._newkvs; // VOLATILE READ before key compare + + // Key-compare + if( keyeq(K,key,hashes,idx,fullhash) ) + return K; // Return existing Key! + + // get and put must have the same key lookup logic! But only 'put' + // needs to force a table-resize for a too-long key-reprobe sequence. + // Check for too-many-reprobes on get - and flip to the new table. + if( ++reprobe_cnt >= reprobe_limit(len) || // too many probes + K == TOMBSTONE ) { // found a TOMBSTONE key, means no more keys in this table + return newkvs == null ? null : getk_impl(topmap,topmap.help_copy(newkvs),key); // Retry in the new table + } + + idx = (idx+((fullhash>>16)|1))&(len-1); // Divergent reprobe chain + } + } finally { + topmap.record(reprobe_cnt); + } + } + + // --- putIfMatch --------------------------------------------------------- + // Put, Remove, PutIfAbsent, etc. Return the old value. If the returned + // value is equal to expVal (or expVal is NO_MATCH_OLD) then the put can be + // assumed to work (although might have been immediately overwritten). Only + // the path through copy_slot passes in an expected value of null, and + // putIfMatch only returns a null if passed in an expected null. + static volatile int DUMMY_VOLATILE; + private static final Object putIfMatch( final NonBlockingHashMap topmap, final Object[] kvs, final Object key, final Object putval, final Object expVal ) { + assert putval != null; + assert !(putval instanceof Prime); + assert !(expVal instanceof Prime); + final int fullhash = hash (key); // throws NullPointerException if key null + final int len = len (kvs); // Count of key/value pairs, reads kvs.length + final CHM chm = chm (kvs); // Reads kvs[0] + final int[] hashes = hashes(kvs); // Reads kvs[1], read before kvs[0] + int idx = fullhash & (len-1); + + // --- + // Key-Claim stanza: spin till we can claim a Key (or force a resizing). + int reprobe_cnt=0; + Object K=null, V=null; + Object[] newkvs=null; + try { + while( true ) { // Spin till we get a Key slot + V = val(kvs,idx); // Get old value (before volatile read below!) + K = key(kvs,idx); // Get current key + if( K == null ) { // Slot is free? + // Found an empty Key slot - which means this Key has never been in + // this table. No need to put a Tombstone - the Key is not here! + if( putval == TOMBSTONE ) return putval; // Not-now & never-been in this table + if( expVal == MATCH_ANY ) return null; // Will not match, even after K inserts + // Claim the null key-slot + if( CAS_key(kvs,idx, null, key ) ) { // Claim slot for Key + chm._slots.add(1); // Raise key-slots-used count + hashes[idx] = fullhash; // Memoize fullhash + break; // Got it! + } + // CAS to claim the key-slot failed. + // + // This re-read of the Key points out an annoying short-coming of Java + // CAS. Most hardware CAS's report back the existing value - so that + // if you fail you have a *witness* - the value which caused the CAS to + // fail. The Java API turns this into a boolean destroying the + // witness. Re-reading does not recover the witness because another + // thread can write over the memory after the CAS. Hence we can be in + // the unfortunate situation of having a CAS fail *for cause* but + // having that cause removed by a later store. This turns a + // non-spurious-failure CAS (such as Azul has) into one that can + // apparently spuriously fail - and we avoid apparent spurious failure + // by not allowing Keys to ever change. + + // Volatile read, to force loads of K to retry despite JIT, otherwise + // it is legal to e.g. haul the load of "K = key(kvs,idx);" outside of + // this loop (since failed CAS ops have no memory ordering semantics). + int dummy = DUMMY_VOLATILE; + continue; + } + // Key slot was not null, there exists a Key here + + // We need a volatile-read here to preserve happens-before semantics on + // newly inserted Keys. If the Key body was written just before inserting + // into the table a Key-compare here might read the uninitialized Key body. + // Annoyingly this means we have to volatile-read before EACH key compare. + newkvs = chm._newkvs; // VOLATILE READ before key compare + + if( keyeq(K,key,hashes,idx,fullhash) ) + break; // Got it! + + // get and put must have the same key lookup logic! Lest 'get' give + // up looking too soon. + //topmap._reprobes.add(1); + if( ++reprobe_cnt >= reprobe_limit(len) || // too many probes or + K == TOMBSTONE ) { // found a TOMBSTONE key, means no more keys + // We simply must have a new table to do a 'put'. At this point a + // 'get' will also go to the new table (if any). We do not need + // to claim a key slot (indeed, we cannot find a free one to claim!). + newkvs = chm.resize(topmap,kvs); + if( expVal != null ) topmap.help_copy(newkvs); // help along an existing copy + return putIfMatch(topmap,newkvs,key,putval,expVal); + } + + idx = (idx+((fullhash>>16)|1))&(len-1); // Divergent reprobe chain + } // End of spinning till we get a Key slot + } finally { + topmap.record(reprobe_cnt); + } + + // --- + // Found the proper Key slot, now update the matching Value slot. We + // never put a null, so Value slots monotonically move from null to + // not-null (deleted Values use Tombstone). Thus if 'V' is null we + // fail this fast cutout and fall into the check for table-full. + if( putval == V ) return V; // Fast cutout for no-change + + // See if we want to move to a new table (to avoid high average re-probe + // counts). We only check on the initial set of a Value from null to + // not-null (i.e., once per key-insert). Of course we got a 'free' check + // of newkvs once per key-compare (not really free, but paid-for by the + // time we get here). + if( newkvs == null && // New table-copy already spotted? + // Once per fresh key-insert check the hard way + ((V == null && chm.tableFull(reprobe_cnt,len)) || + // Or we found a Prime, but the JMM allowed reordering such that we + // did not spot the new table (very rare race here: the writing + // thread did a CAS of _newkvs then a store of a Prime. This thread + // reads the Prime, then reads _newkvs - but the read of Prime was so + // delayed (or the read of _newkvs was so accelerated) that they + // swapped and we still read a null _newkvs. The resize call below + // will do a CAS on _newkvs forcing the read. + V instanceof Prime) ) + newkvs = chm.resize(topmap,kvs); // Force the new table copy to start + // See if we are moving to a new table. + // If so, copy our slot and retry in the new table. + if( newkvs != null ) + return putIfMatch(topmap,chm.copy_slot_and_check(topmap,kvs,idx,expVal),key,putval,expVal); + + // --- + // We are finally prepared to update the existing table + assert !(V instanceof Prime); + + // Must match old, and we do not? Then bail out now. Note that either V + // or expVal might be TOMBSTONE. Also V can be null, if we've never + // inserted a value before. expVal can be null if we are called from + // copy_slot. + + if( expVal != NO_MATCH_OLD && // Do we care about expected-Value at all? + V != expVal && // No instant match already? + (expVal != MATCH_ANY || V == TOMBSTONE || V == null) && + !(V==null && expVal == TOMBSTONE) && // Match on null/TOMBSTONE combo + (expVal == null || !expVal.equals(V)) ) // Expensive equals check at the last + return V; // Do not update! + + // Actually change the Value in the Key,Value pair + if( CAS_val(kvs, idx, V, putval ) ) { + // CAS succeeded - we did the update! + // Both normal put's and table-copy calls putIfMatch, but table-copy + // does not (effectively) increase the number of live k/v pairs. + if( expVal != null ) { + // Adjust sizes - a striped counter + if( (V == null || V == TOMBSTONE) && putval != TOMBSTONE ) chm._size.add( 1); + if( !(V == null || V == TOMBSTONE) && putval == TOMBSTONE ) chm._size.add(-1); + } + } else { // Else CAS failed + V = val(kvs,idx); // Get new value + // If a Prime'd value got installed, we need to re-run the put on the + // new table. Otherwise we lost the CAS to another racing put. + // Simply retry from the start. + if( V instanceof Prime ) + return putIfMatch(topmap,chm.copy_slot_and_check(topmap,kvs,idx,expVal),key,putval,expVal); + } + // Win or lose the CAS, we are done. If we won then we know the update + // happened as expected. If we lost, it means "we won but another thread + // immediately stomped our update with no chance of a reader reading". + return (V==null && expVal!=null) ? TOMBSTONE : V; + } + + // --- help_copy --------------------------------------------------------- + // Help along an existing resize operation. This is just a fast cut-out + // wrapper, to encourage inlining for the fast no-copy-in-progress case. We + // always help the top-most table copy, even if there are nested table + // copies in progress. + private final Object[] help_copy( Object[] helper ) { + // Read the top-level KVS 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). + Object[] topkvs = _kvs; + CHM topchm = chm(topkvs); + if( topchm._newkvs == null ) return helper; // No copy in-progress + topchm.help_copy_impl(this,topkvs,false); + return helper; + } + + + // --- CHM ----------------------------------------------------------------- + // The control structure for the NonBlockingHashMap + private static final class CHM<TypeK,TypeV> { + // Size in active K,V pairs + private final ConcurrentAutoTable _size; + public int size () { return (int)_size.get(); } + + // --- + // These next 2 fields are used in the resizing heuristics, to judge when + // it is time to resize or copy the table. Slots is a count of used-up + // key slots, and when it nears a large fraction of the table we probably + // end up reprobing too much. Last-resize-milli is the time since the + // last resize; if we are running back-to-back resizes without growing + // (because there are only a few live keys but many slots full of dead + // keys) then we need a larger table to cut down on the churn. + + // Count of used slots, to tell when table is full of dead unusable slots + private final ConcurrentAutoTable _slots; + public int slots() { return (int)_slots.get(); } + + // --- + // New mappings, used during resizing. + // The 'new KVs' array - created during a resize operation. This + // represents the new table being copied from the old one. It's the + // volatile variable that is read as we cross from one table to the next, + // to get the required memory orderings. It monotonically transits from + // null to set (once). + volatile Object[] _newkvs; + private final AtomicReferenceFieldUpdater<CHM,Object[]> _newkvsUpdater = + AtomicReferenceFieldUpdater.newUpdater(CHM.class,Object[].class, "_newkvs"); + // Set the _next field if we can. + boolean CAS_newkvs( Object[] newkvs ) { + while( _newkvs == null ) + if( _newkvsUpdater.compareAndSet(this,null,newkvs) ) + return true; + return false; + } + + // Sometimes many threads race to create a new very large table. Only 1 + // wins the race, but the losers all allocate a junk large table with + // hefty allocation costs. Attempt to control the overkill here by + // throttling attempts to create a new table. I cannot really block here + // (lest I lose the non-blocking property) but late-arriving threads can + // give the initial resizing thread a little time to allocate the initial + // new table. The Right Long Term Fix here is to use array-lets and + // incrementally create the new very large array. In C I'd make the array + // with malloc (which would mmap under the hood) which would only eat + // virtual-address and not real memory - and after Somebody wins then we + // could in parallel initialize the array. Java does not allow + // un-initialized array creation (especially of ref arrays!). + volatile long _resizers; // count of threads attempting an initial resize + private static final AtomicLongFieldUpdater<CHM> _resizerUpdater = + AtomicLongFieldUpdater.newUpdater(CHM.class, "_resizers"); + + // --- + // Simple constructor + CHM( ConcurrentAutoTable size ) { + _size = size; + _slots= new ConcurrentAutoTable(); + } + + // Fast, not-atomic clear + public void clear() { _size.clear(); _slots.clear(); } + + // --- tableFull --------------------------------------------------------- + // Heuristic to decide if this table is too full, and we should start a + // new table. Note that if a 'get' call has reprobed too many times and + // decided the table must be full, then always the estimate_sum must be + // high and we must report the table is full. If we do not, then we might + // end up deciding that the table is not full and inserting into the + // current table, while a 'get' has decided the same key cannot be in this + // table because of too many reprobes. The invariant is: + // slots.estimate_sum >= max_reprobe_cnt >= reprobe_limit(len) + private final boolean tableFull( int reprobe_cnt, int len ) { + return + // Do the cheap check first: we allow some number of reprobes always + reprobe_cnt >= REPROBE_LIMIT && + (reprobe_cnt >= reprobe_limit(len) || + // More expensive check: see if the table is > 1/2 full. + _slots.estimate_get() >= (len>>1)); + } + + // --- resize ------------------------------------------------------------ + // Resizing after too many probes. "How Big???" heuristics are here. + // Callers will (not this routine) will 'help_copy' any in-progress copy. + // Since this routine has a fast cutout for copy-already-started, callers + // MUST 'help_copy' lest we have a path which forever runs through + // 'resize' only to discover a copy-in-progress which never progresses. + private final Object[] resize( NonBlockingHashMap topmap, Object[] kvs) { + assert chm(kvs) == this; + + // Check for resize already in progress, probably triggered by another thread + Object[] newkvs = _newkvs; // VOLATILE READ + if( newkvs != null ) // See if resize is already in progress + return newkvs; // Use the new table already + + // No copy in-progress, so start one. First up: compute new table size. + int oldlen = len(kvs); // Old count of K,V pairs allowed + int sz = size(); // Get current table count of active K,V pairs + int newsz = sz; // First size estimate + + // Heuristic to determine new size. We expect plenty of dead-slots-with-keys + // and we need some decent padding to avoid endless reprobing. + if( sz >= (oldlen>>2) ) { // If we are >25% full of keys then... + newsz = oldlen<<1; // Double size, so new table will be between 12.5% and 25% full + // For tables less than 1M entries, if >50% full of keys then... + // For tables more than 1M entries, if >75% full of keys then... + if( 4L*sz >= ((oldlen>>20)!=0?3L:2L)*oldlen ) + newsz = oldlen<<2; // Double double size, so new table will be between %12.5 (18.75%) and 25% (25%) + } + // This heuristic in the next 2 lines leads to a much denser table + // with a higher reprobe rate + //if( sz >= (oldlen>>1) ) // If we are >50% full of keys then... + // newsz = oldlen<<1; // Double size + + // Last (re)size operation was very recent? Then double again; slows + // down resize operations for tables subject to a high key churn rate. + long tm = System.currentTimeMillis(); + long q=0; + if( newsz <= oldlen && // New table would shrink or hold steady? + (tm <= topmap._last_resize_milli+10000 || // Recent resize (less than 10 sec ago) + (q=_slots.estimate_get()) >= (sz<<1)) ) // 1/2 of keys are dead? + newsz = oldlen<<1; // Double the existing size + + // Do not shrink, ever + if( newsz < oldlen ) newsz = oldlen; + + // Convert to power-of-2 + int log2; + for( log2=MIN_SIZE_LOG; (1<<log2) < newsz; log2++ ) ; // Compute log2 of size + long len = ((1L << log2) << 1) + 2; + // prevent integer overflow - limit of 2^31 elements in a Java array + // so here, 2^30 + 2 is the largest number of elements in the hash table + if ((int)len!=len) { + log2 = 30; + len = (1L << log2) + 2; + if (sz > ((len >> 2) + (len >> 1))) throw new RuntimeException("Table is full."); + } + + // Now limit the number of threads actually allocating memory to a + // handful - lest we have 750 threads all trying to allocate a giant + // resized array. + long r = _resizers; + while( !_resizerUpdater.compareAndSet(this,r,r+1) ) + r = _resizers; + // Size calculation: 2 words (K+V) per table entry, plus a handful. We + // guess at 64-bit pointers; 32-bit pointers screws up the size calc by + // 2x but does not screw up the heuristic very much. + long megs = ((((1L<<log2)<<1)+8)<<3/*word to bytes*/)>>20/*megs*/; + if( r >= 2 && megs > 0 ) { // Already 2 guys trying; wait and see + newkvs = _newkvs; // Between dorking around, another thread did it + if( newkvs != null ) // See if resize is already in progress + return newkvs; // Use the new table already + // TODO - use a wait with timeout, so we'll wakeup as soon as the new table + // is ready, or after the timeout in any case. + //synchronized( this ) { wait(8*megs); } // Timeout - we always wakeup + // For now, sleep a tad and see if the 2 guys already trying to make + // the table actually get around to making it happen. + try { Thread.sleep(megs); } catch( Exception e ) { } + } + // Last check, since the 'new' below is expensive and there is a chance + // that another thread slipped in a new thread while we ran the heuristic. + newkvs = _newkvs; + if( newkvs != null ) // See if resize is already in progress + return newkvs; // Use the new table already + + // Double size for K,V pairs, add 1 for CHM + newkvs = new Object[(int)len]; // This can get expensive for big arrays + newkvs[0] = new CHM(_size); // CHM in slot 0 + newkvs[1] = new int[1<<log2]; // hashes in slot 1 + + // Another check after the slow allocation + if( _newkvs != null ) // See if resize is already in progress + return _newkvs; // Use the new table already + + // The new table must be CAS'd in so only 1 winner amongst duplicate + // racing resizing threads. Extra CHM's will be GC'd. + if( CAS_newkvs( newkvs ) ) { // NOW a resize-is-in-progress! + //notifyAll(); // Wake up any sleepers + //long nano = System.nanoTime(); + //System.out.println(" "+nano+" Resize from "+oldlen+" to "+(1<<log2)+" and had "+(_resizers-1)+" extras" ); + //if( System.out != null ) System.out.print("["+log2); + topmap.rehash(); // Call for Hashtable's benefit + } else // CAS failed? + newkvs = _newkvs; // Reread new table + return newkvs; + } + + + // The next part of the table to copy. It monotonically transits from zero + // to _kvs.length. Visitors to the table can claim 'work chunks' by + // CAS'ing this field up, then copying the indicated indices from the old + // table to the new table. Workers are not required to finish any chunk; + // the counter simply wraps and work is copied duplicately until somebody + // somewhere completes the count. + volatile long _copyIdx = 0; + static private final AtomicLongFieldUpdater<CHM> _copyIdxUpdater = + AtomicLongFieldUpdater.newUpdater(CHM.class, "_copyIdx"); + + // Work-done reporting. Used to efficiently signal when we can move to + // the new table. From 0 to len(oldkvs) refers to copying from the old + // table to the new. + volatile long _copyDone= 0; + static private final AtomicLongFieldUpdater<CHM> _copyDoneUpdater = + AtomicLongFieldUpdater.newUpdater(CHM.class, "_copyDone"); + + // --- help_copy_impl ---------------------------------------------------- + // Help along an existing resize operation. We hope its the top-level + // copy (it was when we started) but this CHM might have been promoted out + // of the top position. + private final void help_copy_impl( NonBlockingHashMap topmap, Object[] oldkvs, boolean copy_all ) { + assert chm(oldkvs) == this; + Object[] newkvs = _newkvs; + assert newkvs != null; // Already checked by caller + int oldlen = len(oldkvs); // Total amount to copy + final int MIN_COPY_WORK = Math.min(oldlen,1024); // Limit per-thread work + + // --- + int panic_start = -1; + int copyidx=-9999; // Fool javac to think it's initialized + while( _copyDone < oldlen ) { // Still needing to copy? + // Carve out a chunk of work. The counter wraps around so every + // thread eventually tries to copy every slot repeatedly. + + // We "panic" if we have tried TWICE to copy every slot - and it still + // has not happened. i.e., twice some thread somewhere claimed they + // would copy 'slot X' (by bumping _copyIdx) but they never claimed to + // have finished (by bumping _copyDone). Our choices become limited: + // we can wait for the work-claimers to finish (and become a blocking + // algorithm) or do the copy work ourselves. Tiny tables with huge + // thread counts trying to copy the table often 'panic'. + if( panic_start == -1 ) { // No panic? + copyidx = (int)_copyIdx; + while( !_copyIdxUpdater.compareAndSet(this,copyidx,copyidx+MIN_COPY_WORK) ) + copyidx = (int)_copyIdx; // Re-read + if( !(copyidx < (oldlen<<1)) ) // Panic! + panic_start = copyidx; // Record where we started to panic-copy + } + + // We now know what to copy. Try to copy. + int workdone = 0; + for( int i=0; i<MIN_COPY_WORK; i++ ) + if( copy_slot(topmap,(copyidx+i)&(oldlen-1),oldkvs,newkvs) ) // Made an oldtable slot go dead? + workdone++; // Yes! + if( workdone > 0 ) // Report work-done occasionally + copy_check_and_promote( topmap, oldkvs, workdone );// See if we can promote + + copyidx += MIN_COPY_WORK; + // Uncomment these next 2 lines to turn on incremental table-copy. + // Otherwise this thread continues to copy until it is all done. + if( !copy_all && panic_start == -1 ) // No panic? + return; // Then done copying after doing MIN_COPY_WORK + } + // Extra promotion check, in case another thread finished all copying + // then got stalled before promoting. + copy_check_and_promote( topmap, oldkvs, 0 );// See if we can promote + } + + // --- copy_slot_and_check ----------------------------------------------- + // Copy slot 'idx' from the old table to the new table. If this thread + // confirmed the copy, update the counters and check for promotion. + // + // Returns the result of reading the volatile _newkvs, mostly as a + // convenience to callers. We come here with 1-shot copy requests + // typically because the caller has found a Prime, and has not yet read + // the _newkvs volatile - which must have changed from null-to-not-null + // before any Prime appears. So the caller needs to read the _newkvs + // field to retry his operation in the new table, but probably has not + // read it yet. + private final Object[] copy_slot_and_check( NonBlockingHashMap topmap, Object[] oldkvs, int idx, Object should_help ) { + assert chm(oldkvs) == this; + Object[] newkvs = _newkvs; // VOLATILE READ + // We're only here because the caller saw a Prime, which implies a + // table-copy is in progress. + assert newkvs != null; + if( copy_slot(topmap,idx,oldkvs,_newkvs) ) // Copy the desired slot + copy_check_and_promote(topmap, oldkvs, 1); // Record the slot copied + // Generically help along any copy (except if called recursively from a helper) + return (should_help == null) ? newkvs : topmap.help_copy(newkvs); + } + + // --- copy_check_and_promote -------------------------------------------- + private final void copy_check_and_promote( NonBlockingHashMap topmap, Object[] oldkvs, int workdone ) { + assert chm(oldkvs) == this; + int oldlen = len(oldkvs); + // We made a slot unusable and so did some of the needed copy work + long copyDone = _copyDone; + assert (copyDone+workdone) <= oldlen; + if( workdone > 0 ) { + while( !_copyDoneUpdater.compareAndSet(this,copyDone,copyDone+workdone) ) { + copyDone = _copyDone; // Reload, retry + assert (copyDone+workdone) <= oldlen; + } + //if( (10*copyDone/oldlen) != (10*(copyDone+workdone)/oldlen) ) + //System.out.print(" "+(copyDone+workdone)*100/oldlen+"%"+"_"+(_copyIdx*100/oldlen)+"%"); + } + + // Check for copy being ALL done, and promote. Note that we might have + // nested in-progress copies and manage to finish a nested copy before + // finishing the top-level copy. We only promote top-level copies. + if( copyDone+workdone == oldlen && // Ready to promote this table? + topmap._kvs == oldkvs && // Looking at the top-level table? + // Attempt to promote + topmap.CAS_kvs(oldkvs,_newkvs) ) { + topmap._last_resize_milli = System.currentTimeMillis(); // Record resize time for next check + //long nano = System.nanoTime(); + //System.out.println(" "+nano+" Promote table to "+len(_newkvs)); + //if( System.out != null ) System.out.print("]"); + } + } + + // --- copy_slot --------------------------------------------------------- + // Copy one K/V pair from oldkvs[i] to newkvs. Returns true if we can + // confirm that the new table guaranteed has a value for this old-table + // slot. We need an accurate confirmed-copy count so that we know when we + // can promote (if we promote the new table too soon, other threads may + // 'miss' on values not-yet-copied from the old table). We don't allow + // any direct updates on the new table, unless they first happened to the + // old table - so that any transition in the new table from null to + // not-null must have been from a copy_slot (or other old-table overwrite) + // and not from a thread directly writing in the new table. Thus we can + // count null-to-not-null transitions in the new table. + private boolean copy_slot( NonBlockingHashMap topmap, int idx, Object[] oldkvs, Object[] newkvs ) { + // Blindly set the key slot from null to TOMBSTONE, to eagerly stop + // fresh put's from inserting new values in the old table when the old + // table is mid-resize. We don't need to act on the results here, + // because our correctness stems from box'ing the Value field. Slamming + // the Key field is a minor speed optimization. + Object key; + while( (key=key(oldkvs,idx)) == null ) + CAS_key(oldkvs,idx, null, TOMBSTONE); + + // --- + // Prevent new values from appearing in the old table. + // Box what we see in the old table, to prevent further updates. + Object oldval = val(oldkvs,idx); // Read OLD table + while( !(oldval instanceof Prime) ) { + final Prime box = (oldval == null || oldval == TOMBSTONE) ? TOMBPRIME : new Prime(oldval); + if( CAS_val(oldkvs,idx,oldval,box) ) { // CAS down a box'd version of oldval + // If we made the Value slot hold a TOMBPRIME, then we both + // prevented further updates here but also the (absent) + // oldval is vacuously available in the new table. We + // return with true here: any thread looking for a value for + // this key can correctly go straight to the new table and + // skip looking in the old table. + if( box == TOMBPRIME ) + return true; + // Otherwise we boxed something, but it still needs to be + // copied into the new table. + oldval = box; // Record updated oldval + break; // Break loop; oldval is now boxed by us + } + oldval = val(oldkvs,idx); // Else try, try again + } + if( oldval == TOMBPRIME ) return false; // Copy already complete here! + + // --- + // Copy the value into the new table, but only if we overwrite a null. + // If another value is already in the new table, then somebody else + // wrote something there and that write is happens-after any value that + // appears in the old table. If putIfMatch does not find a null in the + // new table - somebody else should have recorded the null-not_null + // transition in this copy. + Object old_unboxed = ((Prime)oldval)._V; + assert old_unboxed != TOMBSTONE; + putIfMatch(topmap, newkvs, key, old_unboxed, null); + + // --- + // Finally, now that any old value is exposed in the new table, we can + // forever hide the old-table value by slapping a TOMBPRIME down. This + // will stop other threads from uselessly attempting to copy this slot + // (i.e., it's a speed optimization not a correctness issue). + while( oldval != TOMBPRIME && !CAS_val(oldkvs,idx,oldval,TOMBPRIME) ) + oldval = val(oldkvs,idx); + + return true; + } // end copy_slot + } // End of CHM + + + // --- Snapshot ------------------------------------------------------------ + // The main class for iterating over the NBHM. It "snapshots" a clean + // view of the K/V array. + private class SnapshotV implements Iterator<TypeV>, Enumeration<TypeV> { + final Object[] _sskvs; + public SnapshotV() { + while( true ) { // Verify no table-copy-in-progress + Object[] topkvs = _kvs; + CHM topchm = chm(topkvs); + if( topchm._newkvs == null ) { // No table-copy-in-progress + // The "linearization point" for the iteration. Every key in this + // table will be visited, but keys added later might be skipped or + // even be added to a following table (also not iterated over). + _sskvs = topkvs; + break; + } + // Table copy in-progress - so we cannot get a clean iteration. We + // must help finish the table copy before we can start iterating. + topchm.help_copy_impl(NonBlockingHashMap.this,topkvs,true); + } + // Warm-up the iterator + next(); + } + int length() { return len(_sskvs); } + Object key(int idx) { return NonBlockingHashMap.key(_sskvs,idx); } + Object val(int idx) { return NonBlockingHashMap.val(_sskvs,idx); } + private int _idx; // Varies from 0-keys.length + private Object _nextK, _prevK; // Last 2 keys found + private TypeV _nextV, _prevV; // Last 2 values found + public boolean hasNext() { return _nextV != null; } + @SuppressWarnings("unchecked") + public TypeV next() { + // 'next' actually knows what the next value will be - it had to + // figure that out last go-around lest 'hasNext' report true and + // some other thread deleted the last value. Instead, 'next' + // spends all its effort finding the key that comes after the + // 'next' key. + if( _idx != 0 && _nextV == null ) throw new NoSuchElementException(); + _prevK = _nextK; // This will become the previous key + _prevV = _nextV; // This will become the previous value + _nextV = null; // We have no more next-key + Object nV; + // Attempt to set <_nextK,_nextV> to the next K,V pair. + // _nextV is the trigger: stop searching when it is != null + while( _idx<length() ) { // Scan array + _nextK = key(_idx++); // Get a key that definitely is in the set (for the moment!) + if( _nextK != null && // Found something? + _nextK != TOMBSTONE && // Key is not TOMBSTONE + // Keys can be deleted and not TOMBSTONE, and after deletion had + // their innards gutted... so you cannot use them to compute their + // own hash or 'get' a Value. So get the paired Value directly. + (nV=val(_idx-1)) != null && // Get value + nV != TOMBSTONE ) // Value is not TOMBSTONE + { _nextV = (TypeV)nV; break; } // Got it! _nextK/_nextV is a valid Key/Value + } // Else keep scanning + return _prevV; // Return current value. + } + public void remove() { + if( _prevV == null ) throw new IllegalStateException(); + putIfMatch( NonBlockingHashMap.this, _sskvs, _prevK, TOMBSTONE, _prevV ); + _prevV = null; + } + + public TypeV nextElement() { return next(); } + public boolean hasMoreElements() { return hasNext(); } + } + public Object[] raw_array() { return new SnapshotV()._sskvs; } + + /** Returns an enumeration of the values in this table. + * @return an enumeration of the values in this table + * @see #values() */ + public Enumeration<TypeV> elements() { return new SnapshotV(); } + + // --- values -------------------------------------------------------------- + /** Returns a {@link 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 + * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, + * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. + * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. + * + * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator that + * will never throw {@link 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. */ + @Override + public Collection<TypeV> values() { + return new AbstractCollection<TypeV>() { + @Override public void clear ( ) { NonBlockingHashMap.this.clear ( ); } + @Override public int size ( ) { return NonBlockingHashMap.this.size ( ); } + @Override public boolean contains( Object v ) { return NonBlockingHashMap.this.containsValue(v); } + @Override public Iterator<TypeV> iterator() { return new SnapshotV(); } + }; + } + + // --- keySet -------------------------------------------------------------- + @SuppressWarnings("unchecked") + private class SnapshotK implements Iterator<TypeK>, Enumeration<TypeK> { + final SnapshotV _ss; + public SnapshotK() { _ss = new SnapshotV(); } + public void remove() { _ss.remove(); } + public TypeK next() { _ss.next(); return (TypeK)_ss._prevK; } + public boolean hasNext() { return _ss.hasNext(); } + public TypeK nextElement() { return next(); } + public boolean hasMoreElements() { return hasNext(); } + } + + /** Returns an enumeration of the keys in this table. + * @return an enumeration of the keys in this table + * @see #keySet() */ + public Enumeration<TypeK> keys() { return new SnapshotK(); } + + /** Returns a {@link 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 <tt>Iterator.remove</tt>, + * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and + * <tt>clear</tt> operations. It does not support the <tt>add</tt> or + * <tt>addAll</tt> operations. + * + * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator that + * will never throw {@link 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. */ + @Override + public Set<TypeK> keySet() { + return new AbstractSet<TypeK> () { + @Override public void clear ( ) { NonBlockingHashMap.this.clear ( ); } + @Override public int size ( ) { return NonBlockingHashMap.this.size ( ); } + @Override public boolean contains( Object k ) { return NonBlockingHashMap.this.containsKey(k); } + @Override public boolean remove ( Object k ) { return NonBlockingHashMap.this.remove (k) != null; } + @Override public Iterator<TypeK> iterator() { return new SnapshotK(); } + }; + } + + + // --- entrySet ------------------------------------------------------------ + // Warning: Each call to 'next' in this iterator constructs a new NBHMEntry. + private class NBHMEntry extends AbstractEntry<TypeK,TypeV> { + NBHMEntry( final TypeK k, final TypeV v ) { super(k,v); } + public TypeV setValue(final TypeV val) { + if( val == null ) throw new NullPointerException(); + _val = val; + return put(_key, val); + } + } + + @SuppressWarnings("unchecked") + private class SnapshotE implements Iterator<Map.Entry<TypeK,TypeV>> { + final SnapshotV _ss; + public SnapshotE() { _ss = new SnapshotV(); } + public void remove() { _ss.remove(); } + public Map.Entry<TypeK,TypeV> next() { _ss.next(); return new NBHMEntry((TypeK)_ss._prevK,_ss._prevV); } + public boolean hasNext() { return _ss.hasNext(); } + } + + /** Returns a {@link 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 + * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>, + * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support + * the <tt>add</tt> or <tt>addAll</tt> operations. + * + * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator + * that will never throw {@link 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. + * + * <p><strong>Warning:</strong> the iterator associated with this Set + * requires the creation of {@link java.util.Map.Entry} objects with each + * iteration. The {@link NonBlockingHashMap} does not normally create or + * using {@link java.util.Map.Entry} objects so they will be created soley + * to support this iteration. Iterating using {@link #keySet} or {@link + * #values} will be more efficient. + */ + @Override + public Set<Map.Entry<TypeK,TypeV>> entrySet() { + return new AbstractSet<Map.Entry<TypeK,TypeV>>() { + @Override public void clear ( ) { NonBlockingHashMap.this.clear( ); } + @Override public int size ( ) { return NonBlockingHashMap.this.size ( ); } + @Override public boolean remove( final Object o ) { + if( !(o instanceof Map.Entry)) return false; + final Map.Entry<?,?> e = (Map.Entry<?,?>)o; + return NonBlockingHashMap.this.remove(e.getKey(), e.getValue()); + } + @Override 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.equals(e.getValue()); + } + @Override public Iterator<Map.Entry<TypeK,TypeV>> iterator() { return new SnapshotE(); } + }; + } + + // --- writeObject ------------------------------------------------------- + // Write a NBHM to a stream + private void writeObject(java.io.ObjectOutputStream s) throws IOException { + s.defaultWriteObject(); // Nothing to write + for( Object K : keySet() ) { + final Object V = get(K); // Do an official 'get' + s.writeObject(K); // Write the <TypeK,TypeV> pair + s.writeObject(V); + } + s.writeObject(null); // Sentinel to indicate end-of-data + s.writeObject(null); + } + + // --- readObject -------------------------------------------------------- + // Read a CHM from a stream + @SuppressWarnings("unchecked") + private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { + s.defaultReadObject(); // Read nothing + initialize(MIN_SIZE); + for(;;) { + final TypeK K = (TypeK) s.readObject(); + final TypeV V = (TypeV) s.readObject(); + if( K == null ) break; + put(K,V); // Insert with an offical put + } + } + +} // End NonBlockingHashMap class diff --git a/src/main/java/com/seaofnodes/util/NonBlockingHashMapLong.java b/src/main/java/com/seaofnodes/util/NonBlockingHashMapLong.java new file mode 100644 index 00000000..6ab2b5ee --- /dev/null +++ b/src/main/java/com/seaofnodes/util/NonBlockingHashMapLong.java @@ -0,0 +1,1367 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ +package com.seaofnodes.util; + +import java.io.IOException; +import java.io.Serializable; +import java.util.*; +import java.util.concurrent.ConcurrentMap; +import java.util.concurrent.atomic.AtomicLongFieldUpdater; +import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; + +import static com.seaofnodes.util.UtilUnsafe.UNSAFE; +import static com.seaofnodes.util.UtilUnsafe.fieldOffset; + + +/** + * A lock-free alternate implementation of {@link java.util.concurrent.ConcurrentHashMap} + * with <strong>primitive long keys</strong>, better scaling properties and + * generally lower costs. The use of {@code 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. {@link + * NonBlockingHashMapLong} scales substatially better than {@link + * 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. + * + * <p><strong>The main benefit of this class</strong> over using plain {@link + * NonBlockingHashMap} with {@link Long} keys is + * that it avoids the auto-boxing and unboxing costs. Since auto-boxing is + * <em>automatic</em>, it is easy to accidentally cause auto-boxing and negate + * the space and speed benefits. + * + * <p>This class obeys the same functional specification as {@link + * java.util.Hashtable}, and includes versions of methods corresponding to + * each method of <tt>Hashtable</tt>. However, even though all operations are + * thread-safe, operations do <em>not</em> entail locking and there is + * <em>not</em> any support for locking the entire table in a way that + * prevents all access. This class is fully interoperable with + * <tt>Hashtable</tt> in programs that rely on its thread safety but not on + * its synchronization details. + * + * <p> Operations (including <tt>put</tt>) generally do not block, so may + * overlap with other update operations (including other <tt>puts</tt> and + * <tt>removes</tt>). Retrievals reflect the results of the most recently + * <em>completed</em> update operations holding upon their onset. For + * aggregate operations such as <tt>putAll</tt>, 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 + * <em>not</em> throw {@link ConcurrentModificationException}. However, + * iterators are designed to be used by only one thread at a time. + * + * <p> 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). + * + * <p>This class and its views and iterators implement all of the + * <em>optional</em> methods of the {@link Map} and {@link Iterator} + * interfaces. + * + * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class + * does <em>not</em> allow <tt>null</tt> to be used as a value. + * + * + * @since 1.5 + * @author Cliff Click + * @param <TypeV> the type of mapped values + */ + +public class NonBlockingHashMapLong<TypeV> + extends AbstractMap<Long,TypeV> + implements ConcurrentMap<Long,TypeV>, Cloneable, Serializable { + + private static final long serialVersionUID = 1234123412341234124L; + + private static final int REPROBE_LIMIT=10; // Too many reprobes then force a table-resize + + // --- Bits to allow Unsafe access to arrays + private static final int _Obase = UNSAFE.arrayBaseOffset(Object[].class); + private static final int _Oscale = UNSAFE.arrayIndexScale(Object[].class); + private static long rawIndex(final Object[] ary, final int idx) { + 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); + } + private static final int _Lbase = UNSAFE.arrayBaseOffset(long[].class); + private static final int _Lscale = UNSAFE.arrayIndexScale(long[].class); + private static long rawIndex(final long[] ary, final int idx) { + 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); + } + + // --- Bits to allow Unsafe CAS'ing of the CHM field + private static final long _chm_offset = fieldOffset(NonBlockingHashMapLong.class, "_chm"); + private static final long _val_1_offset = fieldOffset(NonBlockingHashMapLong.class, "_val_1"); + + private boolean CAS( final long offset, final Object old, final Object nnn ) { + return UNSAFE.compareAndSwapObject(this, offset, old, nnn ); + } + + // --- Adding a 'prime' bit onto Values via wrapping with a junk wrapper class + private static final class Prime { + final Object _V; + Prime( Object V ) { _V = V; } + static Object unbox( Object V ) { return V instanceof Prime ? ((Prime)V)._V : V; } + } + + // --- The Hash Table -------------------- + private transient CHM _chm; + // This next field holds the value for Key 0 - the special key value which + // is the initial array value, and also means: no-key-inserted-yet. + private transient Object _val_1; // Value for Key: NO_KEY + + // Time since last resize + private transient long _last_resize_milli; + + // Optimize for space: use a 1/2-sized table and allow more re-probes + private final boolean _opt_for_space; + + // --- Minimum table size ---------------- + // Pick size 16 K/V pairs, which turns into (16*2)*4+12 = 140 bytes on a + // standard 32-bit HotSpot, and (16*2)*8+12 = 268 bytes on 64-bit Azul. + private static final int MIN_SIZE_LOG=2; // + private static final int MIN_SIZE=(1<<MIN_SIZE_LOG); // Must be power of 2 + + // --- Sentinels ------------------------- + // No-Match-Old - putIfMatch does updates only if it matches the old value, + // and NO_MATCH_OLD basically counts as a wildcard match. + private static final Object NO_MATCH_OLD = new Object(); // Sentinel + // Match-Any-not-null - putIfMatch does updates only if it find a real old + // value. + private static final Object MATCH_ANY = new Object(); // Sentinel + // This K/V pair has been deleted (but the Key slot is forever claimed). + // The same Key can be reinserted with a new value later. + private static final Object TOMBSTONE = new Object(); + // Prime'd or box'd version of TOMBSTONE. This K/V pair was deleted, then a + // table resize started. The K/V pair has been marked so that no new + // updates can happen to the old table (and since the K/V pair was deleted + // nothing was copied to the new table). + private static final Prime TOMBPRIME = new Prime(TOMBSTONE); + + // I exclude 1 long from the 2^64 possibilities, and test for it before + // entering the main array. The NO_KEY value must be zero, the initial + // value set by Java before it hands me the array. + private static final long NO_KEY = 0L; + + // --- dump ---------------------------------------------------------------- + /** Verbose printout of table internals, useful for debugging. */ + public final void print() { + System.out.println("========="); + print_impl(-99,NO_KEY,_val_1); + _chm.print(); + System.out.println("========="); + } + private static void print_impl(final int i, final long K, final Object V) { + 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+")"); + } + + private void print2() { + System.out.println("========="); + print2_impl(-99,NO_KEY,_val_1); + _chm.print(); + System.out.println("========="); + } + private static void print2_impl(final int i, final long K, final Object V) { + if( V != null && Prime.unbox(V) != TOMBSTONE ) + print_impl(i,K,V); + } + + /** + * 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 <tt>entrySet</tt> view's iterator, enclosed in braces + * (<tt>"{}"</tt>). Adjacent mappings are separated by the characters + * <tt>", "</tt> (comma and space). Each key-value mapping is rendered as + * the key followed by an equals sign (<tt>"="</tt>) followed by the + * associated value. Keys and values are converted to strings as by + * {@link String#valueOf(Object)}. + * + * @return a string representation of this map + */ + @Override + public String toString() { + IteratorLong iter = new IteratorLong(); + if( !iter.hasNext() ) return "{}"; + SB sb = new SB("{"); + for( long key=iter.next(); iter.hasNext(); key=iter.next() ) { + TypeV val = get(key); + sb.p(key).p('=').p(val == this ? "(this Map)" : val.toString()).p(", "); + } + return sb.unchar(2).p("}").toString(); + } + + + // Count of reprobes + private transient AryInt _reprobes = null; + + /** 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. + * @return the count of reprobes since the last call to {@link #reprobes} + * or since the table was created. */ + public AryInt reprobes() { return _reprobes==null ? (_reprobes = new AryInt()) : _reprobes; } + private void record( int ps ) { if( _reprobes!=null ) _record(ps); } + private void _record( int ps ) { _reprobes.setX(ps,_reprobes.atX(ps)+1); } + + + // --- reprobe_limit ----------------------------------------------------- + // Heuristic to decide if we have reprobed toooo many times. Running over + // the reprobe limit on a 'get' call acts as a 'miss'; on a 'put' call it + // can trigger a table resize. Several places must have exact agreement on + // what the reprobe_limit is, so we share it here. + private static int reprobe_limit( int len ) { + return REPROBE_LIMIT + (len>>4); + } + + // --- NonBlockingHashMapLong ---------------------------------------------- + // Constructors + + /** 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). */ + public NonBlockingHashMapLong( ) { this(MIN_SIZE,true); } + + /** 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. */ + public NonBlockingHashMapLong( final int initial_sz ) { this(initial_sz,true); } + + /** Create a new NonBlockingHashMapLong, setting the space-for-speed + * tradeoff. {@code true} optimizes for space and is the default. {@code + * false} optimizes for speed and doubles space costs for roughly a 10% + * speed improvement. */ + public NonBlockingHashMapLong( final boolean opt_for_space ) { this(1,opt_for_space); } + + /** Create a new NonBlockingHashMapLong, setting both the initial size and + * the space-for-speed tradeoff. {@code true} optimizes for space and is + * the default. {@code false} optimizes for speed and doubles space costs + * for roughly a 10% speed improvement. */ + public NonBlockingHashMapLong( final int initial_sz, final boolean opt_for_space ) { + _opt_for_space = opt_for_space; + initialize(initial_sz); + } + private void initialize( final int initial_sz ) { + 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(); + } + + // --- wrappers ------------------------------------------------------------ + + /** Returns the number of key-value mappings in this map. + * @return the number of key-value mappings in this map */ + public int size ( ) { return (_val_1==TOMBSTONE?0:1) + _chm.size(); } + /** Tests if the key in the table. + * @return <tt>true</tt> if the key is in the table */ + public boolean containsKey( long key ) { return get(key) != null; } + + /** Legacy method testing if some key maps into the specified value in this + * table. This method is identical in functionality to {@link + * #containsValue}, and exists solely to ensure full compatibility with + * class {@link java.util.Hashtable}, which supported this method prior to + * introduction of the Java Collections framework. + * @param val a value to search for + * @return <tt>true</tt> if this map maps one or more keys to the specified value + * @throws NullPointerException if the specified value is null */ + public boolean contains ( Object val ) { return containsValue(val); } + + /** Maps the specified key to the specified value in the table. The value + * cannot be null. <p> The value can be retrieved by calling {@link #get} + * with a key that is equal to the original key. + * @param key key with which the specified value is to be associated + * @param val value to be associated with the specified key + * @return the previous value associated with <tt>key</tt>, or + * <tt>null</tt> if there was no mapping for <tt>key</tt> + * @throws NullPointerException if the specified value is null */ + public TypeV put ( long key, TypeV val ) { return putIfMatch( key, val,NO_MATCH_OLD);} + + /** Atomically, do a {@link #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. + * @return the previous value associated with the specified key, + * or <tt>null</tt> if there was no mapping for the key + * @throws NullPointerException if the specified is value is null */ + public TypeV putIfAbsent( long key, TypeV val ) { return putIfMatch( key, val,TOMBSTONE );} + + /** Removes the key (and its corresponding value) from this map. + * This method does nothing if the key is not in the map. + * @return the previous value associated with <tt>key</tt>, or + * <tt>null</tt> if there was no mapping for <tt>key</tt>*/ + public TypeV remove ( long key ) { return putIfMatch( key,TOMBSTONE,NO_MATCH_OLD);} + + /** Atomically do a {@link #remove(long)} if-and-only-if the key is mapped + * to a value which is <code>equals</code> to the given value. + * @throws NullPointerException if the specified value is null */ + public boolean remove ( long key,Object val ) { return putIfMatch( key,TOMBSTONE,val ) == val ;} + + /** Atomically do a <code>put(key,val)</code> if-and-only-if the key is + * mapped to some value already. + * @throws NullPointerException if the specified value is null */ + public TypeV replace ( long key, TypeV val ) { return putIfMatch( key, val,MATCH_ANY );} + + /** Atomically do a <code>put(key,newValue)</code> if-and-only-if the key is + * mapped a value which is <code>equals</code> to <code>oldValue</code>. + * @throws NullPointerException if the specified value is null */ + public boolean replace ( long key, TypeV oldValue, TypeV newValue ) { + return putIfMatch( key, newValue, oldValue ) == oldValue; + } + + @SuppressWarnings("unchecked") + private TypeV putIfMatch( long key, Object newVal, Object oldVal ) { + 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; + } + + /** Removes all the mappings from this map. */ + public void clear() { // 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); + } + // Non-atomic clear, preserving existing large arrays + public void clear(boolean large) { // Smack a new empty table down + _chm.clear(); + CAS(_val_1_offset,_val_1,TOMBSTONE); + } + + /** Returns <tt>true</tt> if this Map maps one or more keys to the specified + * value. <em>Note</em>: This method requires a full internal traversal of the + * hash table and is much slower than {@link #containsKey}. + * @param val value whose presence in this map is to be tested + * @return <tt>true</tt> if this Map maps one or more keys to the specified value + * @throws NullPointerException if the specified value is null */ + public boolean containsValue( Object val ) { + 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; + } + + // Get *any* valid Key. Useful for making worklists out of a hashtable - the + // hashtable can remove dup work. Repeated calls probably return the same + // Key, so only useful if keys are removed after calling. + public long getKey() { + if( _val_1 != TOMBSTONE ) throw new IllegalArgumentException("Cannot return key 0 and distinguish from no key"); + return _chm._getKey(); + } + + // --- get ----------------------------------------------------------------- + /** Returns the value to which the specified key is mapped, or {@code null} + * if this map contains no mapping for the key. + * <p>More formally, if this map contains a mapping from a key {@code k} to + * a value {@code v} such that {@code key==k}, then this method + * returns {@code v}; otherwise it returns {@code null}. (There can be at + * most one such mapping.) + * @throws NullPointerException if the specified key is null */ + // Never returns a Prime nor a Tombstone. + @SuppressWarnings("unchecked") + public final TypeV get( long key ) { + 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; + } + + /** Auto-boxing version of {@link #get(long)}. */ + public TypeV get ( Object key ) { return (key instanceof Long) ? get (((Long)key).longValue()) : null; } + /** Auto-boxing version of {@link #remove(long)}. */ + public TypeV remove ( Object key ) { return (key instanceof Long) ? remove (((Long)key).longValue()) : null; } + /** Auto-boxing version of {@link #remove(long,Object)}. */ + public boolean remove ( Object key, Object Val ) { return (key instanceof Long) && remove(((Long) key).longValue(), Val); } + /** Auto-boxing version of {@link #containsKey(long)}. */ + public boolean containsKey( Object key ) { return (key instanceof Long) && containsKey(((Long) key).longValue()); } + /** Auto-boxing version of {@link #putIfAbsent}. */ + public TypeV putIfAbsent( Long key, TypeV val ) { return putIfAbsent( key.longValue(), val ); } + /** Auto-boxing version of {@link #replace}. */ + public TypeV replace( Long key, TypeV Val ) { return replace(key.longValue(), Val); } + /** Auto-boxing version of {@link #put}. */ + public TypeV put ( Long key, TypeV val ) { return put(key.longValue(),val); } + /** Auto-boxing version of {@link #replace}. */ + public boolean replace( Long key, TypeV oldValue, TypeV newValue ) { + return replace(key.longValue(), oldValue, newValue); + } + + // --- help_copy ----------------------------------------------------------- + // Help along an existing resize operation. This is just a fast cut-out + // wrapper, to encourage inlining for the fast no-copy-in-progress case. We + // always help the top-most table copy, even if there are nested table + // copies in progress. + private void help_copy( ) { + // 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); + } + + // --- hash ---------------------------------------------------------------- + // Helper function to spread lousy hashCodes Throws NPE for null Key, on + // purpose - as the first place to conveniently toss the required NPE for a + // null Key. + private static int hash( long h) { + 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; + } + + + // --- CHM ----------------------------------------------------------------- + // The control structure for the NonBlockingHashMapLong + private static final class CHM implements Serializable { + // Back-pointer to top-level structure + final NonBlockingHashMapLong _nbhml; + + // Size in active K,V pairs + private ConcurrentAutoTable _size; + public int size () { return (int)_size.get(); } + + // --- + // These next 2 fields are used in the resizing heuristics, to judge when + // it is time to resize or copy the table. Slots is a count of used-up + // key slots, and when it nears a large fraction of the table we probably + // end up reprobing too much. Last-resize-milli is the time since the + // last resize; if we are running back-to-back resizes without growing + // (because there are only a few live keys but many slots full of dead + // keys) then we need a larger table to cut down on the churn. + + // Count of used slots, to tell when table is full of dead unusable slots + private ConcurrentAutoTable _slots; + public int slots() { return (int)_slots.get(); } + + // --- + // New mappings, used during resizing. + // The 'next' CHM - created during a resize operation. This represents + // the new table being copied from the old one. It's the volatile + // variable that is read as we cross from one table to the next, to get + // the required memory orderings. It monotonically transits from null to + // set (once). + volatile CHM _newchm; + private static final AtomicReferenceFieldUpdater<CHM,CHM> _newchmUpdater = + AtomicReferenceFieldUpdater.newUpdater(CHM.class,CHM.class, "_newchm"); + // Set the _newchm field if we can. AtomicUpdaters do not fail spuriously. + boolean CAS_newchm( CHM newchm ) { + return _newchmUpdater.compareAndSet(this,null,newchm); + } + // Sometimes many threads race to create a new very large table. Only 1 + // wins the race, but the losers all allocate a junk large table with + // hefty allocation costs. Attempt to control the overkill here by + // throttling attempts to create a new table. I cannot really block here + // (lest I lose the non-blocking property) but late-arriving threads can + // give the initial resizing thread a little time to allocate the initial + // new table. The Right Long Term Fix here is to use array-lets and + // incrementally create the new very large array. In C I'd make the array + // with malloc (which would mmap under the hood) which would only eat + // virtual-address and not real memory - and after Somebody wins then we + // could in parallel initialize the array. Java does not allow + // un-initialized array creation (especially of ref arrays!). + volatile long _resizers; // count of threads attempting an initial resize + private static final AtomicLongFieldUpdater<CHM> _resizerUpdater = + AtomicLongFieldUpdater.newUpdater(CHM.class, "_resizers"); + + // --- key,val ------------------------------------------------------------- + // Access K,V for a given idx + private boolean CAS_key( int idx, long old, long key ) { + return UNSAFE.compareAndSwapLong ( _keys, rawIndex(_keys, idx), old, key ); + } + private boolean CAS_val( int idx, Object old, Object val ) { + return UNSAFE.compareAndSwapObject( _vals, rawIndex(_vals, idx), old, val ); + } + + final long [] _keys; + final Object [] _vals; + + // Simple constructor + CHM( final NonBlockingHashMapLong nbhml, ConcurrentAutoTable size, final int logsize ) { + _nbhml = nbhml; + _size = size; + _slots= new ConcurrentAutoTable(); + _keys = new long [1<<logsize]; + _vals = new Object[1<<logsize]; + } + // Non-atomic clear + void clear() { + _size.clear(); + _slots.clear(); + Arrays.fill(_keys,0); + Arrays.fill(_vals,null); + } + + // --- print innards + private void print() { + for( int i=0; i<_keys.length; i++ ) { + long K = _keys[i]; + if( K != NO_KEY ) + print_impl(i,K,_vals[i]); + } + CHM newchm = _newchm; // New table, if any + if( newchm != null ) { + System.out.println("----"); + newchm.print(); + } + } + + // --- print only the live objects + private void print2( ) { + for( int i=0; i<_keys.length; i++ ) { + long K = _keys[i]; + if( K != NO_KEY ) // key is sane + print2_impl(i,K,_vals[i]); + } + CHM newchm = _newchm; // New table, if any + if( newchm != null ) { + System.out.println("----"); + newchm.print2(); + } + } + + // --- get_impl ---------------------------------------------------------- + // Never returns a Prime nor a Tombstone. + private Object get_impl ( final long key ) { + final int hash = hash(key); + final int len = _keys.length; + int idx = (hash & (len-1)); // First key hash + + // Main spin/reprobe loop, looking for a Key hit + int reprobe_cnt=0; + try { + while( true ) { + final long K = _keys[idx]; // Get key before volatile read, could be NO_KEY + final Object V = _vals[idx]; // Get value before volatile read, could be null or Tombstone or Prime + if( K == NO_KEY ) return null; // A clear miss + + // Key-compare + if( key == K ) { + // Key hit! Check for no table-copy-in-progress + if( !(V instanceof Prime) ) { // No copy? + if( V == TOMBSTONE) return null; + // We need a volatile-read between reading a newly inserted Value + // and returning the Value (so the user might end up reading the + // stale Value contents). + @SuppressWarnings("unused") final CHM newchm = _newchm; // VOLATILE READ before returning V + return V; + } + // Key hit - but slot is (possibly partially) copied to the new table. + // Finish the copy & retry in the new table. + return copy_slot_and_check(idx,key).get_impl(key); // Retry in the new table + } + // get and put must have the same key lookup logic! But only 'put' + // needs to force a table-resize for a too-long key-reprobe sequence. + // Check for too-many-reprobes on get. + if( ++reprobe_cnt >= reprobe_limit(len) ) // too many probes + return _newchm == null // Table copy in progress? + ? null // Nope! A clear miss + : copy_slot_and_check(idx,key).get_impl(key); // Retry in the new table + + idx = (idx+((hash>>16)|1))&(len-1); // Divergent reprobe chain + } + } finally { + _nbhml.record(reprobe_cnt); + } + } + + // --- putIfMatch --------------------------------------------------------- + // Put, Remove, PutIfAbsent, etc. Return the old value. If the returned + // value is equal to expVal (or expVal is NO_MATCH_OLD) then the put can + // be assumed to work (although might have been immediately overwritten). + // Only the path through copy_slot passes in an expected value of null, + // and putIfMatch only returns a null if passed in an expected null. + private static volatile int DUMMY_VOLATILE; + private Object putIfMatch( final long key, final Object putval, final Object expVal ) { + final int hash = hash(key); + assert putval != null; + assert !(putval instanceof Prime); + assert !(expVal instanceof Prime); + final int len = _keys.length; + int idx = (hash & (len-1)); // The first key + + // --- + // Key-Claim stanza: spin till we can claim a Key (or force a resizing). + int reprobe_cnt=0; + long K; + Object V; + try { + while( true ) { // Spin till we get a Key slot + V = _vals[idx]; // Get old value + K = _keys[idx]; // Get current key + if( K == NO_KEY ) { // Slot is free? + // Found an empty Key slot - which means this Key has never been in + // this table. No need to put a Tombstone - the Key is not here! + if( putval == TOMBSTONE ) return TOMBSTONE; // Not-now & never-been in this table + if( expVal == MATCH_ANY ) return TOMBSTONE; // Will not match, even after K inserts + // Claim the zero key-slot + if( CAS_key(idx, NO_KEY, key) ) { // Claim slot for Key + _slots.add(1); // Raise key-slots-used count + break; // Got it! + } + // CAS to claim the key-slot failed. + // + // This re-read of the Key points out an annoying short-coming of Java + // CAS. Most hardware CAS's report back the existing value - so that + // if you fail you have a *witness* - the value which caused the CAS + // to fail. The Java API turns this into a boolean destroying the + // witness. Re-reading does not recover the witness because another + // thread can write over the memory after the CAS. Hence we can be in + // the unfortunate situation of having a CAS fail *for cause* but + // having that cause removed by a later store. This turns a + // non-spurious-failure CAS (such as Azul has) into one that can + // apparently spuriously fail - and we avoid apparent spurious failure + // by not allowing Keys to ever change. + K = _keys[idx]; // CAS failed, get updated value + assert K != NO_KEY ; // If keys[idx] is NO_KEY, CAS shoulda worked + } + // Key slot was not null, there exists a Key here + if( K == key ) + break; // Got it! + + // get and put must have the same key lookup logic! Lest 'get' give + // up looking too soon. + //topmap._reprobes.add(1); + if( ++reprobe_cnt >= reprobe_limit(len) ) { + // We simply must have a new table to do a 'put'. At this point a + // 'get' will also go to the new table (if any). We do not need + // to claim a key slot (indeed, we cannot find a free one to claim!). + final CHM newchm = resize(); + if( expVal != null ) _nbhml.help_copy(); // help along an existing copy + return newchm.putIfMatch(key,putval,expVal); + } + + idx = (idx+((hash>>16)|1))&(len-1); // Divergent reprobe chain + } // End of spinning till we get a Key slot + } finally { + _nbhml.record(reprobe_cnt); + } + + while ( true ) { // Spin till we insert a value + // --- + // Found the proper Key slot, now update the matching Value slot. We + // never put a null, so Value slots monotonically move from null to + // not-null (deleted Values use Tombstone). Thus if 'V' is null we + // fail this fast cutout and fall into the check for table-full. + if( putval == V ) return V; // Fast cutout for no-change + + // See if we want to move to a new table (to avoid high average re-probe + // counts). We only check on the initial set of a Value from null to + // not-null (i.e., once per key-insert). + if( (V == null && tableFull(reprobe_cnt,len)) || + // Or we found a Prime: resize is already in progress. The resize + // call below will do a CAS on _newchm forcing the read. + V instanceof Prime) { + resize(); // Force the new table copy to start + return copy_slot_and_check(idx,expVal).putIfMatch(key,putval,expVal); + } + + // --- + // We are finally prepared to update the existing table + //assert !(V instanceof Prime); // always true, so IDE warnings if uncommented + + // Must match old, and we do not? Then bail out now. Note that either V + // or expVal might be TOMBSTONE. Also V can be null, if we've never + // inserted a value before. expVal can be null if we are called from + // copy_slot. + + if( expVal != NO_MATCH_OLD && // Do we care about expected-Value at all? + V != expVal && // No instant match already? + (expVal != MATCH_ANY || V == TOMBSTONE || V == null) && + !(V==null && expVal == TOMBSTONE) && // Match on null/TOMBSTONE combo + (expVal == null || !expVal.equals(V)) ) // Expensive equals check at the last + return (V==null) ? TOMBSTONE : V; // Do not update! + + // Actually change the Value in the Key,Value pair + if( CAS_val(idx, V, putval ) ) break; + + // CAS failed + // Because we have no witness, we do not know why it failed. + // Indeed, by the time we look again the value under test might have flipped + // a thousand times and now be the expected value (despite the CAS failing). + // Check for the never-succeed condition of a Prime value and jump to any + // nested table, or else just re-run. + + // We would not need this load at all if CAS returned the value on which + // the CAS failed (AKA witness). The new CAS semantics are supported via + // VarHandle in JDK9. + V = _vals[idx]; // Get new value + + // If a Prime'd value got installed, we need to re-run the put on the + // new table. Otherwise we lost the CAS to another racing put. + // Simply retry from the start. + if( V instanceof Prime ) + return copy_slot_and_check(idx,expVal).putIfMatch(key,putval,expVal); + + // Simply retry from the start. + // NOTE: need the fence, since otherwise '_vals[idx]' load could be hoisted + // out of loop. + int dummy = DUMMY_VOLATILE; + } + + // CAS succeeded - we did the update! + // Both normal put's and table-copy calls putIfMatch, but table-copy + // does not (effectively) increase the number of live k/v pairs. + if( expVal != null ) { + // Adjust sizes - a striped counter + if( (V == null || V == TOMBSTONE) && putval != TOMBSTONE ) _size.add( 1); + if( !(V == null || V == TOMBSTONE) && putval == TOMBSTONE ) _size.add(-1); + } + + // We won; we know the update happened as expected. + return (V==null && expVal!=null) ? TOMBSTONE : V; + } + + // --- tableFull --------------------------------------------------------- + // Heuristic to decide if this table is too full, and we should start a + // new table. Note that if a 'get' call has reprobed too many times and + // decided the table must be full, then always the estimate_sum must be + // high and we must report the table is full. If we do not, then we might + // end up deciding that the table is not full and inserting into the + // current table, while a 'get' has decided the same key cannot be in this + // table because of too many reprobes. The invariant is: + // slots.estimate_sum >= max_reprobe_cnt >= reprobe_limit(len) + private boolean tableFull( int reprobe_cnt, int len ) { + return + // Do the cheap check first: we allow some number of reprobes always + reprobe_cnt >= REPROBE_LIMIT && + (reprobe_cnt >= reprobe_limit(len) || + // More expensive check: see if the table is > 1/2 full. + _slots.estimate_get() >= (len>>1)); + } + + // --- resize ------------------------------------------------------------ + // Resizing after too many probes. "How Big???" heuristics are here. + // Callers will (not this routine) will 'help_copy' any in-progress copy. + // Since this routine has a fast cutout for copy-already-started, callers + // MUST 'help_copy' lest we have a path which forever runs through + // 'resize' only to discover a copy-in-progress which never progresses. + private CHM resize() { + // Check for resize already in progress, probably triggered by another thread + CHM newchm = _newchm; // VOLATILE READ + if( newchm != null ) // See if resize is already in progress + return newchm; // Use the new table already + + // No copy in-progress, so start one. First up: compute new table size. + int oldlen = _keys.length; // Old count of K,V pairs allowed + int sz = size(); // Get current table count of active K,V pairs + int newsz = sz; // First size estimate + + // Heuristic to determine new size. We expect plenty of dead-slots-with-keys + // and we need some decent padding to avoid endless reprobing. + if( _nbhml._opt_for_space ) { + // This heuristic leads to a much denser table with a higher reprobe rate + if( sz >= (oldlen>>1) ) // If we are >50% full of keys then... + newsz = oldlen<<1; // Double size + } else { + if( sz >= (oldlen>>2) ) { // If we are >25% full of keys then... + newsz = oldlen<<1; // Double size + if( sz >= (oldlen>>1) ) // If we are >50% full of keys then... + newsz = oldlen<<2; // Double double size + } + } + + // Last (re)size operation was very recent? Then double again + // despite having few live keys; slows down resize operations + // for tables subject to a high key churn rate - but do not + // forever grow the table. If there is a high key churn rate + // the table needs a steady state of rare same-size resize + // operations to clean out the dead keys. + long tm = System.currentTimeMillis(); + if( newsz <= oldlen && // New table would shrink or hold steady? + tm <= _nbhml._last_resize_milli+10000) // Recent resize (less than 10 sec ago) + newsz = oldlen<<1; // Double the existing size + + // Do not shrink, ever. If we hit this size once, assume we + // will again. + if( newsz < oldlen ) newsz = oldlen; + + // Convert to power-of-2 + int log2; + for( log2=MIN_SIZE_LOG; (1<<log2) < newsz; log2++ ) ; // Compute log2 of size + long len = ((1L << log2) << 1) + 2; + // prevent integer overflow - limit of 2^31 elements in a Java array + // so here, 2^30 + 2 is the largest number of elements in the hash table + if ((int)len!=len) { + log2 = 30; + len = (1L << log2) + 2; + if (sz > ((len >> 2) + (len >> 1))) throw new RuntimeException("Table is full."); + } + + // Now limit the number of threads actually allocating memory to a + // handful - lest we have 750 threads all trying to allocate a giant + // resized array. + long r = _resizers; + while( !_resizerUpdater.compareAndSet(this,r,r+1) ) + r = _resizers; + // Size calculation: 2 words (K+V) per table entry, plus a handful. We + // guess at 64-bit pointers; 32-bit pointers screws up the size calc by + // 2x but does not screw up the heuristic very much. + long megs = ((((1L<<log2)<<1)+8)<<3/*word to bytes*/)>>20/*megs*/; + if( r >= 2 && megs > 0 ) { // Already 2 guys trying; wait and see + newchm = _newchm; // Between dorking around, another thread did it + if( newchm != null ) // See if resize is already in progress + return newchm; // Use the new table already + // We could use a wait with timeout, so we'll wakeup as soon as the new table + // is ready, or after the timeout in any case. + //synchronized( this ) { wait(8*megs); } // Timeout - we always wakeup + // For now, sleep a tad and see if the 2 guys already trying to make + // the table actually get around to making it happen. + try { Thread.sleep(megs); } catch( Exception e ) { /*empty*/} + } + // Last check, since the 'new' below is expensive and there is a chance + // that another thread slipped in a new thread while we ran the heuristic. + newchm = _newchm; + if( newchm != null ) // See if resize is already in progress + return newchm; // Use the new table already + + // New CHM - actually allocate the big arrays + newchm = new CHM(_nbhml,_size,log2); + + // Another check after the slow allocation + if( _newchm != null ) // See if resize is already in progress + return _newchm; // Use the new table already + + // The new table must be CAS'd in so only 1 winner amongst duplicate + // racing resizing threads. Extra CHM's will be GC'd. + if( CAS_newchm( newchm ) ) { // NOW a resize-is-in-progress! + //notifyAll(); // Wake up any sleepers + //long nano = System.nanoTime(); + //System.out.println(" "+nano+" Resize from "+oldlen+" to "+(1<<log2)+" and had "+(_resizers-1)+" extras" ); + //System.out.print("["+log2); + } else // CAS failed? + newchm = _newchm; // Reread new table + return newchm; + } + + + // The next part of the table to copy. It monotonically transits from zero + // to _keys.length. Visitors to the table can claim 'work chunks' by + // CAS'ing this field up, then copying the indicated indices from the old + // table to the new table. Workers are not required to finish any chunk; + // the counter simply wraps and work is copied duplicately until somebody + // somewhere completes the count. + volatile long _copyIdx = 0; + static private final AtomicLongFieldUpdater<CHM> _copyIdxUpdater = + AtomicLongFieldUpdater.newUpdater(CHM.class, "_copyIdx"); + + // Work-done reporting. Used to efficiently signal when we can move to + // the new table. From 0 to len(oldkvs) refers to copying from the old + // table to the new. + volatile long _copyDone= 0; + static private final AtomicLongFieldUpdater<CHM> _copyDoneUpdater = + AtomicLongFieldUpdater.newUpdater(CHM.class, "_copyDone"); + + // --- help_copy_impl ---------------------------------------------------- + // Help along an existing resize operation. We hope its the top-level + // copy (it was when we started) but this CHM might have been promoted out + // of the top position. + private void help_copy_impl( final boolean copy_all ) { + final CHM newchm = _newchm; + assert newchm != null; // Already checked by caller + int oldlen = _keys.length; // Total amount to copy + final int MIN_COPY_WORK = Math.min(oldlen,1024); // Limit per-thread work + + // --- + int panic_start = -1; + int copyidx=-9999; // Fool javac to think it's initialized + while( _copyDone < oldlen ) { // Still needing to copy? + // Carve out a chunk of work. The counter wraps around so every + // thread eventually tries to copy every slot repeatedly. + + // We "panic" if we have tried TWICE to copy every slot - and it still + // has not happened. i.e., twice some thread somewhere claimed they + // would copy 'slot X' (by bumping _copyIdx) but they never claimed to + // have finished (by bumping _copyDone). Our choices become limited: + // we can wait for the work-claimers to finish (and become a blocking + // algorithm) or do the copy work ourselves. Tiny tables with huge + // thread counts trying to copy the table often 'panic'. + if( panic_start == -1 ) { // No panic? + copyidx = (int)_copyIdx; + while( copyidx < (oldlen<<1) && // 'panic' check + !_copyIdxUpdater.compareAndSet(this,copyidx,copyidx+MIN_COPY_WORK) ) + copyidx = (int)_copyIdx; // Re-read + if( !(copyidx < (oldlen<<1)) ) // Panic! + panic_start = copyidx; // Record where we started to panic-copy + } + + // We now know what to copy. Try to copy. + int workdone = 0; + for( int i=0; i<MIN_COPY_WORK; i++ ) + if( copy_slot((copyidx+i)&(oldlen-1)) ) // Made an oldtable slot go dead? + workdone++; // Yes! + if( workdone > 0 ) // Report work-done occasionally + copy_check_and_promote( workdone );// See if we can promote + //for( int i=0; i<MIN_COPY_WORK; i++ ) + // if( copy_slot((copyidx+i)&(oldlen-1)) ) // Made an oldtable slot go dead? + // copy_check_and_promote( 1 );// See if we can promote + + copyidx += MIN_COPY_WORK; + // Uncomment these next 2 lines to turn on incremental table-copy. + // Otherwise this thread continues to copy until it is all done. + if( !copy_all && panic_start == -1 ) // No panic? + return; // Then done copying after doing MIN_COPY_WORK + } + // Extra promotion check, in case another thread finished all copying + // then got stalled before promoting. + copy_check_and_promote( 0 ); // See if we can promote + } + + + // --- copy_slot_and_check ----------------------------------------------- + // Copy slot 'idx' from the old table to the new table. If this thread + // confirmed the copy, update the counters and check for promotion. + // + // Returns the result of reading the volatile _newchm, mostly as a + // convenience to callers. We come here with 1-shot copy requests + // typically because the caller has found a Prime, and has not yet read + // the _newchm volatile - which must have changed from null-to-not-null + // before any Prime appears. So the caller needs to read the _newchm + // field to retry his operation in the new table, but probably has not + // read it yet. + private CHM copy_slot_and_check( int idx, Object should_help ) { + // We're only here because the caller saw a Prime, which implies a + // table-copy is in progress. + assert _newchm != null; + if( copy_slot(idx) ) // Copy the desired slot + copy_check_and_promote(1); // Record the slot copied + // Generically help along any copy (except if called recursively from a helper) + if( should_help != null ) _nbhml.help_copy(); + return _newchm; + } + + // --- copy_check_and_promote -------------------------------------------- + private void copy_check_and_promote( int workdone ) { + int oldlen = _keys.length; + // We made a slot unusable and so did some of the needed copy work + long copyDone = _copyDone; + long nowDone = copyDone+workdone; + assert nowDone <= oldlen; + if( workdone > 0 ) { + while( !_copyDoneUpdater.compareAndSet(this,copyDone,nowDone) ) { + copyDone = _copyDone; // Reload, retry + nowDone = copyDone+workdone; + assert nowDone <= oldlen; + } + } + + // Check for copy being ALL done, and promote. Note that we might have + // nested in-progress copies and manage to finish a nested copy before + // finishing the top-level copy. We only promote top-level copies. + if( nowDone == oldlen && // Ready to promote this table? + _nbhml._chm == this && // Looking at the top-level table? + // Attempt to promote + _nbhml.CAS(_chm_offset,this,_newchm) ) { + _nbhml._last_resize_milli = System.currentTimeMillis(); // Record resize time for next check + } + } + + // --- copy_slot --------------------------------------------------------- + // Copy one K/V pair from oldkvs[i] to newkvs. Returns true if we can + // confirm that we set an old-table slot to TOMBPRIME, and only returns after + // updating the new table. We need an accurate confirmed-copy count so + // that we know when we can promote (if we promote the new table too soon, + // other threads may 'miss' on values not-yet-copied from the old table). + // We don't allow any direct updates on the new table, unless they first + // happened to the old table - so that any transition in the new table from + // null to not-null must have been from a copy_slot (or other old-table + // overwrite) and not from a thread directly writing in the new table. + private boolean copy_slot( int idx ) { + // Blindly set the key slot from NO_KEY to some key which hashes here, + // to eagerly stop fresh put's from inserting new values in the old + // table when the old table is mid-resize. We don't need to act on the + // results here, because our correctness stems from box'ing the Value + // field. Slamming the Key field is a minor speed optimization. + long key; + while( (key=_keys[idx]) == NO_KEY ) + CAS_key(idx, NO_KEY, (idx+_keys.length)/*a non-zero key which hashes here*/); + + // --- + // Prevent new values from appearing in the old table. + // Box what we see in the old table, to prevent further updates. + Object oldval = _vals[idx]; // Read OLD table + while( !(oldval instanceof Prime) ) { + final Prime box = (oldval == null || oldval == TOMBSTONE) ? TOMBPRIME : new Prime(oldval); + if( CAS_val(idx,oldval,box) ) { // CAS down a box'd version of oldval + // If we made the Value slot hold a TOMBPRIME, then we both + // prevented further updates here but also the (absent) oldval is + // vaccuously available in the new table. We return with true here: + // any thread looking for a value for this key can correctly go + // straight to the new table and skip looking in the old table. + if( box == TOMBPRIME ) + return true; + // Otherwise we boxed something, but it still needs to be + // copied into the new table. + oldval = box; // Record updated oldval + break; // Break loop; oldval is now boxed by us + } + oldval = _vals[idx]; // Else try, try again + } + if( oldval == TOMBPRIME ) return false; // Copy already complete here! + + // --- + // Copy the value into the new table, but only if we overwrite a null. + // If another value is already in the new table, then somebody else + // wrote something there and that write is happens-after any value that + // appears in the old table. + Object old_unboxed = ((Prime)oldval)._V; + assert old_unboxed != TOMBSTONE; + boolean copied_into_new = (_newchm.putIfMatch(key, old_unboxed, null) == null); + + // --- + // Finally, now that any old value is exposed in the new table, we can + // forever hide the old-table value by slapping a TOMBPRIME down. This + // will stop other threads from uselessly attempting to copy this slot + // (i.e., it's a speed optimization not a correctness issue). + while( oldval != TOMBPRIME && !CAS_val(idx,oldval,TOMBPRIME) ) + oldval = _vals[idx]; + + return copied_into_new; + } // end copy_slot + + // Get *any* random key, or 0 + private long _getKey() { + for( int i=0; i<_keys.length; i++ ) + if( _keys[i] != NO_KEY && Prime.unbox(_vals[i])!=TOMBSTONE ) + return _keys[i]; + return _newchm == null ? 0 : _newchm._getKey(); + } + + } // End of CHM + + + // --- Snapshot ------------------------------------------------------------ + // The main class for iterating over the NBHM. It "snapshots" a clean + // view of the K/V array. + private class SnapshotV implements Iterator<TypeV>, Enumeration<TypeV> { + final CHM _sschm; + public SnapshotV() { + CHM topchm; + while( true ) { // Verify no table-copy-in-progress + topchm = _chm; + if( topchm._newchm == null ) // No table-copy-in-progress + break; + // Table copy in-progress - so we cannot get a clean iteration. We + // must help finish the table copy before we can start iterating. + topchm.help_copy_impl(true); + } + // The "linearization point" for the iteration. Every key in this table + // will be visited, but keys added later might be skipped or even be + // added to a following table (also not iterated over). + _sschm = topchm; + // Warm-up the iterator + _idx = -1; + next(); + } + int length() { return _sschm._keys.length; } + long key(final int idx) { return _sschm._keys[idx]; } + private int _idx; // -2 for NO_KEY, -1 for CHECK_NEW_TABLE_LONG, 0-keys.length + private long _nextK, _prevK; // Last 2 keys found + private TypeV _nextV, _prevV; // Last 2 values found + public boolean hasNext() { return _nextV != null; } + public TypeV next() { + // 'next' actually knows what the next value will be - it had to + // figure that out last go 'round lest 'hasNext' report true and + // some other thread deleted the last value. Instead, 'next' + // spends all its effort finding the key that comes after the + // 'next' key. + if( _idx != -1 && _nextV == null ) throw new NoSuchElementException(); + _prevK = _nextK; // This will become the previous key + _prevV = _nextV; // This will become the previous value + _nextV = null; // We have no more next-key + // Attempt to set <_nextK,_nextV> to the next K,V pair. + // _nextV is the trigger: stop searching when it is != null + if( _idx == -1 ) { // Check for NO_KEY + _idx = 0; // Setup for next phase of search + _nextK = NO_KEY; + if( (_nextV=get(_nextK)) != null ) return _prevV; + } + while( _idx<length() ) { // Scan array + _nextK = key(_idx++); // Get a key that definitely is in the set (for the moment!) + if( _nextK != NO_KEY && // Found something? + (_nextV=get(_nextK)) != null ) + break; // Got it! _nextK is a valid Key + } // Else keep scanning + return _prevV; // Return current value. + } + + public void removeKey() { + if( _prevV == null ) throw new IllegalStateException(); + NonBlockingHashMapLong.this.putIfMatch( _prevK, TOMBSTONE, NO_MATCH_OLD); + _prevV = null; + } + + @Override + public void remove() { + // NOTE: it would seem logical that value removal will semantically mean + // removing the matching value for the mapping <k,v>, but the JDK always + // removes by key, even when the value has changed. + removeKey(); + } + + public TypeV nextElement() { return next(); } + public boolean hasMoreElements() { return hasNext(); } + } + + /** Returns an enumeration of the values in this table. + * @return an enumeration of the values in this table + * @see #values() */ + public Enumeration<TypeV> elements() { return new SnapshotV(); } + + // --- values -------------------------------------------------------------- + /** Returns a {@link 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 + * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, + * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. + * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. + * + * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator that + * will never throw {@link 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. */ + public Collection<TypeV> values() { + 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(); } + }; + } + + // --- keySet -------------------------------------------------------------- + /** A class which implements the {@link Iterator} and {@link Enumeration} + * interfaces, generified to the {@link Long} class and supporting a + * <strong>non-auto-boxing</strong> {@link #nextLong} function. */ + public class IteratorLong implements Iterator<Long>, Enumeration<Long> { + private final SnapshotV _ss; + /** A new IteratorLong */ + public IteratorLong() { _ss = new SnapshotV(); } + /** Remove last key returned by {@link #next} or {@link #nextLong}. */ + public void remove() { _ss.removeKey(); } + /** <strong>Auto-box</strong> and return the next key. */ + public Long next () { _ss.next(); return _ss._prevK; } + /** Return the next key as a primitive {@code long}. */ + public long nextLong() { _ss.next(); return _ss._prevK; } + /** True if there are more keys to iterate over. */ + public boolean hasNext() { return _ss.hasNext(); } + /** <strong>Auto-box</strong> and return the next key. */ + public Long nextElement() { return next(); } + /** True if there are more keys to iterate over. */ + public boolean hasMoreElements() { return hasNext(); } + } + /** Returns an enumeration of the <strong>auto-boxed</strong> keys in this table. + * <strong>Warning:</strong> this version will auto-box all returned keys. + * @return an enumeration of the auto-boxed keys in this table + * @see #keySet() */ + public Enumeration<Long> keys() { return new IteratorLong(); } + + /** Returns a {@link Set} view of the keys contained in this map; with care + * the keys may be iterated over <strong>without auto-boxing</strong>. 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 + * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>, + * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support + * the <tt>add</tt> or <tt>addAll</tt> operations. + * + * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator that + * will never throw {@link 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. */ + public Set<Long> keySet() { + 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(); } + }; + } + + /** Keys as a long array. Array may be zero-padded if keys are concurrently deleted. */ + @SuppressWarnings("unchecked") + public long[] keySetLong() { + 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; + } + + // --- entrySet ------------------------------------------------------------ + // Warning: Each call to 'next' in this iterator constructs a new Long and a + // new NBHMLEntry. + private class NBHMLEntry extends AbstractEntry<Long,TypeV> { + NBHMLEntry( final Long k, final TypeV v ) { super(k,v); } + public TypeV setValue(final TypeV val) { + if (val == null) throw new NullPointerException(); + _val = val; + return put(_key, val); + } + } + private class SnapshotE implements Iterator<Map.Entry<Long,TypeV>> { + final SnapshotV _ss; + public SnapshotE() { _ss = new SnapshotV(); } + public void remove() { + // NOTE: it would seem logical that entry removal will semantically mean + // removing the matching pair <k,v>, but the JDK always removes by key, + // even when the value has changed. + _ss.removeKey(); + } + public Map.Entry<Long,TypeV> next() { _ss.next(); return new NBHMLEntry(_ss._prevK,_ss._prevV); } + public boolean hasNext() { return _ss.hasNext(); } + } + + /** Returns a {@link 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 + * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>, + * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support + * the <tt>add</tt> or <tt>addAll</tt> operations. + * + * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator + * that will never throw {@link 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. + * + * <p><strong>Warning:</strong> the iterator associated with this Set + * requires the creation of {@link java.util.Map.Entry} objects with each + * iteration. The {@link NonBlockingHashMap} + * does not normally create or using {@link java.util.Map.Entry} objects so + * they will be created soley to support this iteration. Iterating using + * {@link Map#keySet} or {@link Map#values} will be more efficient. In addition, + * this version requires <strong>auto-boxing</strong> the keys. + */ + public Set<Map.Entry<Long,TypeV>> entrySet() { + 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(); } + }; + } + + // --- writeObject ------------------------------------------------------- + // Write a NBHML to a stream + private void writeObject(java.io.ObjectOutputStream s) throws IOException { + 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); + } + + // --- readObject -------------------------------------------------------- + // Read a CHM from a stream + @SuppressWarnings("unchecked") + private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { + 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 + } + } + + /** + * 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. + * + * @return a clone of the hashtable. + */ + @SuppressWarnings("unchecked") + @Override + public NonBlockingHashMapLong<TypeV> clone() { + 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(); + } + } + +} // End NonBlockingHashMapLong class diff --git a/src/main/java/com/seaofnodes/util/SB.java b/src/main/java/com/seaofnodes/util/SB.java new file mode 100644 index 00000000..4481ce71 --- /dev/null +++ b/src/main/java/com/seaofnodes/util/SB.java @@ -0,0 +1,80 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + + +/** Tight/tiny StringBuilder wrapper. + * Short short names on purpose; so they don't obscure the printing. + * Can't believe this wasn't done long, long ago. */ +public final class SB { + private final StringBuilder _sb; + private int _indent = 0; + public SB( ) { _sb = new StringBuilder( ); } + public SB(String s) { _sb = new StringBuilder(s); } + public SB p( String s ) { _sb.append(s); return this; } + //public SB p( Type t ) { _sb.append(t.toString()); return this; } + public SB p( float s ) { + if( Float.isNaN(s) ) + _sb.append( "Float.NaN"); + else if( Float.isInfinite(s) ) { + _sb.append(s > 0 ? "Float.POSITIVE_INFINITY" : "Float.NEGATIVE_INFINITY"); + } else _sb.append(s); + return this; + } + public SB p( double s ) { + if( Double.isNaN(s) ) + _sb.append("Double.NaN"); + else if( Double.isInfinite(s) ) { + _sb.append(s > 0 ? "Double.POSITIVE_INFINITY" : "Double.NEGATIVE_INFINITY"); + } else _sb.append(s); + return this; + } + public SB p( char s ) { _sb.append(s); return this; } + public SB p( int s ) { _sb.append(s); return this; } + public SB p( long s ) { _sb.append(s); return this; } + public SB p( boolean s) { _sb.append(s); return this; } + // Not spelled "p" on purpose: too easy to accidentally say "p(1.0)" and + // suddenly call the autoboxed version. + public SB pobj( Object s ) { _sb.append(s.toString()); return this; } + public SB i( int d ) { for( int i=0; i<d+_indent; i++ ) p(" "); return this; } + public SB i( ) { return i(0); } + public SB ip(String s) { return i().p(s); } + public SB s() { _sb.append(' '); return this; } + + // Increase indentation + public SB ii( int i) { _indent += i; return this; } + // Decrease indentation + public SB di( int i) { _indent -= i; return this; } + + public SB nl( ) { return p(System.lineSeparator()); } + + // Delete last char. Useful when doing string-joins and JSON printing and an + // extra seperater char needs to be removed: + // + // sb.p('['); + // for( Foo foo : foos ) + // sb.p(foo).p(','); + // sb.unchar().p(']'); // remove extra trailing comma + // + public SB unchar() { return unchar(1); } + public SB unchar(int x) { _sb.setLength(_sb.length()-x); return this; } + + public SB clear() { _sb.setLength(0); return this; } + public int len() { return _sb.length(); } + @Override public String toString() { return _sb.toString(); } +} diff --git a/src/main/java/com/seaofnodes/util/Util.java b/src/main/java/com/seaofnodes/util/Util.java new file mode 100644 index 00000000..416edf7e --- /dev/null +++ b/src/main/java/com/seaofnodes/util/Util.java @@ -0,0 +1,207 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import java.util.concurrent.ConcurrentMap; +import java.util.Arrays; + +public class Util { + // Fast linear scan for a hit, returns index or -1 + public static int find( int[] es, int e ) { + for( int i=0; i<es.length; i++ ) if( es[i]==e ) return i; + return -1; + } + // Fast linear scan for a hit, returns index or -1 + public static <E> int find( E[] es, E e ) { + for( int i=0; i<es.length; i++ ) if( es[i]==e ) return i; + return -1; + } + + // String-equals, with expected interned strings + public static boolean eq( String s0, String s1 ) { + if( s0==s1 ) return true; + if( s0==null || s1==null ) return false; + assert !s0.equals(s1) : "Not interned: "+s0; + return false; + } + + // Call per every get + private static int REPROBE_CHK_CNT; + public static void reprobe_quality_check_per(NonBlockingHashMap map, String msg) { + if( (REPROBE_CHK_CNT++ & ((1L<<16)-1)) == 0 ) // Reports every 2^16 == 65536 gets + reprobe_quality_check(map,msg); + } + public static void reprobe_quality_check(NonBlockingHashMap map, String msg) { + System.out.print("--- Reprobe histogram "+msg+": "); + AryInt ps = map.reprobes(); + long sum=0, ssum=0; + for( int i=0; i<ps._len; i++ ) { + System.out.print(""+i+":"+ps.at(i)+", "); + long l = ps.at(i); + sum += l; + ssum += l*(i+1); + } + System.out.println(); + System.out.println("--- Reprobe rate "+msg+": ("+ssum+"/"+sum+") = "+((double)ssum/sum)); + } + // Call per every put + public static void hash_quality_check_per(ConcurrentMap map, String msg) { + if( (map.size() & ((1L<<10)-1)) == 0 ) // Reports every 2^16 == 65536 puts + hash_quality_check(map,msg); + } + // Call for a report + public static void hash_quality_check(ConcurrentMap map, String msg) { + System.out.println("--- Hash quality check for "+msg+" ---"); + NonBlockingHashMapLong<Integer> hashs = new NonBlockingHashMapLong<>(); + for( Object k : map.keySet() ) { + int hash = k.hashCode(); + Integer ii = hashs.get(hash); + hashs.put(hash,ii==null ? 1 : ii+1); + } + int[] hist = new int[32]; + int maxval=0; + long maxkey=-1; + for( long l : hashs.keySetLong() ) { + int reps = hashs.get(l); + if( reps > maxval ) { maxval=reps; maxkey=l; } + if( reps < hist.length ) hist[reps]++; + else System.out.println("hash "+l+" repeats "+reps); + } + for( int i=0; i<hist.length; i++ ) + if( hist[i] > 0 ) + System.out.println("Number of hashes with "+i+" repeats: "+hist[i]); + System.out.println("Max repeat key "+maxkey+" repeats: "+maxval); + int cnt=0; + for( Object k : map.keySet() ) { + if( k.hashCode()==maxkey ) { + System.out.println("Sample: "+k); + if( cnt++>3 ) break; + } + } + } + + + // Copied from http://burtleburtle.net/bob/c/lookup3.c + // Call add_hash as many times as you like, then get_hash at the end. + // Uses global statics, does not nest. + public static long rot(long x, int k) { return (x<<k) | (x>>>(64-k)); } + private static long a,b,c; + private static int x; + static public void add_hash( long h ) { + switch( x ) { + case 0: a+=h; x++; return; + case 1: b+=h; x++; return; + case 2: c+=h; + a -= c; a ^= rot(c, 4); c += b; + b -= a; b ^= rot(a, 6); a += c; + c -= b; c ^= rot(b, 8); b += a; + a -= c; a ^= rot(c,16); c += b; + b -= a; b ^= rot(a,19); a += c; + c -= b; c ^= rot(b, 4); b += a; + x=0; + } + } + // Return the resulting hash, which is never 0 + static public long get_hash() { + if( x!=0 ) { + c ^= b; c -= rot(b,14); + a ^= c; a -= rot(c,11); + b ^= a; b -= rot(a,25); + c ^= b; c -= rot(b,16); + a ^= c; a -= rot(c, 4); + b ^= a; b -= rot(a,14); + c ^= b; c -= rot(b,24); + } + long hash=c; + if( hash==0 ) hash=b; + if( hash==0 ) hash=a; + if( hash==0 ) hash=0xcafebabe; + a=b=c=x=0; + return hash; + } + // Single-use hash spreader + static public long mix_hash(long h0) { + add_hash(h0); + return get_hash(); + } + static public long mix_hash( long h0, long h1 ) { + add_hash(h0); + add_hash(h1); + return get_hash(); + } + static public long mix_hash( long h0, long h1, long h2 ) { + add_hash(h0); + add_hash(h1); + add_hash(h2); + return get_hash(); + } + static public long mix_hash( long h0, long h1, long h2, long h3 ) { + add_hash(h0); + add_hash(h1); + add_hash(h2); + add_hash(h3); + return get_hash(); + } + static public long mix_hash( long h0, long h1, long h2, long h3, long h4 ) { + add_hash(h0); + add_hash(h1); + add_hash(h2); + add_hash(h3); + add_hash(h4); + return get_hash(); + } + + static public int gcd(int x, int y) { + if( x==0 || y== 0 ) return 0; + int a = Math.max(x,y), r; + int b = Math.min(x,y); + while((r=(a % b)) != 0) { a = b; b = r; } + return b; + } + + static public boolean isUpperCase( String s ) { + for( int i=0; i<s.length() ; i++ ) + if( !Character.isUpperCase(s.charAt(i)) ) + return false; + return true; + } + + // Return a merged sorted array from two sorted arrays, removing dups. + // If the merge is the same as either array, return that array. + // If the merge is the same as BOTH arrays, return the array with the smaller + // hashCode (goal: canonicalize identical arrays, so the fast == check works + // more often, and we do not make lots of equals-not-== arrays). + static public short[] merge_sort( short[] es0, short[] es1 ) { + if( es0==es1 ) return es0; + if( Arrays.equals(es0,es1) ) + throw new UnsupportedOperationException("Not implemented"); + short[] xs = new short[es0.length+es1.length]; + int i=0, j=0, k=0; + while( i<es0.length || j<es1.length ) { + short s0 = i<es0.length ? es0[i] : Short.MAX_VALUE, s1 = j<es1.length ? es1[j] : Short.MAX_VALUE, s2=s0; + if( s0<=s1 ) { i++; s2=s0; } + if( s1<=s0 ) { j++; s2=s1; } + xs[k++] = s2; + } + assert k>i && k>j; // Arrays were not equals, so at least one element from each copied to other + if( k < xs.length ) + throw new UnsupportedOperationException("Not implemented"); // Compact + return xs; + } + +} diff --git a/src/main/java/com/seaofnodes/util/UtilUnsafe.java b/src/main/java/com/seaofnodes/util/UtilUnsafe.java new file mode 100644 index 00000000..c98f0d21 --- /dev/null +++ b/src/main/java/com/seaofnodes/util/UtilUnsafe.java @@ -0,0 +1,55 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import java.lang.reflect.Field; + +import sun.misc.Unsafe; + +/** + * Simple class to obtain access to the {@link Unsafe} object. {@link Unsafe} + * is required to allow efficient CAS operations on arrays. Note that the + * versions in java.util.concurrent.atomic, such as {@link + * java.util.concurrent.atomic.AtomicLongArray}, require extra memory ordering + * guarantees which are generally not needed in these algorithms and are also + * expensive on most processors. + */ +public class UtilUnsafe { + private UtilUnsafe() { } // dummy private constructor + static final Unsafe UNSAFE = getUnsafe(); + /** Fetch the Unsafe. Use With Caution. */ + public static Unsafe getUnsafe() { + // Not on bootclasspath + if( UtilUnsafe.class.getClassLoader() == null ) + return Unsafe.getUnsafe(); + try { + final Field fld = Unsafe.class.getDeclaredField("theUnsafe"); + fld.setAccessible(true); + return (Unsafe) fld.get(UtilUnsafe.class); + } catch (Exception e) { + throw new RuntimeException("Could not obtain access to sun.misc.Unsafe", e); + } + } + + static final long fieldOffset( Class clz, String field ) { + Field f = null; + try { f = clz.getDeclaredField(field); } + catch( java.lang.NoSuchFieldException e ) { throw new RuntimeException(e); } + return UNSAFE.objectFieldOffset(f); + } +} diff --git a/src/main/java/com/seaofnodes/util/VBitSet.java b/src/main/java/com/seaofnodes/util/VBitSet.java new file mode 100644 index 00000000..5d00a9e4 --- /dev/null +++ b/src/main/java/com/seaofnodes/util/VBitSet.java @@ -0,0 +1,27 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import java.util.BitSet; + +public class VBitSet extends BitSet { + // Cannot override 'set' to return a value... :-P + public boolean tset(int idx) { boolean b = get(idx); set(idx); return b; } + public boolean test(int idx) { return get(idx); } + public VBitSet clr() { clear(); return this; } +} diff --git a/src/main/java/com/seaofnodes/util/Work.java b/src/main/java/com/seaofnodes/util/Work.java new file mode 100644 index 00000000..4f34ed21 --- /dev/null +++ b/src/main/java/com/seaofnodes/util/Work.java @@ -0,0 +1,79 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.util; + +import java.util.function.IntSupplier; + +// Simple worklist. Filters dups on a add. +// Constant-time remove until empty. +// Supports psuedo random pop. +@SuppressWarnings("unchecked") +public class Work<E extends IntSupplier> extends BitSetSparse { + private final Ary<E> _work = new Ary(new Object[1],0); + private int _rseed; // Psuedo-random draw + private int _idx; // Next item to get + public Work() { this(123); } // Default seed + public Work(int rseed) { _rseed = rseed; } + public int len() { return _work._len; } + public boolean isEmpty() { return _work.isEmpty(); } + public E add(E e) { // Add, filtering dups + if( e!=null && !tset(e.getAsInt()) ) + _work.push(e); + return e; + } + public void setSeed(int rseed ) { + assert _work.isEmpty(); + _rseed = rseed; + _idx = 0; + } + @Override public Work clear() { + super.clear(); + _work.clear(); + return this; + } + // Bulk adders + public void add(E[] es) { if(es!=null) for( E e : es ) add(e); } + public void addAll(Ary<? extends E> es) { if( es!=null ) for( E e : es ) add(e); } + public void addAll(Work<E> work) { for( Object o : work._work ) add((E)o); } + public boolean on(E e) { return test(e.getAsInt()); } + // Pull a psuedo-random element. Order depends on rseed. + public E pop() { + if( _work._len==0 ) return null; + _idx = (_idx+_rseed)&((1<<30)-1); + E e = _work.del( _idx % _work._len ); + clr(e.getAsInt()); + return e; + } + public E pop_last() { + if( _work._len==0 ) return null; + E e = _work.pop(); + clr(e.getAsInt()); + return e; + } + // Get/delete "idx"th elements; error if OOB. + public E at(int idx) { return _work.at(idx); } + public void del(int idx) { clr((_work.del(idx)).getAsInt()); } + public String print_work() { return _work.toString(); } + @Override public String toString() { + if( _set.size()==0 ) return "[]"; + SB sb = new SB().p('['); + for( E e : _work ) + sb.p(e.getAsInt()).p(','); + return sb.unchar().p(']').toString(); + } +} |