You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mesos.apache.org by vi...@apache.org on 2013/08/14 20:07:35 UTC
[12/18] git commit: Implemented a LinkedHashMap that preserves the
insertion order of keys of a hashmap.
Implemented a LinkedHashMap that preserves the insertion
order of keys of a hashmap.
Review: https://reviews.apache.org/r/13464
Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/a2ebf17f
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/a2ebf17f
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/a2ebf17f
Branch: refs/heads/master
Commit: a2ebf17f030697696f109db4391a6d9dc9225232
Parents: 930aca1
Author: Vinod Kone <vi...@twitter.com>
Authored: Sat Aug 10 01:13:55 2013 -0700
Committer: Vinod Kone <vi...@twitter.com>
Committed: Wed Aug 14 10:49:29 2013 -0700
----------------------------------------------------------------------
3rdparty/libprocess/3rdparty/Makefile.am | 1 +
3rdparty/libprocess/3rdparty/stout/Makefile.am | 2 +
.../3rdparty/stout/include/stout/hashmap.hpp | 2 +
.../stout/include/stout/linkedhashmap.hpp | 92 +++++++++++++++++++
.../stout/tests/linkedhashmap_tests.cpp | 93 ++++++++++++++++++++
5 files changed, 190 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/mesos/blob/a2ebf17f/3rdparty/libprocess/3rdparty/Makefile.am
----------------------------------------------------------------------
diff --git a/3rdparty/libprocess/3rdparty/Makefile.am b/3rdparty/libprocess/3rdparty/Makefile.am
index 0cd407c..e8561df 100644
--- a/3rdparty/libprocess/3rdparty/Makefile.am
+++ b/3rdparty/libprocess/3rdparty/Makefile.am
@@ -123,6 +123,7 @@ stout_tests_SOURCES = \
$(STOUT)/tests/gzip_tests.cpp \
$(STOUT)/tests/hashset_tests.cpp \
$(STOUT)/tests/json_tests.cpp \
+ $(STOUT)/tests/linkedhashmap_tests.cpp \
$(STOUT)/tests/main.cpp \
$(STOUT)/tests/multimap_tests.cpp \
$(STOUT)/tests/none_tests.cpp \
http://git-wip-us.apache.org/repos/asf/mesos/blob/a2ebf17f/3rdparty/libprocess/3rdparty/stout/Makefile.am
----------------------------------------------------------------------
diff --git a/3rdparty/libprocess/3rdparty/stout/Makefile.am b/3rdparty/libprocess/3rdparty/stout/Makefile.am
index e465fd1..0428aa8 100644
--- a/3rdparty/libprocess/3rdparty/stout/Makefile.am
+++ b/3rdparty/libprocess/3rdparty/stout/Makefile.am
@@ -26,6 +26,7 @@ EXTRA_DIST = \
include/stout/hashset.hpp \
include/stout/json.hpp \
include/stout/lambda.hpp \
+ include/stout/linkedhashmap.hpp \
include/stout/multihashmap.hpp \
include/stout/multimap.hpp \
include/stout/net.hpp \
@@ -66,6 +67,7 @@ EXTRA_DIST = \
tests/gzip_tests.cpp \
tests/hashset_tests.cpp \
tests/json_tests.cpp \
+ tests/linkedhashmap_tests.cpp \
tests/main.cpp \
tests/multimap_tests.cpp \
tests/none_tests.cpp \
http://git-wip-us.apache.org/repos/asf/mesos/blob/a2ebf17f/3rdparty/libprocess/3rdparty/stout/include/stout/hashmap.hpp
----------------------------------------------------------------------
diff --git a/3rdparty/libprocess/3rdparty/stout/include/stout/hashmap.hpp b/3rdparty/libprocess/3rdparty/stout/include/stout/hashmap.hpp
index 796cb50..cea6988 100644
--- a/3rdparty/libprocess/3rdparty/stout/include/stout/hashmap.hpp
+++ b/3rdparty/libprocess/3rdparty/stout/include/stout/hashmap.hpp
@@ -53,6 +53,7 @@ public:
}
// Returns the set of keys in this map.
+ // TODO(vinod/bmahler): Should return a list instead.
hashset<Key> keys() const
{
hashset<Key> result;
@@ -63,6 +64,7 @@ public:
}
// Returns the set of values in this map.
+ // TODO(vinod/bmahler): Should return a list instead.
hashset<Value> values() const
{
hashset<Value> result;
http://git-wip-us.apache.org/repos/asf/mesos/blob/a2ebf17f/3rdparty/libprocess/3rdparty/stout/include/stout/linkedhashmap.hpp
----------------------------------------------------------------------
diff --git a/3rdparty/libprocess/3rdparty/stout/include/stout/linkedhashmap.hpp b/3rdparty/libprocess/3rdparty/stout/include/stout/linkedhashmap.hpp
new file mode 100644
index 0000000..a27ec26
--- /dev/null
+++ b/3rdparty/libprocess/3rdparty/stout/include/stout/linkedhashmap.hpp
@@ -0,0 +1,92 @@
+#ifndef __STOUT_LINKEDHASHMAP_HPP__
+#define __STOUT_LINKEDHASHMAP_HPP__
+
+#include <list>
+#include <utility>
+
+#include <stout/hashmap.hpp>
+#include <stout/option.hpp>
+
+// Implementation of a hashmap that maintains the insertion order
+// of the keys. Note that re-insertion of a key (i.e., update)
+// doesn't update its insertion order.
+// TODO(vinod/bmahler): Consider extending from stout::hashmap and/or
+// having a compatible API with stout::hashmap.
+template <typename Key, typename Value>
+class LinkedHashMap
+{
+public:
+ typedef std::list<Key> list;
+ typedef hashmap<Key, std::pair<Value, typename list::iterator> > map;
+
+ Value& operator[] (const Key& key)
+ {
+ if (!values_.contains(key)) {
+ // Insert into the list and get the "pointer" into the list.
+ typename list::iterator i = keys_.insert(keys_.end(), key);
+ values_[key] = std::make_pair(Value(), i); // Store default value.
+ }
+ return values_[key].first;
+ }
+
+ Option<Value> get(const Key& key) const
+ {
+ if (values_.contains(key)) {
+ return values_.at(key).first;
+ }
+ return None();
+ }
+
+ bool contains(const Key& key) const
+ {
+ return values_.contains(key);
+ }
+
+ size_t erase(const Key& key)
+ {
+ if (values_.contains(key)) {
+ // Get the "pointer" into the list.
+ typename list::iterator i = values_[key].second;
+ keys_.erase(i);
+ return values_.erase(key);
+ }
+ return 0;
+ }
+
+ std::list<Key> keys() const
+ {
+ return keys_;
+ }
+
+ std::list<Value> values() const
+ {
+ std::list<Value> result;
+ foreach (const Key& key, keys_) {
+ result.push_back(values_.at(key).first);
+ }
+ return result;
+ }
+
+ size_t size() const
+ {
+ return keys_.size();
+ }
+
+ bool empty() const
+ {
+ return keys_.empty();
+ }
+
+ void clear()
+ {
+ values_.clear();
+ keys_.clear();
+ }
+
+private:
+ list keys_; // Keys ordered by the insertion order.
+ map values_; // Map of values and "pointers" to the linked list.
+};
+
+
+#endif // __STOUT_LINKEDHASHMAP_HPP__
http://git-wip-us.apache.org/repos/asf/mesos/blob/a2ebf17f/3rdparty/libprocess/3rdparty/stout/tests/linkedhashmap_tests.cpp
----------------------------------------------------------------------
diff --git a/3rdparty/libprocess/3rdparty/stout/tests/linkedhashmap_tests.cpp b/3rdparty/libprocess/3rdparty/stout/tests/linkedhashmap_tests.cpp
new file mode 100644
index 0000000..aca97ca
--- /dev/null
+++ b/3rdparty/libprocess/3rdparty/stout/tests/linkedhashmap_tests.cpp
@@ -0,0 +1,93 @@
+#include <stdint.h>
+
+#include <gtest/gtest.h>
+
+#include <list>
+#include <string>
+
+#include <stout/gtest.hpp>
+#include <stout/linkedhashmap.hpp>
+
+using std::list;
+using std::string;
+
+TEST(LinkedHashmapTest, Put)
+{
+ LinkedHashMap<string, int> map;
+
+ map["foo"] = 1;
+ ASSERT_SOME_EQ(1, map.get("foo"));
+ ASSERT_EQ(1, map.size());
+
+ map["bar"] = 2;
+ ASSERT_SOME_EQ(2, map.get("bar"));
+ ASSERT_EQ(2, map.size());
+
+ map["foo"] = 3;
+ ASSERT_SOME_EQ(3, map.get("foo"));
+ ASSERT_EQ(2, map.size());
+}
+
+
+TEST(LinkedHashmapTest, Contains)
+{
+ LinkedHashMap<string, int> map;
+ map["foo"] = 1;
+ map["bar"] = 2;
+ ASSERT_TRUE(map.contains("foo"));
+ ASSERT_TRUE(map.contains("bar"));
+ ASSERT_FALSE(map.contains("caz"));
+}
+
+
+TEST(LinkedHashmapTest, Erase)
+{
+ LinkedHashMap<string, int> map;
+
+ map["foo"] = 1;
+ map["bar"] = 2;
+ ASSERT_EQ(2, map.size());
+
+ ASSERT_EQ(1, map.erase("foo"));
+ ASSERT_EQ(0, map.erase("caz")); // Non-existent key.
+ ASSERT_NONE(map.get("foo"));
+ ASSERT_EQ(1, map.size());
+ ASSERT_SOME_EQ(2, map.get("bar"));
+}
+
+
+TEST(LinkedHashmapTest, Keys)
+{
+ LinkedHashMap<string, int> map;
+
+ std::list<string> keys;
+ keys.push_back("foo");
+ keys.push_back("bar");
+ keys.push_back("food");
+ keys.push_back("rad");
+ keys.push_back("cat");
+
+ // Insert keys into the map.
+ foreach (const string& key, keys) {
+ map[key] = 1;
+ }
+ map["foo"] = 1; // Re-insert a key.
+
+ // Ensure the keys returned are the same as insertion order.
+ ASSERT_EQ(keys, map.keys());
+}
+
+
+TEST(LinkedHashmapTest, Values)
+{
+ LinkedHashMap<string, int> map;
+
+ map["foo"] = 1;
+ map["bar"] = 2;
+ map["caz"] = 3;
+
+ int val = 0;
+ foreach (int value, map.values()) {
+ ASSERT_EQ(++val, value);
+ }
+}