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     /* working but untrusted implementation */
 307
 308     pWork1 = &(hdpa1->ptrs[hdpa1->nItemCount - 1]);
 309     pWork2 = &(hdpa2->ptrs[hdpa2->nItemCount - 1]);
 310
 311     nIndex = hdpa1->nItemCount - 1;
 312     nCount = hdpa2->nItemCount - 1;
 313
 314     do
 315     {
 316         if (nIndex < 0) {
 317             if ((nCount >= 0) && (dwFlags & DPAM_UNION)) {
 318                 /* Now insert the remaining new items into DPA 1 */
 319                 TRACE("%d items to be inserted at start of DPA 1\n",
 320                       nCount+1);
 321                 for (i=nCount; i>=0; i--) {
 322                     PVOID ptr;
 323
 324                     ptr = (pfnMerge)(DPAMM_INSERT, *pWork2, NULL, lParam);
 325                     if (!ptr)
 326                         return FALSE;
 327                     DPA_InsertPtr (hdpa1, 0, ptr);
 328                     pWork2--;
 329                 }
 330             }
 331             break;
 332         }
 333         nResult = (pfnCompare)(*pWork1, *pWork2, lParam);
 334         TRACE("compare result=%d, dpa1.cnt=%d, dpa2.cnt=%d\n",
 335               nResult, nIndex, nCount);
 336
 337         if (nResult == 0)
 338         {
 339             PVOID ptr;
 340
 341             ptr = (pfnMerge)(DPAMM_MERGE, *pWork1, *pWork2, lParam);
 342             if (!ptr)
 343                 return FALSE;
 344
 345             nCount--;
 346             pWork2--;
 347             *pWork1 = ptr;
 348             nIndex--;
 349             pWork1--;
 350         }
 351         else if (nResult > 0)
 352         {
 353             /* item in DPA 1 missing from DPA 2 */
 354             if (dwFlags & DPAM_INTERSECT)
 355             {
 356                 /* Now delete the extra item in DPA1 */
 357                 PVOID ptr;
 358
 359                 ptr = DPA_DeletePtr (hdpa1, nIndex);
 360
 361                 (pfnMerge)(DPAMM_DELETE, ptr, NULL, lParam);
 362             }
 363             nIndex--;
 364             pWork1--;
 365         }
 366         else
 367         {
 368             /* new item in DPA 2 */
 369             if (dwFlags & DPAM_UNION)
 370             {
 371                 /* Now insert the new item in DPA 1 */
 372                 PVOID ptr;
 373
 374                 ptr = (pfnMerge)(DPAMM_INSERT, *pWork2, NULL, lParam);
 375                 if (!ptr)
 376                     return FALSE;
 377                 DPA_InsertPtr (hdpa1, nIndex+1, ptr);
 378             }
 379             nCount--;
 380             pWork2--;
 381         }
 382
 383     }
 384     while (nCount >= 0);
 385
 386     return TRUE;
 387 }
 388
 389
 390 /**************************************************************************
 391  * DPA_Destroy [COMCTL32.329]
 392  *
 393  * Destroys a dynamic pointer array
 394  *
 395  * PARAMS
 396  *     hdpa [I] handle (pointer) to the pointer array
 397  *
 398  * RETURNS
 399  *     Success: TRUE
 400  *     Failure: FALSE
 401  */
 402 BOOL WINAPI DPA_Destroy (HDPA hdpa)
 403 {
 404     TRACE("(%p)\n", hdpa);
 405
 406     if (!hdpa)
 407         return FALSE;
 408
 409     if (hdpa->ptrs && (!HeapFree (hdpa->hHeap, 0, hdpa->ptrs)))
 410         return FALSE;
 411
 412     return HeapFree (hdpa->hHeap, 0, hdpa);
 413 }
 414
 415
 416 /**************************************************************************
 417  * DPA_Grow [COMCTL32.330]
 418  *
 419  * Sets the growth amount.
 420  *
 421  * PARAMS
 422  *     hdpa  [I] handle (pointer) to the existing (source) pointer array
 423  *     nGrow [I] number of items by which the array grows when it's too small
 424  *
 425  * RETURNS
 426  *     Success: TRUE
 427  *     Failure: FALSE
 428  */
 429 BOOL WINAPI DPA_Grow (HDPA hdpa, INT nGrow)
 430 {
 431     INT items;
 432     TRACE("(%p %d)\n", hdpa, nGrow);
 433
 434     if (!hdpa)
 435         return FALSE;
 436
 437     nGrow = max( 8, nGrow );
 438     items = nGrow * (((hdpa->nMaxCount - 1) / nGrow) + 1);
 439     if (items > hdpa->nMaxCount)
 440     {
 441         void *ptr;
 442
 443         if (hdpa->ptrs)
 444             ptr = HeapReAlloc( hdpa->hHeap, HEAP_ZERO_MEMORY, hdpa->ptrs, items * sizeof(LPVOID) );
 445         else
 446             ptr = HeapAlloc( hdpa->hHeap, HEAP_ZERO_MEMORY, items * sizeof(LPVOID) );
 447         if (!ptr) return FALSE;
 448         hdpa->nMaxCount = items;
 449         hdpa->ptrs = ptr;
 450     }
 451     hdpa->nGrow = nGrow;
 452
 453     return TRUE;
 454 }
 455
 456
 457 /**************************************************************************
 458  * DPA_Clone [COMCTL32.331]
 459  *
 460  * Copies a pointer array to another one or creates a copy
 461  *
 462  * PARAMS
 463  *     hdpa    [I] handle (pointer) to the existing (source) pointer array
 464  *     hdpaNew [O] handle (pointer) to the destination pointer array
 465  *
 466  * RETURNS
 467  *     Success: pointer to the destination pointer array.
 468  *     Failure: NULL
 469  *
 470  * NOTES
 471  *     - If the 'hdpaNew' is a NULL-Pointer, a copy of the source pointer
 472  *       array will be created and its handle (pointer) is returned.
 473  *     - If 'hdpa' is a NULL-Pointer, the original implementation crashes,
 474  *       this implementation just returns NULL.
 475  */
 476 HDPA WINAPI DPA_Clone (const HDPA hdpa, HDPA hdpaNew)
 477 {
 478     INT nNewItems, nSize;
 479     HDPA hdpaTemp;
 480
 481     if (!hdpa)
 482         return NULL;
 483
 484     TRACE("(%p %p)\n", hdpa, hdpaNew);
 485
 486     if (!hdpaNew) {
 487         /* create a new DPA */
 488         hdpaTemp = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
 489                                     sizeof(*hdpaTemp));
 490         hdpaTemp->hHeap = hdpa->hHeap;
 491         hdpaTemp->nGrow = hdpa->nGrow;
 492     }
 493     else
 494         hdpaTemp = hdpaNew;
 495
 496     if (hdpaTemp->ptrs) {
 497         /* remove old pointer array */
 498         HeapFree (hdpaTemp->hHeap, 0, hdpaTemp->ptrs);
 499         hdpaTemp->ptrs = NULL;
 500         hdpaTemp->nItemCount = 0;
 501         hdpaTemp->nMaxCount = 0;
 502     }
 503
 504     /* create a new pointer array */
 505     nNewItems = hdpaTemp->nGrow *
 506                 (((hdpa->nItemCount - 1) / hdpaTemp->nGrow) + 1);
 507     nSize = nNewItems * sizeof(LPVOID);
 508     hdpaTemp->ptrs = HeapAlloc (hdpaTemp->hHeap, HEAP_ZERO_MEMORY, nSize);
 509     hdpaTemp->nMaxCount = nNewItems;
 510
 511     /* clone the pointer array */
 512     hdpaTemp->nItemCount = hdpa->nItemCount;
 513     memmove (hdpaTemp->ptrs, hdpa->ptrs,
 514              hdpaTemp->nItemCount * sizeof(LPVOID));
 515
 516     return hdpaTemp;
 517 }
 518
 519
 520 /**************************************************************************
 521  * DPA_GetPtr [COMCTL32.332]
 522  *
 523  * Retrieves a pointer from a dynamic pointer array
 524  *
 525  * PARAMS
 526  *     hdpa   [I] handle (pointer) to the pointer array
 527  *     nIndex [I] array index of the desired pointer
 528  *
 529  * RETURNS
 530  *     Success: pointer
 531  *     Failure: NULL
 532  */
 533 LPVOID WINAPI DPA_GetPtr (HDPA hdpa, INT nIndex)
 534 {
 535     TRACE("(%p %d)\n", hdpa, nIndex);
 536
 537     if (!hdpa)
 538         return NULL;
 539     if (!hdpa->ptrs) {
 540         WARN("no pointer array.\n");
 541         return NULL;
 542     }
 543     if ((nIndex < 0) || (nIndex >= hdpa->nItemCount)) {
 544         WARN("not enough pointers in array (%d vs %d).\n",nIndex,hdpa->nItemCount);
 545         return NULL;
 546     }
 547
 548     TRACE("-- %p\n", hdpa->ptrs[nIndex]);
 549
 550     return hdpa->ptrs[nIndex];
 551 }
 552
 553
 554 /**************************************************************************
 555  * DPA_GetPtrIndex [COMCTL32.333]
 556  *
 557  * Retrieves the index of the specified pointer
 558  *
 559  * PARAMS
 560  *     hdpa   [I] handle (pointer) to the pointer array
 561  *     p      [I] pointer
 562  *
 563  * RETURNS
 564  *     Success: index of the specified pointer
 565  *     Failure: -1
 566  */
 567 INT WINAPI DPA_GetPtrIndex (HDPA hdpa, LPCVOID p)
 568 {
 569     INT i;
 570
 571     if (!hdpa || !hdpa->ptrs)
 572         return -1;
 573
 574     for (i = 0; i < hdpa->nItemCount; i++) {
 575         if (hdpa->ptrs[i] == p)
 576             return i;
 577     }
 578
 579     return -1;
 580 }
 581
 582
 583 /**************************************************************************
 584  * DPA_InsertPtr [COMCTL32.334]
 585  *
 586  * Inserts a pointer into a dynamic pointer array
 587  *
 588  * PARAMS
 589  *     hdpa [I] handle (pointer) to the array
 590  *     i    [I] array index
 591  *     p    [I] pointer to insert
 592  *
 593  * RETURNS
 594  *     Success: index of the inserted pointer
 595  *     Failure: -1
 596  */
 597 INT WINAPI DPA_InsertPtr (HDPA hdpa, INT i, LPVOID p)
 598 {
 599     TRACE("(%p %d %p)\n", hdpa, i, p);
 600
 601     if (!hdpa || i < 0) return -1;
 602
 603     /* append item if index is out of bounds */
 604     i = min(hdpa->nItemCount, i);
 605
 606     /* create empty spot at the end */
 607     if (!DPA_SetPtr(hdpa, hdpa->nItemCount, 0)) return -1;
 608
 609     if (i != hdpa->nItemCount - 1)
 610         memmove (hdpa->ptrs + i + 1, hdpa->ptrs + i,
 611                  (hdpa->nItemCount - i - 1) * sizeof(LPVOID));
 612
 613     hdpa->ptrs[i] = p;
 614     return i;
 615 }
 616
 617
 618 /**************************************************************************
 619  * DPA_SetPtr [COMCTL32.335]
 620  *
 621  * Sets a pointer in the pointer array
 622  *
 623  * PARAMS
 624  *     hdpa [I] handle (pointer) to the pointer array
 625  *     i    [I] index of the pointer that will be set
 626  *     p    [I] pointer to be set
 627  *
 628  * RETURNS
 629  *     Success: TRUE
 630  *     Failure: FALSE
 631  */
 632 BOOL WINAPI DPA_SetPtr (HDPA hdpa, INT i, LPVOID p)
 633 {
 634     LPVOID *lpTemp;
 635
 636     TRACE("(%p %d %p)\n", hdpa, i, p);
 637
 638     if (!hdpa || i < 0)
 639         return FALSE;
 640
 641     if (hdpa->nItemCount <= i) {
 642         /* within the old array */
 643         if (hdpa->nMaxCount <= i) {
 644             /* resize the block of memory */
 645             INT nNewItems =
 646                 hdpa->nGrow * ((((i+1) - 1) / hdpa->nGrow) + 1);
 647             INT nSize = nNewItems * sizeof(LPVOID);
 648
 649             if (hdpa->ptrs)
 650                 lpTemp = HeapReAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY, hdpa->ptrs, nSize);
 651             else
 652                 lpTemp = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY, nSize);
 653
 654             if (!lpTemp)
 655                 return FALSE;
 656
 657             hdpa->nMaxCount = nNewItems;
 658             hdpa->ptrs = lpTemp;
 659         }
 660         hdpa->nItemCount = i+1;
 661     }
 662
 663     /* put the new entry in */
 664     hdpa->ptrs[i] = p;
 665
 666     return TRUE;
 667 }
 668
 669
 670 /**************************************************************************
 671  * DPA_DeletePtr [COMCTL32.336]
 672  *
 673  * Removes a pointer from the pointer array.
 674  *
 675  * PARAMS
 676  *     hdpa [I] handle (pointer) to the pointer array
 677  *     i    [I] index of the pointer that will be deleted
 678  *
 679  * RETURNS
 680  *     Success: deleted pointer
 681  *     Failure: NULL
 682  */
 683 LPVOID WINAPI DPA_DeletePtr (HDPA hdpa, INT i)
 684 {
 685     LPVOID *lpDest, *lpSrc, lpTemp = NULL;
 686     INT  nSize;
 687
 688     TRACE("(%p %d)\n", hdpa, i);
 689
 690     if ((!hdpa) || i < 0 || i >= hdpa->nItemCount)
 691         return NULL;
 692
 693     lpTemp = hdpa->ptrs[i];
 694
 695     /* do we need to move ?*/
 696     if (i < hdpa->nItemCount - 1) {
 697         lpDest = hdpa->ptrs + i;
 698         lpSrc = lpDest + 1;
 699         nSize = (hdpa->nItemCount - i - 1) * sizeof(LPVOID);
 700         TRACE("-- move dest=%p src=%p size=%x\n",
 701                lpDest, lpSrc, nSize);
 702         memmove (lpDest, lpSrc, nSize);
 703     }
 704
 705     hdpa->nItemCount --;
 706
 707     /* free memory ?*/
 708     if ((hdpa->nMaxCount - hdpa->nItemCount) >= hdpa->nGrow) {
 709         INT nNewItems = max(hdpa->nGrow * 2, hdpa->nItemCount);
 710         nSize = nNewItems * sizeof(LPVOID);
 711         lpDest = HeapReAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
 712                                       hdpa->ptrs, nSize);
 713         if (!lpDest)
 714             return NULL;
 715
 716         hdpa->nMaxCount = nNewItems;
 717         hdpa->ptrs = lpDest;
 718     }
 719
 720     return lpTemp;
 721 }
 722
 723
 724 /**************************************************************************
 725  * DPA_DeleteAllPtrs [COMCTL32.337]
 726  *
 727  * Removes all pointers and reinitializes the array.
 728  *
 729  * PARAMS
 730  *     hdpa [I] handle (pointer) to the pointer array
 731  *
 732  * RETURNS
 733  *     Success: TRUE
 734  *     Failure: FALSE
 735  */
 736 BOOL WINAPI DPA_DeleteAllPtrs (HDPA hdpa)
 737 {
 738     TRACE("(%p)\n", hdpa);
 739
 740     if (!hdpa)
 741         return FALSE;
 742
 743     if (hdpa->ptrs && (!HeapFree (hdpa->hHeap, 0, hdpa->ptrs)))
 744         return FALSE;
 745
 746     hdpa->nItemCount = 0;
 747     hdpa->nMaxCount = hdpa->nGrow * 2;
 748     hdpa->ptrs = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
 749                                      hdpa->nMaxCount * sizeof(LPVOID));
 750
 751     return TRUE;
 752 }
 753
 754
 755 /**************************************************************************
 756  * DPA_QuickSort [Internal]
 757  *
 758  * Ordinary quicksort (used by DPA_Sort).
 759  *
 760  * PARAMS
 761  *     lpPtrs     [I] pointer to the pointer array
 762  *     l          [I] index of the "left border" of the partition
 763  *     r          [I] index of the "right border" of the partition
 764  *     pfnCompare [I] pointer to the compare function
 765  *     lParam     [I] user defined value (3rd parameter in compare function)
 766  *
 767  * RETURNS
 768  *     NONE
 769  */
 770 static VOID DPA_QuickSort (LPVOID *lpPtrs, INT l, INT r,
 771                            PFNDPACOMPARE pfnCompare, LPARAM lParam)
 772 {
 773     INT m;
 774     LPVOID t;
 775
 776     TRACE("l=%i r=%i\n", l, r);
 777
 778     if (l==r)    /* one element is always sorted */
 779         return;
 780     if (r<l)     /* oops, got it in the wrong order */
 781         {
 782         DPA_QuickSort(lpPtrs, r, l, pfnCompare, lParam);
 783         return;
 784         }
 785     m = (l+r)/2; /* divide by two */
 786     DPA_QuickSort(lpPtrs, l, m, pfnCompare, lParam);
 787     DPA_QuickSort(lpPtrs, m+1, r, pfnCompare, lParam);
 788
 789     /* join the two sides */
 790     while( (l<=m) && (m<r) )
 791     {
 792         if(pfnCompare(lpPtrs[l],lpPtrs[m+1],lParam)>0)
 793         {
 794             t = lpPtrs[m+1];
 795             memmove(&lpPtrs[l+1],&lpPtrs[l],(m-l+1)*sizeof(lpPtrs[l]));
 796             lpPtrs[l] = t;
 797
 798             m++;
 799         }
 800         l++;
 801     }
 802 }
 803
 804
 805 /**************************************************************************
 806  * DPA_Sort [COMCTL32.338]
 807  *
 808  * Sorts a pointer array using a user defined compare function
 809  *
 810  * PARAMS
 811  *     hdpa       [I] handle (pointer) to the pointer array
 812  *     pfnCompare [I] pointer to the compare function
 813  *     lParam     [I] user defined value (3rd parameter of compare function)
 814  *
 815  * RETURNS
 816  *     Success: TRUE
 817  *     Failure: FALSE
 818  */
 819 BOOL WINAPI DPA_Sort (HDPA hdpa, PFNDPACOMPARE pfnCompare, LPARAM lParam)
 820 {
 821     if (!hdpa || !pfnCompare)
 822         return FALSE;
 823
 824     TRACE("(%p %p 0x%lx)\n", hdpa, pfnCompare, lParam);
 825
 826     if ((hdpa->nItemCount > 1) && (hdpa->ptrs))
 827         DPA_QuickSort (hdpa->ptrs, 0, hdpa->nItemCount - 1,
 828                        pfnCompare, lParam);
 829
 830     return TRUE;
 831 }
 832
 833
 834 /**************************************************************************
 835  * DPA_Search [COMCTL32.339]
 836  *
 837  * Searches a pointer array for a specified pointer
 838  *
 839  * PARAMS
 840  *     hdpa       [I] handle (pointer) to the pointer array
 841  *     pFind      [I] pointer to search for
 842  *     nStart     [I] start index
 843  *     pfnCompare [I] pointer to the compare function
 844  *     lParam     [I] user defined value (3rd parameter of compare function)
 845  *     uOptions   [I] search options
 846  *
 847  * RETURNS
 848  *     Success: index of the pointer in the array.
 849  *     Failure: -1
 850  */
 851 INT WINAPI DPA_Search (HDPA hdpa, LPVOID pFind, INT nStart,
 852                        PFNDPACOMPARE pfnCompare, LPARAM lParam, UINT uOptions)
 853 {
 854     if (!hdpa || !pfnCompare || !pFind)
 855         return -1;
 856
 857     TRACE("(%p %p %d %p 0x%08lx 0x%08x)\n",
 858            hdpa, pFind, nStart, pfnCompare, lParam, uOptions);
 859
 860     if (uOptions & DPAS_SORTED) {
 861         /* array is sorted --> use binary search */
 862         INT l, r, x, n;
 863         LPVOID *lpPtr;
 864
 865         /* for binary search ignore start index */
 866         l = 0;
 867         r = hdpa->nItemCount - 1;
 868         lpPtr = hdpa->ptrs;
 869         while (r >= l) {
 870             x = (l + r) / 2;
 871             n = (pfnCompare)(pFind, lpPtr[x], lParam);
 872             if (n == 0)
 873                 return x;
 874             else if (n < 0)
 875                 r = x - 1;
 876             else /* (n > 0) */
 877                 l = x + 1;
 878         }
 879         if (uOptions & (DPAS_INSERTBEFORE|DPAS_INSERTAFTER)) return l;
 880     }
 881     else {
 882         /* array is not sorted --> use linear search */
 883         LPVOID *lpPtr;
 884         INT  nIndex;
 885
 886         nIndex = (nStart == -1)? 0 : nStart;
 887         lpPtr = hdpa->ptrs;
 888         for (; nIndex < hdpa->nItemCount; nIndex++) {
 889             if ((pfnCompare)(pFind, lpPtr[nIndex], lParam) == 0)
 890                 return nIndex;
 891         }
 892     }
 893
 894     return -1;
 895 }
 896
 897
 898 /**************************************************************************
 899  * DPA_CreateEx [COMCTL32.340]
 900  *
 901  * Creates a dynamic pointer array using the specified size and heap.
 902  *
 903  * PARAMS
 904  *     nGrow [I] number of items by which the array grows when it is filled
 905  *     hHeap [I] handle to the heap where the array is stored
 906  *
 907  * RETURNS
 908  *     Success: handle (pointer) to the pointer array.
 909  *     Failure: NULL
 910  *
 911  * NOTES
 912  *     The DPA_ functions can be used to create and manipulate arrays of
 913  *     pointers.
 914  */
 915 HDPA WINAPI DPA_CreateEx (INT nGrow, HANDLE hHeap)
 916 {
 917     HDPA hdpa;
 918
 919     TRACE("(%d %p)\n", nGrow, hHeap);
 920
 921     if (hHeap)
 922         hdpa = HeapAlloc (hHeap, HEAP_ZERO_MEMORY, sizeof(*hdpa));
 923     else
 924         hdpa = Alloc (sizeof(*hdpa));
 925
 926     if (hdpa) {
 927         hdpa->nGrow = max(8, nGrow);
 928         hdpa->hHeap = hHeap ? hHeap : GetProcessHeap();
 929         hdpa->nMaxCount = hdpa->nGrow * 2;
 930         hdpa->ptrs = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
 931                                 hdpa->nMaxCount * sizeof(LPVOID));
 932     }
 933
 934     TRACE("-- %p\n", hdpa);
 935
 936     return hdpa;
 937 }
 938
 939
 940 /**************************************************************************
 941  * DPA_Create [COMCTL32.328]
 942  *
 943  * Creates a dynamic pointer array.
 944  *
 945  * PARAMS
 946  *     nGrow [I] number of items by which the array grows when it is filled
 947  *
 948  * RETURNS
 949  *     Success: handle (pointer) to the pointer array.
 950  *     Failure: NULL
 951  *
 952  * NOTES
 953  *     The DPA_ functions can be used to create and manipulate arrays of
 954  *     pointers.
 955  */
 956 HDPA WINAPI DPA_Create (INT nGrow)
 957 {
 958     return DPA_CreateEx( nGrow, 0 );
 959 }
 960
 961
 962 /**************************************************************************
 963  * DPA_EnumCallback [COMCTL32.385]
 964  *
 965  * Enumerates all items in a dynamic pointer array.
 966  *
 967  * PARAMS
 968  *     hdpa     [I] handle to the dynamic pointer array
 969  *     enumProc [I]
 970  *     lParam   [I]
 971  *
 972  * RETURNS
 973  *     none
 974  */
 975 VOID WINAPI DPA_EnumCallback (HDPA hdpa, PFNDPAENUMCALLBACK enumProc,
 976                               LPVOID lParam)
 977 {
 978     INT i;
 979
 980     TRACE("(%p %p %p)\n", hdpa, enumProc, lParam);
 981
 982     if (!hdpa)
 983         return;
 984     if (hdpa->nItemCount <= 0)
 985         return;
 986
 987     for (i = 0; i < hdpa->nItemCount; i++) {
 988         if ((enumProc)(hdpa->ptrs[i], lParam) == 0)
 989             return;
 990     }
 991
 992     return;
 993 }
 994
 995
 996 /**************************************************************************
 997  * DPA_DestroyCallback [COMCTL32.386]
 998  *
 999  * Enumerates all items in a dynamic pointer array and destroys it.
1000  *
1001  * PARAMS
1002  *     hdpa     [I] handle to the dynamic pointer array
1003  *     enumProc [I]
1004  *     lParam   [I]
1005  *
1006  * RETURNS
1007  *     none
1008  */
1009 void WINAPI DPA_DestroyCallback (HDPA hdpa, PFNDPAENUMCALLBACK enumProc,
1010                                  LPVOID lParam)
1011 {
1012     TRACE("(%p %p %p)\n", hdpa, enumProc, lParam);
1013
1014     DPA_EnumCallback (hdpa, enumProc, lParam);
1015     DPA_Destroy (hdpa);
1016 }
1017
1018 /**************************************************************************
1019  * DPA_GetSize [COMCTL32.@]
1020  *
1021  * Returns all array allocated memory size
1022  *
1023  * PARAMS
1024  *     hdpa     [I] handle to the dynamic pointer array
1025  *
1026  * RETURNS
1027  *     Size in bytes
1028  */
1029 ULONGLONG WINAPI DPA_GetSize(HDPA hdpa)
1030 {
1031     TRACE("(%p)\n", hdpa);
1032
1033     if (!hdpa) return 0;
1034
1035     return sizeof(DPA) + hdpa->nMaxCount*sizeof(PVOID);
1036 }