?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
remove \r
[extl.git] / extl / memory / basic_pool.h
blob173a8aa9ceea683399b7a9529d4d3ea636fd7566
1 /* ///////////////////////////////////////////////////////////////////////
2 * File: basic_pool.h
3 *
4 * Created: 08.04.14
5 * Updated: 08.04.28
6 *
7 * Brief: basic_pool class
8 *
9 * [<Home>]
10 * Copyright (c) 2008-2020, Waruqi All rights reserved.
11 * //////////////////////////////////////////////////////////////////// */
12
13 #ifndef EXTL_MEMORY_BASIC_POOL_H
14 #define EXTL_MEMORY_BASIC_POOL_H
15
16 /*!\file basic_pool.h
17 * \brief basic_pool class
18 */
19 #ifndef __cplusplus
20 # error basic_pool.h need be supported by c++.
21 #endif
22
23 /* ///////////////////////////////////////////////////////////////////////
24 * Includes
25 */
26 #include "basic_allocator_selector.h"
27 #include "../type/traits/limit_traits.h"
28 #include "../mpl/math/max_min.h"
29
30 #ifdef EXTL_MEMORY_BASIC_POOL_TEST_ENABLE
31 # include "../counter/clock_counter.h"
32 # include "../math/rand.h"
33 #endif
34
35 /* ///////////////////////////////////////////////////////////////////////
36 * Macros
37 */
38
39 /// EXTL_BASIC_POOL_DEFAULT_MAX_FREE_UNLIMITED
40 #define EXTL_BASIC_POOL_DEFAULT_MAX_FREE_UNLIMITED (0)
41
42 /*!if EXTL_BASIC_POOL_DEFAULT_MAX_FREE_INDEX == 15
43 * max_free_chunk_size = (15 + 1) * 4K = 64K
44 */
45 #define EXTL_BASIC_POOL_DEFAULT_MAX_FREE_INDEX (15)
46
47 /// Default alignment boundary = 2^4 = 16B
48 #define EXTL_BASIC_POOL_DEFAULT_ALIGN_BOUNDARY_POWER (4)
49
50 /* ///////////////////////////////////////////////////////////////////////
51 * ::extl namespace
52 */
53 EXTL_BEGIN_NAMESPACE
54
55 /*!\brief basic_pool class
56 *
57 * \param A The basic allocator type
58 * \param MAX_FREE_INDEX: The maximum index of a free chunk in the pool
59 * \param DEFAULT_ALIGN_BOUNDARY_POWER: Default alignment boundary = 2^DEFAULT_ALIGN_BOUNDARY_POWER (B)
60 *
61 * \ingroup extl_group_memory
62 */
63 template<
64 #ifdef EXTL_TEMPLATE_CLASS_DEFAULT_ARGUMENT_SUPPORT
65 typename_param_k A = typename_type_def_k basic_allocator_selector<e_byte_t>::allocator_type
66 , e_size_t MAX_FREE_INDEX = EXTL_BASIC_POOL_DEFAULT_MAX_FREE_INDEX
67 , e_size_t DEFAULT_ALIGN_BOUNDARY_POWER = EXTL_BASIC_POOL_DEFAULT_ALIGN_BOUNDARY_POWER
68 #else
69 typename_param_k A
70 , e_size_t MAX_FREE_INDEX
71 , e_size_t DEFAULT_ALIGN_BOUNDARY_POWER
72 #endif
73 >
74 class basic_pool
75 #ifdef EXTL_EBO_FORM_2_SUPPORT
76 : protected A /* if EBO is supported */
77 #endif
78 {
79 private:
80 typedef A base_type;
81 /// \name Types
82 /// @{
83 public:
84 typedef basic_pool<A, MAX_FREE_INDEX, DEFAULT_ALIGN_BOUNDARY_POWER > class_type;
85 typedef void value_type;
86 typedef A allocator_type;
87 typedef void* pointer;
88 typedef void const* const_pointer;
89 typedef void reference;
90 typedef void const_reference;
91 typedef typename_type_k allocator_type::size_type size_type;
92 /// @}
93
94 private:
95 /*!\brief Prohibit copy constructor and copy assignment
96 *
97 * Maybe EBO is not supported if uses extl::uncopyable,
98 * because some compilers do not support EBO_FORM_6 - EXTL_EBO_FORM_6_SUPPORT
99 */
100 basic_pool(class_type const&);
101 class_type& operator=(class_type const&);
102
103 private:
104
105 /* ///////////////////////////////////////////////////////////////////////
106 * The size of a memory page : 8K
107 */
108 enum { en_per_page_size = 8 * 1024 };
109
110 /* ///////////////////////////////////////////////////////////////////////
111 * Boundary alignment
112 */
113 /* Default boundary alignment : 16B = 2^4 */
114 enum { en_default_boundary_power = DEFAULT_ALIGN_BOUNDARY_POWER };
115 enum { en_default_boundary = 1 << en_default_boundary_power };
116
117 /* The boundary size of one chunk : 4K */
118 enum { en_chunk_boundary_size = en_per_page_size >> 1 };
119
120 /* ///////////////////////////////////////////////////////////////////////
121 * Index
122 */
123
124 /* Used to the conversion between index and the size of the chunk in the free pool and
125 * en_boundary_index = log2(en_per_page_size / 2)
126 *
127 * [Convertsion]
128 * index = (chunk_size >> en_boundary_index) - 1; ==> index = (chunk_size / 4K) - 1
129 * chunk_size = (index + 1) << en_boundary_index; ==> chunk_size = (index + 1) * 4K
130 */
131 enum { en_boundary_index = 12 };
132
133 /* The maximum index of the free pool
134 * if en_fp_max_index == 20 :
135 * max_regular_chunk_size = 8K(per_page_size) + 4K * (en_fp_max_index - 1) = 84K
136 */
137 enum { en_fp_max_index = 20 };
138
139 /* The index of the larger than en_fp_max_regular_chunk_size size
140 * chunks linked list in the free pool
141 */
142 enum { en_fp_non_regular_index = 0 };
143
144 /* The maximum index of the free chunk
145 * When the size of a chunk is larger than index_to_size(en_fp_max_free_index),
146 * the chunk will be destroyed at once
147 * and if the index is equal with EXTL_BASIC_POOL_DEFAULT_MAX_FREE_UNLIMITED,
148 * the chunk will be not destroyed until the basic_pool is destroyed
149 */
150 enum { en_fp_max_free_index = MAX_FREE_INDEX };
151
152 /* The current maximum index of the chunks linked list in the free pool
153 * ------ ------ ------ ------ ------ ------
154 * | | | | | | |
155 * ------ ------ ------ ------ ------ ------
156 * | |
157 * en_fp_max_index en_fp_max_free_index
158 * [Result]
159 * en_fp_cur_max_index = en_fp_max_index
160 *
161 * ------ ------ ------ ------ ------ ------
162 * | | | | | | |
163 * ------ ------ ------ ------ ------ ------
164 * | |
165 * en_fp_max_free_index en_fp_max_index
166 * [Result]
167 * en_fp_cur_max_index = en_fp_max_free_index
168 *
169 *
170 */
171 enum { en_fp_cur_max_index =
172 (en_fp_max_free_index == EXTL_BASIC_POOL_DEFAULT_MAX_FREE_UNLIMITED)?
173 en_fp_max_index : (EXTL_NS_MPL(min)<en_fp_max_free_index, en_fp_max_index>::value) };
174
175 /* Used to the conversion between index and the size of the block in the active pool */
176 enum { en_ap_max_index = (8 * 1024 / en_default_boundary) };
177 enum { en_ap_larger_blocks_index = en_ap_max_index - 1 };
178 enum { en_ap_non_free_index = 0 };
179
180 private:
181 /// The index of the free pool is converted to the size of the chunk
182 static size_type index_to_size(size_type index)
183 {
184 EXTL_ASSERT(0 < index);
185 return ((index + 1) << en_boundary_index);
186 }
187 /// The size of the chunk is converted to the index of the free pool
188 static size_type size_to_index(size_type size)
189 {
190 EXTL_ASSERT(en_per_page_size <= size);
191 return ((size >> en_boundary_index) - 1);
192 }
193
194 /// Deafult boundary alignment
195 static size_type default_align(size_type size)
196 {
197 return EXTL_ALIGN(size, en_default_boundary);
198 }
199
200 private:
201 enum { en_block_head_size = sizeof(size_type) };
202 /*!\brief The block type
203 * The linked node of the free blocks in one chunk
204 * <pre>
205 * ------ ------ ------ ------ ------ ------
206 * | | | | | | | - m_active_pool
207 * ------ ------ ------ ------ ------ ------
208 * block_head: |
209 * -------------- |
210 * | ap_index | -------
211 * -------------- <-- data()
212 * | next | ---------------> next block
213 * --------------
214 * | |
215 * | |
216 * | |
217 * --------------
218 * </pre>
219 */
220 struct block_head
221 {
222 /// \name Members
223 /// @{
224 size_type ap_index;
225 block_head* next;
226 /// @}
227
228 /// \name Methods
229 /// @{
230 pointer data() { return reinterpret_cast<pointer>(&next); }
231 size_type get_ap_index() const { return ap_index; }
232 void set_ap_index(size_type index) { ap_index = index; }
233 static block_head* get_block(pointer p) { return reinterpret_cast<block_head*>(static_cast<e_byte_t*>(p) - en_block_head_size); }
234 /// @}
235 };
236 friend struct block_head;
237
238 /*!\brief The chunk type
239 * A memory chunk node
240 * <pre>
241 * next: pointer to the next chunk
242 * index: (chunk_size >> boundary_index) - 1
243 *
244 * -------------- --------------
245 * | next | ---------> | | ----------> ... ----------> NULL
246 * -------------- | |
247 * | index | | |
248 * -------------- | chunk_head2 |
249 * | block_size | | |
250 * -------------- | |
251 * | free_count | | |
252 * -------------- | |
253 * | reserve1 | | |
254 * -------------- | |
255 * | first_free | --- | |
256 * -------------- | | |
257 * | last_free | ---|-- | |
258 * -------------- | | --------------
259 * | | <- |
260 * | | |
261 * | free blocks | |
262 * | | |
263 * | | <----
264 * --------------
265 *
266 * [size]
267 * -------------- -
268 * | chunk_head | |
269 * -------------- <- first_free - |
270 * | free_block1 | -- | block_size |
271 * -------------- | - |
272 * | free_block2 | -- | chunk size
273 * -------------- | |
274 * | free_block3 | -- |
275 * -------------- <-| last_free |
276 * | free_block4 | -- |
277 * -------------- | -
278 * NULL <-
279 * </pre>
280 */
281 struct chunk_head
282 {
283 /// \name Members
284 /// @{
285 chunk_head* next;
286 size_type index;
287 size_type block_size;
288 size_type free_count;
289 size_type reserve1;
290 block_head* first_free;
291 block_head* last_free;
292 /// @}
293
294 /// The bit count of the mask in the reserve1
295 enum mask1_bit_count
296 {
297 /// Does allocate free blocks by linked list?
298 en_is_alloc_by_linked_list = 0
299 };
300
301 /// \name Methods
302 /// @{
303 /// Allocates free blocks by linked list
304 e_bool_t is_alloc_by_linked_list() const { return 1 == (reserve1 & (1 << en_is_alloc_by_linked_list)); }
305 void enable_alloc_by_linked_list() { reserve1 |= (1 << en_is_alloc_by_linked_list); }
306 void disable_alloc_by_linked_list() { reserve1 &= ~(1 << en_is_alloc_by_linked_list); }
307
308 size_type chunk_size() const { return index_to_size(index); }
309 size_type data_size() const { return (chunk_size() - sizeof(chunk_head)); }
310 size_type block_count() const { return (data_size() / block_size); }
311 e_byte_t* data() { return reinterpret_cast<e_byte_t*>(&((this)[1])); }
312 block_head* first_block() { return reinterpret_cast<block_head*>(data()); }
313 block_head* last_block() { return reinterpret_cast<block_head*>(data() + (block_count() - 1) * block_size); }
314 e_bool_t is_free() const { return free_count == block_count(); }
315
316 /// Returns true if the block in the chunk
317 e_bool_t is_in_chunk(block_head const* block) const
318 {
319 EXTL_ASSERT(NULL != block);
320 if (reinterpret_cast<e_byte_t const*>(this) < reinterpret_cast<e_byte_t const*>(block) &&
321 reinterpret_cast<e_byte_t const*>(block) < (reinterpret_cast<e_byte_t const*>(this) + chunk_size()))
322 return e_true_v;
323 else return e_false_v;
324 }
325 /// @}
326
327 };
328 friend struct chunk_head;
329
330 /// The snapshot info of the pool
331 struct snapshot_info
332 {
333 /// \name Members
334 /// @{
335 size_type cur_alloc_size_from_system;
336 size_type cur_alloc_size_from_pool;
337 /// @}
338 };
339
340 /// \name Members
341 /// @{
342 private:
343 /*!\brief free pool
344 * <pre>
345 * index: 0 1 2 ... ... en_fp_max_index - 1
346 * chunk_size: larger 8K 8K + 4K * 1 8K + 4K * 2 8K + 4K * (index - 1)
347 * ------------- ------------- ------------- ------------- ------------- -------------
348 * | | | | ... ... | |
349 * ------------- ------------- ------------- ------------- ------------- -------------
350 * | | | | | |
351 * ------------- ------------- -------------
352 * | chunk1 | | ... ... | |
353 * ------------- ------------- -------------
354 * | | |
355 * ------------- ------------- NULL
356 * | chunk2 | |
357 * ------------- -------------
358 * | |
359 * NULL -------------
360 * | |
361 * -------------
362 * |
363 * NULL
364 * Note: non-regular regular ... ... regular regular
365 * descending order
366 * </pre>
367 */
368
369 /*!\brief active pool
370 * <pre>
371 * en_default_boundary = 16
372 *
373 * index: 0 1 2 ... ... en_ap_max_index - 1
374 * block_size: unknown 16B 16B * 2 16B * 3 16B * index en_ap_larger_blocks_index
375 * ------------- ------------- ------------- ------------- ------------- -------------
376 * | | | | ... ... | |
377 * ------------- ------------- ------------- ------------- ------------- -------------
378 * | | | | | |
379 * ------------- ------------- -------------
380 * | chunk1 | | ... ... | |
381 * ------------- ------------- -------------
382 * | | |
383 * ------------- ------------- NULL
384 * | chunk2 | |
385 * ------------- -------------
386 * | |
387 * NULL -------------
388 * | |
389 * -------------
390 * |
391 * NULL
392 *
393 * Note: non-free partial free ... ... partial free partial free
394 * (only a block) ascending order
395 * </pre>
396 */
397 chunk_head* m_free_pool[en_fp_max_index];
398 chunk_head* m_active_pool[en_ap_max_index];
399 /// @}
400
401 private:
402 /// Initialize a free chunk
403 void init_free_chunk(chunk_head* free_chunk, size_type block_size);
404
405
406 /// Allocates a free block from the partial-free chunk
407 block_head* alloc_block_from_free_chunk(chunk_head* free_chunk);
408 /// Allocates a free chunk from the free pool
409 chunk_head* alloc_chunk_from_free_pool(size_type chunk_size);
410
411
412 /// Deallocates a block to the chunk
413 void dealloc_block_to_chunk(block_head* block, chunk_head* chunk);
414 /// Deallocates a allocated chunk to the free pool
415 void dealloc_chunk_to_free_pool(chunk_head* chunk);
416 /// Deallocates a block from the given index of the active pool
417 e_bool_t dealloc_block_from_active_index(pointer block, size_type index);
418
419
420 /// Adds a chunk to the active pool and returns the index in the active pool
421 size_type add_chunk_to_active_pool(chunk_head* chunk);
422
423 /// \name Constructors
424 /// @{
425 public:
426 basic_pool()
427 {
428 EXTL_STATIC_ASSERT(en_ap_max_index >= 2);
429 EXTL_STATIC_ASSERT(en_fp_max_index >= 2);
430
431 /* Creates the basic_pool */
432 create();
433 }
434 ~basic_pool()
435 {
436 /* Destroys the basic_pool */
437 destroy();
438 }
439 /// @}
440
441 public:
442 allocator_type allocator() const
443 {
444 #ifdef EXTL_EBO_FORM_2_SUPPORT
445 return *this;
446 #else
447 return allocator_type();
448 #endif
449 }
450
451 /// Creates the basic_pool
452 void create();
453
454 /// Destroys the basic_pool
455 void destroy();
456
457 /// Shrinks the basic_pool
458 void shrink();
459
460 /// Allocates memory block of the specified size
461 pointer allocate(size_type size);
462
463 /// Reallocates memory block of the specified size
464 pointer reallocate(pointer block, size_type size);
465
466 /// Deallocates the block to pool
467 void deallocate(pointer block);
468
469 public:
470 /// Creates a snapshot of the pool
471 snapshot_info get_snapshot() const;
472
473 };
474
475 /* ///////////////////////////////////////////////////////////////////////
476 * Macro
477 */
478
479 /* Template declaration */
480 #ifdef EXTL_BASIC_POOL_TEMPLATE_DECL
481 # undef EXTL_BASIC_POOL_TEMPLATE_DECL
482 #endif
483
484 #define EXTL_BASIC_POOL_TEMPLATE_DECL \
485 template< typename_param_k A \
486 , e_size_t MAX_FREE_INDEX \
487 , e_size_t DEFAULT_ALIGN_BOUNDARY_POWER \
488 >
489
490 /* Class qualification */
491 #ifdef EXTL_BASIC_POOL_CLASS_QUAL
492 # undef EXTL_BASIC_POOL_CLASS_QUAL
493 #endif
494
495 #define EXTL_BASIC_POOL_CLASS_QUAL basic_pool<A, MAX_FREE_INDEX, DEFAULT_ALIGN_BOUNDARY_POWER>
496
497 /* Class qualification */
498 #ifdef EXTL_BASIC_POOL_CLASS_RET_QUAL
499 # undef EXTL_BASIC_POOL_CLASS_RET_QUAL
500 #endif
501
502 #define EXTL_BASIC_POOL_CLASS_RET_QUAL(ret_type) \
503 typename_type_ret_k EXTL_BASIC_POOL_CLASS_QUAL::ret_type \
504 EXTL_BASIC_POOL_CLASS_QUAL
505 /* ///////////////////////////////////////////////////////////////////////
506 * Class implemention
507 */
508
509 /* Creates the basic_pool */
510 EXTL_BASIC_POOL_TEMPLATE_DECL
511 inline void EXTL_BASIC_POOL_CLASS_QUAL::create()
512 {
513 mem_fill_0(m_free_pool, en_fp_max_index * sizeof(chunk_head*));
514 mem_fill_0(m_active_pool, en_ap_max_index * sizeof(chunk_head*));
515 }
516 /* Destroys the basic_pool */
517 EXTL_BASIC_POOL_TEMPLATE_DECL
518 void EXTL_BASIC_POOL_CLASS_QUAL::destroy()
519 {
520 size_type index;
521
522 /*!Frees all chunks in the active pool to system */
523 for(index = 0; index < en_ap_max_index; index++)
524 {
525 chunk_head* node = m_active_pool[index];
526 while(NULL != node)
527 {
528 chunk_head* pre_node = node;
529 node = node->next;
530 allocator().deallocate(reinterpret_cast<e_byte_t*>(pre_node));
531 }
532 m_active_pool[index] = NULL;
533 }
534
535 /*!Frees all chunks in the free pool to system */
536 for(index = 0; index < en_fp_cur_max_index; index++)
537 {
538 chunk_head* node = m_free_pool[index];
539 while(NULL != node)
540 {
541 chunk_head* pre_node = node;
542 node = node->next;
543 allocator().deallocate(reinterpret_cast<e_byte_t*>(pre_node));
544 }
545 m_free_pool[index] = NULL;
546 }
547 }
548 /* Shrinks the basic_pool */
549 EXTL_BASIC_POOL_TEMPLATE_DECL
550 void EXTL_BASIC_POOL_CLASS_QUAL::shrink()
551 {
552 /* Frees all chunks in the free pool to system */
553 for(size_type index = 0; index < en_fp_cur_max_index; index++)
554 {
555 chunk_head* node = m_free_pool[index];
556 while(NULL != node)
557 {
558 chunk_head* pre_node = node;
559 node = node->next;
560 allocator().deallocate(reinterpret_cast<e_byte_t*>(pre_node));
561 }
562 m_free_pool[index] = NULL;
563 }
564 }
565 /* Allocates memory block of the specified size */
566 EXTL_BASIC_POOL_TEMPLATE_DECL
567 EXTL_BASIC_POOL_CLASS_RET_QUAL(pointer)::allocate(size_type size)
568 {
569 if (0 == size) return NULL;
570
571 /*!Default: the eight-byte alignment */
572 size += en_block_head_size;
573 if(size < sizeof(block_head)) size = sizeof(block_head);
574 size_type block_size = default_align(size);
575 EXTL_ASSERT(0 == block_size % en_default_boundary);
576 EXTL_ASSERT(size <= block_size);
577
578 /*!index = block_size / 16 if en_default_boundary == 16 */
579 size_type index = block_size >> en_default_boundary_power;
580 EXTL_ASSERT((0 < index) && (index <= EXTL_LIMIT_TRAITS_UINT32_MAX));
581 #if 0
582 /*!Allocates a free block from the active pool */
583 if (index > en_ap_larger_blocks_index) index = en_ap_larger_blocks_index;
584 EXTL_ASSERT(0 != index);
585 chunk_head* node = m_active_pool[index];
586 while(NULL != node)
587 {
588 if (NULL != node->first_free && block_size <= node->block_size)
589 {
590 /* Allocates a free block from the free chunk */
591 block_head* block = alloc_block_from_free_chunk(node);
592 if(NULL != block) block->set_ap_index(index);
593
594 EXTL_ASSERT(size <= node->block_size);
595 return block->data();
596 }
597 node = node->next;
598 }
599 #else /* The optimization of the above code */
600 /*!Allocates a free block from the active pool */
601 if (index < en_ap_larger_blocks_index)
602 {
603 EXTL_ASSERT(0 != index);
604 chunk_head* node = m_active_pool[index];
605 while(NULL != node)
606 {
607 if (NULL != node->first_free)
608 {
609 /* Allocates a free block from the free chunk */
610 block_head* block = alloc_block_from_free_chunk(node);
611 if(NULL != block) block->set_ap_index(index);
612
613 EXTL_ASSERT(size <= node->block_size);
614 return block->data();
615 }
616 node = node->next;
617 }
618 }
619 else
620 {
621 chunk_head* node = m_active_pool[en_ap_larger_blocks_index];
622 while(NULL != node)
623 {
624 if (NULL != node->first_free && block_size <= node->block_size)
625 {
626 /* Allocates a free block from the free chunk */
627 block_head* block = alloc_block_from_free_chunk(node);
628 if(NULL != block) block->set_ap_index(en_ap_larger_blocks_index);
629
630 EXTL_ASSERT(size <= node->block_size);
631 return block->data();
632 }
633 node = node->next;
634 }
635
636 }
637 #endif
638 /*!Adjusts the size of a free chunck
639 * <pre>
640 * [Default]
641 * 8K, 8K + 4K * 1, 8K + 4K * 2, ..., 8K + 4K * n
642 * [Note]
643 * per-page size: 8K
644 * </pre>
645 */
646 size_type chunk_size = EXTL_ALIGN(sizeof(chunk_head) + block_size, en_chunk_boundary_size);
647 if (chunk_size < en_per_page_size) chunk_size = en_per_page_size;
648
649 /*!Allocates a free chunk from the free pool
650 * Note: Maybe new_chunk->chunk_size() != chunk_size
651 */
652 chunk_head* new_chunk = alloc_chunk_from_free_pool(chunk_size);
653 EXTL_ASSERT(NULL != new_chunk);
654
655 #if 0
656
657 /* Initializes the free chunk */
658 init_free_chunk(new_chunk, block_size);
659
660 /* Allocates a free block from the free chunk */
661 block_head* block = alloc_block_from_free_chunk(new_chunk);
662
663 #else /* The optimization of the above code */
664
665 EXTL_ASSERT(block_size <= new_chunk->chunk_size());
666 EXTL_ASSERT(sizeof(block_head) <= block_size);
667
668 /*!Initializes the free chunk */
669 new_chunk->block_size = block_size;
670 new_chunk->free_count = (new_chunk->chunk_size() - sizeof(chunk_head)) / block_size;
671 EXTL_ASSERT(0 < new_chunk->free_count);
672
673 /*!Allocates a free block from the free chunk */
674 block_head* block = new_chunk->first_block();
675 new_chunk->last_free = reinterpret_cast<block_head*>(reinterpret_cast<e_byte_t*>(block) + (new_chunk->free_count - 1) * block_size);
676 new_chunk->last_free->next = NULL;
677
678 /*!Delay to segregate a chunk */
679 if (1 == new_chunk->free_count)
680 {
681 new_chunk->first_free = NULL;
682 new_chunk->last_free = NULL;
683 new_chunk->enable_alloc_by_linked_list();
684 }
685 else
686 {
687 new_chunk->first_free = reinterpret_cast<block_head*>(reinterpret_cast<e_byte_t*>(block) + block_size);
688 if (new_chunk->first_free == new_chunk->last_free)
689 new_chunk->enable_alloc_by_linked_list();
690 else new_chunk->disable_alloc_by_linked_list();
691 }
692 --new_chunk->free_count;
693
694 #endif
695 /*!Adds the chunk to the active pool */
696 block->set_ap_index(add_chunk_to_active_pool(new_chunk));
697
698 return block->data();
699 }
700 /* Adds a chunk to the active pool and returns the index in the active pool */
701 EXTL_BASIC_POOL_TEMPLATE_DECL
702 EXTL_BASIC_POOL_CLASS_RET_QUAL(size_type)::add_chunk_to_active_pool(chunk_head* chunk)
703 {
704 EXTL_ASSERT(NULL != chunk);
705 /*!Puts the chunk to m_active_pool[en_ap_non_free_index]
706 * if there is only one block which has been allocated in the chunk
707 * <pre>
708 * [chunk]
709 * --------------
710 * | chunk_head |
711 * -------------- <- first_free
712 * | free_block1 | --
713 * -------------- |
714 * NULL <-
715 * </pre>
716 */
717 if (NULL == chunk->first_free)
718 {
719 EXTL_ASSERT(0 == chunk->free_count);
720 chunk->next = m_active_pool[en_ap_non_free_index];
721 m_active_pool[en_ap_non_free_index] = chunk;
722 return en_ap_non_free_index;
723 }
724 /* Puts the chunk to m_active_pool[index] */
725 else
726 {
727 /*!index = block_size / 8 if en_default_boundary == 8 */
728 size_type index = chunk->block_size >> en_default_boundary_power;
729 EXTL_ASSERT((0 < index) && (index <= EXTL_LIMIT_TRAITS_UINT32_MAX));
730
731 /* smaller block in the chunk */
732 if (index < en_ap_larger_blocks_index)
733 {
734 chunk->next = m_active_pool[index];
735 m_active_pool[index] = chunk;
736 return index;
737 }
738 /*!larger block in the chunk
739 * The chunks in the m_active_pool[en_ap_larger_blocks_index] is sorted by the size of a block in the ascending order
740 * <pre>
741 * m_active_pool[en_ap_larger_blocks_index]
742 * |
743 * --------- <-
744 * | chunk1 | -- eg: block_size = 1
745 * --------- |
746 * | chunk2 | -- eg: block_size = 2
747 * --------- | <- insert a chunk
748 * | chunk3 | -- eg: block_size = 3
749 * --------- |
750 * | chunk4 | -- eg: block_size = 4
751 * --------- |
752 * | chunk5 | -- eg: block_size = 5
753 * -------------- |
754 * NULL <-
755 * </pre>
756 */
757 else
758 {
759 chunk_head* node = m_active_pool[en_ap_larger_blocks_index];
760 if (NULL != node)
761 {
762 chunk_head* pre_node = node;
763 while(NULL != node && node->block_size < chunk->block_size)
764 {
765 pre_node = node;
766 node = node->next;
767 }
768 chunk->next = pre_node->next;
769 pre_node->next = chunk;
770 }
771 else
772 {
773 m_active_pool[en_ap_larger_blocks_index] = chunk;
774 chunk->next = NULL;
775 }
776 return en_ap_larger_blocks_index;
777 }
778 }
779
780 }
781 /* Allocates a free chunk from the free pool */
782 EXTL_BASIC_POOL_TEMPLATE_DECL
783 EXTL_BASIC_POOL_CLASS_RET_QUAL(chunk_head*)::alloc_chunk_from_free_pool(size_type chunk_size)
784 {
785 EXTL_ASSERT(sizeof(chunk_head) < chunk_size);
786 /*!<pre>
787 * index = chunk_size / 4K - 1
788 * [chunk size]
789 * 8K, 8K + 4K * 1, 8K + 4K * 2, ..., 8K + 4K * n
790 * [index]
791 * 1, 2, , 3, , ..., n + 1
792 * [Note]
793 * per-page size: 8K
794 * </pre>
795 */
796 size_type index = size_to_index(chunk_size);
797 EXTL_ASSERT((0 < index) && (index <= EXTL_LIMIT_TRAITS_UINT32_MAX));
798
799 /*!Finds a regular chunk
800 * <pre>
801 * [chunk size]
802 * 8K, 8K + 4K * 1, 8K + 4K * 2, ..., 8K + 4K * n
803 * -----> find
804 * </pre>
805 */
806 for(size_type i = index; i < en_fp_cur_max_index; i++)
807 {
808 /* Non-empty linked list */
809 if (NULL != m_free_pool[i])
810 {
811 chunk_head* node = m_free_pool[i];
812 m_free_pool[i] = m_free_pool[i]->next;
813 node->next = NULL;
814 EXTL_ASSERT(node->index == i);
815 return node;
816 }
817 }
818
819 /*!Finds a non-regular chunk
820 * <pre>
821 * index = en_fp_non_regular_index = 0
822 * [Note]
823 * The size of a non-regular chunk is larger than a regular chunk
824 * </pre>
825 */
826 chunk_head* node = m_free_pool[en_fp_non_regular_index];
827 if (NULL != node && index <= node->index) /* chunk_size <= node->chunk_size() */
828 {
829 m_free_pool[en_fp_non_regular_index] = node->next;
830 node->next = NULL;
831 EXTL_ASSERT(node->index == en_fp_non_regular_index);
832 return node;
833 }
834
835 /*!Allocates a new chunk
836 * if there is not a chunk of the appropriate size in the free pool
837 */
838 node = reinterpret_cast<chunk_head*>(allocator().allocate(chunk_size));
839 EXTL_ASSERT(NULL != node);
840 node->next = NULL;
841 node->index = index;
842
843 return node;
844 }
845 /* Initialize a free chunk */
846 EXTL_BASIC_POOL_TEMPLATE_DECL
847 inline void EXTL_BASIC_POOL_CLASS_QUAL::init_free_chunk(chunk_head* free_chunk, size_type block_size)
848 {
849 EXTL_ASSERT(NULL != free_chunk);
850 EXTL_ASSERT(block_size <= free_chunk->chunk_size());
851 EXTL_ASSERT(sizeof(block_head) <= block_size);
852
853 free_chunk->block_size = block_size;
854 free_chunk->free_count = free_chunk->block_count();
855 free_chunk->first_free = free_chunk->first_block();
856 free_chunk->last_free = free_chunk->last_block();
857 free_chunk->last_free->next = NULL;
858 free_chunk->disable_alloc_by_linked_list();
859 }
860 /* Allocates a free block from the partial-free chunk */
861 EXTL_BASIC_POOL_TEMPLATE_DECL
862 inline EXTL_BASIC_POOL_CLASS_RET_QUAL(block_head*)::alloc_block_from_free_chunk(chunk_head* free_chunk)
863 {
864 EXTL_ASSERT(NULL != free_chunk);
865 EXTL_ASSERT(NULL != free_chunk->first_free);
866 EXTL_ASSERT(0 < free_chunk->free_count);
867
868 block_head* block = free_chunk->first_free;
869
870 if (free_chunk->is_alloc_by_linked_list() || free_chunk->free_count <= 1)
871 {
872 /*!<pre>
873 * --------------
874 * | chunk_head |
875 * --------------
876 * | free_block1 |
877 * -------------- <- first_free
878 * | free_block2 | --
879 * -------------- |
880 * | free_block3 | |
881 * -------------- <- next_free
882 * | free_block4 |
883 * --------------
884 * NULL
885 * </pre>
886 */
887 free_chunk->first_free = free_chunk->first_free->next;
888 }
889 else
890 {
891 /*!Delay to segregate a chunk for optimization
892 *
893 * The chunk is not segregated until a block in the chunk is allocated
894 * and the chunk will be segregated completely when first_free is pointed to the last block,
895 * then the blocks in the chunk will be allocated by linked list
896 * <pre>
897 * --------------
898 * | chunk_head |
899 * --------------
900 * | free_block1 |
901 * -------------- <- first_free
902 * | free_block2 | + block_size
903 * -------------- <- next_free
904 * | free_block3 |
905 * --------------
906 * | free_block4 |
907 * -------------- <- first_free (complete to segregate)
908 * | free_block5 |
909 * --------------
910 * NULL
911 * </pre>
912 */
913 EXTL_ASSERT(1 < free_chunk->free_count);
914 free_chunk->first_free = reinterpret_cast<block_head*>
915 (reinterpret_cast<e_byte_t*>(free_chunk->first_free) + free_chunk->block_size);
916 if (free_chunk->first_free == free_chunk->last_block())
917 free_chunk->enable_alloc_by_linked_list();
918
919 };
920
921 if (NULL == free_chunk->first_free) free_chunk->last_free = NULL;
922
923 EXTL_ASSERT(free_chunk->free_count > 0);
924 --free_chunk->free_count;
925
926 return block;
927 }
928
929 /*!Deallocates the chunk to the pool
930 *
931 * <pre>
932 * active pool:
933 *
934 * index: 0 1 2 ... ...
935 * ------------- ------------- ------------- ------------- ------------- -------------
936 * ---->| | | | ... ... | |
937 * | ------------- ------------- ------------- ------------- ------------- -------------
938 * | |
939 * ap_index |---- -------------
940 * ap_index |---- | chunk1 |
941 * | -------------
942 * | |
943 * ap_index |---- -------------
944 * ap_index |---- | chunk2 |
945 * -------------
946 * |
947 * NULL
948 *
949 * </pre>
950 */
951 EXTL_BASIC_POOL_TEMPLATE_DECL
952 void EXTL_BASIC_POOL_CLASS_QUAL::deallocate(pointer p)
953 {
954 if (NULL == p) return ;
955 block_head* block = block_head::get_block(p);
956 EXTL_ASSERT(NULL != block);
957
958 size_type index = block->get_ap_index();
959 EXTL_ASSERT(index >= 0 && index < en_ap_max_index);
960
961 chunk_head* node = m_active_pool[index];
962 chunk_head* pre_node = node;
963
964 while(NULL != node)
965 {
966 if (node->is_in_chunk(block))
967 {
968 EXTL_ASSERT(((reinterpret_cast<e_byte_t*>(block) -
969 reinterpret_cast<e_byte_t*>(node) -
970 sizeof(chunk_head)) % node->block_size) == 0);
971
972 dealloc_block_to_chunk(block, node);
973
974 /*!Removes the chunk from the active pool
975 * and puts the chunk to the free pool if the chunk is free.
976 */
977 if (node->is_free())
978 {
979 /*!Removes the chunk from the active pool */
980 if (pre_node == node) m_active_pool[index] = node->next; /* Remove the head node */
981 else pre_node->next = node->next;
982
983 /*!Deallocates the chunk to the free pool */
984 dealloc_chunk_to_free_pool(node);
985 }
986 return ;
987 }
988 pre_node = node;
989 node = node->next;
990 }
991 }
992 /* Dealocates a allocated chunk to the free pool */
993 EXTL_BASIC_POOL_TEMPLATE_DECL
994 void EXTL_BASIC_POOL_CLASS_QUAL::dealloc_chunk_to_free_pool(chunk_head* chunk)
995 {
996 EXTL_ASSERT(NULL != chunk);
997 EXTL_ASSERT(chunk->is_free());
998
999 size_type index = chunk->index;
1000 EXTL_ASSERT((0 < index) && (index <= EXTL_LIMIT_TRAITS_UINT32_MAX));
1001
1002 /*!Frees the chunk to system if the size of the chunk is larger than index_to_size(en_fp_max_free_index).
1003 * Does't free the chunk until the pool is destroyed, if en_fp_max_free_index == en_fp_max_free_unlimited.
1004 */
1005 if ((index >= en_fp_max_free_index) &&
1006 (en_fp_max_free_index != EXTL_BASIC_POOL_DEFAULT_MAX_FREE_UNLIMITED))
1007 {
1008 allocator().deallocate(reinterpret_cast<e_byte_t*>(chunk));
1009 }
1010 /*!Frees the regular chunk to the free pool */
1011 else if (index < en_fp_cur_max_index)
1012 {
1013 EXTL_ASSERT(index != en_fp_non_regular_index);
1014 chunk->next = m_free_pool[index];
1015 m_free_pool[index] = chunk;
1016 }
1017 /*!Frees the non-regular chunk to the free pool
1018 * and the non-chunks in the free pool is sorted in descending order by the size of a chunk.
1019 * <pre>
1020 * m_free_pool[0] --
1021 * |
1022 * -------------- <-
1023 * | free_chunk1 | -- eg: size = 10
1024 * -------------- |
1025 * | free_chunk2 | -- eg: size = 8
1026 * -------------- | <- insert a non-regular chunk
1027 * | free_chunk3 | -- eg: size = 5
1028 * -------------- |
1029 * | free_chunk4 | -- eg: size = 3
1030 * -------------- |
1031 * | free_chunk5 | -- eg: size = 1
1032 * -------------- |
1033 * NULL <-
1034 * </pre>
1035 */
1036 else
1037 {
1038 chunk_head* node = m_free_pool[en_fp_non_regular_index];
1039
1040 if (NULL != node)
1041 {
1042 /* Finds the position where the chunk will be inserted */
1043 chunk_head* pre_node = node;
1044 while(NULL != node && node->index > index)
1045 {
1046 pre_node = node;
1047 node = node->next;
1048 }
1049 node = pre_node;
1050
1051 /* Inserts the chunk */
1052 chunk->next = node->next;
1053 node->next = chunk;
1054 }
1055 else
1056 {
1057 /* Inserts the chunk into the head of m_free_pool[en_fp_non_regular_index] */
1058 chunk->next = NULL;
1059 m_free_pool[en_fp_non_regular_index] = chunk;
1060 }
1061 }
1062 }
1063 /* Deallocates a block to the chunk */
1064 EXTL_BASIC_POOL_TEMPLATE_DECL
1065 inline void EXTL_BASIC_POOL_CLASS_QUAL::dealloc_block_to_chunk(block_head* block, chunk_head* chunk)
1066 {
1067 EXTL_ASSERT(NULL != chunk);
1068 EXTL_ASSERT(NULL != block);
1069 EXTL_ASSERT(chunk->is_in_chunk(block));
1070
1071 block->next = NULL;
1072
1073 if (NULL == chunk->last_free)
1074 {
1075 EXTL_ASSERT(NULL == chunk->first_free);
1076 chunk->last_free = block;
1077 chunk->first_free = block;
1078 }
1079 else
1080 {
1081 chunk->last_free->next = block;
1082 chunk->last_free = block;
1083 }
1084
1085 EXTL_ASSERT(chunk->free_count < chunk->block_count());
1086 ++chunk->free_count;
1087 }
1088
1089 /* Reallocates memory block of the specified size */
1090 EXTL_BASIC_POOL_TEMPLATE_DECL
1091 EXTL_BASIC_POOL_CLASS_RET_QUAL(pointer)::reallocate(pointer p, size_type size)
1092 {
1093 if (NULL == p) return NULL;
1094 block_head* block = block_head::get_block(p);
1095 EXTL_ASSERT(NULL != block);
1096
1097 size_type index = block->get_ap_index();
1098 EXTL_ASSERT(index >= 0 && index < en_ap_max_index);
1099
1100 chunk_head* node = m_active_pool[index];
1101 chunk_head* pre_node = node;
1102 while(NULL != node)
1103 {
1104 if (node->is_in_chunk(block))
1105 {
1106 if (size <= node->block_size - en_block_head_size)
1107 return p;
1108 else if (node->block_count() == 1 &&
1109 size <= node->data_size() - en_block_head_size)
1110 return p;
1111 else
1112 {
1113 /* Allocates a new block */
1114 pointer p = allocate(size);
1115
1116 EXTL_ASSERT(NULL != p);
1117 mem_copy(p, block->data(), node->block_size - en_block_head_size);
1118
1119 /* Deallocate the block */
1120 dealloc_block_to_chunk(block, node);
1121 if (node->is_free())
1122 {
1123 /* Removes the chunk from the active pool */
1124 if (pre_node == node) m_active_pool[index] = NULL;
1125 else pre_node->next = node->next;
1126
1127 /* Deallocates the chunk to the free pool */
1128 dealloc_chunk_to_free_pool(node);
1129 }
1130 return p;
1131 }
1132 }
1133 pre_node = node;
1134 node = node->next;
1135 }
1136
1137 return p;
1138 }
1139
1140 /* Creates a snapshot of the pool */
1141 EXTL_BASIC_POOL_TEMPLATE_DECL
1142 EXTL_BASIC_POOL_CLASS_RET_QUAL(snapshot_info)::get_snapshot() const
1143 {
1144 snapshot_info cur_snapshot_info;
1145 mem_fill_0(&cur_snapshot_info, sizeof(snapshot_info));
1146
1147 size_type index;
1148
1149 /* the snapshot info of the active pool */
1150 for(index = 0; index < en_ap_max_index; index++)
1151 {
1152 chunk_head* node = m_active_pool[index];
1153 while(NULL != node)
1154 {
1155 cur_snapshot_info.cur_alloc_size_from_system += node->chunk_size();
1156 cur_snapshot_info.cur_alloc_size_from_pool += node->block_size * (node->block_count() - node->free_count);
1157 node = node->next;
1158 }
1159 }
1160
1161 /* the snapshot info of the free pool */
1162 for(index = 0; index < en_fp_cur_max_index; index++)
1163 {
1164 chunk_head* node = m_free_pool[index];
1165 while(NULL != node)
1166 {
1167 cur_snapshot_info.cur_alloc_size_from_system += node->chunk_size();
1168 node = node->next;
1169 }
1170 }
1171
1172 return cur_snapshot_info;
1173 }
1174
1175 /* ///////////////////////////////////////////////////////////////////////
1176 * Undefine macros
1177 */
1178 #undef EXTL_BASIC_POOL_TEMPLATE_DECL
1179 #undef EXTL_BASIC_POOL_CLASS_QUAL
1180 #undef EXTL_BASIC_POOL_CLASS_RET_QUAL
1181
1182 /* ///////////////////////////////////////////////////////////////////////
1183 * some basic_pool type
1184 */
1185 /// default_basic_pool
1186 typedef basic_pool < basic_allocator_selector<e_byte_t>::allocator_type
1187 , EXTL_BASIC_POOL_DEFAULT_MAX_FREE_INDEX
1188 , EXTL_BASIC_POOL_DEFAULT_ALIGN_BOUNDARY_POWER
1189 > default_basic_pool;
1190 /// fast_basic_pool
1191 typedef basic_pool < basic_allocator_selector<e_byte_t>::allocator_type
1192 , EXTL_BASIC_POOL_DEFAULT_MAX_FREE_UNLIMITED
1193 , 4 /* Default alignment boundary: 16 = 2^4 */
1194 > fast_basic_pool;
1195 /// spare_basic_pool
1196 typedef basic_pool < basic_allocator_selector<e_byte_t>::allocator_type
1197 , 15 /* max_free_chunk_size = (15 + 1) * 4K = 64K */
1198 , 3 /* Default alignment boundary: 8 = 2^8 */
1199 > spare_basic_pool;
1200 /* ///////////////////////////////////////////////////////////////////////
1201 * Unit-testing
1202 */
1203 #ifdef EXTL_MEMORY_BASIC_POOL_TEST_ENABLE
1204 # include "unit_test/basic_pool_test.h"
1205 #endif
1206
1207 /* ///////////////////////////////////////////////////////////////////////
1208 * ::extl namespace
1209 */
1210 EXTL_END_NAMESPACE
1211
1212 /* //////////////////////////////////////////////////////////////////// */
1213 #endif /* EXTL_MEMORY_BASIC_POOL_H */
1214 /* //////////////////////////////////////////////////////////////////// */
a c++ generic library