← Back to branch summary

~ubuntu-branches/debian/sid/eclipse-cdt/sid

« back to all changes in this revision

Viewing changes to results/plugins/org.eclipse.cdt.core/model/org/eclipse/cdt/internal/core/util/LRUCache.java

  • Committer: Package Import Robot
  • Author(s): Jakub Adam
  • Date: 2011-10-06 21:15:04 UTC
  • mfrom: (1.1.4)
  • Revision ID: package-import@ubuntu.com-20111006211504-8dutmljjih0zikfv
Tags: 8.0.1-1
* New upstream release.
* Split the JNI packages into a separate architecture dependent
  package and made eclipse-cdt architecture independent.
* Install JNI libraries into multiarch aware location
* Bumped Standards-Version to 3.9.2.

Show diffs side-by-side

added added

removed removed

Lines of Context:
results/plugins/org.eclipse.cdt.core/model/org/eclipse/cdt/internal/core/util/LRUCache.java
1
 
/*******************************************************************************
2
 
 * Copyright (c) 2002, 2008 IBM Corporation and others.
3
 
 * All rights reserved. This program and the accompanying materials
4
 
 * are made available under the terms of the Eclipse Public License v1.0
5
 
 * which accompanies this distribution, and is available at
6
 
 * http://www.eclipse.org/legal/epl-v10.html
7
 
 *
8
 
 * Contributors:
9
 
 * Rational Software - Initial API and implementation
10
 
 *******************************************************************************/
11
 
package org.eclipse.cdt.internal.core.util;
12
 
 
13
 
 
14
 
 
15
 
import java.util.Enumeration;
16
 
import java.util.Hashtable;
17
 
 
18
 
/**
19
 
 * The <code>LRUCache</code> is a hashtable that stores a finite number of elements.  
20
 
 * When an attempt is made to add values to a full cache, the least recently used values
21
 
 * in the cache are discarded to make room for the new values as necessary.
22
 
 * 
23
 
 * <p>The data structure is based on the LRU virtual memory paging scheme.
24
 
 * 
25
 
 * <p>Objects can take up a variable amount of cache space by implementing
26
 
 * the <code>ILRUCacheable</code> interface.
27
 
 *
28
 
 * <p>This implementation is NOT thread-safe.  Synchronization wrappers would
29
 
 * have to be added to ensure atomic insertions and deletions from the cache.
30
 
 *
31
 
 * @see ILRUCacheable
32
 
 * 
33
 
 * This class is similar to the JDT LRUCache class.
34
 
 */
35
 
public class LRUCache<K,T> implements Cloneable {
36
 
 
37
 
        /**
38
 
         * This type is used internally by the LRUCache to represent entries 
39
 
         * stored in the cache.
40
 
         * It is static because it does not require a pointer to the cache
41
 
         * which contains it.
42
 
         *
43
 
         * @see LRUCache
44
 
         */
45
 
        protected static class LRUCacheEntry<K,T> {
46
 
                
47
 
                /**
48
 
                 * Hash table key
49
 
                 */
50
 
                public K _fKey;
51
 
                 
52
 
                /**
53
 
                 * Hash table value (an LRUCacheEntry object)
54
 
                 */
55
 
                public T _fValue;                
56
 
 
57
 
                /**
58
 
                 * Time value for queue sorting
59
 
                 */
60
 
                public int _fTimestamp;
61
 
                
62
 
                /**
63
 
                 * Cache footprint of this entry
64
 
                 */
65
 
                public int _fSpace;
66
 
                
67
 
                /**
68
 
                 * Previous entry in queue
69
 
                 */
70
 
                public LRUCacheEntry<K,T> _fPrevious;
71
 
                        
72
 
                /**
73
 
                 * Next entry in queue
74
 
                 */
75
 
                public LRUCacheEntry<K,T> _fNext;
76
 
                        
77
 
                /**
78
 
                 * Creates a new instance of the receiver with the provided values
79
 
                 * for key, value, and space.
80
 
                 */
81
 
