? Makefile.in.real
? kcharsets.cpp_mm
? kcharsets.diff
? kdecore.diff
? klibloader.diff
Index: kallocator.cpp
===================================================================
RCS file: /home/kde/kdelibs/kdecore/kallocator.cpp,v
retrieving revision 1.4
diff -u -p -r1.4 kallocator.cpp
--- kallocator.cpp	2000/10/09 21:29:00	1.4
+++ kallocator.cpp	2002/03/07 07:21:36
@@ -2,6 +2,7 @@
     This file is part of the KDE libraries
 
     Copyright (C) 1999 Waldo Bastian (bastian@kde.org)
+    Copyright (C) 2002 Michael Matz (matz@kde.org)
 
     This library is free software; you can redistribute it and/or
     modify it under the terms of the GNU Library General Public
@@ -18,46 +19,227 @@
     the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
     Boston, MA 02111-1307, USA.
 */
-//----------------------------------------------------------------------------
-//
-// KDE HTML Widget -- Objects
+
+/* Fast zone memory allocator with deallocation support, for use as obstack
+   or as general purpose allocator.  It does no compaction.  If the usage
+   pattern is non-optimal it might waste some memory while running.  E.g.
+   allocating many small things at once, and then deallocating only every
+   second one, there is a high chance, that actually no memory is freed.  */
 // $Id: kallocator.cpp,v 1.4 2000/10/09 21:29:00 zander Exp $
 
 #include "kallocator.h"
 #include <kdebug.h>
 
