% Fuad Tabba % cs.auckland.ac.nz AT fuad -module(cbst). -export([rpcContains/2, rpcInsert/2, rpcDelete/2, rpcDump/1]). -compile(export_all). % for debugging % To get started:- % createTree() creates a sample tree % randCreate(KeyRange) creates a random tree within a certain range % testTree(KeyRange, Operations, NoThreads) creates and performs a bunch of % operations on the tree. % Insert, Delete and Contains should always be correct. Dump is used for % debugging and can show an inconsistent state if changes are pending. Dump % must always be correct for a stable tree. % Node Structure: {Key, PidLeft, PidRight} % true if the tree contains the Key, false otherwise rpcContains(_, nil) -> false; rpcContains(Key, Pid) -> Pid ! {contains, Key, self()}, receive Result -> Result end. % Inserting into an empty (nil) node, create a new node rpcInsert(Key, nil) -> Pid = createNode(Key), {Pid, true}; % Insering into an existing node - ask its process to deal with it rpcInsert(Key, Pid) -> Pid ! {insert, Key, self()}, receive Result -> Result end, {Pid, Result}. % Deleting an empty (nil) node - just results in an empty leaf (not found) rpcDelete(_, nil) -> {nil, false}; % Deleting from an existing node send a request to it rpcDelete(Key, Pid) -> Pid ! {delete, Key, self()}, receive Result -> Result end, {Pid, Result}. % For debugging: returns the whole tree rpcDump(nil) -> nil; rpcDump(Pid) -> Pid ! {dump, self()}, receive Tree -> Tree end. % Maintains the state of the node nodeState(Node) -> receive {contains, Key, Client} -> contains(Key, Node, Client), nodeState(Node); {insert, Key, Client} -> nodeState(insert(Key, Node, Client)); {delete, Key, Client} -> nodeState(delete(Key, Node, Client)); {node, Requester} -> Requester ! Node, nodeState(Node); {dump, Requester} -> dump(Node, Requester), nodeState(Node); % Kill the process (part of deleting it) die -> true end. % Get the dump of the subtree dump(Node, Requester) -> if nil =:= Node -> Requester ! nilP; true -> {Key, PidLeft, PidRight} = Node, Requester ! {Key, rpcDump(PidLeft), rpcDump(PidRight)} end. % Check whether the subtree contains the key. contains(Kfind, {Key, PidLeft, _}, Requester) when Kfind < Key -> relayContain(Kfind, PidLeft, Requester); contains(Kfind, {Key, _, PidRight}, Requester) when Kfind > Key -> relayContain(Kfind, PidRight, Requester); contains(Key, {Key, _, _}, Client) -> Client ! true; contains(_, nil, Client) -> Client ! false. % Relays the contain request to the next node, % Or informs the requestor that it's not there if it's a nil node relayContain(_, nil, Client) -> Client ! false; relayContain(Key, NodePid, Client) -> NodePid ! {contains, Key, Client}. insert(Knew, {Key, PidLeft, PidRight}, Client) when Knew < Key -> {Key, relayInsert(Knew, PidLeft, Client), PidRight}; insert(Knew, {Key, PidLeft, PidRight}, Client) when Knew > Key -> {Key, PidLeft, relayInsert(Knew, PidRight, Client)}; insert(Key, {Key, PidLeft, PidRight}, Client) -> Client ! false, % exists {Key, PidLeft, PidRight}; % Inserting into a node whose state is nil, it takes on the key insert(Key, nil, Client) -> Client ! true, % took on its value {Key, nil, nil}. relayInsert(Key, nil, Client) -> Client ! true, createNode(Key); relayInsert(Key, Pid, Client) -> Pid ! {insert, Key, Client}, Pid. % Create a new node and return its Pid createNode(Key) -> spawn(fun() -> nodeState({Key, nil, nil}) end). delete(Kdel, {Key, PidLeft, PidRight}, Client) when Kdel < Key -> {Key, relayDelete(Kdel, PidLeft, Client), PidRight}; delete(Kdel, {Key, PidLeft, PidRight}, Client) when Kdel > Key -> {Key, PidLeft, relayDelete(Kdel, PidRight, Client)}; % There's the possibility of having a node who's state is "nil" % I've decided to take the lazy approach and leave such leaves, only to prune % them when neccessary % % Three possibilities; left is a process with a nil state, right is a process % with a nil state, or neither, which means I need to find the maximum node % in the left delete(Key, {Key, PidLeft, PidRight}, Client) -> NodeLeft = getNode(PidLeft), NodeRight = getNode(PidRight), if NodeLeft =:= nil -> Client ! true, killNode(PidLeft), killNode(PidRight), NodeRight; NodeRight =:= nil -> Client ! true, killNode(PidLeft), killNode(PidRight), NodeLeft; true -> % Find the biggest node in the left subtree assume its identity % then delete it. This step is tricky; if not done right it could % either deadlock or have the tree in an inconsistent state. Kmax = max(NodeLeft), relayDelete(Kmax, PidLeft, Client), {Kmax, PidLeft, PidRight} end; % Not found (this node's saate is nil) delete(_, nil, Client) -> Client ! false, nil. % Kills the process controlling the node (actually just asks it to die) killNode(nil) -> true; killNode(Pid) -> Pid ! die. % Not found (trying to relay it to nil Pid) relayDelete(_, nil, Client) -> Client ! false, nil; relayDelete(Key, Pid, Client) -> Pid ! {delete, Key, Client}, Pid. % Gets the state of the node from its associated process getNode(nil) -> nil; % Ask the process for its state then wait for it to respond. getNode(Pid) -> Pid ! {node, self()}, receive Node when is_integer(element(1, Node)) -> % To avoid receiving other messages (relayed requests) Node; nil -> nil end. % returns the biggest key in this subtree % can't really be parallelized max({Key, _, PidRight}) -> NodeRight = getNode(PidRight), if NodeRight =:= nil -> Key; true -> max(NodeRight) end. % Create a pre-determined test tree createTree() -> {Root, _} = rpcInsert(260, nil), rpcInsert(240, Root), rpcInsert(140, Root), rpcInsert(320, Root), rpcInsert(250, Root), rpcInsert(170, Root), rpcInsert(60, Root), rpcInsert(100, Root), rpcInsert(20, Root), rpcInsert(40, Root), rpcInsert(290, Root), rpcInsert(280, Root), rpcInsert(270, Root), rpcInsert(30, Root), rpcInsert(265, Root), rpcInsert(275, Root), rpcInsert(277, Root), rpcInsert(278, Root), Root. % Creates a random tree within the specified range. KeyRange/2 is the root of % the tree randCreate(KeyRange) -> Kroot = trunc(KeyRange/2), Operations = KeyRange, {Root, _} = rpcInsert(Kroot, nil), lists:foreach(fun(_) -> rpcInsert(random:uniform(KeyRange), Root) end, lists:seq(1, Operations)), Root. % First creates a random tree, then performs randomly selected operations on it % being run on N threads. % % Returns a tuple containing; the root of the tree, the total runtime, and % the wall clock time testTree(KeyRange, Operations, NoThreads) -> Root = randCreate(KeyRange), OpsPerThread = trunc(Operations/NoThreads), Self = self(), statistics(runtime), statistics(wall_clock), lists:foreach(fun(_) -> spawn(fun() -> testThread(Root, KeyRange, OpsPerThread, Self) end) end, lists:seq(1,NoThreads)), lists:foreach(fun(_) -> receive done -> done end end, lists:seq(1,NoThreads)), {_,Run} = statistics(runtime), {_,Wall} = statistics(wall_clock), {Root, Run, Wall}. % Function for the spawned process that performs a certain number of random % operaions. testThread(Root, KeyRange, Operations, Requester) -> lists:foreach(fun(_) -> randOperation(Root, KeyRange) end, lists:seq(1,Operations)), Requester ! done. % Choose a random operation on the tree randOperation(RootPid, KeyRange) -> Op = random:uniform(3), Key = random:uniform(KeyRange), case Op of 1 -> rpcInsert(Key, RootPid); 2 -> rpcDelete(Key, RootPid); _ -> rpcContains(Key, RootPid) end.