Code archives/Algorithms/Synchronized Data Structures

SuperStrict

Rem
bbdoc: Synchronized Linked List
End Rem
'Module Otus.SynchronizedList

'ModuleInfo "Version: 1.00"
'ModuleInfo "Author: Jan Varho"
'ModuleInfo "License: Public domain"

Import BRL.LinkedList

?threaded
Import BRL.Threads
?

Rem
bbdoc: Synchronized Linked List
about:
TSynchronizedList implements atomic operations using a mutex 
so that every operation finishes before another can begin.

Caveats:

Operations on TLinks are not automatically thread safe! If you 
need to operate on TLinks in a thread-safe way, #Lock the list 
*before* aquiring a TLink reference. The same method can be 
used to atomize a sequence of operations.

Enumeration locks the list. Exiting from a For-EachIn loop can 
leave the list locked until GC happens! (So other threads 
cannot access it.)

Swap with a non-Synchronized TList is only atomic if invoked 
on the TSynchronizedList. Ie. slist.Swap(list) is, but 
list.Swap(slist) is not Synchronized.
End Rem
Type TSynchronizedList Extends TList
?threaded
	Field _mutex:TMutex
	
	Method New()
		_mutex = CreateMutex()
	End Method
	
	Method Delete()
		CloseMutex _mutex
	End Method
	
	Rem
	bbdoc: Lock the list
	about: A locked list cannot be used in other threads
	End Rem
	Method Lock()
		_mutex.Lock
	End Method
	
	Rem
	bbdoc: Try to lock the list
	returns: True on success
	about: A locked list cannot be used in other threads
	End Rem
	Method TryLock%()
		Return _mutex.TryLock()
	End Method
	
	Rem
	bbdoc: Unlock the list
	End Rem
	Method Unlock()
		_mutex.Unlock
	End Method
	
	Method Clear()
		_mutex.Lock
		Super.Clear
		_mutex.Unlock
	End Method
	
	Method IsEmpty%()
		_mutex.Lock
		Local ret% = Super.IsEmpty()
		_mutex.Unlock
		Return ret
	End Method
	
	Method Contains%( value:Object )
		_mutex.Lock
		Local ret% = Super.Contains(value)
		_mutex.Unlock
		Return ret
	End Method
	
	Method AddFirst:TLink( value:Object )
		_mutex.Lock
		Local ret:TLink = Super.AddFirst(value)
		_mutex.Unlock
		Return ret
	End Method
	
	Method AddLast:TLink( value:Object )
		_mutex.Lock
		Local ret:TLink = Super.AddLast(value)
		_mutex.Unlock
		Return ret
	End Method
	
	Method First:Object()
		_mutex.Lock
		Local ret:Object = Super.First()
		_mutex.Unlock
		Return ret
	End Method
	
	Method Last:Object()
		_mutex.Lock
		Local ret:Object = Super.Last()
		_mutex.Unlock
		Return ret
	End Method
	
	Method RemoveFirst:Object()
		_mutex.Lock
		Local ret:Object = Super.RemoveFirst()
		_mutex.Unlock
		Return ret
	End Method
	
	Method RemoveLast:Object()
		_mutex.Lock
		Local ret:Object = Super.RemoveLast()
		_mutex.Unlock
		Return ret
	End Method
	
	Method ValueAtIndex:Object( index% )
		_mutex.Lock
		Local ret:Object
		' Throws runtime errors, which we catch to unlock mutex
		Try
			ret = Super.ValueAtIndex(index)
		Catch o:Object
			_mutex.Unlock
			Throw o
		End Try
		_mutex.Unlock
		Return ret
	End Method
	
	Method Count%()
		_mutex.Lock
		Local ret%= Super.Count()
		_mutex.Unlock
		Return ret
	End Method
	
	Method Remove%( value:Object )
		_mutex.Lock
		Local ret% = Super.Remove(value)
		_mutex.Unlock
		Return ret
	End Method
	
	Method Swap( list:TList )
		If Self=list Return
		Local alist:TSynchronizedList = TSynchronizedList(list)
		If alist
			' Comparison solves race condition
			'  on attempting swap on both lists.
			'  Multi-way race conditions are
			'  likewise solved.
			If Self.Compare(alist) < 0
				_mutex.Lock
				alist._mutex.Lock
				Super.Swap(list)
				alist._mutex.Unlock
				_mutex.Unlock
			Else
				alist._mutex.Lock
				_mutex.Lock
				Super.Swap(list)
				_mutex.Unlock
				alist._mutex.Unlock
			End If
		Else
			_mutex.Lock
			Super.Swap(list)
			_mutex.Unlock
		End If
	End Method
	
	Method Copy:TList()
		_mutex.Lock
		Local list:TList = Super.Copy()
		_mutex.Unlock
		Local ret:TList = New TSynchronizedList
		list.Swap ret
		Return ret
	End Method
	
	Method Reverse()
		_mutex.Lock
		Super.Reverse()
		_mutex.Unlock
	End Method
	
	Method Reversed:TList()
		_mutex.Lock
		Local list:TList = Super.Reversed()
		_mutex.Unlock
		Local ret:TList = New TSynchronizedList
		list.Swap ret
		Return ret
	End Method
	
	Method Sort( ascending%=True,compareFunc%( o1:Object,o2:Object )=CompareObjects )
		_mutex.Lock
		Super.Sort(ascending, compareFunc)
		_mutex.Unlock
	End Method
	
	Method ObjectEnumerator:TListEnum()
		' Leaves the mutex locked! See enum.Delete
		_mutex.Lock
		Local enum:TSynchronizedListEnum = New TSynchronizedListEnum
		enum._link = _head._succ
		enum._mutex = _mutex
		Return enum
	End Method
	
	Method ToArray:Object[]()
		_mutex.Lock
		Local ret:Object[] = Super.ToArray()
		_mutex.Unlock
		Return ret
	End Method
	
	Function FromArray:TList( arr:Object[] )
		Local list:TList = TList.FromArray(arr)
		Local ret:TSynchronizedList = New TSynchronizedList
		ret.Swap list
		Return ret
	End Function
