collections.h

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

        ListNode* NextList(int* x) 
        {
            ASSERT(x != NULL && *x >= 0 && *x <= m_size);

            for (int i = *x; i < m_size; ++i) 
            {
                if (m_ppHashtable[i] != NULL) 
                {
                    *x = i;
                    return m_ppHashtable[i];
                }
            }
            return NULL;
        }

        ListNode* Lookup(const KEY& key, int hashValue) 
        {
            ASSERT(hashValue >= 0 && hashValue < m_size);
            ListNode* pNode = m_ppHashtable[hashValue];
            while (pNode != NULL) 
            {
                if (pNode->m_key == key) 
                {
                    return pNode;
                }
                pNode = pNode->m_pNext;
            }
            return NULL;
        }

        ListNode* Remove(const KEY& key, int hashValue) 
        {
            ListNode* pNode = m_ppHashtable[hashValue], *pPrev = NULL;

            while (pNode != NULL) 
            {
                if (pNode->m_key == key) 
                {
                    if (pPrev == NULL)
                    {
                        m_ppHashtable[hashValue] = pNode->m_pNext;
                    }
                    else
                    {
                        pPrev->m_pNext = pNode->m_pNext;
                    }

                    m_count--;

                    return pNode;
                }
                pPrev = pNode;
                pNode = pNode->m_pNext;
            }
            return NULL;
        }

        static void* Alloc(size_t size)
        {
            return ::operator new(size);
        }

        static void Free(void *ptr)
        {
            ::operator delete(ptr);
        }

        //
        // This method could be specialized to provide better distribution for certain values of the template parameter KEY.
        //
        static unsigned int HashValue(const KEY& key, int the_size) 
        {
            unsigned int nHash = 0;
            unsigned char* hashValue = (unsigned char*) key;
            for (int i = 0; i < sizeof(KEY); ++i) 
            {
                nHash += (nHash << 5) + (int)(unsigned char) hashValue++;
            }
            ASSERT(the_size > 0);
            return Randomize(nHash) % the_size;
        }

        static unsigned int Randomize(unsigned int u) 
        {
            // Randomize the hash value further by multiplying by a large prime,
            // then adding the hi and lo DWORDs of the 64-bit result together. This
            // produces an excellent randomization very efficiently.
            unsigned __int64 l = (unsigned __int64) u * (unsigned __int64) 0x7ff19519;  // this number is prime.
            return (unsigned int)l + (unsigned int)(l >> 32);
        }

        //
        // This function could be specialized to provide cleanup for non-trivial keys.
        //
        static void DeleteKey(KEY&) {}
        //
        // This function could be specialized to provide cleanup for non-trivial values.
        //
        static void DeleteValue(VALUE&) {}

        static void FreeNode(ListNode* pNode)
        {
            DeleteKey(pNode->m_key);
            DeleteValue(pNode->m_value);
            pNode->ListNode::~ListNode();
            Free(pNode);
        }
    };

    //
    // reader/writer lock hash table
    // not polymorphic -- never cast to base
    //
    template <class KEY, class VALUE>
    class SafeHash : public Hash<KEY, VALUE>
    {
    public:
        typedef Hash<KEY, VALUE> Base;

        //
        // ctors
        //
        SafeHash(int size = s_hashsize) : Hash(size)
        {
        }

        //
        // public methods
        //

        ListNode* Insert(const KEY& key, const VALUE& value)
        {
            _ReaderWriterLock::_Scoped_lock writeLock(m_lock);
            return Base::Insert(key, value);
        }

        bool Exists(const KEY& key) 
        {
            _ReaderWriterLock::_Scoped_lock_read readLock(m_lock);
            return Base::Exists(key);
        }

        ListNode* Lookup(const KEY& key, VALUE* pValue) 
        {
            _ReaderWriterLock::_Scoped_lock writeLock(m_lock);
            return Base::Lookup(key, pValue);
        }

        bool FindAndDelete(const KEY& key, VALUE* pValue) 
        {
            _ReaderWriterLock::_Scoped_lock writeLock(m_lock);
            return Base::FindAndDelete(key, pValue);
        }

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


        void AcquireWrite() { m_lock._AcquireWrite(); }
        void ReleaseWrite() { m_lock._ReleaseWrite(); }
        void AcquireRead() { m_lock._AcquireRead(); }
        void ReleaseRead() { m_lock._ReleaseRead(); }

        //
        // dtor -- use default dtor
        //

    private:
        //
        // private data
        //

        _ReaderWriterLock m_lock;
    };

