//  Copyright (c) 2007 by Princeton University
//  Use, modification and distribution are subject to the
//  Boost Software License, Version 1.0.
//
//  file : AtomicPtr.h
//  author : Christian Bienia - cbienia@cs.princeton.edu
//  description : An atomic datatype

// IMPORTANT INFORMATION REGARDING USAGE OF ATOMIC POINTERS:
//
// While an atomic pointer itself can be manipulated through
// the provided methods and operators without having to worry
// about race conditions, this does not imply that the data
// pointed to can be worked with in a similar manner without
// taking further precautions.
//
// For example, the following code is incorrect:
//
// AtomicPtr<int> p(&my_int);
// ...
// (*my_int)++;
//
// The pointer to the integer stored inside p is protected
// against concurrent accesses, but the data stored in my_int
// isn't.
//
// Furthermore, users of the atomic pointer class should not
// assume the pointer remains unchanged between accesses.
//
// For example, the following code is also wrong:
//
// AtomicPtr<my_struct_t> p(&my_struct);
// ...
// int x = (*p).x;
// int y = (*p).y;
//
// Unless further steps have been taken, another thread might
// update p between the loads of x and y, and thus values
// belonging to two different structures are read.
//
// If the referenced data is never updated (i.e. no
// synchronization is required), the code can be rewritten
// to be safe by accessing the atomic pointer only once
// as follows:
//
// AtomicPtr<my_struct_t> p(&my_struct);
// ...
// my_struct_t *temp = p.Get();
// int x = temp->x;
// int y = temp->y;
//
// This has been the rationale behind the design decision to
// implement the dereference operator '*', but not the member
// select operator '->'. Member accesses via an atomic pointer
// are inherently non-atomic as a whole.
//
// The atomic pointer class can be used to synchronize accesses
// to the referenced data if two conditions hold:
//
// 1. Only one thread can have the atomic pointer at any time.
//    The atomic pointer will thus have the semantics of a unique
//    token in the system.
// 2. The correct memory barriers are added to prevent the system
//    from reordering the memory accesses and to achieve full
//    acquire / release semantics. This functionality is only
//    indirectly provided by the AtomicPtr class (see below).
//
// The AtomicPtr class provides two functions - Checkin() and
// Checkout() - which fulfill both conditions and allow the atomic
// pointer to function like a mutex. For each Checkout(), exactly
// one Checkin() must be executed.
//
// For example, a critical section updating the referenced data
// can be protected as follows:
//
// temp = p.Checkout();
// update(temp);
// p.Checkin(temp);
//
// While a pointer is checked out from its AtomicPtr container
// object, all accesses to the AtomicPtr object other than Checkin()
// and the Try*() functions will cause the calling thread to spin
// until a pointer has been checked in again. The Try*() functions
// will return false instead to indicate that the operation could not
// be completed and will return immediately without spinning.
//
// The Checkin() function allows the checkin of any pointer, i.e.
// the new pointer may be different from the one previously checked
// out.

#ifndef ATOMICPTR_H
#define ATOMICPTR_H

//uncomment to compile with additional error checks
#define NDEBUG

#include <cassert>

#ifdef ENABLE_THREADS
#include "atomic/atomic.h"
#endif


namespace threads {

template <typename T>
class AtomicPtr {
  private:
    //the pointer to access atomically and types to use for access (32-bit or 64-bit width)
#if defined(_LP64)
    typedef long unsigned int ATOMIC_TYPE;
    T *p __attribute__ ((aligned (8)));
#else
    typedef unsigned int ATOMIC_TYPE;
    T *p __attribute__ ((aligned (4)));
#endif

    //value to use internally to indicate a temporarily unaccessible pointer
    static const T *ATOMIC_NULL;

    //helper function to set the pointer to a value (without any checks)
    inline T *PrivateSet(T *x) {
      T *val;

#ifdef ENABLE_THREADS
      do {
        val = Get();
      } while(!atomic_cmpset_ptr((ATOMIC_TYPE *)&p, (ATOMIC_TYPE)val, (ATOMIC_TYPE)x));
#else
        val = Get();
        p = x;
#endif //ENABLE_THREADS

      return val;
    }

    //helper function to try to set the pointer to a value (without any checks)
    inline bool TryPrivateSet(T *x, T **y) {
      T *val;
      bool rv;

#ifdef ENABLE_THREADS
      if(!TryGet(&val)) {
        return false;
      }
      rv = atomic_cmpset_ptr((ATOMIC_TYPE *)&p, (ATOMIC_TYPE)val, (ATOMIC_TYPE)x);
      if(rv && (y != NULL)) {
        *y = val;
      }
      return rv;
#else
      assert(p != ATOMIC_NULL);
      *y = p;
      p = x;
      return true;
#endif //ENABLE_THREADS
    }

