Point Cloud Library (PCL)  1.9.1-dev
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 
19 class ON_CLASS ON_FixedSizePool
20 {
21 public:
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  */
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  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  */
177  void* FirstElement();
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 
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:
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 
351 private:
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;
357 private:
358  // prohibit copy construction and operator=.
360  ON_FixedSizePool& operator=(const ON_FixedSizePool&);
361 };
362 
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( 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 
489 private:
490  void* m_it_block;
491  void* m_it_element;
492 
493  // no implementation (you can use a copy construtor)
495 };
496 
497 
498 template <class T> class ON_SimpleFixedSizePool : private ON_FixedSizePool
499 {
500 public:
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 
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=.
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 * FirstElement()
void * NextBlock(std::size_t *block_element_count)
void * FirstBlock(std::size_t *block_element_count)
const class ON_FixedSizePool & m_fsp
void * NextElement()