November 28, 2020, 02:18:47 PM

Author Topic: [bmx] Synchronized Data Structures by Otus [ 1+ years ago ]  (Read 630 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : Synchronized Data Structures
Author : Otus
Posted : 1+ years ago

Description : Synchronized implementations of list and map data structures. All operations are made atomic using a mutex. The types extend TList and TMap, so they can be plugged into existing code. Minimal docs are there if installed as a module.

Mutexes currently <a href="../Community/postscc2f.html?topic=84488" target="_blank">work different on Linux and Mac[/url], so some operations may fail without a patch. See comments for other pitfalls.

TSynchronizedList:
Code: [Select]
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


TSynchronizedMap: [/i]

Code :
Code: BlitzMax
  1. SuperStrict
  2.  
  3. Rem
  4. bbdoc: Synchronized Map
  5. End Rem
  6. 'Module Otus.SynchronizedMap
  7.  
  8. 'ModuleInfo "Version: 1.00"
  9. 'ModuleInfo "Author: Jan Varho"
  10. 'ModuleInfo "License: Public domain"
  11.  
  12. Import BRL.Map
  13.  
  14. ?threaded
  15. Import BRL.Threads
  16. ?
  17.  
  18. Rem
  19. bbdoc: Synchronized Map
  20. about:
  21. TSynchronizedMap implements atomic operations using a mutex so
  22. that every operation finishes before another can begin.
  23.  
  24. Note: Enumeration locks the list. Exiting from a For-EachIn
  25. loop can leave the list locked until GC happens.
  26.  
  27. #Lock, #TryLock and #Unlock can be used to make a sequence of
  28. operations atomic.
  29. End Rem
  30. Type TSynchronizedMap Extends TMap
  31. ?threaded
  32.         Field _mutex:TMutex
  33.        
  34.         Method New()
  35.                 _mutex = CreateMutex()
  36.         End Method
  37.        
  38.         Method Delete()
  39.                 CloseMutex _mutex
  40.         End Method
  41.        
  42.         Rem
  43.         bbdoc: Lock the map
  44.         about: A locked map cannot be used in other threads
  45.         End Rem
  46.         Method Lock()
  47.                 _mutex.Lock
  48.         End Method
  49.        
  50.         Rem
  51.         bbdoc: Try to lock the map
  52.         returns: True on success
  53.         about: A locked map cannot be used in other threads
  54.         End Rem
  55.         Method TryLock%()
  56.                 Return _mutex.TryLock()
  57.         End Method
  58.        
  59.         Rem
  60.         bbdoc: Unlock the map
  61.         End Rem
  62.         Method Unlock()
  63.                 _mutex.Unlock
  64.         End Method
  65.        
  66.         Method Clear()
  67.                 _mutex.Lock
  68.                 Super.Clear
  69.                 _mutex.Unlock
  70.         End Method
  71.        
  72.         Method IsEmpty%()
  73.                 _mutex.Lock
  74.                 Local ret% = Super.IsEmpty()
  75.                 _mutex.Unlock
  76.                 Return ret
  77.         End Method
  78.        
  79.         Method Insert( key:Object,value:Object )
  80.                 _mutex.Lock
  81.                 Super.Insert key, value
  82.                 _mutex.Unlock
  83.         End Method
  84.        
  85.         Method Contains%( key:Object )
  86.                 _mutex.Lock
  87.                 Local ret% = Super.Contains(key)
  88.                 _mutex.Unlock
  89.                 Return ret
  90.         End Method
  91.  
  92.         Method ValueForKey:Object( key:Object )
  93.                 _mutex.Lock
  94.                 Local ret:Object = Super.ValueForKey(key)
  95.                 _mutex.Unlock
  96.                 Return ret
  97.         End Method
  98.        
  99.         Method Remove%( key:Object )
  100.                 _mutex.Lock
  101.                 Local ret% = Super.Remove(key)
  102.                 _mutex.Unlock
  103.                 Return ret
  104.         End Method
  105.        
  106.         Method Keys:TMapEnumerator()
  107.                 ' Leaves the map locked! See enum.Delete
  108.                 _mutex.Lock
  109.                 Local enum:TSynchronizedKeyEnumerator = New TSynchronizedKeyEnumerator
  110.                 enum._node = _FirstNode()
  111.                 enum._mutex = _mutex
  112.                 Local menum:TMapEnumerator = New TMapEnumerator
  113.                 menum._enumerator = enum
  114.                 Return menum
  115.         End Method
  116.        
  117.         Method Values:TMapEnumerator()
  118.                 ' Leaves the map locked! See enum.Delete
  119.                 _mutex.Lock
  120.                 Local enum:TSynchronizedValueEnumerator = New TSynchronizedValueEnumerator
  121.                 enum._node = _FirstNode()
  122.                 enum._mutex = _mutex
  123.                 Local menum:TMapEnumerator = New TMapEnumerator
  124.                 menum._enumerator = enum
  125.                 Return menum
  126.         End Method
  127.        
  128.         Method Copy:TMap()
  129.                 _mutex.Lock
  130.                 Local map:TMap = Super.Copy()
  131.                 _mutex.Unlock
  132.                 Local ret:TSynchronizedMap = New TSynchronizedMap
  133.                 Local r:TNode = ret._root
  134.                 ret._root = map._root
  135.                 map._root = r
  136.                 Return ret
  137.         End Method
  138.        
  139.         Method ObjectEnumerator:TNodeEnumerator()
  140.                 ' Leaves the map locked! See enum.Delete
  141.                 _mutex.Lock
  142.                 Local enum:TSynchronizedNodeEnumerator = New TSynchronizedNodeEnumerator
  143.                 enum._node = _FirstNode()
  144.                 enum._mutex = _mutex
  145.                 Return enum
  146.         End Method
  147. ?Not threaded
  148.         ' Dummy methods
  149.         Method Lock()
  150.         End Method
  151.        
  152.         Method TryLock%()
  153.                 Return True
  154.         End Method
  155.        
  156.         Method Unlock()
  157.         End Method
  158. ?
  159. End Type
  160.  
  161. ?threaded
  162. Type TSynchronizedNodeEnumerator Extends TNodeEnumerator
  163.        
  164.         Field _mutex:TMutex
  165.        
  166.         Method Delete()
  167.                 ' Safeguard against incomplete enumeration
  168.                 If _mutex Then _mutex.Unlock
  169.         End Method
  170.        
  171.         Method HasNext%()
  172.                 If Super.HasNext() Then Return True
  173.                 If _mutex
  174.                         _mutex.Unlock
  175.                         _mutex = Null
  176.                 End If
  177.                 Return False
  178.         End Method
  179.        
  180. End Type
  181.  
  182. Type TSynchronizedKeyEnumerator Extends TKeyEnumerator
  183.        
  184.         Field _mutex:TMutex
  185.        
  186.         Method Delete()
  187.                 ' Safeguard against incomplete enumeration
  188.                 If _mutex Then _mutex.Unlock
  189.         End Method
  190.        
  191.         Method HasNext%()
  192.                 If Super.HasNext() Then Return True
  193.                 If _mutex
  194.                         _mutex.Unlock
  195.                         _mutex = Null
  196.                 End If
  197.                 Return False
  198.         End Method
  199.        
  200. End Type
  201.  
  202. Type TSynchronizedValueEnumerator Extends TValueEnumerator
  203.        
  204.         Field _mutex:TMutex
  205.        
  206.         Method Delete()
  207.                 ' Safeguard against incomplete enumeration
  208.                 If _mutex Then _mutex.Unlock
  209.         End Method
  210.        
  211.         Method HasNext%()
  212.                 If Super.HasNext() Then Return True
  213.                 If _mutex
  214.                         _mutex.Unlock
  215.                         _mutex = Null
  216.                 End If
  217.                 Return False
  218.         End Method
  219.        
  220. End Type
  221. ?
  222.  
  223. Rem
  224. bbdoc: Create a synchronized map
  225. returns: A new map object
  226. End Rem
  227. Function CreateSynchronizedMap:TSynchronizedMap()
  228.         Return New TSynchronizedMap
  229. End Function


Comments :


N(Posted 1+ years ago)

 Edit: Eh, don't like my changes - will repost later when I come up with a nicer solution.


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal