collections.h

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

                        // races that may occur if the object is immediately removed before the index field
                        // is set.
                        element->m_listArrayIndex = index+i;

                        // Check the current index to see whether or not we need to increment m_maxArrayIndex
                        // for this insertion
                        int currentMaxIndex = m_maxArrayIndex;

                        // Try to insert at array slot i
                        PVOID initPtr = InterlockedCompareExchangePointer((volatile PVOID *) &elementArray[i], 
                            (PVOID) element, (PVOID) NULL);
                        if (initPtr == NULL)
                        {
                            // Mark this element as inserted at location i
                            inserted = true;
                            index += i;
                            if (index >= currentMaxIndex)
                            {
                                InterlockedIncrement(&m_maxArrayIndex);
                            }

                            // If a previous remove call had marked this location as free, reset the
                            // array as 0, so that the next call will walk again.  The return of this CAS
                            // is irrelevant, it could have been reset by another remove
                            InterlockedCompareExchange((volatile LONG *) &node->m_searchIndex, 
                                (LONG) _ARRAYNODE_NOTFULL, (LONG) i);

                            break;
                        }

                    }
                }

                //
                // If nothing was inserted during this pass, try and mark the array as FULL (-2) and 
                // move on to the next array to search, creating a new one if necessary.  If a remove 
                // of an element in this array happened in the meantime, that's okay, the next Add to
                // this ListArray will happen in that location
                //
                if (inserted == false)
                {
                    //
                    // Try to set this array in "Full" mode.  If an intervening Remove() happened, this
                    // CAS will fail. This current element will just be stored somewhere in the next array
                    //
                    InterlockedCompareExchange((volatile LONG *) &node->m_searchIndex, 
                        (LONG) _ARRAYNODE_FULL, (LONG) _ARRAYNODE_NOTFULL);
                    index += m_arrayLength;

                    //
                    // Try and increase the size of this ListArray
                    //
                    if (node->m_pNext == NULL)
                    {
                        if (InterlockedCompareExchangePointer((PVOID volatile *) &node->m_pNext, (PVOID) s_nonNull, NULL) == NULL)
                        {
                            //
                            // Create a new element array, this is were the actual elements are stored
                            //
                            ELEMENT **elementArray = new ELEMENT*[m_arrayLength];
                            memset(elementArray, 0, m_arrayLength*sizeof(ELEMENT*));

                            //
                            // Create an ArrayNode, which is a wrapper around each element array
                            //
                            ArrayNode *pNode = new ArrayNode(elementArray);

                            //
                            // The m_ppArrayNodes array is used for fast index into the list array
                            // It supports up to 512 ArrayNodes, each with m_arrayLength elements
                            // if we exceed this number, additional array nodes are accessed by as
                            // a linked list off of the last element.
                            //
                            // Note: this is safe since the CAS to s_nonNull is effectively a lock on this until the publication of
                            // pNode below.  **EVERYTHING** must be set up before pNode is published and the relative ordering
                            // of node, node->m_pNext must concur with m_ppArrayNodes[m_nextArrayNodeSlot - 1], 
                            // m_nextArrayNodeSlot]
                            //
                            if (m_nextArrayNodeSlot < m_arrayNodesSize)
                                m_ppArrayNodes[m_nextArrayNodeSlot++] = pNode;

                            _InterlockedExchangePointer((PVOID volatile *) &node->m_pNext, pNode);

                        }
                    }

                    //
                    // Make sure the next array is ready.
                    //
                    if ((size_t) node->m_pNext == s_nonNull)
                    {
                        _SpinWaitBackoffNone spinWait;
                        do
                        {
                            spinWait._SpinOnce();
                        } while ((size_t) node->m_pNext == s_nonNull) ;
                    }
                }
                
                ASSERT(inserted == true || (inserted == false && node->m_pNext != NULL));

                // Move to the next array
                node = node->m_pNext;
            }

            ASSERT(index >= 0);

            return index;
        }

        /// <summary>
        ///     Add a free element into the free pool.  Ignore depth.
        /// </summary>
        /// <param name="element">
        ///     The element being inserted 
        /// </param>
        void AddToFreePool(ELEMENT * element)
        {
            //
            // Add this removed element to the free pool
            //
            InterlockedPushEntrySList(&m_freeElementPool, &(element->m_listArrayFreeLink));
        }

        /// <summary>
        ///     Remove an element from the array
        /// </summary>
        /// <param name="element">
        ///     A pointer to the element being removed
        /// </param>
        /// <param name="addToFreePool">
        ///     Whether we want this removed element to be added to the free pool for reuse
        /// </param>
        /// <returns>
        ///     False when the element does not exist.
        /// </returns>
        bool Remove(ELEMENT * element, bool addToFreePool = true)
        {
            return Remove(element, element->m_listArrayIndex, addToFreePool);
        }

        /// <summary>
        ///     Remove an element from the array
        /// </summary>
        /// <param name="element">
        ///     A pointer to the element being removed
        /// </param>
        /// <param name="listArrayIndex">
        ///     ListArrayIndex of element.
        /// </param>
        /// <param name="addToFreePool">
        ///     Whether we want this removed element to be added to the free pool for reuse
        /// </param>
        /// <returns>
        ///     False when the element does not exist.
        /// </returns>
        bool Remove(ELEMENT * element, int listArrayIndex, bool addToFreePool = true)
        {
            int arrayIndex = listArrayIndex >> m_shiftBits;
            int removeIndex = listArrayIndex & m_arrayLength-1;

            //
            // The element clearly does not exist.
            //
            if (arrayIndex >= m_nextArrayNodeSlot)
            {
                return false;
            }

            ArrayNode * node = NULL;
            if (arrayIndex >= m_arrayNodesSize)
            {
                // If this is actually an element that exceeded the m_ppArrayNodes index,
                // run through the linked list to find the right arrayNode to access.
                // This will only occur with very large number of items in the ListArray
                node = m_ppArrayNodes[m_arrayNodesSize-1];
                for (int i = 0; i <= arrayIndex - m_arrayNodesSize; i++)
                {
                    node = node->m_pNext;
                }
            }
            else
            {
                node = m_ppArrayNodes[arrayIndex];
            }

            ELEMENT ** elementArray = node->m_ppArray;

            //
            // Try and remove the element from the array
            //
            volatile PVOID oldPtr = (PVOID) element;
            volatile PVOID initPtr = InterlockedCompareExchangePointer((volatile PVOID *) &elementArray[removeIndex], 
                (PVOID) NULL, (PVOID) oldPtr);

            if (initPtr == oldPtr)
            {
                //
                // If the remove was successful, then update the Array node to know that the array is not full
                //
                InterlockedCompareExchange((volatile LONG *) &node->m_searchIndex,
                        (LONG) removeIndex, (LONG) _ARRAYNODE_FULL);
            }
            else
            {
                return false;
            }

            //
            // Add this item to the free list.  The AddToFreePool flag is necessary because some elements, like the
            // WorkQueue, don't actually want to remove an element for and have it reused by someone else.  It is 
            // removing it from one ListArray in order to place it on another.
            //
            if (addToFreePool)
            {
                //
                // Check if the number of elements in the free pool has exceeded the threshold for deletion
                // If so, put this element on the deletion pool rather than the free pool
                //

                if (QueryDepthSList(&m_freeElementPool) > m_deletionThreshold)
                {
                    ASSERT(m_deletionThreshold != DeletionThresholdInfinite);

                    //
                    // Add this removed element to the deletion pool
                    //
                    InterlockedPushEntrySList(&m_elementsToDelete, &(element->m_listArrayFreeLink)); 

                    int elementsToDeleteDepth = QueryDepthSList(&m_elementsToDelete);

                    //
                    // Try marking this list array as the one we want to delete from
                    // if the length of the deletion list has hit the threshold
                    //
                    if (elementsToDeleteDepth > m_deletionThreshold && 
                        m_pScheduler->HasCompletedShutdown() == false &&
                        InterlockedCompareExchange(&m_fHasElementsToDelete, TRUE, FALSE) == FALSE)
                    {
                        ASSERT(m_deletionList == NULL);

                        // Take a snapshot of the deletion pool, these are the elements we will actually delete
                        m_deletionList = InterlockedFlushSList(&m_elementsToDelete);

                        //
                        // Inform the scheduler to call us at the next safe point for deletion.  This will guarantee that no virtual
                        // processor has a handle to any of the objects we are deleting.
                        //
                        m_deletionSafePoint.InvokeAtNextSafePoint(reinterpret_cast<SafePointInvocation::InvocationFunction>(&CheckForDeletionBridge), this, m_pScheduler);

                    }
                }
                else
                {
                    //
                    // Add this removed element to the free pool
                    //
                    InterlockedPushEntrySList(&m_freeElementPool, &(element->m_listArrayFreeLink));
                }
            }
            return true;
        }

        /// <summary>
        ///     Index operator for the ListArray
        /// </summary>
        /// <param name="index">
        ///     The index being retreived
        /// </param>
        /// <returns>
        ///     The element being accessed
        /// </returns>
        ELEMENT * operator[](int index) const
        {
            int arrayIndex = index >> m_shiftBits;

            if (arrayIndex >= m_nextArrayNodeSlot)
            {
                return NULL;
            }

            ArrayNode * node = NULL;
            if (arrayIndex >= m_arrayNodesSize)
            {
                // If this is actually an element that exceeded the m_ppArrayNodes index,
                // run through the linked list to find the right arrayNode to access.
                // This will only occur with very large number of items in the ListArray
                node = m_ppArrayNodes[m_arrayNodesSize-1];
                for (int i = 0; i <= arrayIndex - m_arrayNodesSize; i++)
                {
                    node = node->m_pNext;
                }
            }
            else
            {
                node = m_ppArrayNodes[arrayIndex];
            }

            // Index into the array at position (index & m_arrayLength-1), this is the element 
            return node->m_ppArray[index & m_arrayLength-1];
        }

        /// <summary>
        ///     Called in order to retrieve an item from the free pool for reuse
        /// </summary>
        /// <remarks>
        ///     The user of this ListArray is responsible for repurposing this returned object for reuse.
        ///     Thus, reinitialization of the ELEMENT may need to occur
        /// </remarks>
        /// <returns>
        ///     An element from the free pool
        /// </returns>
        ELEMENT * PullFromFreePool()
        {
            PSLIST_ENTRY pListEntry = InterlockedPopEntrySList(&m_freeElementPool);
            if (pListEntry == NULL)
            {
                return NULL;
            }
            ELEMENT * returnElement = CONTAINING_RECORD(pListEntry, ELEMENT, m_listArrayFreeLink);
            return returnElement;
        }

        /// <summary>
        ///     Called in order to retrieve the maximum size the ListArray has grown to
        /// </summary>
        /// <remarks>
        ///     This is used to index into the array
        /// </remarks>
        /// <returns>
        ///     The maximum size of the array
        /// </returns>
        int MaxIndex()
        {
            return m_maxArrayIndex;
        }
    public:

        static const int DeletionThresholdInfinite = INT_MAX;

    private:

        /// <summary>
        ///     A function to check whether a deletion needs to occur
        /// </summary>
        /// <remarks>
        ///     This function assumes that all virtual processors have already reached their safe point.
        /// </remarks>
        void CheckForDeletion()
        {
            // Early return from this function if:
            // 1. The scheduler is already in its shutdown process -- the entire list array will be deleted anyway 
            // 2. The scheduler has not been set in cleanup mode
            if (m_pScheduler->HasCompletedShutdown())
            {
                return;
            }

            DeleteElements(m_deletionList);
            m_deletionList = NULL;
            
            //
            // Allow other deletions to happen on this list array.
            //
            InterlockedExchange(&m_fHasElementsToDelete, FALSE);
        }

        /// <summary>
        ///     A thunk to CheckForDeletion that safe point invocation will call.
        /// </summary>
        static void CheckForDeletionBridge(ListArray<ELEMENT> *pThis)
        {
            pThis->CheckForDeletion();
        }

        /// <summary>
        ///     A function that deletes all the elements of an SList pointed to by a PSLIST_ENTRY
        /// </summary>
        /// <param name="pListEntry">
        ///     The head node of the list being deleted.
        /// </param>
        void DeleteElements(PSLIST_ENTRY pListEntry)
        {
            while (pListEntry != NULL)
            {
                ELEMENT *pElement = CONTAINING_RECORD(pListEntry, ELEMENT, m_listArrayFreeLink);
                pListEntry = pListEntry->Next;
                _InternalDeleteHelper<ELEMENT>(pElement);
            }
        }

        // The scheduler instance the listarray belongs to.
        Concurrency::details::SchedulerBase * m_pScheduler; 

        // The bucketlength of each array
        int m_arrayLength;
        // The number of bits to shift an index by
        int m_shiftBits;

        // The head of the ListArray
        ArrayNode * m_pArrayHead;

        // An Array of pointers to each of the ArrayNodes that are created
        ArrayNode ** m_ppArrayNodes;
        // The current size of the m_ppArrayNodes array
        int m_arrayNodesSize;
        // The next ArrayNode slot that should be inserted into
        int m_nextArrayNodeSlot;

        // The farthest into the array any element has been inserted
        // used for iterating on this array
        volatile long m_maxArrayIndex;

        // The maximum number of elements this array should hold before it begins deletion some
        int m_deletionThreshold;

        // A flag indicating whether or not this ListArray has elements that it wants to delete
        // This set to true immediately after elements have successfully been moved from the 
        // free pool to the deletion list.
        // It is checked in "Check for Deletion" to ensure that only one thread is actually doing
        // the delete of elements, and reset to false.
        volatile long m_fHasElementsToDelete;

        static const size_t s_nonNull = 1;
    };


    template<class T>
    struct ListArrayInlineLink
    {
        int m_listArrayIndex;
        SLIST_ENTRY m_listArrayFreeLink;

        T* m_pObject;
    };
} // namespace details
} // namespace Concurrency