projects / reactos.git / blob
? search:


e3c03c88c8fc323609d3e89b6538486c17b58ffd
[reactos.git] / 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 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 TRACE("(%p %d)\n", hdpa, nGrow);
430
431 if (!hdpa)
432 return FALSE;
433
434 hdpa->nGrow = max(8, nGrow);
435
436 return TRUE;
437 }
438
439
440 /**************************************************************************
441 * DPA_Clone [COMCTL32.331]
442 *
443 * Copies a pointer array to an other one or creates a copy
444 *
445 * PARAMS
446 * hdpa [I] handle (pointer) to the existing (source) pointer array
447 * hdpaNew [O] handle (pointer) to the destination pointer array
448 *
449 * RETURNS
450 * Success: pointer to the destination pointer array.
451 * Failure: NULL
452 *
453 * NOTES
454 * - If the 'hdpaNew' is a NULL-Pointer, a copy of the source pointer
455 * array will be created and it's handle (pointer) is returned.
456 * - If 'hdpa' is a NULL-Pointer, the original implementation crashes,
457 * this implementation just returns NULL.
458 */
459 HDPA WINAPI DPA_Clone (const HDPA hdpa, const HDPA hdpaNew)
460 {
461 INT nNewItems, nSize;
462 HDPA hdpaTemp;
463
464 if (!hdpa)
465 return NULL;
466
467 TRACE("(%p %p)\n", hdpa, hdpaNew);
468
469 if (!hdpaNew) {
470 /* create a new DPA */
471 hdpaTemp = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
472 sizeof(*hdpaTemp));
473 hdpaTemp->hHeap = hdpa->hHeap;
474 hdpaTemp->nGrow = hdpa->nGrow;
475 }
476 else
477 hdpaTemp = hdpaNew;
478
479 if (hdpaTemp->ptrs) {
480 /* remove old pointer array */
481 HeapFree (hdpaTemp->hHeap, 0, hdpaTemp->ptrs);
482 hdpaTemp->ptrs = NULL;
483 hdpaTemp->nItemCount = 0;
484 hdpaTemp->nMaxCount = 0;
485 }
486
487 /* create a new pointer array */
488 nNewItems = hdpaTemp->nGrow *
489 (((hdpa->nItemCount - 1) / hdpaTemp->nGrow) + 1);
490 nSize = nNewItems * sizeof(LPVOID);
491 hdpaTemp->ptrs = HeapAlloc (hdpaTemp->hHeap, HEAP_ZERO_MEMORY, nSize);
492 hdpaTemp->nMaxCount = nNewItems;
493
494 /* clone the pointer array */
495 hdpaTemp->nItemCount = hdpa->nItemCount;
496 memmove (hdpaTemp->ptrs, hdpa->ptrs,
497 hdpaTemp->nItemCount * sizeof(LPVOID));
498
499 return hdpaTemp;
500 }
501
502
503 /**************************************************************************
504 * DPA_GetPtr [COMCTL32.332]
505 *
506 * Retrieves a pointer from a dynamic pointer array
507 *
508 * PARAMS
509 * hdpa [I] handle (pointer) to the pointer array
510 * nIndex [I] array index of the desired pointer
511 *
512 * RETURNS
513 * Success: pointer
514 * Failure: NULL
515 */
516 LPVOID WINAPI DPA_GetPtr (const HDPA hdpa, INT nIndex)
517 {
518 TRACE("(%p %d)\n", hdpa, nIndex);
519
520 if (!hdpa)
521 return NULL;
522 if (!hdpa->ptrs) {
523 WARN("no pointer array.\n");
524 return NULL;
525 }
526 if ((nIndex < 0) || (nIndex >= hdpa->nItemCount)) {
527 WARN("not enough pointers in array (%d vs %d).\n",nIndex,hdpa->nItemCount);
528 return NULL;
529 }
530
531 TRACE("-- %p\n", hdpa->ptrs[nIndex]);
532
533 return hdpa->ptrs[nIndex];
534 }
535
536
537 /**************************************************************************
538 * DPA_GetPtrIndex [COMCTL32.333]
539 *
540 * Retrieves the index of the specified pointer
541 *
542 * PARAMS
543 * hdpa [I] handle (pointer) to the pointer array
544 * p [I] pointer
545 *
546 * RETURNS
547 * Success: index of the specified pointer
548 * Failure: -1
549 */
550 INT WINAPI DPA_GetPtrIndex (HDPA hdpa, LPCVOID p)
551 {
552 INT i;
553
554 if (!hdpa || !hdpa->ptrs)
555 return -1;
556
557 for (i = 0; i < hdpa->nItemCount; i++) {
558 if (hdpa->ptrs[i] == p)
559 return i;
560 }
561
562 return -1;
563 }
564
565
566 /**************************************************************************
567 * DPA_InsertPtr [COMCTL32.334]
568 *
569 * Inserts a pointer into a dynamic pointer array
570 *
571 * PARAMS
572 * hdpa [I] handle (pointer) to the array
573 * i [I] array index
574 * p [I] pointer to insert
575 *
576 * RETURNS
577 * Success: index of the inserted pointer
578 * Failure: -1
579 */
580 INT WINAPI DPA_InsertPtr (const HDPA hdpa, INT i, LPVOID p)
581 {
582 TRACE("(%p %d %p)\n", hdpa, i, p);
583
584 if (!hdpa || i < 0) return -1;
585
586 /* append item if index is out of bounds */
587 i = min(hdpa->nItemCount, i);
588
589 /* create empty spot at the end */
590 if (!DPA_SetPtr(hdpa, hdpa->nItemCount, 0)) return -1;
591
592 if (i != hdpa->nItemCount - 1)
593 memmove (hdpa->ptrs + i + 1, hdpa->ptrs + i,
594 (hdpa->nItemCount - i - 1) * sizeof(LPVOID));
595
596 hdpa->ptrs[i] = p;
597 return i;
598 }
599
600
601 /**************************************************************************
602 * DPA_SetPtr [COMCTL32.335]
603 *
604 * Sets a pointer in the pointer array
605 *
606 * PARAMS
607 * hdpa [I] handle (pointer) to the pointer array
608 * i [I] index of the pointer that will be set
609 * p [I] pointer to be set
610 *
611 * RETURNS
612 * Success: TRUE
613 * Failure: FALSE
614 */
615 BOOL WINAPI DPA_SetPtr (const HDPA hdpa, INT i, LPVOID p)
616 {
617 LPVOID *lpTemp;
618
619 TRACE("(%p %d %p)\n", hdpa, i, p);
620
621 if (!hdpa || i < 0)
622 return FALSE;
623
624 if (hdpa->nItemCount <= i) {
625 /* within the old array */
626 if (hdpa->nMaxCount <= i) {
627 /* resize the block of memory */
628 INT nNewItems =
629 hdpa->nGrow * ((((i+1) - 1) / hdpa->nGrow) + 1);
630 INT nSize = nNewItems * sizeof(LPVOID);
631
632 if (hdpa->ptrs)
633 lpTemp = HeapReAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY, hdpa->ptrs, nSize);
634 else
635 lpTemp = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY, nSize);
636
637 if (!lpTemp)
638 return FALSE;
639
640 hdpa->nMaxCount = nNewItems;
641 hdpa->ptrs = lpTemp;
642 }
643 hdpa->nItemCount = i+1;
644 }
645
646 /* put the new entry in */
647 hdpa->ptrs[i] = p;
648
649 return TRUE;
650 }
651
652
653 /**************************************************************************
654 * DPA_DeletePtr [COMCTL32.336]
655 *
656 * Removes a pointer from the pointer array.
657 *
658 * PARAMS
659 * hdpa [I] handle (pointer) to the pointer array
660 * i [I] index of the pointer that will be deleted
661 *
662 * RETURNS
663 * Success: deleted pointer
664 * Failure: NULL
665 */
666 LPVOID WINAPI DPA_DeletePtr (const HDPA hdpa, INT i)
667 {
668 LPVOID *lpDest, *lpSrc, lpTemp = NULL;
669 INT nSize;
670
671 TRACE("(%p %d)\n", hdpa, i);
672
673 if ((!hdpa) || i < 0 || i >= hdpa->nItemCount)
674 return NULL;
675
676 lpTemp = hdpa->ptrs[i];
677
678 /* do we need to move ?*/
679 if (i < hdpa->nItemCount - 1) {
680 lpDest = hdpa->ptrs + i;
681 lpSrc = lpDest + 1;
682 nSize = (hdpa->nItemCount - i - 1) * sizeof(LPVOID);
683 TRACE("-- move dest=%p src=%p size=%x\n",
684 lpDest, lpSrc, nSize);
685 memmove (lpDest, lpSrc, nSize);
686 }
687
688 hdpa->nItemCount --;
689
690 /* free memory ?*/
691 if ((hdpa->nMaxCount - hdpa->nItemCount) >= hdpa->nGrow) {
692 INT nNewItems = max(hdpa->nGrow * 2, hdpa->nItemCount);
693 nSize = nNewItems * sizeof(LPVOID);
694 lpDest = HeapReAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
695 hdpa->ptrs, nSize);
696 if (!lpDest)
697 return NULL;
698
699 hdpa->nMaxCount = nNewItems;
700 hdpa->ptrs = lpDest;
701 }
702
703 return lpTemp;
704 }
705
706
707 /**************************************************************************
708 * DPA_DeleteAllPtrs [COMCTL32.337]
709 *
710 * Removes all pointers and reinitializes the array.
711 *
712 * PARAMS
713 * hdpa [I] handle (pointer) to the pointer array
714 *
715 * RETURNS
716 * Success: TRUE
717 * Failure: FALSE
718 */
719 BOOL WINAPI DPA_DeleteAllPtrs (const HDPA hdpa)
720 {
721 TRACE("(%p)\n", hdpa);
722
723 if (!hdpa)
724 return FALSE;
725
726 if (hdpa->ptrs && (!HeapFree (hdpa->hHeap, 0, hdpa->ptrs)))
727 return FALSE;
728
729 hdpa->nItemCount = 0;
730 hdpa->nMaxCount = hdpa->nGrow * 2;
731 hdpa->ptrs = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
732 hdpa->nMaxCount * sizeof(LPVOID));
733
734 return TRUE;
735 }
736
737
738 /**************************************************************************
739 * DPA_QuickSort [Internal]
740 *
741 * Ordinary quicksort (used by DPA_Sort).
742 *
743 * PARAMS
744 * lpPtrs [I] pointer to the pointer array
745 * l [I] index of the "left border" of the partition
746 * r [I] index of the "right border" of the partition
747 * pfnCompare [I] pointer to the compare function
748 * lParam [I] user defined value (3rd parameter in compare function)
749 *
750 * RETURNS
751 * NONE
752 */
753 static VOID DPA_QuickSort (LPVOID *lpPtrs, INT l, INT r,
754 PFNDPACOMPARE pfnCompare, LPARAM lParam)
755 {
756 INT m;
757 LPVOID t;
758
759 TRACE("l=%i r=%i\n", l, r);
760
761 if (l==r) /* one element is always sorted */
762 return;
763 if (r<l) /* oops, got it in the wrong order */
764 {
765 DPA_QuickSort(lpPtrs, r, l, pfnCompare, lParam);
766 return;
767 }
768 m = (l+r)/2; /* divide by two */
769 DPA_QuickSort(lpPtrs, l, m, pfnCompare, lParam);
770 DPA_QuickSort(lpPtrs, m+1, r, pfnCompare, lParam);
771
772 /* join the two sides */
773 while( (l<=m) && (m<r) )
774 {
775 if(pfnCompare(lpPtrs[l],lpPtrs[m+1],lParam)>0)
776 {
777 t = lpPtrs[m+1];
778 memmove(&lpPtrs[l+1],&lpPtrs[l],(m-l+1)*sizeof(lpPtrs[l]));
779 lpPtrs[l] = t;
780
781 m++;
782 }
783 l++;
784 }
785 }
786
787
788 /**************************************************************************
789 * DPA_Sort [COMCTL32.338]
790 *
791 * Sorts a pointer array using a user defined compare function
792 *
793 * PARAMS
794 * hdpa [I] handle (pointer) to the pointer array
795 * pfnCompare [I] pointer to the compare function
796 * lParam [I] user defined value (3rd parameter of compare function)
797 *
798 * RETURNS
799 * Success: TRUE
800 * Failure: FALSE
801 */
802 BOOL WINAPI DPA_Sort (const HDPA hdpa, PFNDPACOMPARE pfnCompare, LPARAM lParam)
803 {
804 if (!hdpa || !pfnCompare)
805 return FALSE;
806
807 TRACE("(%p %p 0x%lx)\n", hdpa, pfnCompare, lParam);
808
809 if ((hdpa->nItemCount > 1) && (hdpa->ptrs))
810 DPA_QuickSort (hdpa->ptrs, 0, hdpa->nItemCount - 1,
811 pfnCompare, lParam);
812
813 return TRUE;
814 }
815
816
817 /**************************************************************************
818 * DPA_Search [COMCTL32.339]
819 *
820 * Searches a pointer array for a specified pointer
821 *
822 * PARAMS
823 * hdpa [I] handle (pointer) to the pointer array
824 * pFind [I] pointer to search for
825 * nStart [I] start index
826 * pfnCompare [I] pointer to the compare function
827 * lParam [I] user defined value (3rd parameter of compare function)
828 * uOptions [I] search options
829 *
830 * RETURNS
831 * Success: index of the pointer in the array.
832 * Failure: -1
833 */
834 INT WINAPI DPA_Search (const HDPA hdpa, LPVOID pFind, INT nStart,
835 PFNDPACOMPARE pfnCompare, LPARAM lParam, UINT uOptions)
836 {
837 if (!hdpa || !pfnCompare || !pFind)
838 return -1;
839
840 TRACE("(%p %p %d %p 0x%08lx 0x%08x)\n",
841 hdpa, pFind, nStart, pfnCompare, lParam, uOptions);
842
843 if (uOptions & DPAS_SORTED) {
844 /* array is sorted --> use binary search */
845 INT l, r, x, n;
846 LPVOID *lpPtr;
847
848 /* for binary search ignore start index */
849 l = 0;
850 r = hdpa->nItemCount - 1;
851 lpPtr = hdpa->ptrs;
852 while (r >= l) {
853 x = (l + r) / 2;
854 n = (pfnCompare)(pFind, lpPtr[x], lParam);
855 if (n == 0)
856 return x;
857 else if (n < 0)
858 r = x - 1;
859 else /* (n > 0) */
860 l = x + 1;
861 }
862 if (uOptions & (DPAS_INSERTBEFORE|DPAS_INSERTAFTER)) return l;
863 }
864 else {
865 /* array is not sorted --> use linear search */
866 LPVOID *lpPtr;
867 INT nIndex;
868
869 nIndex = (nStart == -1)? 0 : nStart;
870 lpPtr = hdpa->ptrs;
871 for (; nIndex < hdpa->nItemCount; nIndex++) {
872 if ((pfnCompare)(pFind, lpPtr[nIndex], lParam) == 0)
873 return nIndex;
874 }
875 }
876
877 return -1;
878 }
879
880
881 /**************************************************************************
882 * DPA_CreateEx [COMCTL32.340]
883 *
884 * Creates a dynamic pointer array using the specified size and heap.
885 *
886 * PARAMS
887 * nGrow [I] number of items by which the array grows when it is filled
888 * hHeap [I] handle to the heap where the array is stored
889 *
890 * RETURNS
891 * Success: handle (pointer) to the pointer array.
892 * Failure: NULL
893 *
894 * NOTES
895 * The DPA_ functions can be used to create and manipulate arrays of
896 * pointers.
897 */
898 HDPA WINAPI DPA_CreateEx (INT nGrow, HANDLE hHeap)
899 {
900 HDPA hdpa;
901
902 TRACE("(%d %p)\n", nGrow, hHeap);
903
904 if (hHeap)
905 hdpa = HeapAlloc (hHeap, HEAP_ZERO_MEMORY, sizeof(*hdpa));
906 else
907 hdpa = Alloc (sizeof(*hdpa));
908
909 if (hdpa) {
910 hdpa->nGrow = max(8, nGrow);
911 hdpa->hHeap = hHeap ? hHeap : GetProcessHeap();
912 hdpa->nMaxCount = hdpa->nGrow * 2;
913 hdpa->ptrs = HeapAlloc (hdpa->hHeap, HEAP_ZERO_MEMORY,
914 hdpa->nMaxCount * sizeof(LPVOID));
915 }
916
917 TRACE("-- %p\n", hdpa);
918
919 return hdpa;
920 }
921
922
923 /**************************************************************************
924 * DPA_Create [COMCTL32.328]
925 *
926 * Creates a dynamic pointer array.
927 *
928 * PARAMS
929 * nGrow [I] number of items by which the array grows when it is filled
930 *
931 * RETURNS
932 * Success: handle (pointer) to the pointer array.
933 * Failure: NULL
934 *
935 * NOTES
936 * The DPA_ functions can be used to create and manipulate arrays of
937 * pointers.
938 */
939 HDPA WINAPI DPA_Create (INT nGrow)
940 {
941 return DPA_CreateEx( nGrow, 0 );
942 }
943
944
945 /**************************************************************************
946 * DPA_EnumCallback [COMCTL32.385]
947 *
948 * Enumerates all items in a dynamic pointer array.
949 *
950 * PARAMS
951 * hdpa [I] handle to the dynamic pointer array
952 * enumProc [I]
953 * lParam [I]
954 *
955 * RETURNS
956 * none
957 */
958 VOID WINAPI DPA_EnumCallback (HDPA hdpa, PFNDPAENUMCALLBACK enumProc,
959 LPVOID lParam)
960 {
961 INT i;
962
963 TRACE("(%p %p %p)\n", hdpa, enumProc, lParam);
964
965 if (!hdpa)
966 return;
967 if (hdpa->nItemCount <= 0)
968 return;
969
970 for (i = 0; i < hdpa->nItemCount; i++) {
971 if ((enumProc)(hdpa->ptrs[i], lParam) == 0)
972 return;
973 }
974
975 return;
976 }
977
978
979 /**************************************************************************
980 * DPA_DestroyCallback [COMCTL32.386]
981 *
982 * Enumerates all items in a dynamic pointer array and destroys it.
983 *
984 * PARAMS
985 * hdpa [I] handle to the dynamic pointer array
986 * enumProc [I]
987 * lParam [I]
988 *
989 * RETURNS
990 * none
991 */
992 void WINAPI DPA_DestroyCallback (HDPA hdpa, PFNDPAENUMCALLBACK enumProc,
993 LPVOID lParam)
994 {
995 TRACE("(%p %p %p)\n", hdpa, enumProc, lParam);
996
997 DPA_EnumCallback (hdpa, enumProc, lParam);
998 DPA_Destroy (hdpa);
999 }
1000
1001 /**************************************************************************
1002 * DPA_GetSize [COMCTL32.@]
1003 *
1004 * Returns all array allocated memory size
1005 *
1006 * PARAMS
1007 * hdpa [I] handle to the dynamic pointer array
1008 *
1009 * RETURNS
1010 * Size in bytes
1011 */
1012 ULONGLONG WINAPI DPA_GetSize(HDPA hdpa)
1013 {
1014 TRACE("(%p)\n", hdpa);
1015
1016 if (!hdpa) return 0;
1017
1018 return sizeof(DPA) + hdpa->nMaxCount*sizeof(PVOID);
1019 }
A free Windows-compatible Operating System