1 /* 2 * Dynamic pointer array (DPA) implementation 3 * 4 * Copyright 1998 Eric Kohl 5 * 1998 Juergen Schmied <j.schmied@metronet.de> 6 * 2000 Eric Kohl for CodeWeavers 7 * 8 * This library is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU Lesser General Public 10 * License as published by the Free Software Foundation; either 11 * version 2.1 of the License, or (at your option) any later version. 12 * 13 * This library is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with this library; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA 21 * 22 * NOTES 23 * These functions were involuntarily documented by Microsoft in 2002 as 24 * the outcome of an anti-trust suit brought by various U.S. governments. 25 * As a result the specifications on MSDN are inaccurate, incomplete 26 * and misleading. A much more complete (unofficial) documentation is 27 * available at: 28 * 29 * http://members.ozemail.com.au/~geoffch/samples/win32/shell/comctl32 30 */ 31 32 #define COBJMACROS 33 34 #include <stdarg.h> 35 #include <limits.h> 36 37 #include "windef.h" 38 #include "winbase.h" 39 #include "winuser.h" 40 #include "commctrl.h" 41 #include "objbase.h" 42 43 #include "comctl32.h" 44 #include "wine/debug.h" 45 46 WINE_DEFAULT_DEBUG_CHANNEL(dpa); 47 48 typedef struct _DPA 49 { 50 INT nItemCount; 51 LPVOID *ptrs; 52 HANDLE hHeap; 53 INT nGrow; 54 INT nMaxCount; 55 } DPA; 56 57 typedef struct _STREAMDATA 58 { 59 DWORD dwSize; 60 DWORD dwData2; 61 DWORD dwItems; 62 } STREAMDATA, *PSTREAMDATA; 63 64 /************************************************************************** 65 * DPA_LoadStream [COMCTL32.9] 66 * 67 * Loads a dynamic pointer array from a stream 68 * 69 * PARAMS 70 * phDpa [O] pointer to a handle to a dynamic pointer array 71 * loadProc [I] pointer to a callback function 72 * pStream [I] pointer to a stream 73 * pData [I] pointer to callback data 74 * 75 * RETURNS 76 * Success: S_OK, S_FALSE - partial success 77 * Failure: HRESULT error code 78 * 79 * NOTES 80 * No more information available yet! 81 */ 82 HRESULT WINAPI DPA_LoadStream (HDPA *phDpa, PFNDPASTREAM loadProc, 83 IStream *pStream, LPVOID pData) 84 { 85 HRESULT errCode; 86 LARGE_INTEGER position; 87 ULARGE_INTEGER initial_pos; 88 STREAMDATA streamData; 89 DPASTREAMINFO streamInfo; 90 ULONG ulRead; 91 HDPA hDpa; 92 PVOID *ptr; 93 94 TRACE ("phDpa=%p loadProc=%p pStream=%p pData=%p\n", 95 phDpa, loadProc, pStream, pData); 96 97 if (!phDpa || !loadProc || !pStream) 98 return E_INVALIDARG; 99 100 *phDpa = NULL; 101 102 position.QuadPart = 0; 103 104 errCode = IStream_Seek (pStream, position, STREAM_SEEK_CUR, &initial_pos); 105 if (errCode != S_OK) 106 return errCode; 107 108 memset(&streamData, 0, sizeof(STREAMDATA)); 109 errCode = IStream_Read (pStream, &streamData, sizeof(STREAMDATA), &ulRead); 110 if (errCode != S_OK) 111 return errCode; 112 113 TRACE ("dwSize=%u dwData2=%u dwItems=%u\n", 114 streamData.dwSize, streamData.dwData2, streamData.dwItems); 115 116 if (ulRead < sizeof(STREAMDATA) || 117 streamData.dwSize < sizeof(STREAMDATA) || streamData.dwData2 != 1) { 118 /* back to initial position */ 119 position.QuadPart = initial_pos.QuadPart; 120 IStream_Seek (pStream, position, STREAM_SEEK_SET, NULL); 121 return E_FAIL; 122 } 123 124 if (streamData.dwItems > (UINT_MAX / 2 / sizeof(VOID*))) /* 536870911 */ 125 return E_OUTOFMEMORY; 126 127 /* create the dpa */ 128 hDpa = DPA_Create (streamData.dwItems); 129 if (!hDpa) 130 return E_OUTOFMEMORY; 131 132 if (!DPA_Grow (hDpa, streamData.dwItems)) { 133 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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