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