gb_trees:search/3

[Sven-Olof Nystr|m]

Ulf Wiger (AL/EAB) writes:
 > >  > 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,

That was my point.

 > 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). 

I disagree, but it's not very interesting, so I'll let it drop.


 > New attempt:
 > 
 > search_1(_Fun, Acc, nil) ->

[snip]

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

or to_list().


[Moved example]
 > 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 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_.

So you scan the part of a tree where keys are smaller than 5.

See my comment at the end for alternative ways to provide this
functionality in gb_trees.



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

Too bad.


 > >  > 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.)

OK. I actually didn't realise that they implemented different
functions.


 > >  > 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.

OK. 


 > 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).

That's nice. 

 > 
 > 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?

Sure, previous() and next() could be useful. I would prefer more
descriptive names, such as lookup_smaller() and lookup_larger(). Also,
I think they should always return a strictly smaller/larger key, even
if the given key is present.


 > Today, you can do that with ets ordered_set, but
 > not easily with any of the functional data 
 > structures provided by OTP.

Currently, iterators can only be used to scan the tree from start, One
might consider iterators that start the scan from a point in the
middle of the tree (from a given key), or iterators that scan the
tree backwards.

Another way to do partial scans might be a function 

to_list(Key1, Key2) 

that returns a list of the entries in the tree between the two keys.




Sven-Olof