dpa.c

ReactOS是一些高手根据Windows XP的内核编写出的类XP。内核实现机理和API函数调用几乎相同。甚至可以兼容XP的程序。喜欢研究系统内核的人可以看一看。

    if (!hdpa->ptrs) {
        WARN("no pointer array.\n");
        return NULL;
    }
    if ((nIndex < 0) || (nIndex >= hdpa->nItemCount)) {
        WARN("not enough pointers in array (%d vs %d).\n",nIndex,hdpa->nItemCount);
        return NULL;
    }

    TRACE("-- %p\n", hdpa->ptrs[nIndex]);

    return hdpa->ptrs[nIndex];
}


/**************************************************************************
 * DPA_GetPtrIndex [COMCTL32.333]
 *
 * Retrieves the index of the specified pointer
 *
 * PARAMS
 *     hdpa   [I] handle (pointer) to the pointer array
 *     p      [I] pointer
 *
 * RETURNS
 *     Success: index of the specified pointer
 *     Failure: -1
 */
INT WINAPI DPA_GetPtrIndex (const HDPA hdpa, LPVOID p)
{
    INT i;

    if (!hdpa || !hdpa->ptrs)
        return -1;

    for (i = 0; i < hdpa->nItemCount; i++) {
        if (hdpa->ptrs[i] == p)
            return i;
    }

    return -1;
}


/**************************************************************************
 * DPA_InsertPtr [COMCTL32.334]
 *
 * Inserts a pointer into a dynamic pointer array
 *
 * PARAMS
 *     hdpa [I] handle (pointer) to the array
 *     i    [I] array index
 *     p    [I] pointer to insert
 *
 * RETURNS
 *     Success: index of the inserted pointer
 *     Failure: -1
 */
INT WINAPI DPA_InsertPtr (const HDPA hdpa, INT i, LPVOID p)
{
    TRACE("(%p %d %p)\n", hdpa, i, p);

    if (!hdpa || i < 0) return -1;

    /* append item if index is out of bounds */
    i = min(hdpa->nItemCount, i);

    /* create empty spot at the end */
    if (!DPA_SetPtr(hdpa, hdpa->nItemCount, 0)) return -1;
    
    if (i != hdpa->nItemCount - 1)
        memmove (hdpa->ptrs + i + 1, hdpa->ptrs + i, 
                 (hdpa->nItemCount - i - 1) * sizeof(LPVOID));
    
    hdpa->ptrs[i] = p;
    return i;
}


/**************************************************************************
 * DPA_SetPtr [COMCTL32.335]
 *
 * Sets a pointer in the pointer array
 *
 * PARAMS
 *     hdpa [I] handle (pointer) to the pointer array
 *     i    [I] index of the pointer that will be set
 *     p    [I] pointer to be set
 *
 * RETURNS
 *     Success: TRUE
 *     Failure: FALSE
 */
BOOL WINAPI DPA_SetPtr (const HDPA hdpa, INT i, LPVOID p)
{
    LPVOID *lpTemp;

    TRACE("(%p %d %p)\n", hdpa, i, p);

    if (!hdpa || i < 0)
        return FALSE;

    if (hdpa->nItemCount <= i) {
        /* within the old array */
        if (hdpa->nMaxCount <= i) {
            /* resize the block of memory */
            INT nNewItems =
                hdpa->nGrow * ((INT)(((i+1) - 1) / hdpa->nGrow) + 1);
            INT nSize = nNewItems * sizeof(LPVOID);

            if (hdpa->ptrs)
                lpTemp = HeapReAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY, hdpa->ptrs, nSize);
            else
                lpTemp = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY, nSize);
            
            if (!lpTemp)
                return FALSE;

            hdpa->nMaxCount = nNewItems;
            hdpa->ptrs = lpTemp;
        }
        hdpa->nItemCount = i+1;
    }

    /* put the new entry in */
    hdpa->ptrs[i] = p;

    return TRUE;
}


/**************************************************************************
 * DPA_DeletePtr [COMCTL32.336]
 *
 * Removes a pointer from the pointer array.
 *
 * PARAMS
 *     hdpa [I] handle (pointer) to the pointer array
 *     i    [I] index of the pointer that will be deleted
 *
 * RETURNS
 *     Success: deleted pointer
 *     Failure: NULL
 */
