runtime/vm/hash_map_test.cc

// 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 "vm/hash_map.h"
#include "platform/assert.h"
#include "vm/unit_test.h"

namespace dart {

class TestValue {
 public:
  explicit TestValue(intptr_t x) : x_(x) {}
  // FinalizeHash is used here to provide coverage for FinalizeHash(...)
  // function.
  uword Hash() const { return FinalizeHash(static_cast<uint32_t>(x_) & 1); }
  bool Equals(const TestValue& other) { return x_ == other.x_; }

 private:
  intptr_t x_;
};

TEST_CASE(DirectChainedHashMap) {
  DirectChainedHashMap<PointerSetKeyValueTrait<TestValue>> map;
  EXPECT(map.IsEmpty());
  TestValue v1(0);
  TestValue v2(1);
  TestValue v3(0);
  map.Insert(&v1);
  EXPECT(map.LookupValue(&v1) == &v1);
  map.Insert(&v2);
  EXPECT(map.LookupValue(&v1) == &v1);
  EXPECT(map.LookupValue(&v2) == &v2);
  EXPECT(map.LookupValue(&v3) == &v1);
  EXPECT(map.Remove(&v1));
  EXPECT(map.Lookup(&v1) == nullptr);
  map.Insert(&v1);
  DirectChainedHashMap<PointerSetKeyValueTrait<TestValue>> map2(map);
  EXPECT(map2.LookupValue(&v1) == &v1);
  EXPECT(map2.LookupValue(&v2) == &v2);
  EXPECT(map2.LookupValue(&v3) == &v1);
}

TEST_CASE(DirectChainedHashMapInsertRemove) {
  DirectChainedHashMap<PointerSetKeyValueTrait<TestValue>> map;
  EXPECT(map.IsEmpty());
  TestValue v1(1);
  TestValue v2(3);  // Note: v1, v2, v3 should have the same hash.
  TestValue v3(5);

  // Start with adding and removing the same element.
  map.Insert(&v1);
  EXPECT(map.LookupValue(&v1) == &v1);
  EXPECT(map.Remove(&v1));
  EXPECT(map.Lookup(&v1) == nullptr);

  // Inserting v2 first should put it at the head of the list.
  map.Insert(&v2);
  map.Insert(&v1);
  EXPECT(map.LookupValue(&v2) == &v2);
  EXPECT(map.LookupValue(&v1) == &v1);

  // Check to see if removing the head of the list causes issues.
  EXPECT(map.Remove(&v2));
  EXPECT(map.Lookup(&v2) == nullptr);
  EXPECT(map.LookupValue(&v1) == &v1);

  // Reinsert v2, which will place it at the back of the hash map list.
  map.Insert(&v2);
  EXPECT(map.LookupValue(&v2) == &v2);

  // Remove from the back of the hash map list.
  EXPECT(map.Remove(&v2));
  EXPECT(map.Lookup(&v2) == nullptr);
  EXPECT(map.Remove(&v1));
  EXPECT(map.Lookup(&v1) == nullptr);

  // Check to see that removing an invalid element returns false.
  EXPECT(!map.Remove(&v1));

  // One last case: remove from the middle of a hash map list.
  map.Insert(&v1);
  map.Insert(&v2);
  map.Insert(&v3);

  EXPECT(map.LookupValue(&v1) == &v1);
  EXPECT(map.LookupValue(&v2) == &v2);
  EXPECT(map.LookupValue(&v3) == &v3);

  EXPECT(map.Remove(&v2));
  EXPECT(map.LookupValue(&v1) == &v1);
  EXPECT(map.Lookup(&v2) == nullptr);
  EXPECT(map.LookupValue(&v3) == &v3);

  EXPECT(map.Remove(&v1));
  EXPECT(map.Remove(&v3));

  EXPECT(map.IsEmpty());
}

TEST_CASE(MallocDirectChainedHashMap) {
  MallocDirectChainedHashMap<PointerSetKeyValueTrait<TestValue>> map;
  EXPECT(map.IsEmpty());
  TestValue v1(0);
  TestValue v2(1);
  TestValue v3(0);
  map.Insert(&v1);
  EXPECT(map.LookupValue(&v1) == &v1);
  map.Insert(&v2);
  EXPECT(map.LookupValue(&v1) == &v1);
  EXPECT(map.LookupValue(&v2) == &v2);
  EXPECT(map.LookupValue(&v3) == &v1);
  MallocDirectChainedHashMap<PointerSetKeyValueTrait<TestValue>> map2(map);
  EXPECT(map2.LookupValue(&v1) == &v1);
  EXPECT(map2.LookupValue(&v2) == &v2);
  EXPECT(map2.LookupValue(&v3) == &v1);
}

TEST_CASE(ZoneDirectChainedHashMap) {
  auto zone = thread->zone();
  auto const map = new (zone)
      ZoneDirectChainedHashMap<PointerSetKeyValueTrait<TestValue>>(zone);
  EXPECT(map->IsEmpty());
  TestValue v1(0);
  TestValue v2(1);
  TestValue v3(0);
  map->Insert(&v1);
  EXPECT(map->LookupValue(&v1) == &v1);
  map->Insert(&v2);
  EXPECT(map->LookupValue(&v1) == &v1);
  EXPECT(map->LookupValue(&v2) == &v2);
  EXPECT(map->LookupValue(&v3) == &v1);
}

class IntptrPair {
 public:
  IntptrPair() : first_(-1), second_(-1) {}
  IntptrPair(intptr_t first, intptr_t second)
      : first_(first), second_(second) {}

