gb_trees:search/3

[Ulf Wiger (AL/EAB)]

Sven-Olof Nyström wrote:
> 
> Ulf Wiger (AL/EAB) writes:
>
> Clauses 2 & 3, and 4 & 5 could be merged, of course. 
> 
> The lookup function in the gb_trees library returns 
> {value, V} when a value is found and `none' if not.
> Why not follow the same convention here? 

Indeed. Obviously, the examples were put together
in haste. (:


>  > I'm sure you could do a lot of other stuff with
> search/3 too.
> 
> I'm not so sure. I can think of a few others, such as
> building (unbalanced) trees of all nodes greater or
> smaller than a given key, but I don't think you could
> do much else with the search function.

Well, we're both wrong, as it turns out. (:
As written, you probably cannot do much else with it,
and in fact not even what you suggest, since there 
is no way to make sure that you actually find all nodes
greater or smaller than a given key (since it always 
goes down only one branch). 

New attempt:

search_1(_Fun, Acc, nil) ->
    Acc;
search_1(Fun, Acc, {Key, V, Smaller, Bigger}) ->
    case Fun(Key, V, Acc) of
	{smaller, Acc1} ->
	    search_1(Fun, Acc1, Smaller);
	{both, Acc1} ->
	    Acc2 = search_1(Fun, Acc1, Smaller),
	    search_1(Fun, Acc2, Bigger);
	{bigger, Acc1} ->
	    search_1(Fun, Acc1, Bigger);
	{return, Acc1} ->
	    Acc1
    end.

fixing the mistake of calling Fun(nil,nil,Acc)
and allowing the iteration to scan both branches,
it can at least be used for _some_ more stuff:

2> T = gb_trees:empty().
{0,nil}

3> T1 = lists:foldl(fun({K,V},Tx) -> 
gb_trees:insert(K,V,Tx) end, T, 
[{N,a} || N <- lists:seq(1,10,2)]).
{5,{1,a,nil,{3,a,nil,{5,a,nil,{7,a,nil,
{9,a,nil,nil}}}}}}

5> T2 = lists:foldl(fun({K,V},Tx) -> 
gb_trees:insert(K,V,Tx) end, T1, 
[{N,b} || N <- lists:seq(2,10,2)]).
{10,
 {1,
  a,
  nil,
  {3,
   a,
   {2,b,nil,nil},
   {5,a,{4,b,nil,nil},{7,a,{6,b,nil,nil},
{9,a,{8,b,nil,nil},{10,b,nil,nil}}}}}}} 

11> F = fun(K,a,Acc) -> {both,[K|Acc]};
 (_, _, Acc) -> {both,Acc} end.
#Fun<erl_eval.18.103411980>

12> vccTree:search(F,[],T2).                                               
[9,7,5,3,1]

14> F1 = fun(K,V,Acc) when K > 5 ->
 {smaller,Acc}; (K,V,Acc) ->
 {both,[{K,V}|Acc]} end.
#Fun<erl_eval.18.103411980>

15> vccTree:search(F1,[],T2). 
[{4,b},{5,a},{2,b},{3,a},{1,a}]

The first example doesn't really introduce
anything new, as it scans the whole tree
(most likely less efficient than iterator())

The second example is almost equivalend to 
ets:select/2 on an ordered_set, but with the 
difference (as of now) that ets:select/2 will
scan the whole table if at least the first part
of the key isn't bound(*). Now, this is a feature
that at least I use _a lot_.

(*) Also with the difference that my function
screws up the order.

>  > There's probably a more elegant construct
>  > that would solve the problem with equal
>  > or better efficiency. Please go ahead and
>  > suggest better ways.
> 
> See your next mail :-)

Not fair, as it solved another problem. (:
I want to support both getting the first
available free resource, and reserving
a specific resource (c.f. UNIX sockets.)

>  > free/2 is more involved as it needs to
>  > de-fragment the tree, but that would be
>  > done along the same lines as reserve/2,
>  > using the gb_trees:search/3 function.
> 
> Why defragment? The cost of defragmentation 
> could easily exeed the cost of having a
> fragmented tree in memory (unless you need to be
> able to allocate contiguous sequences of resources,
> of course).

Yes, I do that too.


> Yes, I can see situations where
> fragmentations might be worthwhile (for example,
> if the number of resources is very large), but then
> it might also be a good idea to consider alternatives
> to gb_trees.

My intention was to allow a very large virtual range. 
allocated. BTW, the code to free resources and 
de-fragment looks pretty much like this:

do_free_x(Id, Free) ->
    Prev = prev(Id, Free),
    Next = next(Id, Free),
    case {Prev, Next} of
	{{value,{A,B}}, _} when A >= Id, Id >= B ->
	    erlang:error({not_reserved, Id});
	{_, {value,{C,D}}} when C >= Id, Id >= D ->
	    erlang:error({not_reserved, Id});
	{{value,{A,B}}, {value,{C,D}}} when B == Id-1, C == Id+1 ->
	    Free1 = delete(C, Free),
	    update(A, D, Free1);
	{_, {value,{C,D}}} when Id+1 == C ->
	    Free1 = delete(C, Free),
	    insert(Id, D, Free1);
	{{value,{A,B}}, _} when B+1 == Id ->
	    update(A, Id, Free);
	Other ->
	    insert(Id, Id, Free)
    end.


Ony my SunBlade, reserving and freeing resources
with gb_trees takes about 20-30 microsecs on a 
small tree, and about 40 usecs on a large one 
(10,000 nodes).

Forgetting about this particular example, having
previous(), next() and an efficient way to select
nodes in a tree without having to traverse the 
whole tree would be useful, don't you think?
Today, you can do that with ets ordered_set, but
not easily with any of the functional data 
structures provided by OTP.

/Uffe