                public LRUCacheEntry (K key, T value, int space) {
82
 
                        _fKey = key;
83
 
                        _fValue = value;
84
 
                        _fSpace = space;
85
 
                }
86
 
 
87
 
                /**
88
 
                 * Returns a String that represents the value of this object.
89
 
                 */
90
 
                @Override
91
 
                public String toString() {
92
 
 
93
 
                        return "LRUCacheEntry [" + _fKey + "-->" + _fValue + "]"; //$NON-NLS-3$ //$NON-NLS-1$ //$NON-NLS-2$
94
 
                }
95
 
        }       
96
 
 
97
 
        /**
98
 
         * Amount of cache space used so far
99
 
         */
100
 
        protected int fCurrentSpace;
101
 
        
102
 
        /**
103
 
         * Maximum space allowed in cache
104
 
         */
105
 
        protected int fSpaceLimit;
106
 
        
107
 
        /**
108
 
         * Counter for handing out sequential timestamps
109
 
         */
110
 
        protected int   fTimestampCounter;
111
 
        
112
 
        /**
113
 
         * Hash table for fast random access to cache entries
114
 
         */
115
 
        protected Hashtable<K,LRUCacheEntry<K,T>> fEntryTable;
116
 
 
117
 
        /**
118
 
         * Start of queue (most recently used entry) 
119
 
         */     
120
 
        protected LRUCacheEntry<K,T> fEntryQueue;
121
 
 
122
 
        /**
123
 
         * End of queue (least recently used entry)
124
 
         */     
125
 
        protected LRUCacheEntry<K,T> fEntryQueueTail;
126
 
                
127
 
        /**
128
 
         * Default amount of space in the cache
129
 
         */
130
 
        protected static final int DEFAULT_SPACELIMIT = 100;
131
 
        /**
132
 
         * Creates a new cache.  Size of cache is defined by 
133
 
         * <code>DEFAULT_SPACELIMIT</code>.
134
 
         */
135
 
        public LRUCache() {
136
 
                
137
 
                this(DEFAULT_SPACELIMIT);
138
 
        }
139
 
        /**
140
 
         * Creates a new cache.
141
 
         * @param size Size of Cache
142
 
         */
143
 
        public LRUCache(int size) {
144
 
                
145
 
                fTimestampCounter = fCurrentSpace = 0;
146
 
                fEntryQueue = fEntryQueueTail = null;
147
 
                fEntryTable = new Hashtable<K,LRUCacheEntry<K,T>>(size);
148
 
                fSpaceLimit = size;
149
 
        }
150
 
        /**
151
 
         * Returns a new cache containing the same contents.
152
 
         *
153
 
         * @return New copy of object.
154
 
         */
155
 
        @Override
156
 
        public Object clone() {
157
 
                
158
 
                LRUCache<K,T> newCache = newInstance(fSpaceLimit);
159
 
                LRUCacheEntry<K,T> qEntry;
160
 
                
161
 
                /* Preserve order of entries by copying from oldest to newest */
162
 
                qEntry = this.fEntryQueueTail;
163
 
                while (qEntry != null) {
164
 
                        newCache.privateAdd (qEntry._fKey, qEntry._fValue, qEntry._fSpace);
165
 
                        qEntry = qEntry._fPrevious;
166
 
                }
167
 
                return newCache;
168
 
        }
169
 
        /**
170
 
         * Flushes all entries from the cache.
171
 
         */
172
 
        public void flush() {
173
 
 
174
 
                fCurrentSpace = 0;
175
 
                LRUCacheEntry<K,T> entry = fEntryQueueTail; // Remember last entry
176
 
                fEntryTable = new Hashtable<K,LRUCacheEntry<K,T>>();  // Clear it out
177
 
                fEntryQueue = fEntryQueueTail = null;  
178
 
                while (entry != null) {  // send deletion notifications in LRU order
179
 
                        privateNotifyDeletionFromCache(entry);
180
 
                        entry = entry._fPrevious;
181
 
                }
182
 
        }
183
 
