Copy the KDE 3.5 branch to branches/trinity for new KDE 3.5 features.

BUG:215923


git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/kdelibs@1054174 283d02a7-25f6-0310-bc7c-ecb5cbfe19da

1 files changed, 140 insertions, 0 deletions

diff --git a/kdecore/kallocator.h b/kdecore/kallocator.h
new file mode 100644
index 000000000..755926c81
--- /dev/null
+++ b/kdecore/kallocator.h
@@ -0,0 +1,140 @@
+/*
+    This file is part of the KDE libraries
+
+    Copyright (C) 1999 Waldo Bastian (bastian@kde.org)
+    Copyright (C) 2002 Michael Matz (matz@kde.org)
+              
+    This library is free software; you can redistribute it and/or
+    modify it under the terms of the GNU Library General Public
+    License as published by the Free Software Foundation; either
+    version 2 of the License, or (at your option) any later version.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Library General Public License for more details.
+
+    You should have received a copy of the GNU Library General Public License
+    along with this library; see the file COPYING.LIB.  If not, write to
+    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+    Boston, MA 02110-1301, USA.
+*/
+//----------------------------------------------------------------------------
+//
+// KDE Memory Allocator
+
+#ifndef KALLOCATOR_H
+#define KALLOCATOR_H
+
+#include <qvaluelist.h>
+#include "kdelibs_export.h"
+
+class KZoneAllocatorPrivate;
+
+
+/**
+ * Memory allocator for large groups of small objects.
+ * This should be used for large groups of objects that are created and
+ * destroyed together. When used carefully for this purpose it is faster
+ * and more memory efficient than malloc.  Additionally to a usual obstack
+ * like allocator you can also free the objects individually.  Because it
+ * does no compaction it still is faster then malloc()/free().  Depending
+ * on the exact usage pattern that might come at the expense of some
+ * memory though.
+ * @author Waldo Bastian <bastian@kde.org>, Michael Matz <matz@kde.org>
+ */
+class KDECORE_EXPORT KZoneAllocator
+{
+public:
+    /**
+     * Creates a KZoneAllocator object.
+     * @param _blockSize Size in bytes of the blocks requested from malloc.
+     */
+    KZoneAllocator(unsigned long _blockSize = 8*1024);
+
+    /**
+     * Destructs the ZoneAllocator and free all memory allocated by it.
+     */
+    ~KZoneAllocator();
+
+    /**
+     * Allocates a memory block.
+     * @param _size Size in bytes of the memory block. Memory is aligned to
+     * the size of a pointer.
+     */
+    void* allocate(size_t _size);
+
+    /**
+     * Gives back a block returned by allocate() to the zone
+     * allocator, and possibly deallocates the block holding it (when it's
+     * empty).  The first deallocate() after many allocate() calls
+     * (or the first at all) builds an internal data structure for speeding
+     * up deallocation.  The consistency of that structure is maintained
+     * from then on (by allocate() and deallocate()) unless many
+     * more objects are allocated without any intervening deallocation, in
+     * which case it's thrown away and rebuilt at the next deallocate().
+     *
+     * The effect of this is, that such initial deallocate() calls take
+     * more time then the normal calls, and that after this list is built, i.e.
+     * generally if deallocate() is used at all, also allocate() is a
+     * little bit slower.  This means, that if you want to squeeze out the last
+     * bit performance you would want to use KZoneAllocator as an obstack, i.e.
+     * just use the functions allocate() and free_since().  All the
+     * remaining memory is returned to the system if the zone allocator
+     * is destroyed.
+     * @param ptr Pointer as returned by allocate().
+     */
+    void deallocate(void *ptr);
+
+    /**
+     * Deallocate many objects at once.
+     * free_since() deallocates all objects allocated after @p ptr, 
+     * @em including @p ptr itself.
+     *
+     * The intended use is something along the lines of:
+     * \code
+     * KZoneAllocator alloc(8192);
+     * void *remember_me = alloc.allocate(0);
+     * for (int i = 0; i < 1000; i++)
+     *   do_something_with (alloc.allocate(12));
+     * alloc.free_since (remember_me);
+     * \endcode
+     * Note, that we don't need to remember all the pointers to the 12-byte
+     * objects for freeing them.  The free_since() does deallocate them
+     * all at once.
+     * @param ptr Pointer as returned by allocate().  It acts like
+     * a kind of mark of a certain position in the stack of all objects,
+     * off which you can throw away everything above that mark.
+     */
+    void free_since(void *ptr);
+
+protected:
+    /** A single chunk of memory from the heap. @internal */
+    class MemBlock;
+    /**< A list of chunks. @internal */
+    typedef QValueList<MemBlock *> MemList;
+    void addBlock(MemBlock *b);
+    void delBlock(MemBlock *b);
+    void insertHash(MemBlock *b);
+    void initHash();
+    /** One block is 'current' to satisfy requests. @internal */
+    MemBlock *currentBlock; 
+    /** Store block size from constructor. @internal */
+    unsigned long blockSize; 
+    /** Store offset into current block; size-offset is free. @internal */
+    unsigned long blockOffset;
+    /** base-2 log of the block size. @internal */
+    unsigned int log2;
+    /** Count total number of allocated blocks. @internal */
+    unsigned int num_blocks;
+    /** Collection of lists of blocks, for lookups. @internal */
+    MemList **hashList;
+    /** Count of hashes. @internal */
+    unsigned int hashSize;
+    /** Flag the hashes as in need of reorganization. @internal */
+    bool hashDirty;
+private:
+    KZoneAllocatorPrivate *d;
+};
+
+#endif