PLearn 0.1
ArrayAllocator.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 //
00003 // ArrayAllocator.h
00004 //
00005 // Copyright (C) 2000 Nicolas Chapados
00006 // 
00007 // Redistribution and use in source and binary forms, with or without
00008 //  modification, are permitted provided that the following conditions are met:
00009 // 
00010 //    1. Redistributions of source code must retain the above copyright
00011 //       notice, this list of conditions and the following disclaimer.
00012 //     
00013 //    2. Redistributions in binary form must reproduce the above copyright
00014 //       notice, this list of conditions and the following disclaimer in the
00015 //       documentation and/or other materials provided with the distribution.
00016 //       
00017 //    3. The name of the authors may not be used to endorse or promote
00018 //       products derived from this software without specific prior written
00019 //      permission. 
00020 // 
00021 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00022 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00023 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00024 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00025 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00026 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00027 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00028 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00029 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00030 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00031 //
00032 // This file is part of the PLearn library. For more information on the PLearn
00033 // library, go to the PLearn Web site at www.plearn.org
00034 
00035 /* *******************************************************
00036  * * $Id: ArrayAllocator.h 3994 2005-08-25 13:35:03Z chapados $
00037  * ******************************************************* */
00038 
00039 #ifndef ARRAYALLOCATOR_H
00040 #define ARRAYALLOCATOR_H
00041 
00042 
00043 #include <vector>
00044 #include <algorithm>   
00045 #include "general.h"
00046 #include "ArrayAllocatorIndex.h"
00047 
00048 namespace PLearn {
00049 using namespace std;
00050 
00051 
00052 
00053 //######################  CLASS  ARRAYALLOCATOROPTIONS  #######################
00060 template <class T, class Enclosing>
00061 class Option
00062 {
00063 public:
00064     typedef T value_type;
00065     typedef Enclosing enclosing_type;
00066     
00067 public:
00068     Option(const T& defaultValue, Enclosing* encl)
00069         : optionValue(defaultValue), enclosing(encl)
00070     {}
00071 
00072     Enclosing& operator()(const T& newValue) {
00073         optionValue = newValue;
00074         return *enclosing;
00075     }
00076     const T& operator()() const {
00077         return optionValue;
00078     }
00079     
00080 private:
00081     T optionValue;
00082     Enclosing* enclosing;
00083 };
00084 
00085 
00086 class ArrayAllocatorOptions
00087 {
00088     typedef ArrayAllocatorOptions self;
00089     
00090 public:
00092     ArrayAllocatorOptions()
00093         : numObjs(100,this),
00094           deallocatorType(DeallocatorUnsorted,this)
00095     { }
00096     
00098     Option<size_t, self> numObjs;
00099 
00101     enum DeallocatorType {
00102         DeallocatorNull = 0,
00103         DeallocatorUnsorted = 1,
00104         DeallocatorSorted = 2
00105     };
00106     Option<DeallocatorType, self> deallocatorType;
00107 };
00108 
00109 
00110 
00111 //##########################  CLASS  ARRAYALLOCATOR  ##########################
00136 template <class T, unsigned SizeBits>
00137 class ArrayAllocator
00138 {
00139 public:
00140     typedef ArrayAllocator<T,SizeBits> self_type;
00141     typedef T value_type;
00142     typedef unsigned index_base;
00143     typedef ArrayAllocatorIndex<index_base, SizeBits> index_type;
00144     typedef size_t size_type;
00145     typedef ptrdiff_t difference_type;
00146 
00147     typedef T* pointer;
00148     typedef const T* const_pointer;
00149     typedef T& reference;
00150     typedef const T& const_reference;
00151 
00152 public:
00153     ArrayAllocator(const ArrayAllocatorOptions&);
00155 
00157     pointer allocate(size_t n);
00158 
00160     void deallocate(pointer p, size_type n);
00161     void deallocate(index_type);
00162 
00163     void resize(size_type NewMaxObjs);
00164     size_type max_size() const {
00165         return arr.size();
00166     }
00167     
00168 public:
00170     inline index_type toIndex(pointer p, size_type n);
00171     inline pointer toPointer(index_type);
00172     
00173 public:
00174     void swap(self_type&);
00175     
00176 private:
00178     index_type& derefIndex(index_type i) {
00179         return (index_type&)arr[i.index];
00180     }
00181     index_type& derefIndex(unsigned i) {
00182         return (index_type&)arr[i];
00183     }
00184     
00185 private:
00186     vector<T> arr;
00187     index_type free_root;
00188     ArrayAllocatorOptions options;
00189 };
00190 
00191 
00192 
00193 //#####  Implementation  ######################################################
00194 
00195 template <class T, unsigned SizeBits>
00196 ArrayAllocator<T,SizeBits>::ArrayAllocator(const ArrayAllocatorOptions& opt)
00197     : arr(0), free_root(0,0), options(opt)
00198 {
00199     resize(options.numObjs());
00200 }
00201 
00202 
00203 template <class T, unsigned SizeBits>
00204 void ArrayAllocator<T,SizeBits>::resize(size_type new_max_objs)
00205 {
00212     size_t next_free_block = arr.size();
00213     if (new_max_objs <= next_free_block)
00214         return;
00215 
00217     next_free_block = max(1,int(next_free_block));
00218 
00219     arr.resize(new_max_objs);
00220     index_type dummy(unsigned(-1), unsigned(-1));
00221     size_t max_block_size = dummy.size;
00222     
00223     while (next_free_block < new_max_objs) {
00224         size_t block_size = min(max_block_size, new_max_objs - next_free_block);
00225 
00226         index_type new_index(free_root.index, block_size);
00227         derefIndex(next_free_block) = new_index;
00228         free_root = index_type(next_free_block,0);
00229 
00230         next_free_block += block_size;
00231     }
00232 }
00233 
00234 
00235 template <class T, unsigned SizeBits>
00236 ArrayAllocator<T,SizeBits>::pointer
00237 ArrayAllocator<T,SizeBits>::allocate(size_t n)
00238 {
00239     index_type *free_pointer = &free_root;
00240 
00245     while (free_pointer && !free_pointer->isNull()) {
00246         unsigned size = derefIndex(*free_pointer).size;
00247 
00248         if (size < n)
00249             free_pointer = &derefIndex(*free_pointer);
00250         else
00251             if (size == n) {
00252                 pointer p = toPointer(*free_pointer);
00253                 *free_pointer = index_type(derefIndex(*free_pointer).index,
00254                                            free_pointer->size);
00255                 return p;
00256             }
00257             else {
00258                 pointer p = toPointer(*free_pointer);
00259                 derefIndex(free_pointer->index + n) =
00260                     index_type(derefIndex(*free_pointer).index, size - n);
00261                 *free_pointer = index_type(free_pointer->index + n,
00262                                            free_pointer->size);
00263                 return p;
00264             }
00265     }
00266     PLERROR("Could not allocate; size of memory pool exhausted\n%s\n",
00267             (typeid(*this).name()));
00268     return 0;                                
00269 }
00270 
00271 
00272 template <class T, unsigned SizeBits>
00273 void ArrayAllocator<T,SizeBits>::deallocate(pointer p, size_type n)
00274 {
00275     deallocate(index_type(p,n));
00276 }
00277 
00278 
00279 template <class T, unsigned SizeBits>
00280 void ArrayAllocator<T,SizeBits>::deallocate(index_type i)
00281 {
00283     switch(options.deallocatorType()) {
00284     case ArrayAllocatorOptions::DeallocatorNull :
00286         break;
00287 
00288     case ArrayAllocatorOptions::DeallocatorUnsorted :
00291         if (! i.isNull()) {
00292             derefIndex(i) = index_type(free_root.index, i.size);
00293             free_root.index = i.index;
00294         }
00295         break;
00296 
00297     case ArrayAllocatorOptions::DeallocatorSorted :
00299         PLERROR("ArrayAllocator: the sorted deallocator is not currently "
00300                 "implemented");
00301         break;
00302     }
00303 }
00304 
00305 
00306 template <class T, unsigned SizeBits>
00307 inline ArrayAllocator<T,SizeBits>::index_type
00308 ArrayAllocator<T,SizeBits>::toIndex(pointer p, size_type n)
00309 {
00310     if (p)
00311         return index_type(p-&arr[0], n);
00312     else
00313         return index_type(0,0);
00314 }
00315 
00316 
00317 template <class T, unsigned SizeBits>
00318 inline ArrayAllocator<T,SizeBits>::pointer
00319 ArrayAllocator<T,SizeBits>::toPointer(index_type i)
00320 {
00321     if (i.isNull())
00322         return 0;
00323     else
00324         return &arr[0] + i.index;
00325 }
00326 
00327 
00328 template <class T, unsigned SizeBits>
00329 void ArrayAllocator<T,SizeBits>::swap(self_type& other)
00330 {
00331     swap(arr, other.arr);
00332     swap(free_root, other.free_root);
00333 }
00334 
00335 } // end of namespace PLearn
00336 
00337 
00338 #endif
00339 
00340 
00341 /*
00342   Local Variables:
00343   mode:c++
00344   c-basic-offset:4
00345   c-file-style:"stroustrup"
00346   c-file-offsets:((innamespace . 0)(inline-open . 0))
00347   indent-tabs-mode:nil
00348   fill-column:79
00349   End:
00350 */
00351 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines