comctl32/monthcal: Fix assumption about a single calendar for minimal rectangle calcu...
[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., 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 }