Class: PEROBS::IndexTreeNode

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

Overview

The IndexTreeNode is the building block of the IndexTree. Each node can hold up to 16 entries. An entry is described by type bits and can be empty (0), an reference into the object ID file (1) or a reference to another IndexTreeNode for the next nibble (2). Each level of the tree is associated with an specific nibble of the ID. The nibble is used to identify the entry within the node. IndexTreeNode objects are in-memory represenations of the nodes in the IndexTree file.

Constant Summary collapse

ENTRIES = 
16
ENTRY_BYTES = 
8
TYPE_BYTES = 
4
NODE_BYTES = 
TYPE_BYTES + ENTRIES * ENTRY_BYTES
CACHED_LEVELS =

How many levels of the tree should be kept in memory.

4

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tree, nibble_idx, address = nil) ⇒ IndexTreeNode

Create a new IndexTreeNode.

Parameters:

  • tree (IndexTree) —

    The tree this node belongs to

  • nibble_idx (Fixnum) —

    the level of the node in the tree (root being 0)

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

    The address of this node in the blob file



55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/perobs/IndexTreeNode.rb', line 55

def initialize(tree, nibble_idx, address = nil)
  @tree = tree
  if nibble_idx >= 16
    # We are processing 64 bit numbers, so we have at most 16 nibbles.
    PEROBS.log.fatal 'nibble must be 0 - 15'
  end
  @nibble_idx = nibble_idx
  if (@address = address).nil? || !read_node
    # Create a new node if none with this address exists already.
    @entry_types = 0
    @entries = ::Array.new(ENTRIES, 0)
    @address = @tree.nodes.free_address
    write_node
  end
  # These are the pointers that point to the next level of IndexTreeNode
  # elements.
  @node_ptrs = ::Array.new(ENTRIES, nil)
end

Instance Attribute Details

#address ⇒ Object (readonly)

Returns the value of attribute address.



41
42
43
 
# File 'lib/perobs/IndexTreeNode.rb', line 41

def address
  @address
end

Instance Method Details

#check(flat_file, tree_level) ⇒ Boolean

Recursively check this node and all sub nodes. Compare the found ID/address pairs with the corresponding entry in the given FlatFile.

Parameters:

  • flat_file (FlatFile)
  • tree_level (Fixnum) —

    Assumed level in the tree. Must correspond with @nibble_idx

Returns:

  • (Boolean) —

    true if no errors were found, false otherwise



196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
 
# File 'lib/perobs/IndexTreeNode.rb', line 196

def check(flat_file, tree_level)
  if tree_level >= 16
    PEROBS.log.error "IndexTreeNode level (#{tree_level}) too large"
    return false
  end
  ENTRIES.times do |index|
    case get_entry_type(index)
    when 0
      # Empty entry, nothing to do here.
    when 1
      # There is a value stored for the ID part that we have seen so far.
      # We still need to compare the requested ID with the full ID to
      # determine a match.
      id, address = get_id_and_address(@entries[index])
      unless flat_file.has_id_at?(id, address)
        PEROBS.log.error "The entry for ID #{id} in the index was not " +
          "found in the FlatFile at address #{address}"
        return false
      end
    when 2
      # The entry is a reference to another node. Just follow it and look
      # at the next nibble.
      unless get_node(index).check(flat_file, tree_level + 1)
        return false
      end
    else
      return false
    end
  end

  true
end

#delete_value(id) ⇒ Boolean

Delete the entry for the given ID.

Parameters:

  • id (Integer) —

    ID or key

Returns:

  • (Boolean) —

    True if a key was found and deleted, otherwise false.



151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/perobs/IndexTreeNode.rb', line 151

def delete_value(id)
  index = calc_index(id)
  case get_entry_type(index)
  when 0
    # There is no entry for this ID.
    return false
  when 1
    # We have a value. Check that the ID matches and delete the value.
    stored_id, address = get_id_and_address(@entries[index])
    if id == stored_id
      @tree.ids.delete_blob(@entries[index])
      @entries[index] = 0
      @node_ptrs[index] = nil
      set_entry_type(index, 0)
      write_node
      return true
    else
      # Just a partial ID match.
      return false
    end
  when 2
    # The entry is a reference to another node.
    node = get_node(index)
    result = node.delete_value(id)
    if node.empty?
      # If the sub-node is empty after the delete we delete the whole
      # sub-node.
      @tree.delete_node(@nibble_idx + 1, @entries[index])
      # Eliminate the reference to the sub-node and update this node in
      # the file.
      set_entry_type(index, 0)
      write_node
    end
    return result
  else
    PEROBS.node.fatal "Illegal node type #{get_entry_type(index)}"
  end
