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.