diff options
author | Robert Newson <rnewson@apache.org> | 2020-07-07 18:05:19 +0100 |
---|---|---|
committer | GitHub Enterprise <noreply@github.ibm.com> | 2020-07-07 18:05:19 +0100 |
commit | 44e99049443d6ef9c0e91e1f3b87b752ab6b63a1 (patch) | |
tree | 5af1ee1ab5072bc0bd75146afde0920f0ff34662 | |
parent | ee39d56cbdc86f4d1b818c13ddb9ef588ecfafd8 (diff) | |
parent | 382096d082bb92d34baea9969750dac074bbc9b2 (diff) | |
download | couchdb-44e99049443d6ef9c0e91e1f3b87b752ab6b63a1.tar.gz |
Merge pull request #18 from cloudant/min-max
Introduce min and max keys for open ranges
-rw-r--r-- | src/ebtree.erl | 39 |
1 files changed, 37 insertions, 2 deletions
diff --git a/src/ebtree.erl b/src/ebtree.erl index 12861dadc..c481e5a40 100644 --- a/src/ebtree.erl +++ b/src/ebtree.erl @@ -3,6 +3,8 @@ -export([ open/3, open/4, + min/0, + max/0, insert/4, delete/3, lookup/3, @@ -49,6 +51,10 @@ -define(at_min(Tree, Node), Tree#tree.min == length(Node#node.members)). -define(is_full(Tree, Node), Tree#tree.max == length(Node#node.members)). +%% two special 1-bit bitstrings that cannot appear in valid keys. +-define(MIN, <<0:1>>). +-define(MAX, <<1:1>>). + open(Db, Prefix, Order) -> open(Db, Prefix, Order, []). @@ -77,6 +83,13 @@ open(Db, Prefix, Order, Options) when is_binary(Prefix), is_integer(Order), Orde }. +min() -> + ?MIN. + + +max() -> + ?MAX. + %% lookup lookup(Db, #tree{} = Tree, Key) -> @@ -203,7 +216,7 @@ do_reduce(#tree{} = Tree, MapValues, ReduceValues) when is_list(MapValues), is_l %% group reduce - produces reductions for contiguous keys in the same group. group_reduce(Db, #tree{} = Tree, StartKey, EndKey, GroupKeyFun) -> - NoGroupYet = erlang:make_ref(), + NoGroupYet = ?MIN, Fun = fun ({visit, Key, Value}, {CurrentGroup, GroupAcc, MapAcc, ReduceAcc}) -> AfterEnd = greater_than(Tree, Key, EndKey), @@ -299,6 +312,12 @@ reverse_range(Tx, #tree{} = Tree, #node{} = Node, StartKey, EndKey, Fun, Acc) -> %% insert +insert(_Db, #tree{} = _Tree, ?MIN, _Value) -> + erlang:error(min_not_allowed); + +insert(_Db, #tree{} = _Tree, ?MAX, _Value) -> + erlang:error(max_not_allowed); + insert(Db, #tree{} = Tree, Key, Value) -> erlfdb:transactional(Db, fun(Tx) -> Root0 = get_node(Tx, Tree, ?NODE_ROOT_ID), @@ -779,6 +798,18 @@ less_than(#tree{} = Tree, A, B) -> less_than_or_equal(Tree, A, B). +less_than_or_equal(#tree{} = _Tree, ?MIN, _B) -> + true; + +less_than_or_equal(#tree{} = _Tree, _A, ?MIN) -> + false; + +less_than_or_equal(#tree{} = _Tree, ?MAX, _B) -> + false; + +less_than_or_equal(#tree{} = _Tree, _A, ?MAX) -> + true; + less_than_or_equal(#tree{} = Tree, A, B) -> #tree{collate_fun = CollateFun} = Tree, CollateFun(A, B). @@ -998,7 +1029,11 @@ group_reduce_test_() -> lists:foreach(fun(Key) -> insert(Db, Tree, [Key rem 4, Key rem 3, Key], Key) end, Keys), [ ?_test(?assertEqual([{[1, 0], 408}, {[1, 1], 441}, {[1, 2], 376}], - group_reduce(Db, Tree, [1], [2], GroupKeyFun))) + group_reduce(Db, Tree, [1], [2], GroupKeyFun))), + + ?_test(?assertEqual([{[0,0],432}, {[0,1],468}, {[0,2],400}, {[1,0],408}, {[1,1],441}, {[1,2],376}, + {[2,0],384}, {[2,1],416}, {[2,2],450}, {[3,0],459}, {[3,1],392}, {[3,2],424}], + group_reduce(Db, Tree, ebtree:min(), ebtree:max(), GroupKeyFun))) ]. |