1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 package com.sun.star.lib.uno.protocols.urp;
25 
26 import java.util.HashMap;
27 
28 /**
29    An LRU cache for arbitrary objects.
30 
31    This class is not synchronized, as any necessary synchronization will already
32    take place in the client.
33 */
34 final class Cache {
35     /**
36        Create a cache.
37 
38        @param size the maximum cache size, must be between 0, inclusive, and
39        NOT_CACHED, exclusive
40     */
Cache(int size)41     public Cache(int size) {
42         maxSize = size;
43     }
44 
add(boolean[] found, Object content)45     public int add(boolean[] found, Object content) {
46         Entry e = (Entry) map.get(content);
47         found[0] = e != null;
48         if (e == null) {
49             if (map.size() < maxSize) {
50                 // There is still room for a new entry at the front:
51                 e = new Entry(content, map.size(), null, first);
52                 if (first == null) {
53                     last = e;
54                 } else {
55                     first.prev = e;
56                 }
57                 first = e;
58             } else if (last != null) {
59                 // Take last entry out and recycle as new front:
60                 map.remove(last.content);
61                 e = last;
62                 e.content = content;
63                 if (first != last) {
64                     // Reached only if maxSize > 1:
65                     last = last.prev;
66                     last.next = null;
67                     e.prev = null;
68                     e.next = first;
69                     first.prev = e;
70                     first = e;
71                 }
72             } else {
73                 // Reached iff maxSize == 0:
74                 return NOT_CACHED;
75             }
76             map.put(content, e);
77         } else if (e != first) {
78             // Move to front (reached only if maxSize > 1):
79             e.prev.next = e.next;
80             if (e.next == null) {
81                 last = e.prev;
82             } else {
83                 e.next.prev = e.prev;
84             }
85             e.prev = null;
86             e.next = first;
87             first.prev = e;
88             first = e;
89         }
90         return e.index;
91     }
92 
93     public static final int NOT_CACHED = 0xFFFF;
94 
95     private static final class Entry {
Entry(Object content, int index, Entry prev, Entry next)96         public Entry(Object content, int index, Entry prev, Entry next) {
97             this.content = content;
98             this.index = index;
99             this.prev = prev;
100             this.next = next;
101         }
102 
103         public Object content;
104         public int index;
105         public Entry prev;
106         public Entry next;
107     }
108 
109     // first/last form a list of 0 to maxSize entries, most recently used first;
110     // map contains the same entries; each entry has a unique index in the range
111     // 0 to maxSize - 1
112     private final int maxSize;
113     private final HashMap map = new HashMap(); // from Object to Entry
114     private Entry first = null;
115     private Entry last = null;
116 }
117