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