URL
https://opencores.org/ocsvn/async_sdm_noc/async_sdm_noc/trunk
Subversion Repositories async_sdm_noc
[/] [async_sdm_noc/] [branches/] [init/] [common/] [tb/] [hash_table.h] - Rev 60
Go to most recent revision | Compare with Previous | Blame | View Log
/* Asynchronous SDM NoC (C)2011 Wei Song Advanced Processor Technologies Group Computer Science, the Univ. of Manchester, UK Authors: Wei Song wsong83@gmail.com License: LGPL 3.0 or later A hash table container to store the frames under transmission. ?? Using STL may be better? Sorry, I have no intention to explain the codes below as it is unlikely to modify it. If there are bugs here, please email me. History: 29/06/2010 Initial version. <wsong83@gmail.com> 27/05/2011 Clean up for opensource. <wsong83@gmail.com> */ #ifndef HASH_TABLE_H_ #define HASH_TABLE_H_ #include <ostream> using namespace std; template<typename T, unsigned int HSIZE> class hash_table; template<typename T, unsigned int HSIZE> ostream& operator<< (ostream& os, const hash_table<T,HSIZE>& HB) { T * item; os << "Records in hash table:" << endl; for(unsigned int i=0; i<HSIZE; i++) { os << "vector " << i << ": "; item = HB.dat[i][0]; while(item != NULL) { os << *item << "| "; item = item->next; } os << endl; } return os; } template<typename T, unsigned int HSIZE> class hash_table { public: T * dat [HSIZE][2]; hash_table() { for(unsigned int i=0; i<HSIZE; i++) { dat[i][0] = NULL; dat[i][1] = NULL; } } void insert ( T& ); /* insert an item into the hash table */ T * find ( long ); /* find an item */ T * find ( const T& ); /* find an item by reading an existing item */ void clear ( T * ); /* delete an item in the hash table */ ~hash_table() { for(unsigned int i=0; i<HSIZE; i++) { if(dat[i][0] != NULL) { delete dat[i][0]; dat[i][0] = NULL; dat[i][1] = NULL; } } } friend ostream& operator<< <T,HSIZE> (ostream&, const hash_table<T,HSIZE>&); private: T* search (T*, long); }; template<typename T, unsigned int HSIZE> void hash_table<T,HSIZE>::insert ( T& RD) { long key = RD.key; unsigned int vcn = key%HSIZE; T * entry = dat[vcn][1]; if(entry == NULL) { /* the whole vector is empty right now */ dat[vcn][0] = &RD; dat[vcn][1] = &RD; } else { /* non-empty vector */ entry->next = &RD; RD.pre = entry; dat[vcn][1] = &RD; } } template<typename T, unsigned int HSIZE> T * hash_table<T,HSIZE>::find ( long mkey) { unsigned int vcn = mkey%HSIZE; return search(dat[vcn][0], mkey); } template<typename T, unsigned int HSIZE> T * hash_table<T,HSIZE>::find ( const T& RD) { return find((long)(RD)); } template<typename T, unsigned int HSIZE> void hash_table<T,HSIZE>::clear ( T * RD) { unsigned int vcn = ((long)(*RD)) % HSIZE; if(RD->pre == NULL) /* head of a vector */ dat[vcn][0] = RD->next; if(RD->next == NULL) /* tail of a vector */ dat[vcn][1] = RD->pre; if(RD->pre != NULL) (RD->pre)->next = RD->next; if(RD->next != NULL) (RD->next)->pre = RD->pre; RD->pre = NULL; RD->next = NULL; delete RD; } template<typename T, unsigned int HSIZE> T* hash_table<T,HSIZE>::search (T* entry, long mkey) { while(entry != NULL) { if((long)(*entry) == mkey) return entry; else entry = entry->next; } return NULL; } #endif
Go to most recent revision | Compare with Previous | Blame | View Log