• Skip to content
  • Skip to link menu
KDE 4.2 API Reference
  • KDE API Reference
  • kdelibs
  • Sitemap
  • Contact Us
 

KDECore

kallocator.cpp

Go to the documentation of this file.
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., 51 Franklin Street, Fifth Floor,
00020     Boston, MA 02110-1301, 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  */
00029 
00030 #include "kallocator.h"
00031 #include "kdebug.h"
00032 #include <QList>
00033 
00034 class KZoneAllocator::MemBlock
00035 {
00036   public:
00037     MemBlock(size_t s) : size(s), ref(0), older(0), newer(0)
00038       { begin = new char[s]; }
00039     ~MemBlock() { delete [] begin; }
00040     bool is_in(void *ptr) const {return !(begin > (char *)ptr
00041                               || (begin + size) <= (char *)ptr); }
00042     size_t size;
00043     unsigned int ref;
00044     char *begin;
00045     MemBlock *older;
00046     MemBlock *newer;
00047 };
00048 
00049 class KZoneAllocator::Private
00050 {
00051 public:
00052     Private()
00053         : currentBlock(0), blockSize(1),
00054           blockOffset(0), log2(0), num_blocks(0),
00055           hashList(0), hashSize(0), hashDirty(true)
00056     {
00057     }
00058 
00060     MemBlock *currentBlock; 
00062     unsigned long blockSize; 
00064     unsigned long blockOffset;
00066     unsigned int log2;
00068     unsigned int num_blocks;
00070     MemList **hashList;
00072     unsigned int hashSize;
00074     bool hashDirty;
00075 };
00076 
00077 KZoneAllocator::KZoneAllocator(unsigned long _blockSize)
00078     : d( new Private )
00079 {
00080     while (d->blockSize < _blockSize) {
00081         d->blockSize <<= 1;
00082         d->log2++;
00083     }
00084 
00085     /* Make sure, that a block is allocated at the first time allocate()
00086        is called (even with a 0 size).  */
00087     d->blockOffset = d->blockSize + 1;
00088 }
00089 
00090 KZoneAllocator::~KZoneAllocator()
00091 {
00092   unsigned int count = 0;
00093   if (d->hashList) {
00094     /* No need to maintain the different lists in d->hashList[] anymore.
00095        I.e. no need to use delBlock().  */
00096     for (unsigned int i = 0; i < d->hashSize; i++)
00097       delete d->hashList[i];
00098     delete [] d->hashList;
00099     d->hashList = 0;
00100   }
00101   MemBlock *next;
00102   for (; d->currentBlock; d->currentBlock = next) {
00103     next = d->currentBlock->older;
00104     delete d->currentBlock;
00105     count++;
00106   }
00107 #ifndef NDEBUG // as this is called quite late in the app, we don't care
00108            // to use kDebug
00109   if (count > 1)
00110     qDebug("zone still contained %d blocks", count);
00111 #endif
00112   delete d;
00113 }
00114 
00115 void KZoneAllocator::insertHash(MemBlock *b)
00116 {
00117   unsigned long adr = ((unsigned long)b->begin) & (~(d->blockSize - 1));
00118   unsigned long end = ((unsigned long)b->begin) + d->blockSize;
00119   while (adr < end) {
00120     unsigned long key = adr >> d->log2;
00121     key = key & (d->hashSize - 1);
00122     if (!d->hashList[key])
00123       d->hashList[key] = new QList<MemBlock *>;
00124     d->hashList[key]->append(b);
00125     adr += d->blockSize;
00126   }
00127 }
00128 
00134 void KZoneAllocator::addBlock(MemBlock *b)
00135 {
00136   b->newer = 0;
00137   b->older = d->currentBlock;
00138   if (d->currentBlock)
00139     b->older->newer = b;
00140   d->currentBlock = b;
00141   d->num_blocks++;
00142   /* If we either have no d->hashList at all, or since it's last construction
00143      there are now many more blocks we reconstruct the list.  But don't
00144      make it larger than a certain maximum.  */
00145   if (d->hashList && ((d->num_blocks / 4) > d->hashSize && d->hashSize < 64*1024))
00146     d->hashDirty = true;
00147   /* Only insert this block into the hashlists, if we aren't going to
00148      reconstruct them anyway.  */
00149   if (d->hashList && !d->hashDirty)
00150     insertHash (b);
00151 }
00152 
00154 void KZoneAllocator::initHash()
00155 {
00156   if (d->hashList) {
00157     for (unsigned int i = 0; i < d->hashSize; i++)
00158       delete d->hashList[i];
00159     delete [] d->hashList;
00160     d->hashList = 0;
00161   }
00162   d->hashSize = 1;
00163   while (d->hashSize < d->num_blocks)
00164     d->hashSize <<= 1;
00165   if (d->hashSize < 1024)
00166     d->hashSize = 1024;
00167   if (d->hashSize > 64*1024)
00168     d->hashSize = 64*1024;
00169   d->hashList = new QList<MemBlock *> *[d->hashSize];
00170   memset (d->hashList, 0, sizeof(QList<MemBlock*> *) * d->hashSize);
00171   d->hashDirty = false;
00172   for (MemBlock *b = d->currentBlock; b; b = b->older)
00173     insertHash(b);
00174 }
00175 
00180 void KZoneAllocator::delBlock(MemBlock *b)
00181 {
00182   /* Update also the hashlists if we aren't going to reconstruct them
00183      soon.  */
00184   if (d->hashList && !d->hashDirty) {
00185     unsigned long adr = ((unsigned long)b->begin) & (~(d->blockSize - 1));
00186     unsigned long end = ((unsigned long)b->begin) + d->blockSize;
00187     while (adr < end) {
00188       unsigned long key = adr >> d->log2;
00189       key = key & (d->hashSize - 1);
00190       if (d->hashList[key]) {
00191     QList<MemBlock *> *list = d->hashList[key];
00192     QList<MemBlock *>::Iterator it = list->begin();
00193     QList<MemBlock *>::Iterator endit = list->end();
00194     for (; it != endit; ++it)
00195       if (*it == b) {
00196         list->erase(it);
00197         break;
00198       }
00199       }
00200       adr += d->blockSize;
00201     }
00202   }
00203   if (b->older)
00204     b->older->newer = b->newer;
00205   if (b->newer)
00206     b->newer->older = b->older;
00207   if (b == d->currentBlock) {
00208     d->currentBlock = 0;
00209     d->blockOffset = d->blockSize;
00210   }
00211   delete b;
00212   d->num_blocks--;
00213 }
00214 
00215 void *
00216 KZoneAllocator::allocate(size_t _size)
00217 {
00218    // Use the size of (void *) as alignment
00219    const size_t alignment = sizeof(void *) - 1;
00220    _size = (_size + alignment) & ~alignment;   
00221 
00222    if ((unsigned long) _size + d->blockOffset > d->blockSize)
00223    {
00224       if (_size > d->blockSize) {
00225     qDebug("KZoneAllocator: allocating more than %lu bytes", d->blockSize);
00226     return 0;
00227       }
00228       addBlock(new MemBlock(d->blockSize));
00229       d->blockOffset = 0;
00230       //qDebug ("Allocating block #%d (%x)\n", d->num_blocks, d->currentBlock->begin);
00231    }
00232    void *result = (void *)(d->currentBlock->begin+d->blockOffset);
00233    d->currentBlock->ref++;
00234    d->blockOffset += _size;
00235    return result;
00236 }
00237 
00238 void
00239 KZoneAllocator::deallocate(void *ptr)
00240 {
00241   if (d->hashDirty)
00242     initHash();
00243 
00244   unsigned long key = (((unsigned long)ptr) >> d->log2) & (d->hashSize - 1);
00245   const QList<MemBlock *> *list = d->hashList[key];
00246   if (!list) {
00247     /* Can happen with certain usage pattern of intermixed free_since()
00248        and deallocate().  */
00249     //qDebug("Uhoh");
00250     return;
00251   }
00252   QList<MemBlock*>::ConstIterator it = list->begin();
00253   QList<MemBlock*>::ConstIterator endit = list->end();
00254   for (; it != endit; ++it) {
00255     MemBlock *cur = *it;
00256     if (cur->is_in(ptr)) {
00257       if (!--cur->ref) {
00258     if (cur != d->currentBlock)
00259       delBlock (cur);
00260     else
00261       d->blockOffset = 0;
00262       }
00263       return;
00264     }
00265   }
00266   /* Can happen with certain usage pattern of intermixed free_since()
00267      and deallocate().  */
00268   //qDebug("Uhoh2");
00269 }
00270 
00271 void
00272 KZoneAllocator::free_since(void *ptr)
00273 {
00274   /* If we have a d->hashList and it's not yet dirty, see, if we will dirty
00275      it by removing too many blocks.  This will make the below delBlock()s
00276      faster.  */
00277   if (d->hashList && !d->hashDirty)
00278     {
00279       const MemBlock *b;
00280       unsigned int removed = 0;
00281       for (b = d->currentBlock; b; b = b->older, removed++)
00282     if (b->is_in (ptr))
00283       break;
00284       if (d->hashSize >= 4 * (d->num_blocks - removed))
00285         d->hashDirty = true;
00286     }
00287   while (d->currentBlock && !d->currentBlock->is_in(ptr)) {
00288     d->currentBlock = d->currentBlock->older;
00289     delBlock (d->currentBlock->newer);
00290   }
00291   d->blockOffset = ((char*)ptr) - d->currentBlock->begin;
00292 }

KDECore

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

kdelibs

Skip menu "kdelibs"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • Kate
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • Kross
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Generated for kdelibs by doxygen 1.5.7
This website is maintained by Adriaan de Groot and Allen Winter.
KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal