src/org/ibex/nestedvm/util/InodeCache.java

   1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
   2 // Licensed under the Apache Public Source License 2.0 ("the License").
   3 // You may not use this file except in compliance with the License.
   4
   5 package org.ibex.nestedvm.util;
   6
   7 // Based on the various org.xwt.util.* classes by Adam Megacz
   8
   9 public class InodeCache {
  10     private static final Object PLACEHOLDER = new Object();
  11     private static final short SHORT_PLACEHOLDER = -2;
  12     private static final short SHORT_NULL = -1;
  13     private static final int LOAD_FACTOR = 2;
  14
  15     private final int maxSize;
  16     private final int totalSlots;
  17     private final int maxUsedSlots;
  18
  19     private final Object[] keys;
  20     private final short[] next;
  21     private final short[] prev;
  22     private final short[] inodes;
  23     private final short[] reverse;
  24
  25     private int size, usedSlots;
  26     private short mru, lru;
  27
  28     public InodeCache() { this(1024); }
  29     public InodeCache(int maxSize) {
  30         this.maxSize = maxSize;
  31         totalSlots = maxSize*LOAD_FACTOR*2 + 3;
  32         maxUsedSlots = totalSlots / LOAD_FACTOR;
  33         if(totalSlots > Short.MAX_VALUE) throw new IllegalArgumentException("cache size too large");
  34         keys = new Object[totalSlots];
  35         next = new short[totalSlots];
  36         prev = new short[totalSlots];
  37         inodes = new short[totalSlots];
  38         reverse = new short[totalSlots];
  39         clear();
  40     }
  41
  42     private static void fill(Object[] a,Object o) { for(int i=0;i<a.length;i++) a[i] = o; }
  43     private static void fill(short[] a, short s)  { for(int i=0;i<a.length;i++) a[i] = s; }
  44     public final void clear() {
  45         size = usedSlots = 0;
  46         mru = lru = -1;
  47         fill(keys,null);
  48         fill(inodes,SHORT_NULL);
  49         fill(reverse,SHORT_NULL);
  50     }
  51
  52     public final short get(Object key) {
  53         int hc = key.hashCode() & 0x7fffffff;
  54         int dest = hc % totalSlots;
  55         int odest = dest;
  56         int tries = 1;
  57         boolean plus = true;
  58         Object k;
  59         int placeholder = -1;
  60
  61         while((k = keys[dest]) != null) {
  62             if(k == PLACEHOLDER) {
  63                 if(placeholder == -1) placeholder = dest;
  64             } else if(k.equals(key)) {
  65                 short inode = inodes[dest];
  66                 if(dest == mru) return inode;
  67                 if(lru == dest) {
  68                     lru = next[lru];
  69                 } else {
  70                     short p = prev[dest];
  71                     short n = next[dest];
  72                     next[p] = n;
  73                     prev[n] = p;
  74                 }
  75                 prev[dest] = mru;
  76                 next[mru] = (short) dest;
  77                 mru = (short) dest;
  78                 return inode;
  79             }
  80             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
  81             if(!plus) tries++;
  82             plus = !plus;
  83         }
  84
  85         // not found
  86         int slot;
  87         if(placeholder == -1) {
  88             // new slot
  89             slot = dest;
  90             if(usedSlots == maxUsedSlots) {
  91                 clear();
  92                 return get(key);
  93             }
  94             usedSlots++;
  95         } else {
  96             // reuse a placeholder
  97             slot = placeholder;
  98         }
  99
 100         if(size == maxSize) {
 101             // cache is full
 102             keys[lru] = PLACEHOLDER;
 103             inodes[lru] = SHORT_PLACEHOLDER;
 104             lru = next[lru];
 105         } else {
 106             if(size == 0) lru = (short) slot;
 107             size++;
 108         }
 109
 110         int inode;
 111         OUTER: for(inode = hc & 0x7fff;;inode++) {
 112             dest = inode % totalSlots;
 113             odest = dest;
 114             tries = 1;
 115             plus = true;
 116             placeholder = -1;
 117             int r;
 118             while((r = reverse[dest]) != SHORT_NULL) {
 119                 int i = inodes[r];
 120                 if(i == SHORT_PLACEHOLDER) {
 121                     if(placeholder == -1) placeholder = dest;
 122                 } else if(i == inode) {
 123                     continue OUTER;
 124                 }
 125                 dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
 126                 if(!plus) tries++;
 127                 plus = !plus;
 128             }
 129             // found a free inode
 130             if(placeholder != -1) dest = placeholder;
 131             break OUTER;
 132         }
 133         keys[slot] = key;
 134         reverse[dest] = (short) slot;
 135         inodes[slot] = (short) inode;
 136         if(mru != -1) {
 137             prev[slot] = mru;
 138             next[mru] = (short) slot;
 139         }
 140         mru = (short) slot;
 141         return (short) inode;
 142     }
 143
 144     public Object reverse(short inode) {
 145         int dest = inode % totalSlots;
 146         int odest = dest;
 147         int tries = 1;
 148         boolean plus = true;
 149         int r;
 150         while((r = reverse[dest]) != SHORT_NULL) {
 151             if(inodes[r] == inode) return keys[r];
 152             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
 153             if(!plus) tries++;
 154             plus = !plus;
 155         }
 156         return null;
 157     }
 158
 159     /*private void dump() {
 160         System.err.println("Size " + size);
 161         System.err.println("UsedSlots " + usedSlots);
 162         System.err.println("MRU " + mru);
 163         System.err.println("LRU " + lru);
 164         if(size == 0) return;
 165         for(int i=mru;;i=prev[i]) {
 166             System.err.println("" + i + ": " + keys[i] + " -> " + inodes[i] + "(prev: " + prev[i] + " next: " + next[i] + ")");
 167             if(i == lru) break;
 168         }
 169     }
 170
 171     private void stats() {
 172         int freeKeys = 0;
 173         int freeReverse = 0;
 174         int placeholderKeys = 0;
 175         int placeholderReverse = 0;
 176         for(int i=0;i<totalSlots;i++) {
 177             if(keys[i] == null) freeKeys++;
 178             if(keys[i] == PLACEHOLDER) placeholderKeys++;
 179             if(reverse[i] == SHORT_NULL) freeReverse++;
 180         }
 181         System.err.println("Keys: " + freeKeys + "/" + placeholderKeys);
 182         System.err.println("Reverse: " + freeReverse);
 183     }
 184
 185     public static void main(String[] args) throws Exception {
 186         InodeCache c = new InodeCache();
 187         java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
 188         String s;
 189         boolean good = false;
 190         try {
 191             while((s = br.readLine()) != null) {
 192                 if(s.charAt(0) == '#') {
 193                     short n = Short.parseShort(s.substring(1));
 194                         System.err.println("" + n + " -> " + c.reverse(n));
 195                 } else {
 196                     //System.err.println("Adding " + s);
 197                     short n = c.get(s);
 198                     System.err.println("Added " + s + " -> " + n);
 199                     //c.dump();
 200                 }
 201             }
 202             good = true;
 203         } finally {
 204             if(!good) c.stats();
 205         }
 206     }*/
 207 }