- Main Page
- Modules
- Namespaces
- Data Structures
- Files
- Examples

- File List
- Globals

# bmalloc.h

Go to the documentation of this file.

    00001 #ifndef BMALLOC__H__INCLUDED__
    00002 #define BMALLOC__H__INCLUDED__
    00003 /*
    00004 Copyright(c) 2002-2009 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
    00005
    00006 Permission is hereby granted, free of charge, to any person
    00007 obtaining a copy of this software and associated documentation
    00008 files (the "Software"), to deal in the Software without restriction,
    00009 including without limitation the rights to use, copy, modify, merge,
    00010 publish, distribute, sublicense, and/or sell copies of the Software,
    00011 and to permit persons to whom the Software is furnished to do so,
    00012 subject to the following conditions:
    00013
    00014 The above copyright notice and this permission notice shall be included
    00015 in all copies or substantial portions of the Software.
    00016
    00017 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
    00018 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
    00019 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
    00020 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
    00021 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
    00022 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
    00023 OTHER DEALINGS IN THE SOFTWARE.
    00024
    00025 For more information please visit:  http://bmagic.sourceforge.net
    00026
    00027 */
    00028
    00029 #include <stdlib.h>
    00030 #include <new>
    00031
    00032 namespace bm
    00033 {
    00034
    00035
    00036 /*! @defgroup alloc Memory Allocation
    00037  *  Memory allocation related units
    00038  *  @ingroup bmagic
    00039  *
    00040  *  @{
    00041  */
    00042
    00043 /*!
    00044   @brief Default malloc based bitblock allocator class.
    00045
    00046   Functions allocate and deallocate conform to STL allocator specs.
    00047   @ingroup alloc
    00048 */
    00049 class block_allocator
    00050 {
    00051 public:
    00052     /**
    00053     The member function allocates storage for an array of n bm::word_t
    00054     elements, by calling malloc.
    00055     @return pointer to the allocated memory.
    00056     */
    00057     static bm::word_t* allocate(size_t n, const void *)
    00058     {
    00059         bm::word_t* ptr;
    00060 #if defined(BMSSE2OPT) || defined(BMSSE42OPT)
    00061 # ifdef _MSC_VER
    00062         ptr = (bm::word_t*) ::_aligned_malloc(n * sizeof(bm::word_t), 16);
    00063 #else
    00064         ptr = (bm::word_t*) ::_mm_malloc(n * sizeof(bm::word_t), 16);
    00065 # endif
    00066
    00067 #else
    00068         ptr = (bm::word_t*) ::malloc(n * sizeof(bm::word_t));
    00069 #endif
    00070         if (!ptr)
    00071         {
    00072             throw std::bad_alloc();
    00073         }
    00074         return ptr;
    00075     }
    00076
    00077     /**
    00078     The member function frees storage for an array of n bm::word_t
    00079     elements, by calling free.
    00080     */
    00081     static void deallocate(bm::word_t* p, size_t)
    00082     {
    00083 #if defined(BMSSE2OPT) || defined(BMSSE42OPT)
    00084 # ifdef _MSC_VER
    00085         ::_aligned_free(p);
    00086 #else
    00087         ::_mm_free(p);
    00088 # endif
    00089
    00090 #else
    00091         ::free(p);
    00092 #endif
    00093     }
    00094
    00095 };
    00096
    00097
    00098 // -------------------------------------------------------------------------
    00099
    00100 /*! @brief Default malloc based bitblock allocator class.
    00101
    00102   Functions allocate and deallocate conform to STL allocator specs.
    00103 */
    00104 class ptr_allocator
    00105 {
    00106 public:
    00107     /**
    00108     The member function allocates storage for an array of n void*
    00109     elements, by calling malloc.
    00110     @return pointer to the allocated memory.
    00111     */
    00112     static void* allocate(size_t n, const void *)
    00113     {
    00114         void* ptr = ::malloc(n * sizeof(void*));
    00115         if (!ptr)
    00116         {
    00117             throw std::bad_alloc();
    00118         }
    00119         return ptr;
    00120     }
    00121
    00122     /**
    00123     The member function frees storage for an array of n bm::word_t
    00124     elements, by calling free.
    00125     */
    00126     static void deallocate(void* p, size_t)
    00127     {
    00128         ::free(p);
    00129     }
    00130 };
    00131
    00132 // -------------------------------------------------------------------------
    00133
    00134 /*! @brief BM style allocator adapter.
    00135
    00136   Template takes two parameters BA - allocator object for bit blocks and
    00137   PA - allocator object for pointer blocks.
    00138 */
    00139 template<class BA, class PA> class mem_alloc
    00140 {
    00141 public:
    00142     typedef BA  block_allocator_type;
    00143     typedef PA  ptr_allocator_type;
    00144
    00145 public:
    00146
    00147     mem_alloc(const BA& block_alloc = BA(), const PA& ptr_alloc = PA())
    00148     : block_alloc_(block_alloc),
    00149       ptr_alloc_(ptr_alloc)
    00150     {}
    00151
    00152     /*! @brief Returns copy of the block allocator object
    00153     */
    00154     block_allocator_type get_block_allocator() const
    00155     {
    00156         return BA(block_alloc_);
    00157     }
    00158
    00159     /*! @brief Returns copy of the ptr allocator object
    00160     */
    00161     ptr_allocator_type get_ptr_allocator() const
    00162     {
    00163        return PA(block_alloc_);
    00164     }
    00165
    00166
    00167     /*! @brief Allocates and returns bit block.
    00168         @param alloc_factor
    00169             indicated how many blocks we want to allocate in chunk
    00170             total allocation is going to be bm::set_block_size * alloc_factor
    00171             Default allocation factor is 1
    00172     */
    00173     bm::word_t* alloc_bit_block(unsigned alloc_factor = 1)
    00174     {
    00175         return block_alloc_.allocate(bm::set_block_size * alloc_factor, 0);
    00176     }
    00177
    00178     /*! @brief Frees bit block allocated by alloc_bit_block.
    00179     */
    00180     void free_bit_block(bm::word_t* block, unsigned alloc_factor = 1)
    00181     {
    00182         if (IS_VALID_ADDR(block))
    00183             block_alloc_.deallocate(block, bm::set_block_size * alloc_factor);
    00184     }
    00185
    00186     /*! @brief Allocates GAP block using bit block allocator (BA).
    00187
    00188         GAP blocks in BM library belong to levels. Each level has a
    00189         correspondent length described in bm::gap_len_table<>.
    00190
    00191         @param level GAP block level.
    00192     */
    00193     bm::gap_word_t* alloc_gap_block(unsigned level,
    00194                                     const gap_word_t* glevel_len)
    00195     {
    00196         BM_ASSERT(level < bm::gap_levels);
    00197         unsigned len =
    00198             glevel_len[level] / (sizeof(bm::word_t) / sizeof(gap_word_t));
    00199
    00200         return (bm::gap_word_t*)block_alloc_.allocate(len, 0);
    00201     }
    00202
    00203     /*! @brief Frees GAP block using bot block allocator (BA)
    00204     */
    00205     void free_gap_block(bm::gap_word_t*   block,
    00206                         const gap_word_t* glevel_len)
    00207     {
    00208         BM_ASSERT(IS_VALID_ADDR((bm::word_t*)block));
    00209
    00210         unsigned len = gap_capacity(block, glevel_len);
    00211         len /= sizeof(bm::word_t) / sizeof(bm::gap_word_t);
    00212         block_alloc_.deallocate((bm::word_t*)block, len);
    00213     }
    00214
    00215     /*! @brief Allocates block of pointers.
    00216     */
    00217     void* alloc_ptr(unsigned size = bm::set_array_size)
    00218     {
    00219         return ptr_alloc_.allocate(size, 0);
    00220     }
    00221
    00222     /*! @brief Frees block of pointers.
    00223     */
    00224     void free_ptr(void* p, unsigned size = bm::set_array_size)
    00225     {
    00226         if (p)
    00227             ptr_alloc_.deallocate(p, size);
    00228     }
    00229 private:
    00230     BA            block_alloc_;
    00231     PA            ptr_alloc_;
    00232 };
    00233
    00234 typedef mem_alloc<block_allocator, ptr_allocator> standard_allocator;
    00235
    00236 /** @} */
    00237
    00238
    00239 } // namespace bm
    00240
    00241
    00242 #endif