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