1 /******************************************************************************* 2 * Copyright (c) 2004, 2015 IBM Corporation and others. 3 * 4 * This program and the accompanying materials 5 * are made available under the terms of the Eclipse Public License 2.0 6 * which accompanies this distribution, and is available at 7 * https://www.eclipse.org/legal/epl-2.0/ 8 * 9 * SPDX-License-Identifier: EPL-2.0 10 * 11 * Contributors: 12 * IBM Corporation - initial API and implementation 13 *******************************************************************************/ 14 package org.eclipse.core.internal.utils; 15 16 import org.eclipse.core.runtime.Assert; 17 18 /** 19 * A cache that keeps a collection of at most maximumCapacity+threshold entries. 20 * When the number of entries exceeds that limit, least recently used entries are removed 21 * so the current size is the same as the maximum capacity. 22 */ 23 public class Cache { 24 public class Entry implements KeyedHashSet.KeyedElement { 25 Object cached; 26 Object key; 27 Entry next; 28 Entry previous; 29 long timestamp; 30 Entry(Object key, Object cached, long timestamp)31 public Entry(Object key, Object cached, long timestamp) { 32 this.key = key; 33 this.cached = cached; 34 this.timestamp = timestamp; 35 } 36 37 @Override compare(KeyedHashSet.KeyedElement other)38 public boolean compare(KeyedHashSet.KeyedElement other) { 39 if (!(other instanceof Entry)) 40 return false; 41 Entry otherEntry = (Entry) other; 42 return key.equals(otherEntry.key); 43 } 44 45 /* Removes this entry from the cache */ discard()46 public void discard() { 47 unchain(); 48 cached = null; 49 entries.remove(this); 50 } 51 getCached()52 public Object getCached() { 53 return cached; 54 } 55 56 @Override getKey()57 public Object getKey() { 58 return key; 59 } 60 61 @Override getKeyHashCode()62 public int getKeyHashCode() { 63 return key.hashCode(); 64 } 65 getNext()66 public Entry getNext() { 67 return next; 68 } 69 getPrevious()70 public Entry getPrevious() { 71 return previous; 72 } 73 getTimestamp()74 public long getTimestamp() { 75 return timestamp; 76 } 77 isHead()78 public boolean isHead() { 79 return previous == null; 80 } 81 isTail()82 public boolean isTail() { 83 return next == null; 84 } 85 86 /* Inserts into the head of the list */ makeHead()87 void makeHead() { 88 Entry oldHead = head; 89 head = this; 90 next = oldHead; 91 previous = null; 92 if (oldHead == null) 93 tail = this; 94 else 95 oldHead.previous = this; 96 } 97 setCached(Object cached)98 public void setCached(Object cached) { 99 this.cached = cached; 100 } 101 setTimestamp(long timestamp)102 public void setTimestamp(long timestamp) { 103 this.timestamp = timestamp; 104 } 105 106 @Override toString()107 public String toString() { 108 return key + " -> " + cached + " [" + timestamp + ']'; //$NON-NLS-1$ //$NON-NLS-2$ 109 } 110 111 /* Removes from the linked list, but not from the entries collection */ unchain()112 void unchain() { 113 // it may be in the tail 114 if (tail == this) 115 tail = previous; 116 else 117 next.previous = previous; 118 // it may be in the head 119 if (head == this) 120 head = next; 121 else 122 previous.next = next; 123 } 124 } 125 126 KeyedHashSet entries; 127 Entry head; 128 private int maximumCapacity; 129 Entry tail; 130 private double threshold; 131 Cache(int maximumCapacity)132 public Cache(int maximumCapacity) { 133 this(Math.min(KeyedHashSet.MINIMUM_SIZE, maximumCapacity), maximumCapacity, 0.25); 134 } 135 Cache(int initialCapacity, int maximumCapacity, double threshold)136 public Cache(int initialCapacity, int maximumCapacity, double threshold) { 137 Assert.isTrue(maximumCapacity >= initialCapacity, "maximum capacity < initial capacity"); //$NON-NLS-1$ 138 Assert.isTrue(threshold >= 0 && threshold <= 1, "threshold should be between 0 and 1"); //$NON-NLS-1$ 139 Assert.isTrue(initialCapacity > 0, "initial capacity must be greater than zero"); //$NON-NLS-1$ 140 entries = new KeyedHashSet(initialCapacity); 141 this.maximumCapacity = maximumCapacity; 142 this.threshold = threshold; 143 } 144 addEntry(Object key, Object toCache)145 public void addEntry(Object key, Object toCache) { 146 addEntry(key, toCache, 0); 147 } 148 addEntry(Object key, Object toCache, long timestamp)149 public Entry addEntry(Object key, Object toCache, long timestamp) { 150 Entry newHead = (Entry) entries.getByKey(key); 151 if (newHead == null) 152 entries.add(newHead = new Entry(key, toCache, timestamp)); 153 newHead.cached = toCache; 154 newHead.timestamp = timestamp; 155 newHead.makeHead(); 156 int extraEntries = entries.size() - maximumCapacity; 157 if (extraEntries > maximumCapacity * threshold) 158 // we have reached our limit - ensure we are under the maximum capacity 159 // by discarding older entries 160 packEntries(extraEntries); 161 return newHead; 162 } 163 getEntry(Object key)164 public Entry getEntry(Object key) { 165 return getEntry(key, true); 166 } 167 getEntry(Object key, boolean update)168 public Entry getEntry(Object key, boolean update) { 169 Entry existing = (Entry) entries.getByKey(key); 170 if (existing == null) 171 return null; 172 if (!update) 173 return existing; 174 existing.unchain(); 175 existing.makeHead(); 176 return existing; 177 } 178 getHead()179 public Entry getHead() { 180 return head; 181 } 182 getTail()183 public Entry getTail() { 184 return tail; 185 } 186 packEntries(int extraEntries)187 private void packEntries(int extraEntries) { 188 // should remove in an ad-hoc way to get better performance 189 Entry current = tail; 190 for (; current != null && extraEntries > 0; extraEntries--) { 191 current.discard(); 192 current = current.previous; 193 } 194 } 195 size()196 public long size() { 197 return entries.size(); 198 } 199 discardAll()200 public void discardAll() { 201 entries.clear(); 202 head = tail = null; 203 } 204 dispose()205 public void dispose() { 206 discardAll(); 207 entries = null; 208 head = tail = null; 209 } 210 } 211