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 "v8.h"
  31
  32 #include "cctest.h"
  33 #include "factory.h"
  34
  35 namespace {
  36
  37 using namespace v8::internal;
  38
  39
  40 void CheckIterResultObject(Isolate* isolate,
  41                            Handle<JSObject> result,
  42                            Handle<Object> value,
  43                            bool done) {
  44   Handle<Object> value_object =
  45       Object::GetProperty(isolate, result, "value").ToHandleChecked();
  46   Handle<Object> done_object =
  47       Object::GetProperty(isolate, result, "done").ToHandleChecked();
  48
  49   CHECK_EQ(*value_object, *value);
  50   CHECK(done_object->IsBoolean());
  51   CHECK_EQ(done_object->BooleanValue(), done);
  52 }
  53
  54
  55 TEST(Set) {
  56   i::FLAG_harmony_collections = true;
  57
  58   LocalContext context;
  59   Isolate* isolate = CcTest::i_isolate();
  60   Factory* factory = isolate->factory();
  61   HandleScope scope(isolate);
  62   Handle<OrderedHashSet> ordered_set = factory->NewOrderedHashSet();
  63   CHECK_EQ(2, ordered_set->NumberOfBuckets());
  64   CHECK_EQ(0, ordered_set->NumberOfElements());
  65   CHECK_EQ(0, ordered_set->NumberOfDeletedElements());
  66
  67   Handle<JSSetIterator> value_iterator =
  68       JSSetIterator::Create(ordered_set, JSSetIterator::kKindValues);
  69   Handle<JSSetIterator> value_iterator_2 =
  70       JSSetIterator::Create(ordered_set, JSSetIterator::kKindValues);
  71
  72   Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize);
  73   Handle<JSObject> obj = factory->NewJSObjectFromMap(map);
  74   CHECK(!ordered_set->Contains(obj));
  75   ordered_set = OrderedHashSet::Add(ordered_set, obj);
  76   CHECK_EQ(1, ordered_set->NumberOfElements());
  77   CHECK(ordered_set->Contains(obj));
  78   ordered_set = OrderedHashSet::Remove(ordered_set, obj);
  79   CHECK_EQ(0, ordered_set->NumberOfElements());
  80   CHECK(!ordered_set->Contains(obj));
  81
  82   // Test for collisions/chaining
  83   Handle<JSObject> obj1 = factory->NewJSObjectFromMap(map);
  84   ordered_set = OrderedHashSet::Add(ordered_set, obj1);
  85   Handle<JSObject> obj2 = factory->NewJSObjectFromMap(map);
  86   ordered_set = OrderedHashSet::Add(ordered_set, obj2);
  87   Handle<JSObject> obj3 = factory->NewJSObjectFromMap(map);
  88   ordered_set = OrderedHashSet::Add(ordered_set, obj3);
  89   CHECK_EQ(3, ordered_set->NumberOfElements());
  90   CHECK(ordered_set->Contains(obj1));
  91   CHECK(ordered_set->Contains(obj2));
  92   CHECK(ordered_set->Contains(obj3));
  93
  94   // Test iteration
  95   CheckIterResultObject(
  96       isolate, JSSetIterator::Next(value_iterator), obj1, false);
  97   CheckIterResultObject(
  98       isolate, JSSetIterator::Next(value_iterator), obj2, false);
  99   CheckIterResultObject(
 100       isolate, JSSetIterator::Next(value_iterator), obj3, false);
 101   CheckIterResultObject(isolate,
 102                         JSSetIterator::Next(value_iterator),
 103                         factory->undefined_value(),
 104                         true);
 105
 106   // Test growth
 107   ordered_set = OrderedHashSet::Add(ordered_set, obj);
 108   Handle<JSObject> obj4 = factory->NewJSObjectFromMap(map);
 109   ordered_set = OrderedHashSet::Add(ordered_set, obj4);
 110   CHECK(ordered_set->Contains(obj));
 111   CHECK(ordered_set->Contains(obj1));
 112   CHECK(ordered_set->Contains(obj2));
 113   CHECK(ordered_set->Contains(obj3));
 114   CHECK(ordered_set->Contains(obj4));
 115   CHECK_EQ(5, ordered_set->NumberOfElements());
 116   CHECK_EQ(0, ordered_set->NumberOfDeletedElements());
 117   CHECK_EQ(4, ordered_set->NumberOfBuckets());
 118
 119   // Test iteration after growth
 120   CheckIterResultObject(
 121       isolate, JSSetIterator::Next(value_iterator_2), obj1, false);
 122   CheckIterResultObject(
 123       isolate, JSSetIterator::Next(value_iterator_2), obj2, false);
 124   CheckIterResultObject(
 125       isolate, JSSetIterator::Next(value_iterator_2), obj3, false);
 126   CheckIterResultObject(
 127       isolate, JSSetIterator::Next(value_iterator_2), obj, false);
 128   CheckIterResultObject(
 129       isolate, JSSetIterator::Next(value_iterator_2), obj4, false);
 130   CheckIterResultObject(isolate,
 131                         JSSetIterator::Next(value_iterator_2),
 132                         factory->undefined_value(),
 133                         true);
 134
 135   // Test shrinking
 136   ordered_set = OrderedHashSet::Remove(ordered_set, obj);
 137   ordered_set = OrderedHashSet::Remove(ordered_set, obj1);
 138   ordered_set = OrderedHashSet::Remove(ordered_set, obj2);
 139   ordered_set = OrderedHashSet::Remove(ordered_set, obj3);
 140   CHECK_EQ(1, ordered_set->NumberOfElements());
 141   CHECK_EQ(2, ordered_set->NumberOfBuckets());
 142 }
 143
 144
 145 TEST(Map) {
 146   i::FLAG_harmony_collections = true;
 147
 148   LocalContext context;
 149   Isolate* isolate = CcTest::i_isolate();
 150   Factory* factory = isolate->factory();
 151   HandleScope scope(isolate);
 152   Handle<OrderedHashMap> ordered_map = factory->NewOrderedHashMap();
 153   CHECK_EQ(2, ordered_map->NumberOfBuckets());
 154   CHECK_EQ(0, ordered_map->NumberOfElements());
 155   CHECK_EQ(0, ordered_map->NumberOfDeletedElements());
 156
 157   Handle<JSMapIterator> value_iterator =
 158       JSMapIterator::Create(ordered_map, JSMapIterator::kKindValues);
 159   Handle<JSMapIterator> key_iterator =
 160       JSMapIterator::Create(ordered_map, JSMapIterator::kKindKeys);
 161
 162   Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize);
 163   Handle<JSObject> obj = factory->NewJSObjectFromMap(map);
 164   Handle<JSObject> val = factory->NewJSObjectFromMap(map);
 165   CHECK(ordered_map->Lookup(obj)->IsTheHole());
 166   ordered_map = OrderedHashMap::Put(ordered_map, obj, val);
 167   CHECK_EQ(1, ordered_map->NumberOfElements());
 168   CHECK(ordered_map->Lookup(obj)->SameValue(*val));
 169   ordered_map = OrderedHashMap::Put(
 170       ordered_map, obj, factory->the_hole_value());
 171   CHECK_EQ(0, ordered_map->NumberOfElements());
 172   CHECK(ordered_map->Lookup(obj)->IsTheHole());
 173
 174   // Test for collisions/chaining
 175   Handle<JSObject> obj1 = factory->NewJSObjectFromMap(map);
 176   Handle<JSObject> obj2 = factory->NewJSObjectFromMap(map);
 177   Handle<JSObject> obj3 = factory->NewJSObjectFromMap(map);
 178   Handle<JSObject> val1 = factory->NewJSObjectFromMap(map);
 179   Handle<JSObject> val2 = factory->NewJSObjectFromMap(map);
 180   Handle<JSObject> val3 = factory->NewJSObjectFromMap(map);
 181   ordered_map = OrderedHashMap::Put(ordered_map, obj1, val1);
 182   ordered_map = OrderedHashMap::Put(ordered_map, obj2, val2);
 183   ordered_map = OrderedHashMap::Put(ordered_map, obj3, val3);
 184   CHECK_EQ(3, ordered_map->NumberOfElements());
 185   CHECK(ordered_map->Lookup(obj1)->SameValue(*val1));
 186   CHECK(ordered_map->Lookup(obj2)->SameValue(*val2));
 187   CHECK(ordered_map->Lookup(obj3)->SameValue(*val3));
 188
 189   // Test iteration
 190   CheckIterResultObject(
 191       isolate, JSMapIterator::Next(value_iterator), val1, false);
 192   CheckIterResultObject(
 193       isolate, JSMapIterator::Next(value_iterator), val2, false);
 194   CheckIterResultObject(
 195       isolate, JSMapIterator::Next(value_iterator), val3, false);
 196   CheckIterResultObject(isolate,
 197                         JSMapIterator::Next(value_iterator),
 198                         factory->undefined_value(),
 199                         true);
 200
 201   // Test growth
 202   ordered_map = OrderedHashMap::Put(ordered_map, obj, val);
 203   Handle<JSObject> obj4 = factory->NewJSObjectFromMap(map);
 204   Handle<JSObject> val4 = factory->NewJSObjectFromMap(map);
 205   ordered_map = OrderedHashMap::Put(ordered_map, obj4, val4);
 206   CHECK(ordered_map->Lookup(obj)->SameValue(*val));
 207   CHECK(ordered_map->Lookup(obj1)->SameValue(*val1));
 208   CHECK(ordered_map->Lookup(obj2)->SameValue(*val2));
 209   CHECK(ordered_map->Lookup(obj3)->SameValue(*val3));
 210   CHECK(ordered_map->Lookup(obj4)->SameValue(*val4));
 211   CHECK_EQ(5, ordered_map->NumberOfElements());
 212   CHECK_EQ(4, ordered_map->NumberOfBuckets());
 213
 214   // Test iteration after growth
 215   CheckIterResultObject(
 216       isolate, JSMapIterator::Next(key_iterator), obj1, false);
 217   CheckIterResultObject(
 218       isolate, JSMapIterator::Next(key_iterator), obj2, false);
 219   CheckIterResultObject(
 220       isolate, JSMapIterator::Next(key_iterator), obj3, false);
 221   CheckIterResultObject(
 222       isolate, JSMapIterator::Next(key_iterator), obj, false);
 223   CheckIterResultObject(
 224       isolate, JSMapIterator::Next(key_iterator), obj4, false);
 225   CheckIterResultObject(isolate,
 226                         JSMapIterator::Next(key_iterator),
 227                         factory->undefined_value(),
 228                         true);
 229
 230   // Test shrinking
 231   ordered_map = OrderedHashMap::Put(
 232       ordered_map, obj, factory->the_hole_value());
 233   ordered_map = OrderedHashMap::Put(
 234       ordered_map, obj1, factory->the_hole_value());
 235   ordered_map = OrderedHashMap::Put(
 236       ordered_map, obj2, factory->the_hole_value());
 237   ordered_map = OrderedHashMap::Put(
 238       ordered_map, obj3, factory->the_hole_value());
 239   CHECK_EQ(1, ordered_map->NumberOfElements());
 240   CHECK_EQ(2, ordered_map->NumberOfBuckets());
 241 }
 242
 243
 244 }