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

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



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/perobs/IndexTreeNode.rb', line 53

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
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) ⇒ Boolean

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

Parameters:

Returns:

  • (Boolean) —

    true if no errors were found, false otherwise



189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/perobs/IndexTreeNode.rb', line 189

def check(flat_file)
  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 @tree.get_node(@nibble_idx + 1, @entries[index]).
             check(flat_file)
        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.



147
148
149
150
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
 
# File 'lib/perobs/IndexTreeNode.rb', line 147

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
      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 = @tree.get_node(@nibble_idx + 1, @entries[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.



249
250
251
 
# File 'lib/perobs/IndexTreeNode.rb', line 249

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



116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
# File 'lib/perobs/IndexTreeNode.rb', line 116

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 @tree.get_node(@nibble_idx + 1, @entries[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.



220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
 
# File 'lib/perobs/IndexTreeNode.rb', line 220

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 += "  " + @tree.get_node(@nibble_idx + 1, @entries[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



72
73
74
75
76
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
 
# File 'lib/perobs/IndexTreeNode.rb', line 72

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
      # 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.
    node = @tree.get_node(@nibble_idx + 1, @entries[index])
    node.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



241
242
243
244
245
 
# File 'lib/perobs/IndexTreeNode.rb', line 241

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