xpcom/ds/nsFixedSizeAllocator.h

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is mozilla.org code.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Netscape Communications Corporation.
  19  * Portions created by the Initial Developer are Copyright (C) 1998
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *   Chris Waterson <waterson@netscape.com
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either of the GNU General Public License Version 2 or later (the "GPL"),
  27  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 /*
  40
  41   A simple fixed-size allocator that allocates its memory from an
  42   arena.
  43
  44   Although the allocator can handle blocks of any size, its
  45   preformance will degrade rapidly if used to allocate blocks of
  46   arbitrary size. Ideally, it should be used to allocate and recycle a
  47   large number of fixed-size blocks.
  48
  49   Here is a typical usage pattern:
  50
  51     #include NEW_H // You'll need this!
  52     #include "nsFixedSizeAllocator.h"
  53
  54     // Say this is the object you want to allocate a ton of
  55     class Foo {
  56     public:
  57       // Implement placement new & delete operators that will
  58       // use the fixed size allocator.
  59       static Foo *
  60       Create(nsFixedSizeAllocator &aAllocator)
  61       {
  62         void *place = aAllocator.Alloc(sizeof(Foo));
  63         return place ? ::new (place) Foo() : nsnull;
  64       }
  65
  66       static void
  67       Destroy(nsFixedSizeAllocator &aAllocator, Foo *aFoo)
  68       {
  69         aFoo->~Foo();
  70         aAllocator.Free(aFoo, sizeof(Foo));
  71       }
  72
  73       // ctor & dtor
  74       Foo() {}
  75       ~Foo() {}
  76     };
  77
  78
  79     int main(int argc, char* argv[])
  80     {
  81       // Somewhere in your code, you'll need to create an
  82       // nsFixedSizeAllocator object and initialize it:
  83       nsFixedSizeAllocator pool;
  84
  85       // The fixed size allocator will support multiple fixed sizes.
  86       // This array lists an initial set of sizes that the allocator
  87       // should be prepared to support. In our case, there's just one,
  88       // which is Foo.
  89       static const size_t kBucketSizes[]
  90         = { sizeof(Foo) }
  91
  92       // This is the number of different "buckets" you'll need for
  93       // fixed size objects. In our example, this will be "1".
  94       static const PRInt32 kNumBuckets
  95         = sizeof(kBucketSizes) / sizeof(size_t);
  96
  97       // This is the intial size of the allocator, in bytes. We'll
  98       // assume that we want to start with space for 1024 Foo objects.
  99       static const PRInt32 kInitialPoolSize =
 100         NS_SIZE_IN_HEAP(sizeof(Foo)) * 1024;
 101
 102       // Initialize (or re-initialize) the pool
 103       pool.Init("TheFooPool", kBucketSizes, kNumBuckets, kInitialPoolSize);
 104
 105       // Now we can use the pool.
 106
 107       // Create a new Foo object using the pool:
 108       Foo* foo = Foo::Create(pool);
 109       if (! foo) {
 110         // uh oh, out of memory!
 111       }
 112
 113       // Delete the object. The memory used by `foo' is recycled in
 114       // the pool, and placed in a freelist
 115       Foo::Destroy(foo);
 116
 117       // Create another foo: this one will be allocated from the
 118       // free-list
 119       foo = Foo::Create(pool);
 120
 121       // When pool is destroyed, all of its memory is automatically
 122       // freed. N.B. it will *not* call your objects' destructors! In
 123       // this case, foo's ~Foo() method would never be called.
 124     }
 125
 126 */
 127
 128 #ifndef nsFixedSizeAllocator_h__
 129 #define nsFixedSizeAllocator_h__
 130
 131 #include "nscore.h"
 132 #include "nsError.h"
 133 #include "plarena.h"
 134
 135 #define NS_SIZE_IN_HEAP(_size) (_size)
 136
 137 class NS_COM nsFixedSizeAllocator
 138 {
 139 protected:
 140     PLArenaPool mPool;
 141
 142     struct Bucket;
 143     struct FreeEntry;
 144
 145     friend struct Bucket;
 146     friend struct FreeEntry;
 147
 148     struct FreeEntry {
 149         FreeEntry* mNext;
 150     };
 151
 152     struct Bucket {
 153         size_t     mSize;
 154         FreeEntry* mFirst;
 155         Bucket*    mNext;
 156     };
 157
 158     Bucket* mBuckets;
 159
 160     Bucket *
 161     AddBucket(size_t aSize);
 162
 163     Bucket *
 164     FindBucket(size_t aSize);
 165
 166 public:
 167     nsFixedSizeAllocator() : mBuckets(nsnull) {}
 168
 169     ~nsFixedSizeAllocator() {
 170         if (mBuckets)
 171             PL_FinishArenaPool(&mPool);
 172     }
 173
 174     /**
 175      * Initialize the fixed size allocator. 'aName' is used to tag
 176      * the underlying PLArena object for debugging and measurement
 177      * purposes. 'aNumBuckets' specifies the number of elements in
 178      * 'aBucketSizes', which is an array of integral block sizes
 179      * that this allocator should be prepared to handle.
 180      */
 181     nsresult
 182     Init(const char* aName,
 183          const size_t* aBucketSizes,
 184          PRInt32 aNumBuckets,
 185          PRInt32 aInitialSize,
 186          PRInt32 aAlign = 0);
 187
 188     /**
 189      * Allocate a block of memory 'aSize' bytes big.
 190      */
 191     void* Alloc(size_t aSize);
 192
 193     /**
 194      * Free a pointer allocated using a fixed-size allocator
 195      */
 196     void Free(void* aPtr, size_t aSize);
 197 };
 198
 199
 200
 201 #endif // nsFixedSizeAllocator_h__