ReactOS 0.4.15-dev-8348-gc1b9bb5
dpa.c
Go to the documentation of this file.
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
47
48typedef struct _DPA
49{
56
57typedef struct _STREAMDATA
58{
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 */
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 */
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 */
266 PFNDPACOMPARE pfnCompare, PFNDPAMERGE pfnMerge,
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 */
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 */
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 */
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 */
470HDPA 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 */
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 */
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 */
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 */
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 */
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 */
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 */
764static 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 */
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 */
845INT 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 */
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 */
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 */
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 */
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 */
1024{
1025 TRACE("(%p)\n", hdpa);
1026
1027 if (!hdpa) return 0;
1028
1029 return sizeof(DPA) + hdpa->nMaxCount*sizeof(PVOID);
1030}
#define WINE_DEFAULT_DEBUG_CHANNEL(t)
Definition: precomp.h:23
#define WARN(fmt,...)
Definition: precomp.h:61
PVOID Alloc(IN DWORD dwFlags, IN SIZE_T dwBytes)
Definition: main.c:63
r l[0]
Definition: byte_order.h:168
LPARAM lParam
Definition: combotst.c:139
#define E_OUTOFMEMORY
Definition: ddrawi.h:100
#define E_INVALIDARG
Definition: ddrawi.h:101
#define E_FAIL
Definition: ddrawi.h:102
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
static VOID DPA_QuickSort(LPVOID *lpPtrs, INT l, INT r, PFNDPACOMPARE pfnCompare, LPARAM lParam)
Definition: dpa.c:764
BOOL WINAPI DPA_Sort(HDPA hdpa, PFNDPACOMPARE pfnCompare, LPARAM lParam)
Definition: dpa.c:813
struct _STREAMDATA * PSTREAMDATA
ULONGLONG WINAPI DPA_GetSize(HDPA hdpa)
Definition: dpa.c:1023
struct _DPA DPA
INT WINAPI DPA_Search(HDPA hdpa, LPVOID pFind, INT nStart, PFNDPACOMPARE pfnCompare, LPARAM lParam, UINT uOptions)
Definition: dpa.c:845
BOOL WINAPI DPA_Merge(HDPA hdpa1, HDPA hdpa2, DWORD dwFlags, PFNDPACOMPARE pfnCompare, PFNDPAMERGE pfnMerge, LPARAM lParam)
Definition: dpa.c:265
HDPA WINAPI DPA_Clone(const HDPA hdpa, HDPA hdpaNew)
Definition: dpa.c:470
HDPA WINAPI DPA_CreateEx(INT nGrow, HANDLE hHeap)
Definition: dpa.c:909
BOOL WINAPI DPA_SetPtr(HDPA hdpa, INT i, LPVOID p)
Definition: dpa.c:626
BOOL WINAPI DPA_DeleteAllPtrs(HDPA hdpa)
Definition: dpa.c:730
VOID WINAPI DPA_EnumCallback(HDPA hdpa, PFNDPAENUMCALLBACK enumProc, LPVOID lParam)
Definition: dpa.c:969
HRESULT WINAPI DPA_LoadStream(HDPA *phDpa, PFNDPASTREAM loadProc, IStream *pStream, LPVOID pData)
Definition: dpa.c:82
HRESULT WINAPI DPA_SaveStream(HDPA hDpa, PFNDPASTREAM saveProc, IStream *pStream, LPVOID pData)
Definition: dpa.c:179
INT WINAPI DPA_GetPtrIndex(HDPA hdpa, LPCVOID p)
Definition: dpa.c:561
void WINAPI DPA_DestroyCallback(HDPA hdpa, PFNDPAENUMCALLBACK enumProc, LPVOID lParam)
Definition: dpa.c:1003
BOOL WINAPI DPA_Grow(HDPA hdpa, INT nGrow)
Definition: dpa.c:423
LPVOID WINAPI DPA_DeletePtr(HDPA hdpa, INT i)
Definition: dpa.c:677
BOOL WINAPI DPA_Destroy(HDPA hdpa)
Definition: dpa.c:396
HDPA WINAPI DPA_Create(INT nGrow)
Definition: dpa.c:950
struct _STREAMDATA STREAMDATA
INT WINAPI DPA_InsertPtr(HDPA hdpa, INT i, LPVOID p)
Definition: dpa.c:591
#define GetProcessHeap()
Definition: compat.h:736
int(* FARPROC)()
Definition: compat.h:36
#define HeapAlloc
Definition: compat.h:733
#define HeapReAlloc
Definition: compat.h:734
#define HeapFree(x, y, z)
Definition: compat.h:735
#define HEAP_ZERO_MEMORY
Definition: compat.h:134
BOOL NTAPI IsBadWritePtr(IN LPVOID lp, IN UINT_PTR ucb)
Definition: except.c:883
BOOL NTAPI IsBadCodePtr(FARPROC lpfn)
Definition: except.c:872
unsigned int BOOL
Definition: ntddk_ex.h:94
unsigned long DWORD
Definition: ntddk_ex.h:95
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLdouble GLdouble t
Definition: gl.h:2047
GLdouble n
Definition: glext.h:7729
GLfloat GLfloat p
Definition: glext.h:8902
const GLfloat * m
Definition: glext.h:10848
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define UINT_MAX
Definition: limits.h:41
#define S_OK
Definition: intsafe.h:52
#define memmove(s1, s2, n)
Definition: mkisofs.h:881
static PVOID ptr
Definition: dispmode.c:27
#define min(a, b)
Definition: monoChain.cc:55
unsigned int UINT
Definition: ndis.h:50
#define LPVOID
Definition: nt_native.h:45
static TCHAR * items[]
Definition: page1.c:45
#define DPAS_INSERTBEFORE
Definition: commctrl.h:4863
void *(CALLBACK * PFNDPAMERGE)(_In_ UINT, _In_ void *, _In_ void *, _In_ LPARAM)
Definition: commctrl.h:4897
#define DPAMM_INSERT
Definition: commctrl.h:4969
#define DPAM_UNION
Definition: commctrl.h:4964
#define DPAS_SORTED
Definition: commctrl.h:4862
int(CALLBACK * PFNDPAENUMCALLBACK)(void *p, void *pData)
Definition: commctrl.h:4792
int(CALLBACK * PFNDPACOMPARE)(void *p1, void *p2, LPARAM lParam)
Definition: commctrl.h:4852
#define DPAMM_DELETE
Definition: commctrl.h:4968
#define DPAM_SORTED
Definition: commctrl.h:4962
HRESULT(CALLBACK * PFNDPASTREAM)(_In_ DPASTREAMINFO *, _In_ struct IStream *, _In_opt_ void *)
Definition: commctrl.h:4891
#define DPAS_INSERTAFTER
Definition: commctrl.h:4864
#define DPAM_INTERSECT
Definition: commctrl.h:4965
#define DPAMM_MERGE
Definition: commctrl.h:4967
#define DPA_GetPtr
Definition: commctrl.h:5
#define memset(x, y, z)
Definition: compat.h:39
HRESULT hr
Definition: shlfolder.c:183
#define TRACE(s)
Definition: solgame.cpp:4
void * pvItem
Definition: commctrl.h:4885
Definition: dpa.c:49
HANDLE hHeap
Definition: dpa.c:52
INT nGrow
Definition: dpa.c:53
LPVOID * ptrs
Definition: dpa.c:51
INT nItemCount
Definition: dpa.c:50
INT nMaxCount
Definition: dpa.c:54
DWORD dwItems
Definition: dpa.c:61
DWORD dwSize
Definition: dpa.c:59
DWORD dwData2
Definition: dpa.c:60
ULONGLONG QuadPart
Definition: ms-dtyp.idl:185
#define max(a, b)
Definition: svc.c:63
TW_UINT32 TW_UINT16 TW_UINT16 TW_MEMREF pData
Definition: twain.h:1830
int32_t INT
Definition: typedefs.h:58
uint32_t ULONG
Definition: typedefs.h:59
uint64_t ULONGLONG
Definition: typedefs.h:67
LONGLONG QuadPart
Definition: typedefs.h:114
*nSize LPSTR _Inout_ LPDWORD nSize
Definition: winbase.h:2084
_In_ PCCERT_CONTEXT _In_ DWORD dwFlags
Definition: wincrypt.h:1176
LONG_PTR LPARAM
Definition: windef.h:208
CONST void * LPCVOID
Definition: windef.h:191
#define WINAPI
Definition: msvc.h:6
#define S_FALSE
Definition: winerror.h:2357