-KZoneAllocator::KZoneAllocator(long _blockSize)
-: blockSize(_blockSize), blockOffset(0)
+class KZoneAllocator::MemBlock
+{
+  public:
+    MemBlock(size_t s) : size(s), ref(0), older(0), newer(0)
+      { begin = new char[s]; }
+    ~MemBlock() { delete [] begin; }
+    bool is_in(void *ptr) const {return !(begin > (char *)ptr
+    				          || (begin + size) <= (char *)ptr); }
+    size_t size;
+    unsigned int ref;
+    char *begin;
+    MemBlock *older;
+    MemBlock *newer;
+};
+
+KZoneAllocator::KZoneAllocator(unsigned long _blockSize)
+: currentBlock(0), blockSize(1), blockOffset(0), log2(0), num_blocks(0), 
+  hashList(0), hashSize(0), hashDirty(true)
 {
-    currentBlock = new char[_blockSize];
-    memoryBlocks.append(currentBlock);
+  while (blockSize < _blockSize)
+    blockSize <<= 1, log2++;
+  blockOffset = blockSize;
 }
 
 KZoneAllocator::~KZoneAllocator()
 {
-    while (!memoryBlocks.isEmpty())
-    {
-        char *oldBuffer = (char *) memoryBlocks.take(0);
-        delete [] oldBuffer;
+  unsigned int count = 0;
+  if (hashList) {
+    /* No need to maintain the different lists in hashList[] anymore.
+       I.e. no need to use delBlock().  */
+    for (int i = 0; i < hashSize; i++)
+      delete hashList[i];
+    delete [] hashList;
+    hashList = 0;
+  }
+  MemBlock *next;
+  for (; currentBlock; currentBlock = next) {
+    next = currentBlock->older;
+    delete currentBlock;
+    count++;
+  }
+  if (count > 1)
+    qDebug("zone still contained %d blocks", count);
+}
+
+void KZoneAllocator::insertHash(MemBlock *b)
+{
+  unsigned int adr = ((unsigned int)b->begin) & (~(blockSize - 1));
+  unsigned int end = ((unsigned int)b->begin) + blockSize;
+  while (adr < end) {
+    unsigned int key = adr >> log2;
+    key = key & (hashSize - 1);
+    if (!hashList[key])
+      hashList[key] = new QValueList<MemBlock *>;
+    hashList[key]->append(b);
+    adr += blockSize;
+  }
+}
+
+void KZoneAllocator::addBlock(MemBlock *b)
+{
+  b->newer = 0;
+  b->older = currentBlock;
+  if (currentBlock)
+    b->older->newer = b;
+  currentBlock = b;
+  num_blocks++;
+  /* If we either have no hashList at all, or since it's last construction
+     there are now many more blocks we reconstruct the list.  But don't
+     make it larger than a certain maximum.  */
+  if (hashList && ((num_blocks / 4) > hashSize && hashSize < 64*1024))
+    hashDirty = true;
+  /* Only insert this block into the hashlists, if we aren't going to
+     reconstruct them anyway.  */
+  if (hashList && !hashDirty)
+    insertHash (b);
+}
+
+void KZoneAllocator::initHash()
+{
+  if (hashList) {
+    for (int i = 0; i < hashSize; i++)
+      delete hashList[i];
+    delete [] hashList;
+    hashList = 0;
+  }
+  hashSize = 1;
+  while (hashSize < num_blocks)
+    hashSize <<= 1;
+  if (hashSize < 1024)
+    hashSize = 1024;
+  if (hashSize > 64*1024)
+    hashSize = 64*1024;
+  hashList = new QValueList<MemBlock *> *[hashSize];
+  memset (hashList, 0, sizeof(QValueList<MemBlock*> *) * hashSize);
+  hashDirty = false;
+  for (MemBlock *b = currentBlock; b; b = b->older)
+    insertHash(b);
+}
+
+void KZoneAllocator::delBlock(MemBlock *b)
+{
+  /* Update also the hashlists if we aren't going to reconstruct them
+     soon.  */
+  if (hashList && !hashDirty) {
+    unsigned int adr = ((unsigned int)b->begin) & (~(blockSize - 1));
+    unsigned int end = ((unsigned int)b->begin) + blockSize;
+    while (adr < end) {
+      unsigned int key = adr >> log2;
+      key = key & (hashSize - 1);
+      if (hashList[key]) {
+	QValueList<MemBlock *> *list = hashList[key];
+	QValueList<MemBlock *>::Iterator it = list->begin();
+	QValueList<MemBlock *>::Iterator endit = list->end();
+	for (; it != endit; ++it)
+	  if (*it == b) {
+	    list->remove(it);
+	    break;
+	  }
+      }
+      adr += blockSize;
     }
+  }
+  if (b->older)
+    b->older->newer = b->newer;
+  if (b->newer)
+    b->newer->older = b->older;
+  if (b == currentBlock) {
+    currentBlock = 0;
+    blockOffset = blockSize;
+  }
+  delete b;
+  num_blocks--;
 }
 
 void *
 KZoneAllocator::allocate(size_t _size)
 {
    // Use the size of (void *) as alignment
-   const size_t alignment = sizeof(void *);
-   _size = (_size + alignment - 1) & ~(alignment - 1);   
+   const size_t alignment = sizeof(void *) - 1;
+   _size = (_size + alignment) & ~alignment;   
 
-   if ((long) _size + blockOffset > blockSize)
+   if ((unsigned long) _size + blockOffset > blockSize)
    {
-      currentBlock = new char[blockSize];
-      memoryBlocks.append(currentBlock);
+      if (_size > blockSize) {
+	qDebug("KZoneAllocator: allocating more than %u bytes", blockSize);
+	return 0;
+      }
+      addBlock(new MemBlock(blockSize));
       blockOffset = 0;
-      kdDebug () << "Allocating block #" <<  memoryBlocks.count() << endl;
-   } 
-   void *result = (void *)(currentBlock+blockOffset);
+      //qDebug ("Allocating block #%d (%x)\n", num_blocks, currentBlock->begin);
+   }
+   void *result = (void *)(currentBlock->begin+blockOffset);
+   currentBlock->ref++;
    blockOffset += _size;
    return result;
 }
 
+void
+KZoneAllocator::deallocate(void *ptr)
+{
+  if (hashDirty)
+    initHash();
+
+  unsigned int key = (((unsigned int)ptr) >> log2) & (hashSize - 1);
+  QValueList<MemBlock *> *list = hashList[key];
+  if (!list) {
+    /* Can happen with certain usage pattern of intermixed free_since()
+       and deallocate().  */
+    //qDebug("Uhoh");
+    return;
+  }
+  QValueList<MemBlock*>::ConstIterator it = list->begin();
+  QValueList<MemBlock*>::ConstIterator endit = list->end();
+  for (; it != endit; ++it) {
+    MemBlock *cur = *it;
+    if (cur->is_in(ptr)) {
+      if (!--cur->ref) {
+	if (cur != currentBlock)
+	  delBlock (cur);
+	else
+	  blockOffset = 0;
+      }
+      return;
+    }
+  }
+  /* Can happen with certain usage pattern of intermixed free_since()
+     and deallocate().  */
+  //qDebug("Uhoh2");
+}
+
+void
+KZoneAllocator::free_since(void *ptr)
+{
+  /* If we have a hashList and it's not yet dirty, see, if we will dirty
+     it by removing too many blocks.  This will make the below delBlock()s
+     faster.  */
+  if (hashList && !hashDirty)
+    {
+      const MemBlock *b;
+      unsigned int removed = 0;
+      for (b = currentBlock; b; b = b->older, removed++)
+	if (b->is_in (ptr))
+	  break;
+      if (hashSize >= 4 * (num_blocks - removed))
+        hashDirty = true;
+    }
+  while (currentBlock && !currentBlock->is_in(ptr)) {
+    currentBlock = currentBlock->older;
+    delBlock (currentBlock->newer);
+  }
+  blockOffset = ((char*)ptr) - currentBlock->begin;
+}
Index: kallocator.h
===================================================================
RCS file: /home/kde/kdelibs/kdecore/kallocator.h,v
retrieving revision 1.6
diff -u -p -r1.6 kallocator.h
--- kallocator.h	2001/12/06 13:03:57	1.6
+++ kallocator.h	2002/03/07 07:21:36
@@ -2,6 +2,7 @@
     This file is part of the KDE libraries
 
     Copyright (C) 1999 Waldo Bastian (bastian@kde.org)
