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