diff options
| author | Robert Newson <rnewson@apache.org> | 2020-07-11 15:56:21 +0100 |
|---|---|---|
| committer | GitHub Enterprise <noreply@github.ibm.com> | 2020-07-11 15:56:21 +0100 |
| commit | 6e507b74b9a36ce56da80b64a2edad60d8712449 (patch) | |
| tree | 3f3a98f9a1565a3706a28b573fd8f051216c7f2f | |
| parent | 2818bce6d9f55fd732cd6cf8d1d588de771e5fd5 (diff) | |
| parent | 7485892beb99b8ff793e4796322ef88bfd4b064d (diff) | |
| download | couchdb-6e507b74b9a36ce56da80b64a2edad60d8712449.tar.gz | |
Merge pull request #21 from cloudant/remove_pointers_from_non_leaf
Remove pointers from non leaf
| -rw-r--r-- | src/ebtree.erl | 13 |
1 files changed, 9 insertions, 4 deletions
diff --git a/src/ebtree.erl b/src/ebtree.erl index a2ad0224c..64a6257cb 100644 --- a/src/ebtree.erl +++ b/src/ebtree.erl @@ -526,16 +526,16 @@ rebalance(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} Left1Id = new_node_id(Tx, Tree), Right1Id = new_node_id(Tx, Tree), - Left1 = Left0#node{ + Left1 = remove_pointers_if_not_leaf(Left0#node{ id = Left1Id, next = Right1Id, members = LeftMembers - }, - Right1 = Right0#node{ + }), + Right1 = remove_pointers_if_not_leaf(Right0#node{ id = Right1Id, prev = Left1Id, members = RightMembers - }, + }), {Left1, Right1}. @@ -666,6 +666,7 @@ validate_tree(Tx, #tree{} = Tree, [{_F, _L, P, _R} | Rest]) -> validate_node(#tree{} = Tree, #node{} = Node) -> NumKeys = length(Node#node.members), + IsLeaf = Node#node.level =:= 0, IsRoot = ?NODE_ROOT_ID == Node#node.id, OutOfOrder = Node#node.members /= sort(Tree, Node#node.members), Duplicates = Node#node.members /= usort(Tree, Node#node.members), @@ -676,6 +677,10 @@ validate_node(#tree{} = Tree, #node{} = Node) -> erlang:error({too_few_keys, Node}); NumKeys > Tree#tree.max -> erlang:error({too_many_keys, Node}); + not IsLeaf andalso Node#node.prev /= undefined -> + erlang:error({non_leaf_with_prev, Node}); + not IsLeaf andalso Node#node.next /= undefined -> + erlang:error({non_leaf_with_next, Node}); OutOfOrder -> erlang:error({out_of_order, Node}); Duplicates -> |