1    // Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
2    //
3    // You may modify, copy, and redistribute this code under the terms of
4    // the GNU Library Public License version 2.1, with the exception of
5    // the portion of clause 6a after the semicolon (aka the "obnoxious
6    // relink clause")
7    
8    package org.xwt.util;
9    
10   import java.util.*;
11   
12   // FIXME needs to be a weak hash
13   
14   /**
15    *  A Hash table with a fixed size; drops extraneous elements.  Uses
16    *  LRU strategy.
17    */
18   public class Cache extends Hash {
19   
20       /** head of list is the mru; tail is the lru */
21       Node mru = null;
22       Node lru = null;
23   
24       private int maxSize;
25       private Cache() { }
26       public Cache(int maxSize) {
27           super(maxSize * 2, 3);
28           this.maxSize = maxSize;
29       }
30   
31       /** A doubly-linked list */
32       private class Node {
33           final Object val;
34           final Object k1;
35           final Object k2;
36           public Node(Object k1, Object k2, Object val) { this.k1 = k1; this.k2 = k2; this.val = val; }
37           Node next = null;
38           Node prev = null;
39           void remove() {
40               if (this == lru) lru = prev;
41               if (this == mru) mru = next;
42               if (next != null) next.prev = prev;
43               if (prev != null) prev.next = next;
44               next = prev = null;
45           }
46           void placeAfter(Node n) {
47               remove();
48               if (n == null) return;
49               next = n.next;
50               if (n.next != null) n.next.prev = this;
51               n.next = this;
52               prev = n;
53           }
54           void placeBefore(Node n) {
55               remove();
56               if (n == null) return;
57               next = n;
58               prev = n.prev;
59               n.prev = this;
60               if (prev != null) prev.next = this;
61           }
62       }
63   
64       public void clear() {
65           lru = null;
66           super.clear();
67       }
68   
69       public void remove(Object k1, Object k2) {
70           Object o = super.get(k1, k2);
71           if (o != null) ((Node)o).remove();
72           super.remove(k1, k2);
73       }
74   
75       public Object get(Object k1, Object k2) {
76           Node n = (Node)super.get(k1, k2);
77           if (n == null) return null;
78           n.remove();
79           n.placeBefore(mru);
80           mru = n;
81           return n.val;
82       }
83   
84       public void put(Object k1, Object k2, Object v) {
85           Node n = new Node(k1, k2, v);
86           if (lru == null) {
87               lru = mru = n;
88           } else {
89               n.placeBefore(mru);
90               mru = n;
91           }
92           if (super.get(k1, k2) != null) remove(k1, k2);
93           super.put(k1, k2, n);
94           if (size > maxSize) remove(lru.k1, lru.k2);
95       }
96   
97   }
98   
99   
100