        /**
184
 
         * Flushes the given entry from the cache.  Does nothing if entry does not
185
 
         * exist in cache.
186
 
         *
187
 
         * @param key Key of object to flush
188
 
         */
189
 
        public void flush (Object key) {
190
 
                
191
 
                LRUCacheEntry<K,T> entry;
192
 
                
193
 
                entry = fEntryTable.get(key);
194
 
 
195
 
                /* If entry does not exist, return */
196
 
                if (entry == null) return;
197
 
 
198
 
                this.privateRemoveEntry (entry, false);
199
 
        }
200
 
        /**
201
 
         * Answers the value in the cache at the given key.
202
 
         * If the value is not in the cache, returns null
203
 
         *
204
 
         * @param key Hash table key of object to retrieve
205
 
         * @return Retreived object, or null if object does not exist
206
 
         */
207
 
        public Object get(Object key) {
208
 
                
209
 
                LRUCacheEntry<K,T> entry = fEntryTable.get(key);
210
 
                if (entry == null) {
211
 
                        return null;
212
 
                }
213
 
                
214
 
                this.updateTimestamp (entry);
215
 
                return entry._fValue;
216
 
        }
217
 
        /**
218
 
         * Returns the amount of space that is current used in the cache.
219
 
         */
220
 
        public int getCurrentSpace() {
221
 
                return fCurrentSpace;
222
 
        }
223
 
        /**
224
 
         * Returns the maximum amount of space available in the cache.
225
 
         */
226
 
        public int getSpaceLimit() {
227
 
                return fSpaceLimit;
228
 
        }
229
 
        /**
230
 
         * Returns an Enumeration of the keys currently in the cache.
231
 
         */
232
 
        public Enumeration<K> keys() {
233
 
                
234
 
                return fEntryTable.keys();
235
 
        }
236
 
    /**
237
 
     * Tests if this cache is empty.
238
 
     */
239
 
        public boolean isEmpty() {
240
 
                return fEntryTable.isEmpty();
241
 
        }
242
 
 
243
 
        /**
244
 
         * Ensures there is the specified amount of free space in the receiver,
245
 
         * by removing old entries if necessary.  Returns true if the requested space was
246
 
         * made available, false otherwise.
247
 
         *
248
 
         * @param space Amount of space to free up
249
 
         */
250
 
        protected boolean makeSpace (int space) {
251
 
                
252
 
                int limit;
253
 
                
254
 
                limit = this.getSpaceLimit();
255
 
                
256
 
                /* if space is already available */
257
 
                if (fCurrentSpace + space <= limit) {
258
 
                        return true;
259
 
                }
260
 
                
261
 
                /* if entry is too big for cache */
262
 
                if (space > limit) {
263
 
                        return false;
264
 
                }
265
 
                
266
 
                /* Free up space by removing oldest entries */
267
 
                while (fCurrentSpace + space > limit && fEntryQueueTail != null) {
268
 
                        this.privateRemoveEntry (fEntryQueueTail, false);
269
 
                }
270
 
                return true;
271
 
        }
272
 
        /**
273
 
         * Returns a new LRUCache instance
274
 
         */
275
 
        protected LRUCache<K,T> newInstance(int size) {
276
 
                return new LRUCache<K,T>(size);
277
 
        }
278
 
        /**
279
 
         * Adds an entry for the given key/value/space.
280
 
         */
281
 
        protected void privateAdd (K key, T value, int space) {
282
 
                
283
 
                LRUCacheEntry<K,T> entry;
284
 
                
285
 
                entry = new LRUCacheEntry<K,T>(key, value, space);
286
 
                this.privateAddEntry (entry, false);
287
 
        }
288
 
        /**
289
 
         * Adds the given entry from the receiver.
290
 
         * @param shuffle Indicates whether we are just shuffling the queue 
291
 
         * (i.e., the entry table is left alone).
292
 
         */
293
 
