Subversion Repositories async_sdm_noc

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