You can edit this page using wiki syntax for markup.

Article contents:== Outdated egg! This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for [[/eggref/5/lru-cache|the CHICKEN 5 version of this egg]], if it exists. If it does not exist, there may be equivalent functionality provided by another egg; have a look at the [[https://wiki.call-cc.org/chicken-projects/egg-index-5.html|egg index]]. Otherwise, please consider porting this egg to the current version of CHICKEN. == lru-cache '''lru-cache''' implements an LRU cache of N elements. It uses a hash table for fast lookup and a doubly-linked list to maintain LRU ordering. As the hash table associates keys with list nodes, items may be reordered without traversing the list. [[toc:]] === Interface ==== make-lru-cache <procedure>(make-lru-cache capacity equal? [deleter])</procedure> Create an LRU cache capable of holding {{capacity}} items. {{equal?}} is the item equality procedure and is passed directly to the hash table, as in {{(make-hash-table equal?)}}. {{deleter}} is an optional procedure of two arguments {{(key value)}} which will be invoked whenever an item is deleted, flushed or simply falls off the cache. If {{capacity}} is zero, the cache is disabled. Attempts to read items will return {{#f}}, and writing them will silently fail. ==== lru-cache-ref <procedure>(lru-cache-ref cache key)</procedure> Looks up the item matching {{key}} and returns the associated value, or {{#f}} if no such item exists. If the item is not the most-recently used, it is marked as MRU (in other words, moved to the head of the list). If the item is the most-recently used, the LRU list structure is not modified, and consequently the item is returned a bit faster. ==== lru-cache-set! <procedure>(lru-cache-set! cache key val)</procedure> Add an item into the cache which associates {{key}} with {{val}}, or if an item matching {{key}} already exists, updates the item to the new {{val}}. If the key did not exist, the item is marked as the most-recently used. If the key did exist, the LRU ordering behavior is undefined; currently -- and don't take this for granted -- the LRU order is not updated. If adding this item causes the cache to exceed its capacity, the least-recently used item is deleted, and consequently the deleter (if provided) is invoked. If the deleter throws an exception, the item remains in the cache, and the new item is not added. ==== lru-cache-delete! <procedure>(lru-cache-delete! cache key)</procedure> Deletes the item matching {{key}} from {{cache}}. If no corresponding item exists, the procedure silently fails. The deleter, if provided, will be invoked for this item. Note: if the deleter throws an exception, the item is ''not'' deleted from the cache. ==== lru-cache-flush! <procedure>(lru-cache-flush! cache)</procedure> Delete all items in {{cache}}. The deleter procedure (if provided to {{make-lru-cache}}) is invoked for each item as the item list is traversed from head to tail. If an error occurs in the deleter, the offending item will be left at the head of the cache. ==== lru-cache-walk <procedure>(lru-cache-walk cache proc)</procedure> Call {{(proc key value)}} for each item in the cache, returning an unspecified value. Items are traversed from MRU to LRU. ==== lru-cache-fold <procedure>(lru-cache-fold cache kons knil)</procedure> Iterate over the items in the cache in order from MRU to LRU. {{kons}} is called with three arguments: {{k}}, the item's key; {{v}}, the item's value; and {{s}}, the current state. The initial state is set to {{knil}}, and the return value from the call to {{kons}} is passed as the next state value to {{kons}}. For example, to build a list of {{(key . value)}} pairs in {{cache}} from LRU to MRU, execute: (lru-cache-fold cache (lambda (k v s) (cons (cons k v) s)) '()) ==== lru-cache-size <procedure>(lru-cache-size cache)</procedure> Returns the number of items currently in the cache. ==== lru-cache-capacity <procedure>(lru-cache-capacity cache)</procedure> Returns the capacity of the cache in items. === Example (use lru-cache) (define C (make-lru-cache 4 string=? (lambda (k v) (printf "deleting (~S ~S)\n" k v)))) (lru-cache-set! C "a" 1) ; a (lru-cache-set! C "b" 2) ; b a (lru-cache-set! C "c" 3) ; c b a (lru-cache-set! C "d" 4) ; d c b a (lru-cache-walk C print) ;; d4 ;; c3 ;; b2 ;; a1 (lru-cache-set! C "e" 5) ; e d c b ;; deleting (a 1) (lru-cache-ref C "b") ; 2, b e d c (lru-cache-ref C "d") ; 4, d b e c (lru-cache-walk C print) ;; d4 ;; b2 ;; e5 ;; c3 (lru-cache-delete! C "e") ; d b c ;; deleting ("e" 5) (lru-cache-set! C "a" 6) ; a d b c (lru-cache-flush! C) ;; deleting ("a" 6) ;; deleting ("d" 4) ;; deleting ("b" 2) ;; deleting ("c" 3) (lru-cache-walk C print) === Author [[http://3e8.org/zb|Jim Ursetto]] === Version history * 0.5 (2009-03-23): Initial release === License Copyright (c) 2009 Jim Ursetto. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of the author nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. Description of your changes:

I would like to authenticate

Spam control

What do you get when you multiply 8 by 7?