extl/memory/fixed_pool.h

   1 /* ///////////////////////////////////////////////////////////////////////
   2  * File:                fixed_pool.h
   3  *
   4  * Created:             08.04.14
   5  * Updated:             08.05.01
   6  *
   7  * Brief: fixed_pool class - allocate a fixed-size memory block every once
   8  *
   9  * [<Home>]
  10  * Copyright (c) 2008-2020, Waruqi All rights reserved.
  11  * //////////////////////////////////////////////////////////////////// */
  12
  13 #ifndef EXTL_MEMORY_FIXED_POOL_H
  14 #define EXTL_MEMORY_FIXED_POOL_H
  15
  16 /*!\file fixed_pool.h
  17  * \brief fixed_pool class - allocate a fixed-size memory block every once
  18  *
  19  * Note: The size of a block must be less than 8K
  20  *
  21  */
  22 #ifndef __cplusplus
  23 #       error fixed_pool.h need be supported by c++.
  24 #endif
  25
  26 /* ///////////////////////////////////////////////////////////////////////
  27  * Includes
  28  */
  29 #include "allocator_selector.h"
  30 #include "../utility/suppress_unused.h"
  31
  32 #ifdef EXTL_MEMORY_FIXED_POOL_TEST_ENABLE
  33 #       include "../counter/clock_counter.h"
  34 #endif
  35
  36 /* ///////////////////////////////////////////////////////////////////////
  37  * Macros
  38  */
  39 /// Slightly less than 8K so that a chunk in the basic_pool will fit in 8K
  40 #define EXTL_FIXED_POOL_DEFAULT_CHUNK_SIZE      (8 * 1024 - 64)
  41 /* ///////////////////////////////////////////////////////////////////////
  42  * ::extl namespace
  43  */
  44 EXTL_BEGIN_NAMESPACE
  45
  46 /*!\brief fixed_pool class
  47  *
  48  * \param BLOCK_SIZE The size of the fixed memory block
  49  * \param CHUNK_SIZE The size of a chunk
  50  * \param A The allocator type
  51  *
  52  * [Structure]
  53  *
  54  *               --------------------      --------------------
  55  * m_chunks ---> |      chunk1      | ---> |      chunk2      | ---> NULL
  56  *               --------------------      --------------------
  57  *                       ¡ý
  58  *                                          -------------------------------
  59  * one chunk: m_first_free --> |    block1    -|->   block2   -|-> NULL
  60  *                              -------------------------------
  61  *
  62  * \ingroup extl_group_memory
  63  */
  64 template<       e_size_t BLOCK_SIZE
  65 #ifdef EXTL_TEMPLATE_CLASS_DEFAULT_ARGUMENT_SUPPORT
  66                 ,       e_size_t CHUNK_SIZE = EXTL_FIXED_POOL_DEFAULT_CHUNK_SIZE
  67                 ,       typename_param_k A = typename_type_def_k allocator_selector<e_byte_t>::allocator_type
  68 #else
  69                 ,       e_size_t CHUNK_SIZE
  70                 ,       typename_param_k A
  71 #endif
  72                 >
  73 class fixed_pool
  74 #ifdef EXTL_EBO_FORM_2_SUPPORT
  75         : protected A   /* if EBO is supported */
  76 #endif
  77 {
  78         private:
  79                 typedef A                                                                                                       base_type;
  80         /// \name Types
  81         /// @{
  82         public:
  83                 typedef fixed_pool<BLOCK_SIZE, CHUNK_SIZE, A>                           class_type;
  84                 typedef void                                                                                            value_type;
  85                 typedef A                                                                                                       allocator_type;
  86                 typedef void*                                                                                           pointer;
  87                 typedef void const*                                                                                     const_pointer;
  88                 typedef void                                                                                            reference;
  89                 typedef void                                                                                            const_reference;
  90                 typedef typename_type_k allocator_type::size_type                       size_type;
  91         /// @}
  92
  93         private:
  94
  95                 /// The node of the block_head
  96                 struct block_head{ block_head* next; };
  97                 /// The node of the chunk_head
  98                 struct chunk_head
  99                 {
 100                         /* BCC Bug: Can not use BLOCK_SIZE directly when BLOCK_SIZE = sizeof(object) */
 101                         enum{en_raw_block_size = BLOCK_SIZE};
 102
 103                         /* The size of one block is sizeof(block_head) at least */
 104                 #if EXTL_WORKAROUND_BORLAND(==, 0x564)
 105                         enum { en_block_size =
 106                                         BLOCK_SIZE < sizeof(block_head)? sizeof(block_head) : BLOCK_SIZE };
 107                 #else
 108                         enum { en_block_size =
 109                                         en_raw_block_size < sizeof(block_head)? sizeof(block_head) : en_raw_block_size };
 110                 #endif
 111
 112                         enum { en_data_size = CHUNK_SIZE };
 113                         enum { en_block_count = en_data_size / en_block_size };
 114
 115                         chunk_head* next;
 116                         e_byte_t data[en_data_size];
 117                         block_head* first_block()       { return reinterpret_cast<block_head*>(&data[0]);                                                                               }
 118                         block_head* last_block()        { return reinterpret_cast<block_head*>(data + (en_block_count - 1) * en_block_size);    }
 119
 120                 };
 121                 friend struct chunk_head;
 122
 123                 enum {en_data_size = chunk_head::en_data_size};
 124                 enum {en_block_size = chunk_head::en_block_size};
 125
 126         /// \name Members
 127         /// @{
 128         private:
 129                 chunk_head*                             m_chunks;                                       //!< The head of the linked list of the whole storage
 130                 block_head*                             m_first_free;                           //!< The first free block of the free linked list
 131                 block_head*                             m_last_free;                            //!< The last free block of the free linked list
 132                 chunk_head*                             m_free_chunk;
 133         /// @}
 134
 135         private:
 136                 /*!\brief Prohibit copying and assignment
 137                  *
 138                  * Maybe EBO is not supported if uses extl::uncopyable,
 139                  * because some compilers do not support EBO_FORM_6 - EXTL_EBO_FORM_6_SUPPORT
 140                  */
 141                 fixed_pool(class_type const&);
 142                 class_type& operator=(class_type const&);
 143
 144         /// \name Constructors
 145         /// @{
 146         public:
 147                 fixed_pool()
 148                         : m_chunks(NULL)
 149                         , m_first_free(NULL)
 150                         , m_last_free(NULL)
 151                         , m_free_chunk(NULL)
 152                 {
 153
 154                 }
 155                 virtual ~fixed_pool()
 156                 {
 157                         destroy();
 158                 }
 159         /// @}
 160
 161         public:
 162                 /// Destroys the pool
 163                 void destroy()
 164                 {
 165                         EXTL_ASSERT(is_valid());
 166                         /* Releases the memory of the fixed pool */
 167                         chunk_head* node = m_chunks;
 168                         while(NULL != node)
 169                         {
 170                                 chunk_head* p = node;
 171                                 node = node->next;
 172                                 allocator().deallocate(reinterpret_cast<e_byte_t*>(p), 0);
 173                         }
 174                         m_chunks = NULL;
 175                         m_first_free = NULL;
 176                         m_last_free = NULL;
 177                         m_free_chunk = NULL;
 178
 179                         EXTL_ASSERT(is_valid());
 180                 }
 181
 182         public:
 183                 /// Gets the allocator of the pool
 184                 allocator_type allocator() const
 185                 {
 186                 #ifdef EXTL_EBO_FORM_2_SUPPORT
 187                         return *this;
 188                 #else
 189                         return allocator_type();
 190                 #endif
 191                 }
 192                 /// Allocates a fixed-size memory block
 193                 pointer allocate(size_type n = 1)
 194                 {
 195                         EXTL_SUPPRESS_UNUSED(n);
 196                         EXTL_ASSERT(1 == n);
 197                         EXTL_ASSERT(is_valid());
 198
 199                 #ifdef EXTL_COMPILER_IS_GCC
 200                         EXTL_STATIC_ASSERT(size_type(en_block_size) <= size_type(en_data_size));
 201                 #else
 202                         EXTL_STATIC_ASSERT(en_block_size <= en_data_size);
 203                 #endif
 204
 205                         if (NULL == m_first_free) grow();
 206                         return alloc_block_from_pool();
 207                 }
 208
 209                 /// Only puts the fixed back into the pool
 210                 void deallocate(pointer block)
 211                 {
 212                         dealloc_block_to_pool(block);
 213                 }
 214         private:
 215                 /// Grows the size of the pool
 216                 void grow()
 217                 {
 218                         EXTL_ASSERT(is_valid());
 219                         EXTL_ASSERT(NULL == m_last_free);
 220                         EXTL_ASSERT(NULL == m_first_free);
 221                         /* Adds a new chunk into the pool
 222                          *  -----------     ----------
 223                          * | new_chunk | - |  chunk1  | - ... ...
 224                          *  -----------     ----------
 225                          */
 226                         chunk_head* new_chunk = reinterpret_cast<chunk_head*>(allocator().allocate(sizeof(chunk_head), NULL));
 227                         EXTL_ASSERT(NULL != new_chunk);
 228                         new_chunk->next = m_chunks;
 229                         m_chunks = new_chunk;
 230
 231                         /* The new chunk
 232                          *  -----------------------------------------
 233                          * | block | block |  ....  |        |       |
 234                          *  -----------------------------------------
 235                          *     |                                 |
 236                          * first_free                        last_free
 237                          */
 238                         m_first_free = new_chunk->first_block();
 239                         m_last_free = new_chunk->last_block();
 240                         m_last_free->next = NULL;
 241
 242                         /* The current free chunk */
 243                         m_free_chunk = new_chunk;
 244                         EXTL_ASSERT(is_valid());
 245                 }
 246
 247                 /// Allocates a free block from the pool
 248                 pointer alloc_block_from_pool()
 249                 {
 250                         EXTL_ASSERT(is_valid());
 251                         EXTL_ASSERT(NULL != m_first_free);
 252                         pointer p = static_cast<pointer>(m_first_free);
 253
 254                         /* Allocates a free block by linked list if m_free_chunk is NULL
 255                          * --------------
 256                          * |  free_block1 |
 257                          *  --------------  <- first_free
 258                          * |  free_block2 | --
 259                          *  --------------    |
 260                          * |  free_block3 |   |
 261                          *  --------------  <- next_free
 262                          * |  free_block4 |
 263                          *  --------------
 264                          *       NULL
 265                          */
 266                         if (NULL == m_free_chunk || 1 == chunk_head::en_block_count)
 267                         {
 268                                 m_first_free = m_first_free->next;
 269                         }
 270                         /* Delay to segregate a chunk for optimization
 271                          * The chunk is not segregated until a block in the chunk is allocated
 272                          * and the chunk will be segregated completely when first_free is pointed to the last block,
 273                          * then the blocks in the chunk will be allocated by linked list
 274                          *  --------------
 275                          * |  free_block1 |
 276                          *  --------------  <- first_free
 277                          * |  free_block2 |                +  block_size
 278                          *  --------------  <- next_free
 279                          * |  free_block3 |
 280                          *  --------------
 281                          * |  free_block4 |
 282                          *  --------------  <- first_free (complete to segregate)
 283                          * |  free_block5 |
 284                          *  --------------
 285                          *       NULL
 286                          */
 287                         else
 288                         {
 289                                 m_first_free = reinterpret_cast<block_head*>
 290                                         (reinterpret_cast<e_byte_t*>(m_first_free) + chunk_head::en_block_size);
 291
 292                                 if (m_first_free == m_free_chunk->last_block())
 293                                 {
 294                                         m_free_chunk = NULL;
 295                                 }
 296                         }
 297
 298                         /* There are not more free block after allocating a block from the chunk */
 299                         if (NULL == m_first_free)
 300                                 m_last_free = NULL;
 301
 302                         EXTL_ASSERT(is_valid());
 303                         return p;
 304                 }
 305                 /// Deallocates a block to the pool
 306                 void dealloc_block_to_pool(pointer block)
 307                 {
 308                         EXTL_ASSERT(is_valid());
 309
 310                         block_head* p = static_cast<block_head*>(block);
 311                         p->next = NULL;
 312
 313                         if (NULL == m_last_free)
 314                         {
 315                                 EXTL_ASSERT(NULL == m_first_free);
 316                                 m_last_free = p;
 317                                 m_first_free = p;
 318                         }
 319                         else
 320                         {
 321                                 m_last_free->next = p;
 322                                 m_last_free = p;
 323                         }
 324
 325                         EXTL_ASSERT(is_valid());
 326                 }
 327
 328
 329         private:
 330                 e_bool_t is_valid() const
 331                 {
 332                         if ((NULL == m_first_free) != (NULL == m_last_free))
 333                                 return e_false_v;
 334
 335                         return e_true_v;
 336                 }
 337 };
 338 /* ///////////////////////////////////////////////////////////////////////
 339  * Unit-testing
 340  */
 341 #ifdef EXTL_MEMORY_FIXED_POOL_TEST_ENABLE
 342 #       include "unit_test/fixed_pool_test.h"
 343 #endif
 344
 345 /* ///////////////////////////////////////////////////////////////////////
 346  * ::extl namespace
 347  */
 348 EXTL_END_NAMESPACE
 349
 350 /* //////////////////////////////////////////////////////////////////// */
 351 #endif /* EXTL_MEMORY_FIXED_POOL_H */
 352 /* //////////////////////////////////////////////////////////////////// */