  public:
    // *** Constructors and Destructors ***

    //regular constructor
    AtomicPtr(T *x) {
      assert(x != ATOMIC_NULL);
      p = x;
    }

    //copy constructor
    AtomicPtr(const AtomicPtr<T> &X) {
      p = X.Get();
    }

    // *** Functions to modify and obtain encapsulated data ***

    //set the pointer to x, return the replaced value
    inline T *Set(T *x) {
      assert(x != ATOMIC_NULL);
      return PrivateSet(x);
    }

    //set the pointer to x, store the previous value in *y and return true
    //if the pointer isn't currently checked out, otherwise return false
    //if y is NULL, the previous is not stored in *y
    inline bool TrySet(T *x, T **y = NULL) {
      assert(x != ATOMIC_NULL);
      return TryPrivateSet(x, y);
    }

    //return the current value of the pointer
    inline T *Get() const {
      T *val;

#ifdef ENABLE_THREADS
      do {
        val = (T *)atomic_load_acq_ptr((ATOMIC_TYPE *)&p);
      } while(val == ATOMIC_NULL);
#else
      val = p;
      assert(val != ATOMIC_NULL);
#endif //ENABLE_THREADS

      return val;
    }

    //writes the current value of the pointer to *x and returns true
    //if the pointer isn't currently checked out, otherwise returns
    //false
    inline bool TryGet(T **x) const {
      T *val;

#ifdef ENABLE_THREADS
      val = (T *)atomic_load_acq_ptr((ATOMIC_TYPE *)&p);
#else
      val = p;
#endif //ENABLE_THREADS
      if(val != ATOMIC_NULL) {
        *x = val;
        return true;
      } else {
        return false;
      }
    }

    //swap pointers atomically and deadlock-free
    inline void Swap(AtomicPtr<T> &X) {
      //define partial order in which to acquire elements to prevent deadlocks
      AtomicPtr<T> *first;
      AtomicPtr<T> *last;
      //always process elements from lower to higher memory addresses
      if(this < &X) {
        first = this;
        last = &X;
      } else {
        first = &X;
        last = this;
      }

      //acquire and update elements in correct order
      T *valFirst = first->Checkout();
      T *valLast = last->PrivateSet(valFirst);
      first->Checkin(valLast);
    }

    //try to swap pointers atomically and deadlock-free, return true if successful,
    //false otherwise
    inline bool TrySwap(AtomicPtr<T> &X) {
      //define partial order in which to acquire elements to prevent deadlocks
      AtomicPtr<T> *first;
      AtomicPtr<T> *last;
      //always process elements from lower to higher memory addresses
      if(this < &X) {
        first = this;
        last = &X;
      } else {
        first = &X;
        last = this;
      }

      //acquire and update elements in correct order
      T *valFirst;
      T *valLast;
      if(!first->TryCheckout(&valFirst)) {
        return false;
      } else {
        if(!last->TryPrivateSet(valFirst, &valLast)) {
          first->Checkin(valFirst);
          return false;
        } else {
          first->Checkin(valLast);
          return true;
        }
      }
    }

    // *** Functions with mutex semantics ***

    //acquire a pointer for exclusive access (mutex lock semantics)
    inline T *Checkout() {
      //Note: PrivateSet() calls Get(), which has acquire semantics
      return PrivateSet((T *)ATOMIC_NULL);
    }

    //try to acquire a pointer for exclusive access, return true if
    //successful, false otherwise (mutex trylock semantics)
    inline bool TryCheckout(T **x) {
      //Note: TryPrivateSet() calls TryGet(), which has acquire semantics
      return TryPrivateSet((T *)ATOMIC_NULL, x);
    }

    //release an exclusive pointer (mutex unlock semantics)
    inline void Checkin(T *x) {
#ifdef ENABLE_TRHEADS
      atomic_store_rel_ptr((ATOMIC_TYPE *)(&p), (ATOMIC_TYPE)x);
#else
      p = x;
#endif //ENABLE_THREADS
    }


    // *** Operators ***


    T operator*() {
      return *Get();
    }

    T *operator=(T *x) {
      return Set(x);
    }

    T *operator=(AtomicPtr<T> X) {
#ifdef ENABLE_THREADS
      T *val = (T *)atomic_load_acq_ptr((ATOMIC_TYPE *)&X.p);
#else
      T * val = X.p;
#endif //ENABLE_THREADS
      Set(val);
      return val;
    }

};

//set ATOMIC_NULL to a value the user hopefully will never use
template<typename T>
const T *AtomicPtr<T>::ATOMIC_NULL((T *)((int)NULL + 1));

} //namespace threads

#endif //ATOMICPTR_H