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..409fde24b0f0b8d9111bf76899967b1793843869
--- /dev/null
+++ b/runtime/bin/hashmap_test.cc
@@ -0,0 +1,169 @@
+// 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"
+
+// Default initial size of hashmaps used in these tests.
+static intptr_t kInitialSize = 8;
+
+
+typedef uint32_t (*IntKeyHash)(uint32_t key);
+
+
+class IntSet {
+ public:
+  explicit IntSet(IntKeyHash hash)
+      : hash_(hash), map_(HashMap::SamePointerValue, kInitialSize)  {}
+
+  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_, count);
+    return count;
+  }
+
+ private:
+  IntKeyHash hash_;
+  HashMap map_;
+};
+
+
+static uint32_t WordHash(uint32_t key) { return dart::Utils::WordHash(key); }
+static uint32_t Hash(uint32_t key)  { return 23; }
+static uint32_t CollisionHash1(uint32_t key)  { return key & 0x3; }
+static uint32_t CollisionHash2(uint32_t key)  { return kInitialSize - 1; }
+static uint32_t CollisionHash3(uint32_t key)  { return kInitialSize - 2; }
+static uint32_t CollisionHash4(uint32_t key)  { return kInitialSize - 2; }
+
+
+void TestSet(IntKeyHash hash, int size) {
+  IntSet set(hash);
+  EXPECT_EQ(0u, set.occupancy());
+
+  set.Insert(1);
+  set.Insert(2);
+  set.Insert(3);
+  set.Insert(4);
+  EXPECT_EQ(4u, set.occupancy());
+
+  set.Insert(2);
+  set.Insert(3);
+  EXPECT_EQ(4u, set.occupancy());
+
+  EXPECT(set.Present(1));
+  EXPECT(set.Present(2));
+  EXPECT(set.Present(3));
+  EXPECT(set.Present(4));
+  EXPECT(!set.Present(5));
+  EXPECT_EQ(4u, set.occupancy());
+
+  set.Remove(1);
+  EXPECT(!set.Present(1));
+  EXPECT(set.Present(2));
+  EXPECT(set.Present(3));
+  EXPECT(set.Present(4));
+  EXPECT_EQ(3u, set.occupancy());
+
+  set.Remove(3);
+  EXPECT(!set.Present(1));
+  EXPECT(set.Present(2));
+  EXPECT(!set.Present(3));
+  EXPECT(set.Present(4));
+  EXPECT_EQ(2u, set.occupancy());
+
+  set.Remove(4);
+  EXPECT(!set.Present(1));
+  EXPECT(set.Present(2));
+  EXPECT(!set.Present(3));
+  EXPECT(!set.Present(4));
+  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, set.occupancy());
+    set.Insert(x);
+    x = x * factor + offset;
+  }
+  EXPECT_EQ(n, set.occupancy());
+
+  // 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, set.occupancy());
+
+  // Remove all these values.
+  x = start;
+  for (uint32_t i = 0; i < n; i++) {
+    EXPECT_EQ(n - i, 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(WordHash, 100);
+  TestSet(Hash, 100);
+  TestSet(CollisionHash1, 50);
+  TestSet(CollisionHash2, 50);
+  TestSet(CollisionHash3, 50);
+  TestSet(CollisionHash4, 50);
+}