Use hash map for event handler file descriptor map

runtime/bin/hashmap_test.cc

Index: runtime/bin/hashmap_test.cc
diff --git a/runtime/bin/hashmap_test.cc b/runtime/bin/hashmap_test.cc
new file mode 100644
index 0000000000000000000000000000000000000000..b0b532ef83113f8a7c8a42cd5ef71800f28e3342
--- /dev/null
+++ b/runtime/bin/hashmap_test.cc
@@ -0,0 +1,150 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+#include "bin/hashmap.h"
+#include "platform/assert.h"
+#include "platform/globals.h"
+#include "vm/unit_test.h"
+
+static bool DefaultMatchFun(void* a, void* b) {
+  return a == b;
+}
+
+
+typedef uint32_t (*IntKeyHash)(uint32_t key);
+
+
+class IntSet {
+ public:
+  explicit IntSet(IntKeyHash hash) : hash_(hash), map_(DefaultMatchFun)  {}
+
+  void Insert(int x) {
+    EXPECT_NE(0, x);  // 0 corresponds to (void*)NULL - illegal key value
+    HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), hash_(x), true);
+    EXPECT(p != NULL);  // insert is set!
+    EXPECT_EQ(reinterpret_cast<void*>(x), p->key);
+    // We don't care about p->value.
+  }
+
+  void Remove(int x) {
+    EXPECT_NE(0, x);  // 0 corresponds to (void*)NULL - illegal key value
+    map_.Remove(reinterpret_cast<void*>(x), hash_(x));
+  }
+
+  bool Present(int x) {
+    HashMap::Entry* p =
+        map_.Lookup(reinterpret_cast<void*>(x), hash_(x), false);
+    if (p != NULL) {
+      EXPECT_EQ(reinterpret_cast<void*>(x), p->key);
+    }
+    return p != NULL;
+  }
+
+  void Clear() {
+    map_.Clear();
+  }
+
+  uint32_t occupancy() const {
+    uint32_t count = 0;
+    for (HashMap::Entry* p = map_.Start(); p != NULL; p = map_.Next(p)) {
+      count++;
+    }
+    EXPECT_EQ(map_.occupancy(), static_cast<double>(count));

[Ivan Posva, 2012/01/17 07:57:41]

Why the cast to double?

[Søren Gjesse, 2012/01/17 09:28:04]

Don't know. Changed count to type intptr_t and removed cast.

+    return count;
+  }
+
+ private:
+  IntKeyHash hash_;
+  HashMap map_;
+};
+
+
+static uint32_t Hash(uint32_t key)  { return 23; }
+static uint32_t CollisionHash(uint32_t key)  { return key & 0x3; }

[Ivan Posva, 2012/01/17 07:57:41]

By using these two hash functions you will tend to cluster the collisions at the
beginning. How do you ensure you test wrap around?

[Søren Gjesse, 2012/01/17 09:28:04]

Added a number of additional hash functions with collision at the end (as long
as the backing store as the initial size). Extended the test to use these as
well as the Utils::WordHash hash function.

+
+
+void TestSet(IntKeyHash hash, int size) {
+  IntSet set(hash);
+  EXPECT_EQ(0u, set.occupancy());
+
+  set.Insert(1);
+  set.Insert(2);
+  set.Insert(3);
+  EXPECT_EQ(3u, set.occupancy());
+
+  set.Insert(2);
+  set.Insert(3);
+  EXPECT_EQ(3u, set.occupancy());
+
+  EXPECT(set.Present(1));
+  EXPECT(set.Present(2));
+  EXPECT(set.Present(3));
+  EXPECT(!set.Present(4));
+  EXPECT_EQ(3u, set.occupancy());
+
+  set.Remove(1);
+  EXPECT(!set.Present(1));
+  EXPECT(set.Present(2));
+  EXPECT(set.Present(3));
+  EXPECT_EQ(2u, set.occupancy());
+
+  set.Remove(3);
+  EXPECT(!set.Present(1));
+  EXPECT(set.Present(2));
+  EXPECT(!set.Present(3));
+  EXPECT_EQ(1u, set.occupancy());
+
+  set.Clear();
+  EXPECT_EQ(0u, set.occupancy());
+
+  // Insert a long series of values.
+  const int start = 453;
+  const int factor = 13;
+  const int offset = 7;
+  const uint32_t n = size;
+
+  int x = start;
+  for (uint32_t i = 0; i < n; i++) {
+    EXPECT_EQ(i, static_cast<double>(set.occupancy()));

[Ivan Posva, 2012/01/17 07:57:41]

ditto. Cast to double?

[Søren Gjesse, 2012/01/17 09:28:04]

Removed.

+    set.Insert(x);
+    x = x * factor + offset;
+  }
+  EXPECT_EQ(n, static_cast<double>(set.occupancy()));

[Ivan Posva, 2012/01/17 07:57:41]

ditto. And more places...

[Søren Gjesse, 2012/01/17 09:28:04]

Removed.

+
+  // Verify the same sequence of values.
+  x = start;
+  for (uint32_t i = 0; i < n; i++) {
+    EXPECT(set.Present(x));
+    x = x * factor + offset;
+  }
+  EXPECT_EQ(n, static_cast<double>(set.occupancy()));
+
+  // Remove all these values.
+  x = start;
+  for (uint32_t i = 0; i < n; i++) {
+    EXPECT_EQ(n - i, static_cast<double>(set.occupancy()));
+    EXPECT(set.Present(x));
+    set.Remove(x);
+    EXPECT(!set.Present(x));
+    x = x * factor + offset;
+
+    // Verify the the expected values are still there.
+    int y = start;
+    for (uint32_t j = 0; j < n; j++) {
+      if (j <= i) {
+        EXPECT(!set.Present(y));
+      } else {
+        EXPECT(set.Present(y));
+      }
+      y = y * factor + offset;
+    }
+  }
+  EXPECT_EQ(0u, set.occupancy());
+}
+
+
+UNIT_TEST_CASE(Set) {
+  TestSet(Hash, 100);
+  TestSet(CollisionHash, 50);
+}