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 (Exception 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 136 /** 137 * Special implementation of a double linked list for {@link CacheEntry} 138 * elements. It supports element removal in constant time - in difference to 139 * the Java implementation which needs O(n). 140 * 141 * @author Jan Peter Stotz 142 */ 143 protected static class CacheLinkedListElement { 144 protected CacheEntry firstElement; 145 protected CacheEntry lastElement; 146 protected int elementCount; 147 148 /** 149 * Constructs a new {@code CacheLinkedListElement}. 150 */ 151 public CacheLinkedListElement() { 152 clear(); 153 } 154 155 public void clear() { 156 elementCount = 0; 157 firstElement = null; 158 lastElement = null; 159 } 160 161 /** 162 * Add the element to the head of the list. 163 * 164 * @param element new element to be added 165 */ 166 public void addFirst(CacheEntry element) { 167 if (element == null) return; 168 if (elementCount == 0) { 169 firstElement = element; 170 lastElement = element; 171 element.prev = null; 172 element.next = null; 173 } else { 174 element.next = firstElement; 175 firstElement.prev = element; 176 element.prev = null; 177 firstElement = element; 178 } 179 elementCount++; 180 } 181 182 /** 183 * Removes the specified element from the list. 184 * 185 * @param element element to be removed 186 */ 187 public void removeEntry(CacheEntry element) { 188 if (element == null) return; 189 if (element.next != null) { 190 element.next.prev = element.prev; 191 } 192 if (element.prev != null) { 193 element.prev.next = element.next; 194 } 195 if (element == firstElement) 196 firstElement = element.next; 197 if (element == lastElement) 198 lastElement = element.prev; 199 element.next = null; 200 element.prev = null; 201 elementCount--; 202 } 203 204 public void moveElementToFirstPos(CacheEntry entry) { 205 if (firstElement == entry) 206 return; 207 removeEntry(entry); 208 addFirst(entry); 209 } 210 211 public int getElementCount() { 212 return elementCount; 213 } 214 215 public CacheEntry getLastElement() { 216 return lastElement; 217 } 218 219 public CacheEntry getFirstElement() { 220 return firstElement; 221 } 222 } 223}