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

Fuad Tabba fuad@REDACTED
Thu Jun 26 22:54:44 CEST 2008


Cool, that's matches my understanding of Hynek's suggestion as well. Thanks
Kevin.

I'm actually writing code along similar lines to test out the idea. It seems
rather simple and elegant; what I don't like though is the added overhead of
a process per node - I know that Erlang processes are light, but if I recall
correctly from reading in Joe's book, each process has memory overhead in
the order of 100 bytes. If the the data per node is large then it's not a
big deal, but if the amount of data stored per node is small then that could
be some serious overhead.

Implementing delete() is going to be a bit tricky, need to be wary of
deadlocks; but this isn't an Erlang issue, this is a general issue with
writing a concurrent and shared data structure.

Thanks again!

Cheers,
/Fuad

On Fri, Jun 27, 2008 at 8:22 AM, Kevin Scaldeferri <kevin@REDACTED>
wrote:

>
> 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.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080627/86fc9414/attachment.htm>


More information about the erlang-questions mailing list