[geary/wip/135-contact-popovers: 55/62] Add new generic LRU cache to the client

[Michael Gratton <mjog src gnome org>]

commit a1157917a9edf71e77b08b2059ea030f4e92a49d
Author: Michael Gratton <mike vee net>
Date:   Sun Mar 17 13:48:15 2019 +1100

    Add new generic LRU cache to the client

 po/POTFILES.in                        |   1 +
 src/client/meson.build                |   1 +
 src/client/util/util-cache.vala       | 122 ++++++++++++++++++++++++++++++++++
 test/client/util/util-cache-test.vala |  71 ++++++++++++++++++++
 test/meson.build                      |   1 +
 test/test-client.vala                 |   1 +
 6 files changed, 197 insertions(+)
---
diff --git a/po/POTFILES.in b/po/POTFILES.in
index 74689c48..0e91036d 100644
--- a/po/POTFILES.in
+++ b/po/POTFILES.in
@@ -91,6 +91,7 @@ src/client/sidebar/sidebar-count-cell-renderer.vala
 src/client/sidebar/sidebar-entry.vala
 src/client/sidebar/sidebar-tree.vala
 src/client/util/util-avatar.vala
+src/client/util/util-cache.vala
 src/client/util/util-date.vala
 src/client/util/util-email.vala
 src/client/util/util-files.vala
