gb_trees:search/3

[Sven-Olof Nystr|m]

Ulf Wiger (AL/EAB) writes:
 > 
 > I've been playing with ways to implement a functional resource database.
 > My current version uses gb_trees, but I decided I was missing a function:
 > 
 > 
 > search(Fun, Acc, {_S, T}) ->
 >     _Acc1 = search_1(Fun, Acc, T).
 > 
 > 
 > search_1(Fun, Acc, nil) ->

[snip]
 > 
 > One could say that it's main purpose is to allow the user to come up
 > with new access functions without having to know the exact structure
 > of the tree.
 > 
 > The functions next/2 and prev/2 could then be implemented in 
 > this way:
 > 
 > next(Key, T) ->
 >     F = fun(nil,nil,Acc) ->
 > 		case Acc of
 > 		    {found, Found} ->
 > 			{return, Found};
 > 		    not_found ->
 > 			{return, '$end_of_table'}
 > 		end;
 > 	   (K,V, not_found) when K =< Key ->
 > 		{bigger, not_found};
 > 	   (K,V, {found, Found}) when K =< Key ->
 > 		{bigger, {found, Found}};
 > 	   (K,V, not_found) when K > Key ->
 > 		{smaller, {found, {K,V}}};
 > 	   (K,V, {found,_}) when K > Key ->
 > 		{smaller, {found,{K,V}}}
 > 	end,
 >     gb_trees:search(F, not_found, T).

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? 

 > And my resource database reservation function
 > could look like this.
 > (The tree initially consists of one object,
 > {Min, Max}, indicating the range of free resources.
 > E.g. [{1,99},{101,1000}] would mean that the 
 > resource 100 has been allocated but the rest, i.e.
 > 1-99 and 101-1000, are free
 > 
 >     
 > reserve(N, T) ->
[...]
 > 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.



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


Ulf Wiger (AL/EAB) writes:
 > 
 > Replying to my own post, the easier case 
 > is of course when just a resource (not a specific
 > number) is asked for:
 > 
 > reserve(Free) ->
 >     case gb_trees:take_smallest(Free) of
 > 	{Min, Min, Free1} ->
 > 	    {Min, Free1};
 > 	{Min, Max, Free1} when Max > Min ->
 > 	    {Min, gb_trees:insert(Min+1, Max, Free1)}
 >     end.
 > 
 > 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 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.


Sven-Olof