collections.h

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

            {
                m_pTail = NULL;
            }
            else 
            {
                // hook up head to tail->prev and set tail = tail->prev, preserves head
                pNode->m_pNext->m_pPrev = pNode->m_pPrev; // head->prev = tail->prev
                pNode->m_pPrev->m_pNext = pNode->m_pNext; // tail->prev->next = head
                m_pTail = (T*) m_pTail->m_pPrev;
            }

            return pNode;
        }

        void Enqueue(T* pNode) 
        {
            AddHead(pNode);
        }

        T* Dequeue()
        {
            return RemoveTail();
        }

        //
        // Remove an element from the list.
        // The function asserts that the write lock is held
        //
        void Remove(T* pNode)
        {
            ASSERT(pNode != NULL && m_pTail != NULL);

            Decrement();

            pNode->m_pNext->m_pPrev = pNode->m_pPrev;
            pNode->m_pPrev->m_pNext = pNode->m_pNext;
            if (pNode == m_pTail)
            {
                m_pTail = (m_pTail == m_pTail->m_pNext) ? NULL : (T*) m_pTail->m_pPrev;
            }
        }

        //
        // Iterator functions
        //
        T* First() const
        { 
            return (m_pTail != NULL) ? (T*) m_pTail->m_pNext : NULL; 
        }

        T* Last() const
        {
            return m_pTail; 
        }

        T* Next(T* pNode) const
        {
            return (pNode != m_pTail) ? (T*) pNode->m_pNext : NULL; 
        }

        static T* Next(T* pNode, T* pPosition)
        {
            return (pNode != pPosition) ? (T*) pNode->m_pNext : NULL; 
        }

        static T* Prev(T* pNode, T* pPosition)
        {
            return (pNode != pPosition) ? (T*) pNode->m_pPrev : NULL; 
        }

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

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

        void Clear() { m_pTail = NULL; Counter::Clear(); }

    protected:
        T *m_pTail;
    };

    //
    //  A safe circular linked list.  This implementation uses
    //  a _ReaderWriterLock on the list accesses.
    //
    template <class T, class Counter = CollectionTypes::NoCount, class RWLOCK = _ReaderWriterLock>
    class SafeRWList : public List<T, Counter>
    {
    public:
        SafeRWList()
        {
        }

        void AddHead(T* pNode)
        {
            RWLOCK::_Scoped_lock writeLock(m_lock);
            List<T, Counter>::AddHead(pNode);
        }

        void AddTail(T* pNode)
        {
            RWLOCK::_Scoped_lock writeLock(m_lock);
            List<T, Counter>::AddTail(pNode);
        }

        T* RemoveHead()
        {
            RWLOCK::_Scoped_lock writeLock(m_lock);
            return List<T, Counter>::RemoveHead();
        }

        T* RemoveTail()
        {
            RWLOCK::_Scoped_lock writeLock(m_lock);
            return List<T, Counter>::RemoveTail();
        }

        //
        //  Wrapper functions around AddHead/RemoveTail for consistency purposes
        //
        void Enqueue(T* pNode) 
        {
            AddHead(pNode);
        }

        T* Dequeue()
        {
            return RemoveTail();
        }

        //
        // Synchronized remove an element from the list.
        //
        void Remove(T* pNode)
        {
            RWLOCK::_Scoped_lock writeLock(m_lock);
            List<T, Counter>::Remove(pNode);
        }

#pragma region "unlocked variants"
        void UnlockedAddHead(T* pNode)
        {
            ASSERT(m_lock._HasWriteLock());
            List<T, Counter>::AddHead(pNode);
        }

        void UnlockedAddTail(T* pNode)
        {
            ASSERT(m_lock._HasWriteLock());
            List<T, Counter>::AddTail(pNode);
        }

        T* UnlockedRemoveHead()
        {
            ASSERT(m_lock._HasWriteLock());
            return List<T, Counter>::RemoveHead();
        }

        T* UnlockedRemoveTail()
        {
            ASSERT(m_lock._HasWriteLock());
            return List<T, Counter>::RemoveTail();
        }

        void UnlockedEnqueue(T* pNode)
        {
            ASSERT(m_lock._HasWriteLock());
            List<T, Counter>::AddHead(pNode);
        }

        T* UnlockedDequeue()
        {
            ASSERT(m_lock._HasWriteLock());
            return List<T, Counter>::RemoveTail();
        }

        //
        // Remove an element from the list.
        // The function asserts that the write lock is held
        //
        void UnlockedRemove(T* pNode)
        {
            ASSERT(m_lock._HasWriteLock());
            List<T, Counter>::Remove(pNode);
        }
#pragma endregion

        //
        // R/W Lock acquisition functions
        //
        void AcquireRead() const { m_lock._AcquireRead(); }
        bool TryAcquireRead() const { return m_lock._TryAcquireRead(); }
        void ReleaseRead() const { m_lock._ReleaseRead(); }
        void AcquireWrite() const { m_lock._AcquireWrite(); }
        bool TryAcquireWrite() const { return m_lock._TryAcquireWrite(); }
        void ReleaseWrite() const { m_lock._ReleaseWrite(); }
        void FlushWriteOwners() const { m_lock._FlushWriteOwners(); } 

        /// <summary>
        ///     An exception safe RAII wrapper for writes.
        /// </summary>
        class _Scoped_lock
        {
        public:
            explicit _Scoped_lock(SafeRWList& _Lock) : _M_lock(_Lock)
            {
                _M_lock.AcquireWrite();
            }

            ~_Scoped_lock()
            {
                _M_lock.ReleaseWrite();
            }

        private:

            SafeRWList& _M_lock;

            _Scoped_lock(const _Scoped_lock&);                    // no copy constructor
            _Scoped_lock const & operator=(const _Scoped_lock&);  // no assignment operator
        };

        /// <summary>
        ///     An exception safe RAII wrapper for reads.
        /// </summary>
        class _Scoped_lock_read
        {
        public:
            explicit _Scoped_lock_read(SafeRWList& _Lock) : _M_lock(_Lock)
            {
                _M_lock.AcquireRead();
            }

            ~_Scoped_lock_read()
            {
                _M_lock.ReleaseRead();
            }

        private:

            SafeRWList& _M_lock;

            _Scoped_lock_read(const _Scoped_lock_read&);                    // no copy constructor
            _Scoped_lock_read const & operator=(const _Scoped_lock_read&);  // no assignment operator
        };

    protected:
        mutable RWLOCK m_lock;
    };

    //
    // Naive hash table implemented as an array of single linked lists.
    //
    template <class KEY, class VALUE>
    class Hash 
    {
    public:
        //
        // nested classes
        //

        struct ListNode 
        {
            ListNode(const KEY& key = 0, const VALUE& value = 0) :
                m_pNext(NULL),
                m_key(key),
                m_value(value)
            {
            }

            ListNode* m_pNext;
            KEY m_key;
            VALUE m_value;
        };

    public:
        //
        // ctor
        //

        Hash(int size = s_hashsize)
        {
            m_size = size;
            m_count = 0;
            m_ppHashtable = new(Alloc(sizeof(ListNode*) * m_size)) ListNode*[m_size];
            memset(m_ppHashtable, 0, m_size*sizeof(ListNode*));
        }

        //
        // public methods
        //

        //
        // iterator - The First() and Next() functions do not have supporting Safe versions. Currently they are used
        // by the memory dump tool which uses these APIs from a single thread. If thread safe access
        // is desired the apis must be called after acquiring the read lock in the SafeHash class.
        //
        ListNode* First(int* x) 
        {
            ASSERT(x != NULL);
            *x = 0;
            return NextList(x);
        }

        ListNode* Next(int* x, ListNode* p) 
        {
            ASSERT(p != NULL && x != NULL && *x < m_size);
            if (p->m_pNext != NULL) 
            {
                return p->m_pNext;
            } 
            else 
            {
                ++*x;
                return NextList(x);
            }
        }

        ListNode* Insert(const KEY& key, const VALUE& value)
        {
            int hashValue = HashValue(key, m_size);

            ListNode* pNode = Lookup(key, hashValue);
            if (pNode == NULL)
            {
                pNode = new(Alloc(sizeof(ListNode))) ListNode(key, value);

                pNode->m_pNext = m_ppHashtable[hashValue];
                m_ppHashtable[hashValue] = pNode;

                m_count++;

                return pNode;
            }
            return NULL;
        }

        ListNode* Lookup(const KEY& key, VALUE* pValue) 
        {
            ListNode* pNode = Lookup(key, HashValue(key, m_size));
            if (pNode != NULL)
            {
                *pValue = pNode->m_value;
            }
            return pNode;
        }

        bool Exists(const KEY& key) 
        {
            return (Lookup(key, HashValue(key, m_size)) != NULL);
        }

        bool FindAndDelete(const KEY& key, VALUE* pValue) 
        {
            ListNode* pNode = Remove(key, HashValue(key, m_size));
            if (pNode != NULL) 
            {
                if (pValue != NULL) 
                {
                    *pValue = pNode->m_value;
                }
                FreeNode(pNode);

                return true;
            }
            return false;
        }

        ListNode *Find(const KEY& key, VALUE* pValue)
        {
            ListNode* pNode = Lookup(key, HashValue(key, m_size));
            if (pNode != NULL) 
            {
                if (pValue != NULL) 
                {
                    *pValue = pNode->m_value;
                }
                return pNode;
            }
            return NULL;
        }

        bool Delete(const KEY& key) 
        {
            return FindAndDelete(key, NULL);
        }

        void Wipe()
        {
            if (m_count > 0)
            {
                for (int i = 0; i < m_size; ++i) 
                {
                    ListNode* pNode = m_ppHashtable[i];
                    while (pNode != NULL) 
                    {
                        ListNode* pNext = pNode->m_pNext;
                        FreeNode(pNode);
                        pNode = pNext;
                    }
                }
                m_count = 0;
                memset(m_ppHashtable, 0, m_size*sizeof(ListNode*));
            }
        }

        int Count() const
        {
            return m_count;
        }

        //
        // dtor
        //

        ~Hash() 
        {
            Wipe();
            Free(m_ppHashtable);
        }

    protected:
        //
        // protected data
        //
        static const int s_hashsize = 4097;

    private:
        //
        // private data
        //

        int m_size;
        int m_count;
    
    ListNode** m_ppHashtable;

        //
        // private methods
        //