/*

Copyright (C) 2016 Apple Inc. All Rights Reserved.

See LICENSE.txt for this sample’s licensing information

Abstract:

Part of Core Audio Public Utility Classes

*/

#ifndef __CAAtomicStack_h__

#define __CAAtomicStack_h__

#if !defined(__COREAUDIO_USE_FLAT_INCLUDES__)

    #include <libkern/OSAtomic.h>

#else

    #include <CAAtomic.h>

#endif

#if MAC_OS_X_VERSION_MAX_ALLOWED < MAC_OS_X_VERSION_10_4

    #include <CoreServices/CoreServices.h>

#endif

//  linked list LIFO or FIFO (pop_all_reversed) stack, elements are pushed and popped atomically

//  class T must implement T *& next().

template <class T>

class TAtomicStack {

public:

    TAtomicStack() : mHead(NULL) { }

    // non-atomic routines, for use when initializing/deinitializing, operate NON-atomically

    void    push_NA(T *item)

    {

        item->next() = mHead;

        mHead = item;

    }

    T *     pop_NA()

    {

        T *result = mHead;

        if (result)

            mHead = result->next();

        return result;

    }

    bool    empty() const { return mHead == NULL; }

    T *     head() { return mHead; }

    // atomic routines

    void    push_atomic(T *item)

    {

        T *head_;

        do {

            head_ = mHead;

            item->next() = head_;

        } while (!compare_and_swap(head_, item, &mHead));

    }

    void    push_multiple_atomic(T *item)

        // pushes entire linked list headed by item

    {

        T *head_, *p = item, *tail;

        // find the last one -- when done, it will be linked to head

        do {

            tail = p;

            p = p->next();

        } while (p);

        do {

            head_ = mHead;

            tail->next() = head_;

        } while (!compare_and_swap(head_, item, &mHead));

    }

    T *     pop_atomic_single_reader()

        // this may only be used when only one thread may potentially pop from the stack.

        // if multiple threads may pop, this suffers from the ABA problem.

        // <rdar://problem/4606346> TAtomicStack suffers from the ABA problem

    {

        T *result;

        do {

            if ((result = mHead) == NULL)

                break;

        } while (!compare_and_swap(result, result->next(), &mHead));

        return result;

    }

    T *     pop_atomic()

        // This is inefficient for large linked lists.

        // prefer pop_all() to a series of calls to pop_atomic.

        // push_multiple_atomic has to traverse the entire list.

    {

        T *result = pop_all();

        if (result) {

            T *next = result->next();

            if (next)

                // push all the remaining items back onto the stack

                push_multiple_atomic(next);

        }

        return result;

    }

    T *     pop_all()

    {

        T *result;

        do {

            if ((result = mHead) == NULL)

                break;

        } while (!compare_and_swap(result, NULL, &mHead));

        return result;

    }

    T*      pop_all_reversed()

    {

        TAtomicStack<T> reversed;

        T *p = pop_all(), *next;

        while (p != NULL) {

            next = p->next();

            reversed.push_NA(p);

            p = next;

        }

        return reversed.mHead;

    }

    static bool compare_and_swap(T *oldvalue, T *newvalue, T **pvalue)

    {

#if TARGET_OS_MAC

    #if __LP64__

            return ::OSAtomicCompareAndSwap64Barrier(int64_t(oldvalue), int64_t(newvalue), (int64_t *)pvalue);

    #elif MAC_OS_X_VERSION_MAX_ALLOWED >= MAC_OS_X_VERSION_10_4

            return ::OSAtomicCompareAndSwap32Barrier(int32_t(oldvalue), int32_t(newvalue), (int32_t *)pvalue);

    #else

            return ::CompareAndSwap(UInt32(oldvalue), UInt32(newvalue), (UInt32 *)pvalue);

    #endif

#else

            //return ::CompareAndSwap(UInt32(oldvalue), UInt32(newvalue), (UInt32 *)pvalue);

            return CAAtomicCompareAndSwap32Barrier(SInt32(oldvalue), SInt32(newvalue), (SInt32*)pvalue);

#endif

    }

protected:

    T *     mHead;

};

#if ((MAC_OS_X_VERSION_MAX_ALLOWED >= MAC_OS_X_VERSION_10_5) && !TARGET_OS_WIN32)

#include <libkern/OSAtomic.h>

class CAAtomicStack {

public:

    CAAtomicStack(size_t nextPtrOffset) : mNextPtrOffset(nextPtrOffset) {

        /*OSQueueHead h = OS_ATOMIC_QUEUE_INIT; mHead = h;*/

        mHead.opaque1 = 0; mHead.opaque2 = 0;

    }

    // a subset of the above

    void    push_atomic(void *p) { OSAtomicEnqueue(&mHead, p, mNextPtrOffset); }

    void    push_NA(void *p) { push_atomic(p); }

    void *  pop_atomic() { return OSAtomicDequeue(&mHead, mNextPtrOffset); }

    void *  pop_atomic_single_reader() { return pop_atomic(); }

    void *  pop_NA() { return pop_atomic(); }

private:

    OSQueueHead     mHead;

    size_t          mNextPtrOffset;

};

// a more efficient subset of TAtomicStack using OSQueue.

template <class T>

class TAtomicStack2 {

public:

    TAtomicStack2() {

        /*OSQueueHead h = OS_ATOMIC_QUEUE_INIT; mHead = h;*/

        mHead.opaque1 = 0; mHead.opaque2 = 0;

        mNextPtrOffset = -1;

    }

    void    push_atomic(T *item) {

        if (mNextPtrOffset < 0) {

            T **pnext = &item->next();  // hack around offsetof not working with C++

            mNextPtrOffset = (Byte *)pnext - (Byte *)item;

        }

        OSAtomicEnqueue(&mHead, item, mNextPtrOffset);

    }

    void    push_NA(T *item) { push_atomic(item); }

    T *     pop_atomic() { return (T *)OSAtomicDequeue(&mHead, mNextPtrOffset); }

    T *     pop_atomic_single_reader() { return pop_atomic(); }

    T *     pop_NA() { return pop_atomic(); }

    // caution: do not try to implement pop_all_reversed here. the writer could add new elements

    // while the reader is trying to pop old ones!

private:

    OSQueueHead     mHead;

    ssize_t         mNextPtrOffset;

};

#else

#define TAtomicStack2 TAtomicStack

#endif // MAC_OS_X_VERSION_MAX_ALLOWED && !TARGET_OS_WIN32

#endif // __CAAtomicStack_h__