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