        protected void privateAddEntry (LRUCacheEntry<K,T> entry, boolean shuffle) {
294
 
                
295
 
                if (!shuffle) {
296
 
                        fEntryTable.put (entry._fKey, entry);
297
 
                        fCurrentSpace += entry._fSpace;
298
 
                }
299
 
                
300
 
                entry._fTimestamp = fTimestampCounter++;
301
 
                entry._fNext = this.fEntryQueue;
302
 
                entry._fPrevious = null;
303
 
                
304
 
                if (fEntryQueue == null) {
305
 
                        /* this is the first and last entry */
306
 
                        fEntryQueueTail = entry;
307
 
                } else {
308
 
                        fEntryQueue._fPrevious = entry;
309
 
                }
310
 
                
311
 
                fEntryQueue = entry;
312
 
        }
313
 
        /**
314
 
         * An entry has been removed from the cache, for example because it has 
315
 
         * fallen off the bottom of the LRU queue.  
316
 
         * Subclasses could over-ride this to implement a persistent cache below the LRU cache.
317
 
         */
318
 
        protected void privateNotifyDeletionFromCache(LRUCacheEntry<K,T> entry) {
319
 
                // Default is NOP.
320
 
        }
321
 
        /**
322
 
         * Removes the entry from the entry queue.  
323
 
         * @param shuffle indicates whether we are just shuffling the queue 
324
 
         * (i.e., the entry table is left alone).
325
 
         */
326
 
        protected void privateRemoveEntry (LRUCacheEntry<K,T> entry, boolean shuffle) {
327
 
                
328
 
                LRUCacheEntry<K,T> previous, next;
329
 
                
330
 
                previous = entry._fPrevious;
331
 
                next = entry._fNext;
332
 
                
333
 
                if (!shuffle) {
334
 
                        fEntryTable.remove(entry._fKey);
335
 
                        fCurrentSpace -= entry._fSpace;
336
 
                        privateNotifyDeletionFromCache(entry);
337
 
                }
338
 
 
339
 
                /* if this was the first entry */
340
 
                if (previous == null) {
341
 
                        fEntryQueue = next;
342
 
                } else {
343
 
                        previous._fNext = next;
344
 
                }
345
 
 
346
 
                /* if this was the last entry */
347
 
                if (next == null) {
348
 
                        fEntryQueueTail = previous;
349
 
                } else {
350
 
                        next._fPrevious = previous;
351
 
                }
352
 
        }
353
 
        /**
354
 
         * Sets the value in the cache at the given key. Returns the value.
355
 
         *
356
 
         * @param key Key of object to add.
357
 
         * @param value Value of object to add.
358
 
         * @return added value.
359
 
         */
360
 
        public T put(K key, T value) {
361
 
                
362
 
                int newSpace, oldSpace, newTotal;
363
 
                LRUCacheEntry<K,T> entry;
364
 
                
365
 
                /* Check whether there's an entry in the cache */
366
 
                newSpace = spaceFor (key, value);
367
 
                entry = fEntryTable.get (key);
368
 
                
369
 
                if (entry != null) {
370
 
                        
371
 
                        /**
372
 
                         * Replace the entry in the cache if it would not overflow
373
 
                         * the cache.  Otherwise flush the entry and re-add it so as 
374
 
                         * to keep cache within budget
375
 
                         */
376
 
                        oldSpace = entry._fSpace;
377
 
                        newTotal = getCurrentSpace() - oldSpace + newSpace;
378
 
                        if (newTotal <= getSpaceLimit()) {
379
 
                                updateTimestamp (entry);
380
 
                                entry._fValue = value;
381
 
                                entry._fSpace = newSpace;
382
 
                                this.fCurrentSpace = newTotal;
383
 
                                return value;
384
 
                        }
385
 
                        privateRemoveEntry (entry, false);
386
 
                }
387
 
                if (makeSpace(newSpace)) {
388
 
                        privateAdd (key, value, newSpace);
389
 
                }
390
 
                return value;
391
 
        }
392
 
