Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages

QueuedCache.d

Go to the documentation of this file.
00001 /*******************************************************************************
00002 
00003         @file QueuedCache.d
00004         
00005         Copyright (C) 2004 Kris Bell
00006         
00007         This software is provided 'as-is', without any express or implied
00008         warranty. In no event will the authors be held liable for damages
00009         of any kind arising from the use of this software.
00010         
00011         Permission is hereby granted to anyone to use this software for any 
00012         purpose, including commercial applications, and to alter it and/or 
00013         redistribute it freely, subject to the following restrictions:
00014         
00015         1. The origin of this software must not be misrepresented; you must 
00016            not claim that you wrote the original software. If you use this 
00017            software in a product, an acknowledgment within documentation of 
00018            said product would be appreciated but is not required.
00019 
00020         2. Altered source versions must be plainly marked as such, and must 
00021            not be misrepresented as being the original software.
00022 
00023         3. This notice may not be removed or altered from any distribution
00024            of the source.
00025 
00026 
00027                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
00028 
00029         
00030         @version        Initial version, April 2004      
00031         @author         Kris
00032 
00033 
00034 *******************************************************************************/
00035 
00036 module mango.cache.QueuedCache;
00037 
00038 private import  mango.cache.Payload,
00039                 mango.cache.PlainCache;
00040 
00041 private import  mango.cache.model.IPayload;
00042 
00043 /******************************************************************************
00044 
00045         QueuedCache extends the basic cache type by adding a limit to 
00046         the number of items contained at any given time. In addition, 
00047         QueuedCache sorts the cache entries such that those entries 
00048         frequently accessed are at the head of the queue, and those
00049         least frequently accessed are at the tail. When the queue 
00050         becomes full, old entries are dropped from the tail and are 
00051         reused to house new cache entries.
00052 
00053         This is great for keeping commonly accessed items around, while
00054         limiting the amount of memory used. Typically, the queue size 
00055         would be set in the hundreds (perhaps thousands). 
00056 
00057 ******************************************************************************/
00058 
00059 class QueuedCache : PlainCache
00060 {
00061         // head and tail of queue
00062         private QueuedEntry     head,
00063                                 tail;
00064 
00065         // dimension of queue
00066         private int             entries,
00067                                 capacity;
00068 
00069         /**********************************************************************
00070 
00071                 Construct a cache with the specified maximum number of 
00072                 entries. Additions to the cache beyond this number will
00073                 reuse the slot of the least-recently-referenced cache
00074                 entry. The concurrency level indicates approximately how 
00075                 many threads will content for write access at one time.
00076 
00077         **********************************************************************/
00078 
00079         this (uint capacity, uint concurrency = 16)
00080         {
00081                 super (capacity, concurrency);
00082                 this.capacity = capacity;
00083         }
00084 
00085         /**********************************************************************
00086 
00087                 Get the cache entry identified by the given key
00088 
00089         **********************************************************************/
00090 
00091         override IPayload get (char[] key)
00092         in {
00093            assert (key.length);
00094            }
00095         body
00096         {
00097                 QueuedEntry entry = cast(QueuedEntry) super.get (key);
00098 
00099                 // if we find 'key' then move it to the list head
00100                 if (entry)
00101                     return reReference (entry).entry;
00102                 return null;
00103         }
00104 
00105         /**********************************************************************
00106 
00107                 Place an entry into the cache and associate it with the
00108                 provided key. Note that there can be only one entry for
00109                 any particular key. If two entries are added with the 
00110                 same key, the second effectively overwrites the first.
00111 
00112                 Returns what it was given
00113 
00114         **********************************************************************/
00115 
00116         override IPayload put (char[] key, IPayload item)
00117         in {
00118            assert (key.length);
00119            assert (item);
00120            }
00121         body
00122         {
00123                 IPayload e = super.get (key);
00124 
00125                 // already in the list? -- replace entry
00126                 if (e)
00127                    {
00128                    QueuedEntry q = cast(QueuedEntry) e;
00129 
00130                    // set the new item for this key and move to list head
00131                    q.set (key, item);
00132                    reReference (q);
00133                    }
00134                 else
00135                    // create a new entry at the list head 
00136                    super.put (key, addEntry (key, item));
00137                 return item;
00138         }
00139 
00140         /**********************************************************************
00141 
00142                 Remove (and return) the cache entry associated with the 
00143                 provided key. Returns null if there is no such entry.
00144 
00145         **********************************************************************/
00146 
00147         override IPayload extract (char[] key, ulong timeLimit = ulong.max)
00148         in {
00149            assert (key.length);
00150            }
00151         body
00152         {
00153                 // remove from the lookup table
00154                 QueuedEntry old = cast(QueuedEntry) super.extract (key, timeLimit);
00155 
00156                 // don't actually kill the list entry -- just place
00157                 // it at the list 'tail' ready for subsequent reuse
00158                 if (old)
00159                    {
00160                    IPayload e = deReference (old).entry;
00161                    old.set (null, null);
00162                    return e;
00163                    }
00164 
00165                 return null;
00166         }
00167 
00168         /**********************************************************************
00169 
00170                 Overridable factory for creating list entries.
00171 
00172         **********************************************************************/
00173 
00174         QueuedEntry createQueuedEntry (char[] key, IPayload entry)
00175         in {
00176            assert (key.length);
00177            assert (entry);
00178            }
00179         body
00180         {
00181                 return new QueuedEntry (key, entry);
00182         }
00183 
00184         /**********************************************************************
00185 
00186                 Place a cache entry at the tail of the queue. This makes
00187                 it the least-recently referenced.
00188 
00189         **********************************************************************/
00190 
00191         private final QueuedEntry deReference (QueuedEntry entry)
00192         {
00193                 if (! (entry is tail))
00194                    {
00195                    // adjust head
00196                    if (entry is head)
00197                        head = entry.next;
00198 
00199                    // move to tail
00200                    entry.extract ();
00201                    tail = entry.append (tail);
00202                    }
00203                 return entry;
00204         }
00205 
00206         /**********************************************************************
00207 
00208                 Move a cache entry to the head of the queue. This makes
00209                 it the most-recently referenced.
00210 
00211         **********************************************************************/
00212 
00213         private final QueuedEntry reReference (QueuedEntry entry)
00214         {
00215                 if (! (entry is head))
00216                    {
00217                    // adjust tail
00218                    if (entry is tail)
00219                        tail = entry.prev;
00220 
00221                    // move to head
00222                    entry.extract ();
00223                    head = entry.prepend (head);
00224                    }
00225                 return entry;
00226         }
00227 
00228         /**********************************************************************
00229 
00230                 Add an entry into the queue. If the queue is full, the
00231                 least-recently-referenced entry is reused for the new
00232                 addition. 
00233 
00234         **********************************************************************/
00235 
00236         private final QueuedEntry addEntry (char[] key, IPayload item)
00237         {
00238                 QueuedEntry entry;
00239 
00240                 if (entries < capacity)
00241                    {
00242                    // create a new item
00243                    entry = createQueuedEntry (key, item);
00244 
00245                    // set 'head' & 'tail' if first item in list. We need to
00246                    // do this before reReference() is invoked so it doesn't
00247                    // have to do "first item" checks itself
00248                    if (++entries == 1)
00249                        head = tail = entry;
00250                    }
00251                 else
00252                    if (capacity > 0)
00253                       {
00254                       // steal from tail ...
00255                       entry = tail;
00256 
00257                       // we're re-using an old QueuedEntry, so remove
00258                       // the old name from the hash-table first
00259                       super.extract (entry.key);
00260 
00261                       // replace old content with new (also destroy old)
00262                       entry.reuse (key, item);
00263                       }
00264                    else
00265                       return null;
00266 
00267                 // place at head of list
00268                 return reReference (entry);
00269         }
00270 }
00271 
00272 
00273 /******************************************************************************
00274 
00275         A doubly-linked list entry, used as a wrapper for queued cache 
00276         entries. Note that this class itself is a valid cache entry.
00277 
00278 ******************************************************************************/
00279 
00280 protected class QueuedEntry : Payload
00281 {
00282         protected char[]        key;
00283         protected QueuedEntry   prev,
00284                                 next;
00285         protected IPayload      entry;
00286 
00287         /**********************************************************************
00288 
00289                 Construct a new linked-list entry around the provided 
00290                 IPayload instance, and associate it with the given
00291                 key. Note that the key is held here such that it can
00292                 be referenced by sub-classes which override the reuse()
00293                 method.
00294         
00295         **********************************************************************/
00296 
00297         this (char[] key, IPayload entry)
00298         {
00299                 this.key = key;
00300                 this.entry = entry;
00301         }
00302 
00303         /**********************************************************************
00304 
00305                 Set this linked-list entry with the given arguments. Note
00306                 that the original content is released via a destroy() call.
00307 
00308         **********************************************************************/
00309 
00310         protected void set (char[] key, IPayload entry)
00311         {
00312                 // destroy any existing object first
00313                 if (! (this.entry is entry))
00314                        destroy ();
00315 
00316                 this.entry = entry;
00317                 this.key = key;
00318         }
00319 
00320         /**********************************************************************
00321 
00322                 Overridable method to reuse this linked-list entry. The
00323                 default behavior is to destroy() the original content.
00324 
00325         **********************************************************************/
00326 
00327         protected void reuse (char[] key, IPayload entry)
00328         {
00329                 set (key, entry);
00330         }
00331 
00332         /**********************************************************************
00333 
00334                 Insert this entry into the linked-list just in front of
00335                 the given entry.
00336 
00337         **********************************************************************/
00338 
00339         protected QueuedEntry prepend (QueuedEntry before)
00340         in {
00341            assert (before);
00342            }
00343         body
00344         {
00345                 if (before)
00346                    {
00347                    prev = before.prev;
00348 
00349                    // patch 'prev' to point at me
00350                    if (prev)
00351                        prev.next = this;
00352 
00353                    //patch 'before' to point at me
00354                    next = before;
00355                    before.prev = this;
00356                    }
00357                 return this;
00358         }
00359 
00360         /**********************************************************************
00361                 
00362                 Add this entry into the linked-list just after the given
00363                 entry.
00364 
00365         **********************************************************************/
00366 
00367         protected QueuedEntry append (QueuedEntry after)
00368         in {
00369            assert (after);
00370            }
00371         body
00372         {
00373                 if (after)
00374                    {
00375                    next = after.next;
00376 
00377                    // patch 'next' to point at me
00378                    if (next)
00379                        next.prev = this;
00380 
00381                    //patch 'after' to point at me
00382                    prev = after;
00383                    after.next = this;
00384                    }
00385                 return this;
00386         }
00387 
00388         /**********************************************************************
00389 
00390                 Remove this entry from the linked-list. The previous and
00391                 next entries are patched together appropriately.
00392 
00393         **********************************************************************/
00394 
00395         protected QueuedEntry extract ()
00396         {
00397                 // make 'prev' and 'next' entries see each other
00398                 if (prev)
00399                     prev.next = next;
00400 
00401                 if (next)
00402                     next.prev = prev;
00403 
00404                 // Murphy's law 
00405                 next = prev = null;
00406                 return this;
00407         }
00408 
00409         /**********************************************************************
00410 
00411                 Return the key belonging to this entry.
00412 
00413         **********************************************************************/
00414 
00415         override char[] toString()
00416         {
00417                 return key;
00418         }
00419 
00420         /**********************************************************************
00421 
00422                 Destroy this linked list entry by invoking destroy() on the
00423                 wrapped IPayload.
00424 
00425         **********************************************************************/
00426 
00427         protected void destroy()
00428         {
00429                 if (entry)
00430                    {
00431                    entry.destroy ();
00432                    this.entry = null;
00433                    }
00434         }
00435 }
00436 

Generated on Sun Nov 7 19:06:52 2004 for Mango by doxygen 1.3.6