| # kdecore Library API Documentation
Overview | Class Hierarchy | Classes | Classes (annotated) | Members | Namespaces | Source Files

# 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 376049 2005-01-07 10:24:18Z waba $
    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 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 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 long adr = ((unsigned long)b->begin) & (~(blockSize - 1));
    00144     unsigned long end = ((unsigned long)b->begin) + blockSize;
    00145     while (adr < end) {
    00146       unsigned long 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 long key = (((unsigned long)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 }

This file is part of the documentation for kdecore Library Version 3.4.1.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Sat Jun 11 20:18:00 2005 by doxygen 1.4.1 written by Dimitri van Heesch, © 1997-2003