?Not threaded
	' Dummy methods
	Method Lock()
	End Method
	
	Method TryLock%()
		Return True
	End Method
	
	Method Unlock()
	End Method
?
End Type

?threaded
Type TSynchronizedListEnum Extends TListEnum
	
	Field _mutex:TMutex
	
	Method Delete()
		' Safeguard for incomplete enumeration
		If _mutex Then _mutex.Unlock
	End Method
	
	Method HasNext%()
		If Super.HasNext() Then Return True
		If _mutex
			_mutex.Unlock
			_mutex = Null
		End If
		Return False
	End Method
	
End Type
?

Rem
bbdoc: Create a synchronized list
returns: A new synchronized list object
End Rem
Function CreateSynchronizedList:TSynchronizedList()
	Return New TSynchronizedList
End Function

SuperStrict

Rem
bbdoc: Synchronized Map
End Rem
'Module Otus.SynchronizedMap

'ModuleInfo "Version: 1.00"
'ModuleInfo "Author: Jan Varho"
'ModuleInfo "License: Public domain"

Import BRL.Map

?threaded
Import BRL.Threads
?

Rem
bbdoc: Synchronized Map
about:
TSynchronizedMap implements atomic operations using a mutex so 
that every operation finishes before another can begin.

Note: Enumeration locks the list. Exiting from a For-EachIn 
loop can leave the list locked until GC happens.

