class Concurrent::ThreadSafe::Util::Striped64

@!visibility private
needed again; and for short-lived ones, it does not matter.
observed contention levels will recur, so the cells will eventually be
remove such cells, under the assumption that for long-running instances,
thread to hash to it under expanded mask. We do not try to detect or
to it terminate, as well as in the case where doubling the table causes no
It is possible for a Cell to become unused when threads that once hashed
typically low in these cases.
However, despite these limitations, observed contention rates are
threads are typically not bound to CPUS forever, may not occur at all.
only become known via CAS failures, convergence can be slow, and because
hash codes of colliding threads. Because search is random, and collisions
When we reach capacity, we search for this mapping by randomly varying the
perfect hash function mapping threads to slots that eliminates collisions.
supposing that each thread were bound to a CPU, there would exist a
The table size is capped because, when there are more threads than CPUs,
find a free slot.
proceed by “double hashing”, using a secondary hash (XorShift) to try to
Cell is created. Otherwise, if the slot exists, a CAS is tried. Retries
holds the lock. If a hashed slot is empty, and lock is available, a new
is less than the capacity, it is doubled in size unless some other thread
operation (see method retry_update). Upon a collision, if the table size
table collisions are indicated by failed CASes when performing an update
Per-thread hash codes are initialized to random values. Contention and/or
reduced locality, which is still better than alternatives.
(or the base). During these retries, there is increased contention and
a blocking lock: When the lock is not available, threads try other slots
table, as well as populating slots with new +Cell+s. There is no need for
A single spinlock (busy) is used for initializing and resizing the
needed.
to the number of CPUS. Table slots remain empty (nil) until they are
contention until reaching the nearest power of two greater than or equal
table is initialized to size 2. The table size is doubled upon further
base field. Upon first contention (a failed CAS on base update), the
they are needed. When there is no contention, all updates are made to the
In part because +Cell+s are relatively large, we avoid creating them until
this precaution.
often share cache lines (with a huge negative performance impact) without
arrays will tend to be placed adjacent to each other, and so will most
don’t interfere much with each other. But Atomic objects residing in
Atomics because they are usually irregularly scattered in memory and thus
reduce cache contention on most processors. Padding is overkill for most
Table entries are of class Cell; a variant of AtomicLong padded to
class are private, accessed directly by subclasses.
Indexing uses masked per-thread hash codes. Nearly all methods on this
variables, plus an extra base field. The table size is a power of two.
This class maintains a lazily-initialized table of atomically updated
dynamic striping on 64bit values.
Class holding common representation and mechanics for classes supporting
Original source code available here:
available in public domain.
A Ruby port of the Doug Lea’s jsr166e.Striped64 class version 1.6

def cas_base_computed 

def cas_base_computed
  cas_base(current_base = base, yield(current_base))
end

def expand_table_unless_stale(current_cells) 

def expand_table_unless_stale(current_cells)
  try_in_busy do
    if current_cells == cells # Recheck under lock
      new_cells = current_cells.next_in_size_table
      current_cells.each_with_index {|x, i| new_cells.volatile_set(i, x)}
      self.cells = new_cells
    end
  end
end

def free? 

def free?
  !busy?
end

def hash_code

random, but may be set to a different value upon collisions.
A thread-local hash code accessor. The code is initially 
def hash_code
  Thread.current[THREAD_LOCAL_KEY] ||= XorShiftRandom.get
end

def hash_code=(hash) 

def hash_code=(hash)
  Thread.current[THREAD_LOCAL_KEY] = hash
end

def initialize 

def initialize
  super()
  self.busy = false
  self.base = 0
end

def internal_reset(initial_value)

Sets base and all +cells+ to the given value. 
def internal_reset(initial_value)
  current_cells = cells
  self.base     = initial_value
  if current_cells
    current_cells.each do |cell|
      cell.value = initial_value if cell
    end
  end
end

def retry_update(x, hash_code, was_uncontended) # :yields: current_value

:yields: current_value
false if CAS failed before call
[+x+]
hash code used
[+hash_code+]
the value
[+x+]
Arguments:

reads.
problems of optimistic retry code, relying on rechecked sets of
explanation. This method suffers the usual non-modularity
creating new Cells, and/or contention. See above for
Handles cases of updates involving initialization, resizing, 
def retry_update(x, hash_code, was_uncontended) # :yields: current_value
  hash     = hash_code
  collided = false # True if last slot nonempty
  while true
    if current_cells = cells
      if !(cell = current_cells.volatile_get_by_hash(hash))
        if busy?
          collided = false
        else # Try to attach new Cell
          if try_to_install_new_cell(Cell.new(x), hash) # Optimistically create and try to insert new cell
            break
          else
            redo # Slot is now non-empty
          end
        end
      elsif !was_uncontended # CAS already known to fail
        was_uncontended = true # Continue after rehash
      elsif cell.cas_computed {|current_value| yield current_value}
        break
      elsif current_cells.size >= CPU_COUNT || cells != current_cells # At max size or stale
        collided = false
      elsif collided && expand_table_unless_stale(current_cells)
        collided = false
        redo # Retry with expanded table
      else
        collided = true
      end
      hash = XorShiftRandom.xorshift(hash)
    elsif try_initialize_cells(x, hash) || cas_base_computed {|current_base| yield current_base}
      break
    end
  end
  self.hash_code = hash
end

def try_in_busy 

def try_in_busy
  if cas_busy(false, true)
    begin
      yield
    ensure
      self.busy = false
    end
  end
end

def try_initialize_cells(x, hash) 

def try_initialize_cells(x, hash)
  if free? && !cells
    try_in_busy do
      unless cells # Recheck under lock
        new_cells = PowerOfTwoTuple.new(2)
        new_cells.volatile_set_by_hash(hash, Cell.new(x))
        self.cells = new_cells
      end
    end
  end
end

def try_to_install_new_cell(new_cell, hash) 

def try_to_install_new_cell(new_cell, hash)
  try_in_busy do
    # Recheck under lock
    if (current_cells = cells) && !current_cells.volatile_get(i = current_cells.hash_to_index(hash))
      current_cells.volatile_set(i, new_cell)
    end
  end
end