rtphashtable.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 
00033 #ifndef RTPHASHTABLE_H
00034 
00035 #define RTPHASHTABLE_H
00036 
00041 #include "rtperrors.h"
00042 #include "rtpmemoryobject.h"
00043 
00044 #ifdef RTPDEBUG
00045 #include <iostream>
00046 #endif // RTPDEBUG
00047 
00048 //template<class Element,int GetIndex(const Element &k),int hashsize>
00049 template<class Element,class GetIndex,int hashsize>
00050 class RTPHashTable : public RTPMemoryObject
00051 {
00052 public:
00053         RTPHashTable(RTPMemoryManager *mgr = 0, int memtype = RTPMEM_TYPE_OTHER);
00054         ~RTPHashTable()                                         { 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         int GotoElement(const Element &e);
00062         bool HasElement(const Element &e);
00063         void GotoNextElement();
00064         void GotoPreviousElement();
00065         void Clear();
00066 
00067         int AddElement(const Element &elem);
00068         int DeleteElement(const Element &elem);
00069 
00070 #ifdef RTPDEBUG
00071         void Dump();
00072 #endif // RTPDEBUG
00073 private:
00074         class HashElement
00075         {
00076         public:
00077                 HashElement(const Element &e,int index):element(e) { hashprev = 0; hashnext = 0; listnext = 0; listprev = 0; hashindex = index; }
00078                 int GetHashIndex()                                              { return hashindex; }
00079                 Element &GetElement()                                           { return element; }
00080 #ifdef RTPDEBUG
00081                 void Dump()                                                     { std::cout << "\tHash index " << hashindex << " | Element " << element << std::endl; }
00082 #endif // RTPDEBUG
00083         private:
00084                 int hashindex;
00085                 Element element;
00086         public:
00087                 HashElement *hashprev,*hashnext;
00088                 HashElement *listprev,*listnext;
00089         };
00090 
00091         HashElement *table[hashsize];
00092         HashElement *firsthashelem,*lasthashelem;
00093         HashElement *curhashelem;
00094 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
00095         int memorytype;
00096 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
00097 };
00098 
00099 template<class Element,class GetIndex,int hashsize>
00100 inline RTPHashTable<Element,GetIndex,hashsize>::RTPHashTable(RTPMemoryManager *mgr,int memtype) : RTPMemoryObject(mgr)
00101 {
00102         for (int i = 0 ; i < hashsize ; i++)
00103                 table[i] = 0;
00104         firsthashelem = 0;
00105         lasthashelem = 0;
00106 #ifdef RTP_SUPPORT_MEMORYMANAGEMENT
00107         memorytype = memtype;
00108 #endif // RTP_SUPPORT_MEMORYMANAGEMENT
00109 }
00110 
00111 template<class Element,class GetIndex,int hashsize>
00112 inline int RTPHashTable<Element,GetIndex,hashsize>::DeleteCurrentElement()
00113 {
00114         if (curhashelem)
00115         {
00116                 HashElement *tmp1,*tmp2;
00117                 int index;
00118                 
00119                 // First, relink elements in current hash bucket
00120                 
00121                 index = curhashelem->GetHashIndex();
00122                 tmp1 = curhashelem->hashprev;
00123                 tmp2 = curhashelem->hashnext;
00124                 if (tmp1 == 0) // no previous element in hash bucket
00125                 {
00126                         table[index] = tmp2;
00127                         if (tmp2 != 0)
00128                                 tmp2->hashprev = 0;
00129                 }
00130                 else // there is a previous element in the hash bucket
00131                 {
00132                         tmp1->hashnext = tmp2;
00133                         if (tmp2 != 0)
00134                                 tmp2->hashprev = tmp1;
00135                 }
00136 
00137                 // Relink elements in list
00138                 
00139                 tmp1 = curhashelem->listprev;
00140                 tmp2 = curhashelem->listnext;
00141                 if (tmp1 == 0) // curhashelem is first in list
00142                 {
00143                         firsthashelem = tmp2;
00144                         if (tmp2 != 0)
00145                                 tmp2->listprev = 0;
00146                         else // curhashelem is also last in list
00147                                 lasthashelem = 0;       
00148                 }
00149                 else
00150                 {
00151                         tmp1->listnext = tmp2;
00152                         if (tmp2 != 0)
00153                                 tmp2->listprev = tmp1;
00154                         else // curhashelem is last in list
00155                                 lasthashelem = tmp1;
00156                 }
00157                 
00158                 // finally, with everything being relinked, we can delete curhashelem
00159                 RTPDelete(curhashelem,GetMemoryManager());
00160                 curhashelem = tmp2; // Set to next element in the list
00161         }
00162         else
00163                 return ERR_RTP_HASHTABLE_NOCURRENTELEMENT;
00164         return 0;
00165 }
00166 
00167 template<class Element,class GetIndex,int hashsize>
00168 inline int RTPHashTable<Element,GetIndex,hashsize>::GotoElement(const Element &e)
00169 {
00170         int index;
00171         bool found;
00172         
00173         index = GetIndex::GetIndex(e);
00174         if (index >= hashsize)
00175                 return ERR_RTP_HASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
00176         
00177         curhashelem = table[index]; 
00178         found = false;
00179         while(!found && curhashelem != 0)
00180         {
00181                 if (curhashelem->GetElement() == e)
00182                         found = true;
00183                 else
00184                         curhashelem = curhashelem->hashnext;
00185         }
00186         if (!found)
00187                 return ERR_RTP_HASHTABLE_ELEMENTNOTFOUND;
00188         return 0;
00189 }
00190 
00191 template<class Element,class GetIndex,int hashsize>
00192 inline bool RTPHashTable<Element,GetIndex,hashsize>::HasElement(const Element &e)
00193 {
00194         int index;
00195         bool found;
00196         HashElement *tmp;
00197         
00198         index = GetIndex::GetIndex(e);
00199         if (index >= hashsize)
00200                 return false;
00201         
00202         tmp = table[index]; 
00203         found = false;
00204         while(!found && tmp != 0)
00205         {
00206                 if (tmp->GetElement() == e)
00207                         found = true;
00208                 else
00209                         tmp = tmp->hashnext;
00210         }
00211         return found;
00212 }
00213 
00214 template<class Element,class GetIndex,int hashsize>
00215 inline void RTPHashTable<Element,GetIndex,hashsize>::GotoNextElement()
00216 {
00217         if (curhashelem)
00218                 curhashelem = curhashelem->listnext;
00219 }
00220 
00221 template<class Element,class GetIndex,int hashsize>
00222 inline void RTPHashTable<Element,GetIndex,hashsize>::GotoPreviousElement()
00223 {
00224         if (curhashelem)
00225                 curhashelem = curhashelem->listprev;
00226 }
00227 
00228 template<class Element,class GetIndex,int hashsize>
00229 inline void RTPHashTable<Element,GetIndex,hashsize>::Clear()
00230 {
00231         HashElement *tmp1,*tmp2;
00232         
00233         for (int i = 0 ; i < hashsize ; i++)
00234                 table[i] = 0;
00235         
00236         tmp1 = firsthashelem;
00237         while (tmp1 != 0)
00238         {
00239                 tmp2 = tmp1->listnext;
00240                 RTPDelete(tmp1,GetMemoryManager());
00241                 tmp1 = tmp2;
00242         }
00243         firsthashelem = 0;
00244         lasthashelem = 0;
00245 }
00246 
00247 template<class Element,class GetIndex,int hashsize>
00248 inline int RTPHashTable<Element,GetIndex,hashsize>::AddElement(const Element &elem)
00249 {
00250         int index;
00251         bool found;
00252         HashElement *e,*newelem;
00253         
00254         index = GetIndex::GetIndex(elem);
00255         if (index >= hashsize)
00256                 return ERR_RTP_HASHTABLE_FUNCTIONRETURNEDINVALIDHASHINDEX;
00257         
00258         e = table[index];
00259         found = false;
00260         while(!found && e != 0)
00261         {
00262                 if (e->GetElement() == elem)
00263                         found = true;
00264                 else
00265                         e = e->hashnext;
00266         }
00267         if (found)
00268                 return ERR_RTP_HASHTABLE_ELEMENTALREADYEXISTS;
00269         
00270         // Okay, the key doesn't exist, so we can add the new element in the hash table
00271         
00272         newelem = RTPNew(GetMemoryManager(),memorytype) HashElement(elem,index);
00273         if (newelem == 0)
00274                 return ERR_RTP_OUTOFMEM;
00275 
00276         e = table[index];
00277         table[index] = newelem;
00278         newelem->hashnext = e;
00279         if (e != 0)
00280                 e->hashprev = newelem;
00281         
00282         // Now, we still got to add it to the linked list
00283         
00284         if (firsthashelem == 0)
00285         {
00286                 firsthashelem = newelem;
00287                 lasthashelem = newelem;
00288         }
00289         else // there already are some elements in the list
00290         {
00291                 lasthashelem->listnext = newelem;
00292                 newelem->listprev = lasthashelem;
00293                 lasthashelem = newelem;
00294         }
00295         return 0;
00296 }
00297 
00298 template<class Element,class GetIndex,int hashsize>
00299 inline int RTPHashTable<Element,GetIndex,hashsize>::DeleteElement(const Element &elem)
00300 {
00301         int status;
00302 
00303         status = GotoElement(elem);
00304         if (status < 0)
00305                 return status;
00306         return DeleteCurrentElement();
00307 }
00308 
00309 #ifdef RTPDEBUG
00310 template<class Element,class GetIndex,int hashsize>
00311 inline void RTPHashTable<Element,GetIndex,hashsize>::Dump()
00312 {
00313         HashElement *e;
00314         
00315         std::cout << "DUMPING TABLE CONTENTS:" << std::endl;
00316         for (int i = 0 ; i < hashsize ; i++)
00317         {
00318                 e = table[i];
00319                 while (e != 0)
00320                 {
00321                         e->Dump();
00322                         e = e->hashnext;
00323                 }
00324         }
00325         
00326         std::cout << "DUMPING LIST CONTENTS:" << std::endl;
00327         e = firsthashelem;
00328         while (e != 0)
00329         {
00330                 e->Dump();
00331                 e = e->listnext;
00332         }
00333 }
00334 #endif // RTPDEBUG
00335 
00336 #endif // RTPHASHTABLE_H
00337 

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