+    Copyright (C) 2002 Michael Matz (matz@kde.org)
               
     This library is free software; you can redistribute it and/or
     modify it under the terms of the GNU Library General Public
@@ -26,17 +27,21 @@
 #ifndef KALLOCATOR_H
 #define KALLOCATOR_H
 
-#include <stdio.h>
-#include <qptrlist.h>
+#include <qvaluelist.h>
 
 class KZoneAllocatorPrivate;
 
+
 /**
  * Memory allocator for large groups of small objects.
  * This should be used for large groups of objects that are created and
  * destroyed together. When used carefully for this purpose it is faster
- * and more memory efficient than malloc.
- * @author Waldo Bastian <bastian@kde.org>
+ * and more memory efficient than malloc.  Additionally to a usual obstack
+ * like allocator you can also free the objects individually.  Because it
+ * does no compaction it still is faster then malloc()/free().  Depending
+ * on the exact usage pattern that might come at the expense of some
+ * memory though.
+ * @author Waldo Bastian <bastian@kde.org>, Michael Matz <matz@kde.org>
  * @version $Id: kallocator.h,v 1.6 2001/12/06 13:03:57 faure Exp $
  */
 class KZoneAllocator
@@ -46,7 +51,7 @@ public:
      * Creates a KZoneAllocator object.
      * @param _blockSize Size in bytes of the blocks requested from malloc.
      */
-    KZoneAllocator(long _blockSize = 128*1024);
+    KZoneAllocator(unsigned long _blockSize = 8*1024);
 
     /**
      * Destructs the ZoneAllocator and free all memory allocated by it.
@@ -55,15 +60,70 @@ public:
 
     /**
      * Allocates a memory block.
-     * @param _size Size in bytes of the memory block. Memory is not aligned!
+     * @param _size Size in bytes of the memory block. Memory is aligned to
+     * the size of a pointer.
      */
     void* allocate(size_t _size);
 
+    /**
+     * Gives back a block returned by @ref allocate() to the zone
+     * allocator, and possibly deallocates the block holding it (when it's
+     * empty).  The first @ref deallocate() after many @ref allocate() calls
+     * (or the first at all) builds an internal data structure for speeding
+     * up deallocation.  The consistency of that structure is maintained
+     * from then on (by @ref allocate() and @ref deallocate()) unless many
+     * more objects are allocated without any intervening deallocation, in
+     * which case it's thrown away and rebuilt at the next @ref deallocate().
+     *
+     * The effect of this is, that such initial @ref deallocate() calls take
+     * more time then the normal calls, and that after this list is built, i.e.
+     * generally if @ref deallocate() is used at all, also allocate() is a
+     * little bit slower.  This means, that if you want to squeeze out the last
+     * bit performance you would want to use KZoneAllocator as an obstack, i.e.
+     * just use the functions @ref allocate() and @ref free_since().  All the
+     * remaining memory is returned to the system if the zone allocator
+     * is destroyed.
+     * @param ptr Pointer as returned by @ref allocate().
+     */
+    void deallocate(void *ptr);
+
+    /**
+     * Deallocate many objects at once.
+     * @ref free_since() deallocates all objects allocated after @p ptr, 
+     * @em including @p ptr itself.
+     * @param ptr Pointer as returned by @ref allocate().  It acts like
+     * a kind of mark of a certain position in the stack of all objects,
+     * off which you can throw away everything above that mark.
+     *
+     * The intended use is something along the lines of:
+     * <pre>
+     * KZoneAllocator alloc(8192);
+     * void *remember_me = alloc.allocate(0);
+     * for (int i = 0; i < 1000; i++)
+     *   do_something_with (alloc.allocate(12));
+     * alloc.free_since (remember_me);
+     * </pre>
+     * Note, that we don't need to remember all the pointers to the 12-byte
+     * objects for freeing them.  The @ref free_since() does deallocate them
+     * all at once.
+     */
+    void free_since(void *ptr);
+
 protected:
