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