You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by rn...@apache.org on 2020/07/23 18:21:58 UTC
[couchdb] 01/06: mutate node id of non-leaf,
non-root nodes on insert
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 295e8c577301b22418e33336f7b4949e94762778
Author: Robert Newson <rn...@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 cb5e805..418bd5e 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -509,9 +509,18 @@ split_child(Tx, #tree{} = Tree, #node{} = Parent0, #node{} = Child) ->
umerge(Tree, [{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) ->
@@ -535,7 +544,7 @@ insert_nonfull(Tx, #tree{} = Tree, #node{level = 0} = Node0, Key, Value) ->
members = umerge(Tree, [{Key, Value}], Node0#node.members)
},
set_node(Tx, Tree, 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),
@@ -555,16 +564,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(Tree, [Key, CurrentFirstKey]),
[_, NewLastKey] = sort(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, 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, Node3),
+ {Node3#node.id, reduce_node(Tree, Node3)}.
%% @doc Deletes an entry from the ebtree