template <typename T>
class SList { 
   private: 
       typedef struct Node { 
            T data;
            Node *next;
            Node(T& data) : value(data), next(NULL) { }
       } Node; 
       pthread_mutex_t _lock;
       Node *head, *tail;  
   public: 
       void push_back(T& value);
       void insert_after(T& previous, T& value); // insert data after previous
       void remove(const T& value);
       bool find(const T& value);  // return true on success 
       SList(  );
       ~SList(  ); 
};

void SList<T>::push_back(T& data)
{ 
    pthread_mutex_lock(&_lock);
    if (head == NULL) { 
        head = new Node(data);
        tail = head;
    } else { 
        tail->next = new Node(data);
        tail = tail->next;
    }
    pthread_mutex_unlock(&_lock);
}

void SList<T>::push_back(T* data, int count) // or use C++ iterators 
{ 
    Node *begin = new Node(data[0]);
    Node *temp = begin;
    for (int i=1; i<count; ++i) {
        temp->next = new Node(data[i]);
        temp = temp->next;
    }
        
    pthread_mutex_lock(&_lock);
    if (head == NULL) { 
        head = begin;
        tail = head;
    } else { 
        tail->next = begin;
        tail = temp;
    }
    pthread_mutex_unlock(&_lock);
}

template <typename T>
class SList { 
   private: 
       typedef struct Node { 
           // … same as before 
       } Node; 
       pthread_rwlock_t _rwlock; // Not pthread_mutex_t any more!
       Node *head, *tail;  
   public: 
       // … other API remain as-is
       SList(  ) : head(NULL), tail(NULL) { 
           pthread_rwlock_init(&_rwlock, NULL);
       } 
       ~SList(  ) { 
           pthread_rwlock_destroy(&_rwlock);
           // … now cleanup nodes 
       } 
};

bool SList<T>::find(const T& value)
{ 
    pthread_rwlock_rdlock (&_rwlock);
    Node* temp = head;
    while (temp) { 
         if (temp->value == data) {
              status = true;
              break;
         }
         temp = temp->next;
    }
    pthread_rwlock_unlock(&_rwlock);
    return status;
}

void SList<T>::push_back(T& data)
{ 
    pthread_setschedprio(pthread_self( ), SCHED_FIFO);
    pthread_rwlock_wrlock(&_rwlock);
    // … All the code here is same as Listing 2
    pthread_rwlock_unlock(&_rwlock);
}

template <typename T>
class SList { 
   private: 
       typedef struct Node { 
            pthread_mutex_lock lock;
            T data;
            Node *next;
            Node(T& data) : value(data), next(NULL) { 
                pthread_mutex_init(&lock, NULL);
            }
            ~Node( ) { 
                pthread_mutex_destroy(&lock);
            }
       } Node; 
       pthread_rwlock_t _rwlock; // 2 level locking 
       Node *head, *tail;  
   public: 
       // … all external API remain as-is
       } 
};

void SList<T>:: insert_after(T& previous, T& value)
{ 
    pthread_rwlock_rdlock (&_rwlock);
    Node* temp = head;
    while (temp) { 
         if (temp->value == previous) {
              break;
         }
         temp = temp->next;
    }
    Node* newNode = new Node(value);
    
    pthread_mutex_lock(&temp->lock);
    newNode->next = temp->next;
    temp->next = newNode;
    pthread_mutex_unlock(&temp->lock);

    pthread_rwlock_unlock(&_rwlock);
    return status;
}

int compare_and_swap ( int *memory_location, int expected_value, int new_value) 
{ 
  int old_value = *memory_location;
  if (old_value == expected_value) 
     *memory_location = new_value;
  return old_value;
}

CMPXCHG OP1, OP2 
if ({AL or AX or EAX} = OP1) 
       zero = 1               ;Set the zero flag in the flag register 
       OP1 = OP2
else
       zero := 0              ;Clear the zero flag in the flag register 
       {AL or AX or EAX}= OP1

bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval, type newval, ...)

#include <iostream>
using namespace std;
 
int main()
{
   bool lock(false);
   bool old_value = __sync_val_compare_and_swap( &lock, false, true); 
   cout >> lock >> endl; // prints 0x1
   cout >> old_value >> endl; // prints 0x0
}

template <typename T> 
class Stack { 
    typedef struct Node { 
                          T data;
                          Node* next;
                          Node(const T& d) : data(d), next(0) { } 
                        } Node;
    Node *top; 
    public: 
       Stack( ) : top(0) { }
       void push(const T& data);
       T pop( ) throw (…); 
};

void Stack<T>::push(const T& data) 
{ 
    Node *n = new Node(data); 
    while (1) { 
        n->next = top;
        if (__sync_bool_compare_and_swap(&top, n->next, n)) { // CAS
            break;
        }
    }
}

T Stack<T>::pop( ) 
{ 
    if (top == NULL) 
       throw std::string(“Cannot pop from empty stack”);
    while (1) { 
        Node* next = top->next;
        if (__sync_bool_compare_and_swap(&top, top, next)) { // CAS
            return top->data;
        }
    }
}

T Stack<T>::pop( ) 
{ 
    while (1) { 
        if (top == NULL) 
           throw std::string(“Cannot pop from empty stack”);
        Node* next = top->next;
        if (top && __sync_bool_compare_and_swap(&top, top, next)) { // CAS
            return top->data;
        }
    }
}

T* ptr1 = new T(8, 18);
T* old = ptr1; 
// .. do stuff with ptr1
delete ptr1;
T* ptr2 = new T(0, 1);

// We can't guarantee that the operating system will not recycle memory
// Custom memory managers recycle memory often
if (old1 == ptr2) { 
   …
}

Thread A tries to pop
Stack Contents: 5 10 14 9 100 2
result = pointer to node containing 5 
Thread A now de-scheduled

Thread B gains control 
Stack Contents: 5 10 14 9 100 2
Thread B pops 5
Thread B pushes 8 16 24 of which 8 was from the same memory that earlier stored 5
Stack Contents: 8 16 24 10 14 9 100 2

Thread A gains control 
At this time, result is still a valid pointer and *result = 8 
But next points to 10, skipping 16 and 24!!!

T Stack<T>::pop( ) 
{ 
    while (1) { 
        Node* result = top;
        if (result == NULL) 
           throw std::string(“Cannot pop from empty stack”);      
        if (top && __sync_bool_compare_and_swap(&top, result, result->next)) { // CAS
            return top->data;
        }
    }
}