src/third_party/google-sparsehash/src/densehashtable_test.cc

// Copyright (c) 2010, Google Inc.
// All rights reserved.
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
// 
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// ---
// Author: Giao Nguyen

#include "config.h"
#include <google/sparsehash/densehashtable.h>
#include <google/sparsetable>   // for int16_t and u_int16_t
#include "testutil.h"
#include <stdio.h>
#include <stdlib.h>
#include <functional>   // for equal_to
#include <iostream>
#include <vector>
#include <string>

using STL_NAMESPACE::string;
using STL_NAMESPACE::vector;
using STL_NAMESPACE::cerr;
using STL_NAMESPACE::equal_to;
using STL_NAMESPACE::allocator;

static const int FLAGS_random_insertions = 1000000;
//             "Number of random insertions to test size and capacity"

#define arraysize(a)  ( sizeof(a) / sizeof(*(a)) )

namespace {

typedef int16_t int16;
typedef u_int16_t uint16;

using GOOGLE_NAMESPACE::dense_hashtable;

template<typename Value>
struct Identity {
  Value& operator()(Value& v) const { return v; }
  const Value& operator()(const Value& v) const { return v; }
};

template<typename Value>
struct SetKey {
  void operator()(Value* value, const Value& new_key) const {
    *value = new_key;
  }
};

struct IntHash {
  size_t operator()(int16 v) const { return v; }
};

struct Table : dense_hashtable<int16, int16,
                               IntHash, Identity<int16>, SetKey<int16>,
                               equal_to<int16>, allocator<int16> >  {
  Table() {
    set_empty_key(-32767);
  }
};

static int16 test_data[] = {
  -32766, -5432, -1, 0, 1, 8, 10000, 32766
};

class DensehashtableTest {
 protected:
  virtual void SetUp() {
    for (int i = 0; i < arraysize(test_data); ++i) {
      table_.insert(test_data[i]);
    }
  }

  virtual void TearDown() {
  }