-    long blockSize;
-    QPtrList<char> memoryBlocks;
-    char *currentBlock;
-    long blockOffset;
+    class MemBlock;
+    typedef QValueList<MemBlock *> MemList;
+    void addBlock(MemBlock *b);
+    void delBlock(MemBlock *b);
+    void insertHash(MemBlock *b);
+    void initHash();
+    MemBlock *currentBlock;
+    unsigned long blockSize;
+    unsigned long blockOffset;
+    unsigned int log2;
+    unsigned int num_blocks;
+    MemList **hashList;
+    unsigned int hashSize;
+    bool hashDirty;
 private:
     KZoneAllocatorPrivate *d;
 };
Index: kcompletion.cpp
===================================================================
RCS file: /home/kde/kdelibs/kdecore/kcompletion.cpp,v
retrieving revision 1.49
diff -u -p -r1.49 kcompletion.cpp
--- kcompletion.cpp	2002/03/03 21:20:25	1.49
+++ kcompletion.cpp	2002/03/07 07:21:36
@@ -546,15 +546,14 @@ void KCompletion::extractStringsFromNode
         return;
 
     // kDebug() << "Beginning: " << beginning << endl;
-    KCompTreeChildren::ConstIterator it;
     const KCompTreeChildren *list = node->children();
     QString string;
     QString w;
 
     // loop thru all children
