pool.h

00001 ///\file
00002 
00003 /******************************************************************************
00004 The MIT License(MIT)
00005 
00006 Embedded Template Library.
00007 https://github.com/ETLCPP/etl
00008 http://www.etlcpp.com
00009 
00010 Copyright(c) 2014 jwellbelove
00011 
00012 Permission is hereby granted, free of charge, to any person obtaining a copy
00013 of this software and associated documentation files(the "Software"), to deal
00014 in the Software without restriction, including without limitation the rights
00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
00016 copies of the Software, and to permit persons to whom the Software is
00017 furnished to do so, subject to the following conditions :
00018 
00019 The above copyright notice and this permission notice shall be included in all
00020 copies or substantial portions of the Software.
00021 
00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
00028 SOFTWARE.
00029 ******************************************************************************/
00030 
00031 #ifndef __ETL_POOL__
00032 #define __ETL_POOL__
00033 
00034 #include "platform.h "
00035 #include "alignment.h "
00036 #include "array.h "
00037 #include "container.h "
00038 #include "integral_limits.h "
00039 #include "nullptr.h "
00040 #include "alignment.h "
00041 #include "error_handler.h "
00042 #include "static_assert.h"
00043 
00044 #include <iterator>
00045 #include <algorithm>
00046 
00047 #undef ETL_FILE
00048 #define ETL_FILE "11"
00049 
00050 //*****************************************************************************
00051 ///\defgroup pool pool
00052 /// A fixed capacity pool.
00053 ///\ingroup containers
00054 //*****************************************************************************
00055 
00056 namespace etl
00057 {
00058   //***************************************************************************
00059   /// The base class for pool exceptions.
00060   ///\ingroup pool
00061   //***************************************************************************
00062   class pool_exception : public exception
00063   {
00064   public:
00065 
00066     pool_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00067       : exception(reason_, file_name_, line_number_)
00068     {}
00069   };
00070 
00071   //***************************************************************************
00072   /// The exception thrown when the pool has no more free items.
00073   ///\ingroup pool
00074   //***************************************************************************
00075   class pool_no_allocation : public pool_exception
00076   {
00077   public:
00078 
00079     explicit pool_no_allocation(string_type file_name_, numeric_type line_number_)
00080       : pool_exception(ETL_ERROR_TEXT("pool:allocation", ETL_FILE"A"), file_name_, line_number_)
00081     {}
00082   };
00083 
00084   //***************************************************************************
00085   /// The exception thrown when an object is released which does not belong to the pool.
00086   ///\ingroup pool
00087   //***************************************************************************
00088   class pool_object_not_in_pool : public pool_exception
00089   {
00090   public:
00091 
00092     pool_object_not_in_pool(string_type file_name_, numeric_type line_number_)
00093       : pool_exception(ETL_ERROR_TEXT("pool:not in pool", ETL_FILE"B"), file_name_, line_number_)
00094     {}
00095   };
00096 
00097   //***************************************************************************
00098   /// The exception thrown when an the type requested is larger than the element size.
00099   ///\ingroup pool
00100   //***************************************************************************
00101   class pool_element_size : public pool_exception
00102   {
00103   public:
00104 
00105     pool_element_size(string_type file_name_, numeric_type line_number_)
00106       : pool_exception(ETL_ERROR_TEXT("pool:element size", ETL_FILE"C"), file_name_, line_number_)
00107     {}
00108   };
00109 
00110   //***************************************************************************
00111   ///\ingroup pool
00112   //***************************************************************************
00113   class ipool
00114   {
00115   public:
00116 
00117     typedef size_t size_type;
00118 
00119     //*************************************************************************
00120     /// Allocate an object from the pool.
00121     /// Uses the default constructor.
00122     /// If asserts or exceptions are enabled and there are no more free items an
00123     /// etl::pool_no_allocation if thrown, otherwise a nullptr is returned.
00124     //*************************************************************************
00125     template <typename T>
00126     T* allocate()
00127     {
00128       if (sizeof(T) > ITEM_SIZE)
00129       {
00130         ETL_ASSERT(false, ETL_ERROR(etl::pool_element_size));
00131       }
00132 
00133       return reinterpret_cast<T*>(allocate_item());
00134     }
00135 
00136     //*************************************************************************
00137     /// Release an object in the pool.
00138     /// If asserts or exceptions are enabled and the object does not belong to this
00139     /// pool then an etl::pool_object_not_in_pool is thrown.
00140     /// \param p_object A pointer to the object to be released.
00141     //*************************************************************************
00142     void release(const void* p_object)
00143     {
00144       release_item((char*)p_object);
00145     }
00146 
00147     //*************************************************************************
00148     /// Release all objects in the pool.
00149     //*************************************************************************
00150     void release_all()
00151     {
00152       items_allocated = 0;
00153       items_initialised = 0;
00154       p_next = p_buffer;
00155     }
00156 
00157     //*************************************************************************
00158     /// Check to see if the object belongs to the pool.
00159     /// \param p_object A pointer to the object to be checked.
00160     /// \return <b>true<\b> if it does, otherwise <b>false</b>
00161     //*************************************************************************
00162     //template <typename T>
00163     bool is_in_pool(const void* p_object) const
00164     {
00165       return is_item_in_pool((const char*)p_object);
00166     }
00167 
00168     //*************************************************************************
00169     /// Returns the maximum number of items in the pool.
00170     //*************************************************************************
00171     size_t max_size() const
00172     {
00173       return MAX_SIZE;
00174     }
00175 
00176     //*************************************************************************
00177     /// Returns the number of free items in the pool.
00178     //*************************************************************************
00179     size_t available() const
00180     {
00181       return MAX_SIZE - items_allocated;
00182     }
00183 
00184     //*************************************************************************
00185     /// Returns the number of allocated items in the pool.
00186     //*************************************************************************
00187     size_t size() const
00188     {
00189       return items_allocated;
00190     }
00191 
00192     //*************************************************************************
00193     /// Checks to see if there are no allocated items in the pool.
00194     /// \return <b>true</b> if there are none allocated.
00195     //*************************************************************************
00196     bool empty() const
00197     {
00198       return items_allocated == 0;
00199     }
00200 
00201     //*************************************************************************
00202     /// Checks to see if there are no free items in the pool.
00203     /// \return <b>true</b> if there are none free.
00204     //*************************************************************************
00205     bool full() const
00206     {
00207       return items_allocated == MAX_SIZE;
00208     }
00209 
00210   protected:
00211 
00212     //*************************************************************************
00213     /// Constructor
00214     //*************************************************************************
00215     ipool(char* p_buffer_, uint32_t item_size_, uint32_t max_size_)
00216       : p_buffer(p_buffer_),
00217         p_next(p_buffer_),
00218         items_allocated(0),
00219         items_initialised(0),
00220         ITEM_SIZE(item_size_),
00221         MAX_SIZE(max_size_)
00222     {
00223     }
00224 
00225   private:
00226 
00227     //*************************************************************************
00228     /// Allocate an item from the pool.
00229     //*************************************************************************
00230     char* allocate_item()
00231     {
00232       char* p_value = std::nullptr;
00233 
00234       // Any free space left?
00235       if (items_allocated < MAX_SIZE)
00236       {
00237         // Initialise another one if necessary.
00238         if (items_initialised < MAX_SIZE)
00239         {
00240           uintptr_t p = reinterpret_cast<uintptr_t>(p_buffer + (items_initialised * ITEM_SIZE));
00241           *reinterpret_cast<uintptr_t*>(p) = p + ITEM_SIZE;
00242           ++items_initialised;
00243         }
00244 
00245         // Get the address of new allocated item.
00246         p_value = p_next;
00247 
00248         ++items_allocated;
00249         if (items_allocated != MAX_SIZE)
00250         {
00251           // Set up the pointer to the next free item
00252           p_next = *reinterpret_cast<char**>(p_next);
00253         }
00254         else
00255         {
00256           // No more left!
00257           p_next = std::nullptr;
00258         }
00259       }
00260       else
00261       {
00262         ETL_ASSERT(false, ETL_ERROR(etl::pool_no_allocation));
00263       }
00264 
00265       return p_value;
00266     }
00267 
00268     //*************************************************************************
00269     /// Release an item back to the pool.
00270     //*************************************************************************
00271     void release_item(char* p_value)
00272     {
00273       // Does it belong to us?
00274       ETL_ASSERT(is_item_in_pool(p_value), ETL_ERROR(pool_object_not_in_pool));
00275 
00276       if (p_next != std::nullptr)
00277       {
00278         // Point it to the current free item.
00279         *(uintptr_t*)p_value = reinterpret_cast<uintptr_t>(p_next);
00280       }
00281       else
00282       {
00283         // This is the only free item.
00284         *((uintptr_t*)p_value) = 0;
00285       }
00286 
00287       p_next = p_value;
00288 
00289       --items_allocated;
00290     }
00291 
00292     //*************************************************************************
00293     /// Check if the item belongs to this pool.
00294     //*************************************************************************
00295     bool is_item_in_pool(const char* p) const
00296     {
00297       // Within the range of the buffer?
00298       intptr_t distance = p - p_buffer;
00299       bool is_within_range = (distance >= 0) && (distance <= intptr_t((ITEM_SIZE * MAX_SIZE) - ITEM_SIZE));
00300 
00301       // Modulus and division can be slow on some architectures, so only do this in debug.
00302 #if defined(ETL_DEBUG)
00303       // Is the address on a valid object boundary?
00304       bool is_valid_address = ((distance % ITEM_SIZE) == 0);
00305 #else
00306       bool is_valid_address = true;
00307 #endif
00308 
00309       return is_within_range && is_valid_address;
00310     }
00311 
00312     // Disable copy construction and assignment.
00313     ipool(const ipool&);
00314     ipool& operator =(const ipool&);
00315 
00316     char* p_buffer;
00317     char* p_next;
00318 
00319     uint32_t  items_allocated;   ///< The number of items allocated.
00320     uint32_t  items_initialised; ///< The number of items initialised.
00321 
00322     const uint32_t ITEM_SIZE;    ///< The size of allocated items.
00323     const uint32_t MAX_SIZE;    ///< The maximum number of objects that can be allocated.
00324   };
00325 
00326   //*************************************************************************
00327   /// A templated pool implementation that uses a fixed size pool.
00328   ///\ingroup pool
00329   //*************************************************************************
00330   template <typename T, const size_t SIZE_>
00331   class pool : public etl::ipool
00332   {
00333   public:
00334 
00335     static const size_t SIZE = SIZE_;
00336 
00337     //*************************************************************************
00338     /// Constructor
00339     //*************************************************************************
00340     pool()
00341       : etl::ipool(reinterpret_cast<char*>(&buffer[0]), ELEMENT_SIZE, SIZE)
00342     {
00343     }
00344 
00345     //*************************************************************************
00346     /// Allocate an object from the pool.
00347     /// Uses the default constructor.
00348     /// If asserts or exceptions are enabled and there are no more free items an
00349     /// etl::pool_no_allocation if thrown, otherwise a nullptr is returned.
00350     /// Static asserts if the specified type is too large for the pool.
00351     //*************************************************************************
00352     template <typename U>
00353     U* allocate()
00354     {
00355       STATIC_ASSERT(sizeof(U) <= ELEMENT_SIZE, "Type too large for pool");
00356       return ipool::allocate<U>();
00357     }
00358 
00359   private:
00360 
00361     // The pool element.
00362     union Element
00363     {
00364       uintptr_t next;             ///< Pointer to the next free element.
00365       char      value[sizeof(T)]; ///< Storage for value type.
00366       typename  etl::type_with_alignment<etl::alignment_of<T>::value>::type dummy; ///< Dummy item to get correct alignment.
00367     };
00368 
00369     ///< The memory for the pool of objects.
00370     typename etl::aligned_storage<sizeof(Element), etl::alignment_of<Element>::value>::type buffer[SIZE];
00371 
00372     static const uint32_t ELEMENT_SIZE = sizeof(Element);
00373 
00374     // Should not be copied.
00375     pool(const pool&);
00376     pool& operator =(const pool&);
00377   };
00378 
00379   //*************************************************************************
00380   /// A templated abstract pool implementation that uses a fixed size pool.
00381   ///\ingroup pool
00382   //*************************************************************************
00383   template <const size_t TYPE_SIZE_, const size_t ALIGNMENT_, const size_t SIZE_>
00384   class generic_pool : public etl::ipool
00385   {
00386   public:
00387 
00388     static const size_t SIZE      = SIZE_;
00389     static const size_t ALIGNMENT = ALIGNMENT_;
00390     static const size_t TYPE_SIZE = TYPE_SIZE_;
00391 
00392     //*************************************************************************
00393     /// Constructor
00394     //*************************************************************************
00395     generic_pool()
00396       : etl::ipool(reinterpret_cast<char*>(&buffer[0]), ELEMENT_SIZE, SIZE)
00397     {
00398     }
00399 
00400     //*************************************************************************
00401     /// Allocate an object from the pool.
00402     /// If asserts or exceptions are enabled and there are no more free items an
00403     /// etl::pool_no_allocation if thrown, otherwise a nullptr is returned.
00404     /// Static asserts if the specified type is too large for the pool.
00405     //*************************************************************************
00406     template <typename U>
00407     U* allocate()
00408     {
00409       STATIC_ASSERT(etl::alignment_of<U>::value <= ALIGNMENT_, "Type has incompatible alignment");
00410       STATIC_ASSERT(sizeof(U)  <= ELEMENT_SIZE, "Type too large for pool");
00411       return ipool::allocate<U>();
00412     }
00413 
00414   private:
00415 
00416     // The pool element.
00417     union Element
00418     {
00419       uintptr_t next;              ///< Pointer to the next free element.
00420       char      value[TYPE_SIZE_]; ///< Storage for value type.
00421       typename  etl::type_with_alignment<ALIGNMENT_>::type dummy; ///< Dummy item to get correct alignment.
00422     };
00423 
00424     ///< The memory for the pool of objects.
00425     typename etl::aligned_storage<sizeof(Element), etl::alignment_of<Element>::value>::type buffer[SIZE];
00426 
00427     static const uint32_t ELEMENT_SIZE = sizeof(Element);
00428 
00429     // Should not be copied.
00430     generic_pool(const generic_pool&);
00431     generic_pool& operator =(const generic_pool&);
00432   };
00433 }
00434 
00435 #undef ETL_FILE
00436 
00437 #endif
00438 
00439