Exporting C++ headers from system/core

Moved headers from include/libutils and include/libsysutils to
libutils/include and libsysutils/include respectively, so they can be
exported via these libs. They needed to be moved since Soong does
not allow export from external folder.

Added symlink from old locations. They are needed since Soong
includes system/core/include by default. Once all modules are
cleaned up to explicitly add the required libs, the symlinks will be
removed.

Moved headers of libutils to libutils_headers. They should be used
by modules for header-only inlines. Added libutils_headers as
dependency of libutils.

Split of C++ headers into those that have no dependency and those that
have dependency on libutils.so will be handled in a later CL.

Test: Add above libs to shared lib of local module
Change-Id: I122db72056b26b1f39bad1d9a0c2a1c5efda3550

1 files changed, 298 insertions, 0 deletions

diff --git a/libutils/include/utils/LruCache.h b/libutils/include/utils/LruCache.h
new file mode 100644
index 000000000..89dccd613
--- /dev/null
+++ b/libutils/include/utils/LruCache.h
@@ -0,0 +1,298 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ANDROID_UTILS_LRU_CACHE_H
+#define ANDROID_UTILS_LRU_CACHE_H
+
+#include <memory>
+#include <unordered_set>
+
+#include "utils/TypeHelpers.h"  // hash_t
+
+namespace android {
+
+/**
+ * GenerationCache callback used when an item is removed
+ */
+template<typename EntryKey, typename EntryValue>
+class OnEntryRemoved {
+public:
+    virtual ~OnEntryRemoved() { };
+    virtual void operator()(EntryKey& key, EntryValue& value) = 0;
+}; // class OnEntryRemoved
+
+template <typename TKey, typename TValue>
+class LruCache {
+public:
+    explicit LruCache(uint32_t maxCapacity);
+    virtual ~LruCache();
+
+    enum Capacity {
+        kUnlimitedCapacity,
+    };
+
+    void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
+    size_t size() const;
+    const TValue& get(const TKey& key);
+    bool put(const TKey& key, const TValue& value);
+    bool remove(const TKey& key);
+    bool removeOldest();
+    void clear();
+    const TValue& peekOldestValue();
+
+private:
+    LruCache(const LruCache& that);  // disallow copy constructor
+
+    // Super class so that we can have entries having only a key reference, for searches.
+    class KeyedEntry {
+    public:
+        virtual const TKey& getKey() const = 0;
+        // Make sure the right destructor is executed so that keys and values are deleted.
+        virtual ~KeyedEntry() {}
+    };
+
+    class Entry final : public KeyedEntry {
+    public:
+        TKey key;
+        TValue value;
+        Entry* parent;
+        Entry* child;
+
+        Entry(TKey _key, TValue _value) : key(_key), value(_value), parent(NULL), child(NULL) {
+        }
+        const TKey& getKey() const final { return key; }
+    };
+
+    class EntryForSearch : public KeyedEntry {
+    public:
+        const TKey& key;
+        EntryForSearch(const TKey& key_) : key(key_) {
+        }
+        const TKey& getKey() const final { return key; }
+    };
+
+    struct HashForEntry : public std::unary_function<KeyedEntry*, hash_t> {
+        size_t operator() (const KeyedEntry* entry) const {
+            return hash_type(entry->getKey());
+        };
+    };
+
+    struct EqualityForHashedEntries : public std::unary_function<KeyedEntry*, hash_t> {
+        bool operator() (const KeyedEntry* lhs, const KeyedEntry* rhs) const {
+            return lhs->getKey() == rhs->getKey();
+        };
+    };
+
+    // All entries in the set will be Entry*. Using the weaker KeyedEntry as to allow entries
+    // that have only a key reference, for searching.
+    typedef std::unordered_set<KeyedEntry*, HashForEntry, EqualityForHashedEntries> LruCacheSet;
+
+    void attachToCache(Entry& entry);
+    void detachFromCache(Entry& entry);
+
+    typename LruCacheSet::iterator findByKey(const TKey& key) {
+        EntryForSearch entryForSearch(key);
+        typename LruCacheSet::iterator result = mSet->find(&entryForSearch);
+        return result;
+    }
+
+    std::unique_ptr<LruCacheSet> mSet;
+    OnEntryRemoved<TKey, TValue>* mListener;
+    Entry* mOldest;
+    Entry* mYoungest;
+    uint32_t mMaxCapacity;
+    TValue mNullValue;
+
+public:
+    // To be used like:
+    // while (it.next()) {
+    //   it.value(); it.key();
+    // }
+    class Iterator {
+    public:
+        Iterator(const LruCache<TKey, TValue>& cache):
+                mCache(cache), mIterator(mCache.mSet->begin()), mBeginReturned(false) {
+        }
+
+        bool next() {
+            if (mIterator == mCache.mSet->end()) {
+                return false;
+            }
+            if (!mBeginReturned) {
+                // mIterator has been initialized to the beginning and
+                // hasn't been returned. Do not advance:
+                mBeginReturned = true;
+            } else {
+                std::advance(mIterator, 1);
+            }
+            bool ret = (mIterator != mCache.mSet->end());
+            return ret;
+        }
+
+        const TValue& value() const {
+            // All the elements in the set are of type Entry. See comment in the definition
+            // of LruCacheSet above.
+            return reinterpret_cast<Entry *>(*mIterator)->value;
+        }
+
+        const TKey& key() const {
+            return (*mIterator)->getKey();
+        }
+    private:
+        const LruCache<TKey, TValue>& mCache;
+        typename LruCacheSet::iterator mIterator;
+        bool mBeginReturned;
+    };
+};
+
+// Implementation is here, because it's fully templated
+template <typename TKey, typename TValue>
+LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
+    : mSet(new LruCacheSet())
+    , mListener(NULL)
+    , mOldest(NULL)
+    , mYoungest(NULL)
+    , mMaxCapacity(maxCapacity)
+    , mNullValue(0) {
+    mSet->max_load_factor(1.0);
+};
+
+template <typename TKey, typename TValue>
+LruCache<TKey, TValue>::~LruCache() {
+    // Need to delete created entries.
+    clear();
+};
+
+template<typename K, typename V>
+void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
+    mListener = listener;
+}
+
+template <typename TKey, typename TValue>
+size_t LruCache<TKey, TValue>::size() const {
+    return mSet->size();
+}
+
+template <typename TKey, typename TValue>
+const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
+    typename LruCacheSet::const_iterator find_result = findByKey(key);
+    if (find_result == mSet->end()) {
+        return mNullValue;
+    }
+    // All the elements in the set are of type Entry. See comment in the definition
+    // of LruCacheSet above.
+    Entry *entry = reinterpret_cast<Entry*>(*find_result);
+    detachFromCache(*entry);
+    attachToCache(*entry);
+    return entry->value;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
+    if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
+        removeOldest();
+    }
+
+    if (findByKey(key) != mSet->end()) {
+        return false;
+    }
+
+    Entry* newEntry = new Entry(key, value);
+    mSet->insert(newEntry);
+    attachToCache(*newEntry);
+    return true;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::remove(const TKey& key) {
+    typename LruCacheSet::const_iterator find_result = findByKey(key);
+    if (find_result == mSet->end()) {
+        return false;
+    }
+    // All the elements in the set are of type Entry. See comment in the definition
+    // of LruCacheSet above.
+    Entry* entry = reinterpret_cast<Entry*>(*find_result);
+    mSet->erase(entry);
+    if (mListener) {
+        (*mListener)(entry->key, entry->value);
+    }
+    detachFromCache(*entry);
+    delete entry;
+    return true;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::removeOldest() {
+    if (mOldest != NULL) {
+        return remove(mOldest->key);
+        // TODO: should probably abort if false
+    }
+    return false;
+}
+
+template <typename TKey, typename TValue>
+const TValue& LruCache<TKey, TValue>::peekOldestValue() {
+    if (mOldest) {
+        return mOldest->value;
+    }
+    return mNullValue;
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::clear() {
+    if (mListener) {
+        for (Entry* p = mOldest; p != NULL; p = p->child) {
+            (*mListener)(p->key, p->value);
+        }
+    }
+    mYoungest = NULL;
+    mOldest = NULL;
+    for (auto entry : *mSet.get()) {
+        delete entry;
+    }
+    mSet->clear();
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
+    if (mYoungest == NULL) {
+        mYoungest = mOldest = &entry;
+    } else {
+        entry.parent = mYoungest;
+        mYoungest->child = &entry;
+        mYoungest = &entry;
+    }
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
+    if (entry.parent != NULL) {
+        entry.parent->child = entry.child;
+    } else {
+        mOldest = entry.child;
+    }
+    if (entry.child != NULL) {
+        entry.child->parent = entry.parent;
+    } else {
+        mYoungest = entry.parent;
+    }
+
+    entry.parent = NULL;
+    entry.child = NULL;
+}
+
+}
+#endif // ANDROID_UTILS_LRU_CACHE_H