Initial commit of OpenSPARC T2 architecture model.

[OpenSPARC-T2-SAM] / rst / rstzip3 / rstzip_v3 / rz3_lruhash.h

/*
* ========== Copyright Header Begin ==========================================
* 
* OpenSPARC T2 Processor File: rz3_lruhash.h
* Copyright (c) 2006 Sun Microsystems, Inc.  All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES.
* 
* The above named program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public
* License version 2 as published by the Free Software Foundation.
* 
* The above named program is distributed in the hope that it will be 
* useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
* General Public License for more details.
* 
* You should have received a copy of the GNU General Public
* License along with this work; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
* 
* ========== Copyright Header End ============================================
*/
/* rz3_lruhash.h
* fully-associative cache with lru replacement
*/

#ifndef _rz3_lruhash_h_
#define _rz3_lruhash_h_

#include <stdio.h>
#include <strings.h>
#include <sys/types.h>

struct rz3_lruhash_elem {
 uint64_t v;

 rz3_lruhash_elem * next;
 rz3_lruhash_elem * prev;


 rz3_lruhash_elem() {
   k = 0;
   prev = next = NULL;
   inited = false;
 }

 int GetKey() {
   if (!inited) {
     fprintf(stderr, "warning: rz3_lruhash: rz3_lruhash_elem key not set\n");
   }
   return k;
 }

 bool SetKey(int key) {
   if (!inited) {
     k = key;
     inited = true;
     return true;
   } else {
     fprintf(stderr, "warning: rz3_lruhash: rz3_lruhash_elem key already set\n");
     return false;
   }
 }
private:
 // "k" is equivalent to a java "final" variable - write once
 int k; // "key", which is an index into a linear array in this implementation
 bool inited;
}; // rz3_lruhash_elem


struct rz3_lruhash {

 int nbits(uint64_t n) {
   int rv = 1;
   while(n>>rv) {
     rv++;
   }
   return rv;
 }

 // size must be a power of 2
 rz3_lruhash(int arg_size) {
   size = arg_size;

   idxbits = nbits(size-1);
   arr = new rz3_lruhash_elem [size];

   searchtbl = new rz3_lruhash_elem * [size];

   Clear();

   refs = misses = searchtbl_hits = 0;
 }

 void Clear() {
   newest = arr;
   oldest = arr+(size-1);

   bzero(searchtbl, size*sizeof(rz3_lruhash_elem *));

   int i;
   for (i=0; i<size; i++) {
     rz3_lruhash_elem * elem = arr+i;
     elem->v = i;
     elem->SetKey(i);
     elem->prev = (elem == newest) ? NULL : arr+(i-1);
     elem->next = (elem == oldest) ? NULL : arr+(i+1);
     // insert into searchtbl
     searchtbl[search_idx_fn(elem->v)] = elem;
   }
 } // rz3_lruhash(int arg_size)


 ~rz3_lruhash() {
   delete [] arr;
   delete [] searchtbl;
 } // ~rz3_lruhash()

 // returns a "key" whose value is [0 .. size-1]
 // and whose size is CEIL(log2(arg_size)) bits
 bool Update(uint64_t v, int & k) {


   k = -1;
   refs++;

   // first search for elem
   int searchidx = search_idx_fn(v);
   if ((searchtbl[searchidx] != NULL) && (searchtbl[searchidx]->v == v)) {
     k = searchtbl[searchidx]->GetKey();
     searchtbl_hits++;
   } else {
     int i;
     for (i=0; i<size; i++) {
       if (arr[i].v == v) {
         k = i;
         break;
       }
     }
   }

   bool hit;
   if (k != -1) {
     BringToFront(&(arr[k]));
     hit = true;
   } else {
     k = oldest->GetKey();
     oldest->v = v;
     BringToFront(oldest);
     misses++;
     hit = false;
   }

   searchtbl[searchidx] = &(arr[k]);

   return hit;
 } // int Update(uint64_t v)

 // if key is good, stores corresponding value in v and returns true. also brings (key,v) to the front of the MRU list
 // returns false otherwise
 bool Get(int key, uint64_t & v) {
   if ((key < 0) || (key >= size)) return false;

   v = arr[key].v;

   BringToFront(&(arr[key]));
   int searchidx = search_idx_fn(v);
   searchtbl[searchidx] = &(arr[key]);
   return true;
 } // bool Get(int key, uint64_t & v)


 void BringToFront(rz3_lruhash_elem * elem) {
   if (elem == newest) return;

   elem->prev->next = elem->next;
   if (elem->next == NULL) {
     oldest = elem->prev;
   } else {
     elem->next->prev = elem->prev;
   }
   elem->prev = NULL;
   elem->next = newest;
   newest->prev = elem;
   newest = elem;
 }

 int search_idx_fn(uint64_t v) {
   return (v & (size-1)) ^ ((v >> idxbits) & (size-1));
 }

 void Report(FILE * fp) {
   fprintf(fp, "refs %lld misses %lld (%0.4f%%/ref)\n", refs, misses, misses*100.0/refs);
   uint64_t hits = refs-misses;
   fprintf(fp, "  fasthits %lld (%0.4f%%/hit, %0.4f%%/ref)\n", searchtbl_hits, searchtbl_hits*100.0/hits, searchtbl_hits*100.0/refs);
 }

 int size;

 int idxbits;

 rz3_lruhash_elem * newest;
 rz3_lruhash_elem * oldest;

 rz3_lruhash_elem * arr;

 rz3_lruhash_elem ** searchtbl; // search here first. if fails, search entire list

 uint64_t refs;
 uint64_t misses;
 uint64_t searchtbl_hits;
}; // struct rz3_lruhash

#endif // _rz3_lruhash_h_