[bmx] Synchronized Data Structures by Otus [ 1+ years ago ]

[BlitzBot]

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.