Main Page | Class Hierarchy | Alphabetical List | Class List | Directories | 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                 // cast to void* first to avoid overhead
00101                 QueuedEntry entry = cast(QueuedEntry) cast(void*) super.get (key);
00102 
00103                 // if we find 'key' then move it to the list head
00104                 if (entry)
00105                     return reReference (entry).entry;
00106                 return null;
00107         }
00108 
00109         /**********************************************************************
00110 
00111                 Place an entry into the cache and associate it with the
00112                 provided key. Note that there can be only one entry for
00113                 any particular key. If two entries are added with the 
00114                 same key, the second effectively overwrites the first.
00115 
00116                 Returns what it was given
00117 
00118         **********************************************************************/
00119 
00120         override IPayload put (char[] key, IPayload item)
00121         in {
00122            assert (key.length);
00123            assert (item);
00124            }
00125         body
00126         {
00127                 IPayload e = super.get (key);
00128 
00129                 // already in the list? -- replace entry
00130                 if (e)
00131                    {
00132                    // cast to void* first to avoid overhead
00133                    QueuedEntry q = cast(QueuedEntry) cast(void*) e;
00134 
00135                    // set the new item for this key and move to list head
00136                    q.set (key, item);
00137                    reReference (q);
00138                    }
00139                 else
00140                    // create a new entry at the list head 
00141                    super.put (key, addEntry (key, item));
00142                 return item;
00143         }
00144 
00145         /**********************************************************************
00146 
00147                 Remove (and return) the cache entry associated with the 
00148                 provided key. Returns null if there is no such entry.
00149 
00150         **********************************************************************/
00151 
00152         override IPayload extract (char[] key, ulong timeLimit = ulong.max)
00153         in {
00154            assert (key.length);
00155            }
00156         body
00157         {
00158                 // remove from the lookup table
00159                 // cast to void* first to avoid overhead
00160                 QueuedEntry old = cast(QueuedEntry) cast(void*) super.extract (key, timeLimit);
00161 
00162                 // don't actually kill the list entry -- just place
00163                 // it at the list 'tail' ready for subsequent reuse
00164                 if (old)
00165                    {
00166                    IPayload e = deReference (old).entry;
00167                    old.set (null, null);
00168                    return e;
00169                    }
00170 
00171                 return null;
00172         }
00173 
00174         /**********************************************************************
00175 
00176                 Overridable factory for creating list entries.
00177 
00178         **********************************************************************/
00179 
00180         QueuedEntry createQueuedEntry (char[] key, IPayload entry)
00181         in {
00182            assert (key.length);
00183            assert (entry);
00184            }
00185         body
00186         {
00187                 return new QueuedEntry (key, entry);
00188         }
00189 
00190         /**********************************************************************
00191 
00192                 Place a cache entry at the tail of the queue. This makes
00193                 it the least-recently referenced.
00194 
00195         **********************************************************************/
00196 
00197         private final QueuedEntry deReference (QueuedEntry entry)
00198         {
00199                 if (! (entry is tail))
00200                    {
00201                    // adjust head
00202                    if (entry is head)
00203                        head = entry.next;
00204 
00205                    // move to tail
00206                    entry.extract ();
00207                    tail = entry.append (tail);
00208                    }
00209                 return entry;
00210         }
00211 
00212         /**********************************************************************
00213 
00214                 Move a cache entry to the head of the queue. This makes
00215                 it the most-recently referenced.
00216 
00217         **********************************************************************/
00218 
00219         private final QueuedEntry reReference (QueuedEntry entry)
00220         {
00221                 if (! (entry is head))
00222                    {
00223                    // adjust tail
00224                    if (entry is tail)
00225                        tail = entry.prev;
00226 
00227                    // move to head
00228                    entry.extract ();
00229                    head = entry.prepend (head);
00230                    }
00231                 return entry;
00232         }
00233 
00234         /**********************************************************************
00235 
00236                 Add an entry into the queue. If the queue is full, the
00237                 least-recently-referenced entry is reused for the new
00238                 addition. 
00239 
00240         **********************************************************************/
00241 
00242         private final QueuedEntry addEntry (char[] key, IPayload item)
00243         {
00244                 QueuedEntry entry;
00245 
00246                 if (entries < capacity)
00247                    {
00248                    // create a new item
00249                    entry = createQueuedEntry (key, item);
00250 
00251                    // set 'head' & 'tail' if first item in list. We need to
00252                    // do this before reReference() is invoked so it doesn't
00253                    // have to do "first item" checks itself
00254                    if (++entries == 1)
00255                        head = tail = entry;
00256                    }
00257                 else
00258                    if (capacity > 0)
00259                       {
00260                       // steal from tail ...
00261                       entry = tail;
00262 
00263                       // we're re-using an old QueuedEntry, so remove
00264                       // the old name from the hash-table first
00265                       super.extract (entry.key);
00266 
00267                       // replace old content with new (also destroy old)
00268                       entry.reuse (key, item);
00269                       }
00270                    else
00271                       return null;
00272 
00273                 // place at head of list
00274                 return reReference (entry);
00275         }
00276 }
00277 
00278 
00279 /******************************************************************************
00280 
00281         A doubly-linked list entry, used as a wrapper for queued cache 
00282         entries. Note that this class itself is a valid cache entry.
00283 
00284 ******************************************************************************/
00285 
00286 protected class QueuedEntry : Payload
00287 {
00288         protected char[]        key;
00289         protected QueuedEntry   prev,
00290                                 next;
00291         protected IPayload      entry;
00292 
00293         /**********************************************************************
00294 
00295                 Construct a new linked-list entry around the provided 
00296                 IPayload instance, and associate it with the given
00297                 key. Note that the key is held here such that it can
00298                 be referenced by sub-classes which override the reuse()
00299                 method.
00300         
00301         **********************************************************************/
00302 
00303         this (char[] key, IPayload entry)
00304         {
00305                 this.key = key;
00306                 this.entry = entry;
00307         }
00308 
00309         /**********************************************************************
00310 
00311                 Set this linked-list entry with the given arguments. Note
00312                 that the original content is released via a destroy() call.
00313 
00314         **********************************************************************/
00315 
00316         protected void set (char[] key, IPayload entry)
00317         {
00318                 // destroy any existing object first
00319                 if (! (this.entry is entry))
00320                        destroy ();
00321 
00322                 this.entry = entry;
00323                 this.key = key;
00324         }
00325 
00326         /**********************************************************************
00327 
00328                 Overridable method to reuse this linked-list entry. The
00329                 default behavior is to destroy() the original content.
00330 
00331         **********************************************************************/
00332 
00333         protected void reuse (char[] key, IPayload entry)
00334         {
00335                 set (key, entry);
00336         }
00337 
00338         /**********************************************************************
00339 
00340                 Insert this entry into the linked-list just in front of
00341                 the given entry.
00342 
00343         **********************************************************************/
00344 
00345         protected QueuedEntry prepend (QueuedEntry before)
00346         in {
00347            assert (before);
00348            }
00349         body
00350         {
00351                 if (before)
00352                    {
00353                    prev = before.prev;
00354 
00355                    // patch 'prev' to point at me
00356                    if (prev)
00357                        prev.next = this;
00358 
00359                    //patch 'before' to point at me
00360                    next = before;
00361                    before.prev = this;
00362                    }
00363                 return this;
00364         }
00365 
00366         /**********************************************************************
00367                 
00368                 Add this entry into the linked-list just after the given
00369                 entry.
00370 
00371         **********************************************************************/
00372 
00373         protected QueuedEntry append (QueuedEntry after)
00374         in {
00375            assert (after);
00376            }
00377         body
00378         {
00379                 if (after)
00380                    {
00381                    next = after.next;
00382 
00383                    // patch 'next' to point at me
00384                    if (next)
00385                        next.prev = this;
00386 
00387                    //patch 'after' to point at me
00388                    prev = after;
00389                    after.next = this;
00390                    }
00391                 return this;
00392         }
00393 
00394         /**********************************************************************
00395 
00396                 Remove this entry from the linked-list. The previous and
00397                 next entries are patched together appropriately.
00398 
00399         **********************************************************************/
00400 
00401         protected QueuedEntry extract ()
00402         {
00403                 // make 'prev' and 'next' entries see each other
00404                 if (prev)
00405                     prev.next = next;
00406 
00407                 if (next)
00408                     next.prev = prev;
00409 
00410                 // Murphy's law 
00411                 next = prev = null;
00412                 return this;
00413         }
00414 
00415         /**********************************************************************
00416 
00417                 Return the key belonging to this entry.
00418 
00419         **********************************************************************/
00420 
00421         override char[] toString()
00422         {
00423                 return key;
00424         }
00425 
00426         /**********************************************************************
00427 
00428                 Destroy this linked list entry by invoking destroy() on the
00429                 wrapped IPayload.
00430 
00431         **********************************************************************/
00432 
00433         protected void destroy()
00434         {
00435                 if (entry)
00436                    {
00437                    entry.destroy ();
00438                    this.entry = null;
00439                    }
00440         }
00441 }
00442 

Generated on Sat Dec 24 17:28:33 2005 for Mango by  doxygen 1.4.0