Class: ConcurrentRedBlackTree

Inherits:
RedBlackTree show all
Defined in:
lib/red_black_tree.rb

Defined Under Namespace

Classes: ConcurrentNode

Constant Summary

Constants inherited from RedBlackTree

RedBlackTree::DEFAULT

Instance Attribute Summary

Attributes inherited from RedBlackTree

#default, #default_proc

Instance Method Summary collapse

Methods inherited from RedBlackTree

#dump_sexp, #dump_tree, #each, #each_key, #each_value, #key?, #keys, #size, #to_hash, #values

Constructor Details

#initialize(default = DEFAULT, &block) ⇒ ConcurrentRedBlackTree

Returns a new instance of ConcurrentRedBlackTree.



800
801
802
803
 
# File 'lib/red_black_tree.rb', line 800

def initialize(default = DEFAULT, &block)
  super
  @root = Atomic.new(ConcurrentNode::EMPTY_CONCURRENT)
end

Instance Method Details

#[](key) ⇒ Object 



827
828
829
830
831
832
833
834
 
# File 'lib/red_black_tree.rb', line 827

def [](key)
  value = @root.get.retrieve(key)
  if value == Node::UNDEFINED
    default_value
  else
    value
  end
end

#[]=(key, value) ⇒ Object Also known as: insert 



817
818
819
820
821
822
823
824
 
# File 'lib/red_black_tree.rb', line 817

def []=(key, value)
  @root.update { |root|
    root = root.insert(key, value)
    root.set_root
    root.check_height if $DEBUG
    root
  }
end

#clear ⇒ Object 



813
814
815
 
# File 'lib/red_black_tree.rb', line 813

def clear
  @root.set(ConcurrentNode::EMPTY_CONCURRENT)
end

#delete(key) ⇒ Object 



836
837
838
839
840
841
842
843
844
845
846
847
 
# File 'lib/red_black_tree.rb', line 836

def delete(key)
  deleted = nil
  @root.update { |root|
    deleted, root, rebalance = root.delete(key)
    unless root == ConcurrentNode::EMPTY_CONCURRENT
      root.set_root
      root.check_height if $DEBUG
    end
    root
  }
  deleted.value
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


809
810
811
 
# File 'lib/red_black_tree.rb', line 809

def empty?
  root == ConcurrentNode::EMPTY_CONCURRENT
end

#root ⇒ Object 



805
806
807
 
# File 'lib/red_black_tree.rb', line 805

def root
  @root.get
end