From 293506c1bd594f3d7a6a71bcd9aa8f140fbd13ab Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 20 Aug 2023 00:38:58 +0100 Subject: In this initial commit, following are included: util classes from AA Lexer code extracted from the Parse class. This is all draft as likely to change as we start creating the AST parser. --- .gitignore | 174 +++ pom.xml | 39 + .../java/com/seaofnodes/simple/lexer/Lexer.java | 228 +++ .../java/com/seaofnodes/util/AbstractEntry.java | 63 + src/main/java/com/seaofnodes/util/Ary.java | 367 +++++ src/main/java/com/seaofnodes/util/AryInt.java | 203 +++ .../java/com/seaofnodes/util/BitSetSparse.java | 39 + .../com/seaofnodes/util/ConcurrentAutoTable.java | 229 ++++ src/main/java/com/seaofnodes/util/IBitSet.java | 164 +++ src/main/java/com/seaofnodes/util/IHashMap.java | 32 + .../com/seaofnodes/util/NonBlockingHashMap.java | 1446 ++++++++++++++++++++ .../seaofnodes/util/NonBlockingHashMapLong.java | 1367 ++++++++++++++++++ src/main/java/com/seaofnodes/util/SB.java | 80 ++ src/main/java/com/seaofnodes/util/Util.java | 207 +++ src/main/java/com/seaofnodes/util/UtilUnsafe.java | 55 + src/main/java/com/seaofnodes/util/VBitSet.java | 27 + src/main/java/com/seaofnodes/util/Work.java | 79 ++ .../com/seaofnodes/simple/lexer/TestLexer.java | 33 + 18 files changed, 4832 insertions(+) create mode 100644 pom.xml create mode 100644 src/main/java/com/seaofnodes/simple/lexer/Lexer.java create mode 100644 src/main/java/com/seaofnodes/util/AbstractEntry.java create mode 100644 src/main/java/com/seaofnodes/util/Ary.java create mode 100644 src/main/java/com/seaofnodes/util/AryInt.java create mode 100644 src/main/java/com/seaofnodes/util/BitSetSparse.java create mode 100644 src/main/java/com/seaofnodes/util/ConcurrentAutoTable.java create mode 100644 src/main/java/com/seaofnodes/util/IBitSet.java create mode 100644 src/main/java/com/seaofnodes/util/IHashMap.java create mode 100644 src/main/java/com/seaofnodes/util/NonBlockingHashMap.java create mode 100644 src/main/java/com/seaofnodes/util/NonBlockingHashMapLong.java create mode 100644 src/main/java/com/seaofnodes/util/SB.java create mode 100644 src/main/java/com/seaofnodes/util/Util.java create mode 100644 src/main/java/com/seaofnodes/util/UtilUnsafe.java create mode 100644 src/main/java/com/seaofnodes/util/VBitSet.java create mode 100644 src/main/java/com/seaofnodes/util/Work.java create mode 100644 src/test/java/com/seaofnodes/simple/lexer/TestLexer.java diff --git a/.gitignore b/.gitignore index 524f0963..a4332950 100644 --- a/.gitignore +++ b/.gitignore @@ -1,3 +1,4 @@ +# Java stuff # Compiled class file *.class @@ -22,3 +23,176 @@ # virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml hs_err_pid* replay_pid* + +# Gradle stuff +.gradle +**/build/ +!src/**/build/ + +# Ignore Gradle GUI config +gradle-app.setting + +# Avoid ignoring Gradle wrapper jar file (.jar files are usually ignored) +!gradle-wrapper.jar + +# Avoid ignore Gradle wrappper properties +!gradle-wrapper.properties + +# Cache of project +.gradletasknamecache + + +# Covers JetBrains IDEs: IntelliJ, RubyMine, PhpStorm, AppCode, PyCharm, CLion, Android Studio, WebStorm and Rider +# Reference: https://intellij-support.jetbrains.com/hc/en-us/articles/206544839 + +# User-specific stuff +.idea/**/workspace.xml +.idea/**/tasks.xml +.idea/**/usage.statistics.xml +.idea/**/dictionaries +.idea/**/shelf + +# AWS User-specific +.idea/**/aws.xml + +# Generated files +.idea/**/contentModel.xml + +# Sensitive or high-churn files +.idea/**/dataSources/ +.idea/**/dataSources.ids +.idea/**/dataSources.local.xml +.idea/**/sqlDataSources.xml +.idea/**/dynamic.xml +.idea/**/uiDesigner.xml +.idea/**/dbnavigator.xml + +# Gradle +.idea/**/gradle.xml +.idea/**/libraries + +# Gradle and Maven with auto-import +# When using Gradle or Maven with auto-import, you should exclude module files, +# since they will be recreated, and may cause churn. Uncomment if using +# auto-import. +# .idea/artifacts +# .idea/compiler.xml +# .idea/jarRepositories.xml +# .idea/modules.xml +# .idea/*.iml +# .idea/modules +# *.iml +# *.ipr + +# CMake +cmake-build-*/ + +# Mongo Explorer plugin +.idea/**/mongoSettings.xml + +# File-based project format +*.iws + +# IntelliJ +out/ + +# mpeltonen/sbt-idea plugin +.idea_modules/ + +# JIRA plugin +atlassian-ide-plugin.xml + +# Cursive Clojure plugin +.idea/replstate.xml + +# SonarLint plugin +.idea/sonarlint/ + +# Crashlytics plugin (for Android Studio and IntelliJ) +com_crashlytics_export_strings.xml +crashlytics.properties +crashlytics-build.properties +fabric.properties + +# Editor-based Rest Client +.idea/httpRequests + +# Android studio 3.1+ serialized cache file +.idea/caches/build_file_checksums.ser + + +target/ +pom.xml.tag +pom.xml.releaseBackup +pom.xml.versionsBackup +pom.xml.next +release.properties +dependency-reduced-pom.xml +buildNumber.properties +.mvn/timing.properties +# https://github.com/takari/maven-wrapper#usage-without-binary-jar +.mvn/wrapper/maven-wrapper.jar + +# Eclipse stuff +.metadata +bin/ +tmp/ +*.tmp +*.bak +*.swp +*~.nib +local.properties +.settings/ +.loadpath +.recommenders + +# External tool builders +.externalToolBuilders/ + +# Locally stored "Eclipse launch configurations" +*.launch + +# PyDev specific (Python IDE for Eclipse) +*.pydevproject + +# CDT-specific (C/C++ Development Tooling) +.cproject + +# CDT- autotools +.autotools + +# Java annotation processor (APT) +.factorypath + +# PDT-specific (PHP Development Tools) +.buildpath + +# sbteclipse plugin +.target + +# Tern plugin +.tern-project + +# TeXlipse plugin +.texlipse + +# STS (Spring Tool Suite) +.springBeans + +# Code Recommenders +.recommenders/ + +# Annotation Processing +.apt_generated/ +.apt_generated_test/ + +# Scala IDE specific (Scala & Java development for Eclipse) +.cache-main +.scala_dependencies +.worksheet + +# Eclipse Gradle plugin generated files +# Eclipse Core +.project +# JDT-specific (Eclipse Java Development Tools) +.classpath \ No newline at end of file diff --git a/pom.xml b/pom.xml new file mode 100644 index 00000000..177c3508 --- /dev/null +++ b/pom.xml @@ -0,0 +1,39 @@ + + + 4.0.0 + + com.seaofnodes + simple + 1.0-SNAPSHOT + jar + Simple Programming Language + Simple language implementation to demonstrate Sea of Nodes IR + https://github.com/SeaOfNodes/Simple + + + 17 + 17 + UTF-8 + + + + + org.junit.jupiter + junit-jupiter-engine + 5.9.1 + test + + + + + + + org.apache.maven.plugins + maven-surefire-plugin + 3.1.2 + + + + \ No newline at end of file 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= _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^[]~/&|".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 the type of keys maintained by this map + * @param the type of mapped values + */ + +abstract class AbstractEntry implements Map.Entry { + /** 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 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 "key.hashCode() ^ val.hashCode()" */ + 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 implements Iterable { + 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 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 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 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 addAll( Collection c ) { if( c!=null ) for( E e : c ) add(e); return this; } + + /** @param es Array to be added */ + public Ary 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 addAll( Ary 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 map_update( Function 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 filter_update( Predicate 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 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 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 > Ary merge_or( Ary a0, Ary a1 ) { + int i=0, j=0; + Ary res = new Ary<>(Arrays.copyOf(a0._es,a0._len+a1._len),0); + + while( i0 ) { res.add(y); j++; } + else { res.add(x); i++; j++; } + } + while( i Ary merge_or( Ary a0, Ary a1, Comparator cmpr, Predicate filter) { + int i=0, j=0; + Ary res = new Ary<>(Arrays.copyOf(a0._es,a0._len+a1._len),0); + + while( i0 ) { res.add(y); j++; } + else { res.add(x); i++; j++; } + } + while( i> Ary merge_and( Ary a0, Ary a1 ) { + int i=0, j=0; + Ary res = new Ary<>(Arrays.copyOf(a0._es,Math.min(a0._len,a1._len)),0); + while( i0 ) { j++; } + else { res.add(x); i++; j++; } + } + return res; + } + + /** @return an iterator */ + @Override public Iterator iterator() { return new Iter(); } + private class Iter implements Iterator { + 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 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 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 _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 _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 _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 { + 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 ) { 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 iterator() { return new Iter(); } + private class Iter implements Iterator { + 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 put(T kv) { _map.put(kv,kv); return kv; } + public T put(T k, T v) { _map.put(k,v); return v; } + public 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 Set 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 Hashtable. However, even though all operations are + * thread-safe, operations do not entail locking and there is + * not any support for locking the entire table in a way that + * prevents all access. This class is fully interoperable with + * Hashtable in programs that rely on its thread safety but not on + * its synchronization details. + * + *

