Fix DPA_Search for sorted arrays.
[wine] / 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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 = (HDPA)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=%lu dwData2=%lu dwItems=%lu\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=%lx\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 %08lx %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                 ((INT)((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 * ((INT)(((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 = (LPVOID*)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
819         return l;
820     }
821     else {
822         /* array is not sorted --> use linear search */
823         LPVOID *lpPtr;
824         INT  nIndex;
825
826         nIndex = (nStart == -1)? 0 : nStart;
827         lpPtr = hdpa->ptrs;
828         for (; nIndex < hdpa->nItemCount; nIndex++) {
829             if ((pfnCompare)(pFind, lpPtr[nIndex], lParam) == 0)
830                 return nIndex;
831         }
832     }
833
834     return -1;
835 }
836
837
838 /**************************************************************************
839  * DPA_CreateEx [COMCTL32.340]
840  *
841  * Creates a dynamic pointer array using the specified size and heap.
842  *
843  * PARAMS
844  *     nGrow [I] number of items by which the array grows when it is filled
845  *     hHeap [I] handle to the heap where the array is stored
846  *
847  * RETURNS
848  *     Success: handle (pointer) to the pointer array.
849  *     Failure: NULL
850  *
851  * NOTES
852  *     The DPA_ functions can be used to create and manipulate arrays of
853  *     pointers.
854  */
855 HDPA WINAPI DPA_CreateEx (INT nGrow, HANDLE hHeap)
856 {
857     HDPA hdpa;
858
859     TRACE("(%d %p)\n", nGrow, hHeap);
860
861     if (hHeap)
862         hdpa = HeapAlloc (hHeap, HEAP_ZERO_MEMORY, sizeof(*hdpa));
863     else
864         hdpa = Alloc (sizeof(*hdpa));
865
866     if (hdpa) {
867         hdpa->nGrow = max(8, nGrow);
868         hdpa->hHeap = hHeap ? hHeap : GetProcessHeap();
869         hdpa->nMaxCount = hdpa->nGrow * 2;
870         hdpa->ptrs = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
871                                 hdpa->nMaxCount * sizeof(LPVOID));
872     }
873
874     TRACE("-- %p\n", hdpa);
875
876     return hdpa;
877 }
878
879
880 /**************************************************************************
881  * DPA_Create [COMCTL32.328]
882  *
883  * Creates a dynamic pointer array.
884  *
885  * PARAMS
886  *     nGrow [I] number of items by which the array grows when it is filled
887  *
888  * RETURNS
889  *     Success: handle (pointer) to the pointer array.
890  *     Failure: NULL
891  *
892  * NOTES
893  *     The DPA_ functions can be used to create and manipulate arrays of
894  *     pointers.
895  */
896 HDPA WINAPI DPA_Create (INT nGrow)
897 {
898     return DPA_CreateEx( nGrow, 0 );
899 }
900
901
902 /**************************************************************************
903  * DPA_EnumCallback [COMCTL32.385]
904  *
905  * Enumerates all items in a dynamic pointer array.
906  *
907  * PARAMS
908  *     hdpa     [I] handle to the dynamic pointer array
909  *     enumProc [I]
910  *     lParam   [I]
911  *
912  * RETURNS
913  *     none
914  */
915 VOID WINAPI DPA_EnumCallback (HDPA hdpa, PFNDPAENUMCALLBACK enumProc,
916                               LPVOID lParam)
917 {
918     INT i;
919
920     TRACE("(%p %p %p)\n", hdpa, enumProc, lParam);
921
922     if (!hdpa)
923         return;
924     if (hdpa->nItemCount <= 0)
925         return;
926
927     for (i = 0; i < hdpa->nItemCount; i++) {
928         if ((enumProc)(hdpa->ptrs[i], lParam) == 0)
929             return;
930     }
931
932     return;
933 }
934
935
936 /**************************************************************************
937  * DPA_DestroyCallback [COMCTL32.386]
938  *
939  * Enumerates all items in a dynamic pointer array and destroys it.
940  *
941  * PARAMS
942  *     hdpa     [I] handle to the dynamic pointer array
943  *     enumProc [I]
944  *     lParam   [I]
945  *
946  * RETURNS
947  *     none
948  */
949 void WINAPI DPA_DestroyCallback (HDPA hdpa, PFNDPAENUMCALLBACK enumProc,
950                                  LPVOID lParam)
951 {
952     TRACE("(%p %p %p)\n", hdpa, enumProc, lParam);
953
954     DPA_EnumCallback (hdpa, enumProc, lParam);
955     DPA_Destroy (hdpa);
956 }