kmail

kmdict.cpp

Go to the documentation of this file.
00001 /* simple hash table for kmail.  inspired by QDict */
00002 /* Author: Ronen Tzur <rtzur@shani.net> */
00003 
00004 #ifdef HAVE_CONFIG_H
00005 #include <config.h>
00006 #endif
00007 
00008 #include "kmdict.h"
00009 #include "kmglobal.h"
00010 #include <kdebug.h>
00011 
00012 #include <string.h>
00013 //-----------------------------------------------------------------------------
00014 
00015 KMDict::KMDict( int size )
00016 {
00017   init( ( int ) KMail::nextPrime( size ) );
00018   //kdDebug( 5006 ) << "KMMDict::KMDict Size: " << mSize << endl;
00019 }
00020 
00021 //-----------------------------------------------------------------------------
00022 
00023 KMDict::~KMDict()
00024 {
00025   clear();
00026 }
00027 
00028 //-----------------------------------------------------------------------------
00029 
00030 void KMDict::init(int size)
00031 {
00032   mSize = size;
00033   mVecs = new KMDictItem *[mSize];
00034   memset(mVecs, 0, mSize * sizeof(KMDictItem *));
00035 }
00036 
00037 //-----------------------------------------------------------------------------
00038 
00039 void KMDict::clear()
00040 {
00041   if (!mVecs)
00042     return;
00043   for (int i = 0; i < mSize; i++) {
00044     KMDictItem *item = mVecs[i];
00045     while (item) {
00046       KMDictItem *nextItem = item->next;
00047       delete item;
00048       item = nextItem;
00049     }
00050   }
00051   delete [] mVecs;
00052   mVecs = 0;
00053 }
00054 
00055 //-----------------------------------------------------------------------------
00056 
00057 void KMDict::replace( long key, KMDictItem *item )
00058 {
00059   insert( key, item );
00060   removeFollowing( item, key );           // remove other items with same key
00061 }
00062 
00063 //-----------------------------------------------------------------------------
00064 
00065 
00066 void KMDict::insert( long key, KMDictItem *item )
00067 {
00068   item->key = key;
00069   int idx = (unsigned long)key % mSize; // insert in
00070   item->next = mVecs[idx];              // appropriate
00071   mVecs[idx] = item;                    // column
00072 }
00073 
00074 //-----------------------------------------------------------------------------
00075 
00076 void KMDict::remove(long key)
00077 {
00078   int idx = (unsigned long)key % mSize;
00079   KMDictItem *item = mVecs[idx];
00080 
00081   if (item) {
00082     if (item->key == key) {             // if first in the column
00083       mVecs[idx] = item->next;
00084       delete item;
00085     } else
00086       removeFollowing(item, key);       // if deep in the column
00087   }
00088 }
00089 
00090 //-----------------------------------------------------------------------------
00091 
00092 void KMDict::removeFollowing(KMDictItem *item, long key)
00093 {
00094   while (item) {
00095     KMDictItem *itemNext = item->next;
00096     if (itemNext && itemNext->key == key) {
00097       KMDictItem *itemNextNext = itemNext->next;
00098       delete itemNext;
00099       item->next = itemNextNext;
00100     } else
00101       item = itemNext;
00102   }
00103 }
00104 
00105 //-----------------------------------------------------------------------------
00106 
00107 KMDictItem *KMDict::find(long key)
00108 {
00109   int idx = (unsigned long)key % mSize;
00110   KMDictItem *item = mVecs[idx];
00111   while (item) {
00112     if (item->key == key)
00113       break;
00114     item = item->next;
00115   }
00116   return item;
00117 }