Changeset 2d95a2d for libcfa/src/containers/queueLockFree.hfa
- Timestamp:
- Mar 26, 2021, 5:57:52 PM (3 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- cd26abf
- Parents:
- bd0bdd37
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/containers/queueLockFree.hfa
rbd0bdd37 r2d95a2d 20 20 // Adds an element to the list 21 21 // Multi-Thread Safe, Lock-Free 22 T * push(mcs_queue(T) & this, T & elem) { 23 /* paranoid */ verify(!(&elem)`next); 22 T * push(mcs_queue(T) & this, T * elem) __attribute__((artificial)); 23 T * push(mcs_queue(T) & this, T * elem) { 24 /* paranoid */ verify(!(elem`next)); 24 25 // Race to add to the tail 25 T * prev = __atomic_exchange_n(&this.tail, &elem, __ATOMIC_SEQ_CST);26 T * prev = __atomic_exchange_n(&this.tail, elem, __ATOMIC_SEQ_CST); 26 27 // If we aren't the first, we need to tell the person before us 27 28 // No need to 28 if (prev) prev`next = &elem;29 if (prev) prev`next = elem; 29 30 return prev; 30 31 } … … 33 34 // Passing an element that is not the head is undefined behavior 34 35 // NOT Multi-Thread Safe, concurrent pushes are safe 35 T * advance(mcs_queue(T) & this, T & elem) { 36 T * expected = &elem; 36 T * advance(mcs_queue(T) & this, T * elem) __attribute__((artificial)); 37 T * advance(mcs_queue(T) & this, T * elem) { 38 T * expected = elem; 37 39 // Check if this is already the last item 38 40 if (__atomic_compare_exchange_n(&this.tail, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) return 0p; 39 41 40 // If not wait for next item to show-up 41 // added by push 42 while (!(&elem)`next) Pause(); 43 return (&elem)`next; 42 // If not wait for next item to show-up, filled by push 43 while (!(elem`next)) Pause(); 44 45 // we need to return if the next link was empty 46 T * ret = elem`next; 47 48 // invalidate link to reset to initial state 49 elem`next = 0p; 50 return ret; 44 51 } 45 52 } … … 64 71 // Added a new element to the queue 65 72 // Multi-Thread Safe, Lock-Free 66 T * push(mpsc_queue(T) & this, T & elem) { 73 T * push(mpsc_queue(T) & this, T * elem) __attribute__((artificial)); 74 T * push(mpsc_queue(T) & this, T * elem) { 67 75 T * prev = push((mcs_queue(T)&)this, elem); 68 if (!prev) this.head = &elem;76 if (!prev) this.head = elem; 69 77 return prev; 70 78 } … … 74 82 // next is set to the new head of the queue 75 83 // NOT Multi-Thread Safe 84 T * pop(mpsc_queue(T) & this, T *& next) __attribute__((artificial)); 76 85 T * pop(mpsc_queue(T) & this, T *& next) { 77 86 T * elem = this.head; … … 84 93 // force memory sync 85 94 __atomic_thread_fence(__ATOMIC_SEQ_CST); 95 96 // invalidate link to reset to initial state 97 elem`next = 0p; 86 98 } 87 99 // Otherwise, there might be a race where it only looks but someone is enqueuing … … 91 103 // after that point, it could overwrite the write in push 92 104 this.head = 0p; 93 next = advance((mcs_queue(T)&)this, (*elem));105 next = advance((mcs_queue(T)&)this, elem); 94 106 95 107 // Only write to the head if there is a next element … … 98 110 if (next) this.head = next; 99 111 } 100 101 // invalidate link102 elem`next = 0p;103 112 104 113 // return removed element
Note: See TracChangeset
for help on using the changeset viewer.