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: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45:

open System
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

(* Usage Example *)

type ObservableSource<'a>() =
    let subscriptionList = MutableList<IObserver<'a>>.empty        
    interface IObservable<'a> with
        member x.Subscribe observer =
            subscriptionList.Add observer |> ignore
            { new IDisposable with
                member x.Dispose() = subscriptionList.Remove observer |> ignore
            }

    member x.Complete() = subscriptionList.Value |> List.iter (fun obs -> obs.OnCompleted())
    member x.Push data = subscriptionList.Value |> List.iter (fun observer -> observer.OnNext data)
    member x.Error exn = subscriptionList.Value |> List.iter (fun obs -> obs.OnError exn)

    static member create() = new ObservableSource<'a>()
    static member get (source:ObservableSource<'a>) = source :> IObservable<'a>

let source = ObservableSource<int>()
source |> Observable.subscribe (fun i -> printfn "%d" i) |> ignore

source.Push 123   // 123 should be printed.

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 = Object

Full name: Microsoft.FSharp.Core.obj

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>

Multiple items
type ObservableSource<'a> =
  interface IObservable<'a>
  new : unit -> ObservableSource<'a>
  member Complete : unit -> unit
  member Error : exn:exn -> unit
  member Push : data:'a -> unit
  static member create : unit -> ObservableSource<'a>
  static member get : source:ObservableSource<'a> -> IObservable<'a>

Full name: Script.ObservableSource<_>

--------------------
new : unit -> ObservableSource<'a>

val subscriptionList : MutableList<IObserver<'a>>

type IObserver<'T> =
  member OnCompleted : unit -> unit
  member OnError : error:Exception -> unit
  member OnNext : value:'T -> unit

Full name: System.IObserver<_>

type IObservable<'T> =
member Subscribe : observer:IObserver<'T> -> IDisposable

Full name: System.IObservable<_>

val x : ObservableSource<'a>

override ObservableSource.Subscribe : observer:IObserver<'a> -> IDisposable

Full name: Script.ObservableSource`1.Subscribe

val observer : IObserver<'a>

val ignore : value:'T -> unit

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

type IDisposable =
member Dispose : unit -> unit

Full name: System.IDisposable

val x : IDisposable

IDisposable.Dispose() : unit

member ObservableSource.Complete : unit -> unit

Full name: Script.ObservableSource`1.Complete

property MutableList.Value: IObserver<'a> list

val iter : action:('T -> unit) -> list:'T list -> unit

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

val obs : IObserver<'a>

IObserver.OnCompleted() : unit

member ObservableSource.Push : data:'a -> unit

Full name: Script.ObservableSource`1.Push

val data : 'a

IObserver.OnNext(value: 'a) : unit

member ObservableSource.Error : exn:exn -> unit

Full name: Script.ObservableSource`1.Error

Multiple items
val exn : exn

--------------------
type exn = Exception

Full name: Microsoft.FSharp.Core.exn

IObserver.OnError(error: exn) : unit

static member ObservableSource.create : unit -> ObservableSource<'a>

Full name: Script.ObservableSource`1.create

static member ObservableSource.get : source:ObservableSource<'a> -> IObservable<'a>

Full name: Script.ObservableSource`1.get

val source : ObservableSource<'a>

val source : ObservableSource<int>

Full name: Script.source

Multiple items
val int : value:'T -> int (requires member op_Explicit)

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

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

module Observable

from Microsoft.FSharp.Control

val subscribe : callback:('T -> unit) -> source:IObservable<'T> -> IDisposable

Full name: Microsoft.FSharp.Control.Observable.subscribe

val i : int

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

member ObservableSource.Push : data:'a -> unit

Previous 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