LRUHashtable


1   /*
2   
3   This software is OSI Certified Open Source Software.
4   OSI Certified is a certification mark of the Open Source Initiative.
5   
6   The license (Mozilla version 1.0) can be read at the MMBase site.
7   See http://www.MMBase.org/license
8   
9   */
10  package org.mmbase.util;
11  
12  import org.mmbase.cache.CacheImplementationInterface;
13  import java.util.*;
14  
15  /**
16   * A hashtable which has a maximum of entries.  Old entries are
17   * removed when the maximum is reached.  This table is used mostly to
18   * implement a simple caching system.
19   *
20   * @move consider moving to org.mmbase.cache
21   * @author  Rico Jansen
22   * @author  Michiel Meeuwissen
23   * @version $Id: LRUHashtable.java,v 1.24 2006/02/23 17:37:23 michiel Exp $
24   * @see    org.mmbase.cache.Cache
25   */
26  public class LRUHashtable extends Hashtable implements Cloneable  , CacheImplementationInterface, SizeMeasurable {
27  
28      private static final String   ROOT     = "root";
29      private static final String   DANGLING = "dangling";
30      /**
31       * First (virtual) element of the table.
32       * The element that follows root is the oldest element in the table
33       * (and thus first to be removed if size maxes out).
34       */
35      private final LRUEntry root     = new LRUEntry(ROOT, ROOT);
36      /**
37       * Last (virtual) element of the table.
38       * The element that precedes dangling is the latest element in the table
39       */
40      private final LRUEntry dangling = new LRUEntry(DANGLING, DANGLING);
41  
42      /**
43       * Maximum size (capacity) of the table
44       */
45      private int size = 0;
46      /**
47       * Current size of the table.
48       */
49      private int currentSize = 0;
50  
51      /**
52       * Creates the URL Hashtable.
53       * @param size the maximum capacity
54       * @param cap the starting capacity (used to improve performance)
55       * @param lf the amount with which current capacity frows
56       */
57      public LRUHashtable(int size, int cap, float lf) {
58          super(cap, lf);
59          root.next = dangling;
60          dangling.prev = root;
61          this.size = size;
62      }
63  
64      /**
65       * Creates the URL Hashtable with growing capacity 0.75.
66       * @param size the maximum capacity
67       * @param cap the starting capacity (used to improve performance)
68       */
69      public LRUHashtable(int size, int cap) {
70          this(size, cap, 0.75f);
71      }
72  
73      /**
74       * Creates the URL Hashtable with starting capacity 101 and
75       * growing capacity 0.75.
76       * @param size the maximum capacity
77       */
78      public LRUHashtable(int size) {
79          this(size, 101, 0.75f);
80      }
81  
82      /**
83       * Creates the URL Hashtable with maximum capacity 100,
84       * starting capacity 101, and growing capacity 0.75.
85       */
86      public LRUHashtable() {
87          this(100, 101, 0.75f);
88      }
89  
90      /**
91       * Store an element in the table.
92       * @param key the key of the element
93       * @param value the value of the element
94       * @return the original value of the element if it existed, <code>null</code> if it could not be found
95       */
96      public synchronized Object   put(Object   key, Object   value) {
97          LRUEntry work = (LRUEntry) super.get(key);
98          Object   rtn;
99          if (work != null) {
100             rtn = work.value;
101             work.value = value;
102             removeEntry(work);
103             appendEntry(work);
104         } else {
105             rtn = null;
106             work = new LRUEntry(key, value);
107             super.put(key, work);
108             appendEntry(work);
109             currentSize++;
110             if (currentSize > size) {
111                 remove(root.next.key);
112             }
113         }
114         return rtn;
115     }
116 
117     /**
118      * Retrieves the count of the object with a certain key.
119      * @param key the key of the element
120      * @return the times the key has been requested
121      */
122     public int getCount(Object   key) {
123         LRUEntry work = (LRUEntry) super.get(key);
124         if (work != null) {
125             return work.requestCount;
126         } else {
127             return -1;
128         }
129     }
130 
131     /**
132      * Retrieves an element from the table.
133      * @param key the key of the element
134      * @return the value of the element, or <code>null</code> if it could not be found
135      */
136     public synchronized Object   get(Object   key) {
137         LRUEntry work = (LRUEntry) super.get(key);
138         if (work != null) {
139             work.requestCount++;
140             Object   rtn = work.value;
141             removeEntry(work);
142             appendEntry(work);
143             return rtn;
144         } else {
145             return null;
146         }
147     }
148 
149     /**
150      * Remove an element from the table.
151      * @param key the key of the element
152      * @return the original value of the element if it existed, <code>null</code> if it could not be found
153      */
154     public synchronized Object   remove(Object   key) {
155         LRUEntry work = (LRUEntry) super.remove(key);
156         if (work != null) {
157             Object   rtn = work.value;
158             removeEntry(work);
159             currentSize--;
160             return rtn;
161         } else {
162             return null;
163         }
164     }
165 
166 
167     /**
168      * You should only remove entries from LRUHashtable using the 'remove' function, or using the
169      * iterator of entrySet() otherwise the linked list gets messed up.  The keySet of LRUHashtable
170      * therefore returns an unmodifiable set.
171      * @since MMBase-1.6.3
172      */
173     public Set keySet() {
174         return Collections.unmodifiableSet(super.keySet());
175     }
176 
177     /**
178      * Returns the entries of this Map. Modification are reflected.
179      *
180      * @since MMBase-1.6.3
181      */
182     public Set entrySet() {
183         return new LRUEntrySet();
184     }
185 
186     /**
187      * @see   #keySet
188      * @since MMBase-1.6.3
189      */
190     public Collection values() {
191         return Collections.unmodifiableCollection(super.values());
192     }
193 
194     /**
195      * Return the current size of the table
196      */
197     public int size() {
198         return currentSize;
199     }
200 
201     /**
202      * Change the maximum size of the table.
203      * This may result in removal of entries in the table.
204      * @param size the new desired size
205      */
206     public void setMaxSize(int size) {
207         if (size < 0 ) throw new IllegalArgumentException  ("Cannot set size of LRUHashtable to negative value");
208         if (size < this.size) {
209             while(currentSize > size) {
210                 remove(root.next.key);
211             }
212         }
213         this.size = size;
214     }
215 
216     /**
217      * Return the maximum size of the table
218      */
219     public int maxSize() {
220         return size;
221     }
222 
223     /**
224      * Append an entry to the end of the list.
225      */
226     private void appendEntry(LRUEntry wrk) {
227         dangling.prev.next = wrk;
228         wrk.prev = dangling.prev;
229         wrk.next = dangling;
230         dangling.prev = wrk;
231     }
232 
233     /**
234      * remove an entry from the list.
235      */
236     private void removeEntry(LRUEntry wrk) {
237         wrk.next.prev = wrk.prev;
238         wrk.prev.next = wrk.next;
239         wrk.next = null;
240         wrk.prev = null;
241     }
242 
243     /**
244      * Returns a description of the table.
245      * The information shown includes current size, maximum size, ratio of misses and hits,
246      * and a description of the underlying hashtable
247      */
248     public String   toString() {
249         return "Size=" + currentSize + ", Max=" + size;
250     }
251 
252     /**
253      * Returns a description of the table.
254      * The information shown includes current size, maximum size, ratio of misses and hits,
255      * and either a description of the underlying hashtable, or a list of all stored values.
256      * @param which if <code>true</code>, the stored values are described.
257      * @return a description of the table.
258      */
259     public String   toString(boolean which) {
260         if (which) {
261             StringBuffer   b = new StringBuffer  ();
262             b.append("Size " + currentSize + ", Max " + size + " : ");
263             b.append(super.toString());
264             return b.toString();
265         } else {
266             return toString();
267         }
268     }
269 
270     /**
271      * Clears the table.
272      */
273     public synchronized void clear() {
274         while (root.next != dangling) removeEntry(root.next);
275         super.clear();
276         currentSize = 0;
277     }
278 
279     /**
280      * NOT IMPLEMENTED
281      */
282     public synchronized Object   clone() {
283         throw new UnsupportedOperationException  ();
284     }
285 
286     /**
287      * Returns an <code>Enumeration</code> on the table's element values.
288      */
289     public synchronized Enumeration elements() {
290         return new LRUHashtableEnumeration();
291     }
292 
293 
294 
295     /**
296      * @deprecated use getOrderedEntries
297      */
298     public Enumeration getOrderedElements() {
299         return getOrderedElements(-1);
300     }
301 
302     /**
303      * @deprecated use getOrderedEntries
304      */
305     public Enumeration getOrderedElements(int maxnumber) {
306         List results = new ArrayList();
307         LRUEntry current = root.next;
308         if (maxnumber != -1) {
309             int i = 0;
310             while (current!=null && current!=dangling && i<maxnumber) {
311                 results.add(0, current.value);
312                 current = current.next;
313                 i++;
314             }
315         } else {
316             while (current!=null && current!=dangling) {
317                 results.add(0, current.value);
318                 current = current.next;
319             }
320         }
321         return Collections.enumeration(results);
322     }
323 
324     /**
325      * Returns an ordered list of Map.Entry's.
326      *
327      * @since MMBase-1.6
328      */
329 
330     public List getOrderedEntries() {
331         return getOrderedEntries(-1);
332     }
333 
334     /**
335      * Returns an ordered list of Map.Entry's. This can be used to
336      * present the contents of the LRU Map.
337      *
338      * @since MMBase-1.6
339      */
340 
341     public List getOrderedEntries(int maxNumber) {
342         List results = new ArrayList();
343         LRUEntry current = root.next;
344         int i = 0;
345         while (current != null && current != dangling && (maxNumber < 0 || i < maxNumber)) {
346             results.add(0, current);
347             current = current.next;
348             i++;
349         }
350         return Collections.unmodifiableList(results);
351     }
352 
353 
354     public void config(Map map) {
355         // lru needs no configuration.
356     }
357 
358     public int getByteSize() {
359         return getByteSize(new SizeOf());
360     }
361     public int getByteSize(SizeOf sizeof) {
362         int len = 4 * SizeOf.SZ_REF + (30 + 5 * SizeOf.SZ_REF) * currentSize;  // 30:overhead of Hashtable, 5*SZ_REF: overhead of LRUEntry
363         LRUEntry current = root.next;
364         while (current != null && current != dangling) {
365             current = current.next;
366             len += sizeof.sizeof(current.key);
367             len += sizeof.sizeof(current.value);
368         }
369         return len;
370     }
371 
372     /**
373      * Enumerator for the LRUHashtable.
374      */
375     private class LRUHashtableEnumeration implements Enumeration {
376         private Enumeration superior;
377 
378         LRUHashtableEnumeration() {
379             superior = LRUHashtable.this.elements();
380         }
381 
382         public boolean hasMoreElements() {
383             return superior.hasMoreElements();
384         }
385 
386         public Object   nextElement() {
387             LRUEntry entry = (LRUEntry) superior.nextElement();
388             return entry.value;
389         }
390     }
391 
392 
393     /**
394      * Element used to store information from the LRUHashtable.
395      */
396     public class LRUEntry implements Map.Entry, SizeMeasurable {
397         /**
398          * The element value
399          */
400         protected Object   value;
401         /**
402          * The next, newer, element
403          */
404         protected LRUEntry next;
405         /**
406          * The previous, older, element
407          */
408         protected LRUEntry prev;
409         /**
410          * The element key
411          */
412         protected Object   key;
413         /**
414          * the number of times this
415          * entry has been requested
416          */
417         protected int requestCount = 0;
418 
419         LRUEntry(Object   key, Object   val) {
420             this(key, val, null, null);
421         }
422 
423         LRUEntry(Object   key, Object   value, LRUEntry prev, LRUEntry next) {
424             this.value = value;
425             this.next  = next;
426             this.prev  = prev;
427             this.key   = key;
428         }
429 
430         public Object   getKey() {
431             return key;
432         }
433 
434         public Object   getValue() {
435             return value;
436         }
437 
438         public Object   setValue(Object   o) {
439             throw new UnsupportedOperationException  ("Cannot change values in LRU Hashtable");
440         }
441 
442         public int getByteSize() {
443             return new SizeOf().sizeof(value);
444         }
445         public int getByteSize(SizeOf sizeof) {
446             return 20 + // 5 references
447                 sizeof.sizeof(value);
448         }
449         public String   toString() {
450             return  value == LRUHashtable.this ? "[this lru]" : String.valueOf(value);
451         }
452 
453     }
454     /**
455      * Used by 'entrySet' implementation, to make the Map modifiable.
456      * @since MMBase-1.7.2
457      */
458     protected class LRUEntrySet extends AbstractSet {
459         Set set;
460         LRUEntrySet() {
461             set = LRUHashtable.super.entrySet();
462         }
463         public int size() {
464             return set.size();
465         }
466         public Iterator iterator() {
467             return new LRUEntrySetIterator(set.iterator());
468         }
469     }
470 
471     /**
472      * Used by 'entrySet' implementation, to make the Map modifiable.
473      * @since MMBase-1.7.2
474      */
475     protected class LRUEntrySetIterator implements Iterator {
476         Iterator it;
477         LRUEntry work;
478         LRUEntrySetIterator(Iterator i ) {
479             it = i;
480         }
481         public boolean  hasNext() {
482             return it.hasNext();
483         }
484         public Object   next() {
485             Map.Entry entry = (Map.Entry) it.next();
486             work = (LRUEntry) entry.getValue();
487             return work;
488         }
489         public void remove() {
490             it.remove();
491             if (work != null) {
492                 LRUHashtable.this.removeEntry(work);
493                 LRUHashtable.this.currentSize--;
494             }
495         }
496     }
497 
498     public static void main(String   argv[]) {
499         int treesiz = 1024;
500         int opers = 1000000;
501         int thrds  = 1;
502 
503         try {
504             if (argv.length > 0) {
505                 treesiz = Integer.parseInt(argv[0]);
506             }
507             if (argv.length > 1) {
508                 opers = Integer.parseInt(argv[1]);
509             }
510             if (argv.length > 2) {
511                 thrds = Integer.parseInt(argv[2]);
512             }
513         } catch (Exception   e) {
514             System.out.println("Usage: java org.mmbase.util.LRUHashtable <size of table> <number of operation to do> <threads>");
515             return;
516         }
517 
518         final int TREESIZ = treesiz;
519         final int OPERS = opers;
520         final int THREADS = thrds;
521 
522         final LRUHashtable treap = new LRUHashtable(TREESIZ);
523         long ll1 = System.currentTimeMillis();
524 
525         // fill the map
526         for (int i = 0; i < TREESIZ; i++) {
527             treap.put(""+i,""+i);
528         }
529         long ll2=System.currentTimeMillis();
530         System.out.println("Size "+treap.size());
531 
532         if (TREESIZ <= 1024) {
533             System.out.println("LRUHashtable initaly " + treap.toString(true));
534         }
535 
536         final  int score[][] = new int[TREESIZ][THREADS];
537         long ll3 = System.currentTimeMillis();
538 
539         Thread  [] threads = new Thread  [THREADS];
540         for (int t = 0; t < THREADS; t++) {
541             final int  threadnr = t;
542             Runnable   runnable = new Runnable  () {
543                     public void run() {
544                         if (THREADS > 1) {
545                             System.out.println("Thread " + threadnr + " started");
546                         }
547                         Random rnd = new Random();
548                         for (int i = 0;i<OPERS;i++) {
549                             // Put and get mixed
550                             int j = Math.abs(rnd.nextInt())%(TREESIZ/2)+(TREESIZ/4);
551                             int k = Math.abs(rnd.nextInt())%2;
552                             Object   rtn;
553                             switch (k) {
554                             case 0:
555                                 rtn=treap.put(""+j,""+j);
556                                 score[j][threadnr]++;
557                                 break;
558                             case 1:
559                                 rtn=treap.get(""+j);
560                                 score[j][threadnr]++;
561                                 break;
562                             }
563                             // Only a get
564                             j = Math.abs(rnd.nextInt())%(TREESIZ);
565                             rtn = treap.get(""+j);
566                             score[j][threadnr]++;
567                         }
568                         if (THREADS > 1) {
569                             System.out.println("Thread " + threadnr + " ready");
570                         }
571                     }
572             };
573             threads[t] = new Thread  (runnable);
574             threads[t].start();
575         }
576         long ll4 = System.currentTimeMillis();
577         for (int i = 0; i < THREADS; i++) {
578             try {
579                 threads[i].join();
580             } catch (InterruptedException   ie) {
581                 System.err.println("Interrupted");
582             }
583         }
584                 
585         long ll5 = System.currentTimeMillis();
586         if (TREESIZ <= 1024) {
587             System.out.println("LRUHashtable afterwards " + treap.toString(true));
588 
589             for (int i = 0; i <TREESIZ; i++) {
590                 int totscore = 0;
591                 for (int j = 0; j < THREADS; j++) {
592                     totscore += score[i][j];
593                 }
594                 System.out.println("" + i + " score " + totscore);
595             }
596         }
597         System.out.println("Creation " + (ll2-ll1) + " ms");
598         System.out.println("Thread starting " + (ll4-ll3) + " ms");
599         if (TREESIZ <= 1024) {
600             System.out.println("Print    " + (ll3-ll2) + " ms");
601         } else {
602             System.out.println("Not printed (too huge)");
603         }
604         long timePerKop = (ll5 - ll3) * 1000 / (OPERS);
605         System.out.println("Run      " + (ll5-ll3) + " ms (" + timePerKop + " ms/koperation,  " + (timePerKop / THREADS) + " ms/koperation total from " + THREADS + " threads)");
606     }
607 }
608 
609 
610 
611
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags