reactos/dll/win32/comctl32/dpa.c

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