kallocator.cpp
00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #include "kallocator.h"
00031 #include <kdebug.h>
00032
00033 class KZoneAllocator::MemBlock
00034 {
00035 public:
00036 MemBlock(size_t s) : size(s), ref(0), older(0), newer(0)
00037 { begin = new char[s]; }
00038 ~MemBlock() { delete [] begin; }
00039 bool is_in(void *ptr) const {return !(begin > (char *)ptr
00040 || (begin + size) <= (char *)ptr); }
00041 size_t size;
00042 unsigned int ref;
00043 char *begin;
00044 MemBlock *older;
00045 MemBlock *newer;
00046 };
00047
00048 KZoneAllocator::KZoneAllocator(unsigned long _blockSize)
00049 : currentBlock(0), blockSize(1), blockOffset(0), log2(0), num_blocks(0),
00050 hashList(0), hashSize(0), hashDirty(true)
00051 {
00052 while (blockSize < _blockSize)
00053 blockSize <<= 1, log2++;
00054
00055
00056 blockOffset = blockSize + 1;
00057 }
00058
00059 KZoneAllocator::~KZoneAllocator()
00060 {
00061 unsigned int count = 0;
00062 if (hashList) {
00063
00064
00065 for (unsigned int i = 0; i < hashSize; i++)
00066 delete hashList[i];
00067 delete [] hashList;
00068 hashList = 0;
00069 }
00070 MemBlock *next;
00071 for (; currentBlock; currentBlock = next) {
00072 next = currentBlock->older;
00073 delete currentBlock;
00074 count++;
00075 }
00076 #ifndef NDEBUG // as this is called quite late in the app, we don't care
00077
00078 if (count > 1)
00079 qDebug("zone still contained %d blocks", count);
00080 #endif
00081 }
00082
00083 void KZoneAllocator::insertHash(MemBlock *b)
00084 {
00085 unsigned int adr = ((unsigned int)b->begin) & (~(blockSize - 1));
00086 unsigned int end = ((unsigned int)b->begin) + blockSize;
00087 while (adr < end) {
00088 unsigned int key = adr >> log2;
00089 key = key & (hashSize - 1);
00090 if (!hashList[key])
00091 hashList[key] = new QValueList<MemBlock *>;
00092 hashList[key]->append(b);
00093 adr += blockSize;
00094 }
00095 }
00096
00097 void KZoneAllocator::addBlock(MemBlock *b)
00098 {
00099 b->newer = 0;
00100 b->older = currentBlock;
00101 if (currentBlock)
00102 b->older->newer = b;
00103 currentBlock = b;
00104 num_blocks++;
00105
00106
00107
00108 if (hashList && ((num_blocks / 4) > hashSize && hashSize < 64*1024))
00109 hashDirty = true;
00110
00111
00112 if (hashList && !hashDirty)
00113 insertHash (b);
00114 }
00115
00116 void KZoneAllocator::initHash()
00117 {
00118 if (hashList) {
00119 for (unsigned int i = 0; i < hashSize; i++)
00120 delete hashList[i];
00121 delete [] hashList;
00122 hashList = 0;
00123 }
00124 hashSize = 1;
00125 while (hashSize < num_blocks)
00126 hashSize <<= 1;
00127 if (hashSize < 1024)
00128 hashSize = 1024;
00129 if (hashSize > 64*1024)
00130 hashSize = 64*1024;
00131 hashList = new QValueList<MemBlock *> *[hashSize];
00132 memset (hashList, 0, sizeof(QValueList<MemBlock*> *) * hashSize);
00133 hashDirty = false;
00134 for (MemBlock *b = currentBlock; b; b = b->older)
00135 insertHash(b);
00136 }
00137
00138 void KZoneAllocator::delBlock(MemBlock *b)
00139 {
00140
00141
00142 if (hashList && !hashDirty) {
00143 unsigned int adr = ((unsigned int)b->begin) & (~(blockSize - 1));
00144 unsigned int end = ((unsigned int)b->begin) + blockSize;
00145 while (adr < end) {
00146 unsigned int key = adr >> log2;
00147 key = key & (hashSize - 1);
00148 if (hashList[key]) {
00149 QValueList<MemBlock *> *list = hashList[key];
00150 QValueList<MemBlock *>::Iterator it = list->begin();
00151 QValueList<MemBlock *>::Iterator endit = list->end();
00152 for (; it != endit; ++it)
00153 if (*it == b) {
00154 list->remove(it);
00155 break;
00156 }
00157 }
00158 adr += blockSize;
00159 }
00160 }
00161 if (b->older)
00162 b->older->newer = b->newer;
00163 if (b->newer)
00164 b->newer->older = b->older;
00165 if (b == currentBlock) {
00166 currentBlock = 0;
00167 blockOffset = blockSize;
00168 }
00169 delete b;
00170 num_blocks--;
00171 }
00172
00173 void *
00174 KZoneAllocator::allocate(size_t _size)
00175 {
00176
00177 const size_t alignment = sizeof(void *) - 1;
00178 _size = (_size + alignment) & ~alignment;
00179
00180 if ((unsigned long) _size + blockOffset > blockSize)
00181 {
00182 if (_size > blockSize) {
00183 qDebug("KZoneAllocator: allocating more than %lu bytes", blockSize);
00184 return 0;
00185 }
00186 addBlock(new MemBlock(blockSize));
00187 blockOffset = 0;
00188
00189 }
00190 void *result = (void *)(currentBlock->begin+blockOffset);
00191 currentBlock->ref++;
00192 blockOffset += _size;
00193 return result;
00194 }
00195
00196 void
00197 KZoneAllocator::deallocate(void *ptr)
00198 {
00199 if (hashDirty)
00200 initHash();
00201
00202 unsigned int key = (((unsigned int)ptr) >> log2) & (hashSize - 1);
00203 QValueList<MemBlock *> *list = hashList[key];
00204 if (!list) {
00205
00206
00207
00208 return;
00209 }
00210 QValueList<MemBlock*>::ConstIterator it = list->begin();
00211 QValueList<MemBlock*>::ConstIterator endit = list->end();
00212 for (; it != endit; ++it) {
00213 MemBlock *cur = *it;
00214 if (cur->is_in(ptr)) {
00215 if (!--cur->ref) {
00216 if (cur != currentBlock)
00217 delBlock (cur);
00218 else
00219 blockOffset = 0;
00220 }
00221 return;
00222 }
00223 }
00224
00225
00226
00227 }
00228
00229 void
00230 KZoneAllocator::free_since(void *ptr)
00231 {
00232
00233
00234
00235 if (hashList && !hashDirty)
00236 {
00237 const MemBlock *b;
00238 unsigned int removed = 0;
00239 for (b = currentBlock; b; b = b->older, removed++)
00240 if (b->is_in (ptr))
00241 break;
00242 if (hashSize >= 4 * (num_blocks - removed))
00243 hashDirty = true;
00244 }
00245 while (currentBlock && !currentBlock->is_in(ptr)) {
00246 currentBlock = currentBlock->older;
00247 delBlock (currentBlock->newer);
00248 }
00249 blockOffset = ((char*)ptr) - currentBlock->begin;
00250 }
This file is part of the documentation for kdecore Library Version 3.3.0.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Thu Sep 23 17:11:35 2004 by
doxygen 1.3.8-20040913 written by
Dimitri van Heesch, © 1997-2003