Moved LRU to its own file

6 files changed, 355 insertions, 315 deletions

diff --git a/FishsFish.xcodeproj/project.pbxproj b/FishsFish.xcodeproj/project.pbxproj
index 84aecc70..8ec66f3e 100644
--- a/FishsFish.xcodeproj/project.pbxproj
+++ b/FishsFish.xcodeproj/project.pbxproj
@@ -7,6 +7,8 @@
 	objects = {
 
 /* Begin PBXFileReference section */
+		D03EE83714DF88B200FC7150 /* lru.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = lru.cpp; sourceTree = "<group>"; };
+		D03EE83814DF88B200FC7150 /* lru.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = lru.h; sourceTree = "<group>"; };
 		D049018814B3802E003CEFBC /* builtin_scripts.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = builtin_scripts.cpp; sourceTree = "<group>"; };
 		D049018914B3802E003CEFBC /* builtin_scripts.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = builtin_scripts.h; sourceTree = "<group>"; };
 		D0A0850313B3ACEE0099B651 /* builtin.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = builtin.h; sourceTree = "<group>"; };
@@ -176,6 +178,8 @@
 				D0A0851813B3ACEE0099B651 /* kill.h */,
 				D0A0854F13B3ACEE0099B651 /* kill.cpp */,
 				D0A0854E13B3ACEE0099B651 /* key_reader.cpp */,
+				D03EE83814DF88B200FC7150 /* lru.h */,
+				D03EE83714DF88B200FC7150 /* lru.cpp */,
 				D0A0851913B3ACEE0099B651 /* mimedb.h */,
 				D0A0855013B3ACEE0099B651 /* mimedb.cpp */,
 				D0A0851A13B3ACEE0099B651 /* output.h */,
diff --git a/autoload.cpp b/autoload.cpp
index 69461c09..f7968ac3 100644
--- a/autoload.cpp
+++ b/autoload.cpp
@@ -37,125 +37,6 @@ file_access_attempt_t access_file(const wcstring &path, int mode) {
     return result;
 }
 
-lru_cache_impl_t::lru_cache_impl_t(size_t size) : max_node_count(size), node_count(0), mouth(L"") {
-    /* Hook up the mouth to itself: a one node circularly linked list */
-    mouth.prev = mouth.next = &mouth;
-}
-
-void lru_cache_impl_t::node_was_evicted(lru_node_t *node) { }
-
-void lru_cache_impl_t::evict_node(lru_node_t *condemned_node) {
-    /* We should never evict the mouth */
-    assert(condemned_node != NULL && condemned_node != &mouth);
-
-    /* Remove it from the linked list */
-    condemned_node->prev->next = condemned_node->next;
-    condemned_node->next->prev = condemned_node->prev;
-
-    /* Remove us from the set */
-    node_set.erase(condemned_node);
-    node_count--;
-
-    /* Tell ourselves */
-    this->node_was_evicted(condemned_node);
-}
-
-void lru_cache_impl_t::evict_last_node(void) {
-    /* Simple */
-    evict_node(mouth.prev);
-}
-
-bool lru_cache_impl_t::evict_node(const wcstring &key) {
-    /* Construct a fake node as our key */
-    lru_node_t node_key(key);
-    
-    /* Look for it in the set */
-    node_set_t::iterator iter = node_set.find(&node_key);
-    if (iter == node_set.end())
-        return false;
-    
-    /* Evict the given node */
-    evict_node(*iter);
-    return true;
-}
-
-void lru_cache_impl_t::promote_node(lru_node_t *node) {
-    /* We should never promote the mouth */
-    assert(node != &mouth);
-    
-    /* First unhook us */
-    node->prev->next = node->next;
-    node->next->prev = node->prev;
-    
-    /* Put us after the mouth */
-    node->next = mouth.next;
-    node->next->prev = node;
-    node->prev = &mouth;
-    mouth.next = node;
-}
-
-bool lru_cache_impl_t::add_node(lru_node_t *node) {
-    /* Add our node without eviction */
-    if (! this->add_node_without_eviction(node))
-        return false;
-    
-    /* Evict */
-    while (node_count > max_node_count)
-        evict_last_node();
-    
-    /* Success */
-    return true;
-}
-
-bool lru_cache_impl_t::add_node_without_eviction(lru_node_t *node) {
-    assert(node != NULL && node != &mouth);
-    
-    /* Try inserting; return false if it was already in the set */
-    if (! node_set.insert(node).second)
-        return false;
-    
-    /* Add the node after the mouth */
-    node->next = mouth.next;
-    node->next->prev = node;
-    node->prev = &mouth;
-    mouth.next = node;
-    
-    /* Update the count */
-    node_count++;
-    
-    /* Evict */
-    while (node_count > max_node_count)
-        evict_last_node();
-    
-    /* Success */
-    return true;
-}
-
-lru_node_t *lru_cache_impl_t::get_node(const wcstring &key) {
-    lru_node_t *result = NULL;
-    
-    /* Construct a fake node as our key */
-    lru_node_t node_key(key);
-    
-    /* Look for it in the set */
-    node_set_t::iterator iter = node_set.find(&node_key);
-    
-    /* If we found a node, promote and return it */
-    if (iter != node_set.end()) {
-        result = *iter;
-        promote_node(result);
-    }
-    return result;
-}
-
-void lru_cache_impl_t::evict_all_nodes() {
-    while (node_count > 0) {
-        evict_last_node();
-    }
-}
-
-
-
 autoload_t::autoload_t(const wcstring &env_var_name_var, const builtin_script_t * const scripts, size_t script_count) :
                        env_var_name(env_var_name_var),
                        builtin_scripts(scripts),
diff --git a/autoload.h b/autoload.h
index 1f8606fd..2d060488 100644
--- a/autoload.h
+++ b/autoload.h
@@ -11,6 +11,7 @@
 #include <set>
 #include <list>
 #include "common.h"
+#include "lru.h"
 
 /** A struct responsible for recording an attempt to access a file. */
 struct file_access_attempt_t {
@@ -21,83 +22,8 @@ struct file_access_attempt_t {
     int error; /** If we could not access the file, the error code */
 };
 
-/** A predicate to compare dereferenced pointers */
-struct dereference_less_t {
-    template <typename ptr_t>
-    bool operator()(ptr_t p1, ptr_t p2) const { return *p1 < *p2; }
-};
-
 file_access_attempt_t access_file(const wcstring &path, int mode);
 
-class lru_node_t {
-    friend class lru_cache_impl_t;
-    /** Our linked list pointer */
-    lru_node_t *prev, *next;
-    
-public:
-    /** The key used to look up in the cache */
-    const wcstring key;
-    
-    /** Constructor */
-    lru_node_t(const wcstring &keyVar) : prev(NULL), next(NULL), key(keyVar) { }
-    bool operator<(const lru_node_t &other) const { return key < other.key; }
-};
-
-class lru_cache_impl_t {
-private:
-    void promote_node(lru_node_t *);
-    void evict_node(lru_node_t *node);
-    void evict_last_node(void);
-    
-    /** Max node count */
-    const size_t max_node_count;
-    
-    /** Count of nodes */
-    size_t node_count;
-    
-    /** The set of nodes */
-    typedef std::set<lru_node_t *, dereference_less_t> node_set_t;
-    node_set_t node_set;
-    
-    /** Head of the linked list */
-    lru_node_t mouth;
-    
-protected:
-    /** Overridable callback for when a node is evicted */
-    virtual void node_was_evicted(lru_node_t *node);
-    
-public:
-    /** Constructor */
-    lru_cache_impl_t(size_t max_size = 1024 );
-    
-    /** Returns the node for a given key, or NULL */
-    lru_node_t *get_node(const wcstring &key);
-    
-    /** Evicts the node for a given key, returning true if a node was evicted. */
-    bool evict_node(const wcstring &key);
-    
-    /** Adds a node under the given key. Returns true if the node was added, false if the node was not because a node with that key is already in the set. */
-    bool add_node(lru_node_t *node);
-    
-    /** Adds a node under the given key without triggering eviction. Returns true if the node was added, false if the node was not because a node with that key is already in the set. */
-    bool add_node_without_eviction(lru_node_t *node);
-    
-    /** Counts nodes */
-    size_t size(void) { return node_count; }
-    
-    /** Evicts all nodes */
-    void evict_all_nodes(void);
-};
-
-/** Template cover to avoid casting */
-template<class node_type_t>
-class lru_cache_t : public lru_cache_impl_t {
-public:
-    node_type_t *get_node(const wcstring &key) { return static_cast<node_type_t *>(lru_cache_impl_t::get_node(key)); }
-    bool add_node(node_type_t *node) { return lru_cache_impl_t::add_node(node); }
-    lru_cache_t(size_t max_size = 1024 ) : lru_cache_impl_t(max_size) { }
-};
-
 struct autoload_function_t : public lru_node_t
 {   
     autoload_function_t(const wcstring &key) : lru_node_t(key), is_loaded(false), is_placeholder(false) { bzero(&access, sizeof access); }
diff --git a/history.cpp b/history.cpp
index 04cafdb4..50fb18ba 100644
--- a/history.cpp
+++ b/history.cpp
@@ -28,7 +28,55 @@
 #include "intern.h"
 #include "path.h"
 #include "signal.h"
+#include "autoload.h"
 #include <map>
+#include <algorithm>
+
+/** When we rewrite the history, the number of items we keep */
+#define HISTORY_SAVE_MAX (1024 * 256)
+
+/** Interval in seconds between automatic history save */
+#define SAVE_INTERVAL (5*60)
+
+/** Number of new history entries to add before automatic history save */
+#define SAVE_COUNT 5
+
+/* Our LRU cache is used for restricting the amount of history we have, and limiting how long we order it. */
+class history_lru_node_t : public lru_node_t {
+    public:
+    time_t timestamp;
+    history_lru_node_t(const history_item_t &item) : lru_node_t(item.str()), timestamp(item.timestamp())
+    {
+    }
+};
+
+class history_lru_cache_t : public lru_cache_t<history_lru_node_t> {
+    protected:
+    
+    /* Override to delete evicted nodes */
+    virtual void node_was_evicted(history_lru_node_t *node) {
+        delete node;
+    }
+
+    public:
+    history_lru_cache_t(size_t max) : lru_cache_t<history_lru_node_t>(max) { }
+    
+    /* Function to add a history item */
+    void add_item(const history_item_t &item) {
+        /* Skip empty items */
+        if (item.empty())
+            return;
+            
+        /* See if it's in the cache. If it is, update the timestamp. If not, we create a new node and add it. Note that calling get_node promotes the node to the front. */
+        history_lru_node_t *node = this->get_node(item.str());
+        if (node != NULL) {
+            node->timestamp = std::max(node->timestamp, item.timestamp());
+        } else {
+            node = new history_lru_node_t(item);
+            this->add_node(node);
+        }
+    }
+};
 
 static pthread_mutex_t hist_lock = PTHREAD_MUTEX_INITIALIZER;
 
@@ -36,11 +84,12 @@ static std::map<wcstring, history_t *> histories;
 
 static wcstring history_filename(const wcstring &name, const wcstring &suffix);
 
-static hash_table_t *mode_table=0;
-
 /* Unescapes newlines in-place */
 static void unescape_newlines(wcstring &str);
 
+/* Escapes newlines in-place */
+static void escape_newlines(wcstring &str);
+
 /* Custom deleter for our shared_ptr */
 class history_item_data_deleter_t {
     private:
@@ -53,15 +102,19 @@ class history_item_data_deleter_t {
     }
 };
 
-history_item_t::history_item_t(const wcstring &str) : contents(str), timestamp(time(NULL))
+history_item_t::history_item_t(const wcstring &str) : contents(str), creation_timestamp(time(NULL))
 {
 }
 
-history_item_t::history_item_t(const wcstring &str, time_t when) : contents(str), timestamp(when)
+history_item_t::history_item_t(const wcstring &str, time_t when) : contents(str), creation_timestamp(when)
 {
 }
 
-
+bool history_item_t::write_to_file(FILE *f) const {
+    wcstring escaped = contents;
+    escape_newlines(escaped);
+	return fwprintf( f, L"# %d\n%ls\n", creation_timestamp, escaped.c_str());
+}
 
 history_t & history_t::history_with_name(const wcstring &name) {
     /* Note that histories are currently never deleted, so we can return a reference to them without using something like shared_ptr */
@@ -91,6 +144,10 @@ void history_t::add(const wcstring &str)
 {
     scoped_lock locker(lock);
     new_items.push_back(history_item_t(str.c_str(), true));
+    
+    /* This might be a good candidate for moving to a background thread */
+    if((time(0) > save_timestamp + SAVE_INTERVAL) || (new_items.size() >= SAVE_COUNT))
+		this->save_internal();
 }
 
 history_item_t history_t::item_at_index(size_t idx) {
@@ -350,15 +407,6 @@ history_item_t history_search_t::current_item() const {
     return history->item_at_index(idx);
 }
 
-/**
-   Interval in seconds between automatic history save
-*/
-#define SAVE_INTERVAL (5*60)
-
-/**
-   Number of new history entries to add before automatic history save
-*/
-#define SAVE_COUNT 5
 
 /**
    A struct representiong a history list
@@ -529,10 +577,8 @@ static wchar_t *history_escape_newlines( wchar_t *in )
 	return (wchar_t *)out->buff;
 }
 
-static void unescape_newlines(wcstring &str)
+static void replace_all(wcstring &str, const wchar_t *needle, const wchar_t *replacement)
 {
-    /* Replace instances of backslash + newline with just the newline */
-    const wchar_t *needle = L"\\\n", *replacement = L"\n";
     size_t needle_len = wcslen(needle);
     size_t offset = 0;
     while((offset = str.find(needle, offset)) != wcstring::npos)
@@ -542,6 +588,22 @@ static void unescape_newlines(wcstring &str)
     }
 }
 
+static void unescape_newlines(wcstring &str)
+{
+    /* Replace instances of backslash + newline with just the newline */
+    replace_all(str, L"\\\n", L"\n");
+}
+
+static void escape_newlines(wcstring &str)
+{
+    /* Replace instances of newline with backslash + newline with newline */
+    replace_all(str, L"\\\n", L"\n");
+    
+    /* If the string ends with a backslash, we'll combine it with the next line. Hack around that by appending a newline. */
+    if (! str.empty() && str.at(str.size() - 1) == L'\\')
+        str.push_back('\n');
+}
+
 /**
    Remove backslashes from all newlines. This makes a string from the
    history file better formated for on screen display. The memory for
@@ -949,83 +1011,55 @@ static void history_load( history_mode_t *m )
 	signal_unblock();
 }
 
-#if 0
-/**
-   Save the specified mode to file
-*/
-void history_t::save( void *n, history_mode_t *m )
+/** Save the specified mode to file */
+void history_t::save_internal()
 {
-    scoped_lock locker(lock);
+    /* This must be called while locked */
     
     /* Nothing to do if there's no new items */
     if (new_items.empty())
         return;
     
-	FILE *out;
-	int i;
-	int has_new=0;
-	wchar_t *tmp_name;
-
-	int ok = 1;
+	bool ok = true;
 	
 	signal_block();
     
     wcstring tmp_name = history_filename(name, L".tmp");
-	
 	if( ! tmp_name.empty() )
 	{
-		if( (out=wfopen( tmp_name, "w" ) ) )
+        FILE *out;
+		if( (out=wfopen( tmp_name.c_str(), "w" ) ) )
 		{
-			hash_table_t mine;
-			
-			hash_init( &mine, &hash_item_func, &hash_item_cmp );
-			
-			for( i=0; i<al_get_count(&m->item); i++ )
-			{
-				void *ptr = al_get( &m->item, i );
-				int is_new = item_is_new( m, ptr );
-				if( is_new )
-				{
-					hash_put( &mine, item_get( m, ptr ), L"" );
-				}
-			}
-			
-			/*
-			  Re-save the old history
-			*/
-			for( i=0; ok && (i<al_get_count(&on_disk->item)); i++ )
-			{
-				void *ptr = al_get( &on_disk->item, i );
-				item_t *i = item_get( on_disk, ptr );
-				if( !hash_get( &mine, i ) )
-				{
-					if( item_write( out, on_disk, ptr ) == -1 )
-					{
-						ok = 0;
-						break;
-					}
-				}
-				
-			}
-			
-			hash_destroy( &mine );
-		
-			/*
-			  Add our own items last
-			*/		
-			for( i=0; ok && (i<al_get_count(&m->item)); i++ )
-			{
-				void *ptr = al_get( &m->item, i );
-				int is_new = item_is_new( m, ptr );
-				if( is_new )
-				{
-					if( item_write( out, m, ptr ) == -1 )
-					{						
-						ok = 0;
-					}
-				}
-			}
-			
+                
+            /* Load old */
+            load_old_if_needed();
+            
+            /* Make an LRU cache to save only the last N elements */
+            history_lru_cache_t lru(HISTORY_SAVE_MAX);
+            
+            /* Insert old items in, from old to new */
+            for (std::vector<size_t>::iterator iter = old_item_offsets.begin(); iter != old_item_offsets.end(); iter++) {
+                size_t offset = *iter;
+                history_item_t item = history_t::decode_item(mmap_start + offset, mmap_length - offset);
+                lru.add_item(item);
+            }
+            
+            /* Insert new items */
+            for (std::vector<history_item_t>::iterator iter = new_items.begin(); iter != new_items.end(); iter++) {
+                lru.add_item(*iter);
+            }
+            
+            /* Write them out */
+            for (history_lru_cache_t::iterator iter = lru.begin(); iter != lru.end(); iter++) {
+#if 0
+                if (! (*iter)->write_to_file(out)) {
+                    ok = false;
+                    break;
+                }
+#endif
+            }
+
+
 			if( fclose( out ) || !ok )
 			{
 				/*
@@ -1036,43 +1070,33 @@ void history_t::save( void *n, history_mode_t *m )
 			}
 			else
 			{
-				wrename( tmp_name, history_filename( on_disk, m->name, 0 ) );
+                wcstring new_name = history_filename(name, wcstring());
+				wrename(tmp_name.c_str(), new_name.c_str());
 			}
 		}
-		free( tmp_name );
 	}	
-	
-	halloc_free( on_disk);
 
 	if( ok )
 	{
-
-		/*
-		  Reset the history. The item_t entries created in this session
-		  are not lost or dropped, they are stored in the session_item
-		  hash table. On reload, they will be automatically inserted at
-		  the end of the history list.
-		*/
-			
-		if( m->mmap_start && (m->mmap_start != MAP_FAILED ) )
-		{
-			munmap( m->mmap_start, m->mmap_length );
-		}
-		
-		al_truncate( &m->item, 0 );
-		al_truncate( &m->used, 0 );
-		m->pos = 0;
-		m->has_loaded = 0;
-		m->mmap_start=0;
-		m->mmap_length=0;
-	
-		m->save_timestamp=time(0);
-		m->new_count = 0;
+		/* Our history has been written to the file, so clear our state so we can re-reference the file. */
+		if (mmap_start != NULL && mmap_start != MAP_FAILED) {
+			munmap((void *)mmap_start, mmap_length);
+        }
+        mmap_start = 0;
+        mmap_length = 0;
+        loaded_old = false;
+        new_items.clear();
+        old_item_offsets.clear();
+		save_timestamp=time(0);
 	}
 	
 	signal_unblock();
 }
-#endif
+
+void history_t::save(void) {
+    scoped_lock locker(lock);
+    this->save_internal();
+}
 
 /**
    Save the specified mode to file
@@ -1425,14 +1449,10 @@ void history_init()
 
 void history_destroy()
 {
-	if( mode_table )
-	{
-		hash_foreach( mode_table, (void (*)(void *, void *))&history_save_mode );
-		hash_foreach( mode_table, (void (*)(void *, void *))&history_destroy_mode_wrapper );
-		hash_destroy( mode_table );
-		free( mode_table );
-		mode_table=0;
-	}
+    /* Save all histories */
+    for (std::map<wcstring, history_t *>::iterator iter = histories.begin(); iter != histories.end(); iter++) {
+        iter->second->save();
+    }
 }
 
 
diff --git a/history.h b/history.h
index 48cd951e..466c2b78 100644
--- a/history.h
+++ b/history.h
@@ -23,12 +23,15 @@ class history_item_t {
 	wcstring contents;
     	
 	/** Original creation time for the entry */
-	time_t timestamp;
+	time_t creation_timestamp;
     
     public:
     const wcstring &str() const { return contents; }
     bool empty() const { return contents.empty(); }
     bool matches_search(const wcstring &val) const { return contents.find(val) != wcstring::npos; }
+    time_t timestamp() const { return creation_timestamp; }
+    
+    bool write_to_file(FILE *f) const;
 };
 
 class history_t {
@@ -76,6 +79,9 @@ private:
     /** Loads old if necessary */
     void load_old_if_needed(void);
     
+    /** Saves history */
+    void save_internal();
+    
 public:
     /** Returns history with the given name, creating it if necessary */
     static history_t & history_with_name(const wcstring &name);
@@ -123,16 +129,14 @@ public:
         history(&hist),
         term(str),
         idx()
-    {
-    }
+    {}
     
     /* Default constructor */
     history_search_t() :
         history(),
         term(),
         idx()
-    {
-    }
+    {}
     
 };
 
diff --git a/lru.h b/lru.h
new file mode 100644
index 00000000..c985aca8
--- /dev/null
+++ b/lru.h
@@ -0,0 +1,205 @@
+/** \file lru.h
+
+    Least-recently-used cache implementation
+*/
+
+#ifndef FISH_LRU_H
+#define FISH_LRU_H
+
+#include <wchar.h>
+#include <map>
+#include <set>
+#include <list>
+#include "common.h"
+
+/** A predicate to compare dereferenced pointers */
+struct dereference_less_t {
+    template <typename ptr_t>
+    bool operator()(ptr_t p1, ptr_t p2) const { return *p1 < *p2; }
+};
+
+class lru_node_t {
+    template<class T> friend class lru_cache_t;
+    
+    /** Our linked list pointer */
+    lru_node_t *prev, *next;
+    
+public:
+    /** The key used to look up in the cache */
+    const wcstring key;
+    
+    /** Constructor */
+    lru_node_t(const wcstring &pkey) : prev(NULL), next(NULL), key(pkey) { }
+    
+    /** operator< for std::set */
+    bool operator<(const lru_node_t &other) const { return key < other.key; }
+};
+
+template<class node_type_t>
+class lru_cache_t {
+    private:
+
+    /** Max node count */
+    const size_t max_node_count;
+    
+    /** Count of nodes */
+    size_t node_count;
+    
+    /** The set of nodes */
+    typedef std::set<lru_node_t *, dereference_less_t> node_set_t;
+    node_set_t node_set;
+        
+    void promote_node(node_type_t *node) {
+        /* We should never promote the mouth */
+        assert(node != &mouth);
+        
+        /* First unhook us */
+        node->prev->next = node->next;
+        node->next->prev = node->prev;
+        
+        /* Put us after the mouth */
+        node->next = mouth.next;
+        node->next->prev = node;
+        node->prev = &mouth;
+        mouth.next = node;
+    }
+    
+    void evict_node(node_type_t *condemned_node) {
+        /* We should never evict the mouth */
+        assert(condemned_node != NULL && condemned_node != &mouth);
+
+        /* Remove it from the linked list */
+        condemned_node->prev->next = condemned_node->next;
+        condemned_node->next->prev = condemned_node->prev;
+
+        /* Remove us from the set */
+        node_set.erase(condemned_node);
+        node_count--;
+
+        /* Tell ourselves */
+        this->node_was_evicted(condemned_node);
+    }
+    
+    void evict_last_node(void) {
+        /* Simple */
+        evict_node((node_type_t *)mouth.prev);
+    }
+    
+    protected:
+    
+    /** Head of the linked list */
+    lru_node_t mouth;
+
+    /** Overridable callback for when a node is evicted */
+    virtual void node_was_evicted(node_type_t *node) { }
+    
+    public:
+    
+    /** Constructor */
+    lru_cache_t(size_t max_size = 1024 ) : max_node_count(max_size), node_count(0), mouth(wcstring()) {
+        /* Hook up the mouth to itself: a one node circularly linked list! */
+        mouth.prev = mouth.next = &mouth;
+    }
+    
+    /** Returns the node for a given key, or NULL */
+    node_type_t *get_node(const wcstring &key) {
+        node_type_t *result = NULL;
+        
+        /* Construct a fake node as our key */
+        lru_node_t node_key(key);
+        
+        /* Look for it in the set */
+        node_set_t::iterator iter = node_set.find(&node_key);
+        
+        /* If we found a node, promote and return it */
+        if (iter != node_set.end()) {
+            result = static_cast<node_type_t*>(*iter);
+            promote_node(result);
+        }
+        return result;
+    }
+    
+    /** Evicts the node for a given key, returning true if a node was evicted. */
+    bool evict_node(const wcstring &key) {
+        /* Construct a fake node as our key */
+        lru_node_t node_key(key);
+        
+        /* Look for it in the set */
+        node_set_t::iterator iter = node_set.find(&node_key);
+        if (iter == node_set.end())
+            return false;
+        
+        /* Evict the given node */
+        evict_node(static_cast<node_type_t*>(*iter));
+        return true;
+    }
+    
+    /** Adds a node under the given key. Returns true if the node was added, false if the node was not because a node with that key is already in the set. */
+    bool add_node(node_type_t *node) {
+        /* Add our node without eviction */
+        if (! this->add_node_without_eviction(node))
+            return false;
+        
+        /* Evict */
+        while (node_count > max_node_count)
+            evict_last_node();
+        
+        /* Success */
+        return true;
+    }
+    
+    /** Adds a node under the given key without triggering eviction. Returns true if the node was added, false if the node was not because a node with that key is already in the set. */
+    bool add_node_without_eviction(node_type_t *node) {
+        assert(node != NULL && node != &mouth);
+        
+        /* Try inserting; return false if it was already in the set */
+        if (! node_set.insert(node).second)
+            return false;
+        
+        /* Add the node after the mouth */
+        node->next = mouth.next;
+        node->next->prev = node;
+        node->prev = &mouth;
+        mouth.next = node;
+        
+        /* Update the count */
+        node_count++;
+        
+        /* Evict */
+        while (node_count > max_node_count)
+            evict_last_node();
+        
+        /* Success */
+        return true;
+    }
+    
+    /** Counts nodes */
+    size_t size(void) {
+        return node_count;
+    }
+    
+    /** Evicts all nodes */
+    void evict_all_nodes(void) {
+        while (node_count > 0) {
+            evict_last_node();
+        }
+    }
+    
+    /** Iterator for walking nodes, from least recently used to most */
+    class iterator {
+        lru_node_t *node;
+        public:
+        iterator(lru_node_t *val) : node(val) { }
+        void operator++() { node = node->prev; }
+        void operator++(int x) { node = node->prev; }
+        bool operator==(const iterator &other) { return node == other.node; }
+        bool operator!=(const iterator &other) { return !(*this == other); }
+        node_type_t *operator*() { return static_cast<node_type_t *>(node); }
+    };
+    
+    iterator begin() { return iterator(mouth.prev); }
+    iterator end() { return iterator(&mouth); }
+};
+
+
+#endif