Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(61)

Side by Side Diff: src/collection.js

Issue 1398733002: Move builtin JavaScript sources into own directory. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Also move macros.py file. Created 5 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/code-stubs.js ('k') | src/collection-iterator.js » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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 })
OLDNEW
« no previous file with comments | « src/code-stubs.js ('k') | src/collection-iterator.js » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698