src/collection.js

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 var $getHash;
   6 var $getExistingHash;
   7 var $mapSet;
   8 var $mapHas;
   9 var $mapDelete;
  10 var $setAdd;
  11 var $setHas;
  12 var $setDelete;
  13 var $mapFromArray;
  14 var $setFromArray;
  15
  16 (function(global, utils) {
  17 "use strict";
  18
  19 %CheckIsBootstrapping();
  20
  21 // -------------------------------------------------------------------
  22 // Imports
  23
  24 var GlobalMap = global.Map;
  25 var GlobalObject = global.Object;
  26 var GlobalSet = global.Set;
  27 var IntRandom;
  28
  29 utils.Import(function(from) {
  30   IntRandom = from.IntRandom;
  31 });
  32
  33 var NumberIsNaN;
  34
  35 utils.Import(function(from) {
  36   NumberIsNaN = from.NumberIsNaN;
  37 });
  38
  39 // -------------------------------------------------------------------
  40
  41 function HashToEntry(table, hash, numBuckets) {
  42   var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets);
  43   return ORDERED_HASH_TABLE_BUCKET_AT(table, bucket);
  44 }
  45 %SetForceInlineFlag(HashToEntry);
  46
  47
  48 function SetFindEntry(table, numBuckets, key, hash) {
  49   var entry = HashToEntry(table, hash, numBuckets);
  50   if (entry === NOT_FOUND) return entry;
  51   var candidate = ORDERED_HASH_SET_KEY_AT(table, entry, numBuckets);
  52   if (key === candidate) return entry;
  53   var keyIsNaN = NumberIsNaN(key);
  54   while (true) {
  55     if (keyIsNaN && NumberIsNaN(candidate)) {
  56       return entry;
  57     }
  58     entry = ORDERED_HASH_SET_CHAIN_AT(table, entry, numBuckets);
  59     if (entry === NOT_FOUND) return entry;
  60     candidate = ORDERED_HASH_SET_KEY_AT(table, entry, numBuckets);
  61     if (key === candidate) return entry;
  62   }
  63   return NOT_FOUND;
  64 }
  65 %SetForceInlineFlag(SetFindEntry);
  66
  67
  68 function MapFindEntry(table, numBuckets, key, hash) {
  69   var entry = HashToEntry(table, hash, numBuckets);
  70   if (entry === NOT_FOUND) return entry;
  71   var candidate = ORDERED_HASH_MAP_KEY_AT(table, entry, numBuckets);
  72   if (key === candidate) return entry;
  73   var keyIsNaN = NumberIsNaN(key);
  74   while (true) {
  75     if (keyIsNaN && NumberIsNaN(candidate)) {
  76       return entry;
  77     }
  78     entry = ORDERED_HASH_MAP_CHAIN_AT(table, entry, numBuckets);
  79     if (entry === NOT_FOUND) return entry;
  80     candidate = ORDERED_HASH_MAP_KEY_AT(table, entry, numBuckets);
  81     if (key === candidate) return entry;
  82   }
  83   return NOT_FOUND;
  84 }
  85 %SetForceInlineFlag(MapFindEntry);
  86
  87
  88 function ComputeIntegerHash(key, seed) {
  89   var hash = key;
  90   hash = hash ^ seed;
  91   hash = ~hash + (hash << 15);  // hash = (hash << 15) - hash - 1;
  92   hash = hash ^ (hash >>> 12);
  93   hash = hash + (hash << 2);
  94   hash = hash ^ (hash >>> 4);
  95   hash = (hash * 2057) | 0;  // hash = (hash + (hash << 3)) + (hash << 11);
  96   hash = hash ^ (hash >>> 16);
  97   return hash & 0x3fffffff;
  98 }
  99 %SetForceInlineFlag(ComputeIntegerHash);
 100
 101 var hashCodeSymbol = GLOBAL_PRIVATE("hash_code_symbol");
 102
 103 function GetExistingHash(key) {
 104   if (%_IsSmi(key)) {
 105     return ComputeIntegerHash(key, 0);
 106   }
 107   if (IS_STRING(key)) {
 108     var field = %_StringGetRawHashField(key);
 109     if ((field & 1 /* Name::kHashNotComputedMask */) === 0) {
 110       return field >>> 2 /* Name::kHashShift */;
 111     }
 112   } else if (IS_SPEC_OBJECT(key) && !%_IsJSProxy(key) && !IS_GLOBAL(key)) {
 113     var hash = GET_PRIVATE(key, hashCodeSymbol);
 114     return hash;
 115   }
 116   return %GenericHash(key);
 117 }
 118 %SetForceInlineFlag(GetExistingHash);
 119
 120
 121 function GetHash(key) {
 122   var hash = GetExistingHash(key);
 123   if (IS_UNDEFINED(hash)) {
 124     hash = IntRandom() | 0;
 125     if (hash === 0) hash = 1;
 126     SET_PRIVATE(key, hashCodeSymbol, hash);
 127   }
 128   return hash;
 129 }
 130 %SetForceInlineFlag(GetHash);
 131
 132
 133 // -------------------------------------------------------------------
 134 // Harmony Set
 135
 136 function SetConstructor(iterable) {
 137   if (!%_IsConstructCall()) {
 138     throw MakeTypeError(kConstructorNotFunction, "Set");
 139   }
 140
 141   %_SetInitialize(this);
 142
 143   if (!IS_NULL_OR_UNDEFINED(iterable)) {
 144     var adder = this.add;
 145     if (!IS_SPEC_FUNCTION(adder)) {
 146       throw MakeTypeError(kPropertyNotFunction, 'add', this);
 147     }
 148
 149     for (var value of iterable) {
 150       %_CallFunction(this, value, adder);
 151     }
 152   }
 153 }
 154
 155
 156 function SetAdd(key) {
 157   if (!IS_SET(this)) {
 158     throw MakeTypeError(kIncompatibleMethodReceiver, 'Set.prototype.add', this);
 159   }
 160   // Normalize -0 to +0 as required by the spec.
 161   // Even though we use SameValueZero as the comparison for the keys we don't
 162   // want to ever store -0 as the key since the key is directly exposed when
 163   // doing iteration.
 164   if (key === 0) {
 165     key = 0;
 166   }
 167   var table = %_JSCollectionGetTable(this);
 168   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
 169   var hash = GetHash(key);
 170   if (SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND) return this;
 171
 172   var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
 173   var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table);
 174   var capacity = numBuckets << 1;
 175   if ((nof + nod) >= capacity) {
 176     // Need to grow, bail out to runtime.
 177     %SetGrow(this);
 178     // Re-load state from the grown backing store.
 179     table = %_JSCollectionGetTable(this);
 180     numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
 181     nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
 182     nod = ORDERED_HASH_TABLE_DELETED_COUNT(table);
 183   }
 184   var entry = nof + nod;
 185   var index = ORDERED_HASH_SET_ENTRY_TO_INDEX(entry, numBuckets);
 186   var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets);
 187   var chainEntry = ORDERED_HASH_TABLE_BUCKET_AT(table, bucket);
 188   ORDERED_HASH_TABLE_SET_BUCKET_AT(table, bucket, entry);
 189   ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof + 1);
 190   FIXED_ARRAY_SET(table, index, key);
 191   FIXED_ARRAY_SET_SMI(table, index + 1, chainEntry);
 192   return this;
 193 }
 194
 195
 196 function SetHas(key) {
 197   if (!IS_SET(this)) {
 198     throw MakeTypeError(kIncompatibleMethodReceiver, 'Set.prototype.has', this);
 199   }
 200   var table = %_JSCollectionGetTable(this);
 201   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
 202   var hash = GetExistingHash(key);
 203   if (IS_UNDEFINED(hash)) return false;
 204   return SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND;
 205 }
 206
 207
 208 function SetDelete(key) {
 209   if (!IS_SET(this)) {
 210     throw MakeTypeError(kIncompatibleMethodReceiver,
 211                         'Set.prototype.delete', this);
 212   }
 213   var table = %_JSCollectionGetTable(this);
 214   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
 215   var hash = GetExistingHash(key);
 216   if (IS_UNDEFINED(hash)) return false;
 217   var entry = SetFindEntry(table, numBuckets, key, hash);
 218   if (entry === NOT_FOUND) return false;
 219
 220   var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table) - 1;
 221   var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table) + 1;
 222   var index = ORDERED_HASH_SET_ENTRY_TO_INDEX(entry, numBuckets);
 223   FIXED_ARRAY_SET(table, index, %_TheHole());
 224   ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof);
 225   ORDERED_HASH_TABLE_SET_DELETED_COUNT(table, nod);
 226   if (nof < (numBuckets >>> 1)) %SetShrink(this);
 227   return true;
 228 }
 229
 230
 231 function SetGetSize() {
 232   if (!IS_SET(this)) {
 233     throw MakeTypeError(kIncompatibleMethodReceiver,
 234                         'Set.prototype.size', this);
 235   }
 236   var table = %_JSCollectionGetTable(this);
 237   return ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
 238 }
 239
 240
 241 function SetClearJS() {
 242   if (!IS_SET(this)) {
 243     throw MakeTypeError(kIncompatibleMethodReceiver,
 244                         'Set.prototype.clear', this);
 245   }
 246   %_SetClear(this);
 247 }
 248
 249
 250 function SetForEach(f, receiver) {
 251   if (!IS_SET(this)) {
 252     throw MakeTypeError(kIncompatibleMethodReceiver,
 253                         'Set.prototype.forEach', this);
 254   }
 255
 256   if (!IS_SPEC_FUNCTION(f)) throw MakeTypeError(kCalledNonCallable, f);
 257   var needs_wrapper = false;
 258   if (IS_NULL(receiver)) {
 259     if (%IsSloppyModeFunction(f)) receiver = UNDEFINED;
 260   } else if (!IS_UNDEFINED(receiver)) {
 261     needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
 262   }
 263
 264   var iterator = new SetIterator(this, ITERATOR_KIND_VALUES);
 265   var key;
 266   var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
 267   var value_array = [UNDEFINED];
 268   while (%SetIteratorNext(iterator, value_array)) {
 269     if (stepping) %DebugPrepareStepInIfStepping(f);
 270     key = value_array[0];
 271     var new_receiver = needs_wrapper ? TO_OBJECT(receiver) : receiver;
 272     %_CallFunction(new_receiver, key, key, this, f);
 273   }
 274 }
 275
 276 // -------------------------------------------------------------------
 277
 278 %SetCode(GlobalSet, SetConstructor);
 279 %FunctionSetLength(GlobalSet, 0);
 280 %FunctionSetPrototype(GlobalSet, new GlobalObject());
 281 %AddNamedProperty(GlobalSet.prototype, "constructor", GlobalSet, DONT_ENUM);
 282 %AddNamedProperty(GlobalSet.prototype, symbolToStringTag, "Set",
 283                   DONT_ENUM | READ_ONLY);
 284
 285 %FunctionSetLength(SetForEach, 1);
 286
 287 // Set up the non-enumerable functions on the Set prototype object.
 288 utils.InstallGetter(GlobalSet.prototype, "size", SetGetSize);
 289 utils.InstallFunctions(GlobalSet.prototype, DONT_ENUM, [
 290   "add", SetAdd,
 291   "has", SetHas,
 292   "delete", SetDelete,
 293   "clear", SetClearJS,
 294   "forEach", SetForEach
 295 ]);
 296
 297
 298 // -------------------------------------------------------------------
 299 // Harmony Map
 300
 301 function MapConstructor(iterable) {
 302   if (!%_IsConstructCall()) {
 303     throw MakeTypeError(kConstructorNotFunction, "Map");
 304   }
 305
 306   %_MapInitialize(this);
 307
 308   if (!IS_NULL_OR_UNDEFINED(iterable)) {
 309     var adder = this.set;
 310     if (!IS_SPEC_FUNCTION(adder)) {
 311       throw MakeTypeError(kPropertyNotFunction, 'set', this);
 312     }
 313
 314     for (var nextItem of iterable) {
 315       if (!IS_SPEC_OBJECT(nextItem)) {
 316         throw MakeTypeError(kIteratorValueNotAnObject, nextItem);
 317       }
 318       %_CallFunction(this, nextItem[0], nextItem[1], adder);
 319     }
 320   }
 321 }
 322
 323
 324 function MapGet(key) {
 325   if (!IS_MAP(this)) {
 326     throw MakeTypeError(kIncompatibleMethodReceiver,
 327                         'Map.prototype.get', this);
 328   }
 329   var table = %_JSCollectionGetTable(this);
 330   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
 331   var hash = GetExistingHash(key);
 332   if (IS_UNDEFINED(hash)) return UNDEFINED;
 333   var entry = MapFindEntry(table, numBuckets, key, hash);
 334   if (entry === NOT_FOUND) return UNDEFINED;
 335   return ORDERED_HASH_MAP_VALUE_AT(table, entry, numBuckets);
 336 }
 337
 338
 339 function MapSet(key, value) {
 340   if (!IS_MAP(this)) {
 341     throw MakeTypeError(kIncompatibleMethodReceiver,
 342                         'Map.prototype.set', this);
 343   }
 344   // Normalize -0 to +0 as required by the spec.
 345   // Even though we use SameValueZero as the comparison for the keys we don't
 346   // want to ever store -0 as the key since the key is directly exposed when
 347   // doing iteration.
 348   if (key === 0) {
 349     key = 0;
 350   }
 351
 352   var table = %_JSCollectionGetTable(this);
 353   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
 354   var hash = GetHash(key);
 355   var entry = MapFindEntry(table, numBuckets, key, hash);
 356   if (entry !== NOT_FOUND) {
 357     var existingIndex = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets);
 358     FIXED_ARRAY_SET(table, existingIndex + 1, value);
 359     return this;
 360   }
 361
 362   var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
 363   var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table);
 364   var capacity = numBuckets << 1;
 365   if ((nof + nod) >= capacity) {
 366     // Need to grow, bail out to runtime.
 367     %MapGrow(this);
 368     // Re-load state from the grown backing store.
 369     table = %_JSCollectionGetTable(this);
 370     numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
 371     nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
 372     nod = ORDERED_HASH_TABLE_DELETED_COUNT(table);
 373   }
 374   entry = nof + nod;
 375   var index = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets);
 376   var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets);
 377   var chainEntry = ORDERED_HASH_TABLE_BUCKET_AT(table, bucket);
 378   ORDERED_HASH_TABLE_SET_BUCKET_AT(table, bucket, entry);
 379   ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof + 1);
 380   FIXED_ARRAY_SET(table, index, key);
 381   FIXED_ARRAY_SET(table, index + 1, value);
 382   FIXED_ARRAY_SET(table, index + 2, chainEntry);
 383   return this;
 384 }
 385
 386
 387 function MapHas(key) {
 388   if (!IS_MAP(this)) {
 389     throw MakeTypeError(kIncompatibleMethodReceiver,
 390                         'Map.prototype.has', this);
 391   }
 392   var table = %_JSCollectionGetTable(this);
 393   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
 394   var hash = GetHash(key);
 395   return MapFindEntry(table, numBuckets, key, hash) !== NOT_FOUND;
 396 }
 397
 398
 399 function MapDelete(key) {
 400   if (!IS_MAP(this)) {
 401     throw MakeTypeError(kIncompatibleMethodReceiver,
 402                         'Map.prototype.delete', this);
 403   }
 404   var table = %_JSCollectionGetTable(this);
 405   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
 406   var hash = GetHash(key);
 407   var entry = MapFindEntry(table, numBuckets, key, hash);
 408   if (entry === NOT_FOUND) return false;
 409
 410   var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table) - 1;
 411   var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table) + 1;
 412   var index = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets);
 413   FIXED_ARRAY_SET(table, index, %_TheHole());
 414   FIXED_ARRAY_SET(table, index + 1, %_TheHole());
 415   ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof);
 416   ORDERED_HASH_TABLE_SET_DELETED_COUNT(table, nod);
 417   if (nof < (numBuckets >>> 1)) %MapShrink(this);
 418   return true;
 419 }
 420
 421
 422 function MapGetSize() {
 423   if (!IS_MAP(this)) {
 424     throw MakeTypeError(kIncompatibleMethodReceiver,
 425                         'Map.prototype.size', this);
 426   }
 427   var table = %_JSCollectionGetTable(this);
 428   return ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
 429 }
 430
 431
 432 function MapClearJS() {
 433   if (!IS_MAP(this)) {
 434     throw MakeTypeError(kIncompatibleMethodReceiver,
 435                         'Map.prototype.clear', this);
 436   }
 437   %_MapClear(this);
 438 }
 439
 440
 441 function MapForEach(f, receiver) {
 442   if (!IS_MAP(this)) {
 443     throw MakeTypeError(kIncompatibleMethodReceiver,
 444                         'Map.prototype.forEach', this);
 445   }
 446
 447   if (!IS_SPEC_FUNCTION(f)) throw MakeTypeError(kCalledNonCallable, f);
 448   var needs_wrapper = false;
 449   if (IS_NULL(receiver)) {
 450     if (%IsSloppyModeFunction(f)) receiver = UNDEFINED;
 451   } else if (!IS_UNDEFINED(receiver)) {
 452     needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
 453   }
 454
 455   var iterator = new MapIterator(this, ITERATOR_KIND_ENTRIES);
 456   var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
 457   var value_array = [UNDEFINED, UNDEFINED];
 458   while (%MapIteratorNext(iterator, value_array)) {
 459     if (stepping) %DebugPrepareStepInIfStepping(f);
 460     var new_receiver = needs_wrapper ? TO_OBJECT(receiver) : receiver;
 461     %_CallFunction(new_receiver, value_array[1], value_array[0], this, f);
 462   }
 463 }
 464
 465 // -------------------------------------------------------------------
 466
 467 %SetCode(GlobalMap, MapConstructor);
 468 %FunctionSetLength(GlobalMap, 0);
 469 %FunctionSetPrototype(GlobalMap, new GlobalObject());
 470 %AddNamedProperty(GlobalMap.prototype, "constructor", GlobalMap, DONT_ENUM);
 471 %AddNamedProperty(
 472     GlobalMap.prototype, symbolToStringTag, "Map", DONT_ENUM | READ_ONLY);
 473
 474 %FunctionSetLength(MapForEach, 1);
 475
 476 // Set up the non-enumerable functions on the Map prototype object.
 477 utils.InstallGetter(GlobalMap.prototype, "size", MapGetSize);
 478 utils.InstallFunctions(GlobalMap.prototype, DONT_ENUM, [
 479   "get", MapGet,
 480   "set", MapSet,
 481   "has", MapHas,
 482   "delete", MapDelete,
 483   "clear", MapClearJS,
 484   "forEach", MapForEach
 485 ]);
 486
 487 // Expose to the global scope.
 488 $getHash = GetHash;
 489 $getExistingHash = GetExistingHash;
 490 $mapGet = MapGet;
 491 $mapSet = MapSet;
 492 $mapHas = MapHas;
 493 $mapDelete = MapDelete;
 494 $setAdd = SetAdd;
 495 $setHas = SetHas;
 496 $setDelete = SetDelete;
 497
 498 $mapFromArray = function(array) {
 499   var map = new GlobalMap;
 500   var length = array.length;
 501   for (var i = 0; i < length; i += 2) {
 502     var key = array[i];
 503     var value = array[i + 1];
 504     %_CallFunction(map, key, value, MapSet);
 505   }
 506   return map;
 507 };
 508
 509 $setFromArray = function(array) {
 510   var set = new GlobalSet;
 511   var length = array.length;
 512   for (var i = 0; i < length; ++i) {
 513     %_CallFunction(set, array[i], SetAdd);
 514   }
 515   return set;
 516 };
 517
 518 })