jrtplib 3.7.1
|
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