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

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