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 if (count > 1)
00077 qDebug("zone still contained %d blocks", count);
00078 }
00079
00080 void KZoneAllocator::insertHash(MemBlock *b)
00081 {
00082 unsigned int adr = ((unsigned int)b->begin) & (~(blockSize - 1));
00083 unsigned int end = ((unsigned int)b->begin) + blockSize;
00084 while (adr < end) {
00085 unsigned int key = adr >> log2;
00086 key = key & (hashSize - 1);
00087 if (!hashList[key])
00088 hashList[key] = new QValueList<MemBlock *>;
00089 hashList[key]->append(b);
00090 adr += blockSize;
00091 }
00092 }
00093
00094 void KZoneAllocator::addBlock(MemBlock *b)
00095 {
00096 b->newer = 0;
00097 b->older = currentBlock;
00098 if (currentBlock)
00099 b->older->newer = b;
00100 currentBlock = b;
00101 num_blocks++;
00102
00103
00104
00105 if (hashList && ((num_blocks / 4) > hashSize && hashSize < 64*1024))
00106 hashDirty = true;
00107
00108
00109 if (hashList && !hashDirty)
00110 insertHash (b);
00111 }
00112
00113 void KZoneAllocator::initHash()
00114 {
00115 if (hashList) {
00116 for (unsigned int i = 0; i < hashSize; i++)
00117 delete hashList[i];
00118 delete [] hashList;
00119 hashList = 0;
00120 }
00121 hashSize = 1;
00122 while (hashSize < num_blocks)
00123 hashSize <<= 1;
00124 if (hashSize < 1024)
00125 hashSize = 1024;
00126 if (hashSize > 64*1024)
00127 hashSize = 64*1024;
00128 hashList = new QValueList<MemBlock *> *[hashSize];
00129 memset (hashList, 0, sizeof(QValueList<MemBlock*> *) * hashSize);
00130 hashDirty = false;
00131 for (MemBlock *b = currentBlock; b; b = b->older)
00132 insertHash(b);
00133 }
00134
00135 void KZoneAllocator::delBlock(MemBlock *b)
00136 {
00137
00138
00139 if (hashList && !hashDirty) {
00140 unsigned int adr = ((unsigned int)b->begin) & (~(blockSize - 1));
00141 unsigned int end = ((unsigned int)b->begin) + blockSize;
00142 while (adr < end) {
00143 unsigned int key = adr >> log2;
00144 key = key & (hashSize - 1);
00145 if (hashList[key]) {
00146 QValueList<MemBlock *> *list = hashList[key];
00147 QValueList<MemBlock *>::Iterator it = list->begin();
00148 QValueList<MemBlock *>::Iterator endit = list->end();
00149 for (; it != endit; ++it)
00150 if (*it == b) {
00151 list->remove(it);
00152 break;
00153 }
00154 }
00155 adr += blockSize;
00156 }
00157 }
00158 if (b->older)
00159 b->older->newer = b->newer;
00160 if (b->newer)
00161 b->newer->older = b->older;
00162 if (b == currentBlock) {
00163 currentBlock = 0;
00164 blockOffset = blockSize;
00165 }
00166 delete b;
00167 num_blocks--;
00168 }
00169
00170 void *
00171 KZoneAllocator::allocate(size_t _size)
00172 {
00173
00174 const size_t alignment = sizeof(void *) - 1;
00175 _size = (_size + alignment) & ~alignment;
00176
00177 if ((unsigned long) _size + blockOffset > blockSize)
00178 {
00179 if (_size > blockSize) {
00180 qDebug("KZoneAllocator: allocating more than %lu bytes", blockSize);
00181 return 0;
00182 }
00183 addBlock(new MemBlock(blockSize));
00184 blockOffset = 0;
00185
00186 }
00187 void *result = (void *)(currentBlock->begin+blockOffset);
00188 currentBlock->ref++;
00189 blockOffset += _size;
00190 return result;
00191 }
00192
00193 void
00194 KZoneAllocator::deallocate(void *ptr)
00195 {
00196 if (hashDirty)
00197 initHash();
00198
00199 unsigned int key = (((unsigned int)ptr) >> log2) & (hashSize - 1);
00200 QValueList<MemBlock *> *list = hashList[key];
00201 if (!list) {
00202
00203
00204
00205 return;
00206 }
00207 QValueList<MemBlock*>::ConstIterator it = list->begin();
00208 QValueList<MemBlock*>::ConstIterator endit = list->end();
00209 for (; it != endit; ++it) {
00210 MemBlock *cur = *it;
00211 if (cur->is_in(ptr)) {
00212 if (!--cur->ref) {
00213 if (cur != currentBlock)
00214 delBlock (cur);
00215 else
00216 blockOffset = 0;
00217 }
00218 return;
00219 }
00220 }
00221
00222
00223
00224 }
00225
00226 void
00227 KZoneAllocator::free_since(void *ptr)
00228 {
00229
00230
00231
00232 if (hashList && !hashDirty)
00233 {
00234 const MemBlock *b;
00235 unsigned int removed = 0;
00236 for (b = currentBlock; b; b = b->older, removed++)
00237 if (b->is_in (ptr))
00238 break;
00239 if (hashSize >= 4 * (num_blocks - removed))
00240 hashDirty = true;
00241 }
00242 while (currentBlock && !currentBlock->is_in(ptr)) {
00243 currentBlock = currentBlock->older;
00244 delBlock (currentBlock->newer);
00245 }
00246 blockOffset = ((char*)ptr) - currentBlock->begin;
00247 }
This file is part of the documentation for kdelibs Version 3.1.0.