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