hash_table_test.cc

// 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 ObjectPtr 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);
}

ISOLATE_UNIT_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();
}

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

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

}  // namespace dart