/*

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 __CAThreadSafeList_h__

#define __CAThreadSafeList_h__

#include "CAAtomicStack.h"

//  linked list of T's

//  T must define operator ==

template <class T>

class TThreadSafeList {

private:

    enum EEventType { kAdd, kRemove, kClear };

    class Node {

    public:

        Node *      mNext;

        EEventType  mEventType;

        T           mObject;

        Node *& next() { return mNext; }

    };

public:

    class iterator {

    public:

        iterator() { }

        iterator(Node *n) : mNode(n) { }

        bool operator == (const iterator &other) const { return this->mNode == other.mNode; }

        bool operator != (const iterator &other) const { return this->mNode != other.mNode; }

        T & operator * () const { return mNode->mObject; }

        iterator & operator ++ () { mNode = mNode->next(); return *this; }  // preincrement

        iterator operator ++ (int) { iterator tmp = *this; mNode = mNode->next(); return tmp; } // postincrement

    private:

        Node *      mNode;

    };

    TThreadSafeList() { }

    ~TThreadSafeList()

    {

        mActiveList.free_all();

        mPendingList.free_all();

        mFreeList.free_all();

    }

    // These may be called on any thread

    void    deferred_add(const T &obj)  // can be called on any thread

    {

        Node *node = AllocNode();

        node->mEventType = kAdd;

        node->mObject = obj;

        mPendingList.push_atomic(node);

        //mPendingList.dump("pending after add");

    }

    void    deferred_remove(const T &obj)   // can be called on any thread

    {

        Node *node = AllocNode();

        node->mEventType = kRemove;

        node->mObject = obj;

        mPendingList.push_atomic(node);

        //mPendingList.dump("pending after remove");

    }

    void    deferred_clear()                    // can be called on any thread

    {

        Node *node = AllocNode();

        node->mEventType = kClear;

        mPendingList.push_atomic(node);

    }

    // These must be called from only one thread

    void    update()        // must only be called from one thread

    {

        NodeStack reversed;

        Node *event, *node, *next;

        bool workDone = false;

        // reverse the events so they are in order

        event = mPendingList.pop_all();

        while (event != NULL) {

            next = event->mNext;

            reversed.push_NA(event);

            event = next;

            workDone = true;

        }

        if (workDone) {

            //reversed.dump("pending popped");

            //mActiveList.dump("active before update");

            // now process them

            while ((event = reversed.pop_NA()) != NULL) {

                switch (event->mEventType) {

                case kAdd:

                    {

                        Node **pnode;

                        bool needToInsert = true;

                        for (pnode = mActiveList.phead(); *pnode != NULL; pnode = &node->mNext) {

                            node = *pnode;

                            if (node->mObject == event->mObject) {

                                //printf("already active!!!\n");

                                FreeNode(event);

                                needToInsert = false;

                                break;

                            }

                        }

                        if (needToInsert) {

                            // link the new event in at the end of the active list

                            *pnode = event;

                            event->mNext = NULL;

                        }

                    }

                    break;

                case kRemove:

                    // find matching node in the active list, remove it

                    for (Node **pnode = mActiveList.phead(); *pnode != NULL; ) {

                        node = *pnode;

                        if (node->mObject == event->mObject) {

                            *pnode = node->mNext;   // remove from linked list

                            FreeNode(node);

                            break;

                        }

                        pnode = &node->mNext;

                    }

                    // dispose the request node

                    FreeNode(event);

                    break;

                case kClear:

                    for (node = mActiveList.head(); node != NULL; ) {

                        next = node->mNext;

                        FreeNode(node);

                        node = next;

                    }

                    FreeNode(event);

                    break;

                default:

                    //printf("invalid node type %d!\n", event->mEventType);

                    break;

                }

            }

            //mActiveList.dump("active after update");

        }

    }

    iterator begin() const {

        //mActiveList.dump("active at begin");

        return iterator(mActiveList.head());

    }

    iterator end() const { return iterator(NULL); }

private:

    Node *  AllocNode()

    {

        Node *node = mFreeList.pop_atomic();

        if (node == NULL)

            node = (Node *)CA_malloc(sizeof(Node));

        return node;

    }

    void    FreeNode(Node *node)

    {

        mFreeList.push_atomic(node);

    }

private:

    class NodeStack : public TAtomicStack<Node> {

    public:

        void free_all() {

            Node *node;

            while ((node = this->pop_NA()) != NULL)

                free(node);

        }

        Node ** phead() { return &this->mHead; }

        Node *  head() const { return this->mHead; }

    };

    NodeStack   mActiveList;    // what's actually in the container - only accessed on one thread

    NodeStack   mPendingList;   // add or remove requests - threadsafe

    NodeStack   mFreeList;      // free nodes for reuse - threadsafe

};

#endif // __CAThreadSafeList_h__