kmdict.cpp
00001 /* simple hash table for kmail. inspired by TQDict */ 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 }