[erlang-questions] Writing a Concurrent Binary Search Tree Data Structure in Erlang

[Kevin Scaldeferri]

On Jun 25, 2008, at 3:10 PM, Fuad Tabba wrote:

> I think I understand what you're saying here; but I still can't wrap  
> my head around putting that into code. Is there similar code that  
> you know of available online? The structure doesn't have to be a  
> BST, just anything that demonstrates the idea of having a structure  
> that stores lots persistent data to be viewed/modified by many  
> processes and is scalable...
>
>
> On Wed, Jun 25, 2008 at 9:40 PM, Hynek Vychodil <vychodil.hynek@REDACTED 
> > wrote:
> Because there is no shared state between processes in Erlang, I  
> would start think about process per tree node, not process per  
> action as usual in classic shared memory (for example C)  
> implementations.
> I know, it sounds weird, but may be help you :-)



Here's a basic outline of this idea, if I understand it right.   
delete() is not implemented, and it has some other deficiencies, but I  
hope it at least starts to demonstrate the idea of a recursive data  
structure represented as a collection of processes.


-kevin

%%%%%%%%%%%%%%%%%%%%%%%%%

-module(cbst).
-export([new/1, exists/2, insert/2, delete/2]).

-record(node, {key,
                left=null,
                right=null}).

%%
%% public API
%%

new(Key) ->
     spawn(fun() -> create(Key) end).

exists(Node, Key) ->
     Node ! {exists, Key, self()},
     receive
         true -> true;
         false -> false
     end.

insert(Node, Key) ->
     Node ! {insert, Key}.

delete(Node, Key) ->
     Node ! {delete, Key}.


%%
%% private functions
%%

create(Key) ->
     Node = #node{key=Key},
     loop(Node).

loop(Node) ->
     receive
         {exists, Key, Caller}=Q ->
             case Node#node.key of
                 Key ->
                     Caller ! true;
                 This when Key < This, Node#node.left =/= null ->
                     Node#node.left ! Q;
                 This when Key > This, Node#node.right =/= null ->
                     Node#node.right ! Q;
                 _ ->
                     Caller ! false
             end,
             loop(Node);
         {insert, Key} ->
             case Node#node.key of
                 Key ->
                     loop(Node); % already in tree
                 This when Key < This ->
                     case Node#node.left of
                         null ->
                             Left = new(Key),
                             loop(Node#node{left=Left});
                         Left ->
                             Left ! {insert, Key},
                             loop(Node)
                     end;
                 This when Key > This ->
                     case Node#node.right of
                         null ->
                             Right = new(Key),
                             loop(Node#node{right=Right});
                         Right ->
                             Right ! {insert, Key},
                             loop(Node)
                     end
             end;
         {delete, Key} ->
             % left as an exercise for the reader
             loop(Node)
     end.