Class: ThreadSafe::AtomicReferenceCacheBackend::Node

Inherits:
Object
  • Object
show all
Extended by:
Util::Volatile
Includes:
Util::CheapLockable
Defined in:
lib/thread_safe/atomic_reference_cache_backend.rb

Overview

Key-value entry. Nodes with a hash field of MOVED are special, and do not contain user keys or values. Otherwise, keys are never nil, and NULL value fields indicate that a node is in the process of being deleted or created. For purposes of read-only access, a key may be read before a value, but can only be used after checking value to be != NULL.

Constant Summary collapse

MOVED =

Encodings for special uses of Node hash fields. See above for explanation.

('10' << ('0' * bit_shift)).to_i(2)
LOCKED =

set/tested only as a bit

('01' << ('0' * bit_shift)).to_i(2)
WAITING =

both bits set/tested together

('11' << ('0' * bit_shift)).to_i(2)
HASH_BITS =

usable bits of normal node hash

('00' << ('1' * bit_shift)).to_i(2)
SPIN_LOCK_ATTEMPTS = 
Util::CPU_COUNT > 1 ? Util::CPU_COUNT * 2 : 0

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Util::Volatile

attr_volatile

Constructor Details

#initialize(hash, key, value, next_node = nil) ⇒ Node

Returns a new instance of Node.



254
255
256
257
258
259
260
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 254

def initialize(hash, key, value, next_node = nil)
  super()
  @key = key
  self.lazy_set_hash(hash)
  self.lazy_set_value(value)
  self.next = next_node
end

Instance Attribute Details

#key ⇒ Object (readonly)

Returns the value of attribute key.



252
253
254
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 252

def key
  @key
end

Class Method Details

.locked_hash?(hash) ⇒ Boolean

Returns:

  • (Boolean) 


339
340
341
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 339

def locked_hash?(hash)
  (hash & LOCKED) != 0
end

Instance Method Details

#key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


294
295
296
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 294

def key?(key)
  @key.eql?(key)
end

#locked? ⇒ Boolean

Returns:

  • (Boolean) 


316
317
318
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 316

def locked?
  self.class.locked_hash?(hash)
end

#matches?(key, hash) ⇒ Boolean

Returns:

  • (Boolean) 


298
299
300
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 298

def matches?(key, hash)
  pure_hash == hash && key?(key)
end

#pure_hash ⇒ Object 



302
303
304
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 302

def pure_hash
  hash & HASH_BITS
end

#try_await_lock(table, i) ⇒ Object

Spins a while if LOCKED bit set and this node is the first of its bin, and then sets WAITING bits on hash field and blocks (once) if they are still set. It is OK for this method to return even if lock is not available upon exit, which enables these simple single-wait mechanics.

The corresponding signalling operation is performed within callers: Upon detecting that WAITING has been set when unlocking lock (via a failed CAS from non-waiting LOCKED state), unlockers acquire the cheap_synchronize lock and perform a cheap_broadcast.



273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 273

def try_await_lock(table, i)
  if table && i >= 0 && i < table.size # bounds check, TODO: why are we bounds checking?
    spins = SPIN_LOCK_ATTEMPTS
    randomizer = base_randomizer = Util::XorShiftRandom.get
    while equal?(table.volatile_get(i)) && self.class.locked_hash?(my_hash = hash)
      if spins >= 0
        if (randomizer = (randomizer >> 1)).even? # spin at random
          if (spins -= 1) == 0
            Thread.pass # yield before blocking
          else
            randomizer = base_randomizer = Util::XorShiftRandom.xorshift(base_randomizer) if randomizer.zero?
          end
        end
      elsif cas_hash(my_hash, my_hash | WAITING)
        force_aquire_lock(table, i)
        break
      end
    end
  end
end

#try_lock_via_hash(node_hash = hash) ⇒ Object 



306
307
308
309
310
311
312
313
314
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 306

def try_lock_via_hash(node_hash = hash)
  if cas_hash(node_hash, locked_hash = node_hash | LOCKED)
    begin
      yield
    ensure
      unlock_via_hash(locked_hash, node_hash)
    end
  end
end

#unlock_via_hash(locked_hash, node_hash) ⇒ Object 



320
321
322
323
324
325
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 320

def unlock_via_hash(locked_hash, node_hash)
  unless cas_hash(locked_hash, node_hash)
    self.hash = node_hash
    cheap_synchronize { cheap_broadcast }
  end
end