logd: switch to unordered_map from BasicHashtable

(charry pick from commit 511338dd575572d567c04d69eaea60627b6c3452)

BasicHashtable is relatively untested, move over to
a C++ template library that has more bake time.

Bug: 20419786
Bug: 21590652
Bug: 20500228
Change-Id: I926aaecdc8345eca75c08fdd561b0473504c5d95

3 files changed, 56 insertions, 63 deletions

diff --git a/logd/LogBuffer.cpp b/logd/LogBuffer.cpp
index 1da52d8..80fc9f5 100644
--- a/logd/LogBuffer.cpp
+++ b/logd/LogBuffer.cpp
@@ -22,6 +22,8 @@
 #include <time.h>
 #include <unistd.h>
 
+#include <unordered_map>
+
 #include <cutils/properties.h>
 #include <log/logger.h>
 
@@ -246,31 +248,21 @@ public:
     uint64_t getKey() { return value; }
 };
 
-class LogBufferElementEntry {
-    const uint64_t key;
-    LogBufferElement *last;
-
-public:
-    LogBufferElementEntry(const uint64_t &k, LogBufferElement *e):key(k),last(e) { }
+class LogBufferElementLast {
 
-    const uint64_t&getKey() const { return key; }
-
-    LogBufferElement *getLast() { return last; }
-};
-
-class LogBufferElementLast : public android::BasicHashtable<uint64_t, LogBufferElementEntry> {
+    typedef std::unordered_map<uint64_t, LogBufferElement *> LogBufferElementMap;
+    LogBufferElementMap map;
 
 public:
+
     bool merge(LogBufferElement *e, unsigned short dropped) {
         LogBufferElementKey key(e->getUid(), e->getPid(), e->getTid());
-        android::hash_t hash = android::hash_type(key.getKey());
-        ssize_t index = find(-1, hash, key.getKey());
-        if (index != -1) {
-            LogBufferElementEntry &entry = editEntryAt(index);
-            LogBufferElement *l = entry.getLast();
+        LogBufferElementMap::iterator it = map.find(key.getKey());
+        if (it != map.end()) {
+            LogBufferElement *l = it->second;
             unsigned short d = l->getDropped();
             if ((dropped + d) > USHRT_MAX) {
-                removeAt(index);
+                map.erase(it);
             } else {
                 l->setDropped(dropped + d);
                 return true;
@@ -279,26 +271,24 @@ public:
         return false;
     }
 
-    size_t add(LogBufferElement *e) {
+    void add(LogBufferElement *e) {
         LogBufferElementKey key(e->getUid(), e->getPid(), e->getTid());
-        android::hash_t hash = android::hash_type(key.getKey());
-        return android::BasicHashtable<uint64_t, LogBufferElementEntry>::
-            add(hash, LogBufferElementEntry(key.getKey(), e));
+        map[key.getKey()] = e;
     }
 
     inline void clear() {
-        android::BasicHashtable<uint64_t, LogBufferElementEntry>::clear();
+        map.clear();
     }
 
     void clear(LogBufferElement *e) {
         uint64_t current = e->getRealTime().nsec() - NS_PER_SEC;
-        ssize_t index = -1;
-        while((index = next(index)) >= 0) {
-            LogBufferElement *l = editEntryAt(index).getLast();
+        for(LogBufferElementMap::iterator it = map.begin(); it != map.end();) {
+            LogBufferElement *l = it->second;
             if ((l->getDropped() >= EXPIRE_THRESHOLD)
                     && (current > l->getRealTime().nsec())) {
-                removeAt(index);
-                index = -1;
+                it = map.erase(it);
+            } else {
+                ++it;
             }
         }
     }
diff --git a/logd/LogStatistics.cpp b/logd/LogStatistics.cpp
index 90c49c0..48c2fe6 100644
--- a/logd/LogStatistics.cpp
+++ b/logd/LogStatistics.cpp
@@ -161,9 +161,8 @@ char *LogStatistics::uidToName(uid_t uid) {
     }
 
     // report uid -> pid(s) -> pidToName if unique
-    ssize_t index = -1;
-    while ((index = pidTable.next(index)) != -1) {
-        const PidEntry &entry = pidTable.entryAt(index);
+    for(pidTable_t::iterator it = pidTable.begin(); it != pidTable.end(); ++it) {
+        const PidEntry &entry = it->second;
 
         if (entry.getUid() == uid) {
             const char *n = entry.getName();
@@ -520,12 +519,12 @@ uid_t pidToUid(pid_t pid) {
 }
 
 uid_t LogStatistics::pidToUid(pid_t pid) {
-    return pidTable.entryAt(pidTable.add(pid)).getUid();
+    return pidTable.add(pid)->second.getUid();
 }
 
 // caller must free character string
 char *LogStatistics::pidToName(pid_t pid) {
-    const char *name = pidTable.entryAt(pidTable.add(pid)).getName();
+    const char *name = pidTable.add(pid)->second.getName();
     if (!name) {
         return NULL;
     }
diff --git a/logd/LogStatistics.h b/logd/LogStatistics.h
index f60f3ed..b9e9650 100644
--- a/logd/LogStatistics.h
+++ b/logd/LogStatistics.h
@@ -21,8 +21,9 @@
 #include <stdlib.h>
 #include <sys/types.h>
 
+#include <unordered_map>
+
 #include <log/log.h>
-#include <utils/BasicHashtable.h>
 
 #include "LogBufferElement.h"
 
@@ -30,8 +31,14 @@
     for (log_id_t i = LOG_ID_MIN; i < LOG_ID_MAX; i = (log_id_t) (i + 1))
 
 template <typename TKey, typename TEntry>
-class LogHashtable : public android::BasicHashtable<TKey, TEntry> {
+class LogHashtable {
+
+    std::unordered_map<TKey, TEntry> map;
+
 public:
+
+    typedef typename std::unordered_map<TKey, TEntry>::iterator iterator;
+
     std::unique_ptr<const TEntry *[]> sort(size_t n) {
         if (!n) {
             std::unique_ptr<const TEntry *[]> sorted(NULL);
@@ -41,9 +48,8 @@ public:
         const TEntry **retval = new const TEntry* [n];
         memset(retval, 0, sizeof(*retval) * n);
 
-        ssize_t index = -1;
-        while ((index = android::BasicHashtable<TKey, TEntry>::next(index)) >= 0) {
-            const TEntry &entry = android::BasicHashtable<TKey, TEntry>::entryAt(index);
+        for(iterator it = map.begin(); it != map.end(); ++it) {
+            const TEntry &entry = it->second;
             size_t s = entry.getSizes();
             ssize_t i = n - 1;
             while ((!retval[i] || (s > retval[i]->getSizes())) && (--i >= 0))
@@ -70,45 +76,43 @@ public:
         return index;
     }
 
-    ssize_t next(ssize_t index) {
-        return android::BasicHashtable<TKey, TEntry>::next(index);
-    }
-
-    size_t add(TKey key, LogBufferElement *e) {
-        android::hash_t hash = android::hash_type(key);
-        ssize_t index = android::BasicHashtable<TKey, TEntry>::find(-1, hash, key);
-        if (index == -1) {
-            return android::BasicHashtable<TKey, TEntry>::add(hash, TEntry(e));
+    inline iterator add(TKey key, LogBufferElement *e) {
+        iterator it = map.find(key);
+        if (it == map.end()) {
+            it = map.insert(std::make_pair(key, TEntry(e))).first;
+        } else {
+            it->second.add(e);
         }
-        android::BasicHashtable<TKey, TEntry>::editEntryAt(index).add(e);
-        return index;
+        return it;
     }
 
-    inline size_t add(TKey key) {
-        android::hash_t hash = android::hash_type(key);
-        ssize_t index = android::BasicHashtable<TKey, TEntry>::find(-1, hash, key);
-        if (index == -1) {
-            return android::BasicHashtable<TKey, TEntry>::add(hash, TEntry(key));
+    inline iterator add(TKey key) {
+        iterator it = map.find(key);
+        if (it == map.end()) {
+            it = map.insert(std::make_pair(key, TEntry(key))).first;
+        } else {
+            it->second.add(key);
         }
-        android::BasicHashtable<TKey, TEntry>::editEntryAt(index).add(key);
-        return index;
+        return it;
     }
 
     void subtract(TKey key, LogBufferElement *e) {
-        ssize_t index = android::BasicHashtable<TKey, TEntry>::find(-1, android::hash_type(key), key);
-        if ((index != -1)
-         && android::BasicHashtable<TKey, TEntry>::editEntryAt(index).subtract(e)) {
-            android::BasicHashtable<TKey, TEntry>::removeAt(index);
+        iterator it = map.find(key);
+        if ((it != map.end()) && it->second.subtract(e)) {
+            map.erase(it);
         }
     }
 
     inline void drop(TKey key, LogBufferElement *e) {
-        ssize_t index = android::BasicHashtable<TKey, TEntry>::find(-1, android::hash_type(key), key);
-        if (index != -1) {
-            android::BasicHashtable<TKey, TEntry>::editEntryAt(index).drop(e);
+        iterator it = map.find(key);
+        if (it != map.end()) {
+            it->second.drop(e);
         }
     }
 
+    inline iterator begin() { return map.begin(); }
+    inline iterator end() { return map.end(); }
+
 };
 
 struct EntryBase {