#define _ARRAYNODE_FULL    -2
#define _ARRAYNODE_NOTFULL -1

    class SchedulerBase;

    //
    // The ListArray class is a generalized array that can be accesed by index
    // Each node in the list includes an array of elements is default constructed to bucket size 256 
    // and contains a pointer to the next list and a searchIndex field.  
    //
    // The searchIndex field is an indicator as to whether this array is full.  A value of _ARRAYNODE_FULL
    // means the array is full and can be skipped over on insertion.  A value of _ARRAYNODE_NOTFULL means 
    // the array is not full and should be searched.  A value >=0 means that that specific element in the 
    // array has been removed and could be used.
    //
    // On the side, an Array pointing to the each array node is kept in m_ppArrayNodes.  This allows
    // for fast O(1) access on removal and the index operator, up to size m_arrayNodeSize*m_arrayLength
    // elements (default 512*256).
    //
    // m_ppArrayNodes:
    // +---+---+---+---+
    // | 1 | 2 |   |512|
    // +---+---+---+---+
    //   |   |
    //   |   +---------------------------------------------+
    //   |                                                 |
    //   V                                                 V
    // ArrayNode 1:                                      ArrayNode 2:
    // +---+---+---+-------+---+------+-------+          +---+---+---+-------+---+------+-------+
    // | 1 | 2 | 3 |  ...  |256| next | index |     +--> | 1 | 2 | 3 |  ...  |256| next | index |
    // +---+---+---+-------+---+------+-------+     |    +---+---+---+-------+---+------+-------+
    //                             |                |
    //                             +----------------+
    // 
    // An Add(object) will currently run through the arrays for a non-full (not _ARRAYNODE_FULL) array, then start
    // searching that specific array for a non-NULL slot.  A CAS is used to place the element in that
    // slot.  
    //
    // Any object that has an integer m_listArrayIndex field can be placed into this ListArray implementation.  
    // In the ConcRT scheduler, it will be mainly used for R/W objects that are often read, to avoid using a 
    // lock-based collection like the SafeRWList.  
    //
    //
    // ELEMENT DELETION FROM LIST ARRAYS
    //
    // The general algorithm for deletion is as follows:
    //
    // ListArray.Remove() CAS's items out of the main list array and inserts them into the free pool.  After
    // the insertion, the ListArray checks to see if the number of items in the free pool has exceeded a set
    // threshold amount (stored in m_deletionThreshold).  If so, it calls the scheduler and asks it to invoke
    // the deletion at the next safe point: a point where all Contexts have reached a point in their
    // dispatch loops where they are outside of their stealing logic and could not possibly be holding a bad pointer.
    // At this point, the Remove() function moves half of the elements on the free pool over to a "elements to delete" 
    // list and sets a flag (m_fHasElementsToDelete) in this ListArray indicating it is the list array awaiting contexts 
    // to reach safe points. 
    // 
    // In the InterContextBase::Dispatch code, a single check is placed in one of its safe points which will mark the
    // virtual processor as "ReachedSafePoint" if there is a pending cleanup.
    //
    // The m_fHasElementsToDelete call prevents two outstanding invocations for deletion at once.
    //
    // Note: it is currently not safe to walk a list array from an external context if the list array is deleting items.
    template <class ELEMENT>
    class ListArray
    {
        struct ArrayNode {
            ArrayNode(ELEMENT ** ppArray)
                : m_ppArray(ppArray), m_pNext(NULL), m_searchIndex(_ARRAYNODE_NOTFULL)
            {
            }
            // The actual array of elements being stored
            ELEMENT ** m_ppArray; 
            // The next array
            ArrayNode * m_pNext;
            // A integer indicating whether this array is full, or where a free index slot is
            //  -2: array is full
            //  -1: array is not full, and should be 
            // >=0: some array element has been removed
            int m_searchIndex;
        };

        //
        // Pool of free Elements, can be returned and reused
        // The user is responsible for reinitializing the elements to a correct state before using them
        //
        typedef struct __FreeElement {
            SLIST_ENTRY ItemEntry;
            ELEMENT * m_pElement; 
        } FreeElement, *PFreeElement;

        // The Slist of free elements saved for reuse
        SLIST_HEADER m_freeElementPool;  // must be 16-bye aligned in x64

        // Elements removed from the free pool because it exceeded its threshold size.
        // The elements are held in this list until they are safe to delete
        SLIST_HEADER m_elementsToDelete; // must be 16-bye aligned in x64

        // When a deletion is started, all elements to delete are snapped, and pointed to
        // by this SLIST_ENTRY.
        PSLIST_ENTRY m_deletionList;

        // The invocation for deletion which will happen on safe points.
        SafePointInvocation m_deletionSafePoint;

    public:
        /// <summary>
        ///     Constructor for ListArray
        /// </summary>
        /// <param name="arrayLength">
        ///     The length of each array in the list
        /// </param>
        ListArray(Concurrency::details::SchedulerBase * pScheduler, int arrayLength = 256, int deletionThreshold = 64)
            : m_pScheduler(pScheduler),
              m_pArrayHead(NULL), 
              m_shiftBits(0), 
              m_nextArrayNodeSlot(1), 
              m_arrayNodesSize(512), 
              m_maxArrayIndex(0),
              m_deletionThreshold(deletionThreshold),
              m_fHasElementsToDelete(FALSE),
              m_deletionList(NULL)
        {
            //
            // Initialize the arrayLength to the next largest power of 2
            //
            if ((arrayLength & (arrayLength-1)) != 0)
            {
                arrayLength = (arrayLength >> 1) | arrayLength;
                arrayLength = (arrayLength >> 2) | arrayLength;
                arrayLength = (arrayLength >> 4) | arrayLength;
                arrayLength = (arrayLength >> 8) | arrayLength;
                arrayLength = (arrayLength >> 16) | arrayLength;
                arrayLength = arrayLength + 1;
            }
            m_arrayLength = arrayLength;

            // Create an array of m_arrayLength (default is 256)
            ELEMENT ** elementArray = new ELEMENT*[m_arrayLength];
            memset(elementArray, 0, m_arrayLength*sizeof(ELEMENT*));
            m_pArrayHead = new ArrayNode(elementArray);

            // Creates an array for quick access to the right ArrayNode
            m_ppArrayNodes = new ArrayNode*[m_arrayNodesSize];
            m_ppArrayNodes[0] = m_pArrayHead;

            // Initialize the Free Element Pool Slist
            InitializeSListHead(&m_freeElementPool);

            InitializeSListHead(&m_elementsToDelete);

            // Precalculate number of bits to shift this arraylength
            int i = m_arrayLength;
            while ((i >>= 1) != 0)
            {
                m_shiftBits++;
            }
        }

        /// <summary>
        ///     ListArray destructor
        /// </summary>
        ~ListArray()
        {
            //
            // Delete items that were added to the free list
            //
            PSLIST_ENTRY pListEntry = InterlockedFlushSList(&m_freeElementPool);
            DeleteElements(pListEntry);

            //
            // Delete items that were added to the elements to delete slist
            //
            pListEntry = InterlockedFlushSList(&m_elementsToDelete);
            DeleteElements(pListEntry);

            //
            // Delete any elements that were snapped for deletion but the
            // deletion did not actually occur yet
            //
            DeleteElements(m_deletionList);

            //
            // Delete each individual array
            //
            ArrayNode * node = m_pArrayHead;
            while (node != NULL)
            {
                for (int i = 0; i < m_arrayLength; i++)
                {
                    _InternalDeleteHelper<ELEMENT>(node->m_ppArray[i]);
                }
                ArrayNode * next = node->m_pNext;
                delete [] node->m_ppArray;
                delete node;
                node = next;
            }

            delete [] m_ppArrayNodes;
        }

        /// <summary>
        ///     Determines if there are any elements in the list array.
        ///     This routine shall only be called when the list array is
        ///.    is not being modified.
        /// </summary>
        /// <returns>
        ///     true if the list array is empty, false otherwise
        /// </returns>
        bool IsEmptyAtSafePoint()
        {
            ArrayNode * node = m_pArrayHead;
            while (node != NULL)
            {
                for (int i = 0; i < m_arrayLength; i++)
                {
                    if (node->m_ppArray[i] != NULL)
                    {
                        return false;
                    }
                }
                node = node->m_pNext;
            }

            return true;
        }

        /// <summary>
        ///     Add an element into the ListArray
        /// </summary>
        /// <param name="element">
        ///     The element being inserted 
        /// </param>
        /// <returns>
        ///     The absolute index in the array that it was inserted at
        /// </returns>
        int Add(ELEMENT * element)
        {
            // A flag for whether the object has actually been inserted into the ListArray
            bool inserted = false;
            // The return value: the absolute index in the array that the item was inserted
            int index = 0;

            ArrayNode * node = m_pArrayHead;
            while (inserted == false)
            {
                //
                // A m_searchIndex value of -1 indicates that this current array being looked at
                // is not known to be full.  A walk of the array to find a non-NULL slot is performed
                //
                if (node->m_searchIndex >= -1)
                {
                    ELEMENT ** elementArray = node->m_ppArray;

                    for (int i = 0; i < m_arrayLength; i++)
                    {
                        // Continue if the slot is non-NULL
                        if (elementArray[i] != NULL)
                        {
                            continue;
                        }

                        // Set this element's m_listArrayIndex field to point to this field we're trying
                        // to insert at.  This is set before the CAS with the ListArray bucket to avoid