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}