  Table table_;
};


// This test verifies basic functionalities of densehashtable
TEST_F(DensehashtableTest, Basic) {
  // Test empty() on the preconstructed table
  EXPECT_FALSE(table_.empty());

  // Test default constructor and empty table
  Table ht;
  EXPECT_TRUE(ht.empty());
  EXPECT_EQ(ht.size(), 0);
  EXPECT_EQ(ht.bucket_count(), 32);  // min bucket count

  // Test operator==()
  EXPECT_TRUE(ht == ht);
  EXPECT_TRUE(ht != table_);
  EXPECT_TRUE(table_ == table_);

  // Test copy constructor
  Table ht2(table_);
  EXPECT_TRUE(ht2 == table_);

  // Test assignment
  ht = table_;
  EXPECT_TRUE(ht == table_);
  EXPECT_TRUE(ht == ht2);

  // Test clear()
  ht.clear();
  EXPECT_EQ(ht.size(), 0);
  EXPECT_FALSE(ht == ht2);
  EXPECT_TRUE(ht.empty());
  EXPECT_FALSE(ht2.empty());

  // Test swap()
  ht.swap(ht2);
  EXPECT_FALSE(ht.empty());
  EXPECT_TRUE(ht2.empty());
  EXPECT_FALSE(ht2 == table_);
  EXPECT_TRUE(ht == table_);
}


TEST_F(DensehashtableTest, Insert) {
  // Test insert()
  Table ht;
  ht.insert(6);
  EXPECT_EQ(ht.size(), 1);
  ht.insert(8);
  EXPECT_EQ(ht.size(), 2);

  // Save a copy to compare later
  Table ht2(ht);

  // Inserting the same element won't change the size nor content
  ht.insert(6);
  EXPECT_EQ(ht.size(), 2);
  EXPECT_TRUE(ht == ht2);

  // Insert a different item will change the content
  ht.insert(9);
  EXPECT_EQ(ht.size(), 3);
  EXPECT_FALSE(ht == ht2);

  // Test insert(iterator, iterator); begin() and end()
  ht2.clear();
  EXPECT_EQ(ht2.size(), 0);
  ht2.insert(table_.begin(), table_.end());
  EXPECT_TRUE(ht2 == table_);
  EXPECT_FALSE(ht2 == ht);

  // Test resize() and inserting a lot of items
  ht.clear();
  Table::size_type num_buckets = ht.bucket_count();
  ht.resize(FLAGS_random_insertions);
  EXPECT_GT(ht.bucket_count(), num_buckets);
  cerr << "After reserving " << FLAGS_random_insertions
       << " buckets, size=" << ht.size()
       << " old_bucket_count=" << num_buckets
       << " new_bucket_count=" << ht.bucket_count() << "\n";
  num_buckets = ht.bucket_count();

  Table::size_type num_entries = ht.size();
  for (int i = 0; i < FLAGS_random_insertions; ++i) {
    int16 val = static_cast<int16>(rand() & 0xFFFF);  // signed -> unsigned
    if (val == ht.empty_key())
      val++;
    num_entries += 1 - ht.count(val);
    ht.insert(val);
    EXPECT_EQ(ht.count(val), 1);
  }
  EXPECT_EQ(ht.size(), num_entries);
  // Check to see if the table got resized during insertion
  EXPECT_EQ(ht.bucket_count(), num_buckets);
  cerr << "After inserting " << FLAGS_random_insertions
       << " entries, size=" << ht.size()
       << " old_bucket_count=" << num_buckets
       << " new_bucket_count=" << ht.bucket_count() << "\n";
}


TEST_F(DensehashtableTest, Find) {
  // Test find() and count()
  Table ht;
  for (int i = 0; i < arraysize(test_data); ++i) {
    int16 val = test_data[i];
    EXPECT_EQ(ht.count(val), 0);
    EXPECT_EQ(table_.count(val), 1);

    Table::const_iterator it = table_.find(val);
    EXPECT_TRUE(it != table_.end());
    EXPECT_EQ(*it, val);
  }
}


TEST_F(DensehashtableTest, Erase) {
  Table ht(table_);
  EXPECT_TRUE(ht == table_);

  const int16 kDelKey = -32768;

  // Test set_deleted_key()
  ht.set_deleted_key(kDelKey);
  EXPECT_EQ(ht.deleted_key(), kDelKey);

  // Test erase(key)
  for (int i = 0; i < arraysize(test_data); ++i) {
    int16 val = test_data[i];
    EXPECT_EQ(ht.count(val), 1);
    ht.erase(val);
    EXPECT_EQ(ht.count(val), 0);
    EXPECT_EQ(ht.size(), table_.size() - i - 1);
  }
  EXPECT_EQ(ht.size(), 0);
  EXPECT_TRUE(ht.empty());

  // Test erase(iterator)
  ht = table_;
  ht.set_deleted_key(kDelKey);
  EXPECT_FALSE(ht.empty());
  EXPECT_TRUE(ht == table_);
  for (int i = 0; i < arraysize(test_data); ++i) {
    int16 val = test_data[i];
    Table::const_iterator it = ht.find(val);
    ht.erase(it);
    EXPECT_EQ(ht.count(val), 0);
    EXPECT_TRUE(ht.find(val) == ht.end());
  }

  // Test erase(iterator, iterator)
  ht = table_;
  ht.set_deleted_key(kDelKey);
  EXPECT_TRUE(ht == table_);
  ht.erase(table_.begin(), table_.end());
  EXPECT_FALSE(ht == table_);
  EXPECT_EQ(ht.size(), 0);
}

}  // namespace


int main(int argc, char **argv) {
  // Tests are run via global constructors, so we have nothing to do.
  printf("\nSizeOf: dense_hashtable<int16> = %d\n",
         static_cast<int>(sizeof(Table)));
  printf("PASS.\n");
  return 0;
}