diff --git a/src/client/meson.build b/src/client/meson.build
index 1f3f15a7..fcfebf8b 100644
--- a/src/client/meson.build
+++ b/src/client/meson.build
@@ -96,6 +96,7 @@ geary_client_vala_sources = files(
   'sidebar/sidebar-tree.vala',
 
   'util/util-avatar.vala',
+  'util/util-cache.vala',
   'util/util-date.vala',
   'util/util-email.vala',
   'util/util-files.vala',
diff --git a/src/client/util/util-cache.vala b/src/client/util/util-cache.vala
new file mode 100644
index 00000000..3161fd39
--- /dev/null
+++ b/src/client/util/util-cache.vala
@@ -0,0 +1,122 @@
+/*
+ * Copyright 2019 Michael Gratton <mike vee net>
+ *
+ * This software is licensed under the GNU Lesser General Public License
+ * (version 2.1 or later). See the COPYING file in this distribution.
+ */
+
+/** A simple least-recently-used cache. */
+public class Util.Cache.Lru<T> : Geary.BaseObject {
+
+
+    private class CacheEntry<T> {
+
+
+        public static int lru_compare(CacheEntry<T> a, CacheEntry<T> b) {
+            return (a.key == b.key)
+                ? 0 : (int) (a.last_used - b.last_used);
+        }
+
+
+        public string key;
+        public T value;
+        public int64 last_used;
+
+
+        public CacheEntry(string key, T value, int64 last_used) {
+            this.key = key;
+            this.value = value;
+            this.last_used = last_used;
+        }
+
+    }
+
+
+    /** Specifies the maximum number of cache entries to be stored. */
+    public uint max_size { get; set; }
+
+    /** Determines if the cache has any entries or not. */
+    public bool is_empty {
+        get { return this.cache.is_empty; }
+    }
+
+    /** Determines the current number of cache entries. */
+    public uint size {
+        get { return this.cache.size; }
+    }
+
+    private Gee.Map<string,CacheEntry<T>> cache =
+        new Gee.HashMap<string,CacheEntry<T>>();
+    private Gee.SortedSet<CacheEntry<T>> ordering =
+        new Gee.TreeSet<CacheEntry<T>>(CacheEntry.lru_compare);
+
+
+    /**
+     * Creates a new least-recently-used cache with the given size.
+     */
+    public Lru(uint max_size) {
+        this.max_size = max_size;
+    }
+
+    /**
+     * Sets an entry in the cache, replacing any existing entry.
+     *
+     * The entry is added to the back of the removal queue. If adding
+     * the entry causes the size of the cache to exceed the maximum,
+     * the entry at the front of the queue will be evicted.
+     */
+    public void set_entry(string key, T value) {
+        int64 now = GLib.get_monotonic_time();
+        CacheEntry<T> entry = new CacheEntry<T>(key, value, now);
+        this.cache.set(key, entry);
+        this.ordering.add(entry);
+
+        // Prune if needed
+        if (this.cache.size > this.max_size) {
+            CacheEntry oldest = this.ordering.first();
+            this.cache.unset(oldest.key);
+            this.ordering.remove(oldest);
+        }
+    }
+
+    /**
+     * Returns the entry from the cache, if found.
+     *
+     * If the entry was found, it is move to the back of the removal
+     * queue.
+     */
+    public T get_entry(string key) {
+        int64 now = GLib.get_monotonic_time();
+        CacheEntry<T>? entry = this.cache.get(key);
+        T value = null;
+        if (entry != null) {
+            value = entry.value;
+            // Need to remove the entry from the ordering before
+            // updating the last used time since doing so changes the
+            // ordering
+            this.ordering.remove(entry);
+            entry.last_used = now;
+            this.ordering.add(entry);
+        }
+        return value;
+    }
+
+    /** Removes an entry from the cache and returns it, if found. */
+    public T remove_entry(string key) {
+        CacheEntry<T>? entry = null;
+        T value = null;
+        this.cache.unset(key, out entry);
+        if (entry != null) {
+            this.ordering.remove(entry);
+            value = entry.value;
+        }
+        return value;
+    }
+
+    /** Evicts all entries in the cache. */
+    public void clear() {
+        this.cache.clear();
+        this.ordering.clear();
+    }
+
+}
diff --git a/test/client/util/util-cache-test.vala b/test/client/util/util-cache-test.vala
new file mode 100644
index 00000000..1a40b7a9
--- /dev/null
+++ b/test/client/util/util-cache-test.vala
@@ -0,0 +1,71 @@
+/*
+ * Copyright 2019 Michael Gratton <mike vee net>
+ *
+ * This software is licensed under the GNU Lesser General Public License
+ * (version 2.1 or later). See the COPYING file in this distribution.
+ */
+
+public class Util.Cache.Test : TestCase {
+
+    public Test() {
+        base("UtilCacheTest");
+        add_test("lru_insertion", lru_insertion);
+        add_test("lru_eviction", lru_eviction);
+    }
+
+    public void lru_insertion() throws GLib.Error {
+        const string A = "a";
+        const string B = "b";
+        const string C = "c";
+        const string D = "d";
+
+        Lru<string> test_article = new Lru<string>(2);
+
+        assert_true(test_article.is_empty);
+        assert_uint(0, test_article.size);
+
+        assert_true(test_article.get_entry(A) == null);
+        test_article.set_entry(A, A);
+        assert_string(A, test_article.get_entry(A));
+
+        assert_false(test_article.is_empty);
+        assert_uint(1, test_article.size);
+
+        test_article.set_entry(B, B);
+        assert_string(B, test_article.get_entry(B));
+        assert_uint(2, test_article.size);
+
+        test_article.set_entry(C, C);
+        assert_string(C, test_article.get_entry(C));
+        assert_uint(2, test_article.size);
+        assert_true(test_article.get_entry(A) == null);
+
+        test_article.set_entry(D, D);
+        assert_string(D, test_article.get_entry(D));
+        assert_uint(2, test_article.size);
+        assert_true(test_article.get_entry(B) == null);
+
+        test_article.clear();
+        assert_true(test_article.is_empty);
+        assert_uint(0, test_article.size);
+    }
+
+    public void lru_eviction() throws GLib.Error {
+        const string A = "a";
+        const string B = "b";
+        const string C = "c";
+
+        Lru<string> test_article = new Lru<string>(2);
+
+        test_article.set_entry(A, A);
+        test_article.set_entry(B, B);
+
+        test_article.get_entry(A);
+        test_article.set_entry(C, C);
+
+        assert_string(C, test_article.get_entry(C));
+        assert_string(A, test_article.get_entry(A));
+        assert_true(test_article.get_entry(B) == null);
+    }
+
+}
diff --git a/test/meson.build b/test/meson.build
index ab3ea78c..27d4a3fa 100644
--- a/test/meson.build
+++ b/test/meson.build
@@ -77,6 +77,7 @@ geary_test_client_sources = [
   'client/components/client-web-view-test-case.vala',
   'client/composer/composer-web-view-test.vala',
   'client/util/util-avatar-test.vala',
+  'client/util/util-cache-test.vala',
   'client/util/util-email-test.vala',
 
   'js/client-page-state-test.vala',
diff --git a/test/test-client.vala b/test/test-client.vala
index 1852ba6e..fe408374 100644
--- a/test/test-client.vala
+++ b/test/test-client.vala
@@ -44,6 +44,7 @@ int main(string[] args) {
     client.add_suite(new ComposerWebViewTest().get_suite());
     client.add_suite(new ConfigurationTest().get_suite());
     client.add_suite(new Util.Avatar.Test().get_suite());
+    client.add_suite(new Util.Cache.Test().get_suite());
     client.add_suite(new Util.Email.Test().get_suite());
 
     TestSuite js = new TestSuite("js");