Class: XRBP::SHAMap

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/xrbp/nodestore/shamap.rb,
lib/xrbp/nodestore/shamap/item.rb,
lib/xrbp/nodestore/shamap/node.rb,
lib/xrbp/nodestore/shamap/errors.rb,
lib/xrbp/nodestore/shamap/node_id.rb,
lib/xrbp/nodestore/shamap/tree_node.rb,
lib/xrbp/nodestore/shamap/inner_node.rb,
lib/xrbp/nodestore/shamap/node_factory.rb,
lib/xrbp/nodestore/shamap/tagged_cache.rb

Defined Under Namespace

Modules: Errors, NodeFactory Classes: InnerNode, Item, Node, NodeID, TaggedCache, TreeNode

Instance Method Summary collapse

Constructor Details

#initialize(args = {}) ⇒ SHAMap

Returns a new instance of SHAMap.



13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/xrbp/nodestore/shamap.rb', line 13

def initialize(args={})
        @db = args[:db]
   @version = args[:version]

  if @version == 2
    @root = InnerNode.new :v2    => true,
                          :depth => 0
  else
    @root = InnerNode.new :v2 => false
  end
end

Instance Method Details

#cdir_first(root_index) ⇒ Object

Returns first directory index in the specified root index

See Also:



400
401
402
403
404
 
# File 'lib/xrbp/nodestore/shamap.rb', line 400

def cdir_first(root_index)
  node = read(root_index)
  raise unless node # never probe for dirs
  cdir_next(root_index, node, 0)
end

#cdir_next(root_index, node, dir_entry) ⇒ Object

Returns the key of the index in the the node’s “indexes” field corresponding to ‘dir_entry’.

Also returns directory node which contains key of the node being returned.

Also returns dir_entry index of next record in directory node.

This method handles the special case where dir_entry is greater than the local indexes size but the ‘index_next’ is also set. In this case, index traversal will continue on the next SLE node whose lookup key is calculated from the root index and ‘index_next’ value. In this case the directory node and next dir_entry will be set appropriately and returned.

Parameters:

  • root_index —

    top level index of the tree being traversed.

  • node —

    SLE containing ‘indexes’ field from which the ‘dir_entry’th index will be returned

  • dir_entry —

    numerical array index to return from ‘indexes’



430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
 
# File 'lib/xrbp/nodestore/shamap.rb', line 430

def cdir_next(root_index, node, dir_entry)
  indexes = node.field(:vector256, :indexes)
  raise unless dir_entry <= indexes.size

  if dir_entry >= indexes.size
    nxt = node.field(:uint64, :index_next)
    return nil unless nxt

    nxt = read(NodeStore::Indexes::page(root_index, nxt))
    return nil unless nxt

    return cdir_next(root_index, nxt, 0)
  end

  return indexes[dir_entry], node, (dir_entry + 1)
end

#each ⇒ Object

Invoke callback block w/ each sequential SHAMap item Implements Enumerable interface.



27
28
29
30
31
32
33
34
35
 
# File 'lib/xrbp/nodestore/shamap.rb', line 27

def each
  current, stack = *peek_first_item
  until current.nil?
    yield current.item
    current, stack = *peek_next_item(current.item.key, stack)
  end

  return self
end

#fetch_node(key) ⇒ Object

Fetch node from database raising error if it is not found



105
106
107
108
109
 
# File 'lib/xrbp/nodestore/shamap.rb', line 105

def fetch_node(key)
  node = fetch_node_nt(key)
  raise unless node
  node
end

#fetch_node_nt(key) ⇒ Object

Retrieve node from db. nt = no throw



113
114
115
116
117
 
# File 'lib/xrbp/nodestore/shamap.rb', line 113

def fetch_node_nt(key)
  res = get_cache(key)
  return res if res
  canonicalize(key, fetch_node_from_db(key))
end

#fetch_root(key) ⇒ Object

Fetch key from database and assign result as root element



121
122
123
124
125
126
127
128
129
 
# File 'lib/xrbp/nodestore/shamap.rb', line 121

def fetch_root(key)
  return true if key == root.hash

  root = fetch_node_nt(key)
  return false unless root

  @root = root
  return true
end

#peek_first_item ⇒ Object

Return node corresponding to first item in map



69
70
71
72
73
74
 
# File 'lib/xrbp/nodestore/shamap.rb', line 69

def peek_first_item
  stack = []
  node, stack = *first_below(@root, stack)
  return nil unless node
  return node, stack
end

#peek_item(key) ⇒ Object

Return node corresponding to key or nil if not found



62
63
64
65
66
 
# File 'lib/xrbp/nodestore/shamap.rb', line 62

def peek_item(key)
  leaf = find_key(key)
  return nil unless leaf
  leaf.peek_item
end

#peek_next_item(id, stack) ⇒ Object

Return node corresponding to next sequential item in map



78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/xrbp/nodestore/shamap.rb', line 78

def peek_next_item(id, stack)
  raise if stack.empty?
  raise unless stack.last.first.leaf?
  stack.pop

  until stack.empty?
    node, node_id = *stack.last
    raise if node.leaf?

    # Select next higher tree branch
    inner = node
    (node_id.select_branch(id) + 1).upto(15) { |b|
      next if inner.empty_branch?(b)
      node = descend_throw(inner, b)
      leaf, stack = *first_below(node, stack, b)
      raise unless leaf && leaf.leaf?
      return leaf, stack
    }

    stack.pop
  end

  return nil
end

#read(key) ⇒ Object

Read Key from database and return corresponding SLE



48
49
50
51
52
53
54
55
56
 
# File 'lib/xrbp/nodestore/shamap.rb', line 48

def read(key)
  raise if key.zero?
  item = peek_item(key)
  return nil unless item
   sle = NodeStore::SLE.new :item => item,
                            :key  => key
  #return nil unless key.check?(sle)
   sle
end

#succ(key, last) ⇒ Object

Return the next key in tree greater than specified one and less than last



39
40
41
42
43
44
 
# File 'lib/xrbp/nodestore/shamap.rb', line 39

def succ(key, last)
  item = upper_bound(key)
  return nil if item == map_end
  return nil if last && item.key.to_bn >= last.to_bn
  return item.key
end