1 package org.ibex.nestedvm.util;
3 import java.util.Arrays;
5 // Based on the various org.xwt.util.* classes by Adam Megacz
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;
13 private final int maxSize;
14 private final int totalSlots;
15 private final int maxUsedSlots;
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;
23 private int size, usedSlots;
24 private short mru, lru;
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];
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() {
46 fill(inodes,SHORT_NULL);
47 fill(reverse,SHORT_NULL);
50 public final short get(Object key) {
51 int hc = key.hashCode() & 0x7fffffff;
52 int dest = hc % totalSlots;
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;
74 next[mru] = (short) dest;
78 dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
85 if(placeholder == -1) {
88 if(usedSlots == maxUsedSlots) {
94 // reuse a placeholder
100 keys[lru] = PLACEHOLDER;
101 inodes[lru] = SHORT_PLACEHOLDER;
104 if(size == 0) lru = (short) slot;
109 OUTER: for(inode = hc & 0x7fff;;inode++) {
110 dest = inode % totalSlots;
116 while((r = reverse[dest]) != SHORT_NULL) {
118 if(i == SHORT_PLACEHOLDER) {
119 if(placeholder == -1) placeholder = dest;
120 } else if(i == inode) {
123 dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
127 // found a free inode
128 if(placeholder != -1) dest = placeholder;
132 reverse[dest] = (short) slot;
133 inodes[slot] = (short) inode;
136 next[mru] = (short) slot;
139 return (short) inode;
142 public Object reverse(short inode) {
143 int dest = inode % totalSlots;
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);
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] + ")");
169 private void stats() {
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++;
179 System.err.println("Keys: " + freeKeys + "/" + placeholderKeys);
180 System.err.println("Reverse: " + freeReverse);
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));
187 boolean good = false;
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));
194 //System.err.println("Adding " + s);
196 System.err.println("Added " + s + " -> " + n);