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:57 UTC
[couchdb] branch prototype/fdb-layer-ebtree-immutable created (now
d959efb)
This is an automated email from the ASF dual-hosted git repository.
rnewson pushed a change to branch prototype/fdb-layer-ebtree-immutable
in repository https://gitbox.apache.org/repos/asf/couchdb.git.
at d959efb add cache test
This branch includes the following new commits:
new 295e8c5 mutate node id of non-leaf, non-root nodes on insert
new 8190602 mutate node id of non-leaf, non-root nodes on delete
new be55a65 consolidate id mutation logic into one function
new f21324e pluggable caching of inner nodes
new 81e0704 convert node ids to uuids
new d959efb add cache test
The 6 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
[couchdb] 06/06: add cache test
Posted by rn...@apache.org.
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 d959efb8f5c9578c5f6a802a09e7813aaac990a6
Author: Robert Newson <rn...@apache.org>
AuthorDate: Thu Jul 23 19:16:25 2020 +0100
add cache test
---
src/ebtree/src/ebtree.erl | 18 ++++++++++++++++++
1 file changed, 18 insertions(+)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index bbe5728..decb81e 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -1392,6 +1392,24 @@ custom_collation_reverse_range_test_() ->
end}.
+cache_test_() ->
+ {spawn, [fun() ->
+ Db = erlfdb_util:get_test_db([empty]),
+ CacheFun = fun
+ (set, Node) ->
+ erlang:put(Node#node.id, Node);
+ (clear, Node) ->
+ erlang:erase(Node#node.id);
+ (get, Id) ->
+ erlang:get(Id)
+ end,
+ Tree = open(Db, <<1,2,3>>, 4, [{cache_fun, CacheFun}]),
+ [ebtree:insert(Db, Tree, I, I) || I <- lists:seq(1, 16)],
+ ?assertEqual({1, 1}, ebtree:lookup(Db, Tree, 1)),
+ NodeCache = [V || {_K, V} <- erlang:get(), is_record(V, node)],
+ ?assertEqual(3, length(NodeCache))
+ end]}.
+
msec(Native) ->
erlang:max(1, erlang:convert_time_unit(Native, native, millisecond)).
[couchdb] 04/06: pluggable caching of inner nodes
Posted by rn...@apache.org.
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 f21324e02d9934f72462ed00f0afde4c9cb9f29d
Author: Robert Newson <rn...@apache.org>
AuthorDate: Thu Jul 23 19:10:04 2020 +0100
pluggable caching of inner nodes
---
src/ebtree/src/ebtree.erl | 60 ++++++++++++++++++++++++++++++++++++++++-------
1 file changed, 52 insertions(+), 8 deletions(-)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index b6ae91d..08ca2bc 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -45,7 +45,8 @@
max,
collate_fun,
reduce_fun,
- encode_fun
+ encode_fun,
+ cache_fun
}).
-define(META, 0).
@@ -82,12 +83,14 @@ open(Db, Prefix, Order, Options) when is_binary(Prefix), is_integer(Order), Orde
ReduceFun = proplists:get_value(reduce_fun, Options, fun reduce_noop/2),
CollateFun = proplists:get_value(collate_fun, Options, fun collate_raw/2),
EncodeFun = proplists:get_value(encode_fun, Options, fun encode_erlang/3),
+ CacheFun = proplists:get_value(cache_fun, Options, fun cache_noop/2),
Tree = #tree{
prefix = Prefix,
reduce_fun = ReduceFun,
collate_fun = CollateFun,
- encode_fun = EncodeFun
+ encode_fun = EncodeFun,
+ cache_fun = CacheFun
},
erlfdb:transactional(Db, fun(Tx) ->
@@ -735,10 +738,17 @@ meta_key(Prefix, MetaKey) when is_binary(Prefix) ->
%% node persistence functions
get_node(Tx, #tree{} = Tree, Id) ->
- Key = node_key(Tree#tree.prefix, Id),
- Future = erlfdb:get(Tx, Key),
- Value = erlfdb:wait(Future),
- decode_node(Tree, Id, Key, Value).
+ case cache_fun(Tree, get, Id) of
+ undefined ->
+ Key = node_key(Tree#tree.prefix, Id),
+ Future = erlfdb:get(Tx, Key),
+ Value = erlfdb:wait(Future),
+ Node = decode_node(Tree, Id, Key, Value),
+ cache_fun(Tree, set, Node),
+ Node;
+ #node{} = Node ->
+ Node
+ end.
clear_nodes(Tx, #tree{} = Tree, Nodes) ->
@@ -748,8 +758,9 @@ clear_nodes(Tx, #tree{} = Tree, Nodes) ->
clear_node(Tx, #tree{} = Tree, #node{} = Node) ->
- Key = node_key(Tree#tree.prefix, Node#node.id),
- erlfdb:clear(Tx, Key).
+ Key = node_key(Tree#tree.prefix, Node#node.id),
+ cache_fun(Tree, clear, Node),
+ erlfdb:clear(Tx, Key).
set_nodes(Tx, #tree{} = Tree, Nodes) ->
@@ -762,6 +773,7 @@ set_node(Tx, #tree{} = Tree, #node{} = Node) ->
validate_node(Tree, Node),
Key = node_key(Tree#tree.prefix, Node#node.id),
Value = encode_node(Tree, Key, Node),
+ cache_fun(Tree, set, Node),
erlfdb:set(Tx, Key, Value).
@@ -950,6 +962,38 @@ encode_erlang(encode, _Key, Value) ->
encode_erlang(decode, _Key, Value) ->
binary_to_term(Value, [safe]).
+%% cache functions
+
+cache_noop(set, _) ->
+ ok;
+cache_noop(clear, _) ->
+ ok;
+cache_noop(get, _) ->
+ undefined.
+
+
+cache_fun(#tree{} = Tree, Action, #node{} = Node) when Action == set; Action == clear ->
+ #tree{cache_fun = CacheFun} = Tree,
+ NodeIsCacheable = node_is_cacheable(Node),
+ if
+ NodeIsCacheable andalso CacheFun /= undefined ->
+ CacheFun(Action, Node);
+ true ->
+ ok
+ end;
+
+cache_fun(#tree{} = _Tree, get, ?NODE_ROOT_ID) ->
+ undefined;
+
+cache_fun(#tree{} = Tree, get, Id) ->
+ #tree{cache_fun = CacheFun} = Tree,
+ if
+ CacheFun /= undefined ->
+ CacheFun(get, Id);
+ true ->
+ undefined
+ end.
+
%% private functions
init_order(#tree{} = Tree, Order)
[couchdb] 01/06: mutate node id of non-leaf,
non-root nodes on insert
Posted by rn...@apache.org.
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
[couchdb] 02/06: mutate node id of non-leaf,
non-root nodes on delete
Posted by rn...@apache.org.
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 8190602097de859ce364503c831f2777c45b17f9
Author: Robert Newson <rn...@apache.org>
AuthorDate: Thu Jul 23 19:01:02 2020 +0100
mutate node id of non-leaf, non-root nodes on delete
---
src/ebtree/src/ebtree.erl | 26 ++++++++++++++++++++++----
1 file changed, 22 insertions(+), 4 deletions(-)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index 418bd5e..cf8ac91 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -643,20 +643,38 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
end, Members2, NewNodes),
Parent1 = Parent0#node{
- %% TODO change id
members = Members3
},
+ 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_nodes(Tx, Tree, [Child0, Sibling]),
set_nodes(Tx, Tree, NewNodes),
- Parent1;
+ Parent2;
false ->
set_node(Tx, Tree, Child1),
{_OldFirstKey, _OldLastKey, ChildId0, _OldReduction} = lists:keyfind(ChildId0, 3, Parent0#node.members),
- Parent0#node{
+ Parent1 = Parent0#node{
members = lists:keyreplace(ChildId0, 3, Parent0#node.members,
{first_key(Child1), last_key(Child1), Child1#node.id, reduce_node(Tree, Child1)})
- }
+ },
+ 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,
+ Parent2
end.
[couchdb] 03/06: consolidate id mutation logic into one function
Posted by rn...@apache.org.
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 be55a65560581e524e51b7303e5cba7d9306d64a
Author: Robert Newson <rn...@apache.org>
AuthorDate: Thu Jul 23 19:02:24 2020 +0100
consolidate id mutation logic into one function
---
src/ebtree/src/ebtree.erl | 64 +++++++++++++++++++----------------------------
1 file changed, 26 insertions(+), 38 deletions(-)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index cf8ac91..b6ae91d 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -509,15 +509,7 @@ 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,
+ Parent2 = new_node_id_if_cacheable(Tx, Tree, Parent0, Parent1),
clear_node(Tx, Tree, Child),
set_nodes(Tx, Tree, [LeftChild, RightChild, Parent2]),
{Parent2, LeftChild, RightChild}.
@@ -572,15 +564,7 @@ insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
members = lists:keyreplace(ChildId1, 3, Node1#node.members,
{NewFirstKey, NewLastKey, ChildId2, NewReduction})
},
- 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,
+ Node3 = new_node_id_if_cacheable(Tx, Tree, Node0, Node2),
set_node(Tx, Tree, Node3),
{Node3#node.id, reduce_node(Tree, Node3)}.
@@ -645,16 +629,7 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
Parent1 = Parent0#node{
members = Members3
},
- 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,
-
+ Parent2 = new_node_id_if_cacheable(Tx, Tree, Parent0, Parent1),
clear_nodes(Tx, Tree, [Child0, Sibling]),
set_nodes(Tx, Tree, NewNodes),
Parent2;
@@ -665,16 +640,7 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
members = lists:keyreplace(ChildId0, 3, Parent0#node.members,
{first_key(Child1), last_key(Child1), Child1#node.id, reduce_node(Tree, Child1)})
},
- 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,
- Parent2
+ new_node_id_if_cacheable(Tx, Tree, Parent0, Parent1)
end.
@@ -1013,6 +979,28 @@ last_key(Members) when is_list(Members) ->
end.
+new_node_id_if_cacheable(Tx, #tree{} = Tree, #node{} = Old, #node{} = New) ->
+ MembersChanged = Old#node.members /= New#node.members,
+ NodeIsCacheable = node_is_cacheable(New),
+ if
+ MembersChanged andalso NodeIsCacheable ->
+ clear_node(Tx, Tree, New),
+ New#node{id = new_node_id(Tx, Tree)};
+ true ->
+ New
+ end.
+
+
+node_is_cacheable(#node{id = ?NODE_ROOT_ID}) ->
+ false;
+
+node_is_cacheable(#node{level = 0}) ->
+ false;
+
+node_is_cacheable(#node{}) ->
+ true.
+
+
new_node_id(Tx, Tree) ->
NextId = get_meta(Tx, Tree, ?META_NEXT_ID),
set_meta(Tx, Tree, ?META_NEXT_ID, NextId + 1),
[couchdb] 05/06: convert node ids to uuids
Posted by rn...@apache.org.
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 81e0704f4cc1e6f5a30779d8e28d74898edd28ed
Author: Robert Newson <rn...@apache.org>
AuthorDate: Thu Jul 23 19:15:33 2020 +0100
convert node ids to uuids
---
src/ebtree/src/ebtree.erl | 50 +++++++++++++++++++++++++++--------------------
1 file changed, 29 insertions(+), 21 deletions(-)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index 08ca2bc..bbe5728 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -51,10 +51,9 @@
-define(META, 0).
-define(META_ORDER, 0).
--define(META_NEXT_ID, 1).
-define(NODE, 1).
--define(NODE_ROOT_ID, 0).
+-define(NODE_ROOT_ID, <<0>>).
-define(underflow(Tree, Node), Tree#tree.min > length(Node#node.members)).
-define(at_min(Tree, Node), Tree#tree.min == length(Node#node.members)).
@@ -98,7 +97,6 @@ open(Db, Prefix, Order, Options) when is_binary(Prefix), is_integer(Order), Orde
not_found ->
erlfdb:clear_range_startswith(Tx, Prefix),
set_meta(Tx, Tree, ?META_ORDER, Order),
- set_meta(Tx, Tree, ?META_NEXT_ID, 1),
set_node(Tx, Tree, #node{id = ?NODE_ROOT_ID}),
init_order(Tree, Order);
ActualOrder when is_integer(ActualOrder) ->
@@ -455,7 +453,7 @@ insert(Db, #tree{} = Tree, Key, Value) ->
Root0 = get_node(Tx, Tree, ?NODE_ROOT_ID),
case ?is_full(Tree, Root0) of
true ->
- OldRoot = Root0#node{id = new_node_id(Tx, Tree)},
+ OldRoot = Root0#node{id = new_node_id()},
FirstKey = first_key(OldRoot),
LastKey = last_key(OldRoot),
Root1 = #node{
@@ -474,8 +472,8 @@ insert(Db, #tree{} = Tree, Key, Value) ->
split_child(Tx, #tree{} = Tree, #node{} = Parent0, #node{} = Child) ->
{LeftMembers, RightMembers} = lists:split(Tree#tree.min, Child#node.members),
- LeftId = new_node_id(Tx, Tree),
- RightId = new_node_id(Tx, Tree),
+ LeftId = new_node_id(),
+ RightId = new_node_id(),
LeftChild = remove_pointers_if_not_leaf(#node{
id = LeftId,
@@ -610,12 +608,12 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
Sibling = get_node(Tx, Tree, SiblingId),
NewNodes = case ?at_min(Tree, Sibling) of
true ->
- Merged = merge(Tx, Tree, Child1, Sibling),
+ Merged = merge(Tree, Child1, Sibling),
update_prev_neighbour(Tx, Tree, Merged),
update_next_neighbour(Tx, Tree, Merged),
[Merged];
false ->
- {Left, Right} = rebalance(Tx, Tree, Child1, Sibling),
+ {Left, Right} = rebalance(Tree, Child1, Sibling),
update_prev_neighbour(Tx, Tree, Left),
update_next_neighbour(Tx, Tree, Right),
[Left, Right]
@@ -647,11 +645,11 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
end.
-merge(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
+merge(#tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
[Left, Right] = sort(Tree, [Node1, Node2]),
#node{
- id = new_node_id(Tx, Tree),
+ id = new_node_id(),
level = Level,
prev = Left#node.prev,
next = Right#node.next,
@@ -659,14 +657,14 @@ merge(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = N
}.
-rebalance(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
+rebalance(#tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
[Left0, Right0] = sort(Tree, [Node1, Node2]),
Members = lists:append(Left0#node.members, Right0#node.members),
{LeftMembers, RightMembers} = lists:split(length(Members) div 2, Members),
- Left1Id = new_node_id(Tx, Tree),
- Right1Id = new_node_id(Tx, Tree),
+ Left1Id = new_node_id(),
+ Right1Id = new_node_id(),
Left1 = remove_pointers_if_not_leaf(Left0#node{
id = Left1Id,
@@ -777,7 +775,7 @@ set_node(Tx, #tree{} = Tree, #node{} = Node) ->
erlfdb:set(Tx, Key, Value).
-node_key(Prefix, Id) when is_binary(Prefix), is_integer(Id) ->
+node_key(Prefix, Id) when is_binary(Prefix), is_binary(Id) ->
erlfdb_tuple:pack({?NODE, Id}, Prefix).
@@ -1029,7 +1027,7 @@ new_node_id_if_cacheable(Tx, #tree{} = Tree, #node{} = Old, #node{} = New) ->
if
MembersChanged andalso NodeIsCacheable ->
clear_node(Tx, Tree, New),
- New#node{id = new_node_id(Tx, Tree)};
+ New#node{id = new_node_id()};
true ->
New
end.
@@ -1045,10 +1043,8 @@ node_is_cacheable(#node{}) ->
true.
-new_node_id(Tx, Tree) ->
- NextId = get_meta(Tx, Tree, ?META_NEXT_ID),
- set_meta(Tx, Tree, ?META_NEXT_ID, NextId + 1),
- NextId.
+new_node_id() ->
+ crypto:strong_rand_bytes(16).
%% remove prev/next pointers for nonleaf nodes
@@ -1059,10 +1055,22 @@ remove_pointers_if_not_leaf(#node{} = Node) ->
Node#node{prev = undefined, next = undefined}.
+print_node(#node{level = 0} = Node) ->
+ io:format("#node{id = ~s, level = ~w, prev = ~s, next = ~s, members = ~w}~n~n",
+ [b64(Node#node.id), Node#node.level, b64(Node#node.prev), b64(Node#node.next),
+ Node#node.members]);
+
print_node(#node{} = Node) ->
- io:format("#node{id = ~w, level = ~w, prev = ~w, next = ~w, members = ~w}~n~n",
- [Node#node.id, Node#node.level, Node#node.prev, Node#node.next, Node#node.members]).
+ io:format("#node{id = ~s, level = ~w, prev = ~s, next = ~s, members = ~s}~n~n",
+ [base64:encode(Node#node.id), Node#node.level, b64(Node#node.prev), b64(Node#node.next),
+ [io_lib:format("{~w, ~w, ~s, ~w}, ", [F, L, b64(P), R]) || {F, L, P, R} <- Node#node.members]]).
+
+
+b64(undefined) ->
+ undefined;
+b64(Bin) ->
+ base64:encode(Bin).
%% tests