Class: PEROBS::IndexTree

Inherits:
Object
  • Object
show all
Defined in:
lib/perobs/IndexTree.rb

Overview

The IndexTree maps the object ID to the address in the FlatFile. The search in the tree is much faster than the linear search in the FlatFile.

Constant Summary collapse

MAX_CACHED_LEVEL =

Determines how many levels of the IndexTree will be kept in memory to accerlerate the access. A number of 7 will keep up to 21845 entries in the cache but will accelerate the access to the FlatFile address.

7

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(db_dir) ⇒ IndexTree

Returns a new instance of IndexTree.



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/perobs/IndexTree.rb', line 44

def initialize(db_dir)
  # Directory path used to store the files.
  @db_dir = db_dir

  # This FixedSizeBlobFile contains the nodes of the IndexTree.
  @nodes = FixedSizeBlobFile.new(db_dir, 'database_index',
                                 IndexTreeNode::NODE_BYTES)

  # The node sequence usually only reveals a partial match with the
  # requested ID. So, the leaves of the tree point to the object_id_index
  # file which contains the full object ID and the address of the
  # corresponding object in the FlatFile.
  @ids = FixedSizeBlobFile.new(db_dir, 'object_id_index', 2 * 8)

  # The first MAX_CACHED_LEVEL levels of nodes will be cached in memory to
  # improve access times.
  @node_cache = {}
end

Instance Attribute Details

#ids ⇒ Object (readonly)

Returns the value of attribute ids.



42
43
44
 
# File 'lib/perobs/IndexTree.rb', line 42

def ids
  @ids
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



42
43
44
 
# File 'lib/perobs/IndexTree.rb', line 42

def nodes
  @nodes
end

Instance Method Details

#check(flat_file) ⇒ Object

Check if the index is OK and matches the flat_file data.



151
152
153
 
# File 'lib/perobs/IndexTree.rb', line 151

def check(flat_file)
  @root.check(flat_file)
end

#clear ⇒ Object

Delete all data from the tree.



83
84
85
86
87
88
 
# File 'lib/perobs/IndexTree.rb', line 83

def clear
  @nodes.clear
  @ids.clear
  @node_cache = {}
  @root = IndexTreeNode.new(self, 0, 0)
end

#close ⇒ Object

Close the tree files.



71
72
73
74
 
# File 'lib/perobs/IndexTree.rb', line 71

def close
  @ids.close
  @nodes.close
end

#delete_node(nibble, address) ⇒ Object

Delete a node from the tree that corresponds to the address.

Parameters:

  • nibble (Fixnum) —

    The corresponding nibble for the node

  • address (Integer) —

    The address of the node in @nodes



114
115
116
117
118
119
120
 
# File 'lib/perobs/IndexTree.rb', line 114

def delete_node(nibble, address)
  # First delete the node from the node cache.
  mask = (2 ** ((1 + nibble) * 4)) - 1
  @node_cache.delete(address & mask)
  # Then delete it from the 'database_index' file.
  @nodes.delete_blob(address)
end

#delete_value(id) ⇒ Object

Delete the value with the given ID.

Parameters:

  • id (Integer) 


146
147
148
 
# File 'lib/perobs/IndexTree.rb', line 146

def delete_value(id)
  @root.delete_value(id)
end

#get_node(nibble, address = nil) ⇒ Object

Return an IndexTreeNode object that corresponds to the given address.

Parameters:

  • nibble (Fixnum) —

    Index of the nibble the node should correspond to

  • address (Integer) (defaults to: nil) —

    Address of the node in @nodes or nil



93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/perobs/IndexTree.rb', line 93

def get_node(nibble, address = nil)
  # Generate a mask for the least significant bits up to and including the
  # nibble.
  mask = (2 ** ((1 + nibble) * 4)) - 1
  if address && (node = @node_cache[address & mask])
    # We have an address and have found the node in the node cache.
    return node
  else
    # We don't have a IndexTreeNode object yet for this node. Create it
    # with the data from the 'database_index' file.
    node = IndexTreeNode.new(self, nibble, address)
    # Add the node to the node cache if it's up to MAX_CACHED_LEVEL levels
    # down from the root.
    @node_cache[address & mask] = node if nibble <= MAX_CACHED_LEVEL
    return node
  end
end

#get_value(id) ⇒ Fixnum

Retrieve the value that was stored with the given ID.

Parameters:

  • id (Integer) —

    ID of the value to retrieve

Returns:

  • (Fixnum) —

    value



140
141
142
 
# File 'lib/perobs/IndexTree.rb', line 140

def get_value(id)
  @root.get_value(id)
end

#inspect ⇒ String

Convert the tree into a human readable form.

Returns:

  • (String) 


157
158
159
 
# File 'lib/perobs/IndexTree.rb', line 157

def inspect
  @root.inspect
end

#open ⇒ Object

Open the tree files.



64
65
66
67
68
 
# File 'lib/perobs/IndexTree.rb', line 64

def open
  @nodes.open
  @ids.open
  @root = IndexTreeNode.new(self, 0, 0)
end

#put_value(id, value) ⇒ Object

Store a ID/value touple into the tree. The value can later be retrieved by the ID again. IDs are always unique in the tree. If the ID already exists in the tree, the value will be overwritten.

Parameters:

  • id (Integer) —

    ID or key

  • value (Integer) —

    value to store



127
128
129
130
131
132
133
134
135
 
# File 'lib/perobs/IndexTree.rb', line 127

def put_value(id, value)
  #MAX_CACHED_LEVEL.downto(0) do |i|
  #  mask = (2 ** ((1 + i) * 4)) - 1
  #  if (node = @node_cache[value & mask])
  #    return node.put_value(id, value)
  #  end
  #end
  @root.put_value(id, value)
end

#sync ⇒ Object

Flush out all unwritten data



77
78
79
80
 
# File 'lib/perobs/IndexTree.rb', line 77

def sync
  @ids.sync
  @nodes.sync
end