ReactOS  0.4.14-dev-50-g13bb5e2
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 
48 typedef struct _DPA
49 {
55 } DPA;
56 
57 typedef 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,
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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 }
void WINAPI DPA_DestroyCallback(HDPA hdpa, PFNDPAENUMCALLBACK enumProc, LPVOID lParam)
Definition: dpa.c:1003
#define memmove(s1, s2, n)
Definition: mkisofs.h:881
#define max(a, b)
Definition: svc.c:63
#define TRUE
Definition: types.h:120
static PFNDPASTREAM
Definition: dpa.c:56
HDPA WINAPI DPA_Create(INT nGrow)
Definition: dpa.c:950
BOOL NTAPI IsBadWritePtr(IN LPVOID lp, IN UINT_PTR ucb)
Definition: except.c:885
WINE_DEFAULT_DEBUG_CHANNEL(dpa)
#define DPAS_SORTED
Definition: commctrl.h:4833
HRESULT hr
Definition: shlfolder.c:183
static PFNDPAENUMCALLBACK
Definition: dpa.c:50
BOOL WINAPI DPA_Destroy(HDPA hdpa)
Definition: dpa.c:396
LPVOID WINAPI DPA_GetPtr(HDPA hdpa, INT nIndex)
Definition: dpa.c:527
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define DPAS_INSERTAFTER
Definition: commctrl.h:4835
#define WARN(fmt,...)
Definition: debug.h:111
*nSize LPSTR _Inout_ LPDWORD nSize
Definition: winbase.h:2024
DWORD dwData2
Definition: dpa.c:60
BOOL WINAPI DPA_Merge(HDPA hdpa1, HDPA hdpa2, DWORD dwFlags, PFNDPACOMPARE pfnCompare, PFNDPAMERGE pfnMerge, LPARAM lParam)
Definition: dpa.c:265
GLdouble n
Definition: glext.h:7729
GLdouble GLdouble t
Definition: gl.h:2047
INT nGrow
Definition: dpa.c:53
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
struct _STREAMDATA * PSTREAMDATA
DWORD dwItems
Definition: dpa.c:61
#define E_FAIL
Definition: ddrawi.h:102
#define DPAMM_INSERT
Definition: commctrl.h:4940
int32_t INT
Definition: typedefs.h:56
const GLfloat * m
Definition: glext.h:10848
HDPA WINAPI DPA_CreateEx(INT nGrow, HANDLE hHeap)
Definition: dpa.c:909
BOOL NTAPI IsBadCodePtr(FARPROC lpfn)
Definition: except.c:874
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 E_OUTOFMEMORY
Definition: ddrawi.h:100
HRESULT WINAPI DPA_SaveStream(HDPA hDpa, PFNDPASTREAM saveProc, IStream *pStream, LPVOID pData)
Definition: dpa.c:179
struct _STREAMDATA STREAMDATA
ULONGLONG QuadPart
Definition: ms-dtyp.idl:185
unsigned int BOOL
Definition: ntddk_ex.h:94
#define DPAM_SORTED
Definition: commctrl.h:4933
static PVOID ptr
Definition: dispmode.c:27
#define S_FALSE
Definition: winerror.h:2357
#define E_INVALIDARG
Definition: ddrawi.h:101
HDPA WINAPI DPA_Clone(const HDPA hdpa, HDPA hdpaNew)
Definition: dpa.c:470
smooth NULL
Definition: ftsmooth.c:416
LONG_PTR LPARAM
Definition: windef.h:208
#define DPAM_INTERSECT
Definition: commctrl.h:4936
r l[0]
Definition: byte_order.h:167
#define TRACE(s)
Definition: solgame.cpp:4
HRESULT WINAPI DPA_LoadStream(HDPA *phDpa, PFNDPASTREAM loadProc, IStream *pStream, LPVOID pData)
Definition: dpa.c:82
#define GetProcessHeap()
Definition: compat.h:395
PVOID WINAPI HeapAlloc(HANDLE, DWORD, SIZE_T)
LONG HRESULT
Definition: typedefs.h:77
uint64_t ULONGLONG
Definition: typedefs.h:65
#define WINAPI
Definition: msvc.h:8
BOOL WINAPI DPA_DeleteAllPtrs(HDPA hdpa)
Definition: dpa.c:730
static PFNDPAMERGE
Definition: dpa.c:57
PVOID Alloc(IN DWORD dwFlags, IN SIZE_T dwBytes)
Definition: main.c:63
unsigned long DWORD
Definition: ntddk_ex.h:95
INT WINAPI DPA_GetPtrIndex(HDPA hdpa, LPCVOID p)
Definition: dpa.c:561
LPVOID * ptrs
Definition: dpa.c:51
static IStream LPVOID
Definition: dpa.c:56
INT WINAPI DPA_InsertPtr(HDPA hdpa, INT i, LPVOID p)
Definition: dpa.c:591
_In_ PCCERT_CONTEXT _In_ DWORD dwFlags
Definition: wincrypt.h:1175
BOOL WINAPI DPA_Sort(HDPA hdpa, PFNDPACOMPARE pfnCompare, LPARAM lParam)
Definition: dpa.c:813
HANDLE hHeap
Definition: dpa.c:52
VOID WINAPI DPA_EnumCallback(HDPA hdpa, PFNDPAENUMCALLBACK enumProc, LPVOID lParam)
Definition: dpa.c:969
#define DPAMM_MERGE
Definition: commctrl.h:4938
DWORD dwSize
Definition: dpa.c:59
#define DPAM_UNION
Definition: commctrl.h:4935
#define UINT_MAX
Definition: limits.h:41
BOOL WINAPI DPA_Grow(HDPA hdpa, INT nGrow)
Definition: dpa.c:423
#define S_OK
Definition: intsafe.h:59
#define HeapReAlloc
Definition: compat.h:393
#define DPAMM_DELETE
Definition: commctrl.h:4939
#define min(a, b)
Definition: monoChain.cc:55
unsigned int UINT
Definition: ndis.h:50
#define HEAP_ZERO_MEMORY
Definition: compat.h:123
CONST void * LPCVOID
Definition: windef.h:191
LPVOID WINAPI DPA_DeletePtr(HDPA hdpa, INT i)
Definition: dpa.c:677
static VOID DPA_QuickSort(LPVOID *lpPtrs, INT l, INT r, PFNDPACOMPARE pfnCompare, LPARAM lParam)
Definition: dpa.c:764
unsigned int ULONG
Definition: retypes.h:1
struct _DPA DPA
ULONGLONG WINAPI DPA_GetSize(HDPA hdpa)
Definition: dpa.c:1023
GLfloat GLfloat p
Definition: glext.h:8902
TW_UINT32 TW_UINT16 TW_UINT16 TW_MEMREF pData
Definition: twain.h:1827
void * pvItem
Definition: commctrl.h:4856
static TCHAR * items[]
Definition: page1.c:45
static PFNDPACOMPARE
Definition: dpa.c:57
#define memset(x, y, z)
Definition: compat.h:39
LPARAM lParam
Definition: combotst.c:139
#define DPAS_INSERTBEFORE
Definition: commctrl.h:4834
INT WINAPI DPA_Search(HDPA hdpa, LPVOID pFind, INT nStart, PFNDPACOMPARE pfnCompare, LPARAM lParam, UINT uOptions)
Definition: dpa.c:845
#define HeapFree(x, y, z)
Definition: compat.h:394
int(* FARPROC)()
Definition: compat.h:28
INT nItemCount
Definition: dpa.c:50
LONGLONG QuadPart
Definition: typedefs.h:112
INT nMaxCount
Definition: dpa.c:54
Definition: dpa.c:48
BOOL WINAPI DPA_SetPtr(HDPA hdpa, INT i, LPVOID p)
Definition: dpa.c:626