collections.h

C语言库函数的原型,有用的拿去

// ==++==
//
// Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// ==--==
// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
//
// collections.h
//
// Header file containing collection classes for ConcRT  
//
// These data structures assume in-data links with the names m_pNext and m_pPrev
// Currently defined collections are: Stack, LockFreeStack, SafeStack
//                                    SQueue, SafeSQueue
//                                    List, SafeRWList
//                                    Hash, SafeHash
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

#if !defined(ASSERT) && defined(_DEBUG)
#define ASSERT(x) (_ASSERTE(x), __assume(x))
#elif !defined(ASSERT)
#define ASSERT(x) __assume(x)
#endif

#ifndef CONTAINING_RECORD
#define CONTAINING_RECORD(address, type, field) \
    ((type *)((char *)(address) - (ULONG_PTR)(&((type *)0)->field)))
#endif

#if !defined(UNREACHED)
#define UNREACHED 0
#endif

namespace Concurrency
{
namespace details
{
    //
    // Allows multiple intrusive links within a single data structure.
    //
    struct ListEntry
    {
        ListEntry *m_pPrev;
        ListEntry *m_pNext;
    };

    //
    // Heap allocated generic list block.
    //
    template <class T>
    struct ListNode
    {
        ListNode(T* pData) : m_pData(pData)
        {
        }

        ListNode *m_pPrev;
        ListNode *m_pNext;
        T* m_pData;
    };

    class CollectionTypes
    {
    public:
        //
        // public types
        //

        class Count
        {
        public:
            Count() : m_count(0) {}
            void Increment() { ++m_count; }
            void Decrement() { --m_count; }
            int Value() const { return m_count; }
            void Clear() { m_count = 0; }
        private:
            int m_count;
        };

        class NoCount
        {
        public:
            static void Increment() {}
            static void Decrement() {}
            static int Value() { ASSERT(UNREACHED); return -1; }
            static void Clear() {}
        };
    };

    //
    // The base class of stacks.  This implementation is not thread-safe.
    //
    template <class T, class Counter = CollectionTypes::NoCount>
    class Stack : public Counter
    {
    public:
        Stack() : m_pHead(NULL) {}

        T* Pop()
        {
            if (m_pHead == NULL)
            {
                return NULL;
            }
            T* pHead = m_pHead;
            m_pHead = m_pHead->m_pNext;
            Decrement();
            return pHead;
        }

        void Push(T* pNode)
        {
            ASSERT(pNode != NULL);

            Increment();
            pNode->m_pNext = m_pHead;
            m_pHead = pNode;
        }

        bool Empty() const
        {
            return m_pHead == NULL;
        }

        int Count() const
        {
            return Value();
        }

        T* First()
        {
            return m_pHead;
        }

        T* Next(T* pNode)
        {
            //OACR_USE_PTR(this);
            return pNode->m_pNext;
        }

    private:
        T* m_pHead;
    };

    // 
    // An implementation of interlocked SLIST that does not support Pop. This
    // avoids the ABA problem. The reason for this data structure is to get
    // to the top node (Windows SLIST does not provide this functionality
    // without FirstSListEntry).
    // Type T is required to have an intrusive SLIST_ENTRY m_slNext.
    //
    template <class T>
    class LockFreePushStack
    {
    public:
        LockFreePushStack()
        {
            m_pTop = NULL;
        }

        ~LockFreePushStack()
        {
            // We expect the user to have flushed the stack
            // before deleting it.
            ASSERT(m_pTop == NULL);
        }

        // Returns the current top of the stack
        // THIS OPERATION IS NOT SYNCHRONIZED
        // Anyone walking the list needs to ensure that there
        // are no concurrent push/flush operations.
        T * Unsafe_Top()
        {
            return Delta(m_pTop);
        }

        // Push an element into the stack
        void Push(T * pNode)
        {
            PSLIST_ENTRY top;

            do
            {
                // Make this node point to the head. 
                // m_pTop needs to be volatile to ensure that it is not enregistered
                top = m_pTop;
                pNode->m_slNext.Next = top;

                // Make head point to this node
            }
            while ((InterlockedCompareExchangePointer(reinterpret_cast<volatile PVOID *>(&m_pTop), &pNode->m_slNext, top) != top));
        }

        // Flush all the elements in the stack
        T * Flush()
        {
            return Delta(reinterpret_cast<void *>(InterlockedExchangePointer(reinterpret_cast<volatile PVOID *>(&m_pTop), NULL)));
        }

        static T* Next(T* pNode)
        {
            return Delta(pNode->m_slNext.Next);
        }

    private:

        // m_pTop needs to be volatile to ensure that it is not enregistered
        volatile PSLIST_ENTRY m_pTop;

        static T* Delta(void* p) { return (p == NULL) ? NULL : (T*) ((BYTE*)p - offsetof(T, m_slNext)); }
    };

    //
    // Lock free stack implemented using a windows SLIST. Type T is required to have an intrusive SLIST_ENTRY m_slNext.
    //
    template <class T>
    class LockFreeStack
    {
    public:
        LockFreeStack()
        {
            InitializeSListHead(&m_head);
        }

        T* Pop()
        {
           return Delta(InterlockedPopEntrySList(&m_head));
        }

