• Skip to content
  • Skip to link menu
  • KDE API Reference
  • kdelibs-4.14.38 API Reference
  • KDE Home
  • Contact Us
 

KDECore

  • kdecore
  • util
kallocator.cpp
Go to the documentation of this file.
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/* Fast zone memory allocator with deallocation support, for use as obstack
24 or as general purpose allocator. It does no compaction. If the usage
25 pattern is non-optimal it might waste some memory while running. E.g.
26 allocating many small things at once, and then deallocating only every
27 second one, there is a high chance, that actually no memory is freed.
28 */
29
30#include "kallocator.h"
31
32#include <QList>
33
34#include <stdio.h>
35
36class KZoneAllocator::MemBlock
37{
38 public:
39 MemBlock(size_t s) : size(s), ref(0), older(0), newer(0)
40 { begin = new char[s]; }
41 ~MemBlock() { delete [] begin; }
42 bool is_in(void *ptr) const {return !(begin > (char *)ptr
43 || (begin + size) <= (char *)ptr); }
44 size_t size;
45 unsigned int ref;
46 char *begin;
47 MemBlock *older;
48 MemBlock *newer;
49};
50
51class KZoneAllocator::Private
52{
53public:
54 Private()
55 : currentBlock(0), blockSize(1),
56 blockOffset(0), log2(0), num_blocks(0),
57 hashList(0), hashSize(0), hashDirty(true)
58 {
59 }
60
62 MemBlock *currentBlock;
64 unsigned long blockSize;
66 unsigned long blockOffset;
68 unsigned int log2;
70 unsigned int num_blocks;
72 MemList **hashList;
74 unsigned int hashSize;
76 bool hashDirty;
77};
78
79KZoneAllocator::KZoneAllocator(unsigned long _blockSize)
80 : d( new Private )
81{
82 while (d->blockSize < _blockSize) {
83 d->blockSize <<= 1;
84 d->log2++;
85 }
86
87 /* Make sure, that a block is allocated at the first time allocate()
88 is called (even with a 0 size). */
89 d->blockOffset = d->blockSize + 1;
90}
91
92KZoneAllocator::~KZoneAllocator()
93{
94 unsigned int count = 0;
95 if (d->hashList) {
96 /* No need to maintain the different lists in d->hashList[] anymore.
97 I.e. no need to use delBlock(). */
98 for (unsigned int i = 0; i < d->hashSize; i++)
99 delete d->hashList[i];
100 delete [] d->hashList;
101 d->hashList = 0;
102 }
103 MemBlock *next;
104 for (; d->currentBlock; d->currentBlock = next) {
105 next = d->currentBlock->older;
106 delete d->currentBlock;
107 count++;
108 }
109#ifndef NDEBUG // as this is called quite late in the app, we don't care
110 // to use qDebug
111 if (count > 1)
112 fprintf(stderr, "zone still contained %d blocks", count);
113#endif
114 delete d;
115}
116
117void KZoneAllocator::insertHash(MemBlock *b)
118{
119 quintptr adr = ((quintptr)b->begin) & (~(d->blockSize - 1));
120 quintptr end = ((quintptr)b->begin) + d->blockSize;
121 while (adr < end) {
122 quintptr key = adr >> d->log2;
123 key = key & (d->hashSize - 1);
124 if (!d->hashList[key])
125 d->hashList[key] = new QList<MemBlock *>;
126 d->hashList[key]->append(b);
127 adr += d->blockSize;
128 }
129}
130
136void KZoneAllocator::addBlock(MemBlock *b)
137{
138 b->newer = 0;
139 b->older = d->currentBlock;
140 if (d->currentBlock)
141 b->older->newer = b;
142 d->currentBlock = b;
143 d->num_blocks++;
144 /* If we either have no d->hashList at all, or since it's last construction
145 there are now many more blocks we reconstruct the list. But don't
146 make it larger than a certain maximum. */
147 if (d->hashList && ((d->num_blocks / 4) > d->hashSize && d->hashSize < 64*1024))
148 d->hashDirty = true;
149 /* Only insert this block into the hashlists, if we aren't going to
150 reconstruct them anyway. */
151 if (d->hashList && !d->hashDirty)
152 insertHash (b);
153}
154
156void KZoneAllocator::initHash()
157{
158 if (d->hashList) {
159 for (unsigned int i = 0; i < d->hashSize; i++)
160 delete d->hashList[i];
161 delete [] d->hashList;
162 d->hashList = 0;
163 }
164 d->hashSize = 1;
165 while (d->hashSize < d->num_blocks)
166 d->hashSize <<= 1;
167 if (d->hashSize < 1024)
168 d->hashSize = 1024;
169 if (d->hashSize > 64*1024)
170 d->hashSize = 64*1024;
171 d->hashList = new QList<MemBlock *> *[d->hashSize];
172 memset (d->hashList, 0, sizeof(QList<MemBlock*> *) * d->hashSize);
173 d->hashDirty = false;
174 for (MemBlock *b = d->currentBlock; b; b = b->older)
175 insertHash(b);
176}
177
182void KZoneAllocator::delBlock(MemBlock *b)
183{
184 /* Update also the hashlists if we aren't going to reconstruct them
185 soon. */
186 if (d->hashList && !d->hashDirty) {
187 quintptr adr = (( quintptr )b->begin) & (~(d->blockSize - 1));
188 quintptr end = (( quintptr )b->begin) + d->blockSize;
189 while (adr < end) {
190 quintptr key = adr >> d->log2;
191 key = key & (d->hashSize - 1);
192 if (d->hashList[key]) {
193 QList<MemBlock *> *list = d->hashList[key];
194 QList<MemBlock *>::Iterator it = list->begin();
195 QList<MemBlock *>::Iterator endit = list->end();
196 for (; it != endit; ++it)
197 if (*it == b) {
198 list->erase(it);
199 break;
200 }
201 }
202 adr += d->blockSize;
203 }
204 }
205 if (b->older)
206 b->older->newer = b->newer;
207 if (b->newer)
208 b->newer->older = b->older;
209 if (b == d->currentBlock) {
210 d->currentBlock = 0;
211 d->blockOffset = d->blockSize;
212 }
213 delete b;
214 d->num_blocks--;
215}
216
217void *
218KZoneAllocator::allocate(size_t _size)
219{
220 // Use the size of (void *) as alignment
221 const size_t alignment = sizeof(void *) - 1;
222 _size = (_size + alignment) & ~alignment;
223
224 if ((unsigned long) _size + d->blockOffset > d->blockSize)
225 {
226 if (_size > d->blockSize) {
227 qDebug("KZoneAllocator: allocating more than %lu bytes", d->blockSize);
228 return 0;
229 }
230 addBlock(new MemBlock(d->blockSize));
231 d->blockOffset = 0;
232 //qDebug ("Allocating block #%d (%x)\n", d->num_blocks, d->currentBlock->begin);
233 }
234 void *result = (void *)(d->currentBlock->begin+d->blockOffset);
235 d->currentBlock->ref++;
236 d->blockOffset += _size;
237 return result;
238}
239
240void
241KZoneAllocator::deallocate(void *ptr)
242{
243 if (d->hashDirty)
244 initHash();
245
246 quintptr key = (((quintptr)ptr) >> d->log2) & (d->hashSize - 1);
247 const QList<MemBlock *> *list = d->hashList[key];
248 if (!list) {
249 /* Can happen with certain usage pattern of intermixed free_since()
250 and deallocate(). */
251 //qDebug("Uhoh");
252 return;
253 }
254 QList<MemBlock*>::ConstIterator it = list->begin();
255 QList<MemBlock*>::ConstIterator endit = list->end();
256 for (; it != endit; ++it) {
257 MemBlock *cur = *it;
258 if (cur->is_in(ptr)) {
259 if (!--cur->ref) {
260 if (cur != d->currentBlock)
261 delBlock (cur);
262 else
263 d->blockOffset = 0;
264 }
265 return;
266 }
267 }
268 /* Can happen with certain usage pattern of intermixed free_since()
269 and deallocate(). */
270 //qDebug("Uhoh2");
271}
272
273void
274KZoneAllocator::free_since(void *ptr)
275{
276 /* If we have a d->hashList and it's not yet dirty, see, if we will dirty
277 it by removing too many blocks. This will make the below delBlock()s
278 faster. */
279 if (d->hashList && !d->hashDirty)
280 {
281 const MemBlock *b;
282 unsigned int removed = 0;
283 for (b = d->currentBlock; b; b = b->older, removed++)
284 if (b->is_in (ptr))
285 break;
286 if (d->hashSize >= 4 * (d->num_blocks - removed))
287 d->hashDirty = true;
288 }
289 while (d->currentBlock && !d->currentBlock->is_in(ptr)) {
290 d->currentBlock = d->currentBlock->older;
291 delBlock (d->currentBlock->newer);
292 }
293 d->blockOffset = ((char*)ptr) - d->currentBlock->begin;
294}
KZoneAllocator::MemList
QList< MemBlock * > MemList
A list of chunks.
Definition: kallocator.h:116
KZoneAllocator::free_since
void free_since(void *ptr)
Deallocate many objects at once.
Definition: kallocator.cpp:274
KZoneAllocator::initHash
void initHash()
Reinitialize hash list.
Definition: kallocator.cpp:156
KZoneAllocator::delBlock
void delBlock(MemBlock *b)
Delete a memory block.
Definition: kallocator.cpp:182
KZoneAllocator::KZoneAllocator
KZoneAllocator(unsigned long _blockSize=8 *1024)
Creates a KZoneAllocator object.
Definition: kallocator.cpp:79
KZoneAllocator::insertHash
void insertHash(MemBlock *b)
Definition: kallocator.cpp:117
KZoneAllocator::allocate
void * allocate(size_t _size)
Allocates a memory block.
Definition: kallocator.cpp:218
KZoneAllocator::addBlock
void addBlock(MemBlock *b)
Add a new memory block to the pool of blocks, and reorganize the hash lists if needed.
Definition: kallocator.cpp:136
KZoneAllocator::~KZoneAllocator
~KZoneAllocator()
Destructs the ZoneAllocator and free all memory allocated by it.
Definition: kallocator.cpp:92
KZoneAllocator::deallocate
void deallocate(void *ptr)
Gives back a block returned by allocate() to the zone allocator, and possibly deallocates the block h...
Definition: kallocator.cpp:241
QList
Definition: kaboutdata.h:33
kallocator.h
KGlobal::ref
void ref()
Tells KGlobal about one more operations that should be finished before the application exits.
Definition: kglobal.cpp:321
This file is part of the KDE documentation.
Documentation copyright © 1996-2023 The KDE developers.
Generated on Mon Feb 20 2023 00:00:00 by doxygen 1.9.6 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.

KDECore

Skip menu "KDECore"
  • Main Page
  • Namespace List
  • Namespace Members
  • Alphabetical List
  • Class List
  • Class Hierarchy
  • Class Members
  • File List
  • File Members
  • Modules
  • Related Pages

kdelibs-4.14.38 API Reference

Skip menu "kdelibs-4.14.38 API Reference"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDEWebKit
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • KPty
  • Kross
  • KUnitConversion
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Report problems with this website to our bug tracking system.
Contact the specific authors with questions and comments about the page contents.

KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal