Lock-free, mutable list

Lock-free, mutable list that supports multi-threading scenarios.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21:

open System.Threading

type MutableList<'item when 'item:equality>(init) =
    let mutable items: 'item list = init

    member x.Value = items

    member x.Update updater =
        let current = items
        let newItems = updater current
        if not <| obj.ReferenceEquals(current, Interlocked.CompareExchange(&items, newItems, current))
            then x.Update updater
            else x

    member x.Add item = x.Update (fun L -> item::L)
    member x.Remove item = x.Update (fun L -> List.filter (fun i -> i <> item) L)

    static member empty = new MutableList<'item>([])
    static member add item (l:MutableList<'item>) = l.Add item
    static member get (l:MutableList<'item>) = l.Value
    static member remove item (l:MutableList<'item>) = l.Remove item

namespace System

namespace System.Threading

Multiple items
type MutableList<'item (requires equality)> =
  new : init:'item list -> MutableList<'item>
  member Add : item:'item -> MutableList<'item>
  member Remove : item:'item -> MutableList<'item>
  member Update : updater:('item list -> 'item list) -> MutableList<'item>
  member Value : 'item list
  static member add : item:'item -> l:MutableList<'item> -> MutableList<'item>
  static member get : l:MutableList<'item> -> 'item list
  static member empty : MutableList<'item>
  static member remove : item:'item -> l:MutableList<'item> -> MutableList<'item>

Full name: Script.MutableList<_>

--------------------
new : init:'item list -> MutableList<'item>

val init : 'item list (requires equality)

val mutable items : 'item list (requires equality)

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

val x : MutableList<'item> (requires equality)

member MutableList.Value : 'item list

Full name: Script.MutableList`1.Value

member MutableList.Update : updater:('item list -> 'item list) -> MutableList<'item>

Full name: Script.MutableList`1.Update

val updater : ('item list -> 'item list) (requires equality)

val current : 'item list (requires equality)

val newItems : 'item list (requires equality)

val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

type obj = System.Object

Full name: Microsoft.FSharp.Core.obj

System.Object.ReferenceEquals(objA: obj, objB: obj) : bool

type Interlocked =
  static member Add : location1:int * value:int -> int + 1 overload
  static member CompareExchange : location1:int * value:int * comparand:int -> int + 6 overloads
  static member Decrement : location:int -> int + 1 overload
  static member Exchange : location1:int * value:int -> int + 6 overloads
  static member Increment : location:int -> int + 1 overload
  static member Read : location:int64 -> int64

Full name: System.Threading.Interlocked

Interlocked.CompareExchange<'T (requires reference type)>(location1: byref<'T>, value: 'T, comparand: 'T) : 'T
Interlocked.CompareExchange(location1: byref<nativeint>, value: nativeint, comparand: nativeint) : nativeint
Interlocked.CompareExchange(location1: byref<obj>, value: obj, comparand: obj) : obj
Interlocked.CompareExchange(location1: byref<float>, value: float, comparand: float) : float
Interlocked.CompareExchange(location1: byref<float32>, value: float32, comparand: float32) : float32
Interlocked.CompareExchange(location1: byref<int64>, value: int64, comparand: int64) : int64
Interlocked.CompareExchange(location1: byref<int>, value: int, comparand: int) : int

member MutableList.Update : updater:('item list -> 'item list) -> MutableList<'item>

member MutableList.Add : item:'item -> MutableList<'item>

Full name: Script.MutableList`1.Add

val item : 'item (requires equality)

val L : 'item list (requires equality)

member MutableList.Remove : item:'item -> MutableList<'item>

Full name: Script.MutableList`1.Remove

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter

val i : 'item (requires equality)

static member MutableList.empty : MutableList<'item>

Full name: Script.MutableList`1.empty

static member MutableList.add : item:'item -> l:MutableList<'item> -> MutableList<'item>

Full name: Script.MutableList`1.add

val l : MutableList<'item> (requires equality)

member MutableList.Add : item:'item -> MutableList<'item>

static member MutableList.get : l:MutableList<'item> -> 'item list

Full name: Script.MutableList`1.get

property MutableList.Value: 'item list

static member MutableList.remove : item:'item -> l:MutableList<'item> -> MutableList<'item>

Full name: Script.MutableList`1.remove

member MutableList.Remove : item:'item -> MutableList<'item>

Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/ok
Posted:	10 years ago
Author:	Ruxo Zheng
Tags:	list , mutable , multithreading