Operations (including put) generally do not block, so may + * overlap with other update operations (including other puts and + * removes). Retrievals reflect the results of the most recently + * completed update operations holding upon their onset. For + * aggregate operations such as putAll, concurrent retrievals may + * reflect insertion or removal of only some entries. Similarly, Iterators + * and Enumerations return elements reflecting the state of the hash table at + * some point at or since the creation of the iterator/enumeration. They do + * not throw {@link ConcurrentModificationException}. However, + * iterators are designed to be used by only one thread at a time. + * + *

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

This class and its views and iterators implement all of the + * optional methods of the {@link Map} and {@link Iterator} + * interfaces. + * + *

Like {@link Hashtable} but unlike {@link HashMap}, this class + * does not allow null to be used as a key or value. + * + * + * @since 1.5 + * @author Cliff Click + * @param the type of keys maintained by this map + * @param the type of mapped values + */ + +public class NonBlockingHashMap + extends AbstractMap + implements ConcurrentMap, 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 { // + 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<>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<size() == 0. + * @return size() == 0 */ + @Override + public boolean isEmpty ( ) { return size() == 0; } + + /** Tests if the key in the table using the equals method. + * @return true if the key is in the table using the equals 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 true 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. + *

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 key, or + * null if there was no mapping for key + * @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 null 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 key, or + * null if there was no mapping for key + * @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 equals 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 put(key,val) 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 put(key,newValue) if-and-only-if the key is + * mapped a value which is equals to oldValue. + * @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 m) { + for (Map.Entry 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 true if this Map maps one or more keys to the specified + * value. Note: This method requires a full internal traversal of the + * hash table and is much slower than {@link #containsKey}. + * @param val value whose presence in this map is to be tested + * @return true 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 t = (NonBlockingHashMap) 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 entrySet view's iterator, enclosed in braces + * ("{}"). Adjacent mappings are separated by the characters + * ", " (comma and space). Each key-value mapping is rendered as + * the key followed by an equals sign ("=") followed by the + * associated value. Keys and values are converted to strings as by + * {@link String#valueOf(Object)}. + * + * @return a string representation of this map + */ + @Override + public String toString() { + Iterator> i = entrySet().iterator(); + if( !i.hasNext()) + return "{}"; + + StringBuilder sb = new StringBuilder(); + sb.append('{'); + for (;;) { + Entry 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; iMore 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 { + // 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 _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 _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< ((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<>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< _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 _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 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, Enumeration { + 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 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 + * Iterator.remove, Collection.remove, + * removeAll, retainAll, and clear operations. + * It does not support the add or addAll operations. + * + *

The view's iterator is a "weakly consistent" iterator that + * will never throw {@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 values() { + return new AbstractCollection() { + @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 iterator() { return new SnapshotV(); } + }; + } + + // --- keySet -------------------------------------------------------------- + @SuppressWarnings("unchecked") + private class SnapshotK implements Iterator, Enumeration { + 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 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 Iterator.remove, + * Set.remove, removeAll, retainAll, and + * clear operations. It does not support the add or + * addAll operations. + * + *

The view's iterator is a "weakly consistent" iterator that + * will never throw {@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 keySet() { + return new AbstractSet () { + @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 iterator() { return new SnapshotK(); } + }; + } + + + // --- entrySet ------------------------------------------------------------ + // Warning: Each call to 'next' in this iterator constructs a new NBHMEntry. + private class NBHMEntry extends AbstractEntry { + 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> { + final SnapshotV _ss; + public SnapshotE() { _ss = new SnapshotV(); } + public void remove() { _ss.remove(); } + public Map.Entry 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 + * Iterator.remove, Set.remove, removeAll, + * retainAll, and clear operations. It does not support + * the add or addAll operations. + * + *

The view's iterator is a "weakly consistent" iterator + * that will never throw {@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. + * + *

Warning: 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> entrySet() { + return new AbstractSet>() { + @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> 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 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 primitive long keys, 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. + * + *

The main benefit of this class over using plain {@link + * NonBlockingHashMap} with {@link Long} keys is + * that it avoids the auto-boxing and unboxing costs. Since auto-boxing is + * automatic, it is easy to accidentally cause auto-boxing and negate + * the space and speed benefits. + * + *

This class obeys the same functional specification as {@link + * java.util.Hashtable}, and includes versions of methods corresponding to + * each method of Hashtable. However, even though all operations are + * thread-safe, operations do not entail locking and there is + * not any support for locking the entire table in a way that + * prevents all access. This class is fully interoperable with + * Hashtable in programs that rely on its thread safety but not on + * its synchronization details. + * + *

Operations (including put) generally do not block, so may + * overlap with other update operations (including other puts and + * removes). Retrievals reflect the results of the most recently + * completed update operations holding upon their onset. For + * aggregate operations such as putAll, concurrent retrievals may + * reflect insertion or removal of only some entries. Similarly, Iterators + * and Enumerations return elements reflecting the state of the hash table at + * some point at or since the creation of the iterator/enumeration. They do + * not throw {@link ConcurrentModificationException}. However, + * iterators are designed to be used by only one thread at a time. + * + *

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

This class and its views and iterators implement all of the + * optional methods of the {@link Map} and {@link Iterator} + * interfaces. + * + *

Like {@link Hashtable} but unlike {@link HashMap}, this class + * does not allow null to be used as a value. + * + * + * @since 1.5 + * @author Cliff Click + * @param the type of mapped values + */ + +public class NonBlockingHashMapLong + extends AbstractMap + implements ConcurrentMap, 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<entrySet view's iterator, enclosed in braces + * ("{}"). Adjacent mappings are separated by the characters + * ", " (comma and space). Each key-value mapping is rendered as + * the key followed by an equals sign ("=") followed by the + * associated value. Keys and values are converted to strings as by + * {@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<true 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 true 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.

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 key, or + * null if there was no mapping for key + * @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 null 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 key, or + * null if there was no mapping for key*/ + 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 equals 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 put(key,val) 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 put(key,newValue) if-and-only-if the key is + * mapped a value which is equals to oldValue. + * @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 true if this Map maps one or more keys to the specified + * value. Note: This method requires a full internal traversal of the + * hash table and is much slower than {@link #containsKey}. + * @param val value whose presence in this map is to be tested + * @return true 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. + *

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 _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 _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<= 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< ((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<>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< _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 _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 0 ) // Report work-done occasionally + copy_check_and_promote( workdone );// See if we can promote + //for( int i=0; i 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, Enumeration { + 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, 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 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 + * Iterator.remove, Collection.remove, + * removeAll, retainAll, and clear operations. + * It does not support the add or addAll operations. + * + *

The view's iterator is a "weakly consistent" iterator that + * will never throw {@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 values() { + return new AbstractCollection() { + 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 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 + * non-auto-boxing {@link #nextLong} function. */ + public class IteratorLong implements Iterator, Enumeration { + 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(); } + /** Auto-box 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(); } + /** Auto-box 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 auto-boxed keys in this table. + * Warning: this version will auto-box all returned keys. + * @return an enumeration of the auto-boxed keys in this table + * @see #keySet() */ + public Enumeration keys() { return new IteratorLong(); } + + /** Returns a {@link Set} view of the keys contained in this map; with care + * the keys may be iterated over without auto-boxing. The + * set is backed by the map, so changes to the map are reflected in the + * set, and vice-versa. The set supports element removal, which removes + * the corresponding mapping from this map, via the + * Iterator.remove, Set.remove, removeAll, + * retainAll, and clear operations. It does not support + * the add or addAll operations. + * + *

The view's iterator is a "weakly consistent" iterator that + * will never throw {@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 keySet() { + return new AbstractSet () { + 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 { + 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> { + 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 , but the JDK always removes by key, + // even when the value has changed. + _ss.removeKey(); + } + public Map.Entry 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 + * Iterator.remove, Set.remove, removeAll, + * retainAll, and clear operations. It does not support + * the add or addAll operations. + * + *

The view's iterator is a "weakly consistent" iterator + * that will never throw {@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. + * + *

Warning: 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 auto-boxing the keys. + */ + public Set> entrySet() { + return new AbstractSet>() { + 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> 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 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 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 t = (NonBlockingHashMapLong) 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 int find( E[] es, E e ) { + for( int i=0; i 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 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<>>(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; ii && 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 extends BitSetSparse { + private final Ary _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 es) { if( es!=null ) for( E e : es ) add(e); } + public void addAll(Work 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(); + } +} diff --git a/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java b/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java new file mode 100644 index 00000000..335bcf5e --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java @@ -0,0 +1,33 @@ +/** + * 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 org.junit.jupiter.api.Assertions; +import org.junit.jupiter.api.Test; + +public class TestLexer { + + @Test + public void testLexLineComment() + { + final String source = "//a comment\nx"; + Lexer lexer = new Lexer("test", source); + String token = lexer.token(); + Assertions.assertEquals("x", token); + } +} -- cgit v1.2.3