Cool, that's matches my understanding of Hynek's suggestion as well. Thanks Kevin.<br><br>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.<br>
<br>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.<br><br>Thanks again!<br clear="all">
<br>Cheers,<br>/Fuad
<br><br><div class="gmail_quote">On Fri, Jun 27, 2008 at 8:22 AM, Kevin Scaldeferri <<a href="mailto:kevin@scaldeferri.com">kevin@scaldeferri.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d"><br>
On Jun 25, 2008, at 3:10 PM, Fuad Tabba wrote:<br>
<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d">
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...<br>
<br>
<br></div><div class="Ih2E3d">
On Wed, Jun 25, 2008 at 9:40 PM, Hynek Vychodil <<a href="mailto:vychodil.hynek@gmail.com" target="_blank">vychodil.hynek@gmail.com</a>> wrote:<br>
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.<br>
I know, it sounds weird, but may be help you :-)<br>
</div></blockquote>
<br>
<br>
<br>
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.<br>
<br>
<br>
-kevin<br>
<br>
%%%%%%%%%%%%%%%%%%%%%%%%%<br>
<br>
-module(cbst).<br>
-export([new/1, exists/2, insert/2, delete/2]).<br>
<br>
-record(node, {key,<br>
left=null,<br>
right=null}).<br>
<br>
%%<br>
%% public API<br>
%%<br>
<br>
new(Key) -><br>
spawn(fun() -> create(Key) end).<br>
<br>
exists(Node, Key) -><br>
Node ! {exists, Key, self()},<br>
receive<br>
true -> true;<br>
false -> false<br>
end.<br>
<br>
insert(Node, Key) -><br>
Node ! {insert, Key}.<br>
<br>
delete(Node, Key) -><br>
Node ! {delete, Key}.<br>
<br>
<br>
%%<br>
%% private functions<br>
%%<br>
<br>
create(Key) -><br>
Node = #node{key=Key},<br>
loop(Node).<br>
<br>
loop(Node) -><br>
receive<br>
{exists, Key, Caller}=Q -><br>
case Node#node.key of<br>
Key -><br>
Caller ! true;<br>
This when Key < This, Node#node.left =/= null -><br>
Node#node.left ! Q;<br>
This when Key > This, Node#node.right =/= null -><br>
Node#node.right ! Q;<br>
_ -><br>
Caller ! false<br>
end,<br>
loop(Node);<br>
{insert, Key} -><br>
case Node#node.key of<br>
Key -><br>
loop(Node); % already in tree<br>
This when Key < This -><br>
case Node#node.left of<br>
null -><br>
Left = new(Key),<br>
loop(Node#node{left=Left});<br>
Left -><br>
Left ! {insert, Key},<br>
loop(Node)<br>
end;<br>
This when Key > This -><br>
case Node#node.right of<br>
null -><br>
Right = new(Key),<br>
loop(Node#node{right=Right});<br>
Right -><br>
Right ! {insert, Key},<br>
loop(Node)<br>
end<br>
end;<br>
{delete, Key} -><br>
% left as an exercise for the reader<br>
loop(Node)<br>
end.<br>
<br>
</blockquote></div><br>