LPVOID WINAPI DPA_DeletePtr (const HDPA hdpa, INT i)
{
    LPVOID *lpDest, *lpSrc, lpTemp = NULL;
    INT  nSize;

    TRACE("(%p %d)\n", hdpa, i);

    if ((!hdpa) || i < 0 || i >= hdpa->nItemCount)
        return NULL;

    lpTemp = hdpa->ptrs[i];

    /* do we need to move ?*/
    if (i < hdpa->nItemCount - 1) {
        lpDest = hdpa->ptrs + i;
        lpSrc = lpDest + 1;
        nSize = (hdpa->nItemCount - i - 1) * sizeof(LPVOID);
        TRACE("-- move dest=%p src=%p size=%x\n",
               lpDest, lpSrc, nSize);
        memmove (lpDest, lpSrc, nSize);
    }

    hdpa->nItemCount --;

    /* free memory ?*/
    if ((hdpa->nMaxCount - hdpa->nItemCount) >= hdpa->nGrow) {
        INT nNewItems = max(hdpa->nGrow * 2, hdpa->nItemCount);
        nSize = nNewItems * sizeof(LPVOID);
        lpDest = HeapReAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
                                      hdpa->ptrs, nSize);
        if (!lpDest)
            return NULL;

        hdpa->nMaxCount = nNewItems;
        hdpa->ptrs = (LPVOID*)lpDest;
    }

    return lpTemp;
}


/**************************************************************************
 * DPA_DeleteAllPtrs [COMCTL32.337]
 *
 * Removes all pointers and reinitializes the array.
 *
 * PARAMS
 *     hdpa [I] handle (pointer) to the pointer array
 *
 * RETURNS
 *     Success: TRUE
 *     Failure: FALSE
 */
BOOL WINAPI DPA_DeleteAllPtrs (const HDPA hdpa)
{
    TRACE("(%p)\n", hdpa);

    if (!hdpa)
        return FALSE;

    if (hdpa->ptrs && (!HeapFree (hdpa->hHeap, 0, hdpa->ptrs)))
        return FALSE;

    hdpa->nItemCount = 0;
    hdpa->nMaxCount = hdpa->nGrow * 2;
    hdpa->ptrs = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
                                     hdpa->nMaxCount * sizeof(LPVOID));

    return TRUE;
}


/**************************************************************************
 * DPA_QuickSort [Internal]
 *
 * Ordinary quicksort (used by DPA_Sort).
 *
 * PARAMS
 *     lpPtrs     [I] pointer to the pointer array
 *     l          [I] index of the "left border" of the partition
 *     r          [I] index of the "right border" of the partition
 *     pfnCompare [I] pointer to the compare function
 *     lParam     [I] user defined value (3rd parameter in compare function)
 *
 * RETURNS
 *     NONE
 */
static VOID DPA_QuickSort (LPVOID *lpPtrs, INT l, INT r,
                           PFNDPACOMPARE pfnCompare, LPARAM lParam)
{
    INT m;
    LPVOID t;

    TRACE("l=%i r=%i\n", l, r);

    if (l==r)    /* one element is always sorted */
        return;
    if (r<l)     /* oops, got it in the wrong order */
        {
        DPA_QuickSort(lpPtrs, r, l, pfnCompare, lParam);
        return;
        }
    m = (l+r)/2; /* divide by two */
    DPA_QuickSort(lpPtrs, l, m, pfnCompare, lParam);
    DPA_QuickSort(lpPtrs, m+1, r, pfnCompare, lParam);

    /* join the two sides */
    while( (l<=m) && (m<r) )
    {
        if(pfnCompare(lpPtrs[l],lpPtrs[m+1],lParam)>0)
        {
            t = lpPtrs[m+1];
            memmove(&lpPtrs[l+1],&lpPtrs[l],(m-l+1)*sizeof(lpPtrs[l]));
            lpPtrs[l] = t;

            m++;
        }
        l++;
    }
}


/**************************************************************************
 * DPA_Sort [COMCTL32.338]
 *
 * Sorts a pointer array using a user defined compare function
 *
 * PARAMS
 *     hdpa       [I] handle (pointer) to the pointer array
 *     pfnCompare [I] pointer to the compare function
 *     lParam     [I] user defined value (3rd parameter of compare function)
 *
 * RETURNS
 *     Success: TRUE
 *     Failure: FALSE
 */
BOOL WINAPI DPA_Sort (const HDPA hdpa, PFNDPACOMPARE pfnCompare, LPARAM lParam)
{
    if (!hdpa || !pfnCompare)
        return FALSE;

    TRACE("(%p %p 0x%lx)\n", hdpa, pfnCompare, lParam);

    if ((hdpa->nItemCount > 1) && (hdpa->ptrs))
        DPA_QuickSort (hdpa->ptrs, 0, hdpa->nItemCount - 1,
                       pfnCompare, lParam);

    return TRUE;
}


/**************************************************************************
 * DPA_Search [COMCTL32.339]
 *
 * Searches a pointer array for a specified pointer
 *
 * PARAMS
 *     hdpa       [I] handle (pointer) to the pointer array
 *     pFind      [I] pointer to search for
 *     nStart     [I] start index
 *     pfnCompare [I] pointer to the compare function
 *     lParam     [I] user defined value (3rd parameter of compare function)
 *     uOptions   [I] search options
 *
 * RETURNS
 *     Success: index of the pointer in the array.
 *     Failure: -1
 */
