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