couchdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From rnew...@apache.org
Subject [couchdb] 01/07: mutate node id of non-leaf, non-root nodes on insert
Date Thu, 03 Sep 2020 17:42:22 GMT
This is an automated email from the ASF dual-hosted git repository.

rnewson pushed a commit to branch prototype/fdb-layer-ebtree-immutable
in repository https://gitbox.apache.org/repos/asf/couchdb.git

commit 43d6adcc3234562a310aac4600fdcabe20b6e3a2
Author: Robert Newson <rnewson@apache.org>
AuthorDate: Thu Jul 23 19:00:48 2020 +0100

    mutate node id of non-leaf, non-root nodes on insert
---
 src/ebtree/src/ebtree.erl | 32 +++++++++++++++++++++++++-------
 1 file changed, 25 insertions(+), 7 deletions(-)

diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index 536d3b1..639406e 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -549,9 +549,18 @@ split_child(Tx, #tree{} = Tree, #node{} = Parent0, #node{} = Child) ->
                 umerge_members(Tree, Parent0#node.level, [{FirstRightKey, LastRightKey, RightId,
RightReduction}],
                     lists:keydelete(Child#node.id, 3, Parent0#node.members)))
     },
+    Parent2 =
+        if Parent1#node.id == ?NODE_ROOT_ID ->
+            Parent1;
+        Parent0#node.members == Parent1#node.members ->
+            Parent1;
+        true ->
+            clear_node(Tx, Tree, Parent1),
+            Parent1#node{id = new_node_id(Tx, Tree)}
+    end,
     clear_node(Tx, Tree, Child),
-    set_nodes(Tx, Tree, [LeftChild, RightChild, Parent1]),
-    {Parent1, LeftChild, RightChild}.
+    set_nodes(Tx, Tree, [LeftChild, RightChild, Parent2]),
+    {Parent2, LeftChild, RightChild}.
 
 
 update_prev_neighbour(_Tx, #tree{} = _Tree, #node{prev = undefined} = _Node) ->
@@ -575,7 +584,7 @@ insert_nonfull(Tx, #tree{} = Tree, #node{level = 0} = Node0, Key, Value)
->
         members = umerge_members(Tree, 0, [{Key, Value}], Node0#node.members)
     },
     set_node(Tx, Tree, Node0, Node1),
-    reduce_node(Tree, Node1);
+    {Node1#node.id, reduce_node(Tree, Node1)};
 
 insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
     ChildId0 = find_child_id(Tree, Node0, Key),
@@ -595,16 +604,25 @@ insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
             {Node0, Child0}
     end,
     ChildId1 = Child1#node.id,
-    NewReduction = insert_nonfull(Tx, Tree, Child1, Key, Value),
+    {ChildId2, NewReduction} = insert_nonfull(Tx, Tree, Child1, Key, Value),
     {CurrentFirstKey, CurrentLastKey, ChildId1, _OldReduction} = lists:keyfind(ChildId1,
3, Node1#node.members),
     [NewFirstKey, _] = sort_keys(Tree, [Key, CurrentFirstKey]),
     [_, NewLastKey] = sort_keys(Tree, [Key, CurrentLastKey]),
     Node2 = Node1#node{
         members = lists:keyreplace(ChildId1, 3, Node1#node.members,
-            {NewFirstKey, NewLastKey, ChildId1, NewReduction})
+            {NewFirstKey, NewLastKey, ChildId2, NewReduction})
     },
-    set_node(Tx, Tree, Node0, Node2),
-    reduce_node(Tree, Node2).
+    Node3 = if
+        Node2#node.id == ?NODE_ROOT_ID ->
+            Node2;
+        Node0#node.members == Node2#node.members ->
+            Node2;
+        true ->
+            clear_node(Tx, Tree, Node2),
+            Node2#node{id = new_node_id(Tx, Tree)}
+    end,
+    set_node(Tx, Tree, Node0, Node3),
+    {Node3#node.id, reduce_node(Tree, Node3)}.
 
 
 %% @doc Deletes an entry from the ebtree


Mime
View raw message