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