lil Insertion

Metadata

Class QuART_lil represents a QuART tree with lil implementation. It uses the following metadata to perform lil insertions:

• root: The root node of the tree
• maxKeyLength: The maximum possible length of a key in this tree
• fp: The node at the end of the fast path; the last internal node inserted to
• fp_ref: A reference to fp within the tree
• fp_path: An array of the internal nodes along the path from the root to fp; size is the maximum prefix length
• fp_path_ref: An array of references to the nodes of fp_path; size is the maximum prefix length
• fp_path_length: The current length of the fast path; can act as an index to the last item in fp_path/fp_path_ref
• fp_leaf: The last leaf inserted to the tree
• fp_depth: The prefix depth of fp

Functions

canLilInsert

Determines if a key fits on the end of the current fast path.

Arguments

• uint8_t key[]: The key of some value to insert

Algorithm

• If the root is null or a leaf (if the tree is empty or has one value) then return false.
  • There is not currently a fast path to insert to as there are no internal nodes.
• Extract the value of fp_leaf and use it to determine a corresponding key array.
• Compare that array to key using memcmp.
  • If they do not match at some point, they must belong at different parts of the tree and a fast path insert must not be viable. Return false.
  • Else, they must share a path and the fast path insert is viable. Return True.

insert (public)

Public-facing insert function that calls the recursive insert function.

Arguments

• uint8_t key[]: The key of the value to be inserted
• uintptr_t value: The value to be inserted

Algorithm

• If fp is not null, canLilInsert(key) returns true, and fp does not have enough children to fill its capacity, value can be inserted on the fast path.
• If inserting to the fast path, call insert(this, *fp_ref, fp_ref, key, fp_depth, value, maxPrefixLength, true).
  • Insert starting from fp instead of from root.
• Else, set fast path metadata to include only the root and call insert(this, root, &root, key, root prefix length, value, maxPrefixLength, true).
  • The new fast path will be built as this insert is processed so the relevant metadata needs to be set to just the root to prepare for this.
    • Set all values in fp_path and fp_path_ref but the first to be null.
    • Set fp_path_length to 1.
    • Set fp_depth to the length of the root prefix.
    • Set fp to be root.
    • Set fp_ref to be a reference to root.
    • Set fp_leaf to be null.
  • Then, perform an insertion starting at the root.

insertRecursive (private)

Private function that recursively traverses the tree and performs logic for inserting new values.

Arguments

• ArtNode* node: The internal node of the tree being inserted into in this call
• ArtNode** nodeRef: The pointer to node within the tree
• uint8_t key[]: The key of the value being inserted
• unsigned depth: The prefix depth of node
• uintptr_t value: The value being inserted
• bool firstCall: Indicates if this recursive call is the first in the series

Algorithm

• If node is null:
  • Create a new leaf for value and assign the value at nodeRef to this leaf.
  • Return.
  • No changes are made to the fast path as, if node is null, then the tree was previously empty and has no internal nodes to compose a fast path yet.
• If node is a leaf:
  • Create a new node4 with a prefix of the common sections of both key and the key of node.
  • Create a new leaf for value, then insert it and node into the new node4 as children.
  • Update the value referenced by nodeRef to be the new node4.
    • Since the current root is a leaf, it must be that this node4 will be the only internal node in the tree and thus must be the new root. nodeRef must be referencing the root in this case so root does not need to be directly modified.
  • Update fast path metadata.
    • Update fp to be root and fp_ref to be nodeRef.
    • Update the value of fp_path[0] to be root and fp_path_ref[0] to be nodeRef.
    • Set fp_path_length to 1.
    • Set fp_depth to be the length of the root prefix.
    • Set fp_leaf to be the leaf created from value.
  • Return.
• If node has a prefix:
  • If the prefix of node does not match the section of key corresponding to the current depth:
    • This condition would mean that key does not fit into the current node and cannot be inserted into it or one of its children. A new branch needs to be added to accommodate the new key.
    • Create a new node4 with a prefix of the common sections of both key and the key of node. Set the value of nodeRef to be the new node4.
    • Replace the prefix of node with its current prefix minus the section that is now the prefix of the new node4.
    • Create a new leaf for value, then insert it and node into the new node4 as children.
    • Update fast path metadata.
      • Update fp to be the new node4.
      • Update fp_ref to be nodeRef.
      • Update the value of fp_path[fp_path_length] to be fp and fp_path_ref[fp_path_length] to be fp_ref.
      • Increment fp_path_length by 1.
      • Increment fp_depth by the length of the new node4 prefix.
      • Set fp_leaf to be the leaf created from value.
    • Return.
  • Increment depth by the length of the prefix of node.
• If firstCall is false:
  • The first recursive call will always be to a node already on the end of the fast path. In order to avoid double-counting it on the fast path, only update the fast path on subsequent recursive calls in the series.
  • Update the fast path metadata.
    • Update fp to be node.
    • Update fp_ref to be nodeRef.
    • Update the value of fp_path[fp_path_length] to be fp and fp_path_ref[fp_path_length] to be fp_ref.
    • Increment fp_path_length by 1.
    • Increment fp_depth by the length of the node prefix.
• Check for a child internal node in node.
• If node has a child internal node (designated as "child"):
  • Call insertRecursive(this, child, reference to child, key, depth + 1, value, maxKeyLength, false).
  • Return.
• If node is an internal node and its prefix matches the corresponding portion of key then the leaf for value must belong on the same path as node. If this is true and node has no internal node children that key might possibly be inserted into then the leaf for value can only be inserted into node.
• Create a new leaf for value and set fp_leaf to be this leaf.
• Call insertNodeX(this, nodeRef, key[depth], fp_leaf) where X is the size of node (4, 16, 48, or 256).