1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
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
|
