projects / reactos.git / blob
? search:


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