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 }
1035
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.