INT WINAPI DPA_Search (const HDPA hdpa, LPVOID pFind, INT nStart,
                       PFNDPACOMPARE pfnCompare, LPARAM lParam, UINT uOptions)
{
    if (!hdpa || !pfnCompare || !pFind)
        return -1;

    TRACE("(%p %p %d %p 0x%08lx 0x%08x)\n",
           hdpa, pFind, nStart, pfnCompare, lParam, uOptions);

    if (uOptions & DPAS_SORTED) {
        /* array is sorted --> use binary search */
        INT l, r, x, n;
        LPVOID *lpPtr;

        l = (nStart == -1) ? 0 : nStart;
        r = hdpa->nItemCount - 1;
        lpPtr = hdpa->ptrs;
        while (r >= l) {
            x = (l + r) / 2;
            n = (pfnCompare)(pFind, lpPtr[x], lParam);
            if (n == 0)
                return x;
            else if (n < 0)
                r = x - 1;
            else /* (n > 0) */
                l = x + 1;
        }
        if (uOptions & (DPAS_INSERTBEFORE|DPAS_INSERTAFTER)) return l;
    }
    else {
        /* array is not sorted --> use linear search */
        LPVOID *lpPtr;
        INT  nIndex;

        nIndex = (nStart == -1)? 0 : nStart;
        lpPtr = hdpa->ptrs;
        for (; nIndex < hdpa->nItemCount; nIndex++) {
            if ((pfnCompare)(pFind, lpPtr[nIndex], lParam) == 0)
                return nIndex;
        }
    }

    return -1;
}


/**************************************************************************
 * DPA_CreateEx [COMCTL32.340]
 *
 * Creates a dynamic pointer array using the specified size and heap.
 *
 * PARAMS
 *     nGrow [I] number of items by which the array grows when it is filled
 *     hHeap [I] handle to the heap where the array is stored
 *
 * RETURNS
 *     Success: handle (pointer) to the pointer array.
 *     Failure: NULL
 *
 * NOTES
 *     The DPA_ functions can be used to create and manipulate arrays of
 *     pointers.
 */
HDPA WINAPI DPA_CreateEx (INT nGrow, HANDLE hHeap)
{
    HDPA hdpa;

    TRACE("(%d %p)\n", nGrow, hHeap);

    if (hHeap)
        hdpa = HeapAlloc (hHeap, HEAP_ZERO_MEMORY, sizeof(*hdpa));
    else
        hdpa = Alloc (sizeof(*hdpa));

    if (hdpa) {
        hdpa->nGrow = max(8, nGrow);
        hdpa->hHeap = hHeap ? hHeap : GetProcessHeap();
        hdpa->nMaxCount = hdpa->nGrow * 2;
        hdpa->ptrs = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
                                hdpa->nMaxCount * sizeof(LPVOID));
    }

    TRACE("-- %p\n", hdpa);

    return hdpa;
}


/**************************************************************************
 * DPA_Create [COMCTL32.328]
 *
 * Creates a dynamic pointer array.
 *
 * PARAMS
 *     nGrow [I] number of items by which the array grows when it is filled
 *
 * RETURNS
 *     Success: handle (pointer) to the pointer array.
 *     Failure: NULL
 *
 * NOTES
 *     The DPA_ functions can be used to create and manipulate arrays of
 *     pointers.
 */
HDPA WINAPI DPA_Create (INT nGrow)
{
    return DPA_CreateEx( nGrow, 0 );
}


/**************************************************************************
 * DPA_EnumCallback [COMCTL32.385]
 *
 * Enumerates all items in a dynamic pointer array.
 *
 * PARAMS
 *     hdpa     [I] handle to the dynamic pointer array
 *     enumProc [I]
 *     lParam   [I]
 *
 * RETURNS
 *     none
 */
VOID WINAPI DPA_EnumCallback (HDPA hdpa, PFNDPAENUMCALLBACK enumProc,
                              LPVOID lParam)
{
    INT i;

    TRACE("(%p %p %p)\n", hdpa, enumProc, lParam);

    if (!hdpa)
        return;
    if (hdpa->nItemCount <= 0)
        return;

    for (i = 0; i < hdpa->nItemCount; i++) {
        if ((enumProc)(hdpa->ptrs[i], lParam) == 0)
            return;
    }

    return;
}


/**************************************************************************
 * DPA_DestroyCallback [COMCTL32.386]
 *
 * Enumerates all items in a dynamic pointer array and destroys it.
 *
 * PARAMS
 *     hdpa     [I] handle to the dynamic pointer array
 *     enumProc [I]
 *     lParam   [I]
 *
 * RETURNS
 *     none
 */
void WINAPI DPA_DestroyCallback (HDPA hdpa, PFNDPAENUMCALLBACK enumProc,
                                 LPVOID lParam)
{
    TRACE("(%p %p %p)\n", hdpa, enumProc, lParam);

    DPA_EnumCallback (hdpa, enumProc, lParam);
    DPA_Destroy (hdpa);
}