Point Cloud Library (PCL) 1.14.0
Loading...
Searching...
No Matches
opennurbs_fsp.h
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
19class ON_CLASS ON_FixedSizePool
20{
21public:
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 std::size_t sizeof_element,
54 std::size_t element_count_estimate,
55 std::size_t block_element_capacity
56 );
57
58 /*
59 Returns:
60 Size of the elements in this pool.
61 */
62 std::size_t SizeofElement() const;
63
64 /*
65 Returns:
66 A pointer to sizeof_element bytes. The memory is zeroed.
67 */
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 std::size_t ActiveElementCount() const;
126
127 /*
128 Returns:
129 Total number of elements = number of active elements + number of returned elements.
130 */
131 std::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 */
178 void* FirstElement( std::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 std::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 ( std::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( std::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( std::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(std::size_t element_index) const;
299
300public:
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 */
327
328private:
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 std::size_t m_al_count;
345 std::size_t m_sizeof_element;
346 std::size_t m_block_element_count; // block element count
347 std::size_t m_active_element_count; // number of active elements
348 std::size_t m_total_element_count; // total number of elements (active + returned)
349 ON_MEMORY_POOL* m_heap;
350
351private:
352 // returns capacity of elements in existing block
353 std::size_t BlockElementCapacity( const void* block ) const;
354
355 // returns number of allocated of elements in existing block
356 std::size_t BlockElementCount( const void* block ) const;
357private:
358 // prohibit copy construction and operator=.
360 ON_FixedSizePool& operator=(const ON_FixedSizePool&);
361};
362
364{
365public:
367
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 */
409 void* FirstElement( std::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 std::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 ( std::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( std::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( std::size_t* block_element_count );
488
489private:
490 void* m_it_block;
491 void* m_it_element;
492
493 // no implementation (you can use a copy construtor)
495};
496
497
498template <class T> class ON_SimpleFixedSizePool : private ON_FixedSizePool
499{
500public:
501 // construction ////////////////////////////////////////////////////////
502
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 std::size_t element_count_estimate,
530 std::size_t block_element_count
531 );
532
533 /*
534 Returns:
535 Size of the elements in this pool.
536 */
537 std::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 std::size_t ActiveElementCount() const;
601
602 /*
603 Returns:
604 Total number of elements = number of active elements + number of returned elements.
605 */
606 std::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 std::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( std::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( std::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(std::size_t element_index) const;
713
714public:
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
742private:
743 // prohibit copy construction and operator=.
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
void * NextElement()
bool Create(std::size_t sizeof_element, std::size_t element_count_estimate, std::size_t block_element_capacity)
ON_MEMORY_POOL * Heap()
void ReturnElement(void *p)
std::size_t TotalElementCount() const
void SetHeap(ON_MEMORY_POOL *heap)
void * FirstBlock(std::size_t *block_element_count)
void * FirstElement(std::size_t element_index)
std::size_t ActiveElementCount() const
void * NextBlock(std::size_t *block_element_count)
std::size_t SizeofElement() const
void * Element(std::size_t element_index) const
void * FirstElement()
void * AllocateElement()
void EmergencyDestroy()
void * FirstElement(std::size_t element_index)
void * NextBlock(std::size_t *block_element_count)
void * FirstBlock(std::size_t *block_element_count)
ON_FixedSizePoolIterator(const class ON_FixedSizePool &fsp)
const class ON_FixedSizePool & m_fsp
T * NextBlock(std::size_t *block_element_count)
T * Element(std::size_t element_index) const
T * FirstBlock(std::size_t *block_element_count)
std::size_t TotalElementCount() const
void SetHeap(ON_MEMORY_POOL *heap)
std::size_t ActiveElementCount() const
std::size_t SizeofElement() const
bool Create(std::size_t element_count_estimate, std::size_t block_element_count)