• Skip to content
  • Skip to link menu
Trinity API Reference
  • Trinity API Reference
  • tdecore
 

tdecore

  • tdecore
kallocator.cpp
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 // $Id$
29 
30 #include "kallocator.h"
31 #include <kdebug.h>
32 
33 class TDEZoneAllocator::MemBlock
34 {
35  public:
36  MemBlock(size_t s) : size(s), ref(0), older(0), newer(0)
37  { begin = new char[s]; }
38  ~MemBlock() { delete [] begin; }
39  bool is_in(void *ptr) const {return !(begin > (char *)ptr
40  || (begin + size) <= (char *)ptr); }
41  size_t size;
42  unsigned int ref;
43  char *begin;
44  MemBlock *older;
45  MemBlock *newer;
46 };
47 
48 TDEZoneAllocator::TDEZoneAllocator(unsigned long _blockSize)
49 : currentBlock(0), blockSize(1), blockOffset(0), log2(0), num_blocks(0),
50  hashList(0), hashSize(0), hashDirty(true)
51 {
52  while (blockSize < _blockSize)
53  blockSize <<= 1, log2++;
54  /* Make sure, that a block is allocated at the first time allocate()
55  is called (even with a 0 size). */
56  blockOffset = blockSize + 1;
57 }
58 
59 TDEZoneAllocator::~TDEZoneAllocator()
60 {
61  unsigned int count = 0;
62  if (hashList) {
63  /* No need to maintain the different lists in hashList[] anymore.
64  I.e. no need to use delBlock(). */
65  for (unsigned int i = 0; i < hashSize; i++)
66  delete hashList[i];
67  delete [] hashList;
68  hashList = 0;
69  }
70  MemBlock *next;
71  for (; currentBlock; currentBlock = next) {
72  next = currentBlock->older;
73  delete currentBlock;
74  count++;
75  }
76 #ifndef NDEBUG // as this is called quite late in the app, we don't care
77  // to use kdDebug
78  if (count > 1)
79  tqDebug("zone still contained %d blocks", count);
80 #endif
81 }
82 
83 void TDEZoneAllocator::insertHash(MemBlock *b)
84 {
85  unsigned long adr = ((unsigned long)b->begin) & (~(blockSize - 1));
86  unsigned long end = ((unsigned long)b->begin) + blockSize;
87  while (adr < end) {
88  unsigned long key = adr >> log2;
89  key = key & (hashSize - 1);
90  if (!hashList[key])
91  hashList[key] = new TQValueList<MemBlock *>;
92  hashList[key]->append(b);
93  adr += blockSize;
94  }
95 }
96 
102 void TDEZoneAllocator::addBlock(MemBlock *b)
103 {
104  b->newer = 0;
105  b->older = currentBlock;
106  if (currentBlock)
107  b->older->newer = b;
108  currentBlock = b;
109  num_blocks++;
110  /* If we either have no hashList at all, or since it's last construction
111  there are now many more blocks we reconstruct the list. But don't
112  make it larger than a certain maximum. */
113  if (hashList && ((num_blocks / 4) > hashSize && hashSize < 64*1024))
114  hashDirty = true;
115  /* Only insert this block into the hashlists, if we aren't going to
116  reconstruct them anyway. */
117  if (hashList && !hashDirty)
118  insertHash (b);
119 }
120 
122 void TDEZoneAllocator::initHash()
123 {
124  if (hashList) {
125  for (unsigned int i = 0; i < hashSize; i++)
126  delete hashList[i];
127  delete [] hashList;
128  hashList = 0;
129  }
130  hashSize = 1;
131  while (hashSize < num_blocks)
132  hashSize <<= 1;
133  if (hashSize < 1024)
134  hashSize = 1024;
135  if (hashSize > 64*1024)
136  hashSize = 64*1024;
137  hashList = new TQValueList<MemBlock *> *[hashSize];
138  memset (hashList, 0, sizeof(TQValueList<MemBlock*> *) * hashSize);
139  hashDirty = false;
140  for (MemBlock *b = currentBlock; b; b = b->older)
141  insertHash(b);
142 }
143 
148 void TDEZoneAllocator::delBlock(MemBlock *b)
149 {
150  /* Update also the hashlists if we aren't going to reconstruct them
151  soon. */
152  if (hashList && !hashDirty) {
153  unsigned long adr = ((unsigned long)b->begin) & (~(blockSize - 1));
154  unsigned long end = ((unsigned long)b->begin) + blockSize;
155  while (adr < end) {
156  unsigned long key = adr >> log2;
157  key = key & (hashSize - 1);
158  if (hashList[key]) {
159  TQValueList<MemBlock *> *list = hashList[key];
160  TQValueList<MemBlock *>::Iterator it = list->begin();
161  TQValueList<MemBlock *>::Iterator endit = list->end();
162  for (; it != endit; ++it)
163  if (*it == b) {
164  list->remove(it);
165  break;
166  }
167  }
168  adr += blockSize;
169  }
170  }
171  if (b->older)
172  b->older->newer = b->newer;
173  if (b->newer)
174  b->newer->older = b->older;
175  if (b == currentBlock) {
176  currentBlock = 0;
177  blockOffset = blockSize;
178  }
179  delete b;
180  num_blocks--;
181 }
182 
183 void *
184 TDEZoneAllocator::allocate(size_t _size)
185 {
186  // Use the size of (void *) as alignment
187  const size_t alignment = sizeof(void *) - 1;
188  _size = (_size + alignment) & ~alignment;
189 
190  if ((unsigned long) _size + blockOffset > blockSize)
191  {
192  if (_size > blockSize) {
193  tqDebug("TDEZoneAllocator: allocating more than %lu bytes", blockSize);
194  return 0;
195  }
196  addBlock(new MemBlock(blockSize));
197  blockOffset = 0;
198  //tqDebug ("Allocating block #%d (%x)\n", num_blocks, currentBlock->begin);
199  }
200  void *result = (void *)(currentBlock->begin+blockOffset);
201  currentBlock->ref++;
202  blockOffset += _size;
203  return result;
204 }
205 
206 void
207 TDEZoneAllocator::deallocate(void *ptr)
208 {
209  if (hashDirty)
210  initHash();
211 
212  unsigned long key = (((unsigned long)ptr) >> log2) & (hashSize - 1);
213  TQValueList<MemBlock *> *list = hashList[key];
214  if (!list) {
215  /* Can happen with certain usage pattern of intermixed free_since()
216  and deallocate(). */
217  //tqDebug("Uhoh");
218  return;
219  }
220  TQValueList<MemBlock*>::ConstIterator it = list->begin();
221  TQValueList<MemBlock*>::ConstIterator endit = list->end();
222  for (; it != endit; ++it) {
223  MemBlock *cur = *it;
224  if (cur->is_in(ptr)) {
225  if (!--cur->ref) {
226  if (cur != currentBlock)
227  delBlock (cur);
228  else
229  blockOffset = 0;
230  }
231  return;
232  }
233  }
234  /* Can happen with certain usage pattern of intermixed free_since()
235  and deallocate(). */
236  //tqDebug("Uhoh2");
237 }
238 
239 void
240 TDEZoneAllocator::free_since(void *ptr)
241 {
242  /* If we have a hashList and it's not yet dirty, see, if we will dirty
243  it by removing too many blocks. This will make the below delBlock()s
244  faster. */
245  if (hashList && !hashDirty)
246  {
247  const MemBlock *b;
248  unsigned int removed = 0;
249  for (b = currentBlock; b; b = b->older, removed++)
250  if (b->is_in (ptr))
251  break;
252  if (hashSize >= 4 * (num_blocks - removed))
253  hashDirty = true;
254  }
255  while (currentBlock && !currentBlock->is_in(ptr)) {
256  currentBlock = currentBlock->older;
257  delBlock (currentBlock->newer);
258  }
259  blockOffset = ((char*)ptr) - currentBlock->begin;
260 }
TDEZoneAllocator::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:207
TDEZoneAllocator::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:102
TDEZoneAllocator::log2
unsigned int log2
base-2 log of the block size.
Definition: kallocator.h:127
TDEZoneAllocator::hashList
MemList ** hashList
Collection of lists of blocks, for lookups.
Definition: kallocator.h:131
TDEZoneAllocator::blockSize
unsigned long blockSize
Store block size from constructor.
Definition: kallocator.h:123
TDEZoneAllocator::num_blocks
unsigned int num_blocks
Count total number of allocated blocks.
Definition: kallocator.h:129
TDEZoneAllocator::blockOffset
unsigned long blockOffset
Store offset into current block; size-offset is free.
Definition: kallocator.h:125
TDEZoneAllocator::TDEZoneAllocator
TDEZoneAllocator(unsigned long _blockSize=8 *1024)
Creates a TDEZoneAllocator object.
Definition: kallocator.cpp:48
TDEZoneAllocator::free_since
void free_since(void *ptr)
Deallocate many objects at once.
Definition: kallocator.cpp:240
TDEZoneAllocator::currentBlock
MemBlock * currentBlock
One block is 'current' to satisfy requests.
Definition: kallocator.h:121
TDEZoneAllocator::hashDirty
bool hashDirty
Flag the hashes as in need of reorganization.
Definition: kallocator.h:135
TDEZoneAllocator::hashSize
unsigned int hashSize
Count of hashes.
Definition: kallocator.h:133
TDEZoneAllocator::delBlock
void delBlock(MemBlock *b)
Delete a memory block.
Definition: kallocator.cpp:148
TDEZoneAllocator::initHash
void initHash()
Reinitialize hash list.
Definition: kallocator.cpp:122
TDEZoneAllocator::~TDEZoneAllocator
~TDEZoneAllocator()
Destructs the ZoneAllocator and free all memory allocated by it.
Definition: kallocator.cpp:59
TDEZoneAllocator::allocate
void * allocate(size_t _size)
Allocates a memory block.
Definition: kallocator.cpp:184

tdecore

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

tdecore

Skip menu "tdecore"
  • arts
  • dcop
  • dnssd
  • interfaces
  •   kspeech
  •     interface
  •     library
  •   tdetexteditor
  • kate
  • kded
  • kdoctools
  • kimgio
  • kjs
  • libtdemid
  • libtdescreensaver
  • tdeabc
  • tdecmshell
  • tdecore
  • tdefx
  • tdehtml
  • tdeinit
  • tdeio
  •   bookmarks
  •   httpfilter
  •   kpasswdserver
  •   kssl
  •   tdefile
  •   tdeio
  •   tdeioexec
  • tdeioslave
  •   http
  • tdemdi
  •   tdemdi
  • tdenewstuff
  • tdeparts
  • tdeprint
  • tderandr
  • tderesources
  • tdespell2
  • tdesu
  • tdeui
  • tdeunittest
  • tdeutils
  • tdewallet
Generated for tdecore by doxygen 1.9.1
This website is maintained by Timothy Pearson.