rtpkeyhashtable.h

Go to the documentation of this file.
00001 /*
00002 
00003   This file is a part of JRTPLIB
00004   Copyright (c) 1999-2007 Jori Liesenborgs
00005 
00006   Contact: jori.liesenborgs@gmail.com
00007 
00008   This library was developed at the "Expertisecentrum Digitale Media"
00009   (http://www.edm.uhasselt.be), a research center of the Hasselt University
00010   (http://www.uhasselt.be). The library is based upon work done for 
00011   my thesis at the School for Knowledge Technology (Belgium/The Netherlands).
00012 
00013   Permission is hereby granted, free of charge, to any person obtaining a
00014   copy of this software and associated documentation files (the "Software"),
00015   to deal in the Software without restriction, including without limitation
00016   the rights to use, copy, modify, merge, publish, distribute, sublicense,
00017   and/or sell copies of the Software, and to permit persons to whom the
00018   Software is furnished to do so, subject to the following conditions:
00019 
00020   The above copyright notice and this permission notice shall be included
00021   in all copies or substantial portions of the Software.
00022 
00023   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
00024   OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00025   FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
00026   THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00027   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
00028   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
00029   IN THE SOFTWARE.
00030 
00031 */
00032 
00037 #ifndef RTPKEYHASHTABLE_H
00038 
00039 #define RTPKEYHASHTABLE_H
00040 
00041 #include "rtpconfig.h"
00042 #include "rtperrors.h"
00043 #include "rtpmemoryobject.h"
00044 
00045 #ifdef RTPDEBUG
00046 #include <iostream>
00047 #endif // RTPDEBUG
00048 
00049 template<class Key,class Element,class GetIndex,int hashsize>
00050 class RTPKeyHashTable : public RTPMemoryObject
00051 {
00052 public:
00053         RTPKeyHashTable(RTPMemoryManager *mgr = 0,int memtype = RTPMEM_TYPE_OTHER);
00054         ~RTPKeyHashTable()                                      { Clear(); }
00055 
00056         void GotoFirstElement()                                 { curhashelem = firsthashelem; }
00057         void GotoLastElement()                                  { curhashelem = lasthashelem; }
00058         bool HasCurrentElement()                                { return (curhashelem == 0)?false:true; }
00059         int DeleteCurrentElement();
00060         Element &GetCurrentElement()                            { return curhashelem->GetElement(); }
00061         Key &GetCurrentKey()                                    { return curhashelem->GetKey(); }
00062         int GotoElement(const Key &k);
00063         bool HasElement(const Key &k);
00064         void GotoNextElement();
00065         void GotoPreviousElement();
00066         void Clear();
00067 
00068         int AddElement(const Key &k,const Element &elem);
00069         int DeleteElement(const Key &k);
00070 
00071 #ifdef RTPDEBUG
00072         void Dump();
00073 #endif // RTPDEBUG
00074 private:
00075         class HashElement
00076         {
00077         public:
00078                 HashElement(const Key &k,const Element &e,int index):key(k),element(e) { hashprev = 0; hashnext = 0; listnext = 0; listprev = 0; hashindex = index; }
00079                 int GetHashIndex()                                              { return hashindex; }
00080                 Key &GetKey()                                                   { return key; }
00081                 Element &GetElement()                                           { return element; }
00082 #ifdef RTPDEBUG
00083                 void Dump()                                                     { std::cout << "\tHash index " << hashindex << " | Key " << key << " | Element " << element << std::endl; }
00084 #endif // RTPDEBUG
00085         private:
00086                 int hashindex;
00087                 Key key;
00088                 Element element;
00089         public:
00090                 HashElement *hashprev,*hashnext;
00091                 HashElement *listprev,*listnext;
00092         };
00093 
00094         HashElement *table[hashsize];
00095         HashElement *firsthashelem,*lasthashelem;
00096         HashElement *curhashelem;
00097 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
00098         int memorytype;
00099 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
00100 };
00101 
00102 template<class Key,class Element,class GetIndex,int hashsize>
00103 inline RTPKeyHashTable<Key,Element,GetIndex,hashsize>::RTPKeyHashTable(RTPMemoryManager *mgr,int memtype) : RTPMemoryObject(mgr)
00104 {
00105         for (int i = 0 ; i < hashsize ; i++)
00106                 table[i] = 0;
00107         firsthashelem = 0;
00108         lasthashelem = 0;
00109 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
00110         memorytype = memtype;
00111 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
00112 }
00113 
00114 template<class Key,class Element,class GetIndex,int hashsize>
00115 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::DeleteCurrentElement()
00116 {
00117         if (curhashelem)
00118         {
00119                 HashElement *tmp1,*tmp2;
00120                 int index;
00121                 
00122                 // First, relink elements in current hash bucket
00123                 
00124                 index = curhashelem->GetHashIndex();
00125                 tmp1 = curhashelem->hashprev;
00126                 tmp2 = curhashelem->hashnext;
00127                 if (tmp1 == 0) // no previous element in hash bucket
00128                 {
00129                         table[index] = tmp2;
00130                         if (tmp2 != 0)
00131                                 tmp2->hashprev = 0;
00132                 }
00133                 else // there is a previous element in the hash bucket
00134                 {
00135                         tmp1->hashnext = tmp2;
00136                         if (tmp2 != 0)
00137                                 tmp2->hashprev = tmp1;
00138                 }
00139 
00140                 // Relink elements in list
00141                 
00142                 tmp1 = curhashelem->listprev;
00143                 tmp2 = curhashelem->listnext;
00144                 if (tmp1 == 0) // curhashelem is first in list
00145                 {
00146                         firsthashelem = tmp2;
00147                         if (tmp2 != 0)
00148                                 tmp2->listprev = 0;
00149                         else // curhashelem is also last in list
00150                                 lasthashelem = 0;       
00151                 }
00152                 else
00153                 {
00154                         tmp1->listnext = tmp2;
00155                         if (tmp2 != 0)
00156                                 tmp2->listprev = tmp1;
00157                         else // curhashelem is last in list
00158                                 lasthashelem = tmp1;
00159                 }
00160                 
00161                 // finally, with everything being relinked, we can delete curhashelem
00162                 RTPDelete(curhashelem,GetMemoryManager());
00163                 curhashelem = tmp2; // Set to next element in list
00164         }
00165         else
00166                 return ERR_RTP_KEYHASHTABLE_NOCURRENTELEMENT;
00167         return 0;
00168 }
00169         
00170 template<class Key,class Element,class GetIndex,int hashsize>
00171 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::GotoElement(const Key &k)
00172 {
00173         int index;
00174         bool found;
00175         
00176         index = GetIndex::GetIndex(k);
00177         if (index >= hashsize)
00178                 return ERR_RTP_KEYHASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
00179         
00180         curhashelem = table[index]; 
00181         found = false;
00182         while(!found && curhashelem != 0)
00183         {
00184                 if (curhashelem->GetKey() == k)
00185                         found = true;
00186                 else
00187                         curhashelem = curhashelem->hashnext;
00188         }
00189         if (!found)
00190                 return ERR_RTP_KEYHASHTABLE_KEYNOTFOUND;
00191         return 0;
00192 }
00193 
00194 template<class Key,class Element,class GetIndex,int hashsize>
00195 inline bool RTPKeyHashTable<Key,Element,GetIndex,hashsize>::HasElement(const Key &k)
00196 {
00197         int index;
00198         bool found;
00199         HashElement *tmp;
00200         
00201         index = GetIndex::GetIndex(k);
00202         if (index >= hashsize)
00203                 return false;
00204         
00205         tmp = table[index]; 
00206         found = false;
00207         while(!found && tmp != 0)
00208         {
00209                 if (tmp->GetKey() == k)
00210                         found = true;
00211                 else
00212                         tmp = tmp->hashnext;
00213         }
00214         return found;
00215 }
00216 
00217 template<class Key,class Element,class GetIndex,int hashsize>
00218 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::GotoNextElement()
00219 {
00220         if (curhashelem)
00221                 curhashelem = curhashelem->listnext;
00222 }
00223 
00224 template<class Key,class Element,class GetIndex,int hashsize>
00225 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::GotoPreviousElement()
00226 {
00227         if (curhashelem)
00228                 curhashelem = curhashelem->listprev;
00229 }
00230 
00231 template<class Key,class Element,class GetIndex,int hashsize>
00232 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::Clear()
00233 {
00234         HashElement *tmp1,*tmp2;
00235         
00236         for (int i = 0 ; i < hashsize ; i++)
00237                 table[i] = 0;
00238         
00239         tmp1 = firsthashelem;
00240         while (tmp1 != 0)
00241         {
00242                 tmp2 = tmp1->listnext;
00243                 RTPDelete(tmp1,GetMemoryManager());
00244                 tmp1 = tmp2;
00245         }
00246         firsthashelem = 0;
00247         lasthashelem = 0;
00248 }
00249 
00250 template<class Key,class Element,class GetIndex,int hashsize>
00251 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::AddElement(const Key &k,const Element &elem)
00252 {
00253         int index;
00254         bool found;
00255         HashElement *e,*newelem;
00256         
00257         index = GetIndex::GetIndex(k);
00258         if (index >= hashsize)
00259                 return ERR_RTP_KEYHASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
00260         
00261         e = table[index];
00262         found = false;
00263         while(!found && e != 0)
00264         {
00265                 if (e->GetKey() == k)
00266                         found = true;
00267                 else
00268                         e = e->hashnext;
00269         }
00270         if (found)
00271                 return ERR_RTP_KEYHASHTABLE_KEYALREADYEXISTS;
00272         
00273         // Okay, the key doesn't exist, so we can add the new element in the hash table
00274         
00275         newelem = RTPNew(GetMemoryManager(),memorytype) HashElement(k,elem,index);
00276         if (newelem == 0)
00277                 return ERR_RTP_OUTOFMEM;
00278 
00279         e = table[index];
00280         table[index] = newelem;
00281         newelem->hashnext = e;
00282         if (e != 0)
00283                 e->hashprev = newelem;
00284         
00285         // Now, we still got to add it to the linked list
00286         
00287         if (firsthashelem == 0)
00288         {
00289                 firsthashelem = newelem;
00290                 lasthashelem = newelem;
00291         }
00292         else // there already are some elements in the list
00293         {
00294                 lasthashelem->listnext = newelem;
00295                 newelem->listprev = lasthashelem;
00296                 lasthashelem = newelem;
00297         }
00298         return 0;
00299 }
00300 
00301 template<class Key,class Element,class GetIndex,int hashsize>
00302 inline int RTPKeyHashTable<Key,Element,GetIndex,hashsize>::DeleteElement(const Key &k)
00303 {
00304         int status;
00305 
00306         status = GotoElement(k);
00307         if (status < 0)
00308                 return status;
00309         return DeleteCurrentElement();
00310 }
00311 
00312 #ifdef RTPDEBUG
00313 template<class Key,class Element,class GetIndex,int hashsize>
00314 inline void RTPKeyHashTable<Key,Element,GetIndex,hashsize>::Dump()
00315 {
00316         HashElement *e;
00317         
00318         std::cout << "DUMPING TABLE CONTENTS:" << std::endl;
00319         for (int i = 0 ; i < hashsize ; i++)
00320         {
00321                 e = table[i];
00322                 while (e != 0)
00323                 {
00324                         e->Dump();
00325                         e = e->hashnext;
00326                 }
00327         }
00328         
00329         std::cout << "DUMPING LIST CONTENTS:" << std::endl;
00330         e = firsthashelem;
00331         while (e != 0)
00332         {
00333                 e->Dump();
00334                 e = e->listnext;
00335         }
00336 }
00337 #endif // RTPDEBUG
00338 
00339 #endif // RTPKEYHASHTABLE_H

Generated on Thu Feb 8 16:22:05 2007 for jrtplib by  doxygen 1.5.1