#Lock, #TryLock and #Unlock can be used to make a sequence of 
operations atomic.
End Rem
Type TSynchronizedMap Extends TMap
?threaded
	Field _mutex:TMutex 
	
	Method New()
		_mutex = CreateMutex()
	End Method
	
	Method Delete()
		CloseMutex _mutex
	End Method
	
	Rem
	bbdoc: Lock the map
	about: A locked map cannot be used in other threads
	End Rem
	Method Lock()
		_mutex.Lock
	End Method
	
	Rem
	bbdoc: Try to lock the map
	returns: True on success
	about: A locked map cannot be used in other threads
	End Rem
	Method TryLock%()
		Return _mutex.TryLock()
	End Method
	
	Rem
	bbdoc: Unlock the map
	End Rem
	Method Unlock()
		_mutex.Unlock
	End Method
	
	Method Clear()
		_mutex.Lock
		Super.Clear
		_mutex.Unlock
	End Method
	
	Method IsEmpty%()
		_mutex.Lock
		Local ret% = Super.IsEmpty()
		_mutex.Unlock
		Return ret
	End Method
	
	Method Insert( key:Object,value:Object )
		_mutex.Lock
		Super.Insert key, value
		_mutex.Unlock
	End Method
	
	Method Contains%( key:Object )
		_mutex.Lock
		Local ret% = Super.Contains(key)
		_mutex.Unlock
		Return ret
	End Method

	Method ValueForKey:Object( key:Object )
		_mutex.Lock
		Local ret:Object = Super.ValueForKey(key)
		_mutex.Unlock
		Return ret
	End Method
	
	Method Remove%( key:Object )
		_mutex.Lock
		Local ret% = Super.Remove(key)
		_mutex.Unlock
		Return ret
	End Method
	
	Method Keys:TMapEnumerator()
		' Leaves the map locked! See enum.Delete
		_mutex.Lock
		Local enum:TSynchronizedKeyEnumerator = New TSynchronizedKeyEnumerator
		enum._node = _FirstNode()
		enum._mutex = _mutex
		Local menum:TMapEnumerator = New TMapEnumerator
		menum._enumerator = enum
		Return menum
	End Method
	
	Method Values:TMapEnumerator()
		' Leaves the map locked! See enum.Delete
		_mutex.Lock
		Local enum:TSynchronizedValueEnumerator = New TSynchronizedValueEnumerator
		enum._node = _FirstNode()
		enum._mutex = _mutex
		Local menum:TMapEnumerator = New TMapEnumerator
		menum._enumerator = enum
		Return menum
	End Method
	
	Method Copy:TMap()
		_mutex.Lock
		Local map:TMap = Super.Copy()
		_mutex.Unlock
		Local ret:TSynchronizedMap = New TSynchronizedMap
		Local r:TNode = ret._root
		ret._root = map._root
		map._root = r
		Return ret
	End Method
	
	Method ObjectEnumerator:TNodeEnumerator()
		' Leaves the map locked! See enum.Delete
		_mutex.Lock
		Local enum:TSynchronizedNodeEnumerator = New TSynchronizedNodeEnumerator
		enum._node = _FirstNode()
		enum._mutex = _mutex
		Return enum
	End Method
?Not threaded
	' Dummy methods
	Method Lock()
	End Method
	
	Method TryLock%()
		Return True
	End Method
	
	Method Unlock()
	End Method
?
End Type

?threaded
Type TSynchronizedNodeEnumerator Extends TNodeEnumerator
	
	Field _mutex:TMutex
	
	Method Delete()
		' Safeguard against incomplete enumeration
		If _mutex Then _mutex.Unlock
	End Method
	
	Method HasNext%()
		If Super.HasNext() Then Return True
		If _mutex
			_mutex.Unlock
			_mutex = Null
		End If
		Return False
	End Method
	
End Type

Type TSynchronizedKeyEnumerator Extends TKeyEnumerator
	
	Field _mutex:TMutex
	
	Method Delete()
		' Safeguard against incomplete enumeration
		If _mutex Then _mutex.Unlock
	End Method
	
	Method HasNext%()
		If Super.HasNext() Then Return True
		If _mutex
			_mutex.Unlock
			_mutex = Null
		End If
		Return False
	End Method
	
End Type

Type TSynchronizedValueEnumerator Extends TValueEnumerator
	
	Field _mutex:TMutex
	
	Method Delete()
		' Safeguard against incomplete enumeration
		If _mutex Then _mutex.Unlock
	End Method
	
	Method HasNext%()
		If Super.HasNext() Then Return True
		If _mutex
			_mutex.Unlock
			_mutex = Null
		End If
		Return False
	End Method
	
End Type
?

Rem
bbdoc: Create a synchronized map
returns: A new map object
End Rem
Function CreateSynchronizedMap:TSynchronizedMap()
	Return New TSynchronizedMap
End Function