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