1 package org.ibex.nestedvm.util;
3 // Based on the various org.xwt.util.* classes by Adam Megacz
5 public class InodeCache {
6 private static final Object PLACEHOLDER = new Object();
7 private static final short SHORT_PLACEHOLDER = -2;
8 private static final short SHORT_NULL = -1;
9 private static final int LOAD_FACTOR = 2;
11 private final int maxSize;
12 private final int totalSlots;
13 private final int maxUsedSlots;
15 private final Object[] keys;
16 private final short[] next;
17 private final short[] prev;
18 private final short[] inodes;
19 private final short[] reverse;
21 private int size, usedSlots;
22 private short mru, lru;
24 public InodeCache() { this(1024); }
25 public InodeCache(int maxSize) {
26 this.maxSize = maxSize;
27 totalSlots = maxSize*LOAD_FACTOR*2 + 3;
28 maxUsedSlots = totalSlots / LOAD_FACTOR;
29 if(totalSlots > Short.MAX_VALUE) throw new IllegalArgumentException("cache size too large");
30 keys = new Object[totalSlots];
31 next = new short[totalSlots];
32 prev = new short[totalSlots];
33 inodes = new short[totalSlots];
34 reverse = new short[totalSlots];
38 private static void fill(Object[] a,Object o) { for(int i=0;i<a.length;i++) a[i] = o; }
39 private static void fill(short[] a, short s) { for(int i=0;i<a.length;i++) a[i] = s; }
40 public final void clear() {
44 fill(inodes,SHORT_NULL);
45 fill(reverse,SHORT_NULL);
48 public final short get(Object key) {
49 int hc = key.hashCode() & 0x7fffffff;
50 int dest = hc % totalSlots;
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;
72 next[mru] = (short) dest;
76 dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
83 if(placeholder == -1) {
86 if(usedSlots == maxUsedSlots) {
92 // reuse a placeholder
98 keys[lru] = PLACEHOLDER;
99 inodes[lru] = SHORT_PLACEHOLDER;
102 if(size == 0) lru = (short) slot;
107 OUTER: for(inode = hc & 0x7fff;;inode++) {
108 dest = inode % totalSlots;
114 while((r = reverse[dest]) != SHORT_NULL) {
116 if(i == SHORT_PLACEHOLDER) {
117 if(placeholder == -1) placeholder = dest;
118 } else if(i == inode) {
121 dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
125 // found a free inode
126 if(placeholder != -1) dest = placeholder;
130 reverse[dest] = (short) slot;
131 inodes[slot] = (short) inode;
134 next[mru] = (short) slot;
137 return (short) inode;
140 public Object reverse(short inode) {
141 int dest = inode % totalSlots;
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);
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] + ")");
167 private void stats() {
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++;
177 System.err.println("Keys: " + freeKeys + "/" + placeholderKeys);
178 System.err.println("Reverse: " + freeReverse);
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));
185 boolean good = false;
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));
192 //System.err.println("Adding " + s);
194 System.err.println("Added " + s + " -> " + n);