This is an automated email from the ASF dual-hosted git repository. bneradt pushed a commit to branch lru-cache in repository https://gitbox.apache.org/repos/asf/trafficserver-libswoc.git
commit c22b27453c856c96ce8e11e63ab3c4a586e816d7 Author: Alan M. Carroll <[email protected]> AuthorDate: Fri Oct 1 10:14:02 2021 -0500 LRU Cache - checkpoint. --- code/include/swoc/MemSpan.h | 14 ++--- code/include/swoc/swoc_ip.h | 31 +++++++++- example/CMakeLists.txt | 6 ++ example/ex_lru_cache.cc | 137 ++++++++++++++++++++++++++++++++++++++++++++ unit_tests/test_MemArena.cc | 6 +- 5 files changed, 183 insertions(+), 11 deletions(-) diff --git a/code/include/swoc/MemSpan.h b/code/include/swoc/MemSpan.h index 326a59d..03f26de 100644 --- a/code/include/swoc/MemSpan.h +++ b/code/include/swoc/MemSpan.h @@ -49,21 +49,21 @@ public: constexpr MemSpan() = default; /// Copy constructor. - constexpr MemSpan(self_type const &that) = default; + constexpr MemSpan(self_type const &) = default; - /** Construct from a first element @a start and a @a count of elements. + /** Construct from a first element @a ptr and a @a count of elements. * - * @param start First element. + * @param ptr First element. * @param count Total number of elements. */ - constexpr MemSpan(value_type *start, size_t count); + constexpr MemSpan(value_type *ptr, size_t count); /** Construct from a half open range [start, last). * * @param start Start of range. * @param last Past end of range. */ - constexpr MemSpan(value_type *start, value_type *last); + constexpr MemSpan(value_type *first, value_type *last); /** Construct to cover an array. * @@ -100,7 +100,7 @@ public: bool operator!=(self_type const &that) const; /// Assignment - the span is copied, not the content. - self_type &operator=(self_type const &that) = default; + self_type &operator=(self_type const &) = default; /// Access element at index @a idx. T &operator[](size_t idx) const; @@ -292,7 +292,7 @@ public: * @param start Start of the span. * @param n # of bytes in the span. */ - constexpr MemSpan(value_type *start, size_t n); + constexpr MemSpan(value_type *ptr, size_t n); /** Construct from a half open range of [start, last). * diff --git a/code/include/swoc/swoc_ip.h b/code/include/swoc/swoc_ip.h index df40557..ee87f99 100644 --- a/code/include/swoc/swoc_ip.h +++ b/code/include/swoc/swoc_ip.h @@ -459,6 +459,10 @@ public: /// Return the address in network order. in6_addr network_order() const; + /// Return the address as words. + word_type * words() { return _addr._store.data(); } + word_type const * words() const { return _addr._store.data(); } + /** Parse a string for an IP address. The address resuling from the parse is copied to this object if the conversion is successful, @@ -546,7 +550,7 @@ class IPAddr { using self_type = IPAddr; ///< Self reference type. public: IPAddr() = default; ///< Default constructor - invalid result. - IPAddr(self_type const& that) = default; ///< Copy constructor. + IPAddr(self_type const&) = default; ///< Copy constructor. /// Construct using IPv4 @a addr. explicit IPAddr(in_addr_t addr); @@ -2946,6 +2950,31 @@ public: using type = swoc::IPMask; }; +template <> struct hash<swoc::IP4Addr> { + uint32_t operator() (swoc::IP4Addr const& addr) const { return addr.network_order(); } +}; + +template <> struct hash<swoc::IP6Addr> { + uint32_t operator() (swoc::IP6Addr const& addr) const { + static_assert(sizeof(swoc::IP6Addr::word_type) == 2 * sizeof(uint32_t)); + // XOR the 64 chunks then XOR that down to 32 bits. + auto words = addr.words(); + union { + swoc::IP6Addr::word_type w; + uint32_t n[2]; + } x{words[0] ^ words[1]}; + return x.n[0] ^ x.n[1]; + } +}; + +template <> struct hash<swoc::IPAddr> { + uint32_t operator() (swoc::IPAddr const& addr) const { + return addr.is_ip4() ? hash<swoc::IP4Addr>()(addr.ip4()) + : addr.is_ip6() ? hash<swoc::IP6Addr>()(addr.ip6()) + : 0; + } +}; + } // namespace std /// @endcond diff --git a/example/CMakeLists.txt b/example/CMakeLists.txt index 8d072e0..e1e0563 100644 --- a/example/CMakeLists.txt +++ b/example/CMakeLists.txt @@ -21,3 +21,9 @@ target_link_libraries(ex_flat_space PUBLIC libswoc) if (CMAKE_COMPILER_IS_GNUCXX) target_compile_options(ex_flat_space PRIVATE -Wall -Wextra -Werror) endif() + +add_executable(ex_lru_cache ex_lru_cache.cc) +target_link_libraries(ex_lru_cache PUBLIC libswoc) +if (CMAKE_COMPILER_IS_GNUCXX) + target_compile_options(ex_lru_cache PRIVATE -Wall -Wextra -Werror) +endif() diff --git a/example/ex_lru_cache.cc b/example/ex_lru_cache.cc new file mode 100644 index 0000000..777a150 --- /dev/null +++ b/example/ex_lru_cache.cc @@ -0,0 +1,137 @@ +// SPDX-License-Identifier: Apache-2.0 +// Copyright 2020 Verizon Media + +/** @file + + Example of building a thread safe LRU cache using intrusive containers. +*/ + +#include <unistd.h> +#include <chrono> +#include <utility> + +#include "swoc/TextView.h" +#include "swoc/swoc_ip.h" +#include "swoc/bwf_ip.h" +#include "swoc/bwf_ex.h" +#include "swoc/bwf_std.h" +#include "swoc/swoc_file.h" +#include "swoc/Errata.h" +#include "swoc/IntrusiveDList.h" +#include "swoc/IntrusiveHashMap.h" +#include "swoc/MemArena.h" + +using namespace std::literals; +using namespace swoc::literals; + +using swoc::TextView; +using swoc::MemSpan; +using swoc::Errata; +using swoc::IPAddr; + +using time_point = std::chrono::time_point<std::chrono::system_clock>; + +template < typename K, typename V > class LRU { + using self_type = LRU; +public: + LRU() = default; + + self_type & insert(K const& key, V && value); + self_type & erase(K const& key); + V retrieve(K const& key) const; + +protected: + struct Item { + using self_type = Item; + struct Links { + self_type * _next = nullptr; + self_type * _prev = nullptr; + }; + + K _key; + V _value; + + Links _list; + Links _map; + }; + + struct Linkage { + static Item * next_ptr(Item * item) { return item->_list._next; } + static Item * prev_ptr(Item * item) { return item->_list._prev; } + }; + using List = swoc::IntrusiveDList<Linkage>; + + struct Hashing { + static Item * next_ptr(Item * item) { return item->_map._next; } + static Item * prev_ptr(Item * item) { return item->_map._prev; } + static inline const std::hash<K> Hasher; + static K const& key_of(Item * item) { return item->_key; } + static decltype(Hasher(std::declval<K>())) hash_of(K const& key) { return Hasher(key); } + static bool equal(K const& lhs, K const& rhs) { return lhs == rhs; } + }; + using Table = swoc::IntrusiveHashMap<Hashing>; + + std::shared_mutex _mutex; ///< Read/write lock. + size_t _max = 1024; ///< Maximum number of elements. + List _list; ///< LRU list. + Table _table; ///< Keyed set of values. + List _free; ///< Free list. + swoc::MemArena _arena; +}; + +template <typename K, typename V> auto LRU<K, V>::insert(K const &key, V &&value) -> self_type & { + Item *target = nullptr; + { + std::unique_lock lock(_mutex); + auto spot = _table.find(key); + if (spot != _table.end()) { + spot->_value = std::move(value); + } else { + auto *item = _arena.make<Item>(key, std::move(value)); + _table.insert(item); + _list.append(item); + if (_list.size() > _max) { + target = _list.take_head(); + } + } + } + + if (target) { + target->_key.~K(); + target->_value.~V(); + std::unique_lock lock(_mutex); + _free.append(target); + } + return *this; +} + +template <typename K, typename V> auto LRU<K, V>::erase(K const &key) -> self_type & { + std::unique_lock lock(_mutex); + auto spot = _table.find(key); + if (spot != _table.end()) { + Item * item = spot; + _table.erase(item); + _list.erase(item); + _free.append(item); + } + return *this; +} + +template <typename K, typename V> auto LRU<K, V>::retrieve(K const &key) const -> V { + std::shared_lock lock(_mutex); + auto spot = _table.find(key); + return spot == _table.end() ? V{} : *spot; +} + +// -------------------------------------------------- + +int main(int, char *[]) { + struct Data { + time_point _expire; + int _code = 0; + }; + + LRU<IPAddr, Data> lru; + + return 0; +} diff --git a/unit_tests/test_MemArena.cc b/unit_tests/test_MemArena.cc index a20e9e3..021e25d 100644 --- a/unit_tests/test_MemArena.cc +++ b/unit_tests/test_MemArena.cc @@ -152,13 +152,13 @@ TEST_CASE("MemArena helper", "[libswoc][MemArena]") { struct Thing { int ten{10}; - std::string name{"name"}; + std::string_view name{"name"}; Thing() {} Thing(int x) : ten(x) {} - Thing(std::string const &s) : name(s) {} + Thing(std::string_view s) : name(s) {} Thing(int x, std::string_view s) : ten(x), name(s) {} - Thing(std::string const &s, int x) : ten(x), name(s) {} + Thing(std::string_view s, int x) : ten(x), name(s) {} }; swoc::MemArena arena{256};
