kdecore Library API Documentation

kallocator.cpp

00001 /* 00002 This file is part of the KDE libraries 00003 00004 Copyright (C) 1999 Waldo Bastian (bastian@kde.org) 00005 Copyright (C) 2002 Michael Matz (matz@kde.org) 00006 00007 This library is free software; you can redistribute it and/or 00008 modify it under the terms of the GNU Library General Public 00009 License as published by the Free Software Foundation; either 00010 version 2 of the License, or (at your option) any later version. 00011 00012 This library is distributed in the hope that it will be useful, 00013 but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 Library General Public License for more details. 00016 00017 You should have received a copy of the GNU Library General Public License 00018 along with this library; see the file COPYING.LIB. If not, write to 00019 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, 00020 Boston, MA 02111-1307, USA. 00021 */ 00022 00023 /* Fast zone memory allocator with deallocation support, for use as obstack 00024 or as general purpose allocator. It does no compaction. If the usage 00025 pattern is non-optimal it might waste some memory while running. E.g. 00026 allocating many small things at once, and then deallocating only every 00027 second one, there is a high chance, that actually no memory is freed. */ 00028 // $Id: kallocator.cpp,v 1.9 2002/12/16 12:59:42 coolo Exp $ 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 /* Make sure, that a block is allocated at the first time allocate() 00055 is called (even with a 0 size). */ 00056 blockOffset = blockSize + 1; 00057 } 00058 00059 KZoneAllocator::~KZoneAllocator() 00060 { 00061 unsigned int count = 0; 00062 if (hashList) { 00063 /* No need to maintain the different lists in hashList[] anymore. 00064 I.e. no need to use delBlock(). */ 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 // to use kdDebug 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 /* If we either have no hashList at all, or since it's last construction 00106 there are now many more blocks we reconstruct the list. But don't 00107 make it larger than a certain maximum. */ 00108 if (hashList && ((num_blocks / 4) > hashSize && hashSize < 64*1024)) 00109 hashDirty = true; 00110 /* Only insert this block into the hashlists, if we aren't going to 00111 reconstruct them anyway. */ 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 /* Update also the hashlists if we aren't going to reconstruct them 00141 soon. */ 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 // Use the size of (void *) as alignment 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 //qDebug ("Allocating block #%d (%x)\n", num_blocks, currentBlock->begin); 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 /* Can happen with certain usage pattern of intermixed free_since() 00206 and deallocate(). */ 00207 //qDebug("Uhoh"); 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 /* Can happen with certain usage pattern of intermixed free_since() 00225 and deallocate(). */ 00226 //qDebug("Uhoh2"); 00227 } 00228 00229 void 00230 KZoneAllocator::free_since(void *ptr) 00231 { 00232 /* If we have a hashList and it's not yet dirty, see, if we will dirty 00233 it by removing too many blocks. This will make the below delBlock()s 00234 faster. */ 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 }
KDE Logo
This file is part of the documentation for kdecore Library Version 3.3.1.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Sun Oct 17 11:26:05 2004 by doxygen 1.3.8 written by Dimitri van Heesch, © 1997-2003