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