  intptr_t first() const { return first_; }
  intptr_t second() const { return second_; }

  bool operator==(const IntptrPair& other) {
    return (first_ == other.first_) && (second_ == other.second_);
  }

  bool operator!=(const IntptrPair& other) {
    return (first_ != other.first_) || (second_ != other.second_);
  }

 private:
  intptr_t first_;
  intptr_t second_;
};

TEST_CASE(DirectChainedHashMapIterator) {
  IntptrPair p1(1, 1);
  IntptrPair p2(2, 2);
  IntptrPair p3(3, 3);
  IntptrPair p4(4, 4);
  IntptrPair p5(5, 5);
  DirectChainedHashMap<NumbersKeyValueTrait<IntptrPair>> map;
  EXPECT(map.IsEmpty());
  DirectChainedHashMap<NumbersKeyValueTrait<IntptrPair>>::Iterator it =
      map.GetIterator();
  EXPECT(it.Next() == nullptr);
  it.Reset();

  map.Insert(p1);
  EXPECT(*it.Next() == p1);
  it.Reset();

  map.Insert(p2);
  map.Insert(p3);
  map.Insert(p4);
  map.Insert(p5);
  intptr_t count = 0;
  intptr_t sum = 0;
  while (true) {
    IntptrPair* p = it.Next();
    if (p == nullptr) {
      break;
    }
    count++;
    sum += p->second();
  }

  EXPECT(count == 5);
  EXPECT(sum == 15);
}

TEST_CASE(DirectChainedHashMapIteratorWithCollisionInLastBucket) {
  intptr_t values[] = {65,  325, 329, 73,  396, 207, 215, 93,  227, 39,
                       431, 112, 176, 313, 188, 317, 61,  127, 447};
  IntMap<intptr_t> map;

  for (intptr_t value : values) {
    map.Insert(value, value);
  }

  bool visited[ARRAY_SIZE(values)] = {};
  intptr_t count = 0;
  auto it = map.GetIterator();
  for (auto* p = it.Next(); p != nullptr; p = it.Next()) {
    ++count;
    bool found = false;
    intptr_t i = 0;
    for (intptr_t v : values) {
      if (v == p->key) {
        EXPECT(v == p->value);
        EXPECT(!visited[i]);
        visited[i] = true;
        found = true;
        break;
      }
      ++i;
    }
    EXPECT(found);
  }
  EXPECT(count == ARRAY_SIZE(values));
  for (bool is_visited : visited) {
    EXPECT(is_visited);
  }
}

TEST_CASE(ZoneCStringSet) {
  auto zone = thread->zone();

  const char* const kConst1 = "test";
  const char* const kConst2 = "test 2";

  char* const str1 = OS::SCreate(zone, "%s", kConst1);
  char* const str2 = OS::SCreate(zone, "%s", kConst2);
  char* const str3 = OS::SCreate(zone, "%s", kConst1);

  // Make sure these strings are pointer-distinct, but C-string-equal.
  EXPECT_NE(str1, str3);
  EXPECT_STREQ(str1, str3);

  auto const set = new (zone) ZoneCStringSet(zone);
  EXPECT(set->IsEmpty());

  set->Insert(str1);
  EXPECT_NOTNULL(set->Lookup(str1));
  EXPECT_NULLPTR(set->Lookup(str2));
  EXPECT_NOTNULL(set->Lookup(str3));

  set->Insert(str2);
  EXPECT_NOTNULL(set->Lookup(str1));
  EXPECT_NOTNULL(set->Lookup(str2));
  EXPECT_NOTNULL(set->Lookup(str3));

  EXPECT(set->Remove(str3));
  EXPECT_NULLPTR(set->Lookup(str1));
  EXPECT_NOTNULL(set->Lookup(str2));
  EXPECT_NULLPTR(set->Lookup(str3));

  EXPECT(!set->Remove(str3));
  EXPECT(set->Remove(str2));
  EXPECT(set->IsEmpty());
}

TEST_CASE(CStringIntMap) {
  const char* const kConst1 = "test";
  const char* const kConst2 = "test 2";

  char* const str1 = OS::SCreate(nullptr, "%s", kConst1);
  char* const str2 = OS::SCreate(nullptr, "%s", kConst2);
  char* const str3 = OS::SCreate(nullptr, "%s", kConst1);

  // Make sure these strings are pointer-distinct, but C-string-equal.
  EXPECT_NE(str1, str3);
  EXPECT_STREQ(str1, str3);

  const intptr_t i1 = 1;
  const intptr_t i2 = 2;

  CStringIntMap map;
  EXPECT(map.IsEmpty());

  map.Insert({str1, i1});
  EXPECT_NOTNULL(map.Lookup(str1));
  EXPECT_EQ(i1, map.LookupValue(str1));
  EXPECT_NULLPTR(map.Lookup(str2));
  EXPECT_NOTNULL(map.Lookup(str3));
  EXPECT_EQ(i1, map.LookupValue(str3));

  map.Insert({str2, i2});
  EXPECT_NOTNULL(map.Lookup(str1));
  EXPECT_EQ(i1, map.LookupValue(str1));
  EXPECT_NOTNULL(map.Lookup(str2));
  EXPECT_EQ(i2, map.LookupValue(str2));
  EXPECT_NOTNULL(map.Lookup(str3));
  EXPECT_EQ(i1, map.LookupValue(str3));

  EXPECT(map.Remove(str3));
  EXPECT_NULLPTR(map.Lookup(str1));
  EXPECT_NOTNULL(map.Lookup(str2));
  EXPECT_EQ(i2, map.LookupValue(str2));
  EXPECT_NULLPTR(map.Lookup(str3));

  EXPECT(!map.Remove(str3));
  EXPECT(map.Remove(str2));
  EXPECT(map.IsEmpty());

  free(str3);
  free(str2);
  free(str1);
}

TEST_CASE(CStringIntMapUpdate) {
  const char* const kConst1 = "test";
  const char* const kConst2 = "test 2";

  char* str1 = OS::SCreate(nullptr, "%s", kConst1);
  char* str2 = OS::SCreate(nullptr, "%s", kConst2);
  char* str3 = OS::SCreate(nullptr, "%s", kConst1);
  char* str4 = OS::SCreate(nullptr, "%s", kConst1);  // Only used for lookup.

  // Make sure these strings are pointer-distinct, but C-string-equal.
  EXPECT_NE(str1, str3);
  EXPECT_NE(str1, str4);
  EXPECT_NE(str3, str4);
  EXPECT_STREQ(str1, str3);
  EXPECT_STREQ(str1, str4);

  CStringIntMapKeyValueTrait::Pair p1{str1, 1};
  CStringIntMapKeyValueTrait::Pair p2{str2, 2};
  CStringIntMapKeyValueTrait::Pair p3{str3, 3};

  CStringIntMap map;
  EXPECT(map.IsEmpty());

  map.Update(p1);
  EXPECT_NOTNULL(map.Lookup(str1));
  EXPECT_EQ(p1.value, map.LookupValue(str1));
  EXPECT_NULLPTR(map.Lookup(str2));
  EXPECT_NOTNULL(map.Lookup(str3));
  EXPECT_EQ(p1.value, map.LookupValue(str3));
  EXPECT_NOTNULL(map.Lookup(str4));
  EXPECT_EQ(p1.value, map.LookupValue(str4));

  map.Update(p2);
  EXPECT_NOTNULL(map.Lookup(str1));
  EXPECT_EQ(p1.value, map.LookupValue(str1));
  EXPECT_NOTNULL(map.Lookup(str2));
  EXPECT_EQ(p2.value, map.LookupValue(str2));
  EXPECT_NOTNULL(map.Lookup(str3));
  EXPECT_EQ(p1.value, map.LookupValue(str3));
  EXPECT_NOTNULL(map.Lookup(str4));
  EXPECT_EQ(p1.value, map.LookupValue(str4));

  // Check Lookup after Update.
  map.Update(p3);
  EXPECT_NOTNULL(map.Lookup(str1));
  EXPECT_EQ(p3.value, map.LookupValue(str1));
  EXPECT_NOTNULL(map.Lookup(str2));
  EXPECT_EQ(p2.value, map.LookupValue(str2));
  EXPECT_NOTNULL(map.Lookup(str3));
  EXPECT_EQ(p3.value, map.LookupValue(str3));
  EXPECT_NOTNULL(map.Lookup(str4));
  EXPECT_EQ(p3.value, map.LookupValue(str4));

  // Check that single Remove after only Updates ensures Lookup fails after.
  EXPECT(map.Remove(str3));
  EXPECT_NULLPTR(map.Lookup(str1));
  EXPECT_NOTNULL(map.Lookup(str2));
  EXPECT_EQ(p2.value, map.LookupValue(str2));
  EXPECT_NULLPTR(map.Lookup(str3));
  EXPECT_NULLPTR(map.Lookup(str4));

  EXPECT(!map.Remove(str3));
  EXPECT(map.Remove(str2));
  EXPECT(map.IsEmpty());

  // Quick double-check that these weren't side-effected by the implementation
  // of hash maps (p1 especially).
  EXPECT_EQ(str1, p1.key);
  EXPECT_EQ(1, p1.value);
  EXPECT_EQ(str2, p2.key);
  EXPECT_EQ(2, p2.value);
  EXPECT_EQ(str3, p3.key);
  EXPECT_EQ(3, p3.value);

  free(str4);
  free(str3);
  free(str2);
  free(str1);
}

}  // namespace dart