gb_trees:search/3

[Ulf Wiger (AL/EAB)]

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) ->
    case Fun(nil, nil, Acc) of
	{return, Acc1} ->
	    Acc1;
	Other ->
	    erlang:error({bad_return, Other})
    end;
search_1(Fun, Acc, {Key, V, Smaller, Bigger}) ->
    case Fun(Key, V, Acc) of
	{smaller, Acc1} ->
	    search_1(Fun, Acc1, Smaller);
	{bigger, Acc1} ->
	    search_1(Fun, Acc1, Bigger);
	{return, Acc1} ->
	    Acc1
    end.

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


prev(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 ->
		{smaller, not_found};
	   (K,V, {found, Found}) when K >= Key ->
		{smaller, {found, Found}};
	   (K,V, not_found) when K < Key ->
		{bigger, {found, {K,V}}};
	   (K,V, {found,_}) when K < Key ->
		{bigger, {found,{K,V}}}
	end,
    gb_rees:search(F, not_found, T).

********************

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) ->
    F = fun(nil, nil, Acc) ->
		{return,Acc};
	   (A, A, _) when N==A ->
		{return,
             [fun(T1) -> gb_trees:delete(A, T1) end]};
	   (A, B, _) when N==A ->
		{return,
             [fun(T1) -> gb_trees:delete(A, T1) end,
              fun(T1) -> gb_trees:insert(A+1, B,T1) end]};
	   (A, B, _) when N==B ->
		{return,
             [fun(T1) -> gb_trees:update(A, B-1, T1) end]};
	   (A, B, _) when A < N, N < B ->
		{return,
             [fun(T1) -> gb_trees:update(A, N-1, T1) end,
              fun(T1) -> gb_trees:insert(N+1, B, T1) end]};
	   (A, _, Acc) when N > A ->
		{bigger, Acc};
	   (_, B, Acc) when N < B ->
		{smaller, Acc}
	end,
    case gb_trees:search(F, [], T) of
        [] -> throw(busy);
        [_|_] = Fns ->
           lists:foldl(fun(F,Tree) -> F(Tree) end, T, Fns)
    end.

I'm sure you could do a lot of other stuff with search/3 too.

There's probably a more elegant construct that would solve the problem with equal or better efficiency. Please go ahead and suggest better ways.

/Uffe