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

Generated on Tue Jan 25 21:18:22 2005 for Mango by doxygen 1.3.6