CouchProjects/CouchDb/couch_btree.erl

   1 %% CouchDb
   2 %% Copyright (C) 2006  Damien Katz
   3 %%
   4 %% This program is free software; you can redistribute it and/or
   5 %% modify it under the terms of the GNU General Public License
   6 %% as published by the Free Software Foundation; either version 2
   7 %% of the License, or (at your option) any later version.
   8 %%
   9 %% This program is distributed in the hope that it will be useful,
  10 %% but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 %% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 %% GNU General Public License for more details.
  13 %%
  14 %% You should have received a copy of the GNU General Public License
  15 %% along with this program; if not, write to the Free Software
  16 %% Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  17
  18 -module(couch_btree).
  19
  20 -export([open/2, open/3, query_modify/4, add_remove/3, foldl/3, foldl/4]).
  21 -export([foldr/3, foldr/4, fold/4, fold/5, lookup_single/2, row_count/1]).
  22 -export([lookup/2, get_state/1, query_compute_if_missing/3, test/1, test/0]).
  23
  24
  25
  26 -define(CHUNK_THRESHOLD, 16#fff).
  27
  28
  29 -record(btree,
  30         {
  31         fd,
  32         root,
  33         less_fun = fun(A,B) -> A < B end
  34         }).
  35
  36
  37 % pass in 'nil' for State if a new Btree.
  38 open(State, Fd) ->
  39         {ok, #btree{root=State, fd=Fd}}.
  40
  41 open(State, Fd, LessFun) ->
  42         {ok, #btree{root=State, fd=Fd, less_fun=LessFun}}.
  43
  44 get_state(#btree{root=Root}) ->
  45         Root.
  46
  47 row_count(#btree{root=nil}) ->
  48         0;
  49 row_count(#btree{root={_RootPointer, Count}}) ->
  50         Count.
  51
  52 foldl(Bt, Fun, Acc) ->
  53         fold(Bt, fwd, Fun, Acc).
  54
  55 foldl(Bt, Key, Fun, Acc) ->
  56         fold(Bt, Key, fwd, Fun, Acc).
  57
  58 foldr(Bt, Fun, Acc) ->
  59         fold(Bt, rev, Fun, Acc).
  60
  61 foldr(Bt, Key, Fun, Acc) ->
  62         fold(Bt, Key, rev, Fun, Acc).
  63
  64 % wraps a 2 arity function with the proper 3 arity function
  65 convert_fun_arity(Fun) ->
  66         case erlang:fun_info(Fun, arity) of
  67         {arity, 2} ->
  68                 fun(KV, _Offset, AccIn) -> Fun(KV, AccIn) end;
  69         {arity, 3} ->
  70                 Fun    % Already arity 3
  71         end.
  72
  73 fold(Bt, Dir, Fun, Acc) ->
  74         {_ContinueFlag, Acc2} = stream_node(Bt, 0, Bt#btree.root, nil, Dir, convert_fun_arity(Fun), Acc),
  75         {ok, Acc2}.
  76
  77 fold(Bt, Key, Dir, Fun, Acc) ->
  78         {_ContinueFlag, Acc2} = stream_node(Bt, 0, Bt#btree.root, Key, Dir, convert_fun_arity(Fun), Acc),
  79         {ok, Acc2}.
  80
  81 add_remove(Bt, InsertKeyValues, RemoveKeys) ->
  82         {Result, [], Bt2} = query_modify(Bt, [], InsertKeyValues, RemoveKeys),
  83         {Result, Bt2}.
  84
  85 query_compute_if_missing(Bt, Key, ComputeValueFun) ->
  86         {ok, [Code, {Key, Result}]} = query_modify(Bt, [], [], [], [{Key, ComputeValueFun}]),
  87         {Code, Result}.
  88
  89 query_modify(Bt, LookupKeys, InsertKeyValues, RemoveKeys) ->
  90         query_modify(Bt, LookupKeys, InsertKeyValues, RemoveKeys, []).
  91
  92 query_modify(Bt, LookupKeys, InsertKeyValues, RemoveKeys, MissingInsertKeyFuns) ->
  93         #btree{root=Root, less_fun=Less} = Bt,
  94         InsertActions = [{insert, Key, Value} || {Key, Value} <- InsertKeyValues],
  95         RemoveActions = [{remove, Key, nil} || Key <- RemoveKeys],
  96         FetchActions = [{fetch, Key, nil} || Key <- LookupKeys],
  97         MissingInsertActions = [{missing_insert, Key, Fun} || {Key, Fun} <- MissingInsertKeyFuns],
  98         SortFun = fun({OpA,A,_},{OpB,B,_}) ->
  99                         case Less(A, B) of
 100                         true ->
 101                                 true;
 102                         false ->
 103                                 case Less(B, A) of
 104                                 true ->
 105                                         false;
 106                                 false ->
 107                                         % A and B are equal, sort by op. fetch < remove < insert < missing_insert
 108                                         OpIntFunc = fun(Op) ->
 109                                                         case Op of
 110                                                                 fetch -> 1;
 111                                                                 remove -> 2;
 112                                                                 insert -> 3;
 113                                                                 missing_insert -> 4
 114                                                         end
 115                                                 end,
 116                                         OpIntFunc(OpA) < OpIntFunc(OpB)
 117                                 end
 118                         end
 119                 end,
 120         Actions = lists:sort(SortFun, lists:append([InsertActions, RemoveActions, FetchActions, MissingInsertActions])),
 121         {ok, KeyPointers, QueryResults, Bt2} = modify_node(Bt, Root, Actions, []),
 122         {ok, NewRoot, Bt3} = complete_root(Bt2, KeyPointers),
 123         {ok, QueryResults, Bt3#btree{root=NewRoot}}.
 124
 125 lookup_single(Bt, Key) ->
 126         {ok, [{Status, {Key, Value}}]} = lookup(Bt, [Key]),
 127         case Status of
 128         ok ->
 129                 {ok, Value};
 130         not_found ->
 131                 not_found
 132         end.
 133
 134 lookup(Bt, Keys) ->
 135         #btree{root=Root,less_fun=Less} = Bt,
 136         SortedKeys = lists:sort(Less, Keys),
 137         {ok, SortedResults} = lookup(Bt, Root, SortedKeys),
 138         % We want to return the results in the same order as the keys were input
 139         % but we may have changed the order when we sorted. So we need to put the
 140         % order back into the results.
 141         KeyDict = dict:from_list(SortedResults),
 142         Results =
 143         lists:map(fun(Key) ->
 144                         {ok, {Result, Value}} = dict:find(Key, KeyDict),
 145                         {Result, {Key, Value}}
 146                 end,
 147                 Keys),
 148         {ok, Results}.
 149
 150 lookup(_Bt, nil, Keys) ->
 151         {ok, [{Key, {not_found, nil}} || Key <- Keys]};
 152 lookup(Bt, {Pointer, _Count}, Keys) ->
 153         {ok, {NodeType, NodeList}} = couch_file:pread_term(Bt#btree.fd, Pointer),
 154         case NodeType of
 155         kp_node ->
 156                 {ok, NewResults} = lookup_kpnode(Bt, NodeList, Keys, []);
 157         kv_node ->
 158                 {ok, NewResults} = lookup_kvnode(Bt, NodeList, Keys, [])
 159         end,
 160         {ok, NewResults}.
 161
 162
 163 lookup_kpnode(_Bt, [], Keys, Output) ->
 164         {ok, lists:reverse(Output, [{Key, {not_found, nil}} || Key <- Keys])};
 165
 166 lookup_kpnode(_Bt, _KPs, [], Output) ->
 167         {ok, lists:reverse(Output)};
 168
 169 lookup_kpnode(Bt, [{Key, PointerInfo} | RestKPs], LookupKeys, Output) ->
 170         LessFun = Bt#btree.less_fun,
 171         % Split the Keys into two lists, queries of values less
 172         % than equals, and greater than the current key
 173         SplitFun = fun(LookupKey) -> not LessFun(Key, LookupKey) end,
 174         case lists:splitwith(SplitFun, LookupKeys) of
 175         {[], GreaterQueries} ->
 176                 lookup_kpnode(Bt, RestKPs, GreaterQueries, Output);
 177         {LessEqQueries, GreaterQueries} ->
 178                 {ok, Results} = lookup(Bt, PointerInfo, LessEqQueries),
 179                 lookup_kpnode(Bt, RestKPs, GreaterQueries, lists:reverse(Results, Output))
 180         end.
 181
 182
 183
 184 lookup_kvnode(_Bt, _KVs, [], Output) ->
 185         {ok, lists:reverse(Output)};
 186 lookup_kvnode(_Bt, [], Keys, Output) ->
 187         % keys not found
 188         {ok, lists:reverse(Output, [{Key, {not_found, nil}} || Key <- Keys])};
 189 lookup_kvnode(Bt, [{Key, Value} | RestKVs], [LookupKey | RestLookupKeys], Output) ->
 190         LessFun = Bt#btree.less_fun,
 191         case LessFun(LookupKey, Key) of
 192         true ->
 193                 lookup_kvnode(Bt, [{Key, Value} | RestKVs], RestLookupKeys, [{LookupKey, {not_found, nil}} | Output]);
 194         false ->
 195                 case LessFun(Key, LookupKey) of
 196                 true ->
 197                         % LookupKey is greater than Key
 198                         lookup_kvnode(Bt, RestKVs, [LookupKey | RestLookupKeys], Output);
 199                 false ->
 200                         % LookupKey is equal to Key
 201                         lookup_kvnode(Bt, RestKVs, RestLookupKeys, [{LookupKey, {ok, Value}} | Output])
 202                 end
 203         end.
 204
 205
 206 complete_root(Bt, []) ->
 207         {ok, nil, Bt};
 208 complete_root(Bt, [{_Key, PointerInfo}])->
 209         {ok, PointerInfo, Bt};
 210 complete_root(Bt, KPs) ->
 211         {ok, ResultKeyPointers, Bt2} = write_node(Bt, kp_node, KPs),
 212         complete_root(Bt2, ResultKeyPointers).
 213
 214 %%%%%%%%%%%%% The chunkify function sucks!
 215 %%%%%%%%%%%%% Could be much more intelligent about sizing the blocks for output.
 216
 217 chunkify(_Bt, []) ->
 218         [];
 219 chunkify(Bt, InList) ->
 220         case size(term_to_binary(InList)) of
 221         Size when Size > ?CHUNK_THRESHOLD ->
 222                 NumberOfChunksLikely = ((Size div ?CHUNK_THRESHOLD) + 1),
 223                 ChunkThreshold = Size div NumberOfChunksLikely,
 224                 chunkify(Bt, InList, ChunkThreshold, [], 0, []);
 225         _Else ->
 226                 [InList]
 227         end.
 228
 229 chunkify(_Bt, [], _ChunkThreshold, [], 0, OutputChunks) ->
 230         lists:reverse(OutputChunks);
 231 chunkify(_Bt, [], _ChunkThreshold, OutList, _OutListSize, OutputChunks) ->
 232         lists:reverse([lists:reverse(OutList) | OutputChunks]);
 233 chunkify(Bt, [InElement | RestInList], ChunkThreshold, OutList, OutListSize, OutputChunks) ->
 234         case size(term_to_binary(InElement)) of
 235         Size when (Size + OutListSize) > ChunkThreshold ->
 236                 chunkify(Bt, RestInList, ChunkThreshold, [], 0, [lists:reverse([InElement | OutList]) | OutputChunks]);
 237         Size ->
 238                 chunkify(Bt, RestInList, ChunkThreshold, [InElement | OutList], OutListSize + Size, OutputChunks)
 239         end.
 240
 241 modify_node(Bt, RootPointerInfo, Actions, QueryOutput) ->
 242         case RootPointerInfo of
 243         nil ->
 244                 NodeType = kv_node,
 245                 NodeList =[];
 246         {Pointer, _count} ->
 247                 {ok, {NodeType, NodeList}} = couch_file:pread_term(Bt#btree.fd, Pointer)
 248         end,
 249         case NodeType of
 250         kp_node ->
 251                 {ok, NewNodeList, QueryOutput2, Bt2} = modify_kpnode(Bt, NodeList, Actions, [], QueryOutput);
 252         kv_node ->
 253                 {ok, NewNodeList, QueryOutput2, Bt2} = modify_kvnode(Bt, NodeList, Actions, [], QueryOutput)
 254         end,
 255         case NewNodeList of
 256         [] ->  % no nodes remain
 257                 {ok, [], QueryOutput2, Bt2};
 258         NodeList ->  % nothing changed
 259                 {LastKey, _LastValue} = lists:last(NodeList),
 260                 {ok, [{LastKey, RootPointerInfo}], QueryOutput2, Bt2};
 261         _Else2 ->
 262                 {ok, ResultList, Bt3} = write_node(Bt2, NodeType, NewNodeList),
 263                 {ok, ResultList, QueryOutput2, Bt3}
 264         end.
 265
 266
 267 count(kv_node, NodeList) ->
 268         length(NodeList);
 269 count(kp_node, NodeList) ->
 270         lists:foldl( fun({_Key, {_Pointer, Count}}, AccCount) ->
 271                         Count + AccCount
 272                 end,
 273                 0, NodeList).
 274
 275 write_node(Bt, NodeType, NodeList) ->
 276         % split up nodes into smaller sizes
 277         NodeListList = chunkify(Bt, NodeList),
 278         % now write out each chunk and return the KeyPointer pairs for those nodes
 279         ResultList = [
 280                 begin
 281                         {ok, Pointer} = couch_file:append_term(Bt#btree.fd, {NodeType, ANodeList}),
 282                         {LastKey, _} = lists:last(ANodeList),
 283                         {LastKey, {Pointer, count(NodeType, ANodeList)}}
 284                 end
 285         ||
 286                 ANodeList <- NodeListList
 287         ],
 288         {ok, ResultList, Bt}.
 289
 290 modify_kpnode(Bt, KPs, [], ResultNode, QueryOutput) ->
 291         % processed all queries for the current tree
 292         {ok, lists:reverse(ResultNode, KPs), QueryOutput, Bt};
 293
 294 modify_kpnode(Bt, [], Actions, [{_Key, PointerInfo} | ResultNode], QueryOutput) ->
 295         {ok, ChildKPs, QueryOutput2, Bt2} = modify_node(Bt, PointerInfo, Actions, QueryOutput),
 296         {ok, lists:reverse(ResultNode, ChildKPs), QueryOutput2, Bt2};
 297
 298 modify_kpnode(Bt, [{Key,PointerInfo} | RestKPs], Actions, ResultNode, QueryOutput) ->
 299         LessFun = Bt#btree.less_fun,
 300         % Split the actions into two lists, queries of values less
 301         % than equals, and greater than the current key
 302         SplitFun = fun({_ActionType, ActionKey, _ActionValue}) ->
 303                         not LessFun(Key, ActionKey)
 304                 end,
 305         case lists:splitwith(SplitFun, Actions) of
 306         {[], GreaterQueries} ->
 307                 modify_kpnode(Bt, RestKPs, GreaterQueries, [{Key, PointerInfo} | ResultNode], QueryOutput);
 308         {LessEqQueries, GreaterQueries} ->
 309                 {ok, ChildKPs, QueryOutput2, Bt2} = modify_node(Bt, PointerInfo, LessEqQueries, QueryOutput),
 310                 modify_kpnode(Bt2, RestKPs, GreaterQueries, lists:reverse(ChildKPs, ResultNode), QueryOutput2)
 311         end.
 312
 313 modify_kvnode(Bt, KVs, [], ResultNode, QueryOutput) ->
 314         {ok, lists:reverse(ResultNode, KVs), QueryOutput, Bt};
 315 modify_kvnode(Bt, [], [{ActionType, ActionKey, ActionValue} | RestActions], ResultNode, QueryOutput) ->
 316         case ActionType of
 317         insert ->
 318                 modify_kvnode(Bt, [], RestActions, [{ActionKey, ActionValue} | ResultNode], QueryOutput);
 319         remove ->
 320                 % just drop the action
 321                 modify_kvnode(Bt, [], RestActions, ResultNode, QueryOutput);
 322         fetch ->
 323                 % the key/value must not exist in the tree
 324                 modify_kvnode(Bt, [], RestActions, ResultNode, [{not_found, {ActionKey, nil}} | QueryOutput]);
 325         missing_insert ->
 326                 Value = ActionValue(),
 327                 modify_kvnode(Bt, [], RestActions, [{ActionKey, ActionValue} | ResultNode], [{ok, {ActionKey, Value}} | QueryOutput])
 328         end;
 329 modify_kvnode(Bt, [{Key, Value} | RestKVs], [{ActionType, ActionKey, ActionValue} | RestActions], ResultNode, QueryOutput) ->
 330         LessFun = Bt#btree.less_fun,
 331         case LessFun(ActionKey, Key) of
 332         true ->
 333                 case ActionType of
 334                 insert ->
 335                         % ActionKey is less than the Key, so insert
 336                         modify_kvnode(Bt, [{Key, Value} | RestKVs], RestActions, [{ActionKey, ActionValue} | ResultNode], QueryOutput);
 337                 remove ->
 338                         % ActionKey is less than the Key, just drop the action
 339                         modify_kvnode(Bt, [{Key, Value} | RestKVs], RestActions, ResultNode, QueryOutput);
 340                 fetch ->
 341                         % ActionKey is less than the Key, the key/value must not exist in the tree
 342                         modify_kvnode(Bt, [{Key, Value} | RestKVs], RestActions, ResultNode, [{not_found, {ActionKey, nil}} | QueryOutput]);
 343                 missing_insert ->
 344                         Value = ActionValue(),
 345                         modify_kvnode(Bt, [], RestActions, [{ActionKey, Value} | ResultNode], [{ok, {ActionKey, Value}} | QueryOutput])
 346                 end;
 347         false ->
 348                 case LessFun(Key, ActionKey) of
 349                 true ->
 350                         % ActionKey is greater than Key
 351                         modify_kvnode(Bt, RestKVs, [{ActionType, ActionKey, ActionValue} | RestActions], [{Key, Value} | ResultNode], QueryOutput);
 352                 false ->
 353                         % InsertKey is equal to Key
 354                         case ActionType of
 355                         insert ->
 356                                 % ActionKey is less than the Key, so insert
 357                                 modify_kvnode(Bt, RestKVs, RestActions, [{ActionKey, ActionValue} | ResultNode], QueryOutput);
 358                         remove ->
 359                                 modify_kvnode(Bt, RestKVs, RestActions, ResultNode, QueryOutput);
 360                         fetch ->
 361                                 % ActionKey is equal to the Key, insert into the QueryOuput, but re-process the node
 362                                 % since an identical action key can follow it.
 363                                 modify_kvnode(Bt, [{Key, Value} | RestKVs], RestActions, ResultNode, [{ok, {Key, Value}} | QueryOutput]);
 364                         missing_insert ->
 365                                 modify_kvnode(Bt, [], RestActions, [{Key, Value} | ResultNode], [{ok, {Key, Value}} | QueryOutput])
 366                         end
 367                 end
 368         end.
 369
 370 adjust_dir(fwd, List) ->
 371         List;
 372 adjust_dir(rev, List) ->
 373         lists:reverse(List).
 374
 375 stream_node(Bt, Offset, PointerInfo, nil, Dir, Fun, Acc) ->
 376         stream_node(Bt, Offset, PointerInfo, Dir, Fun, Acc);
 377 stream_node(_Bt, _Offset, nil, _StartKey, _Dir, _Fun, Acc) ->
 378         {ok, Acc};
 379 stream_node(#btree{fd=Fd} = Bt, Offset, {Pointer, _Count}, StartKey, Dir, Fun, Acc) ->
 380         {ok, {NodeType, NodeList}} = couch_file:pread_term(Fd, Pointer),
 381         case NodeType of
 382         kp_node ->
 383                 stream_kp_node(Bt, Offset, adjust_dir(Dir, NodeList), StartKey, Dir, Fun, Acc);
 384         kv_node ->
 385                 stream_kv_node(Bt, Offset, adjust_dir(Dir, NodeList), StartKey, Dir, Fun, Acc)
 386         end.
 387
 388 stream_node(_Bt, _Offset, nil, _Dir, _Fun, Acc) ->
 389         {ok, Acc};
 390 stream_node(#btree{fd=Fd} = Bt, Offset, {Pointer, _Count}, Dir, Fun, Acc) ->
 391         {ok, {NodeType, NodeList}} = couch_file:pread_term(Fd, Pointer),
 392         case NodeType of
 393         kp_node ->
 394                 stream_kp_node(Bt, Offset, adjust_dir(Dir, NodeList), Dir, Fun, Acc);
 395         kv_node ->
 396                 stream_kv_node(Offset, adjust_dir(Dir, NodeList), Dir, Fun, Acc)
 397         end.
 398
 399 stream_kp_node(_Bt, _Offset, [], _Dir, _Fun, Acc) ->
 400         {ok, Acc};
 401 stream_kp_node(Bt, Offset, [{_Key, {Pointer, Count}} | Rest], Dir, Fun, Acc) ->
 402         case stream_node(Bt, Offset, {Pointer, Count}, Dir, Fun, Acc) of
 403         {ok, Acc2} ->
 404                 stream_kp_node(Bt, Offset + Count, Rest, Dir, Fun, Acc2);
 405         {stop, Acc2} ->
 406                 {stop, Acc2}
 407         end.
 408
 409 drop_nodes(Offset, _LessFun, _StartKey, []) ->
 410         {Offset, []};
 411 drop_nodes(Offset, LessFun, StartKey, [{NodeKey, {Pointer, Count}} | RestKPs]) ->
 412         case LessFun(NodeKey, StartKey) of
 413         true -> drop_nodes(Offset + Count, LessFun, StartKey, RestKPs);
 414         false -> {Offset, [{NodeKey, {Pointer, Count}} | RestKPs]}
 415         end.
 416
 417 stream_kp_node(Bt, Offset, KPs, StartKey, Dir, Fun, Acc) ->
 418         #btree{less_fun=LessFun} = Bt,
 419         {NewOffset, NodesToStream} =
 420         case Dir of
 421         fwd ->
 422                 % drop all nodes sorting before the key
 423                 drop_nodes(Offset, LessFun, StartKey, KPs);
 424         rev ->
 425                 % keep all nodes sorting before the key, AND the first node to sort after
 426                 RevKPs = lists:reverse(KPs),
 427                 case lists:splitwith(fun({Key, _Pointer}) -> LessFun(Key, StartKey) end, RevKPs) of
 428                 {_RevBefore, []} ->
 429                         % everything sorts before it
 430                         {Offset, KPs};
 431                 {RevBefore, [FirstAfter | Drop]} ->
 432                         {Offset + count(kp_node, Drop), [FirstAfter | lists:reverse(RevBefore)]}
 433                 end
 434         end,
 435         case NodesToStream of
 436         [] ->
 437                 {ok, Acc};
 438         [{_Key, PointerInfo} | Rest] ->
 439                 case stream_node(Bt, NewOffset, PointerInfo, StartKey, Dir, Fun, Acc) of
 440                 {ok, Acc2} ->
 441                         stream_kp_node(Bt, NewOffset, Rest, Dir, Fun, Acc2);
 442                 {stop, Acc2} ->
 443                         {stop, Acc2}
 444                 end
 445         end.
 446
 447 stream_kv_node(_Offset, [], _Dir, _Fun, Acc) ->
 448         {ok, Acc};
 449 stream_kv_node(Offset, [KV | RestKVs], Dir, Fun, Acc) ->
 450         case Fun(KV, Offset, Acc) of
 451         {ok, Acc2} ->
 452                 stream_kv_node(Offset + 1, RestKVs, Dir, Fun, Acc2);
 453         {stop, Acc2} ->
 454                 {stop, Acc2}
 455         end.
 456
 457 stream_kv_node(Bt, Offset, KVs, StartKey, Dir, Fun, Acc) ->
 458         LessFun = Bt#btree.less_fun,
 459         DropFun =
 460         case Dir of
 461         fwd ->
 462                 fun({Key, _}) -> LessFun(Key, StartKey) end;
 463         rev ->
 464                 fun({Key, _}) -> LessFun(StartKey, Key) end
 465         end,
 466         % drop all nodes preceding the key
 467         GTEKVs = lists:dropwhile(DropFun, KVs),
 468         LenSkipped = length(KVs) - length(GTEKVs),
 469         stream_kv_node(Offset + LenSkipped, GTEKVs, Dir, Fun, Acc).
 470
 471
 472
 473
 474 test()->
 475         test(1000).
 476
 477 test(N) ->
 478         KeyValues = [{random:uniform(), random:uniform()} || _Seq <- lists:seq(1, N)],
 479         test_btree(KeyValues),                          % randomly distributed
 480         Sorted = lists:sort(KeyValues),
 481         test_btree(Sorted),                                     % sorted regular
 482         test_btree(lists:reverse(Sorted)).      % sorted reverse
 483
 484
 485 test_btree(KeyValues) ->
 486         {ok, Fd} = couch_file:open("foo", [create,overwrite]),
 487         {ok, Btree} = open(nil, Fd),
 488
 489         % first dump in all the values in one go
 490         {ok, Btree10} = add_remove(Btree, KeyValues, []),
 491
 492         ok = test_keys(Btree10, KeyValues),
 493
 494         % remove everything
 495         {ok, Btree20} = test_remove(Btree10, KeyValues),
 496
 497         % make sure its empty
 498         {ok, false} = foldl(Btree20, fun(_X, _Acc) ->
 499                         {ok, true} % change Acc to 'true'
 500                 end,
 501                 false),
 502
 503         % add everything back one at a time.
 504         {ok, Btree30} = test_add(Btree20, KeyValues),
 505
 506         ok = test_keys(Btree30, KeyValues),
 507
 508         KeyValuesRev = lists:reverse(KeyValues),
 509
 510         % remove everything, in reverse order
 511         {ok, Btree40} = test_remove(Btree30, KeyValuesRev),
 512
 513         % make sure its empty
 514         {ok, false} = foldl(Btree40, fun(_X, _Acc) ->
 515                         {ok, true} % change Acc to 'true'
 516                 end,
 517                 false),
 518
 519
 520         {A, B} = every_other(KeyValues),
 521
 522         % add everything back
 523         {ok, Btree50} = test_add(Btree40,KeyValues),
 524
 525         ok = test_keys(Btree50, KeyValues),
 526
 527         % remove half the values
 528         {ok, Btree60} = test_remove(Btree50, A),
 529
 530         % verify the remaining
 531         ok = test_keys(Btree60, B),
 532
 533         % add A back
 534         {ok, Btree70} = test_add(Btree60, A),
 535
 536         % verify
 537         ok = test_keys(Btree70, KeyValues),
 538
 539         % remove B
 540         {ok, Btree80} = test_remove(Btree70, B),
 541
 542         % verify the remaining
 543         ok = test_keys(Btree80, A),
 544
 545         ok = couch_file:close(Fd).
 546
 547
 548
 549
 550 every_other(List) ->
 551         every_other(List, [], [], 1).
 552
 553 every_other([], AccA, AccB, _Flag) ->
 554         {lists:reverse(AccA), lists:reverse(AccB)};
 555 every_other([H|T], AccA, AccB, 1) ->
 556         every_other(T, [H|AccA], AccB, 0);
 557 every_other([H|T], AccA, AccB, 0) ->
 558         every_other(T, AccA, [H|AccB], 1).
 559
 560 test_keys(Btree, List) ->
 561         FoldFun =
 562         fun(Element, [HAcc|TAcc]) ->
 563                         Element = HAcc, % must match
 564                         {ok, TAcc}
 565                 end,
 566         Sorted = lists:sort(List),
 567         {ok, []} = foldl(Btree, FoldFun, Sorted),
 568         {ok, []} = foldr(Btree, FoldFun, lists:reverse(Sorted)),
 569
 570         test_lookup(Btree, List).
 571
 572 % Makes sure each key value pair is found in the btree
 573 test_lookup(_Btree, []) ->
 574         ok;
 575 test_lookup(Btree, [{Key, Value} | Rest]) ->
 576         {ok, [{ok,{Key, Value}}]} = lookup(Btree, [Key]),
 577         {ok, []} = foldl(Btree, Key, fun({KeyIn, ValueIn}, []) ->
 578                         KeyIn = Key,
 579                         ValueIn = Value,
 580                         {stop, []}
 581                 end,
 582                 []),
 583         {ok, []} = foldr(Btree, Key, fun({KeyIn, ValueIn}, []) ->
 584                         KeyIn = Key,
 585                         ValueIn = Value,
 586                         {stop, []}
 587                 end,
 588                 []),
 589         test_lookup(Btree, Rest).
 590
 591 % removes each key one at a time from the btree
 592 test_remove(Btree, []) ->
 593         {ok, Btree};
 594 test_remove(Btree, [{Key, _Value} | Rest]) ->
 595         {ok, Btree2} = add_remove(Btree,[], [Key]),
 596         test_remove(Btree2, Rest).
 597
 598 % adds each key one at a time from the btree
 599 test_add(Btree, []) ->
 600         {ok, Btree};
 601 test_add(Btree, [KeyValue | Rest]) ->
 602         {ok, Btree2} = add_remove(Btree, [KeyValue], []),
 603         test_add(Btree2, Rest).
 604