1 /* $NoKeywords: $ */ 2 /* 3 // 4 // Copyright (c) 1993-2012 Robert McNeel & Associates. All rights reserved. 5 // OpenNURBS, Rhinoceros, and Rhino3D are registered trademarks of Robert 6 // McNeel & Associates. 7 // 8 // THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY. 9 // ALL IMPLIED WARRANTIES OF FITNESS FOR ANY PARTICULAR PURPOSE AND OF 10 // MERCHANTABILITY ARE HEREBY DISCLAIMED. 11 // 12 // For complete openNURBS copyright information see <http://www.opennurbs.org>. 13 // 14 //////////////////////////////////////////////////////////////// 15 */ 16 #if !defined(OPENNURBS_FSP_INC_) 17 #define OPENNURBS_FSP_INC_ 18 19 class ON_CLASS ON_FixedSizePool 20 { 21 public: 22 ON_FixedSizePool(); 23 ~ON_FixedSizePool(); 24 25 /* 26 Description: 27 Create a fixed size memory pool. 28 Parameters: 29 sizeof_element - [in] 30 number of bytes in each element. This parameter must be greater than zero. 31 In general, use sizeof(element type). If you pass a "raw" number as 32 sizeof_element, then be certain that it is the right size to insure the 33 fields in your elements will be properly aligned. 34 element_count_estimate - [in] (0 = good default) 35 If you know how many elements you will need, pass that number here. 36 It is better to slightly overestimate than to slightly underestimate. 37 If you do not have a good estimate, then use zero. 38 block_element_capacity - [in] (0 = good default) 39 If block_element_capacity is zero, Create() will calculate a block 40 size that is efficent for most applications. If you are an expert 41 user and want to specify the number of elements per block, 42 then pass the number of elements per block here. When 43 block_element_capacity > 0 and element_count_estimate > 0, the first 44 block will have a capacity of at least element_count_estimate; in this 45 case do not ask for extraordinarly large amounts of contiguous heap. 46 Remarks: 47 You must call Create() on an unused ON_FixedSizePool or call Destroy() 48 before calling create. 49 Returns: 50 True if successful and the pool can be used. 51 */ 52 bool Create( 53 size_t sizeof_element, 54 size_t element_count_estimate, 55 size_t block_element_capacity 56 ); 57 58 /* 59 Returns: 60 Size of the elements in this pool. 61 */ 62 size_t SizeofElement() const; 63 64 /* 65 Returns: 66 A pointer to sizeof_element bytes. The memory is zeroed. 67 */ 68 void* AllocateElement(); 69 70 /* 71 Description: 72 Return an element to the pool. 73 Parameters: 74 p - [in] 75 A pointer returned by AllocateElement(). 76 It is critical that p be from this pool and that 77 you return a pointer no more than one time. 78 Remarks: 79 If you find the following remarks confusing, but you really want to use 80 ReturnElement(), then here are some simple guidelines. 81 1) SizeofElement() must be >= 16 82 2) SizeofElement() must be a multiple of 8. 83 3) Do not use FirstElement() and NextElement() to iterate through 84 the pool. 85 86 If 1 to 3 don't work for you, then you need to understand the following 87 information before using ReturnElement(). 88 89 ON_FixedMemoryPool uses the first sizeof(void*) bytes of the 90 returned element for bookkeeping purposes. Therefore, if you 91 are going to use ReturnElement(), then SizeofElement() must be 92 at least sizeof(void*). If you are using a platform that requires 93 pointers to be aligned on sizeof(void*) boundaries, then 94 SizeofElement() must be a multiple of sizeof(void*). 95 If you are going to use ReturnElement() and then use FirstElement() 96 and NextElement() to iterate through the list of elements, then you 97 need to set a value in the returned element to indicate that it 98 needs to be skipped during the iteration. This value cannot be 99 located in the fist sizeof(void*) bytes of the element. If the 100 element is a class with a vtable, you cannot call a virtual 101 function on a returned element because the vtable pointer is 102 trashed when ReturnElement() modifies the fist sizeof(void*) bytes. 103 */ 104 void ReturnElement(void* p); 105 106 /* 107 Description: 108 Return all allocated elements to the pool. No heap is freed and 109 the pool remains initialized and ready for AllocateElement() 110 to be called. 111 */ 112 void ReturnAll(); 113 114 /* 115 Description: 116 Destroy the pool and free all the heap. The pool cannot be used again 117 until Create() is called. 118 */ 119 void Destroy(); 120 121 /* 122 Returns: 123 Number of active elements. (Elements that have been returned are not active.) 124 */ 125 size_t ActiveElementCount() const; 126 127 /* 128 Returns: 129 Total number of elements = number of active elements + number of returned elements. 130 */ 131 size_t TotalElementCount() const; 132 133 /* 134 Description: 135 Get the first element when iterating through the list of elements. 136 Parameters: 137 element_index - [in] 138 If you use the version of FirstElement() that has an 139 element_index parameter, then the iteration begins at 140 that element. 141 Example: 142 The loop will iteratate through all the elements returned from 143 AllocateElement(), including any that have be returned to the pool 144 using ReturnElement(). 145 146 // iterate through all elements in the pool 147 // This iteration will go through TotalElements() items. 148 for ( void* p = FirstElement(); 0 != p; p = NextElement() ) 149 { 150 // If you are not using ReturnElement(), then you may process 151 // "p" immediately. If you have used ReturnElement(), then you 152 // must check some value in p located after the first sizeof(void*) 153 // bytes to see if p is active. 154 if ( p is not active ) 155 continue; 156 157 ... process p 158 } 159 160 Returns: 161 The first element when iterating through the list of elements. 162 Remarks: 163 FirstElement() and NextElement() will return elements that have 164 been returned to the pool using ReturnElement(). If you use 165 ReturnElement(), then be sure to mark the element so it can be 166 identified and skipped. 167 168 Do not make any calls to FirstBlock() or NextBlock() when using 169 FirstElement() and NextElement() to iteratate through elements. 170 171 If you need iterate through a fixed size pool and another 172 function may also be in the middle of iterating the pool 173 as well, then use ON_FixedSizePoolIterator. In particular, 174 if you have multiple concurrent threads iterating the same 175 fixed size pool, then use ON_FixedSizePoolIterator. 176 */ 177 void* FirstElement(); 178 void* FirstElement( size_t element_index ); 179 180 /* 181 Description: 182 Get the next element when iterating through the list of elements. 183 Example: 184 See the FirstElement() documentation. 185 Returns: 186 The next element when iterating through the list of elements. 187 Remarks: 188 FirstElement() and NextElement() will return elements that have 189 been returned to the pool using ReturnElement(). If you use 190 ReturnElement(), then be sure to mark the element so it can be 191 identified and skipped. 192 193 Do not make any calls to FirstBlock() or NextBlock() when using 194 FirstElement() and NextElement() to iteratate through elements. 195 196 If you need iterate through a fixed size pool and another 197 function may also be in the middle of iterating the pool 198 as well, then use ON_FixedSizePoolIterator. In particular, 199 if you have multiple concurrent threads iterating the same 200 fixed size pool, then use ON_FixedSizePoolIterator. 201 */ 202 void* NextElement(); 203 204 /* 205 Description: 206 Get a pointer to the first element in the first block. 207 Parameters: 208 block_element_count - [out] (can be null) 209 If not null, the number of elements allocated from the 210 first block is returned in block_element_count. 211 Note that if you have used ReturnElement(), some 212 of these elemements may have been returned. 213 Example: 214 The loop will iteratate through all the blocks. 215 216 // iterate through all blocks in the pool 217 size_t block_element_count = 0; 218 for ( void* p = FirstBlock(&block_element_count); 219 0 != p; 220 p = NextBlock(&block_element_count) 221 ) 222 { 223 ElementType* e = (ElementType*)p; 224 for ( size_t i = 0; 225 i < block_element_count; 226 i++, e = ((const char*)e) + SizeofElement() 227 ) 228 { 229 ... 230 } 231 } 232 233 Returns: 234 The first block when iterating the list of blocks. 235 Remarks: 236 The heap for a fixed size memory pool is simply a linked 237 list of blocks. FirstBlock() and NextBlock() can be used 238 to iterate through the list of blocks. 239 240 Do not make any calls to FirstElement() or NextElement() when using 241 FirstBlock() and NextBlock() to iteratate through blocks. 242 243 If you need iterate through a fixed size pool and another 244 function may also be in the middle of iterating the pool 245 as well, then use ON_FixedSizePoolIterator. In particular, 246 if you have multiple concurrent threads iterating the same 247 fixed size pool, then use ON_FixedSizePoolIterator. 248 */ 249 void* FirstBlock( size_t* block_element_count ); 250 251 /* 252 Description: 253 Get the next block when iterating through the blocks. 254 Parameters: 255 block_element_count - [out] (can be null) 256 If not null, the number of elements allocated from the 257 block is returned in block_element_count. Note that if 258 you have used ReturnElement(), some of these elemements 259 may have been returned. 260 Example: 261 See the FirstBlock() documentation. 262 Returns: 263 The next block when iterating through the blocks. 264 Remarks: 265 Do not make any calls to FirstElement() or NextElement() when using 266 FirstBlock() and NextBlock() to iteratate through blocks. 267 268 If you need iterate through a fixed size pool and another 269 function may also be in the middle of iterating the pool 270 as well, then use ON_FixedSizePoolIterator. In particular, 271 if you have multiple concurrent threads iterating the same 272 fixed size pool, then use ON_FixedSizePoolIterator. 273 */ 274 void* NextBlock( size_t* block_element_count ); 275 276 /* 277 Description: 278 Get the i-th elment in the pool. 279 Parameters: 280 element_index - [in] 281 Returns: 282 A pointer to the i-th element. The first element has index = 0 283 and is the element returned by the first call to AllocateElement(). 284 The last element has index = ElementCount()-1. 285 If i is out of range, null is returned. 286 Remarks: 287 It is faster to use FirstElement() and NextElement() to iterate 288 through the entire list of elements. This function is relatively 289 efficient when there are a few large blocks in the pool 290 or element_index is small compared to the number of elements 291 in the first few blocks. 292 293 If ReturnElement() is not used or AllocateElement() calls to 294 are made after any use of ReturnElement(), then the i-th 295 element is the one returned by the (i+1)-th call to 296 AllocateElement(). 297 */ 298 void* Element(size_t element_index) const; 299 300 public: 301 // Expert user functions below for situations where you 302 // need to specify the heap used for this pool. 303 304 /* 305 Description: 306 Expert user function to specify which heap is used. 307 */ 308 void SetHeap( ON_MEMORY_POOL* heap ); 309 310 /* 311 Description: 312 Expert user function. 313 Returns: 314 Heap used by this pool. A null pointer means the default 315 heap is being used. 316 */ 317 ON_MEMORY_POOL* Heap(); 318 319 /* 320 Description: 321 Expert user function to call when the heap used by this pool 322 is no longer valid. This call zeros all fields and does not 323 call any heap functions. After calling EmergencyDestroy(), 324 the destructor will not attempt to free any heap. 325 */ 326 void EmergencyDestroy(); 327 328 private: 329 friend class ON_FixedSizePoolIterator; 330 331 void* m_first_block; 332 333 // ReturnElement() adds to the m_al_element stack. 334 // AllocateElement() will use the stack before using m_al_element_array[] 335 void* m_al_element_stack; 336 337 // used by the iterators 338 void* m_qwerty_it_block; 339 void* m_qwerty_it_element; 340 341 void* m_al_block; // current element allocation block. 342 // m_al_element_array[] is in m_al_block and has length m_al_count. 343 void* m_al_element_array; 344 size_t m_al_count; 345 size_t m_sizeof_element; 346 size_t m_block_element_count; // block element count 347 size_t m_active_element_count; // number of active elements 348 size_t m_total_element_count; // total number of elements (active + returned) 349 ON_MEMORY_POOL* m_heap; 350 351 private: 352 // returns capacity of elements in existing block 353 size_t BlockElementCapacity( const void* block ) const; 354 355 // returns number of allocated of elements in existing block 356 size_t BlockElementCount( const void* block ) const; 357 private: 358 // prohibit copy construction and operator=. 359 ON_FixedSizePool(const ON_FixedSizePool&); 360 ON_FixedSizePool& operator=(const ON_FixedSizePool&); 361 }; 362 363 class ON_CLASS ON_FixedSizePoolIterator 364 { 365 public: 366 ON_FixedSizePoolIterator( const class ON_FixedSizePool& fsp ); 367 368 const class ON_FixedSizePool& m_fsp; 369 370 /* 371 Description: 372 Get the first element when iterating through the list of elements. 373 Parameters: 374 element_index - [in] 375 If you use the version of FirstElement() that has an 376 element_index parameter, then the iteration begins at 377 that element. 378 Example: 379 The loop will iteratate through all the elements returned from 380 AllocateElement(), including any that have be returned to the pool 381 using ReturnElement(). 382 383 // iterate through all elements in the pool 384 // This iteration will go through TotalElements() items. 385 for ( void* p = FirstElement(); 0 != p; p = NextElement() ) 386 { 387 // If you are not using ReturnElement(), then you may process 388 // "p" immediately. If you have used ReturnElement(), then you 389 // must check some value in p located after the first sizeof(void*) 390 // bytes to see if p is active. 391 if ( p is not active ) 392 continue; 393 394 ... process p 395 } 396 397 Returns: 398 The first element when iterating through the list of elements. 399 Remarks: 400 FirstElement() and NextElement() will return elements that have 401 been returned to the pool using ReturnElement(). If you use 402 ReturnElement(), then be sure to mark the element so it can be 403 identified and skipped. 404 405 Do not make any calls to FirstBlock() or NextBlock() when using 406 FirstElement() and NextElement() to iteratate through elements. 407 */ 408 void* FirstElement(); 409 void* FirstElement( size_t element_index ); 410 411 /* 412 Description: 413 Get the next element when iterating through the list of elements. 414 Example: 415 See the FirstElement() documentation. 416 Returns: 417 The next element when iterating through the list of elements. 418 Remarks: 419 FirstElement() and NextElement() will return elements that have 420 been returned to the pool using ReturnElement(). If you use 421 ReturnElement(), then be sure to mark the element so it can be 422 identified and skipped. 423 424 Do not make any calls to FirstBlock() or NextBlock() when using 425 FirstElement() and NextElement() to iteratate through elements. 426 */ 427 void* NextElement(); 428 429 /* 430 Description: 431 Get a pointer to the first element in the first block. 432 Parameters: 433 block_element_count - [out] (can be null) 434 If not null, the number of elements allocated from the 435 first block is returned in block_element_count. 436 Note that if you have used ReturnElement(), some 437 of these elemements may have been returned. 438 Example: 439 The loop will iteratate through all the blocks. 440 441 // iterate through all blocks in the pool 442 size_t block_element_count = 0; 443 for ( void* p = FirstBlock(&block_element_count); 444 0 != p; 445 p = NextBlock(&block_element_count) 446 ) 447 { 448 ElementType* e = (ElementType*)p; 449 for ( size_t i = 0; 450 i < block_element_count; 451 i++, e = ((const char*)e) + SizeofElement() 452 ) 453 { 454 ... 455 } 456 } 457 458 Returns: 459 The first block when iterating the list of blocks. 460 Remarks: 461 The heap for a fixed size memory pool is simply a linked 462 list of blocks. FirstBlock() and NextBlock() can be used 463 to iterate through the list of blocks. 464 465 Do not make any calls to FirstElement() or NextElement() when using 466 FirstBlock() and NextBlock() to iteratate through blocks. 467 */ 468 void* FirstBlock( size_t* block_element_count ); 469 470 /* 471 Description: 472 Get the next block when iterating through the blocks. 473 Parameters: 474 block_element_count - [out] (can be null) 475 If not null, the number of elements allocated from the 476 block is returned in block_element_count. Note that if 477 you have used ReturnElement(), some of these elemements 478 may have been returned. 479 Example: 480 See the FirstBlock() documentation. 481 Returns: 482 The next block when iterating through the blocks. 483 Remarks: 484 Do not make any calls to FirstElement() or NextElement() when using 485 FirstBlock() and NextBlock() to iteratate through blocks. 486 */ 487 void* NextBlock( size_t* block_element_count ); 488 489 private: 490 void* m_it_block; 491 void* m_it_element; 492 493 // no implementation (you can use a copy construtor) 494 ON_FixedSizePoolIterator& operator=(const ON_FixedSizePoolIterator&); 495 }; 496 497 498 template <class T> class ON_SimpleFixedSizePool : private ON_FixedSizePool 499 { 500 public: 501 // construction //////////////////////////////////////////////////////// 502 503 ON_SimpleFixedSizePool(); 504 ~ON_SimpleFixedSizePool(); 505 506 /* 507 Description: 508 Create a fixed size memory pool. 509 Parameters: 510 element_count_estimate - [in] (0 = good default) 511 If you know how many elements you will need, pass that number here. 512 It is better to slightly overestimate than to slightly underestimate. 513 If you do not have a good estimate, then use zero. 514 block_element_count - [in] (0 = good default) 515 If block_element_count is zero, Create() will calculate a block 516 size that is efficent for most applications. If you are an expert 517 user and want to specify the number of blocks, then pass the number 518 of elements per block here. When block_element_count > 0 and 519 element_count_estimate > 0, the first block will be large enough 520 element_count_estimate*sizeof(T) bytes; in this case do not 521 ask for extraordinarly large amounts of contiguous heap. 522 Remarks: 523 You must call Create() on an unused ON_FixedSizePool or call Destroy() 524 before calling create. 525 Returns: 526 True if successful and the pool can be used. 527 */ 528 bool Create( 529 size_t element_count_estimate, 530 size_t block_element_count 531 ); 532 533 /* 534 Returns: 535 Size of the elements in this pool. 536 */ 537 size_t SizeofElement() const; 538 539 /* 540 Returns: 541 A pointer to sizeof_element bytes. The memory is zeroed. 542 */ 543 T* AllocateElement(); 544 545 /* 546 Description: 547 Return an element to the pool. 548 Parameters: 549 p - [in] 550 A pointer returned by AllocateElement(). 551 It is critical that p be from this pool and that 552 you return a pointer no more than one time. 553 Remarks: 554 If you find the following remarks confusing, but you really want to use 555 ReturnElement(), then here are some simple guidelines. 556 1) SizeofElement() must be >= 16 557 2) SizeofElement() must be a multiple of 8. 558 3) Do not use FirstElement() and NextElement() to iterate through 559 the pool. 560 561 If 1 to 3 don't work for you, then you need to understand the following 562 information before using ReturnElement(). 563 564 ON_FixedMemoryPool uses the first sizeof(void*) bytes of the 565 returned element for bookkeeping purposes. Therefore, if you 566 are going to use ReturnElement(), then SizeofElement() must be 567 at least sizeof(void*). If you are using a platform that requires 568 pointers to be aligned on sizeof(void*) boundaries, then 569 SizeofElement() must be a multiple of sizeof(void*). 570 If you are going to use ReturnElement() and then use FirstElement() 571 and NextElement() to iterate through the list of elements, then you 572 need to set a value in the returned element to indicate that it 573 needs to be skipped during the iteration. This value cannot be 574 located in the fist sizeof(void*) bytes of the element. If the 575 element is a class with a vtable, you cannot call a virtual 576 function on a returned element because the vtable pointer is 577 trashed when ReturnElement() modifies the fist sizeof(void*) bytes. 578 */ 579 void ReturnElement(T* p); 580 581 /* 582 Description: 583 Return all allocated elements to the pool. No heap is freed and 584 the pool remains initialized and ready for AllocateElement() 585 to be called. 586 */ 587 void ReturnAll(); 588 589 /* 590 Description: 591 Destroy the pool and free all the heap. The pool cannot be used again 592 until Create() is called. 593 */ 594 void Destroy(); 595 596 /* 597 Returns: 598 Number of active elements. (Elements that have been returned are not active.) 599 */ 600 size_t ActiveElementCount() const; 601 602 /* 603 Returns: 604 Total number of elements = number of active elements + number of returned elements. 605 */ 606 size_t TotalElementCount() const; 607 608 /* 609 Description: 610 Get the next element when iterating through the active elements. 611 Example: 612 The loop will iteratate through all the elements returned from 613 AllocateElement(), including any that have be returned to the pool 614 using ReturnElement(). 615 616 // iterate through all elements in the pool 617 for ( T* p = FirstElement(); 0 != p; p = NextElement() ) 618 { 619 // If you are not using ReturnElement(), then you may process 620 // "p" immediately. If you have used ReturnElement(), then you 621 // must check some value in p located after the first sizeof(void*) 622 // bytes to see if p is active. 623 if ( p is not active ) 624 continue; 625 626 ... process p 627 } 628 629 Returns: 630 The next element when iterating through the active elements. 631 Remarks: 632 NextElement() will return elements that have been returned to 633 the pool using ReturnElement(). If you use ReturnElement(), 634 be sure to mark the element so it can be identified and skipped. 635 */ 636 T* FirstElement(); 637 638 /* 639 Description: 640 Get the next element when iterating through the active elements. 641 Example: 642 See the FirstElement() documentation. 643 Returns: 644 The next element when iterating through the active elements. 645 Remarks: 646 NextElement() will return elements that have been returned to 647 the pool using ReturnElement(). If you use ReturnElement(), 648 be sure to mark the element so it can be identified and skipped. 649 */ 650 T* NextElement(); 651 652 /* 653 Description: 654 Get a pointer to the first element in the first block. 655 Example: 656 The loop will iteratate through all the blocks. 657 658 // iterate through all blocks in the pool 659 size_t block_element_count = 0; 660 for ( T* p = FirstBlock(&block_element_count); 661 0 != p; 662 p = NextBlock(&block_element_count) 663 ) 664 { 665 // a[] is an array of length block_element_count 666 } 667 668 Returns: 669 The next block when iterating the list of blocks. 670 Remarks: 671 Do not make any calls to FirstElement() or NextElement() when using 672 FirstBlock() and NextBlock() to iteratate through blocks. 673 */ 674 T* FirstBlock( size_t* block_element_count ); 675 676 /* 677 Description: 678 Get the next block when iterating through the blocks. 679 Example: 680 See the FirstBlock() documentation. 681 Returns: 682 The next block when iterating through the blocks. 683 Remarks: 684 Do not make any calls to FirstElement() or NextElement() when using 685 FirstBlock() and NextBlock() to iteratate through blocks. 686 */ 687 T* NextBlock( size_t* block_element_count ); 688 689 690 /* 691 Description: 692 Get the i-th elment in the pool. 693 Parameters: 694 element_index - [in] 695 Returns: 696 A pointer to the i-th element. The first element has index = 0 697 and is the element returned by the first call to AllocateElement(). 698 The last element has index = ElementCount()-1. 699 If i is out of range, null is returned. 700 Remarks: 701 It is faster to use FirstElement() and NextElement() to iterate 702 through the entire list of elements. This function is relatively 703 efficient when there are a few large blocks in the pool 704 or element_index is small compared to the number of elements 705 in the first few blocks. 706 707 If ReturnElement() is not used or AllocateElement() calls to 708 are made after any use of ReturnElement(), then the i-th 709 element is the one returned by the (i+1)-th call to 710 AllocateElement(). 711 */ 712 T* Element(size_t element_index) const; 713 714 public: 715 // Expert user functions below for situations where you 716 // need to specify the heap used for this pool. 717 718 /* 719 Description: 720 Expert user function to specify which heap is used. 721 */ 722 void SetHeap( ON_MEMORY_POOL* heap ); 723 724 /* 725 Description: 726 Expert user function. 727 Returns: 728 Heap used by this pool. A null pointer means the default 729 heap is being used. 730 */ 731 ON_MEMORY_POOL* Heap(); 732 733 /* 734 Description: 735 Expert user function to call when the heap used by this pool 736 is no longer valid. This call zeros all fields and does not 737 call any heap functions. After calling EmergencyDestroy(), 738 the destructor will not attempt to free any heap. 739 */ 740 void EmergencyDestroy(); 741 742 private: 743 // prohibit copy construction and operator=. 744 ON_SimpleFixedSizePool(const ON_SimpleFixedSizePool<T>&); 745 ON_SimpleFixedSizePool<T>& operator=(const ON_SimpleFixedSizePool<T>&); 746 }; 747 748 // definitions of the template functions are in a different file 749 // so that Microsoft's developer studio's autocomplete utility 750 // will work on the template functions. 751 #include "opennurbs_fsp_defs.h" 752 753 #endif 754 755