• Skip to content
  • Skip to link menu
  • KDE API Reference
  • kdelibs-4.10.4 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 #include "kdebug.h"
32 #include <QList>
33 
34 class KZoneAllocator::MemBlock
35 {
36  public:
37  MemBlock(size_t s) : size(s), ref(0), older(0), newer(0)
38  { begin = new char[s]; }
39  ~MemBlock() { delete [] begin; }
40  bool is_in(void *ptr) const {return !(begin > (char *)ptr
41  || (begin + size) <= (char *)ptr); }
42  size_t size;
43  unsigned int ref;
44  char *begin;
45  MemBlock *older;
46  MemBlock *newer;
47 };
48 
49 class KZoneAllocator::Private
50 {
51 public:
52  Private()
53  : currentBlock(0), blockSize(1),
54  blockOffset(0), log2(0), num_blocks(0),
55  hashList(0), hashSize(0), hashDirty(true)
56  {
57  }
58 
60  MemBlock *currentBlock;
62  unsigned long blockSize;
64  unsigned long blockOffset;
66  unsigned int log2;
68  unsigned int num_blocks;
70  MemList **hashList;
72  unsigned int hashSize;
74  bool hashDirty;
75 };
76 
77 KZoneAllocator::KZoneAllocator(unsigned long _blockSize)
78  : d( new Private )
79 {
80  while (d->blockSize < _blockSize) {
81  d->blockSize <<= 1;
82  d->log2++;
83  }
84 
85  /* Make sure, that a block is allocated at the first time allocate()
86  is called (even with a 0 size). */
87  d->blockOffset = d->blockSize + 1;
88 }
89 
90 KZoneAllocator::~KZoneAllocator()
91 {
92  unsigned int count = 0;
93  if (d->hashList) {
94  /* No need to maintain the different lists in d->hashList[] anymore.
95  I.e. no need to use delBlock(). */
96  for (unsigned int i = 0; i < d->hashSize; i++)
97  delete d->hashList[i];
98  delete [] d->hashList;
99  d->hashList = 0;
100  }
101  MemBlock *next;
102  for (; d->currentBlock; d->currentBlock = next) {
103  next = d->currentBlock->older;
104  delete d->currentBlock;
105  count++;
106  }
107 #ifndef NDEBUG // as this is called quite late in the app, we don't care
108  // to use kDebug
109  if (count > 1)
110  qDebug("zone still contained %d blocks", count);
111 #endif
112  delete d;
113 }
114 
115 void KZoneAllocator::insertHash(MemBlock *b)
116 {
117  quintptr adr = ((quintptr)b->begin) & (~(d->blockSize - 1));
118  quintptr end = ((quintptr)b->begin) + d->blockSize;
119  while (adr < end) {
120  quintptr key = adr >> d->log2;
121  key = key & (d->hashSize - 1);
122  if (!d->hashList[key])
123  d->hashList[key] = new QList<MemBlock *>;
124  d->hashList[key]->append(b);
125  adr += d->blockSize;
126  }
127 }
128 
134 void KZoneAllocator::addBlock(MemBlock *b)
135 {
136  b->newer = 0;
137  b->older = d->currentBlock;
138  if (d->currentBlock)
139  b->older->newer = b;
140  d->currentBlock = b;
141  d->num_blocks++;
142  /* If we either have no d->hashList at all, or since it's last construction
143  there are now many more blocks we reconstruct the list. But don't
144  make it larger than a certain maximum. */
145  if (d->hashList && ((d->num_blocks / 4) > d->hashSize && d->hashSize < 64*1024))
146  d->hashDirty = true;
147  /* Only insert this block into the hashlists, if we aren't going to
148  reconstruct them anyway. */
149  if (d->hashList && !d->hashDirty)
150  insertHash (b);
151 }
152 
154 void KZoneAllocator::initHash()
155 {
156  if (d->hashList) {
157  for (unsigned int i = 0; i < d->hashSize; i++)
158  delete d->hashList[i];
159  delete [] d->hashList;
160  d->hashList = 0;
161  }
162  d->hashSize = 1;
163  while (d->hashSize < d->num_blocks)
164  d->hashSize <<= 1;
165  if (d->hashSize < 1024)
166  d->hashSize = 1024;
167  if (d->hashSize > 64*1024)
168  d->hashSize = 64*1024;
169  d->hashList = new QList<MemBlock *> *[d->hashSize];
170  memset (d->hashList, 0, sizeof(QList<MemBlock*> *) * d->hashSize);
171  d->hashDirty = false;
172  for (MemBlock *b = d->currentBlock; b; b = b->older)
173  insertHash(b);
174 }
175 
180 void KZoneAllocator::delBlock(MemBlock *b)
181 {
182  /* Update also the hashlists if we aren't going to reconstruct them
183  soon. */
184  if (d->hashList && !d->hashDirty) {
185  quintptr adr = (( quintptr )b->begin) & (~(d->blockSize - 1));
186  quintptr end = (( quintptr )b->begin) + d->blockSize;
187  while (adr < end) {
188  quintptr key = adr >> d->log2;
189  key = key & (d->hashSize - 1);
190  if (d->hashList[key]) {
191  QList<MemBlock *> *list = d->hashList[key];
192  QList<MemBlock *>::Iterator it = list->begin();
193  QList<MemBlock *>::Iterator endit = list->end();
194  for (; it != endit; ++it)
195  if (*it == b) {
196  list->erase(it);
197  break;
198  }
199  }
200  adr += d->blockSize;
201  }
202  }
203  if (b->older)
204  b->older->newer = b->newer;
205  if (b->newer)
206  b->newer->older = b->older;
207  if (b == d->currentBlock) {
208  d->currentBlock = 0;
209  d->blockOffset = d->blockSize;
210  }
211  delete b;
212  d->num_blocks--;
213 }
214 
215 void *
216 KZoneAllocator::allocate(size_t _size)
217 {
218  // Use the size of (void *) as alignment
219  const size_t alignment = sizeof(void *) - 1;
220  _size = (_size + alignment) & ~alignment;
221 
222  if ((unsigned long) _size + d->blockOffset > d->blockSize)
223  {
224  if (_size > d->blockSize) {
225  qDebug("KZoneAllocator: allocating more than %lu bytes", d->blockSize);
226  return 0;
227  }
228  addBlock(new MemBlock(d->blockSize));
229  d->blockOffset = 0;
230  //qDebug ("Allocating block #%d (%x)\n", d->num_blocks, d->currentBlock->begin);
231  }
232  void *result = (void *)(d->currentBlock->begin+d->blockOffset);
233  d->currentBlock->ref++;
234  d->blockOffset += _size;
235  return result;
236 }
237 
238 void
239 KZoneAllocator::deallocate(void *ptr)
240 {
241  if (d->hashDirty)
242  initHash();
243 
244  quintptr key = (((quintptr)ptr) >> d->log2) & (d->hashSize - 1);
245  const QList<MemBlock *> *list = d->hashList[key];
246  if (!list) {
247  /* Can happen with certain usage pattern of intermixed free_since()
248  and deallocate(). */
249  //qDebug("Uhoh");
250  return;
251  }
252  QList<MemBlock*>::ConstIterator it = list->begin();
253  QList<MemBlock*>::ConstIterator endit = list->end();
254  for (; it != endit; ++it) {
255  MemBlock *cur = *it;
256  if (cur->is_in(ptr)) {
257  if (!--cur->ref) {
258  if (cur != d->currentBlock)
259  delBlock (cur);
260  else
261  d->blockOffset = 0;
262  }
263  return;
264  }
265  }
266  /* Can happen with certain usage pattern of intermixed free_since()
267  and deallocate(). */
268  //qDebug("Uhoh2");
269 }
270 
271 void
272 KZoneAllocator::free_since(void *ptr)
273 {
274  /* If we have a d->hashList and it's not yet dirty, see, if we will dirty
275  it by removing too many blocks. This will make the below delBlock()s
276  faster. */
277  if (d->hashList && !d->hashDirty)
278  {
279  const MemBlock *b;
280  unsigned int removed = 0;
281  for (b = d->currentBlock; b; b = b->older, removed++)
282  if (b->is_in (ptr))
283  break;
284  if (d->hashSize >= 4 * (d->num_blocks - removed))
285  d->hashDirty = true;
286  }
287  while (d->currentBlock && !d->currentBlock->is_in(ptr)) {
288  d->currentBlock = d->currentBlock->older;
289  delBlock (d->currentBlock->newer);
290  }
291  d->blockOffset = ((char*)ptr) - d->currentBlock->begin;
292 }
This file is part of the KDE documentation.
Documentation copyright © 1996-2013 The KDE developers.
Generated on Wed Jun 5 2013 18:35:20 by doxygen 1.8.3.1 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.10.4 API Reference

Skip menu "kdelibs-4.10.4 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