Volatile long _resizers; // count of threads attempting a resize

static private final AtomicLongFieldUpdater<CAT> _resizerUpdater =

AtomicLongFieldUpdater.newUpdater(CAT.class, "_resizers");

private final CAT _next;

private volatile long _sum_cache;

private volatile long _fuzzy_sum_cache;

private volatile long _fuzzy_time;

private static final int MAX_SPIN=2;

private long[] _t; // Power-of-2 array of longs

CAT( CAT next, int sz, long init ) {

_next = next;

_sum_cache = Long.MIN_VALUE;

_t = new long[sz];

_t[0] = init;

}

// Only add 'x' to some slot in table, hinted at by 'hash', if bits under

// the mask are all zero. The sum can overflow or 'x' can contain bits in

// the mask. Value is CAS'd so no counts are lost. The CAS is attempted

// ONCE.

public long add_if_mask( long x, long mask, int hash, ConcurrentAutoTable master ) {

long[] t = _t;

int idx = hash & (t.length-1);

// Peel loop; try once fast

long old = t[idx];

boolean ok = CAS( t, idx, old&~mask, old+x );

if( _sum_cache != Long.MIN_VALUE )

_sum_cache = Long.MIN_VALUE; // Blow out cache

if( ok ) return old; // Got it

if( (old&mask) != 0 ) return old; // Failed for bit-set under mask

// Try harder

int cnt=0;

while( true ) {

old = t[idx];

if( (old&mask) != 0 ) return old; // Failed for bit-set under mask

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;

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?

// 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. 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.

master.CAS_cat(this,newcat);

return old;

}

// Return the current sum of all things in the table, stripping off mask

// before the add. Writers can be updating the table furiously, so the

// sum is only locally accurate.

public long sum( long mask ) {

long sum = _sum_cache;

if( sum != Long.MIN_VALUE ) return sum;

sum = _next == null ? 0 : _next.sum(mask); // Recursively get cached sum

long[] t = _t;

for( int i=0; i<t.length; i++ )

sum += t[i]&(~mask);

_sum_cache = sum; // Cache includes recursive counts

return sum;

}

// Fast fuzzy version. Used a cached value until it gets old, then re-up

// the cache.

public long estimate_sum( long mask ) {

// For short tables, just do the work

if( _t.length <= 64 ) return sum(mask);

// For bigger tables, periodically freshen a cached value

long millis = System.currentTimeMillis();

if( _fuzzy_time != millis ) { // Time marches on?

_fuzzy_sum_cache = sum(mask); // Get sum the hard way

_fuzzy_time = millis; // Indicate freshness of cached value

}

return _fuzzy_sum_cache; // Return cached sum

}

// Update all table slots with CAS.

public void all_or ( long mask ) {

long[] t = _t;

for( int i=0; i<t.length; i++ ) {

boolean done = false;

while( !done ) {

long old = t[i];

done = CAS(t,i, old, old|mask );

}

}

if( _next != null ) _next.all_or(mask);

if( _sum_cache != Long.MIN_VALUE )

_sum_cache = Long.MIN_VALUE; // Blow out cache

}

public void all_and( long mask ) {

long[] t = _t;

for( int i=0; i<t.length; i++ ) {

boolean done = false;

while( !done ) {

long old = t[i];

done = CAS(t,i, old, old&mask );

}

}

if( _next != null ) _next.all_and(mask);

if( _sum_cache != Long.MIN_VALUE )

_sum_cache = Long.MIN_VALUE; // Blow out cache

}

// Set/stomp all table slots. No CAS.

public void all_set( long val ) {

long[] t = _t;

for( int i=0; i<t.length; i++ )

t[i] = val;

if( _next != null ) _next.all_set(val);

if( _sum_cache != Long.MIN_VALUE )

_sum_cache = Long.MIN_VALUE; // Blow out cache

}

String toString( long mask ) { return Long.toString(sum(mask)); }

public void print() {

long[] t = _t;

System.out.print("[sum="+_sum_cache+","+t[0]);

for( int i=1; i<t.length; i++ )

System.out.print(","+t[i]);

System.out.print("]");

if( _next != null ) _next.print();

}

}

}

Clutter. Code that is not dead but does not add any functionality.

Dead comments. Comments cover unused things.

public class Counter extends ConcurrentAutoTable {

// Add the given value to current counter value. Concurrent updates will

// not be lost, but addAndGet or getAndAdd are not implemented because but

// the total counter value is not atomically updated.

//public void add( long x );

//public void decrement();

//public void increment();

// 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 all the striped counters.

//public long get();

//public int intValue();

//public long longValue();

// A cheaper 'get'. Updated only once/millisecond, but fast as a simple

// load instruction when not updating.

//public long estimate_get( );

}

Needless complexity. The design contains elements that are currently not useful.

Chatty tests. A tests that fill the console with text.

public class BitPrintTest extends TestCase {

public void testBitPrinting() {

long[] buf = new long[256];

for(int i = 0; i < buf.length; i++) {

buf[i] = i;

}

System.out.println(BitPrint.fmt(buf));

}

}