        /**
393
 
         * Removes and returns the value in the cache for the given key.
394
 
         * If the key is not in the cache, returns null.
395
 
         *
396
 
         * @param key Key of object to remove from cache.
397
 
         * @return Value removed from cache.
398
 
         */
399
 
        public T removeKey (K key) {
400
 
                
401
 
                LRUCacheEntry<K,T> entry = fEntryTable.get(key);
402
 
                if (entry == null) {
403
 
                        return null;
404
 
                }
405
 
                T value = entry._fValue;
406
 
                this.privateRemoveEntry (entry, false);
407
 
                return value;
408
 
        }
409
 
        /**
410
 
         * Sets the maximum amount of space that the cache can store
411
 
         *
412
 
         * @param limit Number of units of cache space
413
 
         */
414
 
        public void setSpaceLimit(int limit) {
415
 
                if (limit < fSpaceLimit) {
416
 
                        makeSpace(fSpaceLimit - limit);
417
 
                }
418
 
                fSpaceLimit = limit;
419
 
        }
420
 
        /**
421
 
         * Returns the space taken by the given key and value.
422
 
         */
423
 
        protected int spaceFor (Object key, Object value) {
424
 
                
425
 
                if (value instanceof ILRUCacheable) {
426
 
                        return ((ILRUCacheable) value).getCacheFootprint();
427
 
                }
428
 
                return 1;
429
 
        }
430
 
/**
431
 
 * Returns a String that represents the value of this object.  This method
432
 
 * is for debugging purposes only.
433
 
 */
434
 
@Override
435
 
public String toString() {
436
 
        return 
437
 
                "LRUCache " + (fCurrentSpace * 100.0 / fSpaceLimit) + "% full\n" + //$NON-NLS-1$ //$NON-NLS-2$
438
 
                this.toStringContents();
439
 
}
440
 
/**
441
 
 * Returns a String that represents the contents of this object.  This method
442
 
 * is for debugging purposes only.
443
 
 */
444
 
protected String toStringContents() {
445
 
        StringBuffer result = new StringBuffer();
446
 
        int length = fEntryTable.size();
447
 
        Object[] unsortedKeys = new Object[length];
448
 
        String[] unsortedToStrings = new String[length];
449
 
        Enumeration<K> e = this.keys();
450
 
        for (int i = 0; i < length; i++) {
451
 
                Object key = e.nextElement();
452
 
                unsortedKeys[i] = key;
453
 
                unsortedToStrings[i] = 
454
 
                        (key instanceof org.eclipse.cdt.internal.core.model.CElement) ?
455
 
                                ((org.eclipse.cdt.internal.core.model.CElement)key).getElementName() :
456
 
                                key.toString();
457
 
        }
458
 
        ToStringSorter sorter = new ToStringSorter();
459
 
        sorter.sort(unsortedKeys, unsortedToStrings);
460
 
        for (int i = 0; i < length; i++) {
461
 
                String toString = sorter.sortedStrings[i];
462
 
                Object value = this.get(sorter.sortedObjects[i]);
463
 
                result.append(toString);                
464
 
                result.append(" -> "); //$NON-NLS-1$
465
 
                result.append(value);
466
 
                result.append("\n"); //$NON-NLS-1$
467
 
        }
468
 
        return   result.toString();
469
 
}
470
 
        /**
471
 
         * Updates the timestamp for the given entry, ensuring that the queue is 
472
 
         * kept in correct order.  The entry must exist
473
 
         */
474
 
        protected void updateTimestamp (LRUCacheEntry<K,T> entry) {
475
 
                
476
 
                entry._fTimestamp = fTimestampCounter++;
477
 
                if (fEntryQueue != entry) {
478
 
                        this.privateRemoveEntry (entry, true);
479
 
                        this.privateAddEntry (entry, true);
480
 
                }
481
 
                return;
482
 
        }
483
 
 
484
 
}