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.
5 package org.ibex.nestedvm.util;
7 // Based on the various org.xwt.util.* classes by Adam Megacz
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;
15 private final int maxSize;
16 private final int totalSlots;
17 private final int maxUsedSlots;
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;
25 private int size, usedSlots;
26 private short mru, lru;
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];
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() {
48 fill(inodes,SHORT_NULL);
49 fill(reverse,SHORT_NULL);
52 public final short get(Object key) {
53 int hc = key.hashCode() & 0x7fffffff;
54 int dest = hc % totalSlots;
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;
76 next[mru] = (short) dest;
80 dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
87 if(placeholder == -1) {
90 if(usedSlots == maxUsedSlots) {
96 // reuse a placeholder
100 if(size == maxSize) {
102 keys[lru] = PLACEHOLDER;
103 inodes[lru] = SHORT_PLACEHOLDER;
106 if(size == 0) lru = (short) slot;
111 OUTER: for(inode = hc & 0x7fff;;inode++) {
112 dest = inode % totalSlots;
118 while((r = reverse[dest]) != SHORT_NULL) {
120 if(i == SHORT_PLACEHOLDER) {
121 if(placeholder == -1) placeholder = dest;
122 } else if(i == inode) {
125 dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
129 // found a free inode
130 if(placeholder != -1) dest = placeholder;
134 reverse[dest] = (short) slot;
135 inodes[slot] = (short) inode;
138 next[mru] = (short) slot;
141 return (short) inode;
144 public Object reverse(short inode) {
145 int dest = inode % totalSlots;
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);
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] + ")");
171 private void stats() {
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++;
181 System.err.println("Keys: " + freeKeys + "/" + placeholderKeys);
182 System.err.println("Reverse: " + freeReverse);
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));
189 boolean good = false;
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));
196 //System.err.println("Adding " + s);
198 System.err.println("Added " + s + " -> " + n);