dlls/comctl32/dpa.c

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