001// License: GPL. For details, see Readme.txt file. 002package org.openstreetmap.gui.jmapviewer; 003 004import java.util.HashMap; 005import java.util.Map; 006import java.util.logging.Logger; 007 008import org.openstreetmap.gui.jmapviewer.interfaces.TileCache; 009import org.openstreetmap.gui.jmapviewer.interfaces.TileSource; 010 011/** 012 * {@link TileCache} implementation that stores all {@link Tile} objects in 013 * memory up to a certain limit ({@link #getCacheSize()}). If the limit is 014 * exceeded the least recently used {@link Tile} objects will be deleted. 015 * 016 * @author Jan Peter Stotz 017 */ 018public class MemoryTileCache implements TileCache { 019 020 protected static final Logger log = Logger.getLogger(MemoryTileCache.class.getName()); 021 022 /** 023 * Default cache size 024 */ 025 protected int cacheSize; 026 027 protected final Map<String, CacheEntry> hash; 028 029 /** 030 * List of all tiles in their last recently used order 031 */ 032 protected final CacheLinkedListElement lruTiles; 033 034 /** 035 * Constructs a new {@code MemoryTileCache}. 036 */ 037 public MemoryTileCache() { 038 this(200); 039 } 040 041 /** 042 * Constructs a new {@code MemoryTileCache}. 043 * @param cacheSize size of the cache 044 */ 045 public MemoryTileCache(int cacheSize) { 046 this.cacheSize = cacheSize; 047 hash = new HashMap<>(cacheSize); 048 lruTiles = new CacheLinkedListElement(); 049 } 050 051 @Override 052 public synchronized void addTile(Tile tile) { 053 CacheEntry entry = createCacheEntry(tile); 054 if (hash.put(tile.getKey(), entry) == null) { 055 // only if hash hadn't had the element, add it to LRU 056 lruTiles.addFirst(entry); 057 if (hash.size() > cacheSize || lruTiles.getElementCount() > cacheSize) { 058 removeOldEntries(); 059 } 060 } 061 } 062 063 @Override 064 public synchronized Tile getTile(TileSource source, int x, int y, int z) { 065 CacheEntry entry = hash.get(Tile.getTileKey(source, x, y, z)); 066 if (entry == null) 067 return null; 068 lruTiles.moveElementToFirstPos(entry); 069 return entry.tile; 070 } 071 072 /** 073 * Removes the least recently used tiles 074 */ 075 protected synchronized void removeOldEntries() { 076 try { 077 while (lruTiles.getElementCount() > cacheSize) { 078 removeEntry(lruTiles.getLastElement()); 079 } 080 } catch (NullPointerException e) { 081 log.warning(e.getMessage()); 082 } 083 } 084 085 protected synchronized void removeEntry(CacheEntry entry) { 086 hash.remove(entry.tile.getKey()); 087 lruTiles.removeEntry(entry); 088 } 089 090 protected CacheEntry createCacheEntry(Tile tile) { 091 return new CacheEntry(tile); 092 } 093 094 @Override 095 public synchronized void clear() { 096 hash.clear(); 097 lruTiles.clear(); 098 } 099 100 @Override 101 public synchronized int getTileCount() { 102 return hash.size(); 103 } 104 105 @Override 106 public synchronized int getCacheSize() { 107 return cacheSize; 108 } 109 110 /** 111 * Changes the maximum number of {@link Tile} objects that this cache holds. 112 * 113 * @param cacheSize 114 * new maximum number of tiles 115 */ 116 public synchronized void setCacheSize(int cacheSize) { 117 this.cacheSize = cacheSize; 118 if (hash.size() > cacheSize) 119 removeOldEntries(); 120 } 121 122 /** 123 * Linked list element holding the {@link Tile} and links to the 124 * {@link #next} and {@link #prev} item in the list. 125 */ 126 protected static class CacheEntry { 127 private Tile tile; 128 private CacheEntry next; 129 private CacheEntry prev; 130 131 protected CacheEntry(Tile tile) { 132 this.tile = tile; 133 } 134 135 @Override 136 public String toString() { 137 return tile.toString(); 138 } 139 } 140 141 /** 142 * Special implementation of a double linked list for {@link CacheEntry} 143 * elements. It supports element removal in constant time - in difference to 144 * the Java implementation which needs O(n). 145 * 146 * @author Jan Peter Stotz 147 */ 148 protected static class CacheLinkedListElement { 149 protected CacheEntry firstElement; 150 protected CacheEntry lastElement; 151 protected int elementCount; 152 153 /** 154 * Constructs a new {@code CacheLinkedListElement}. 155 */ 156 public CacheLinkedListElement() { 157 clear(); 158 } 159 160 public void clear() { 161 elementCount = 0; 162 firstElement = null; 163 lastElement = null; 164 } 165 166 /** 167 * Add the element to the head of the list. 168 * 169 * @param element new element to be added 170 */ 171 public void addFirst(CacheEntry element) { 172 if (element == null) return; 173 if (elementCount == 0) { 174 firstElement = element; 175 lastElement = element; 176 element.prev = null; 177 element.next = null; 178 } else { 179 element.next = firstElement; 180 firstElement.prev = element; 181 element.prev = null; 182 firstElement = element; 183 } 184 elementCount++; 185 } 186 187 /** 188 * Removes the specified element from the list. 189 * 190 * @param element element to be removed 191 */ 192 public void removeEntry(CacheEntry element) { 193 if (element == null) return; 194 if (element.next != null) { 195 element.next.prev = element.prev; 196 } 197 if (element.prev != null) { 198 element.prev.next = element.next; 199 } 200 if (element == firstElement) 201 firstElement = element.next; 202 if (element == lastElement) 203 lastElement = element.prev; 204 element.next = null; 205 element.prev = null; 206 elementCount--; 207 } 208 209 public void moveElementToFirstPos(CacheEntry entry) { 210 if (firstElement == entry) 211 return; 212 removeEntry(entry); 213 addFirst(entry); 214 } 215 216 public int getElementCount() { 217 return elementCount; 218 } 219 220 public CacheEntry getLastElement() { 221 return lastElement; 222 } 223 224 public CacheEntry getFirstElement() { 225 return firstElement; 226 } 227 } 228}