The MutableBinarySearchTree approach, augmented with readers-writers synchronization and some fine-grained locking.

{- 

	Instantiate a framework for readers-writers synchronization.
	Calling readerswriters() publishes a tuple (reader, writer, quit)
	and starts a supporting readers-writers loop.
	
	reader(f) runs the function f as a reader; any number of other
	readers may also run concurrently, but no writer may run concurrently.
	f runs until it publishes a value and then it is terminated; the
	return value of reader(f) is the value published by f. If f halts,
	reader(f) also halts, and is no longer considered a running reader.

	writer(f) behaves similarly except that no reader or writer may
	run concurrently with a writer. 

	The scheduling is fair for readers if all functions passed as writers
	eventually publish a value or halt.
	
	The scheduling is fair for writers if all functions passed as readers
	or writers eventually publish a value or halt.

-}
type rw = Reader() | Writer() | End()
def readerswriters() =
  	val req = Buffer()
  	val cb  = Counter()
  	def rw() =
  		req.get() >(b,s)>
    		( b >Reader()>                cb.inc() >> s.release() >>                rw()
    		| b >Writer()> cb.onZero() >> cb.inc() >> s.release() >> cb.onZero() >> rw()
    		| b >End()> cb.onZero() >> s.release() >> signal)  	
  	def request(r, f) =
  		val s = Semaphore(0)
  		req.put((r,s)) >> 
  		s.acquire() >> 
  		( let(f()) >v> cb.dec() >> v 
  		            ;  cb.dec() >> stop )
  	def reader(f) = request(Reader(), f)
  	def writer(f) = request(Writer(), f) 
  	def quit() = request(End(), lambda () = signal)
  	(reader, writer, quit) << rw()



readerswriters() >(reader,writer,quit)>

(

{- Singleton null (bottom sentinel) for all trees -}
val null = Dictionary()

{- A tree node is a dictionary with a left entry, a right entry, and a semaphore. -}
def Node() =
	Dictionary() >r>
	(r.left := null , r.right := null , r.sem := Semaphore(1)) >>
	r

{- All nodes besides the top sentinel also have a value. -}
def singleton(v) = Node() >n> n.val := v >> n


{- 
	Redirect d pointer of p to q. 
	p /= null.
	Direction of pointer: false for left and true for right.
	p and q are both nodes.
-}
def update(p,d,q) =  
   if d then p.right := q else p.left := q



{- Top sentinel for the tree; it has no value -}
val tsent = Node()

{- Return (p,d,q) where p.d = q and (q.val = key or q = null) -}
def searchstart(key) = 
   def searchloop(p,d,q,key) =
   {- given p is non-null, and p.d = q. q may be null.
      Start search from q for key.
      Return (u,d,t) where u.d = t and (t.val = key or t = null)
   -}
   if (q = null) >> (p,d,q)
 | if (q /= null) >> q.val? >v>
     (
       if(key < v) >> searchloop(q,false,q.left?,key)
     | if(key = v) >> (p,d,q)
     | if(key > v) >> searchloop(q,true,q.right?,key)
     )

 {- Goal for searchstart -}
  searchloop(tsent,false,tsent.left?,key) 
 

{- Return (p,d,q) where p.d = q and (q.val = key or q = null) -}
def isearchstart(key) = 
  	def isearchloop(p,d,q,key) =
   		{- 
   		   Given p is non-null, and p.d = q. q may be null.
       	   Start search from q for key.
       	   Return (u,d,t) where u.d = t and (t.val = key or t = null)
    	-}
 		if (q = null) >> (p,d,q)
 	  |	if (q /= null) >> q.sem?.acquire() >> q.val? >v>
     	(
       	  if(key < v) >> p.sem?.release() >> isearchloop(q,false,q.left?,key)
     	| if(key = v) >> q.sem?.release() >> (p,d,q)
     	| if(key > v) >> p.sem?.release() >> isearchloop(q,true,q.right?,key)
     	)
 	{- Goal for searchstart: -}
 	tsent.sem?.acquire() >> isearchloop(tsent,false,tsent.left?,key)
 
 

{- Return true if key is in the tree, false otherwise. -}
def search(key) = 
   def searchreader() = searchstart(key)
   val (_,_,q) = reader(searchreader)
   (q /= null)


{- return true if value was inserted, false if it was already there. -}
def insert(key) = 
	def insertreader() =
   		isearchstart(key) >(p,d,q)> 
   		(  if (q = null)
   			then singleton(key) >r> update(p,d,r)
   			else signal 
		) >> 
   		p.sem?.release() >>
   		(q = null)
   reader(insertreader)


def delete(key) =
  	def isucc(p) =
      {- 
      	 In-order successor of p. p has genuine left and right sons.
         Returns (s,d,t) where t is the d-child of s.
         t is the in-order successor of s, t.left = null
         t is the leftmost genuine (non-sentinel) node in the right subtree of p.
      -}
      def leftmost(p,d,q) =
          {-
          	Given q is the d-child of p and q /= null.
      		Return (p',d,q') where q' is the d-child of p' and q'.left = null
      		Either (p,q) = (p',q') or (p',q') is in the leftmost path in
      		the subtree rooted at q.
      	  -}
      	  q.left? >l> (if l = null then (p,d,q) else leftmost(q,false,l))
  	  {- Goal of isucc: -}
  	  leftmost(p,true,p.right?)

 	def del() =
 		val (p,d,q) = searchstart(key)
 		if(q = null) then {- key is not in -} false
 		else 
 			{- q /= null -}
 			(
 				{- Return v if v is not null, otherwise halt. -}
				def notnull(v) = if(v /= null) >> v
 				val l = notnull(q.left?)
 				val r = notnull(q.right?)
 		
 				{- q has two children -}
 				(l,r) >> 
 		  	  	isucc(q) >(u,d,t)> 
 		  	  	q.val := t.val? >> 
 		  	  	update(u,d,t.right?)
 		
 				{- q has at most one child -}
 				; l >> update(p,d,l) 
 				; r >> update(p,d,r)
 		
 				{- q has no children, -}
 				; update(p,d,null)
  			) >> 
  			true
  			
  	{- Goal of delete: -}
	writer(del)


def inorder() =
	def traverse(t) =
		if (t = null) 
			then [] 
			else append(traverse(t.left?), append([t.val?], traverse(t.right?)))
	writer(lambda () = traverse(tsent.left?))
	


(4 | 6 | 10 | 8 | 5 | 3) >i> insert(i) >> stop ;
println(inorder()) >> stop ;
(5 | 6 | 10 | 3 | 4) >i> delete(i) >> stop ;
println(inorder()) >> stop ;
(3 | 4 | 5 | 6 | 8 | 10) >i> println(cat(i, if search(i) then " is in the tree" else " was not found")) >> stop ;
quit()


)

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-1) was last changed on 25-Nov-2008 17:02 by David