src/v8/test/cctest/test-ordered-hash-table.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #include <stdlib.h>
  29
  30 #include "src/v8.h"
  31
  32 #include "src/factory.h"
  33 #include "test/cctest/cctest.h"
  34
  35 namespace {
  36
  37 using namespace v8::internal;
  38
  39
  40 TEST(Set) {
  41   LocalContext context;
  42   Isolate* isolate = CcTest::i_isolate();
  43   Factory* factory = isolate->factory();
  44   HandleScope scope(isolate);
  45   Handle<OrderedHashSet> ordered_set = factory->NewOrderedHashSet();
  46   CHECK_EQ(2, ordered_set->NumberOfBuckets());
  47   CHECK_EQ(0, ordered_set->NumberOfElements());
  48   CHECK_EQ(0, ordered_set->NumberOfDeletedElements());
  49
  50   Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize);
  51   Handle<JSObject> obj = factory->NewJSObjectFromMap(map);
  52   CHECK(!ordered_set->Contains(obj));
  53   ordered_set = OrderedHashSet::Add(ordered_set, obj);
  54   CHECK_EQ(1, ordered_set->NumberOfElements());
  55   CHECK(ordered_set->Contains(obj));
  56   bool was_present = false;
  57   ordered_set = OrderedHashSet::Remove(ordered_set, obj, &was_present);
  58   CHECK(was_present);
  59   CHECK_EQ(0, ordered_set->NumberOfElements());
  60   CHECK(!ordered_set->Contains(obj));
  61
  62   // Removing a not-present object should set was_present to false.
  63   ordered_set = OrderedHashSet::Remove(ordered_set, obj, &was_present);
  64   CHECK(!was_present);
  65
  66   // Test for collisions/chaining
  67   Handle<JSObject> obj1 = factory->NewJSObjectFromMap(map);
  68   ordered_set = OrderedHashSet::Add(ordered_set, obj1);
  69   Handle<JSObject> obj2 = factory->NewJSObjectFromMap(map);
  70   ordered_set = OrderedHashSet::Add(ordered_set, obj2);
  71   Handle<JSObject> obj3 = factory->NewJSObjectFromMap(map);
  72   ordered_set = OrderedHashSet::Add(ordered_set, obj3);
  73   CHECK_EQ(3, ordered_set->NumberOfElements());
  74   CHECK(ordered_set->Contains(obj1));
  75   CHECK(ordered_set->Contains(obj2));
  76   CHECK(ordered_set->Contains(obj3));
  77
  78   // Test growth
  79   ordered_set = OrderedHashSet::Add(ordered_set, obj);
  80   Handle<JSObject> obj4 = factory->NewJSObjectFromMap(map);
  81   ordered_set = OrderedHashSet::Add(ordered_set, obj4);
  82   CHECK(ordered_set->Contains(obj));
  83   CHECK(ordered_set->Contains(obj1));
  84   CHECK(ordered_set->Contains(obj2));
  85   CHECK(ordered_set->Contains(obj3));
  86   CHECK(ordered_set->Contains(obj4));
  87   CHECK_EQ(5, ordered_set->NumberOfElements());
  88   CHECK_EQ(0, ordered_set->NumberOfDeletedElements());
  89   CHECK_EQ(4, ordered_set->NumberOfBuckets());
  90
  91   // Test shrinking
  92   ordered_set = OrderedHashSet::Remove(ordered_set, obj, &was_present);
  93   CHECK(was_present);
  94   ordered_set = OrderedHashSet::Remove(ordered_set, obj1, &was_present);
  95   CHECK(was_present);
  96   ordered_set = OrderedHashSet::Remove(ordered_set, obj2, &was_present);
  97   CHECK(was_present);
  98   ordered_set = OrderedHashSet::Remove(ordered_set, obj3, &was_present);
  99   CHECK(was_present);
 100   CHECK_EQ(1, ordered_set->NumberOfElements());
 101   CHECK_EQ(2, ordered_set->NumberOfBuckets());
 102 }
 103
 104
 105 TEST(Map) {
 106   LocalContext context;
 107   Isolate* isolate = CcTest::i_isolate();
 108   Factory* factory = isolate->factory();
 109   HandleScope scope(isolate);
 110   Handle<OrderedHashMap> ordered_map = factory->NewOrderedHashMap();
 111   CHECK_EQ(2, ordered_map->NumberOfBuckets());
 112   CHECK_EQ(0, ordered_map->NumberOfElements());
 113   CHECK_EQ(0, ordered_map->NumberOfDeletedElements());
 114
 115   Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize);
 116   Handle<JSObject> obj = factory->NewJSObjectFromMap(map);
 117   Handle<JSObject> val = factory->NewJSObjectFromMap(map);
 118   CHECK(ordered_map->Lookup(obj)->IsTheHole());
 119   ordered_map = OrderedHashMap::Put(ordered_map, obj, val);
 120   CHECK_EQ(1, ordered_map->NumberOfElements());
 121   Object* lookup = ordered_map->Lookup(obj);
 122   CHECK(lookup->SameValue(*val));
 123   bool was_present = false;
 124   ordered_map = OrderedHashMap::Remove(ordered_map, obj, &was_present);
 125   CHECK(was_present);
 126   CHECK_EQ(0, ordered_map->NumberOfElements());
 127   CHECK(ordered_map->Lookup(obj)->IsTheHole());
 128
 129   // Test for collisions/chaining
 130   Handle<JSObject> obj1 = factory->NewJSObjectFromMap(map);
 131   Handle<JSObject> obj2 = factory->NewJSObjectFromMap(map);
 132   Handle<JSObject> obj3 = factory->NewJSObjectFromMap(map);
 133   Handle<JSObject> val1 = factory->NewJSObjectFromMap(map);
 134   Handle<JSObject> val2 = factory->NewJSObjectFromMap(map);
 135   Handle<JSObject> val3 = factory->NewJSObjectFromMap(map);
 136   ordered_map = OrderedHashMap::Put(ordered_map, obj1, val1);
 137   ordered_map = OrderedHashMap::Put(ordered_map, obj2, val2);
 138   ordered_map = OrderedHashMap::Put(ordered_map, obj3, val3);
 139   CHECK_EQ(3, ordered_map->NumberOfElements());
 140   lookup = ordered_map->Lookup(obj1);
 141   CHECK(lookup->SameValue(*val1));
 142   lookup = ordered_map->Lookup(obj2);
 143   CHECK(lookup->SameValue(*val2));
 144   lookup = ordered_map->Lookup(obj3);
 145   CHECK(lookup->SameValue(*val3));
 146
 147   // Test growth
 148   ordered_map = OrderedHashMap::Put(ordered_map, obj, val);
 149   Handle<JSObject> obj4 = factory->NewJSObjectFromMap(map);
 150   Handle<JSObject> val4 = factory->NewJSObjectFromMap(map);
 151   ordered_map = OrderedHashMap::Put(ordered_map, obj4, val4);
 152   lookup = ordered_map->Lookup(obj);
 153   CHECK(lookup->SameValue(*val));
 154   lookup = ordered_map->Lookup(obj1);
 155   CHECK(lookup->SameValue(*val1));
 156   lookup = ordered_map->Lookup(obj2);
 157   CHECK(lookup->SameValue(*val2));
 158   lookup = ordered_map->Lookup(obj3);
 159   CHECK(lookup->SameValue(*val3));
 160   lookup = ordered_map->Lookup(obj4);
 161   CHECK(lookup->SameValue(*val4));
 162   CHECK_EQ(5, ordered_map->NumberOfElements());
 163   CHECK_EQ(4, ordered_map->NumberOfBuckets());
 164
 165   // Test shrinking
 166   ordered_map = OrderedHashMap::Remove(ordered_map, obj, &was_present);
 167   CHECK(was_present);
 168   ordered_map = OrderedHashMap::Remove(ordered_map, obj1, &was_present);
 169   CHECK(was_present);
 170   ordered_map = OrderedHashMap::Remove(ordered_map, obj2, &was_present);
 171   CHECK(was_present);
 172   ordered_map = OrderedHashMap::Remove(ordered_map, obj3, &was_present);
 173   CHECK(was_present);
 174   CHECK_EQ(1, ordered_map->NumberOfElements());
 175   CHECK_EQ(2, ordered_map->NumberOfBuckets());
 176 }
 177
 178
 179 }