-    for ( it = list->begin(); it != list->end(); ++it ) {
+    for ( KCompTreeNode *cur = list->begin(); cur ; cur = cur->next) {
         string = beginning;
-        node = *it;
+	node = cur;
 	if ( !node->isNull() )
 	    string += *node;
 
@@ -660,9 +659,12 @@ void KCompletion::doBeep( BeepMode mode 
 KCompTreeNode::~KCompTreeNode()
 {
     // delete all children
-    KCompTreeChildren::Iterator it;
-    for ( it = myChildren.begin(); it != myChildren.end(); ++it )
-        delete *it;
+    KCompTreeNode *cur = myChildren.begin();
+    while (cur) {
+        KCompTreeNode * next = cur->next;
+        delete myChildren.remove(cur);
+        cur = next;
+    }
 }
 
 
@@ -676,14 +678,19 @@ KCompTreeNode * KCompTreeNode::insert( c
 
 	// FIXME, first (slow) sorted insertion implementation
 	if ( sorted ) {
-	    KCompTreeChildren::Iterator it = myChildren.begin();
-	    while ( it != myChildren.end() ) {
-	        if ( ch > *(*it) )
-		    ++it;
-		else
+	    KCompTreeNode * prev = 0;
+	    KCompTreeNode * cur = myChildren.begin();
+	    while ( cur ) {
+	        if ( ch > *cur ) {
+		    prev = cur;
+		    cur = cur->next;
+		} else
 		    break;
 	    }
-	    myChildren.insert( it, child );
+	    if (prev)
+	        myChildren.insert( prev, child );
+	    else
+	        myChildren.prepend(child);
 	}
 
 	else
@@ -705,8 +712,7 @@ void KCompTreeNode::remove( const QStrin
 
     if ( string.isEmpty() ) {
         child = find( 0x0 );
-        delete child;
-        myChildren.remove( child );
+        delete myChildren.remove( child );
         return;
     }
 
@@ -715,8 +721,7 @@ void KCompTreeNode::remove( const QStrin
     if ( child ) {
         child->remove( string.right( string.length() -1 ) );
         if ( child->myChildren.count() == 0 ) {
-            delete child;
-            myChildren.remove( child );
+            delete myChildren.remove( child );
         }
     }
 }
@@ -786,6 +791,79 @@ void KCompletionMatches::removeDuplicate
         }
     }
 }
+
+void KCompTreeNodeList::append(KCompTreeNode *item)
+{
+    m_count++;
+    if (!last) {
+	last = item;
+	last->next = 0;
+	first = item;
+	return;
+    }
+    last->next = item;
+    item->next = 0;
+    last = item;
+}
+
+void KCompTreeNodeList::prepend(KCompTreeNode *item)
+{
+    m_count++;
+    if (!last) {
+	last = item;
+	last->next = 0;
+	first = item;
+	return;
+    }
+    item->next = first;
+    first = item;
+}
+
+void KCompTreeNodeList::insert(KCompTreeNode *after, KCompTreeNode *item)
+{
+    if (!after) {
+	append(item);
+	return;
+    }
+
+    m_count++;
+
+    item->next = after->next;
+    after->next = item;
+
+    if (after == last)
+	last = item;
+}
+
+KCompTreeNode *KCompTreeNodeList::remove(KCompTreeNode *item)
+{
+    if (!first || !item)
+	return 0;
+    KCompTreeNode *cur = 0;
+
+    if (item == first)
+	first = first->next;
+    else {
+	cur = first;
+	while (cur && cur->next != item) cur = cur->next;
+	if (!cur)
+	    return 0;
+	cur->next = item->next;
+    }
+    if (item == last)
+	last = cur;
+    m_count--;
+    return item;
+}
+
+KCompTreeNode *KCompTreeNodeList::at(uint index) const
+{
+    KCompTreeNode *cur = first;
+    while (index-- && cur) cur = cur->next;
+    return cur;
+}
+
+KZoneAllocator KCompTreeNode::alloc(8192);
 
 void KCompletion::virtual_hook( int, void* )
 { /*BASE::virtual_hook( id, data );*/ }
Index: kcompletion_private.h
===================================================================
RCS file: /home/kde/kdelibs/kdecore/kcompletion_private.h,v
retrieving revision 1.12
diff -u -p -r1.12 kcompletion_private.h
--- kcompletion_private.h	2002/01/11 16:12:42	1.12
+++ kcompletion_private.h	2002/03/07 07:21:36
@@ -25,8 +25,30 @@
 #include <ksortablevaluelist.h>
 
 class KCompTreeNode;
-typedef QValueList<KCompTreeNode *> KCompTreeChildren;
 
+#include <kallocator.h>
+
+class KCompTreeNodeList
+{
+public:
+    KCompTreeNodeList() : first(0), last(0), m_count(0) {}
+    KCompTreeNode *begin() const { return first; }
+    KCompTreeNode *end() const { return last; }
+
+    KCompTreeNode *at(uint index) const;
+    void append(KCompTreeNode *item); 
+    void prepend(KCompTreeNode *item); 
+    void insert(KCompTreeNode *after, KCompTreeNode *item);
+    KCompTreeNode *remove(KCompTreeNode *item);
+    uint count() const { return m_count; }
+
+private:
+    KCompTreeNode *first, *last;
+    uint m_count;
+};
+
+typedef KCompTreeNodeList KCompTreeChildren;
+
 /**
  * A helper class for KCompletion. Implements a tree of QChar.
  *
@@ -58,6 +80,9 @@ typedef QValueList<KCompTreeNode *> KCom
  */
 class KCompTreeNode : public QChar
 {
+  friend class KCompTreeNodeList;
+  friend class KCompletion;
+
 public:
     KCompTreeNode() : QChar(), myWeight(0) {}
     KCompTreeNode( const QChar& ch, uint weight = 0 )
@@ -65,15 +90,19 @@ public:
           myWeight( weight ) {}
     ~KCompTreeNode();
 
+    void * operator new( size_t s ) {
+      return alloc.allocate( s );
+    }
+    void operator delete( void * s ) {
+      alloc.deallocate( s );
+    }
+
     // Returns a child of this node matching ch, if available.
     // Otherwise, returns 0L
     inline KCompTreeNode * find( const QChar& ch ) const {
-	KCompTreeChildren::ConstIterator it;
-	for ( it = myChildren.begin(); it != myChildren.end(); ++it )
-	    if ( *(*it) == ch )
-		return *it;
-
-	return 0L;
+      KCompTreeNode * cur = myChildren.begin();
+      while (cur && (*cur != ch)) cur = cur->next;
+      return cur;
     }
     KCompTreeNode *	insert( const QChar&, bool sorted );
     void 		remove( const QString& );
@@ -90,20 +119,22 @@ public:
 	return &myChildren;
     }
     inline const KCompTreeNode * childAt(int index) const {
-	return myChildren[index];
+	return myChildren.at(index);
     }
     inline const KCompTreeNode * firstChild() const {
-	return myChildren.first();
+	return myChildren.begin();
     }
     inline const KCompTreeNode * lastChild()  const {
-	return myChildren.last();
+	return myChildren.end();
     }
 
 private:
     uint myWeight;
-    KCompTreeChildren	myChildren;
-
+    KCompTreeNodeList	myChildren;
+    KCompTreeNode *next;
+    static KZoneAllocator alloc;
 };
+
 
 
 // some more helper stuff