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