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