dlls/comctl32/dpa.c

   1 /*
   2  * Dynamic pointer array (DPA) implementation
   3  *
   4  * Copyright 1998 Eric Kohl
   5  *           1998 Juergen Schmied <j.schmied@metronet.de>
   6  *           2000 Eric Kohl for CodeWeavers
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  21  *
  22  * NOTES
  23  *     These functions were involuntarily documented by Microsoft in 2002 as
  24  *     the outcome of an anti-trust suit brought by various U.S. governments.
  25  *     As a result the specifications on MSDN are inaccurate, incomplete
  26  *     and misleading. A much more complete (unofficial) documentation is
  27  *     available at:
  28  *
  29  *     http://members.ozemail.com.au/~geoffch/samples/win32/shell/comctl32
  30  */
  31
  32 #define COBJMACROS
  33
  34 #include <stdarg.h>
  35 #include <limits.h>
  36
  37 #include "windef.h"
  38 #include "winbase.h"
  39 #include "winuser.h"
  40 #include "commctrl.h"
  41 #include "objbase.h"
  42
  43 #include "comctl32.h"
  44 #include "wine/debug.h"
  45
  46 WINE_DEFAULT_DEBUG_CHANNEL(dpa);
  47
  48 typedef struct _DPA
  49 {
  50     INT    nItemCount;
  51     LPVOID   *ptrs;
  52     HANDLE hHeap;
  53     INT    nGrow;
  54     INT    nMaxCount;
  55 } DPA;
  56
  57 typedef struct _STREAMDATA
  58 {
  59     DWORD dwSize;
  60     DWORD dwData2;
  61     DWORD dwItems;
  62 } STREAMDATA, *PSTREAMDATA;
  63
  64 /**************************************************************************
  65  * DPA_LoadStream [COMCTL32.9]
  66  *
  67  * Loads a dynamic pointer array from a stream
  68  *
  69  * PARAMS
  70  *     phDpa    [O] pointer to a handle to a dynamic pointer array
  71  *     loadProc [I] pointer to a callback function
  72  *     pStream  [I] pointer to a stream
  73  *     pData    [I] pointer to callback data
  74  *
  75  * RETURNS
  76  *     Success: S_OK, S_FALSE - partial success
  77  *     Failure: HRESULT error code
  78  *
  79  * NOTES
  80  *     No more information available yet!
  81  */
  82 HRESULT WINAPI DPA_LoadStream (HDPA *phDpa, PFNDPASTREAM loadProc,
  83                                IStream *pStream, LPVOID pData)
  84 {
  85     HRESULT errCode;
  86     LARGE_INTEGER position;
  87     ULARGE_INTEGER initial_pos;
  88     STREAMDATA  streamData;
  89     DPASTREAMINFO streamInfo;
  90     ULONG ulRead;
  91     HDPA hDpa;
  92     PVOID *ptr;
  93
  94     TRACE ("phDpa=%p loadProc=%p pStream=%p pData=%p\n",
  95            phDpa, loadProc, pStream, pData);
  96
  97     if (!phDpa || !loadProc || !pStream)
  98         return E_INVALIDARG;
  99
 100     *phDpa = NULL;
 101
 102     position.QuadPart = 0;
 103
 104     errCode = IStream_Seek (pStream, position, STREAM_SEEK_CUR, &initial_pos);
 105     if (errCode != S_OK)
 106         return errCode;
 107
 108     memset(&streamData, 0, sizeof(STREAMDATA));
 109     errCode = IStream_Read (pStream, &streamData, sizeof(STREAMDATA), &ulRead);
 110     if (errCode != S_OK)
 111         return errCode;
 112
 113     TRACE ("dwSize=%u dwData2=%u dwItems=%u\n",
 114            streamData.dwSize, streamData.dwData2, streamData.dwItems);
 115
 116     if (ulRead < sizeof(STREAMDATA) ||
 117         streamData.dwSize < sizeof(STREAMDATA) || streamData.dwData2 != 1) {
 118         /* back to initial position */
 119         position.QuadPart = initial_pos.QuadPart;
 120         IStream_Seek (pStream, position, STREAM_SEEK_SET, NULL);
 121         return E_FAIL;
 122     }
 123
 124     if (streamData.dwItems > (UINT_MAX / 2 / sizeof(VOID*))) /* 536870911 */
 125         return E_OUTOFMEMORY;
 126
 127     /* create the dpa */
 128     hDpa = DPA_Create (streamData.dwItems);
 129     if (!hDpa)
 130         return E_OUTOFMEMORY;
 131
 132     if (!DPA_Grow (hDpa, streamData.dwItems))
 133         return E_OUTOFMEMORY;
 134
 135     /* load data from the stream into the dpa */
 136     ptr = hDpa->ptrs;
 137     for (streamInfo.iPos = 0; streamInfo.iPos < streamData.dwItems; streamInfo.iPos++) {
 138         errCode = (loadProc)(&streamInfo, pStream, pData);
 139         if (errCode != S_OK) {
 140             errCode = S_FALSE;
 141             break;
 142         }
 143
 144         *ptr = streamInfo.pvItem;
 145         ptr++;
 146     }
 147
 148     /* set the number of items */
 149     hDpa->nItemCount = streamInfo.iPos;
 150
 151     /* store the handle to the dpa */
 152     *phDpa = hDpa;
 153     TRACE ("new hDpa=%p, errorcode=%x\n", hDpa, errCode);
 154
 155     return errCode;
 156 }
 157
 158
 159 /**************************************************************************
 160  * DPA_SaveStream [COMCTL32.10]
 161  *
 162  * Saves a dynamic pointer array to a stream
 163  *
 164  * PARAMS
 165  *     hDpa     [I] handle to a dynamic pointer array
 166  *     saveProc [I] pointer to a callback function
 167  *     pStream  [I] pointer to a stream
 168  *     pData    [I] pointer to callback data
 169  *
 170  * RETURNS
 171  *     Success: S_OK, S_FALSE - partial success
 172  *     Failure: HRESULT error code
 173  *
 174  * NOTES
 175  *     No more information available yet!
 176  */
 177 HRESULT WINAPI DPA_SaveStream (const HDPA hDpa, PFNDPASTREAM saveProc,
 178                                IStream *pStream, LPVOID pData)
 179 {
 180     LARGE_INTEGER position;
 181     ULARGE_INTEGER initial_pos, curr_pos;
 182     STREAMDATA  streamData;
 183     DPASTREAMINFO streamInfo;
 184     HRESULT hr;
 185     PVOID *ptr;
 186
 187     TRACE ("hDpa=%p saveProc=%p pStream=%p pData=%p\n",
 188             hDpa, saveProc, pStream, pData);
 189
 190     if (!hDpa || !saveProc || !pStream) return E_INVALIDARG;
 191
 192     /* save initial position to write header after completion */
 193     position.QuadPart = 0;
 194     hr = IStream_Seek (pStream, position, STREAM_SEEK_CUR, &initial_pos);
 195     if (hr != S_OK)
 196         return hr;
 197
 198     /* write empty header */
 199     streamData.dwSize  = sizeof(streamData);
 200     streamData.dwData2 = 1;
 201     streamData.dwItems = 0;
 202
 203     hr = IStream_Write (pStream, &streamData, sizeof(streamData), NULL);
 204     if (hr != S_OK) {
 205         position.QuadPart = initial_pos.QuadPart;
 206         IStream_Seek (pStream, position, STREAM_SEEK_SET, NULL);
 207         return hr;
 208     }
 209
 210     /* no items - we're done */
 211     if (hDpa->nItemCount == 0) return S_OK;
 212
 213     ptr = hDpa->ptrs;
 214     for (streamInfo.iPos = 0; streamInfo.iPos < hDpa->nItemCount; streamInfo.iPos++) {
 215         streamInfo.pvItem = *ptr;
 216         hr = (saveProc)(&streamInfo, pStream, pData);
 217         if (hr != S_OK) {
 218             hr = S_FALSE;
 219             break;
 220         }
 221         ptr++;
 222     }
 223
 224     /* write updated header */
 225     position.QuadPart = 0;
 226     IStream_Seek (pStream, position, STREAM_SEEK_CUR, &curr_pos);
 227
 228     streamData.dwSize  = curr_pos.QuadPart - initial_pos.QuadPart;
 229     streamData.dwData2 = 1;
 230     streamData.dwItems = streamInfo.iPos;
 231
 232     position.QuadPart = initial_pos.QuadPart;
 233     IStream_Seek (pStream, position, STREAM_SEEK_SET, NULL);
 234     IStream_Write (pStream, &streamData, sizeof(streamData), NULL);
 235
 236     position.QuadPart = curr_pos.QuadPart;
 237     IStream_Seek (pStream, position, STREAM_SEEK_SET, NULL);
 238
 239     return hr;
 240 }
 241
 242
 243 /**************************************************************************
 244  * DPA_Merge [COMCTL32.11]
 245  *
 246  * Merge two dynamic pointers arrays.
 247  *
 248  * PARAMS
 249  *     hdpa1       [I] handle to a dynamic pointer array
 250  *     hdpa2       [I] handle to a dynamic pointer array
 251  *     dwFlags     [I] flags
 252  *     pfnCompare  [I] pointer to sort function
 253  *     pfnMerge    [I] pointer to merge function
 254  *     lParam      [I] application specific value
 255  *
 256  * RETURNS
 257  *     Success: TRUE
 258  *     Failure: FALSE
 259  *
 260  * NOTES
 261  *     No more information available yet!
 262  */
 263 BOOL WINAPI DPA_Merge (HDPA hdpa1, HDPA hdpa2, DWORD dwFlags,
 264                        PFNDPACOMPARE pfnCompare, PFNDPAMERGE pfnMerge,
 265                        LPARAM lParam)
 266 {
 267     INT nCount;
 268     LPVOID *pWork1, *pWork2;
 269     INT nResult, i;
 270     INT nIndex;
 271
 272     TRACE("%p %p %08x %p %p %08lx)\n",
 273            hdpa1, hdpa2, dwFlags, pfnCompare, pfnMerge, lParam);
 274
 275     if (IsBadWritePtr (hdpa1, sizeof(*hdpa1)))
 276         return FALSE;
 277
 278     if (IsBadWritePtr (hdpa2, sizeof(*hdpa2)))
 279         return FALSE;
 280
 281     if (IsBadCodePtr ((FARPROC)pfnCompare))
 282         return FALSE;
 283
 284     if (IsBadCodePtr ((FARPROC)pfnMerge))
 285         return FALSE;
 286
 287     if (!(dwFlags & DPAM_SORTED)) {
 288         TRACE("sorting dpa's!\n");
 289         if (hdpa1->nItemCount > 0)
 290         DPA_Sort (hdpa1, pfnCompare, lParam);
 291         TRACE ("dpa 1 sorted!\n");
 292         if (hdpa2->nItemCount > 0)
 293         DPA_Sort (hdpa2, pfnCompare, lParam);
 294         TRACE ("dpa 2 sorted!\n");
 295     }
 296
 297     if (hdpa2->nItemCount < 1)
 298         return TRUE;
 299
 300     TRACE("hdpa1->nItemCount=%d hdpa2->nItemCount=%d\n",
 301            hdpa1->nItemCount, hdpa2->nItemCount);
 302
 303
 304     /* working but untrusted implementation */
 305
 306     pWork1 = &(hdpa1->ptrs[hdpa1->nItemCount - 1]);
 307     pWork2 = &(hdpa2->ptrs[hdpa2->nItemCount - 1]);
 308
 309     nIndex = hdpa1->nItemCount - 1;
 310     nCount = hdpa2->nItemCount - 1;
 311
 312     do
 313     {
 314         if (nIndex < 0) {
 315             if ((nCount >= 0) && (dwFlags & DPAM_UNION)) {
 316                 /* Now insert the remaining new items into DPA 1 */
 317                 TRACE("%d items to be inserted at start of DPA 1\n",
 318                       nCount+1);
 319                 for (i=nCount; i>=0; i--) {
 320                     PVOID ptr;
 321
 322                     ptr = (pfnMerge)(DPAMM_INSERT, *pWork2, NULL, lParam);
 323                     if (!ptr)
 324                         return FALSE;
 325                     DPA_InsertPtr (hdpa1, 0, ptr);
 326                     pWork2--;
 327                 }
 328             }
 329             break;
 330         }
 331         nResult = (pfnCompare)(*pWork1, *pWork2, lParam);
 332         TRACE("compare result=%d, dpa1.cnt=%d, dpa2.cnt=%d\n",
 333               nResult, nIndex, nCount);
 334
 335         if (nResult == 0)
 336         {
 337             PVOID ptr;
 338
 339             ptr = (pfnMerge)(DPAMM_MERGE, *pWork1, *pWork2, lParam);
 340             if (!ptr)
 341                 return FALSE;
 342
 343             nCount--;
 344             pWork2--;
 345             *pWork1 = ptr;
 346             nIndex--;
 347             pWork1--;
 348         }
 349         else if (nResult > 0)
 350         {
 351             /* item in DPA 1 missing from DPA 2 */
 352             if (dwFlags & DPAM_INTERSECT)
 353             {
 354                 /* Now delete the extra item in DPA1 */
 355                 PVOID ptr;
 356
 357                 ptr = DPA_DeletePtr (hdpa1, nIndex);
 358
 359                 (pfnMerge)(DPAMM_DELETE, ptr, NULL, lParam);
 360             }
 361             nIndex--;
 362             pWork1--;
 363         }
 364         else
 365         {
 366             /* new item in DPA 2 */
 367             if (dwFlags & DPAM_UNION)
 368             {
 369                 /* Now insert the new item in DPA 1 */
 370                 PVOID ptr;
 371
 372                 ptr = (pfnMerge)(DPAMM_INSERT, *pWork2, NULL, lParam);
 373                 if (!ptr)
 374                     return FALSE;
 375                 DPA_InsertPtr (hdpa1, nIndex+1, ptr);
 376             }
 377             nCount--;
 378             pWork2--;
 379         }
 380
 381     }
 382     while (nCount >= 0);
 383
 384     return TRUE;
 385 }
 386
 387
 388 /**************************************************************************
 389  * DPA_Destroy [COMCTL32.329]
 390  *
 391  * Destroys a dynamic pointer array
 392  *
 393  * PARAMS
 394  *     hdpa [I] handle (pointer) to the pointer array
 395  *
 396  * RETURNS
 397  *     Success: TRUE
 398  *     Failure: FALSE
 399  */
 400 BOOL WINAPI DPA_Destroy (const HDPA hdpa)
 401 {
 402     TRACE("(%p)\n", hdpa);
 403
 404     if (!hdpa)
 405         return FALSE;
 406
 407     if (hdpa->ptrs && (!HeapFree (hdpa->hHeap, 0, hdpa->ptrs)))
 408         return FALSE;
 409
 410     return HeapFree (hdpa->hHeap, 0, hdpa);
 411 }
 412
 413
 414 /**************************************************************************
 415  * DPA_Grow [COMCTL32.330]
 416  *
 417  * Sets the growth amount.
 418  *
 419  * PARAMS
 420  *     hdpa  [I] handle (pointer) to the existing (source) pointer array
 421  *     nGrow [I] number of items by which the array grows when it's too small
 422  *
 423  * RETURNS
 424  *     Success: TRUE
 425  *     Failure: FALSE
 426  */
 427 BOOL WINAPI DPA_Grow (HDPA hdpa, INT nGrow)
 428 {
 429     TRACE("(%p %d)\n", hdpa, nGrow);
 430
 431     if (!hdpa)
 432         return FALSE;
 433
 434     hdpa->nGrow = max(8, nGrow);
 435
 436     return TRUE;
 437 }
 438
 439
 440 /**************************************************************************
 441  * DPA_Clone [COMCTL32.331]
 442  *
 443  * Copies a pointer array to an other one or creates a copy
 444  *
 445  * PARAMS
 446  *     hdpa    [I] handle (pointer) to the existing (source) pointer array
 447  *     hdpaNew [O] handle (pointer) to the destination pointer array
 448  *
 449  * RETURNS
 450  *     Success: pointer to the destination pointer array.
 451  *     Failure: NULL
 452  *
 453  * NOTES
 454  *     - If the 'hdpaNew' is a NULL-Pointer, a copy of the source pointer
 455  *       array will be created and it's handle (pointer) is returned.
 456  *     - If 'hdpa' is a NULL-Pointer, the original implementation crashes,
 457  *       this implementation just returns NULL.
 458  */
 459 HDPA WINAPI DPA_Clone (const HDPA hdpa, const HDPA hdpaNew)
 460 {
 461     INT nNewItems, nSize;
 462     HDPA hdpaTemp;
 463
 464     if (!hdpa)
 465         return NULL;
 466
 467     TRACE("(%p %p)\n", hdpa, hdpaNew);
 468
 469     if (!hdpaNew) {
 470         /* create a new DPA */
 471         hdpaTemp = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
 472                                     sizeof(*hdpaTemp));
 473         hdpaTemp->hHeap = hdpa->hHeap;
 474         hdpaTemp->nGrow = hdpa->nGrow;
 475     }
 476     else
 477         hdpaTemp = hdpaNew;
 478
 479     if (hdpaTemp->ptrs) {
 480         /* remove old pointer array */
 481         HeapFree (hdpaTemp->hHeap, 0, hdpaTemp->ptrs);
 482         hdpaTemp->ptrs = NULL;
 483         hdpaTemp->nItemCount = 0;
 484         hdpaTemp->nMaxCount = 0;
 485     }
 486
 487     /* create a new pointer array */
 488     nNewItems = hdpaTemp->nGrow *
 489                 (((hdpa->nItemCount - 1) / hdpaTemp->nGrow) + 1);
 490     nSize = nNewItems * sizeof(LPVOID);
 491     hdpaTemp->ptrs = HeapAlloc (hdpaTemp->hHeap, HEAP_ZERO_MEMORY, nSize);
 492     hdpaTemp->nMaxCount = nNewItems;
 493
 494     /* clone the pointer array */
 495     hdpaTemp->nItemCount = hdpa->nItemCount;
 496     memmove (hdpaTemp->ptrs, hdpa->ptrs,
 497              hdpaTemp->nItemCount * sizeof(LPVOID));
 498
 499     return hdpaTemp;
 500 }
 501
 502
 503 /**************************************************************************
 504  * DPA_GetPtr [COMCTL32.332]
 505  *
 506  * Retrieves a pointer from a dynamic pointer array
 507  *
 508  * PARAMS
 509  *     hdpa   [I] handle (pointer) to the pointer array
 510  *     nIndex [I] array index of the desired pointer
 511  *
 512  * RETURNS
 513  *     Success: pointer
 514  *     Failure: NULL
 515  */
 516 LPVOID WINAPI DPA_GetPtr (const HDPA hdpa, INT nIndex)
 517 {
 518     TRACE("(%p %d)\n", hdpa, nIndex);
 519
 520     if (!hdpa)
 521         return NULL;
 522     if (!hdpa->ptrs) {
 523         WARN("no pointer array.\n");
 524         return NULL;
 525     }
 526     if ((nIndex < 0) || (nIndex >= hdpa->nItemCount)) {
 527         WARN("not enough pointers in array (%d vs %d).\n",nIndex,hdpa->nItemCount);
 528         return NULL;
 529     }
 530
 531     TRACE("-- %p\n", hdpa->ptrs[nIndex]);
 532
 533     return hdpa->ptrs[nIndex];
 534 }
 535
 536
 537 /**************************************************************************
 538  * DPA_GetPtrIndex [COMCTL32.333]
 539  *
 540  * Retrieves the index of the specified pointer
 541  *
 542  * PARAMS
 543  *     hdpa   [I] handle (pointer) to the pointer array
 544  *     p      [I] pointer
 545  *
 546  * RETURNS
 547  *     Success: index of the specified pointer
 548  *     Failure: -1
 549  */
 550 INT WINAPI DPA_GetPtrIndex (HDPA hdpa, LPCVOID p)
 551 {
 552     INT i;
 553
 554     if (!hdpa || !hdpa->ptrs)
 555         return -1;
 556
 557     for (i = 0; i < hdpa->nItemCount; i++) {
 558         if (hdpa->ptrs[i] == p)
 559             return i;
 560     }
 561
 562     return -1;
 563 }
 564
 565
 566 /**************************************************************************
 567  * DPA_InsertPtr [COMCTL32.334]
 568  *
 569  * Inserts a pointer into a dynamic pointer array
 570  *
 571  * PARAMS
 572  *     hdpa [I] handle (pointer) to the array
 573  *     i    [I] array index
 574  *     p    [I] pointer to insert
 575  *
 576  * RETURNS
 577  *     Success: index of the inserted pointer
 578  *     Failure: -1
 579  */
 580 INT WINAPI DPA_InsertPtr (const HDPA hdpa, INT i, LPVOID p)
 581 {
 582     TRACE("(%p %d %p)\n", hdpa, i, p);
 583
 584     if (!hdpa || i < 0) return -1;
 585
 586     /* append item if index is out of bounds */
 587     i = min(hdpa->nItemCount, i);
 588
 589     /* create empty spot at the end */
 590     if (!DPA_SetPtr(hdpa, hdpa->nItemCount, 0)) return -1;
 591
 592     if (i != hdpa->nItemCount - 1)
 593         memmove (hdpa->ptrs + i + 1, hdpa->ptrs + i,
 594                  (hdpa->nItemCount - i - 1) * sizeof(LPVOID));
 595
 596     hdpa->ptrs[i] = p;
 597     return i;
 598 }
 599
 600
 601 /**************************************************************************
 602  * DPA_SetPtr [COMCTL32.335]
 603  *
 604  * Sets a pointer in the pointer array
 605  *
 606  * PARAMS
 607  *     hdpa [I] handle (pointer) to the pointer array
 608  *     i    [I] index of the pointer that will be set
 609  *     p    [I] pointer to be set
 610  *
 611  * RETURNS
 612  *     Success: TRUE
 613  *     Failure: FALSE
 614  */
 615 BOOL WINAPI DPA_SetPtr (const HDPA hdpa, INT i, LPVOID p)
 616 {
 617     LPVOID *lpTemp;
 618
 619     TRACE("(%p %d %p)\n", hdpa, i, p);
 620
 621     if (!hdpa || i < 0)
 622         return FALSE;
 623
 624     if (hdpa->nItemCount <= i) {
 625         /* within the old array */
 626         if (hdpa->nMaxCount <= i) {
 627             /* resize the block of memory */
 628             INT nNewItems =
 629                 hdpa->nGrow * ((((i+1) - 1) / hdpa->nGrow) + 1);
 630             INT nSize = nNewItems * sizeof(LPVOID);
 631
 632             if (hdpa->ptrs)
 633                 lpTemp = HeapReAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY, hdpa->ptrs, nSize);
 634             else
 635                 lpTemp = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY, nSize);
 636
 637             if (!lpTemp)
 638                 return FALSE;
 639
 640             hdpa->nMaxCount = nNewItems;
 641             hdpa->ptrs = lpTemp;
 642         }
 643         hdpa->nItemCount = i+1;
 644     }
 645
 646     /* put the new entry in */
 647     hdpa->ptrs[i] = p;
 648
 649     return TRUE;
 650 }
 651
 652
 653 /**************************************************************************
 654  * DPA_DeletePtr [COMCTL32.336]
 655  *
 656  * Removes a pointer from the pointer array.
 657  *
 658  * PARAMS
 659  *     hdpa [I] handle (pointer) to the pointer array
 660  *     i    [I] index of the pointer that will be deleted
 661  *
 662  * RETURNS
 663  *     Success: deleted pointer
 664  *     Failure: NULL
 665  */
 666 LPVOID WINAPI DPA_DeletePtr (const HDPA hdpa, INT i)
 667 {
 668     LPVOID *lpDest, *lpSrc, lpTemp = NULL;
 669     INT  nSize;
 670
 671     TRACE("(%p %d)\n", hdpa, i);
 672
 673     if ((!hdpa) || i < 0 || i >= hdpa->nItemCount)
 674         return NULL;
 675
 676     lpTemp = hdpa->ptrs[i];
 677
 678     /* do we need to move ?*/
 679     if (i < hdpa->nItemCount - 1) {
 680         lpDest = hdpa->ptrs + i;
 681         lpSrc = lpDest + 1;
 682         nSize = (hdpa->nItemCount - i - 1) * sizeof(LPVOID);
 683         TRACE("-- move dest=%p src=%p size=%x\n",
 684                lpDest, lpSrc, nSize);
 685         memmove (lpDest, lpSrc, nSize);
 686     }
 687
 688     hdpa->nItemCount --;
 689
 690     /* free memory ?*/
 691     if ((hdpa->nMaxCount - hdpa->nItemCount) >= hdpa->nGrow) {
 692         INT nNewItems = max(hdpa->nGrow * 2, hdpa->nItemCount);
 693         nSize = nNewItems * sizeof(LPVOID);
 694         lpDest = HeapReAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
 695                                       hdpa->ptrs, nSize);
 696         if (!lpDest)
 697             return NULL;
 698
 699         hdpa->nMaxCount = nNewItems;
 700         hdpa->ptrs = lpDest;
 701     }
 702
 703     return lpTemp;
 704 }
 705
 706
 707 /**************************************************************************
 708  * DPA_DeleteAllPtrs [COMCTL32.337]
 709  *
 710  * Removes all pointers and reinitializes the array.
 711  *
 712  * PARAMS
 713  *     hdpa [I] handle (pointer) to the pointer array
 714  *
 715  * RETURNS
 716  *     Success: TRUE
 717  *     Failure: FALSE
 718  */
 719 BOOL WINAPI DPA_DeleteAllPtrs (const HDPA hdpa)
 720 {
 721     TRACE("(%p)\n", hdpa);
 722
 723     if (!hdpa)
 724         return FALSE;
 725
 726     if (hdpa->ptrs && (!HeapFree (hdpa->hHeap, 0, hdpa->ptrs)))
 727         return FALSE;
 728
 729     hdpa->nItemCount = 0;
 730     hdpa->nMaxCount = hdpa->nGrow * 2;
 731     hdpa->ptrs = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
 732                                      hdpa->nMaxCount * sizeof(LPVOID));
 733
 734     return TRUE;
 735 }
 736
 737
 738 /**************************************************************************
 739  * DPA_QuickSort [Internal]
 740  *
 741  * Ordinary quicksort (used by DPA_Sort).
 742  *
 743  * PARAMS
 744  *     lpPtrs     [I] pointer to the pointer array
 745  *     l          [I] index of the "left border" of the partition
 746  *     r          [I] index of the "right border" of the partition
 747  *     pfnCompare [I] pointer to the compare function
 748  *     lParam     [I] user defined value (3rd parameter in compare function)
 749  *
 750  * RETURNS
 751  *     NONE
 752  */
 753 static VOID DPA_QuickSort (LPVOID *lpPtrs, INT l, INT r,
 754                            PFNDPACOMPARE pfnCompare, LPARAM lParam)
 755 {
 756     INT m;
 757     LPVOID t;
 758
 759     TRACE("l=%i r=%i\n", l, r);
 760
 761     if (l==r)    /* one element is always sorted */
 762         return;
 763     if (r<l)     /* oops, got it in the wrong order */
 764         {
 765         DPA_QuickSort(lpPtrs, r, l, pfnCompare, lParam);
 766         return;
 767         }
 768     m = (l+r)/2; /* divide by two */
 769     DPA_QuickSort(lpPtrs, l, m, pfnCompare, lParam);
 770     DPA_QuickSort(lpPtrs, m+1, r, pfnCompare, lParam);
 771
 772     /* join the two sides */
 773     while( (l<=m) && (m<r) )
 774     {
 775         if(pfnCompare(lpPtrs[l],lpPtrs[m+1],lParam)>0)
 776         {
 777             t = lpPtrs[m+1];
 778             memmove(&lpPtrs[l+1],&lpPtrs[l],(m-l+1)*sizeof(lpPtrs[l]));
 779             lpPtrs[l] = t;
 780
 781             m++;
 782         }
 783         l++;
 784     }
 785 }
 786
 787
 788 /**************************************************************************
 789  * DPA_Sort [COMCTL32.338]
 790  *
 791  * Sorts a pointer array using a user defined compare function
 792  *
 793  * PARAMS
 794  *     hdpa       [I] handle (pointer) to the pointer array
 795  *     pfnCompare [I] pointer to the compare function
 796  *     lParam     [I] user defined value (3rd parameter of compare function)
 797  *
 798  * RETURNS
 799  *     Success: TRUE
 800  *     Failure: FALSE
 801  */
 802 BOOL WINAPI DPA_Sort (const HDPA hdpa, PFNDPACOMPARE pfnCompare, LPARAM lParam)
 803 {
 804     if (!hdpa || !pfnCompare)
 805         return FALSE;
 806
 807     TRACE("(%p %p 0x%lx)\n", hdpa, pfnCompare, lParam);
 808
 809     if ((hdpa->nItemCount > 1) && (hdpa->ptrs))
 810         DPA_QuickSort (hdpa->ptrs, 0, hdpa->nItemCount - 1,
 811                        pfnCompare, lParam);
 812
 813     return TRUE;
 814 }
 815
 816
 817 /**************************************************************************
 818  * DPA_Search [COMCTL32.339]
 819  *
 820  * Searches a pointer array for a specified pointer
 821  *
 822  * PARAMS
 823  *     hdpa       [I] handle (pointer) to the pointer array
 824  *     pFind      [I] pointer to search for
 825  *     nStart     [I] start index
 826  *     pfnCompare [I] pointer to the compare function
 827  *     lParam     [I] user defined value (3rd parameter of compare function)
 828  *     uOptions   [I] search options
 829  *
 830  * RETURNS
 831  *     Success: index of the pointer in the array.
 832  *     Failure: -1
 833  */
 834 INT WINAPI DPA_Search (const HDPA hdpa, LPVOID pFind, INT nStart,
 835                        PFNDPACOMPARE pfnCompare, LPARAM lParam, UINT uOptions)
 836 {
 837     if (!hdpa || !pfnCompare || !pFind)
 838         return -1;
 839
 840     TRACE("(%p %p %d %p 0x%08lx 0x%08x)\n",
 841            hdpa, pFind, nStart, pfnCompare, lParam, uOptions);
 842
 843     if (uOptions & DPAS_SORTED) {
 844         /* array is sorted --> use binary search */
 845         INT l, r, x, n;
 846         LPVOID *lpPtr;
 847
 848         /* for binary search ignore start index */
 849         l = 0;
 850         r = hdpa->nItemCount - 1;
 851         lpPtr = hdpa->ptrs;
 852         while (r >= l) {
 853             x = (l + r) / 2;
 854             n = (pfnCompare)(pFind, lpPtr[x], lParam);
 855             if (n == 0)
 856                 return x;
 857             else if (n < 0)
 858                 r = x - 1;
 859             else /* (n > 0) */
 860                 l = x + 1;
 861         }
 862         if (uOptions & (DPAS_INSERTBEFORE|DPAS_INSERTAFTER)) return l;
 863     }
 864     else {
 865         /* array is not sorted --> use linear search */
 866         LPVOID *lpPtr;
 867         INT  nIndex;
 868
 869         nIndex = (nStart == -1)? 0 : nStart;
 870         lpPtr = hdpa->ptrs;
 871         for (; nIndex < hdpa->nItemCount; nIndex++) {
 872             if ((pfnCompare)(pFind, lpPtr[nIndex], lParam) == 0)
 873                 return nIndex;
 874         }
 875     }
 876
 877     return -1;
 878 }
 879
 880
 881 /**************************************************************************
 882  * DPA_CreateEx [COMCTL32.340]
 883  *
 884  * Creates a dynamic pointer array using the specified size and heap.
 885  *
 886  * PARAMS
 887  *     nGrow [I] number of items by which the array grows when it is filled
 888  *     hHeap [I] handle to the heap where the array is stored
 889  *
 890  * RETURNS
 891  *     Success: handle (pointer) to the pointer array.
 892  *     Failure: NULL
 893  *
 894  * NOTES
 895  *     The DPA_ functions can be used to create and manipulate arrays of
 896  *     pointers.
 897  */
 898 HDPA WINAPI DPA_CreateEx (INT nGrow, HANDLE hHeap)
 899 {
 900     HDPA hdpa;
 901
 902     TRACE("(%d %p)\n", nGrow, hHeap);
 903
 904     if (hHeap)
 905         hdpa = HeapAlloc (hHeap, HEAP_ZERO_MEMORY, sizeof(*hdpa));
 906     else
 907         hdpa = Alloc (sizeof(*hdpa));
 908
 909     if (hdpa) {
 910         hdpa->nGrow = max(8, nGrow);
 911         hdpa->hHeap = hHeap ? hHeap : GetProcessHeap();
 912         hdpa->nMaxCount = hdpa->nGrow * 2;
 913         hdpa->ptrs = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
 914                                 hdpa->nMaxCount * sizeof(LPVOID));
 915     }
 916
 917     TRACE("-- %p\n", hdpa);
 918
 919     return hdpa;
 920 }
 921
 922
 923 /**************************************************************************
 924  * DPA_Create [COMCTL32.328]
 925  *
 926  * Creates a dynamic pointer array.
 927  *
 928  * PARAMS
 929  *     nGrow [I] number of items by which the array grows when it is filled
 930  *
 931  * RETURNS
 932  *     Success: handle (pointer) to the pointer array.
 933  *     Failure: NULL
 934  *
 935  * NOTES
 936  *     The DPA_ functions can be used to create and manipulate arrays of
 937  *     pointers.
 938  */
 939 HDPA WINAPI DPA_Create (INT nGrow)
 940 {
 941     return DPA_CreateEx( nGrow, 0 );
 942 }
 943
 944
 945 /**************************************************************************
 946  * DPA_EnumCallback [COMCTL32.385]
 947  *
 948  * Enumerates all items in a dynamic pointer array.
 949  *
 950  * PARAMS
 951  *     hdpa     [I] handle to the dynamic pointer array
 952  *     enumProc [I]
 953  *     lParam   [I]
 954  *
 955  * RETURNS
 956  *     none
 957  */
 958 VOID WINAPI DPA_EnumCallback (HDPA hdpa, PFNDPAENUMCALLBACK enumProc,
 959                               LPVOID lParam)
 960 {
 961     INT i;
 962
 963     TRACE("(%p %p %p)\n", hdpa, enumProc, lParam);
 964
 965     if (!hdpa)
 966         return;
 967     if (hdpa->nItemCount <= 0)
 968         return;
 969
 970     for (i = 0; i < hdpa->nItemCount; i++) {
 971         if ((enumProc)(hdpa->ptrs[i], lParam) == 0)
 972             return;
 973     }
 974
 975     return;
 976 }
 977
 978
 979 /**************************************************************************
 980  * DPA_DestroyCallback [COMCTL32.386]
 981  *
 982  * Enumerates all items in a dynamic pointer array and destroys it.
 983  *
 984  * PARAMS
 985  *     hdpa     [I] handle to the dynamic pointer array
 986  *     enumProc [I]
 987  *     lParam   [I]
 988  *
 989  * RETURNS
 990  *     none
 991  */
 992 void WINAPI DPA_DestroyCallback (HDPA hdpa, PFNDPAENUMCALLBACK enumProc,
 993                                  LPVOID lParam)
 994 {
 995     TRACE("(%p %p %p)\n", hdpa, enumProc, lParam);
 996
 997     DPA_EnumCallback (hdpa, enumProc, lParam);
 998     DPA_Destroy (hdpa);
 999 }
1000
1001 /**************************************************************************
1002  * DPA_GetSize [COMCTL32.@]
1003  *
1004  * Returns all array allocated memory size
1005  *
1006  * PARAMS
1007  *     hdpa     [I] handle to the dynamic pointer array
1008  *
1009  * RETURNS
1010  *     Size in bytes
1011  */
1012 ULONGLONG WINAPI DPA_GetSize(HDPA hdpa)
1013 {
1014     TRACE("(%p)\n", hdpa);
1015
1016     if (!hdpa) return 0;
1017
1018     return sizeof(DPA) + hdpa->nMaxCount*sizeof(PVOID);
1019 }