vendor/github.com/tendermint/tmlibs/clist/clist.go

   1 package clist
   2
   3 /*
   4 The purpose of CList is to provide a goroutine-safe linked-list.
   5 This list can be traversed concurrently by any number of goroutines.
   6 However, removed CElements cannot be added back.
   7 NOTE: Not all methods of container/list are (yet) implemented.
   8 NOTE: Removed elements need to DetachPrev or DetachNext consistently
   9 to ensure garbage collection of removed elements.
  10 */
  11
  12 import (
  13         "sync"
  14         "sync/atomic"
  15         "unsafe"
  16 )
  17
  18 // CElement is an element of a linked-list
  19 // Traversal from a CElement are goroutine-safe.
  20 type CElement struct {
  21         prev    unsafe.Pointer
  22         prevWg  *sync.WaitGroup
  23         next    unsafe.Pointer
  24         nextWg  *sync.WaitGroup
  25         removed uint32
  26         Value   interface{}
  27 }
  28
  29 // Blocking implementation of Next().
  30 // May return nil iff CElement was tail and got removed.
  31 func (e *CElement) NextWait() *CElement {
  32         for {
  33                 e.nextWg.Wait()
  34                 next := e.Next()
  35                 if next == nil {
  36                         if e.Removed() {
  37                                 return nil
  38                         } else {
  39                                 continue
  40                         }
  41                 } else {
  42                         return next
  43                 }
  44         }
  45 }
  46
  47 // Blocking implementation of Prev().
  48 // May return nil iff CElement was head and got removed.
  49 func (e *CElement) PrevWait() *CElement {
  50         for {
  51                 e.prevWg.Wait()
  52                 prev := e.Prev()
  53                 if prev == nil {
  54                         if e.Removed() {
  55                                 return nil
  56                         } else {
  57                                 continue
  58                         }
  59                 } else {
  60                         return prev
  61                 }
  62         }
  63 }
  64
  65 // Nonblocking, may return nil if at the end.
  66 func (e *CElement) Next() *CElement {
  67         return (*CElement)(atomic.LoadPointer(&e.next))
  68 }
  69
  70 // Nonblocking, may return nil if at the end.
  71 func (e *CElement) Prev() *CElement {
  72         return (*CElement)(atomic.LoadPointer(&e.prev))
  73 }
  74
  75 func (e *CElement) Removed() bool {
  76         return atomic.LoadUint32(&(e.removed)) > 0
  77 }
  78
  79 func (e *CElement) DetachNext() {
  80         if !e.Removed() {
  81                 panic("DetachNext() must be called after Remove(e)")
  82         }
  83         atomic.StorePointer(&e.next, nil)
  84 }
  85
  86 func (e *CElement) DetachPrev() {
  87         if !e.Removed() {
  88                 panic("DetachPrev() must be called after Remove(e)")
  89         }
  90         atomic.StorePointer(&e.prev, nil)
  91 }
  92
  93 func (e *CElement) setNextAtomic(next *CElement) {
  94         for {
  95                 oldNext := atomic.LoadPointer(&e.next)
  96                 if !atomic.CompareAndSwapPointer(&(e.next), oldNext, unsafe.Pointer(next)) {
  97                         continue
  98                 }
  99                 if next == nil && oldNext != nil { // We for-loop in NextWait() so race is ok
 100                         e.nextWg.Add(1)
 101                 }
 102                 if next != nil && oldNext == nil {
 103                         e.nextWg.Done()
 104                 }
 105                 return
 106         }
 107 }
 108
 109 func (e *CElement) setPrevAtomic(prev *CElement) {
 110         for {
 111                 oldPrev := atomic.LoadPointer(&e.prev)
 112                 if !atomic.CompareAndSwapPointer(&(e.prev), oldPrev, unsafe.Pointer(prev)) {
 113                         continue
 114                 }
 115                 if prev == nil && oldPrev != nil { // We for-loop in PrevWait() so race is ok
 116                         e.prevWg.Add(1)
 117                 }
 118                 if prev != nil && oldPrev == nil {
 119                         e.prevWg.Done()
 120                 }
 121                 return
 122         }
 123 }
 124
 125 func (e *CElement) setRemovedAtomic() {
 126         atomic.StoreUint32(&(e.removed), 1)
 127 }
 128
 129 //--------------------------------------------------------------------------------
 130
 131 // CList represents a linked list.
 132 // The zero value for CList is an empty list ready to use.
 133 // Operations are goroutine-safe.
 134 type CList struct {
 135         mtx  sync.Mutex
 136         wg   *sync.WaitGroup
 137         head *CElement // first element
 138         tail *CElement // last element
 139         len  int       // list length
 140 }
 141
 142 func (l *CList) Init() *CList {
 143         l.mtx.Lock()
 144         defer l.mtx.Unlock()
 145         l.wg = waitGroup1()
 146         l.head = nil
 147         l.tail = nil
 148         l.len = 0
 149         return l
 150 }
 151
 152 func New() *CList { return new(CList).Init() }
 153
 154 func (l *CList) Len() int {
 155         l.mtx.Lock()
 156         defer l.mtx.Unlock()
 157         return l.len
 158 }
 159
 160 func (l *CList) Front() *CElement {
 161         l.mtx.Lock()
 162         defer l.mtx.Unlock()
 163         return l.head
 164 }
 165
 166 func (l *CList) FrontWait() *CElement {
 167         for {
 168                 l.mtx.Lock()
 169                 head := l.head
 170                 wg := l.wg
 171                 l.mtx.Unlock()
 172                 if head == nil {
 173                         wg.Wait()
 174                 } else {
 175                         return head
 176                 }
 177         }
 178 }
 179
 180 func (l *CList) Back() *CElement {
 181         l.mtx.Lock()
 182         defer l.mtx.Unlock()
 183         return l.tail
 184 }
 185
 186 func (l *CList) BackWait() *CElement {
 187         for {
 188                 l.mtx.Lock()
 189                 tail := l.tail
 190                 wg := l.wg
 191                 l.mtx.Unlock()
 192                 if tail == nil {
 193                         wg.Wait()
 194                 } else {
 195                         return tail
 196                 }
 197         }
 198 }
 199
 200 func (l *CList) PushBack(v interface{}) *CElement {
 201         l.mtx.Lock()
 202         defer l.mtx.Unlock()
 203
 204         // Construct a new element
 205         e := &CElement{
 206                 prev:   nil,
 207                 prevWg: waitGroup1(),
 208                 next:   nil,
 209                 nextWg: waitGroup1(),
 210                 Value:  v,
 211         }
 212
 213         // Release waiters on FrontWait/BackWait maybe
 214         if l.len == 0 {
 215                 l.wg.Done()
 216         }
 217         l.len += 1
 218
 219         // Modify the tail
 220         if l.tail == nil {
 221                 l.head = e
 222                 l.tail = e
 223         } else {
 224                 l.tail.setNextAtomic(e)
 225                 e.setPrevAtomic(l.tail)
 226                 l.tail = e
 227         }
 228
 229         return e
 230 }
 231
 232 // CONTRACT: Caller must call e.DetachPrev() and/or e.DetachNext() to avoid memory leaks.
 233 // NOTE: As per the contract of CList, removed elements cannot be added back.
 234 func (l *CList) Remove(e *CElement) interface{} {
 235         l.mtx.Lock()
 236         defer l.mtx.Unlock()
 237
 238         prev := e.Prev()
 239         next := e.Next()
 240
 241         if l.head == nil || l.tail == nil {
 242                 panic("Remove(e) on empty CList")
 243         }
 244         if prev == nil && l.head != e {
 245                 panic("Remove(e) with false head")
 246         }
 247         if next == nil && l.tail != e {
 248                 panic("Remove(e) with false tail")
 249         }
 250
 251         // If we're removing the only item, make CList FrontWait/BackWait wait.
 252         if l.len == 1 {
 253                 l.wg.Add(1)
 254         }
 255         l.len -= 1
 256
 257         // Connect next/prev and set head/tail
 258         if prev == nil {
 259                 l.head = next
 260         } else {
 261                 prev.setNextAtomic(next)
 262         }
 263         if next == nil {
 264                 l.tail = prev
 265         } else {
 266                 next.setPrevAtomic(prev)
 267         }
 268
 269         // Set .Done() on e, otherwise waiters will wait forever.
 270         e.setRemovedAtomic()
 271         if prev == nil {
 272                 e.prevWg.Done()
 273         }
 274         if next == nil {
 275                 e.nextWg.Done()
 276         }
 277
 278         return e.Value
 279 }
 280
 281 func waitGroup1() (wg *sync.WaitGroup) {
 282         wg = &sync.WaitGroup{}
 283         wg.Add(1)
 284         return
 285 }