OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 "use strict"; | 5 "use strict"; |
6 | 6 |
7 // This file relies on the fact that the following declaration has been made | 7 // This file relies on the fact that the following declaration has been made |
8 // in runtime.js: | 8 // in runtime.js: |
9 // var $Array = global.Array; | 9 // var $Array = global.Array; |
10 | 10 |
11 var $Set = global.Set; | 11 var $Set = global.Set; |
12 var $Map = global.Map; | 12 var $Map = global.Map; |
13 | 13 |
14 | 14 |
| 15 // Used by harmony-templates.js |
| 16 var $MapGet; |
| 17 var $MapSet; |
| 18 |
| 19 |
| 20 (function() { |
| 21 |
| 22 |
| 23 function HashToEntry(table, hash, numBuckets) { |
| 24 var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets); |
| 25 return ORDERED_HASH_TABLE_BUCKET_AT(table, bucket); |
| 26 } |
| 27 %SetInlineBuiltinFlag(HashToEntry); |
| 28 |
| 29 |
| 30 function SetFindEntry(table, numBuckets, key, hash) { |
| 31 var keyIsNaN = IS_NUMBER(key) && NUMBER_IS_NAN(key); |
| 32 for (var entry = HashToEntry(table, hash, numBuckets); |
| 33 entry !== NOT_FOUND; |
| 34 entry = ORDERED_HASH_SET_CHAIN_AT(table, entry, numBuckets)) { |
| 35 var candidate = ORDERED_HASH_SET_KEY_AT(table, entry, numBuckets); |
| 36 if (key === candidate) { |
| 37 return entry; |
| 38 } |
| 39 if (keyIsNaN && IS_NUMBER(candidate) && NUMBER_IS_NAN(candidate)) { |
| 40 return entry; |
| 41 } |
| 42 } |
| 43 return NOT_FOUND; |
| 44 } |
| 45 %SetInlineBuiltinFlag(SetFindEntry); |
| 46 |
| 47 |
| 48 function MapFindEntry(table, numBuckets, key, hash) { |
| 49 var keyIsNaN = IS_NUMBER(key) && NUMBER_IS_NAN(key); |
| 50 for (var entry = HashToEntry(table, hash, numBuckets); |
| 51 entry !== NOT_FOUND; |
| 52 entry = ORDERED_HASH_MAP_CHAIN_AT(table, entry, numBuckets)) { |
| 53 var candidate = ORDERED_HASH_MAP_KEY_AT(table, entry, numBuckets); |
| 54 if (key === candidate) { |
| 55 return entry; |
| 56 } |
| 57 if (keyIsNaN && IS_NUMBER(candidate) && NUMBER_IS_NAN(candidate)) { |
| 58 return entry; |
| 59 } |
| 60 } |
| 61 return NOT_FOUND; |
| 62 } |
| 63 %SetInlineBuiltinFlag(MapFindEntry); |
| 64 |
| 65 |
| 66 function ComputeIntegerHash(key, seed) { |
| 67 var hash = key; |
| 68 hash = hash ^ seed; |
| 69 hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1; |
| 70 hash = hash ^ (hash >>> 12); |
| 71 hash = hash + (hash << 2); |
| 72 hash = hash ^ (hash >>> 4); |
| 73 hash = (hash * 2057) | 0; // hash = (hash + (hash << 3)) + (hash << 11); |
| 74 hash = hash ^ (hash >>> 16); |
| 75 return hash; |
| 76 } |
| 77 %SetInlineBuiltinFlag(ComputeIntegerHash); |
| 78 |
| 79 |
| 80 function GetHash(key) { |
| 81 if (%_IsSmi(key)) { |
| 82 return ComputeIntegerHash(key, 0); |
| 83 } |
| 84 if (IS_STRING(key)) { |
| 85 var field = %_StringGetRawHashField(key); |
| 86 if ((field & 1 /* Name::kHashNotComputedMask */) === 0) { |
| 87 return field >>> 2 /* Name::kHashShift */; |
| 88 } |
| 89 } |
| 90 return %GenericHash(key); |
| 91 } |
| 92 %SetInlineBuiltinFlag(GetHash); |
| 93 |
| 94 |
15 // ------------------------------------------------------------------- | 95 // ------------------------------------------------------------------- |
16 // Harmony Set | 96 // Harmony Set |
17 | 97 |
18 function SetConstructor(iterable) { | 98 function SetConstructor(iterable) { |
19 if (!%_IsConstructCall()) { | 99 if (!%_IsConstructCall()) { |
20 throw MakeTypeError('constructor_not_function', ['Set']); | 100 throw MakeTypeError('constructor_not_function', ['Set']); |
21 } | 101 } |
22 | 102 |
23 %_SetInitialize(this); | 103 %_SetInitialize(this); |
24 | 104 |
25 if (!IS_NULL_OR_UNDEFINED(iterable)) { | 105 if (!IS_NULL_OR_UNDEFINED(iterable)) { |
26 var adder = this.add; | 106 var adder = this.add; |
27 if (!IS_SPEC_FUNCTION(adder)) { | 107 if (!IS_SPEC_FUNCTION(adder)) { |
28 throw MakeTypeError('property_not_function', ['add', this]); | 108 throw MakeTypeError('property_not_function', ['add', this]); |
29 } | 109 } |
30 | 110 |
31 for (var value of iterable) { | 111 for (var value of iterable) { |
32 %_CallFunction(this, value, adder); | 112 %_CallFunction(this, value, adder); |
33 } | 113 } |
34 } | 114 } |
35 } | 115 } |
36 | 116 |
37 | 117 |
38 function SetAddJS(key) { | 118 function SetAdd(key) { |
39 if (!IS_SET(this)) { | 119 if (!IS_SET(this)) { |
40 throw MakeTypeError('incompatible_method_receiver', | 120 throw MakeTypeError('incompatible_method_receiver', |
41 ['Set.prototype.add', this]); | 121 ['Set.prototype.add', this]); |
42 } | 122 } |
43 // Normalize -0 to +0 as required by the spec. | 123 // Normalize -0 to +0 as required by the spec. |
44 // Even though we use SameValueZero as the comparison for the keys we don't | 124 // Even though we use SameValueZero as the comparison for the keys we don't |
45 // want to ever store -0 as the key since the key is directly exposed when | 125 // want to ever store -0 as the key since the key is directly exposed when |
46 // doing iteration. | 126 // doing iteration. |
47 if (key === 0) { | 127 if (key === 0) { |
48 key = 0; | 128 key = 0; |
49 } | 129 } |
50 return %_SetAdd(this, key); | 130 var table = %_JSCollectionGetTable(this); |
| 131 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); |
| 132 var hash = GetHash(key); |
| 133 if (SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND) return this; |
| 134 |
| 135 var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table); |
| 136 var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table); |
| 137 var capacity = numBuckets << 1; |
| 138 if ((nof + nod) >= capacity) { |
| 139 // Need to grow, bail out to runtime. |
| 140 %SetGrow(this); |
| 141 // Re-load state from the grown backing store. |
| 142 table = %_JSCollectionGetTable(this); |
| 143 numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); |
| 144 nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table); |
| 145 nod = ORDERED_HASH_TABLE_DELETED_COUNT(table); |
| 146 } |
| 147 var entry = nof + nod; |
| 148 var index = ORDERED_HASH_SET_ENTRY_TO_INDEX(entry, numBuckets); |
| 149 var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets); |
| 150 var chainEntry = ORDERED_HASH_TABLE_BUCKET_AT(table, bucket); |
| 151 ORDERED_HASH_TABLE_SET_BUCKET_AT(table, bucket, entry); |
| 152 ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof + 1); |
| 153 FIXED_ARRAY_SET(table, index, key); |
| 154 FIXED_ARRAY_SET_SMI(table, index + 1, chainEntry); |
| 155 return this; |
51 } | 156 } |
52 | 157 |
53 | 158 |
54 function SetHasJS(key) { | 159 function SetHas(key) { |
55 if (!IS_SET(this)) { | 160 if (!IS_SET(this)) { |
56 throw MakeTypeError('incompatible_method_receiver', | 161 throw MakeTypeError('incompatible_method_receiver', |
57 ['Set.prototype.has', this]); | 162 ['Set.prototype.has', this]); |
58 } | 163 } |
59 return %_SetHas(this, key); | 164 var table = %_JSCollectionGetTable(this); |
| 165 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); |
| 166 var hash = GetHash(key); |
| 167 return SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND; |
60 } | 168 } |
61 | 169 |
62 | 170 |
63 function SetDeleteJS(key) { | 171 function SetDelete(key) { |
64 if (!IS_SET(this)) { | 172 if (!IS_SET(this)) { |
65 throw MakeTypeError('incompatible_method_receiver', | 173 throw MakeTypeError('incompatible_method_receiver', |
66 ['Set.prototype.delete', this]); | 174 ['Set.prototype.delete', this]); |
67 } | 175 } |
68 return %_SetDelete(this, key); | 176 var table = %_JSCollectionGetTable(this); |
| 177 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); |
| 178 var hash = GetHash(key); |
| 179 var entry = SetFindEntry(table, numBuckets, key, hash); |
| 180 if (entry === NOT_FOUND) return false; |
| 181 |
| 182 var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table) - 1; |
| 183 var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table) + 1; |
| 184 var index = ORDERED_HASH_SET_ENTRY_TO_INDEX(entry, numBuckets); |
| 185 FIXED_ARRAY_SET(table, index, %_TheHole()); |
| 186 ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof); |
| 187 ORDERED_HASH_TABLE_SET_DELETED_COUNT(table, nod); |
| 188 if (nof < (numBuckets >>> 1)) %SetShrink(this); |
| 189 return true; |
69 } | 190 } |
70 | 191 |
71 | 192 |
72 function SetGetSizeJS() { | 193 function SetGetSize() { |
73 if (!IS_SET(this)) { | 194 if (!IS_SET(this)) { |
74 throw MakeTypeError('incompatible_method_receiver', | 195 throw MakeTypeError('incompatible_method_receiver', |
75 ['Set.prototype.size', this]); | 196 ['Set.prototype.size', this]); |
76 } | 197 } |
77 return %_SetGetSize(this); | 198 var table = %_JSCollectionGetTable(this); |
| 199 return ORDERED_HASH_TABLE_ELEMENT_COUNT(table); |
78 } | 200 } |
79 | 201 |
80 | 202 |
81 function SetClearJS() { | 203 function SetClearJS() { |
82 if (!IS_SET(this)) { | 204 if (!IS_SET(this)) { |
83 throw MakeTypeError('incompatible_method_receiver', | 205 throw MakeTypeError('incompatible_method_receiver', |
84 ['Set.prototype.clear', this]); | 206 ['Set.prototype.clear', this]); |
85 } | 207 } |
86 %_SetClear(this); | 208 %_SetClear(this); |
87 } | 209 } |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
123 | 245 |
124 %SetCode($Set, SetConstructor); | 246 %SetCode($Set, SetConstructor); |
125 %FunctionSetPrototype($Set, new $Object()); | 247 %FunctionSetPrototype($Set, new $Object()); |
126 %AddNamedProperty($Set.prototype, "constructor", $Set, DONT_ENUM); | 248 %AddNamedProperty($Set.prototype, "constructor", $Set, DONT_ENUM); |
127 %AddNamedProperty( | 249 %AddNamedProperty( |
128 $Set.prototype, symbolToStringTag, "Set", DONT_ENUM | READ_ONLY); | 250 $Set.prototype, symbolToStringTag, "Set", DONT_ENUM | READ_ONLY); |
129 | 251 |
130 %FunctionSetLength(SetForEach, 1); | 252 %FunctionSetLength(SetForEach, 1); |
131 | 253 |
132 // Set up the non-enumerable functions on the Set prototype object. | 254 // Set up the non-enumerable functions on the Set prototype object. |
133 InstallGetter($Set.prototype, "size", SetGetSizeJS); | 255 InstallGetter($Set.prototype, "size", SetGetSize); |
134 InstallFunctions($Set.prototype, DONT_ENUM, $Array( | 256 InstallFunctions($Set.prototype, DONT_ENUM, $Array( |
135 "add", SetAddJS, | 257 "add", SetAdd, |
136 "has", SetHasJS, | 258 "has", SetHas, |
137 "delete", SetDeleteJS, | 259 "delete", SetDelete, |
138 "clear", SetClearJS, | 260 "clear", SetClearJS, |
139 "forEach", SetForEach | 261 "forEach", SetForEach |
140 )); | 262 )); |
141 } | 263 } |
142 | 264 |
143 SetUpSet(); | 265 SetUpSet(); |
144 | 266 |
145 | 267 |
146 // ------------------------------------------------------------------- | 268 // ------------------------------------------------------------------- |
147 // Harmony Map | 269 // Harmony Map |
(...skipping 14 matching lines...) Expand all Loading... |
162 for (var nextItem of iterable) { | 284 for (var nextItem of iterable) { |
163 if (!IS_SPEC_OBJECT(nextItem)) { | 285 if (!IS_SPEC_OBJECT(nextItem)) { |
164 throw MakeTypeError('iterator_value_not_an_object', [nextItem]); | 286 throw MakeTypeError('iterator_value_not_an_object', [nextItem]); |
165 } | 287 } |
166 %_CallFunction(this, nextItem[0], nextItem[1], adder); | 288 %_CallFunction(this, nextItem[0], nextItem[1], adder); |
167 } | 289 } |
168 } | 290 } |
169 } | 291 } |
170 | 292 |
171 | 293 |
172 function MapGetJS(key) { | 294 function MapGet(key) { |
173 if (!IS_MAP(this)) { | 295 if (!IS_MAP(this)) { |
174 throw MakeTypeError('incompatible_method_receiver', | 296 throw MakeTypeError('incompatible_method_receiver', |
175 ['Map.prototype.get', this]); | 297 ['Map.prototype.get', this]); |
176 } | 298 } |
177 return %_MapGet(this, key); | 299 var table = %_JSCollectionGetTable(this); |
| 300 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); |
| 301 var hash = GetHash(key); |
| 302 var entry = MapFindEntry(table, numBuckets, key, hash); |
| 303 if (entry === NOT_FOUND) return UNDEFINED; |
| 304 return ORDERED_HASH_MAP_VALUE_AT(table, entry, numBuckets); |
178 } | 305 } |
179 | 306 |
180 | 307 |
181 function MapSetJS(key, value) { | 308 function MapSet(key, value) { |
182 if (!IS_MAP(this)) { | 309 if (!IS_MAP(this)) { |
183 throw MakeTypeError('incompatible_method_receiver', | 310 throw MakeTypeError('incompatible_method_receiver', |
184 ['Map.prototype.set', this]); | 311 ['Map.prototype.set', this]); |
185 } | 312 } |
186 // Normalize -0 to +0 as required by the spec. | 313 // Normalize -0 to +0 as required by the spec. |
187 // Even though we use SameValueZero as the comparison for the keys we don't | 314 // Even though we use SameValueZero as the comparison for the keys we don't |
188 // want to ever store -0 as the key since the key is directly exposed when | 315 // want to ever store -0 as the key since the key is directly exposed when |
189 // doing iteration. | 316 // doing iteration. |
190 if (key === 0) { | 317 if (key === 0) { |
191 key = 0; | 318 key = 0; |
192 } | 319 } |
193 return %_MapSet(this, key, value); | 320 |
| 321 var table = %_JSCollectionGetTable(this); |
| 322 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); |
| 323 var hash = GetHash(key); |
| 324 var entry = MapFindEntry(table, numBuckets, key, hash); |
| 325 if (entry !== NOT_FOUND) { |
| 326 var existingIndex = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets); |
| 327 FIXED_ARRAY_SET(table, existingIndex + 1, value); |
| 328 return this; |
| 329 } |
| 330 |
| 331 var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table); |
| 332 var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table); |
| 333 var capacity = numBuckets << 1; |
| 334 if ((nof + nod) >= capacity) { |
| 335 // Need to grow, bail out to runtime. |
| 336 %MapGrow(this); |
| 337 // Re-load state from the grown backing store. |
| 338 table = %_JSCollectionGetTable(this); |
| 339 numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); |
| 340 nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table); |
| 341 nod = ORDERED_HASH_TABLE_DELETED_COUNT(table); |
| 342 } |
| 343 entry = nof + nod; |
| 344 var index = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets); |
| 345 var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets); |
| 346 var chainEntry = ORDERED_HASH_TABLE_BUCKET_AT(table, bucket); |
| 347 ORDERED_HASH_TABLE_SET_BUCKET_AT(table, bucket, entry); |
| 348 ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof + 1); |
| 349 FIXED_ARRAY_SET(table, index, key); |
| 350 FIXED_ARRAY_SET(table, index + 1, value); |
| 351 FIXED_ARRAY_SET(table, index + 2, chainEntry); |
| 352 return this; |
194 } | 353 } |
195 | 354 |
196 | 355 |
197 function MapHasJS(key) { | 356 function MapHas(key) { |
198 if (!IS_MAP(this)) { | 357 if (!IS_MAP(this)) { |
199 throw MakeTypeError('incompatible_method_receiver', | 358 throw MakeTypeError('incompatible_method_receiver', |
200 ['Map.prototype.has', this]); | 359 ['Map.prototype.has', this]); |
201 } | 360 } |
202 return %_MapHas(this, key); | 361 var table = %_JSCollectionGetTable(this); |
| 362 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); |
| 363 var hash = GetHash(key); |
| 364 return MapFindEntry(table, numBuckets, key, hash) !== NOT_FOUND; |
203 } | 365 } |
204 | 366 |
205 | 367 |
206 function MapDeleteJS(key) { | 368 function MapDelete(key) { |
207 if (!IS_MAP(this)) { | 369 if (!IS_MAP(this)) { |
208 throw MakeTypeError('incompatible_method_receiver', | 370 throw MakeTypeError('incompatible_method_receiver', |
209 ['Map.prototype.delete', this]); | 371 ['Map.prototype.delete', this]); |
210 } | 372 } |
211 return %_MapDelete(this, key); | 373 var table = %_JSCollectionGetTable(this); |
| 374 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); |
| 375 var hash = GetHash(key); |
| 376 var entry = MapFindEntry(table, numBuckets, key, hash); |
| 377 if (entry === NOT_FOUND) return false; |
| 378 |
| 379 var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table) - 1; |
| 380 var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table) + 1; |
| 381 var index = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets); |
| 382 FIXED_ARRAY_SET(table, index, %_TheHole()); |
| 383 FIXED_ARRAY_SET(table, index + 1, %_TheHole()); |
| 384 ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof); |
| 385 ORDERED_HASH_TABLE_SET_DELETED_COUNT(table, nod); |
| 386 if (nof < (numBuckets >>> 1)) %MapShrink(this); |
| 387 return true; |
212 } | 388 } |
213 | 389 |
214 | 390 |
215 function MapGetSizeJS() { | 391 function MapGetSize() { |
216 if (!IS_MAP(this)) { | 392 if (!IS_MAP(this)) { |
217 throw MakeTypeError('incompatible_method_receiver', | 393 throw MakeTypeError('incompatible_method_receiver', |
218 ['Map.prototype.size', this]); | 394 ['Map.prototype.size', this]); |
219 } | 395 } |
220 return %_MapGetSize(this); | 396 var table = %_JSCollectionGetTable(this); |
| 397 return ORDERED_HASH_TABLE_ELEMENT_COUNT(table); |
221 } | 398 } |
222 | 399 |
223 | 400 |
224 function MapClearJS() { | 401 function MapClearJS() { |
225 if (!IS_MAP(this)) { | 402 if (!IS_MAP(this)) { |
226 throw MakeTypeError('incompatible_method_receiver', | 403 throw MakeTypeError('incompatible_method_receiver', |
227 ['Map.prototype.clear', this]); | 404 ['Map.prototype.clear', this]); |
228 } | 405 } |
229 %_MapClear(this); | 406 %_MapClear(this); |
230 } | 407 } |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
264 | 441 |
265 %SetCode($Map, MapConstructor); | 442 %SetCode($Map, MapConstructor); |
266 %FunctionSetPrototype($Map, new $Object()); | 443 %FunctionSetPrototype($Map, new $Object()); |
267 %AddNamedProperty($Map.prototype, "constructor", $Map, DONT_ENUM); | 444 %AddNamedProperty($Map.prototype, "constructor", $Map, DONT_ENUM); |
268 %AddNamedProperty( | 445 %AddNamedProperty( |
269 $Map.prototype, symbolToStringTag, "Map", DONT_ENUM | READ_ONLY); | 446 $Map.prototype, symbolToStringTag, "Map", DONT_ENUM | READ_ONLY); |
270 | 447 |
271 %FunctionSetLength(MapForEach, 1); | 448 %FunctionSetLength(MapForEach, 1); |
272 | 449 |
273 // Set up the non-enumerable functions on the Map prototype object. | 450 // Set up the non-enumerable functions on the Map prototype object. |
274 InstallGetter($Map.prototype, "size", MapGetSizeJS); | 451 InstallGetter($Map.prototype, "size", MapGetSize); |
275 InstallFunctions($Map.prototype, DONT_ENUM, $Array( | 452 InstallFunctions($Map.prototype, DONT_ENUM, $Array( |
276 "get", MapGetJS, | 453 "get", MapGet, |
277 "set", MapSetJS, | 454 "set", MapSet, |
278 "has", MapHasJS, | 455 "has", MapHas, |
279 "delete", MapDeleteJS, | 456 "delete", MapDelete, |
280 "clear", MapClearJS, | 457 "clear", MapClearJS, |
281 "forEach", MapForEach | 458 "forEach", MapForEach |
282 )); | 459 )); |
| 460 |
| 461 $MapGet = MapGet; |
| 462 $MapSet = MapSet; |
283 } | 463 } |
284 | 464 |
285 SetUpMap(); | 465 SetUpMap(); |
| 466 |
| 467 })(); |
OLD | NEW |