From b4f53143b0e05fd3061cdf2e65e17a6a2904090b Mon Sep 17 00:00:00 2001 From: ridiculousfish Date: Fri, 24 Jul 2015 00:50:58 -0700 Subject: Migrate source files into src/ directory This change moves source files into a src/ directory, and puts object files into an obj/ directory. The Makefile and xcode project are updated accordingly. Fixes #1866 --- src/lru.h | 256 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 256 insertions(+) create mode 100644 src/lru.h (limited to 'src/lru.h') diff --git a/src/lru.h b/src/lru.h new file mode 100644 index 00000000..5899087c --- /dev/null +++ b/src/lru.h @@ -0,0 +1,256 @@ +/** \file lru.h + + Least-recently-used cache implementation +*/ + +#ifndef FISH_LRU_H +#define FISH_LRU_H + +#include +#include +#include +#include +#include "common.h" + +/** A predicate to compare dereferenced pointers */ +struct dereference_less_t +{ + template + bool operator()(ptr_t p1, ptr_t p2) const + { + return *p1 < *p2; + } +}; + +class lru_node_t +{ + template 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) { } + + /** Virtual destructor that does nothing for classes that inherit lru_node_t */ + virtual ~lru_node_t() {} + + /** operator< for std::set */ + bool operator<(const lru_node_t &other) const + { + return key < other.key; + } +}; + +template +class lru_cache_t +{ +private: + + /** Max node count. This may be (transiently) exceeded by add_node_without_eviction, which is used from background threads. */ + const size_t max_node_count; + + /** Count of nodes */ + size_t node_count; + + /** The set of nodes */ + typedef std::set 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); + } + + static lru_node_t *get_previous(lru_node_t *node) + { + return node->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; + } + + /** Note that we do not evict nodes in our destructor (even though they typically need to be deleted by their creator). */ + virtual ~lru_cache_t() { } + + + /** 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(*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(*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. This may push us over the maximum node count. */ + node_count++; + + /* 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 = lru_cache_t::get_previous(node); + } + void operator++(int x) + { + node = lru_cache_t::get_previous(node); + } + 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); + } + }; + + iterator begin() + { + return iterator(mouth.prev); + } + iterator end() + { + return iterator(&mouth); + } +}; + + +#endif -- cgit v1.2.3