        T* Flush() 
        {
            return Delta(InterlockedFlushSList(&m_head));
        }

        void Push(T* pNode)
        {
            InterlockedPushEntrySList(&m_head, &(pNode->m_slNext)); 
        }

        static T* Next(T* pNode)
        {
            return Delta(pNode->m_slNext.Next);
        }

        // implicit max of 64K entries
        int Count() const { return static_cast<int> (QueryDepthSList(const_cast<PSLIST_HEADER> (&m_head))); }

    private:
        SLIST_HEADER m_head; // must be 16-bye aligned in x64

        static T* Delta(void* p) { return (p == NULL) ? NULL : (T*) ((BYTE*)p - offsetof(T, m_slNext)); }
    };

    //
    // The derived SafeStack class, which acquires a lock around accesses to the stack.
    //
    template <class T, class Counter = CollectionTypes::NoCount, class LOCK = _NonReentrantLock>
    class SafeStack : public Stack<T, Counter>
    {
    public:
        T* Pop()
        {
            LOCK::_Scoped_lock lockHolder(m_lock);
            return Stack<T, Counter>::Pop();
        }

        void Push(T* pNode)
        {
            LOCK::_Scoped_lock lockHolder(m_lock);
            Stack<T, Counter>::Push(pNode);
        }

        void Acquire() const { m_lock._Acquire(); }
        void Release() const { m_lock._Release(); }

    private:
        mutable LOCK m_lock;
    };
    

    //
    //  The base class of singly-linked queues.  This implementation is not thread-safe.
    //
    template <class T>
    class SQueue
    {
    public:
        SQueue() : m_pHead(NULL), m_ppTail(&m_pHead) { };
        
        void Enqueue(T* pNode)
        {
            ASSERT(pNode != NULL);

            pNode->m_pNext = NULL;
            *m_ppTail = pNode;
            m_ppTail = &pNode->m_pNext;
        }

        T* Dequeue()
        {
            if (m_pHead == NULL)
            {
                return NULL;
            }
            T *pHead = m_pHead;
            m_pHead = m_pHead->m_pNext;
            if (m_pHead == NULL)
                m_ppTail = &m_pHead;

            return pHead;
        }

        T* Current() const { return m_pHead; }
        bool Empty() const { return m_pHead == NULL; }

    private:
        T *m_pHead;
        T **m_ppTail;
    };

    //
    //  The derived safe singly-linked queue class.  This implementation acquires 
    //  a lock before accessing the Queue.
    //
    template <class T, class LOCK = _NonReentrantLock>
    class SafeSQueue : public SQueue<T>
    {
    public:
        void Enqueue(T* pNode)
        {
            LOCK::_Scoped_lock lockHolder(m_lock);
            SQueue<T>::Enqueue(pNode);
        }

        T* Dequeue()
        {
            LOCK::_Scoped_lock lockHolder(m_lock);
            return SQueue<T>::Dequeue();
        }

        void Acquire() const { m_lock._Acquire(); }
        void Release() const { m_lock._Release(); }

    private:
        mutable LOCK m_lock;
    };

    //
    //  An unsafe circular linked list. 
    //
    template <class T, class Counter = CollectionTypes::NoCount>
    class List : public Counter
    {
    public:
        List() : m_pTail(NULL)
        {
        }

        void AddHead(T* pNode)
        {
            ASSERT(pNode != NULL);

            // if the list is empty, add it accordingly
            if (m_pTail == NULL)
            {
                m_pTail = pNode;
                m_pTail->m_pPrev = m_pTail;
                m_pTail->m_pNext = m_pTail; 
            }
            else
            {
                // hook up pNode
                pNode->m_pNext = m_pTail->m_pNext; // pNode->next = head
                pNode->m_pPrev = m_pTail;
            
                // hook up old head (viz., tail->next)
                m_pTail->m_pNext->m_pPrev = pNode; // head->prev = pNode
                m_pTail->m_pNext = pNode; // head = pNode
            }

            Increment();
        }

        void AddTail(T* pNode)
        {
            ASSERT(pNode != NULL);

            if (m_pTail == NULL)
            {
                pNode->m_pPrev = pNode->m_pNext = pNode;
            }
            else
            {
                // hook up pNode
                pNode->m_pNext = m_pTail->m_pNext; // pNode->next = head
                pNode->m_pPrev = m_pTail;
            
                // hook up old head (viz., tail->next)
                m_pTail->m_pNext->m_pPrev = pNode; // head->prev = pNode
                m_pTail->m_pNext = pNode; // head = pNode
            }

            m_pTail = pNode; // same as AddHead except we change the tail

            Increment();
        }

        T* RemoveHead()
        {
            if (m_pTail == NULL)
                return NULL;

            Decrement();
            T *pNode = (T*) m_pTail->m_pNext;

            if (m_pTail == pNode)
            {
                m_pTail = NULL;
            }
            else 
            {
                // hook up tail to head->next
                pNode->m_pNext->m_pPrev = m_pTail; // head->next->prev = tail
                m_pTail->m_pNext = pNode->m_pNext; // tail->next = head->next
            }

            return pNode;
        }

        T* RemoveTail()
        {
            if (m_pTail == NULL)
                return NULL;

            Decrement();
            T *pNode = m_pTail;

            if (m_pTail == m_pTail->m_pNext)