runtime/vm/hash_table_test.cc - sdk.git - Git at Google

 // Copyright (c) 2014, 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 <algorithm>
 #include <cstring>
 #include <map>
 #include <set>
 #include <string>
 #include <utility>
 #include <vector>

 #include "platform/assert.h"
 #include "vm/hash_table.h"
 #include "vm/unit_test.h"

 namespace dart {

 // Various ways to look up strings. Uses length as the hash code to make it
 // easy to engineer collisions.
 class TestTraits {
  public:
   static const char* Name() { return "TestTraits"; }
   static bool ReportStats() { return false; }

   static bool IsMatch(const char* key, const Object& obj) {
     return String::Cast(obj).Equals(key);
   }
   static uword Hash(const char* key) { return static_cast<uword>(strlen(key)); }
   static bool IsMatch(const Object& a, const Object& b) {
     return a.IsString() && b.IsString() &&
            String::Cast(a).Equals(String::Cast(b));
   }
   static uword Hash(const Object& obj) { return String::Cast(obj).Length(); }
   static RawObject* NewKey(const char* key) { return String::New(key); }
 };

 template <typename Table>
 void Validate(const Table& table) {
   // Verify consistency of entry state tracking.
   intptr_t num_entries = table.NumEntries();
   intptr_t num_unused = table.NumUnused();
   intptr_t num_occupied = table.NumOccupied();
   intptr_t num_deleted = table.NumDeleted();
   for (intptr_t i = 0; i < num_entries; ++i) {
     EXPECT_EQ(1, table.IsUnused(i) + table.IsOccupied(i) + table.IsDeleted(i));
     num_unused -= table.IsUnused(i);
     num_occupied -= table.IsOccupied(i);
     num_deleted -= table.IsDeleted(i);
   }
   EXPECT_EQ(0, num_unused);
   EXPECT_EQ(0, num_occupied);
   EXPECT_EQ(0, num_deleted);
 }

 TEST_CASE(HashTable) {
   typedef HashTable<TestTraits, 2, 1> Table;
   Table table(Thread::Current()->zone(), HashTables::New<Table>(5));
   // Ensure that we did get at least 5 entries.
   EXPECT_LE(5, table.NumEntries());
   EXPECT_EQ(0, table.NumOccupied());
   Validate(table);
   EXPECT_EQ(-1, table.FindKey("a"));

   // Insertion and lookup.
   intptr_t a_entry = -1;
   EXPECT(!table.FindKeyOrDeletedOrUnused("a", &a_entry));
   EXPECT_NE(-1, a_entry);
   String& a = String::Handle(String::New("a"));
   table.InsertKey(a_entry, a);
   EXPECT_EQ(1, table.NumOccupied());
   Validate(table);
   EXPECT_EQ(a_entry, table.FindKey("a"));
   EXPECT_EQ(-1, table.FindKey("b"));
   intptr_t a_entry_again = -1;
   EXPECT(table.FindKeyOrDeletedOrUnused("a", &a_entry_again));
   EXPECT_EQ(a_entry, a_entry_again);
   intptr_t b_entry = -1;
   EXPECT(!table.FindKeyOrDeletedOrUnused("b", &b_entry));
   String& b = String::Handle(String::New("b"));
   table.InsertKey(b_entry, b);
   EXPECT_EQ(2, table.NumOccupied());
   Validate(table);

   // Deletion.
   table.DeleteEntry(a_entry);
   EXPECT_EQ(1, table.NumOccupied());
   Validate(table);
   EXPECT_EQ(-1, table.FindKey("a"));
   EXPECT_EQ(b_entry, table.FindKey("b"));
   intptr_t c_entry = -1;
   EXPECT(!table.FindKeyOrDeletedOrUnused("c", &c_entry));
   String& c = String::Handle(String::New("c"));
   table.InsertKey(c_entry, c);
   EXPECT_EQ(2, table.NumOccupied());
   Validate(table);
   EXPECT_EQ(c_entry, table.FindKey("c"));

   // Ensure we can actually reach 5 occupied entries (without expansion).
   {
     intptr_t entry = -1;
     EXPECT(!table.FindKeyOrDeletedOrUnused("d", &entry));
     String& k = String::Handle(String::New("d"));
     table.InsertKey(entry, k);
     EXPECT(!table.FindKeyOrDeletedOrUnused("e", &entry));
     k = String::New("e");
     table.InsertKey(entry, k);
     EXPECT(!table.FindKeyOrDeletedOrUnused("f", &entry));
     k = String::New("f");
     table.InsertKey(entry, k);
     EXPECT_EQ(5, table.NumOccupied());
   }
   table.Release();
 }

 std::string ToStdString(const String& str) {
   EXPECT(str.IsOneByteString());
   std::string result;
   for (intptr_t i = 0; i < str.Length(); ++i) {
     result += static_cast<char>(str.CharAt(i));
   }
   return result;
 }

 // Checks that 'expected' and 'actual' are equal sets. If 'ordered' is true,
 // it also verifies that their iteration orders match, i.e., that actual's
 // insertion order coincides with lexicographic order.
 template <typename Set>
 void VerifyStringSetsEqual(const std::set<std::string>& expected,
                            const Set& actual,
                            bool ordered) {
   // Get actual keys in iteration order.
   Array& keys = Array::Handle(HashTables::ToArray(actual, true));
   // Cardinality must match.
   EXPECT_EQ(static_cast<intptr_t>(expected.size()), keys.Length());
   std::vector<std::string> expected_vec(expected.begin(), expected.end());
   // Check containment.
   for (uintptr_t i = 0; i < expected_vec.size(); ++i) {
     EXPECT(actual.ContainsKey(expected_vec[i].c_str()));
   }
   // Equality, including order, if requested.
   std::vector<std::string> actual_vec;
   String& key = String::Handle();
   for (int i = 0; i < keys.Length(); ++i) {
     key ^= keys.At(i);
     actual_vec.push_back(ToStdString(key));
   }
   if (!ordered) {
     std::sort(actual_vec.begin(), actual_vec.end());
   }
   EXPECT(
       std::equal(actual_vec.begin(), actual_vec.end(), expected_vec.begin()));
 }

 // Checks that 'expected' and 'actual' are equal maps. If 'ordered' is true,
 // it also verifies that their iteration orders match, i.e., that actual's
 // insertion order coincides with lexicographic order.
 template <typename Map>
 void VerifyStringMapsEqual(const std::map<std::string, int>& expected,
                            const Map& actual,
                            bool ordered) {
   intptr_t expected_size = expected.size();
   // Get actual concatenated (key, value) pairs in iteration order.
   Array& entries = Array::Handle(HashTables::ToArray(actual, true));
   // Cardinality must match.
   EXPECT_EQ(expected_size * 2, entries.Length());
   std::vector<std::pair<std::string, int> > expected_vec(expected.begin(),
                                                          expected.end());
   // Check containment.
   Smi& value = Smi::Handle();
   for (uintptr_t i = 0; i < expected_vec.size(); ++i) {
     std::string key = expected_vec[i].first;
     EXPECT(actual.ContainsKey(key.c_str()));
     value ^= actual.GetOrNull(key.c_str());
     EXPECT_EQ(expected_vec[i].second, value.Value());
   }
   if (!ordered) {
     return;
   }
   // Equality including order.
   std::vector<std::string> actual_vec;
   String& key = String::Handle();
   for (int i = 0; i < expected_size; ++i) {
     key ^= entries.At(2 * i);
     value ^= entries.At(2 * i + 1);
     EXPECT(expected_vec[i].first == ToStdString(key));
     EXPECT_EQ(expected_vec[i].second, value.Value());
   }
 }

 template <typename Set>
 void TestSet(intptr_t initial_capacity, bool ordered) {
   std::set<std::string> expected;
   Set actual(HashTables::New<Set>(initial_capacity));
   // Insert the following strings twice:
   // aaa...aaa (length 26)
   // bbb..bbb
   // ...
   // yy
   // z
   for (int i = 0; i < 2; ++i) {
     for (char ch = 'a'; ch <= 'z'; ++ch) {
       std::string key('z' - ch + 1, ch);
       expected.insert(key);
       bool present = actual.Insert(String::Handle(String::New(key.c_str())));
       EXPECT_EQ((i != 0), present);
       Validate(actual);
       VerifyStringSetsEqual(expected, actual, ordered);
     }
   }
   actual.Clear();
   EXPECT_EQ(0, actual.NumOccupied());
   actual.Release();
 }

 template <typename Map>
 void TestMap(intptr_t initial_capacity, bool ordered) {
   std::map<std::string, int> expected;
   Map actual(HashTables::New<Map>(initial_capacity));
   // Insert the following (strings, int) mapping:
   // aaa...aaa -> 26
   // bbb..bbb -> 25
   // ...
   // yy -> 2
   // z -> 1
   for (int i = 0; i < 2; ++i) {
     for (char ch = 'a'; ch <= 'z'; ++ch) {
       int length = 'z' - ch + 1;
       std::string key(length, ch);
       // Map everything to zero initially, then update to their final values.
       int value = length * i;
       expected[key] = value;
       bool present =
           actual.UpdateOrInsert(String::Handle(String::New(key.c_str())),
                                 Smi::Handle(Smi::New(value)));
       EXPECT_EQ((i != 0), present);
       Validate(actual);
       VerifyStringMapsEqual(expected, actual, ordered);
     }
   }
   actual.Clear();
   EXPECT_EQ(0, actual.NumOccupied());
   actual.Release();
 }

 TEST_CASE(Sets) {
   for (intptr_t initial_capacity = 0; initial_capacity < 32;
        ++initial_capacity) {
     TestSet<UnorderedHashSet<TestTraits> >(initial_capacity, false);
   }
 }

 TEST_CASE(Maps) {
   for (intptr_t initial_capacity = 0; initial_capacity < 32;
        ++initial_capacity) {
     TestMap<UnorderedHashMap<TestTraits> >(initial_capacity, false);
   }
 }

 }  // namespace dart
	// Copyright (c) 2014, 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 <algorithm>
	#include <cstring>
	#include <map>
	#include <set>
	#include <string>
	#include <utility>
	#include <vector>

	#include "platform/assert.h"
	#include "vm/hash_table.h"
	#include "vm/unit_test.h"

	namespace dart {

	// Various ways to look up strings. Uses length as the hash code to make it
	// easy to engineer collisions.
	class TestTraits {
	public:
	static const char* Name() { return "TestTraits"; }
	static bool ReportStats() { return false; }

	static bool IsMatch(const char* key, const Object& obj) {
	return String::Cast(obj).Equals(key);
	}
	static uword Hash(const char* key) { return static_cast<uword>(strlen(key)); }
	static bool IsMatch(const Object& a, const Object& b) {
	return a.IsString() && b.IsString() &&
	String::Cast(a).Equals(String::Cast(b));
	}
	static uword Hash(const Object& obj) { return String::Cast(obj).Length(); }
	static RawObject* NewKey(const char* key) { return String::New(key); }
	};

	template <typename Table>
	void Validate(const Table& table) {
	// Verify consistency of entry state tracking.
	intptr_t num_entries = table.NumEntries();
	intptr_t num_unused = table.NumUnused();
	intptr_t num_occupied = table.NumOccupied();
	intptr_t num_deleted = table.NumDeleted();
	for (intptr_t i = 0; i < num_entries; ++i) {
	EXPECT_EQ(1, table.IsUnused(i) + table.IsOccupied(i) + table.IsDeleted(i));
	num_unused -= table.IsUnused(i);
	num_occupied -= table.IsOccupied(i);
	num_deleted -= table.IsDeleted(i);
	}
	EXPECT_EQ(0, num_unused);
	EXPECT_EQ(0, num_occupied);
	EXPECT_EQ(0, num_deleted);
	}

	TEST_CASE(HashTable) {
	typedef HashTable<TestTraits, 2, 1> Table;
	Table table(Thread::Current()->zone(), HashTables::New<Table>(5));
	// Ensure that we did get at least 5 entries.
	EXPECT_LE(5, table.NumEntries());
	EXPECT_EQ(0, table.NumOccupied());
	Validate(table);
	EXPECT_EQ(-1, table.FindKey("a"));

	// Insertion and lookup.
	intptr_t a_entry = -1;
	EXPECT(!table.FindKeyOrDeletedOrUnused("a", &a_entry));
	EXPECT_NE(-1, a_entry);
	String& a = String::Handle(String::New("a"));
	table.InsertKey(a_entry, a);
	EXPECT_EQ(1, table.NumOccupied());
	Validate(table);
	EXPECT_EQ(a_entry, table.FindKey("a"));
	EXPECT_EQ(-1, table.FindKey("b"));
	intptr_t a_entry_again = -1;
	EXPECT(table.FindKeyOrDeletedOrUnused("a", &a_entry_again));
	EXPECT_EQ(a_entry, a_entry_again);
	intptr_t b_entry = -1;
	EXPECT(!table.FindKeyOrDeletedOrUnused("b", &b_entry));
	String& b = String::Handle(String::New("b"));
	table.InsertKey(b_entry, b);
	EXPECT_EQ(2, table.NumOccupied());
	Validate(table);

	// Deletion.
	table.DeleteEntry(a_entry);
	EXPECT_EQ(1, table.NumOccupied());
	Validate(table);
	EXPECT_EQ(-1, table.FindKey("a"));
	EXPECT_EQ(b_entry, table.FindKey("b"));
	intptr_t c_entry = -1;
	EXPECT(!table.FindKeyOrDeletedOrUnused("c", &c_entry));
	String& c = String::Handle(String::New("c"));
	table.InsertKey(c_entry, c);
	EXPECT_EQ(2, table.NumOccupied());
	Validate(table);
	EXPECT_EQ(c_entry, table.FindKey("c"));

	// Ensure we can actually reach 5 occupied entries (without expansion).
	{
	intptr_t entry = -1;
	EXPECT(!table.FindKeyOrDeletedOrUnused("d", &entry));
	String& k = String::Handle(String::New("d"));
	table.InsertKey(entry, k);
	EXPECT(!table.FindKeyOrDeletedOrUnused("e", &entry));
	k = String::New("e");
	table.InsertKey(entry, k);
	EXPECT(!table.FindKeyOrDeletedOrUnused("f", &entry));
	k = String::New("f");
	table.InsertKey(entry, k);
	EXPECT_EQ(5, table.NumOccupied());
	}
	table.Release();
	}

	std::string ToStdString(const String& str) {
	EXPECT(str.IsOneByteString());
	std::string result;
	for (intptr_t i = 0; i < str.Length(); ++i) {
	result += static_cast<char>(str.CharAt(i));
	}
	return result;
	}

	// Checks that 'expected' and 'actual' are equal sets. If 'ordered' is true,
	// it also verifies that their iteration orders match, i.e., that actual's
	// insertion order coincides with lexicographic order.
	template <typename Set>
	void VerifyStringSetsEqual(const std::set<std::string>& expected,
	const Set& actual,
	bool ordered) {
	// Get actual keys in iteration order.
	Array& keys = Array::Handle(HashTables::ToArray(actual, true));
	// Cardinality must match.
	EXPECT_EQ(static_cast<intptr_t>(expected.size()), keys.Length());
	std::vector<std::string> expected_vec(expected.begin(), expected.end());
	// Check containment.
	for (uintptr_t i = 0; i < expected_vec.size(); ++i) {
	EXPECT(actual.ContainsKey(expected_vec[i].c_str()));
	}
	// Equality, including order, if requested.
	std::vector<std::string> actual_vec;
	String& key = String::Handle();
	for (int i = 0; i < keys.Length(); ++i) {
	key ^= keys.At(i);
	actual_vec.push_back(ToStdString(key));
	}
	if (!ordered) {
	std::sort(actual_vec.begin(), actual_vec.end());
	}
	EXPECT(
	std::equal(actual_vec.begin(), actual_vec.end(), expected_vec.begin()));
	}

	// Checks that 'expected' and 'actual' are equal maps. If 'ordered' is true,
	// it also verifies that their iteration orders match, i.e., that actual's
	// insertion order coincides with lexicographic order.
	template <typename Map>
	void VerifyStringMapsEqual(const std::map<std::string, int>& expected,
	const Map& actual,
	bool ordered) {
	intptr_t expected_size = expected.size();
	// Get actual concatenated (key, value) pairs in iteration order.
	Array& entries = Array::Handle(HashTables::ToArray(actual, true));
	// Cardinality must match.
	EXPECT_EQ(expected_size * 2, entries.Length());
	std::vector<std::pair<std::string, int> > expected_vec(expected.begin(),
	expected.end());
	// Check containment.
	Smi& value = Smi::Handle();
	for (uintptr_t i = 0; i < expected_vec.size(); ++i) {
	std::string key = expected_vec[i].first;
	EXPECT(actual.ContainsKey(key.c_str()));
	value ^= actual.GetOrNull(key.c_str());
	EXPECT_EQ(expected_vec[i].second, value.Value());
	}
	if (!ordered) {
	return;
	}
	// Equality including order.
	std::vector<std::string> actual_vec;
	String& key = String::Handle();
	for (int i = 0; i < expected_size; ++i) {
	key ^= entries.At(2 * i);
	value ^= entries.At(2 * i + 1);
	EXPECT(expected_vec[i].first == ToStdString(key));
	EXPECT_EQ(expected_vec[i].second, value.Value());
	}
	}

	template <typename Set>
	void TestSet(intptr_t initial_capacity, bool ordered) {
	std::set<std::string> expected;
	Set actual(HashTables::New<Set>(initial_capacity));
	// Insert the following strings twice:
	// aaa...aaa (length 26)
	// bbb..bbb
	// ...
	// yy
	// z
	for (int i = 0; i < 2; ++i) {
	for (char ch = 'a'; ch <= 'z'; ++ch) {
	std::string key('z' - ch + 1, ch);
	expected.insert(key);
	bool present = actual.Insert(String::Handle(String::New(key.c_str())));
	EXPECT_EQ((i != 0), present);
	Validate(actual);
	VerifyStringSetsEqual(expected, actual, ordered);
	}
	}
	actual.Clear();
	EXPECT_EQ(0, actual.NumOccupied());
	actual.Release();
	}

	template <typename Map>
	void TestMap(intptr_t initial_capacity, bool ordered) {
	std::map<std::string, int> expected;
	Map actual(HashTables::New<Map>(initial_capacity));
	// Insert the following (strings, int) mapping:
	// aaa...aaa -> 26
	// bbb..bbb -> 25
	// ...
	// yy -> 2
	// z -> 1
	for (int i = 0; i < 2; ++i) {
	for (char ch = 'a'; ch <= 'z'; ++ch) {
	int length = 'z' - ch + 1;
	std::string key(length, ch);
	// Map everything to zero initially, then update to their final values.
	int value = length * i;
	expected[key] = value;
	bool present =
	actual.UpdateOrInsert(String::Handle(String::New(key.c_str())),
	Smi::Handle(Smi::New(value)));
	EXPECT_EQ((i != 0), present);
	Validate(actual);
	VerifyStringMapsEqual(expected, actual, ordered);
	}
	}
	actual.Clear();
	EXPECT_EQ(0, actual.NumOccupied());
	actual.Release();
	}

	TEST_CASE(Sets) {
	for (intptr_t initial_capacity = 0; initial_capacity < 32;
	++initial_capacity) {
	TestSet<UnorderedHashSet<TestTraits> >(initial_capacity, false);
	}
	}

	TEST_CASE(Maps) {
	for (intptr_t initial_capacity = 0; initial_capacity < 32;
	++initial_capacity) {
	TestMap<UnorderedHashMap<TestTraits> >(initial_capacity, false);
	}
	}

	} // namespace dart