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