1 package com.cliffc.aa.util;
3 import sun.misc.Unsafe;
5 import java.io.IOException;
6 import java.io.Serializable;
7 import java.lang.reflect.Field;
9 import java.util.concurrent.ConcurrentMap;
10 import java.util.concurrent.atomic.AtomicLongFieldUpdater;
11 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
75 implements ConcurrentMap<TypeK, TypeV>,
Cloneable, Serializable {
83 private static final int _Obase =
_unsafe.arrayBaseOffset(Object[].
class);
86 private static long rawIndex(
final Object[] ary,
final int idx) {
87 assert idx >= 0 && idx < ary.length;
98 catch( java.lang.NoSuchFieldException e ) {
throw new RuntimeException(e); }
101 private boolean CAS_kvs(
final Object[] oldkvs,
final Object[] newkvs ) {
115 int h =
key.hashCode();
116 h ^= (h>>>20) ^ (h>>>12);
117 h ^= (h>>> 7) ^ (h>>> 4);
134 private transient Object[]
_kvs;
135 private static final CHM
chm (Object[] kvs) {
return (CHM )kvs[0]; }
136 private static final int[]
hashes(Object[] kvs) {
return (
int[])kvs[1]; }
138 private static final int len(Object[] kvs) {
return (kvs.length-2)>>1; }
172 private static final Object
key(Object[] kvs,
int idx) {
return kvs[(idx<<1)+2]; }
173 private static final Object
val(Object[] kvs,
int idx) {
return kvs[(idx<<1)+3]; }
174 private static final boolean CAS_key( Object[] kvs,
int idx, Object old, Object
key ) {
177 private static final boolean CAS_val( Object[] kvs,
int idx, Object old, Object
val ) {
185 System.out.println(
"=========");
187 System.out.println(
"=========");
190 private final void print( Object[] kvs ) {
191 for(
int i=0; i<
len(kvs); i++ ) {
192 Object K =
key(kvs,i);
194 String KS = (K ==
TOMBSTONE) ?
"XXX" : K.toString();
195 Object V =
val(kvs,i);
196 Object U = Prime.unbox(V);
197 String p = (V==U) ?
"" :
"prime_";
198 String US = (U ==
TOMBSTONE) ?
"tombstone" : U.toString();
199 System.out.println(
""+i+
" ("+KS+
","+p+US+
")");
203 if( newkvs !=
null ) {
204 System.out.println(
"----");
209 private final void print2( Object[] kvs) {
210 for(
int i=0; i<
len(kvs); i++ ) {
213 Object U = Prime.unbox(
val);
216 String p = (
val==U) ?
"" :
"prime_";
217 System.out.println(
""+i+
" ("+
key+
","+p+
val+
")");
221 if( newkvs !=
null ) {
222 System.out.println(
"----");
260 if( initial_sz < 0 )
throw new IllegalArgumentException();
262 if( initial_sz > 1024*1024 ) initial_sz = 1024*1024;
265 _kvs =
new Object[((1<<i)<<1)+2];
267 _kvs[1] =
new int[1<<i];
341 public boolean replace ( TypeK
key, TypeV oldValue, TypeV newValue ) {
350 @SuppressWarnings(
"unchecked")
355 assert !(res instanceof Prime);
360 @SuppressWarnings(
"unchecked")
361 private final TypeV
putIfMatch( Object
key, Object newVal, Object oldVal ) {
362 if (oldVal ==
null || newVal ==
null)
throw new NullPointerException();
364 assert !(res instanceof Prime);
366 return res ==
TOMBSTONE ? null : (TypeV)res;
374 public void putAll(Map<? extends TypeK, ? extends TypeV> m) {
375 for (Map.Entry<? extends TypeK, ? extends TypeV> e : m.entrySet())
376 put(e.getKey(), e.getValue());
395 if(
val ==
null )
throw new NullPointerException();
397 if( V ==
val || V.equals(
val) )
415 @SuppressWarnings(
"unchecked")
429 for( TypeK K :
keySet() ) {
430 final TypeV V =
get(K);
434 }
catch (CloneNotSupportedException e) {
436 throw new InternalError();
454 Iterator<Entry<TypeK,TypeV>> i =
entrySet().iterator();
458 StringBuilder sb =
new StringBuilder();
461 Entry<TypeK,TypeV> e = i.next();
462 TypeK
key = e.getKey();
463 TypeV value = e.getValue();
464 sb.append(
key ==
this ?
"(this Map)" :
key);
466 sb.append(value ==
this ?
"(this Map)" : value);
468 return sb.append(
'}').toString();
476 @SuppressWarnings(
"unchecked")
479 for(
int i=0; i<
len(kvs); i++ ) {
482 Object U = Prime.unbox(
val);
488 return newkvs ==
null ? null :
_getKey(newkvs);
522 @SuppressWarnings(
"unchecked")
524 public TypeV
get( Object
key ) {
526 assert !(V instanceof Prime);
532 final int fullhash=
hash (
key);
533 final int len =
len (kvs);
534 final CHM
chm =
chm (kvs);
537 int idx = fullhash & (
len-1);
544 final Object K =
key(kvs,idx);
545 final Object V =
val(kvs,idx);
546 if( K ==
null )
return null;
562 if( !(V instanceof Prime) )
575 idx = (idx+1)&(
len-1);
584 @SuppressWarnings(
"unchecked")
590 final int fullhash=
hash (
key);
591 final int len =
len (kvs);
592 final CHM
chm =
chm (kvs);
595 int idx = fullhash & (
len-1);
601 final Object K =
key(kvs,idx);
602 if( K ==
null )
return null;
627 idx = (idx+1)&(
len-1);
639 assert putval !=
null;
640 assert !(putval instanceof Prime);
641 assert !(expVal instanceof Prime);
642 final int fullhash =
hash (
key);
643 final int len =
len (kvs);
644 final CHM
chm =
chm (kvs);
646 int idx = fullhash & (
len-1);
651 Object K=
null, V=
null;
652 Object[] newkvs=
null;
707 if( expVal !=
null ) topmap.
help_copy(newkvs);
711 idx = (idx+1)&(
len-1);
719 if( putval == V )
return V;
726 if( newkvs ==
null &&
736 V instanceof Prime) )
745 assert !(V instanceof Prime);
756 (expVal ==
null || !expVal.equals(V)) )
760 if(
CAS_val(kvs, idx, V, putval ) ) {
764 if( expVal !=
null ) {
774 if( V instanceof Prime )
780 return (V==
null && expVal!=
null) ?
TOMBSTONE : V;
792 Object[] topkvs =
_kvs;
793 CHM topchm =
chm(topkvs);
794 if( topchm._newkvs ==
null )
return helper;
795 topchm.help_copy_impl(
this,topkvs,
false);
802 private static final class CHM<TypeK,TypeV> {
829 AtomicReferenceFieldUpdater.newUpdater(
CHM.class,Object[].class,
"_newkvs");
852 AtomicLongFieldUpdater.newUpdater(
CHM.class,
"_resizers");
886 assert
chm(kvs) ==
this;
894 int oldlen =
len(kvs);
900 if( sz >= (oldlen>>2) ) {
904 if( 4L*sz >= ((oldlen>>20)!=0?3L:2L)*oldlen )
914 long tm = System.currentTimeMillis();
916 if( newsz <= oldlen &&
922 if( newsz < oldlen ) newsz = oldlen;
927 long len = ((1L << log2) << 1) + 2;
932 len = (1L << log2) + 2;
933 if (sz > ((
len >> 2) + (
len >> 1)))
throw new RuntimeException(
"Table is full.");
945 long megs = ((((1L<<log2)<<1)+8)<<3)>>20;
946 if( r >= 2 && megs > 0 ) {
955 try { Thread.sleep(megs); }
catch( Exception e ) { }
964 newkvs =
new Object[(int)
len];
966 newkvs[1] =
new int[1<<log2];
994 AtomicLongFieldUpdater.newUpdater(
CHM.class,
"_copyIdx");
1001 AtomicLongFieldUpdater.newUpdater(
CHM.class,
"_copyDone");
1008 assert
chm(oldkvs) ==
this;
1010 assert newkvs !=
null;
1011 int oldlen =
len(oldkvs);
1012 final int MIN_COPY_WORK = Math.min(oldlen,1024);
1015 int panic_start = -1;
1028 if( panic_start == -1 ) {
1030 while( !
_copyIdxUpdater.compareAndSet(
this,copyidx,copyidx+MIN_COPY_WORK) )
1032 if( !(copyidx < (oldlen<<1)) )
1033 panic_start = copyidx;
1038 for(
int i=0; i<MIN_COPY_WORK; i++ )
1039 if(
copy_slot(topmap,(copyidx+i)&(oldlen-1),oldkvs,newkvs) )
1044 copyidx += MIN_COPY_WORK;
1047 if( !copy_all && panic_start == -1 )
1067 assert
chm(oldkvs) ==
this;
1071 assert newkvs !=
null;
1075 return (should_help ==
null) ? newkvs : topmap.
help_copy(newkvs);
1080 assert
chm(oldkvs) ==
this;
1081 int oldlen =
len(oldkvs);
1084 assert (copyDone+workdone) <= oldlen;
1085 if( workdone > 0 ) {
1086 while( !
_copyDoneUpdater.compareAndSet(
this,copyDone,copyDone+workdone) ) {
1088 assert (copyDone+workdone) <= oldlen;
1097 if( copyDone+workdone == oldlen &&
1098 topmap.
_kvs == oldkvs &&
1126 while( (
key=
key(oldkvs,idx)) ==
null )
1132 Object oldval =
val(oldkvs,idx);
1133 while( !(oldval instanceof
Prime) ) {
1135 if(
CAS_val(oldkvs,idx,oldval,box) ) {
1149 oldval =
val(oldkvs,idx);
1160 Object old_unboxed = ((
Prime)oldval)._V;
1170 oldval =
val(oldkvs,idx);
1184 Object[] topkvs =
_kvs;
1185 CHM topchm =
chm(topkvs);
1186 if( topchm.
_newkvs ==
null ) {
1207 @SuppressWarnings(
"unchecked")
1214 if(
_idx != 0 &&
_nextV ==
null )
throw new NoSuchElementException();
1230 {
_nextV = (TypeV)nV;
break; }
1234 public void remove() {
1235 if(
_prevV ==
null )
throw new IllegalStateException();
1243 public Object[]
raw_array() {
return new SnapshotV()._sskvs; }
1266 return new AbstractCollection<TypeV>() {
1270 @Override
public Iterator<TypeV> iterator() {
return new SnapshotV(); }
1275 @SuppressWarnings(
"unchecked")
1306 return new AbstractSet<TypeK> () {
1311 @Override
public Iterator<TypeK> iterator() {
return new SnapshotK(); }
1321 if(
val ==
null )
throw new NullPointerException();
1327 @SuppressWarnings(
"unchecked")
1328 private class
SnapshotE implements Iterator<Map.Entry<TypeK,TypeV>> {
1359 return new AbstractSet<Map.Entry<TypeK,TypeV>>() {
1362 @Override
public boolean remove(
final Object o ) {
1363 if( !(o instanceof Map.Entry))
return false;
1364 final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1367 @Override
public boolean contains(
final Object o) {
1368 if( !(o instanceof Map.Entry))
return false;
1369 final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1370 TypeV v =
get(e.getKey());
1371 return v.equals(e.getValue());
1373 @Override
public Iterator<Map.Entry<TypeK,TypeV>> iterator() {
return new SnapshotE(); }
1379 private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
1380 s.defaultWriteObject();
1381 for( Object K :
keySet() ) {
1382 final Object V =
get(K);
1386 s.writeObject(
null);
1387 s.writeObject(
null);
1392 @SuppressWarnings(
"unchecked")
1393 private
void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {
1394 s.defaultReadObject();
1397 final TypeK K = (TypeK) s.readObject();
1398 final TypeV V = (TypeV) s.readObject();
1399 if( K ==
null )
break;