kdecore/util/kallocator.h

   1 /*
   2     This file is part of the KDE libraries
   3
   4     Copyright (C) 1999 Waldo Bastian (bastian@kde.org)
   5     Copyright (C) 2002 Michael Matz (matz@kde.org)
   6
   7     This library is free software; you can redistribute it and/or
   8     modify it under the terms of the GNU Library General Public
   9     License as published by the Free Software Foundation; either
  10     version 2 of the License, or (at your option) any later version.
  11
  12     This library is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15     Library General Public License for more details.
  16
  17     You should have received a copy of the GNU Library General Public License
  18     along with this library; see the file COPYING.LIB.  If not, write to
  19     the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  20     Boston, MA 02110-1301, USA.
  21 */
  22 //----------------------------------------------------------------------------
  23 //
  24 // KDE Memory Allocator
  25
  26 #ifndef KALLOCATOR_H
  27 #define KALLOCATOR_H
  28
  29 #include <kdecore_export.h>
  30
  31 template <typename T> class QList;
  32
  33
  34 /**
  35  * \class KZoneAllocator kallocator.h <KZoneAllocator>
  36  *
  37  * Memory allocator for large groups of small objects.
  38  * This should be used for large groups of objects that are created and
  39  * destroyed together. When used carefully for this purpose it is faster
  40  * and more memory efficient than malloc.  Additionally to a usual obstack
  41  * like allocator you can also free the objects individually.  Because it
  42  * does no compaction it still is faster than malloc()/free().  Depending
  43  * on the exact usage pattern that might come at the expense of some
  44  * memory though.
  45  * @author Waldo Bastian <bastian@kde.org>, Michael Matz <matz@kde.org>
  46  */
  47 class KDECORE_EXPORT KZoneAllocator
  48 {
  49 public:
  50     /**
  51      * Creates a KZoneAllocator object.
  52      * @param _blockSize Size in bytes of the blocks requested from malloc.
  53      */
  54     explicit KZoneAllocator(unsigned long _blockSize = 8*1024);
  55
  56     /**
  57      * Destructs the ZoneAllocator and free all memory allocated by it.
  58      */
  59     ~KZoneAllocator();
  60
  61     /**
  62      * Allocates a memory block.
  63      * @param _size Size in bytes of the memory block. Memory is aligned to
  64      * the size of a pointer.
  65      */
  66     void* allocate(size_t _size);
  67
  68     /**
  69      * Gives back a block returned by allocate() to the zone
  70      * allocator, and possibly deallocates the block holding it (when it's
  71      * empty).  The first deallocate() after many allocate() calls
  72      * (or the first at all) builds an internal data structure for speeding
  73      * up deallocation.  The consistency of that structure is maintained
  74      * from then on (by allocate() and deallocate()) unless many
  75      * more objects are allocated without any intervening deallocation, in
  76      * which case it's thrown away and rebuilt at the next deallocate().
  77      *
  78      * The effect of this is, that such initial deallocate() calls take
  79      * more time then the normal calls, and that after this list is built, i.e.
  80      * generally if deallocate() is used at all, also allocate() is a
  81      * little bit slower.  This means, that if you want to squeeze out the last
  82      * bit performance you would want to use KZoneAllocator as an obstack, i.e.
  83      * just use the functions allocate() and free_since().  All the
  84      * remaining memory is returned to the system if the zone allocator
  85      * is destroyed.
  86      * @param ptr Pointer as returned by allocate().
  87      */
  88     void deallocate(void *ptr);
  89
  90     /**
  91      * Deallocate many objects at once.
  92      * free_since() deallocates all objects allocated after @p ptr,
  93      * @em including @p ptr itself.
  94      *
  95      * The intended use is something along the lines of:
  96      * \code
  97      * KZoneAllocator alloc(8192);
  98      * void *remember_me = alloc.allocate(0);
  99      * for (int i = 0; i < 1000; i++)
 100      *   do_something_with (alloc.allocate(12));
 101      * alloc.free_since (remember_me);
 102      * \endcode
 103      * Note, that we don't need to remember all the pointers to the 12-byte
 104      * objects for freeing them.  The free_since() does deallocate them
 105      * all at once.
 106      * @param ptr Pointer as returned by allocate().  It acts like
 107      * a kind of mark of a certain position in the stack of all objects,
 108      * off which you can throw away everything above that mark.
 109      */
 110     void free_since(void *ptr);
 111
 112 protected:
 113     /** A single chunk of memory from the heap. @internal */
 114     class MemBlock;
 115     /**< A list of chunks. @internal */
 116     typedef QList<MemBlock *> MemList;
 117     void addBlock(MemBlock *b);
 118     void delBlock(MemBlock *b);
 119     void insertHash(MemBlock *b);
 120     void initHash();
 121 private:
 122     class Private;
 123     Private * const d;
 124 };
 125
 126 #endif