end

#empty? ⇒ Boolean

Check if the node is empty.

Returns:

  • (Boolean) —

    True if all entries are empty.



258
259
260
 
# File 'lib/perobs/IndexTreeNode.rb', line 258

def empty?
  @entry_types == 0
end

#get_value(id) ⇒ Integer

Retrieve the value for the given ID.

Parameters:

  • id (Integer) —

    ID (or key)

Returns:

  • (Integer) —

    value or nil



121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/perobs/IndexTreeNode.rb', line 121

def get_value(id)
  index = calc_index(id)
  case get_entry_type(index)
  when 0
    # There is no entry for this ID.
    return nil
  when 1
    # There is a value stored for the ID part that we have seen so far. We
    # still need to compare the requested ID with the full ID to determine
    # a match.
    stored_id, address = get_id_and_address(@entries[index])
    if id == stored_id
      # We have a match. Return the value.
      return address
    else
      # Just a partial match of the least significant nibbles.
      return nil
    end
  when 2
    # The entry is a reference to another node. Just follow it and look at
    # the next nibble.
    return get_node(index).get_value(id)
  else
    PEROBS.log.fatal "Illegal node type #{get_entry_type(index)}"
  end
end

#inspect ⇒ Object

Convert the node and all sub-nodes to human readable format.



230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
# File 'lib/perobs/IndexTreeNode.rb', line 230

def inspect
  str = "{\n"
  0.upto(15) do |i|
    case get_entry_type(i)
    when 0
      # Don't show empty entries.
    when 1
      id, address = get_id_and_address(@entries[i])
      str += "  #{id} => #{address},\n"
    when 2
      str += "  " + get_node(i).inspect.gsub(/\n/, "\n  ")
    end
  end
  str + "}\n"
end

#put_value(id, value) ⇒ Object

Store a value for the given ID. Existing values will be overwritten.

Parameters:

  • id (Integer) —

    ID (or key)

  • value (Integer) —

    value



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/perobs/IndexTreeNode.rb', line 77

def put_value(id, value)
  index = calc_index(id)
  case get_entry_type(index)
  when 0
    # The entry is still empty. Store the id and value and set the entry
    # to holding a value (1).
    set_entry_type(index, 1)
    @entries[index] = address = @tree.ids.free_address
    store_id_and_value(address, id, value)
    write_node
  when 1
    existing_value = @entries[index]
    existing_id, existing_address = get_id_and_address(existing_value)
    if id == existing_id
      if value != existing_address
        # The entry already holds another value.
        store_id_and_value(@entries[index], id, value)
      end
    else
      # The entry already holds a value. We need to create a new node and
      # store the existing value and the new value in it.
      # First get the exiting value of the entry and the corresponding ID.
      # Create a new node.
      node = @tree.get_node(@nibble_idx + 1)
      # The entry of the current node is now a reference to the new node.
      set_entry_type(index, 2)
      @entries[index] = node.address
      @node_ptrs[index] = node if @nibble_idx < CACHED_LEVELS
      # Store the existing value and the new value with their IDs.
      node.set_entry(existing_id, existing_value)
      node.put_value(id, value)
    end
    write_node
  when 2
    # The entry is a reference to another node.
    get_node(index).put_value(id, value)
  else
    PEROBS.log.fatal "Illegal node type #{get_entry_type(index)}"
  end
end

#set_entry(id, value) ⇒ Object

Utility method to set the value of an existing node entry. address from the ids list.

Parameters:

  • id (Integer) —

    ID or key

  • value (Integer) —

    value to set. Note that this value must be an



250
251
252
253
254
 
# File 'lib/perobs/IndexTreeNode.rb', line 250

def set_entry(id, value)
  index = calc_index(id)
  set_entry_type(index, 1)
  @entries[index] = value
end