1 | // -*- c-basic-offset: 2 -*- |
2 | /* |
3 | * This file is part of the KDE libraries |
4 | * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) |
5 | * Copyright (C) 2003, 2007, 2008 Apple Inc. All rights reserved. |
6 | * Copyright (C) 2003 Peter Kelly (pmk@post.com) |
7 | * Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com) |
8 | * |
9 | * This library is free software; you can redistribute it and/or |
10 | * modify it under the terms of the GNU Lesser General Public |
11 | * License as published by the Free Software Foundation; either |
12 | * version 2 of the License, or (at your option) any later version. |
13 | * |
14 | * This library is distributed in the hope that it will be useful, |
15 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
17 | * Lesser General Public License for more details. |
18 | * |
19 | * You should have received a copy of the GNU Lesser General Public |
20 | * License along with this library; if not, write to the Free Software |
21 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
22 | * |
23 | */ |
24 | |
25 | #include <config-kjs.h> |
26 | #include "array_instance.h" |
27 | |
28 | #include "PropertyNameArray.h" |
29 | #include "JSVariableObject.h" |
30 | #include <wtf/Assertions.h> |
31 | #include <wtf/HashMap.h> |
32 | |
33 | #include <algorithm> |
34 | #include <stdio.h> |
35 | |
36 | using std::min; |
37 | using std::max; |
38 | |
39 | |
40 | namespace KJS { |
41 | |
42 | struct ArrayEntity { |
43 | ArrayEntity() |
44 | : value(0), |
45 | attributes(0) |
46 | { |
47 | } |
48 | |
49 | ArrayEntity(JSValue* jsVal, uint32_t attr) |
50 | : value(jsVal), |
51 | attributes(attr) |
52 | { |
53 | } |
54 | |
55 | JSValue* value; |
56 | uint32_t attributes; |
57 | }; |
58 | |
59 | typedef HashMap<unsigned, ArrayEntity> SparseArrayValueMap; |
60 | |
61 | struct ArrayStorage { |
62 | unsigned m_numValuesInVector; |
63 | SparseArrayValueMap* m_sparseValueMap; |
64 | ArrayEntity m_vector[1]; |
65 | }; |
66 | |
67 | // (2^32)-1 |
68 | static const unsigned maxArrayLength = 0xFFFFFFFFU; |
69 | // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer |
70 | static const unsigned maxArrayIndex = 0xFFFFFFFEU; |
71 | |
72 | // Our policy for when to use a vector and when to use a sparse map. |
73 | // For all array indices under sparseArrayCutoff, we always use a vector. |
74 | // When indices greater than sparseArrayCutoff are involved, we use a vector |
75 | // as long as it is 1/8 full. If more sparse than that, we use a map. |
76 | static const unsigned sparseArrayCutoff = 10000; |
77 | static const unsigned minDensityMultiplier = 8; |
78 | |
79 | static const unsigned mergeSortCutoff = 10000; |
80 | |
81 | const ClassInfo ArrayInstance::info = {"Array" , 0, 0, 0}; |
82 | |
83 | static inline size_t storageSize(unsigned vectorLength) |
84 | { |
85 | return sizeof(ArrayStorage) - sizeof(ArrayEntity) + vectorLength * sizeof(ArrayEntity); |
86 | } |
87 | |
88 | static inline unsigned increasedVectorLength(unsigned newLength) |
89 | { |
90 | return (newLength * 3 + 1) / 2; |
91 | } |
92 | |
93 | static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues) |
94 | { |
95 | return length / minDensityMultiplier <= numValues; |
96 | } |
97 | |
98 | ArrayInstance::ArrayInstance(JSObject* prototype, unsigned initialLength) |
99 | : JSObject(prototype) |
100 | { |
101 | unsigned initialCapacity = min(initialLength, sparseArrayCutoff); |
102 | |
103 | m_length = initialLength; |
104 | m_vectorLength = initialCapacity; |
105 | m_storage = static_cast<ArrayStorage*>(fastCalloc(storageSize(initialCapacity), 1)); |
106 | m_lengthAttributes = DontDelete | DontEnum; |
107 | |
108 | Collector::reportExtraMemoryCost(initialCapacity * sizeof(ArrayEntity)); |
109 | } |
110 | |
111 | ArrayInstance::ArrayInstance(JSObject* prototype, const List& list) |
112 | : JSObject(prototype) |
113 | { |
114 | unsigned length = list.size(); |
115 | |
116 | m_length = length; |
117 | m_vectorLength = length; |
118 | m_lengthAttributes = DontDelete | DontEnum; |
119 | |
120 | ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length))); |
121 | |
122 | storage->m_numValuesInVector = length; |
123 | storage->m_sparseValueMap = 0; |
124 | |
125 | ListIterator it = list.begin(); |
126 | for (unsigned i = 0; i < length; ++i) { |
127 | storage->m_vector[i].value = it++; |
128 | storage->m_vector[i].attributes = 0; |
129 | } |
130 | |
131 | m_storage = storage; |
132 | |
133 | // When the array is created non-empty, its cells are filled, so it's really no worse than |
134 | // a property map. Therefore don't report extra memory cost. |
135 | } |
136 | |
137 | ArrayInstance::~ArrayInstance() |
138 | { |
139 | delete m_storage->m_sparseValueMap; |
140 | fastFree(m_storage); |
141 | } |
142 | |
143 | JSValue* ArrayInstance::getItem(unsigned i) const |
144 | { |
145 | ASSERT(i <= maxArrayIndex); |
146 | |
147 | ArrayEntity* ent = getArrayEntity(i); |
148 | if (ent) |
149 | return ent->value; |
150 | return jsUndefined(); |
151 | } |
152 | |
153 | JSValue* ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot) |
154 | { |
155 | return jsNumber(static_cast<ArrayInstance*>(slot.slotBase())->m_length); |
156 | } |
157 | |
158 | ALWAYS_INLINE bool ArrayInstance::inlineGetOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot) |
159 | { |
160 | if (i >= m_length) { |
161 | if (i > maxArrayIndex) |
162 | return getOwnPropertySlot(exec, Identifier::from(i), slot); |
163 | return false; |
164 | } |
165 | |
166 | ArrayEntity* ent = getArrayEntity(i); |
167 | if (ent) { |
168 | if (ent->attributes & GetterSetter) { |
169 | GetterSetterImp *gs = static_cast<GetterSetterImp *>(ent->value); |
170 | JSObject *getterFunc = gs->getGetter(); |
171 | if (getterFunc) |
172 | slot.setGetterSlot(this, getterFunc); |
173 | else |
174 | slot.setUndefined(this); |
175 | return true; |
176 | } |
177 | slot.setValueSlot(this, &ent->value); |
178 | return true; |
179 | } |
180 | |
181 | return false; |
182 | } |
183 | |
184 | ArrayEntity* ArrayInstance::getArrayEntity(unsigned int i) const |
185 | { |
186 | if (i >= m_length) |
187 | return 0; |
188 | |
189 | ArrayStorage* storage = m_storage; |
190 | if (i < m_vectorLength) { |
191 | if (storage->m_vector[i].value) |
192 | return &storage->m_vector[i]; |
193 | } |
194 | |
195 | SparseArrayValueMap* map = storage->m_sparseValueMap; |
196 | if (map && i > 0 && i <= maxArrayIndex) { |
197 | SparseArrayValueMap::iterator it = map->find(i); |
198 | if (it != map->end()) { |
199 | return &it->second; |
200 | } |
201 | } |
202 | |
203 | return 0; |
204 | } |
205 | |
206 | bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot) |
207 | { |
208 | if (propertyName == exec->propertyNames().length) { |
209 | slot.setCustom(this, lengthGetter); |
210 | return true; |
211 | } |
212 | |
213 | bool isArrayIndex; |
214 | unsigned i = propertyName.toArrayIndex(&isArrayIndex); |
215 | if (isArrayIndex) |
216 | return inlineGetOwnPropertySlot(exec, i, slot); |
217 | |
218 | return JSObject::getOwnPropertySlot(exec, propertyName, slot); |
219 | } |
220 | |
221 | bool ArrayInstance::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot) |
222 | { |
223 | return inlineGetOwnPropertySlot(exec, i, slot); |
224 | } |
225 | |
226 | // ECMA 15.4.5.1 |
227 | void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attributes) |
228 | { |
229 | bool isArrayIndex; |
230 | unsigned i = propertyName.toArrayIndex(&isArrayIndex); |
231 | if (isArrayIndex) { |
232 | put(exec, i, value, attributes); |
233 | return; |
234 | } |
235 | |
236 | if (propertyName == exec->propertyNames().length) { |
237 | if (m_lengthAttributes & ReadOnly) |
238 | return; |
239 | unsigned newLength = value->toUInt32(exec); |
240 | if (value->toNumber(exec) != static_cast<double>(newLength)) { |
241 | throwError(exec, RangeError, "Invalid array length." ); |
242 | return; |
243 | } |
244 | m_lengthAttributes = attributes; |
245 | setLength(newLength); |
246 | return; |
247 | } |
248 | |
249 | JSObject::put(exec, propertyName, value, attributes); |
250 | } |
251 | |
252 | void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value, int attributes) |
253 | { |
254 | ArrayEntity *ent = getArrayEntity(i); |
255 | if (ent) { |
256 | if (ent->attributes & ReadOnly) |
257 | return; |
258 | attributes |= ent->attributes; |
259 | |
260 | JSValue* gs = ent->value; |
261 | if (gs && !gs->isUndefined()) { |
262 | if (ent->attributes & GetterSetter) { |
263 | JSObject *setterFunc = static_cast<GetterSetterImp *>(gs)->getSetter(); |
264 | |
265 | if (!setterFunc) { |
266 | if (false) //if strict is true |
267 | throwError(exec, TypeError, "setting a property that has only a getter" ); |
268 | return; |
269 | } |
270 | |
271 | List args; |
272 | args.append(value); |
273 | |
274 | setterFunc->call(exec, this, args); |
275 | return; |
276 | } |
277 | } |
278 | } |
279 | |
280 | KJS::ArrayInstance::putDirect(i, value, attributes); |
281 | } |
282 | |
283 | bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier& propertyName) |
284 | { |
285 | bool isArrayIndex; |
286 | unsigned i = propertyName.toArrayIndex(&isArrayIndex); |
287 | if (isArrayIndex) |
288 | return deleteProperty(exec, i); |
289 | |
290 | if (propertyName == exec->propertyNames().length) |
291 | return false; |
292 | |
293 | return JSObject::deleteProperty(exec, propertyName); |
294 | } |
295 | |
296 | bool ArrayInstance::deleteProperty(ExecState* exec, unsigned i) |
297 | { |
298 | ArrayStorage* storage = m_storage; |
299 | |
300 | if (i < m_vectorLength) { |
301 | ArrayEntity* ent = &storage->m_vector[i]; |
302 | if (ent->value) { |
303 | if (ent->attributes & DontDelete) |
304 | return false; |
305 | |
306 | JSValue*& valueSlot = ent->value; |
307 | bool hadValue = valueSlot; |
308 | valueSlot = 0; |
309 | storage->m_numValuesInVector -= hadValue; |
310 | ent->value = 0; |
311 | return hadValue; |
312 | } |
313 | } |
314 | |
315 | if (SparseArrayValueMap* map = storage->m_sparseValueMap) { |
316 | SparseArrayValueMap::iterator it = map->find(i); |
317 | if (it != map->end()) { |
318 | if ((*it).second.attributes & DontDelete) |
319 | return false; |
320 | map->remove(it->first); |
321 | return true; |
322 | } |
323 | } |
324 | |
325 | if (i > maxArrayIndex) |
326 | return JSObject::deleteProperty(exec, Identifier::from(i)); |
327 | |
328 | return true; |
329 | } |
330 | |
331 | void ArrayInstance::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames, PropertyMap::PropertyMode mode) |
332 | { |
333 | // FIXME: Filling PropertyNameArray with an identifier for every integer |
334 | // is incredibly inefficient for large arrays. We need a different approach. |
335 | |
336 | ArrayStorage* storage = m_storage; |
337 | |
338 | unsigned usedVectorLength = min(m_length, m_vectorLength); |
339 | for (unsigned i = 0; i < usedVectorLength; ++i) { |
340 | if (storage->m_vector[i].value && |
341 | (!(storage->m_vector[i].attributes & DontEnum) || |
342 | mode == PropertyMap::IncludeDontEnumProperties)) |
343 | propertyNames.add(Identifier::from(i)); |
344 | } |
345 | |
346 | if (SparseArrayValueMap* map = storage->m_sparseValueMap) { |
347 | SparseArrayValueMap::iterator end = map->end(); |
348 | for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) |
349 | if (!((*it).second.attributes & DontEnum) || |
350 | mode == PropertyMap::IncludeDontEnumProperties) |
351 | propertyNames.add(Identifier::from(it->first)); |
352 | } |
353 | |
354 | if (mode == PropertyMap::IncludeDontEnumProperties) |
355 | propertyNames.add(exec->propertyNames().length); |
356 | |
357 | JSObject::getOwnPropertyNames(exec, propertyNames, mode); |
358 | } |
359 | |
360 | bool ArrayInstance::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor) |
361 | { |
362 | if (propertyName == exec->propertyNames().length) { |
363 | descriptor.setPropertyDescriptorValues(exec, jsNumber(m_length), m_lengthAttributes); |
364 | return true; |
365 | } |
366 | |
367 | bool isArrayIndex; |
368 | unsigned i = propertyName.toArrayIndex(&isArrayIndex); |
369 | |
370 | if (isArrayIndex) { |
371 | ArrayEntity* ent = getArrayEntity(i); |
372 | if (ent) { |
373 | descriptor.setPropertyDescriptorValues(exec, ent->value, ent->attributes); |
374 | return true; |
375 | } |
376 | } |
377 | return JSObject::getOwnPropertyDescriptor(exec, propertyName, descriptor); |
378 | } |
379 | |
380 | |
381 | //ECMAScript Edition 5.1r6 - 15.4.5.1 |
382 | bool ArrayInstance::defineOwnProperty(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& desc, bool shouldThrow) |
383 | { |
384 | PropertyDescriptor oldLenDesc; |
385 | getOwnPropertyDescriptor(exec, exec->propertyNames().length, oldLenDesc); |
386 | unsigned int oldLen = oldLenDesc.value()->toUInt32(exec); |
387 | |
388 | //4a |
389 | bool isArrayIndex; |
390 | unsigned index = propertyName.toArrayIndex(&isArrayIndex); |
391 | |
392 | //Step 3 |
393 | if (propertyName == exec->propertyNames().length) { |
394 | //a |
395 | if (!desc.value()) |
396 | return JSObject::defineOwnProperty(exec, propertyName, desc, shouldThrow); |
397 | |
398 | //b |
399 | PropertyDescriptor newLenDesc(desc); |
400 | //c |
401 | unsigned int newLen = desc.value()->toUInt32(exec); |
402 | //d |
403 | if (newLen != desc.value()->toNumber(exec) || desc.value()->toNumber(exec) > maxArrayLength) { |
404 | throwError(exec, RangeError, "Index out of range" ); |
405 | return false; |
406 | } |
407 | //e |
408 | newLenDesc.setValue(jsNumber(newLen)); |
409 | //f |
410 | if (newLen >= oldLen) |
411 | return JSObject::defineOwnProperty(exec, propertyName, newLenDesc, shouldThrow); |
412 | //g |
413 | if (!oldLenDesc.writable()) { |
414 | if (shouldThrow) |
415 | throwError(exec, TypeError, "length is not writable" ); |
416 | return false; |
417 | } |
418 | //h |
419 | bool newWriteable; |
420 | if (!newLenDesc.writableSet() || newLenDesc.writable()) { |
421 | newWriteable = true; |
422 | } else { //i |
423 | if (anyItemHasAttribute(DontDelete)) |
424 | newLenDesc.setWritable(false); |
425 | else |
426 | newLenDesc.setWritable(true); |
427 | newWriteable = false; |
428 | } |
429 | //j |
430 | bool succeeded = JSObject::defineOwnProperty(exec, propertyName, newLenDesc, shouldThrow); |
431 | //k |
432 | if (!succeeded) return false; |
433 | //l |
434 | while (newLen < oldLen) { |
435 | --oldLen; |
436 | bool deleteSucceeded = deleteProperty(exec, oldLen); // 3. argument should be false |
437 | if (!deleteSucceeded) { |
438 | newLenDesc.setValue(jsNumber(oldLen+1)); |
439 | if (!newWriteable) |
440 | newLenDesc.setWritable(false); |
441 | JSObject::defineOwnProperty(exec, propertyName, newLenDesc, false); |
442 | if (shouldThrow) |
443 | throwError(exec, TypeError); |
444 | return false; |
445 | } |
446 | } |
447 | //m |
448 | if (!newWriteable) { |
449 | PropertyDescriptor writableDesc; |
450 | writableDesc.setWritable(false); |
451 | return JSObject::defineOwnProperty(exec, propertyName, writableDesc, false); |
452 | } |
453 | return true; |
454 | } else if (isArrayIndex) {//Step 4 |
455 | //b |
456 | if (index >= oldLen && !oldLenDesc.writable()) { |
457 | if (shouldThrow) |
458 | throwError(exec, TypeError); |
459 | return false; |
460 | } |
461 | //c |
462 | bool succeeded = JSObject::defineOwnProperty(exec, propertyName, desc, false); |
463 | //d |
464 | if (!succeeded) { |
465 | if (shouldThrow) |
466 | throwError(exec, TypeError); |
467 | return false; |
468 | } |
469 | //e |
470 | if (index >= oldLen) { |
471 | oldLenDesc.setValue(jsNumber(index+1)); |
472 | JSObject::defineOwnProperty(exec, exec->propertyNames().length, oldLenDesc, false); |
473 | } |
474 | return true; |
475 | } |
476 | |
477 | return JSObject::defineOwnProperty(exec, propertyName, desc, shouldThrow); |
478 | } |
479 | |
480 | bool ArrayInstance::getPropertyAttributes(const Identifier& propertyName, unsigned int& attributes) const |
481 | { |
482 | bool isArrayIndex; |
483 | unsigned i = propertyName.toArrayIndex(&isArrayIndex); |
484 | |
485 | if (isArrayIndex) { |
486 | ArrayEntity* ent = getArrayEntity(i); |
487 | if (ent) { |
488 | attributes = ent->attributes; |
489 | return true; |
490 | } |
491 | } |
492 | |
493 | return KJS::JSObject::getPropertyAttributes(propertyName, attributes); |
494 | } |
495 | |
496 | JSValue* ArrayInstance::getDirect(const Identifier& propertyName) const |
497 | { |
498 | bool isArrayIndex; |
499 | unsigned i = propertyName.toArrayIndex(&isArrayIndex); |
500 | |
501 | if (isArrayIndex) { |
502 | ArrayEntity* ent = getArrayEntity(i); |
503 | if (ent) { |
504 | if (ent->value) |
505 | return ent->value; |
506 | } |
507 | } |
508 | |
509 | return KJS::JSObject::getDirect(propertyName); |
510 | } |
511 | |
512 | void ArrayInstance::putDirect(unsigned i, JSValue* value, int attributes) |
513 | { |
514 | unsigned length = m_length; |
515 | |
516 | if (i >= length) { |
517 | if (i > maxArrayIndex) { |
518 | KJS::JSObject::putDirect(Identifier::from(i), value, attributes); |
519 | return; |
520 | } |
521 | length = i + 1; |
522 | m_length = length; |
523 | } |
524 | |
525 | ArrayStorage* storage = m_storage; |
526 | |
527 | if (i < m_vectorLength) { |
528 | ArrayEntity* ent = &storage->m_vector[i]; |
529 | if (!ent->value && !isExtensible()) |
530 | return; |
531 | JSValue*& valueSlot = ent->value; |
532 | storage->m_numValuesInVector += !valueSlot; |
533 | valueSlot = value; |
534 | ent->attributes = attributes; |
535 | return; |
536 | } |
537 | |
538 | if (!isExtensible()) |
539 | return; |
540 | |
541 | SparseArrayValueMap* map = storage->m_sparseValueMap; |
542 | if (i >= sparseArrayCutoff) { |
543 | // If the index is high, go to the map unless we're pretty dense. |
544 | if (!map) { |
545 | map = new SparseArrayValueMap; |
546 | storage->m_sparseValueMap = map; |
547 | |
548 | // If we create a sparse map, we need to ensure that there is at least one spot |
549 | // in the vector map, however, since the sparse map can't put/get key 0. |
550 | // It's safe to do it here, since put(0) will always put it in the vector part, |
551 | // but we have to do it before a get(0) or it will crash |
552 | if (!m_vectorLength) |
553 | increaseVectorLength(1); |
554 | } |
555 | |
556 | map->set(i, ArrayEntity(value, attributes)); |
557 | return; |
558 | } |
559 | |
560 | // note: an invariant here is that indeces < sparseArrayCutoff |
561 | // are always inside the vector portion. |
562 | |
563 | // lowish indeces or high density -> we have decided that we'll put the new item into the vector. |
564 | // Fast case is when there is no sparse map, so we can increase the vector size without moving values from the sparse map. |
565 | if (!map || map->isEmpty()) { |
566 | increaseVectorLength(i + 1); |
567 | storage = m_storage; |
568 | ++storage->m_numValuesInVector; |
569 | storage->m_vector[i].value = value; |
570 | storage->m_vector[i].attributes = attributes; |
571 | return; |
572 | } |
573 | |
574 | // Decide just how large we want to make the vector to be. |
575 | unsigned newNumValuesInVector = storage->m_numValuesInVector + 1; |
576 | unsigned newVectorLength = increasedVectorLength(i + 1); |
577 | |
578 | // First, count how much stuff we are guaranteed to move over, now |
579 | // that we've decided to at least include i in the vector. |
580 | for (unsigned j = max(m_vectorLength, sparseArrayCutoff); j < newVectorLength; ++j) |
581 | newNumValuesInVector += map->contains(j); |
582 | if (i >= sparseArrayCutoff) |
583 | newNumValuesInVector -= map->contains(i); |
584 | |
585 | // Continue increasing the vector portion as long as the things in the map are dense enough |
586 | if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) { |
587 | unsigned proposedNewNumValuesInVector = newNumValuesInVector; |
588 | while (true) { |
589 | unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1); |
590 | for (unsigned j = max(newVectorLength, sparseArrayCutoff); j < proposedNewVectorLength; ++j) |
591 | proposedNewNumValuesInVector += map->contains(j); |
592 | if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector)) |
593 | break; |
594 | newVectorLength = proposedNewVectorLength; |
595 | newNumValuesInVector = proposedNewNumValuesInVector; |
596 | } |
597 | } |
598 | |
599 | storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength))); |
600 | |
601 | unsigned vectorLength = m_vectorLength; |
602 | |
603 | // Special case: if we just added a single value, we don't have to scan the map |
604 | // to see what to remove from it |
605 | if (newNumValuesInVector == storage->m_numValuesInVector + 1) { |
606 | for (unsigned j = vectorLength; j < newVectorLength; ++j) |
607 | storage->m_vector[j].value = 0; |
608 | if (i > sparseArrayCutoff) |
609 | map->remove(i); |
610 | } else { |
611 | // Move over things from the map to the new array portion |
612 | for (unsigned j = vectorLength; j < max(vectorLength, sparseArrayCutoff); ++j) |
613 | storage->m_vector[j].value = 0; |
614 | for (unsigned j = max(vectorLength, sparseArrayCutoff); j < newVectorLength; ++j) |
615 | storage->m_vector[j] = map->take(j); |
616 | } |
617 | |
618 | storage->m_vector[i].value = value; |
619 | storage->m_vector[i].attributes = attributes; |
620 | |
621 | m_vectorLength = newVectorLength; |
622 | storage->m_numValuesInVector = newNumValuesInVector; |
623 | |
624 | m_storage = storage; |
625 | } |
626 | |
627 | void ArrayInstance::putDirect(const Identifier& propertyName, JSValue* value, int attr) |
628 | { |
629 | bool isArrayIndex; |
630 | unsigned i = propertyName.toArrayIndex(&isArrayIndex); |
631 | |
632 | if (isArrayIndex) { |
633 | KJS::ArrayInstance::putDirect(i, value, attr); |
634 | return; |
635 | } |
636 | |
637 | KJS::JSObject::putDirect(propertyName, value, attr); |
638 | } |
639 | |
640 | void ArrayInstance::putDirect(const Identifier& propertyName, int value, int attr) |
641 | { |
642 | bool isArrayIndex; |
643 | unsigned i = propertyName.toArrayIndex(&isArrayIndex); |
644 | |
645 | if (isArrayIndex) { |
646 | KJS::ArrayInstance::putDirect(i, jsNumber(value), attr); |
647 | return; |
648 | } |
649 | |
650 | KJS::JSObject::putDirect(propertyName, jsNumber(value), attr); |
651 | } |
652 | |
653 | void ArrayInstance::removeDirect(const Identifier& propertyName) |
654 | { |
655 | bool isArrayIndex; |
656 | unsigned i = propertyName.toArrayIndex(&isArrayIndex); |
657 | |
658 | if (isArrayIndex) { |
659 | ArrayStorage* storage = m_storage; |
660 | |
661 | if (i < m_vectorLength) { |
662 | ArrayEntity* ent = &storage->m_vector[i]; |
663 | if (ent->value) { |
664 | JSValue*& valueSlot = ent->value; |
665 | bool hadValue = valueSlot; |
666 | valueSlot = 0; |
667 | storage->m_numValuesInVector -= hadValue; |
668 | ent->value = 0; |
669 | return; |
670 | } |
671 | } |
672 | |
673 | if (SparseArrayValueMap* map = storage->m_sparseValueMap) { |
674 | SparseArrayValueMap::iterator it = map->find(i); |
675 | if (it != map->end()) { |
676 | map->remove(it->first); |
677 | return; |
678 | } |
679 | } |
680 | } |
681 | |
682 | JSObject::removeDirect(Identifier::from(i)); |
683 | } |
684 | |
685 | void ArrayInstance::increaseVectorLength(unsigned newLength) |
686 | { |
687 | // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map |
688 | // to the vector. Callers have to account for that, because they can do it more efficiently. |
689 | |
690 | ArrayStorage* storage = m_storage; |
691 | |
692 | unsigned vectorLength = m_vectorLength; |
693 | ASSERT(newLength > vectorLength); |
694 | unsigned newVectorLength = increasedVectorLength(newLength); |
695 | |
696 | storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength))); |
697 | m_vectorLength = newVectorLength; |
698 | |
699 | for (unsigned i = vectorLength; i < newVectorLength; ++i) |
700 | storage->m_vector[i].value = 0; |
701 | |
702 | m_storage = storage; |
703 | } |
704 | |
705 | void ArrayInstance::setLength(unsigned newLength) |
706 | { |
707 | ArrayStorage* storage = m_storage; |
708 | |
709 | unsigned length = m_length; |
710 | unsigned newLenSet = newLength; |
711 | |
712 | if (newLength < length) { |
713 | unsigned usedVectorLength = min(length, m_vectorLength); |
714 | if (usedVectorLength > 0) { |
715 | for (unsigned i = usedVectorLength-1; i >= newLength && i > 0; --i) { |
716 | ArrayEntity* ent = &storage->m_vector[i]; |
717 | if (ent->value) { |
718 | if (ent->attributes & DontDelete) { |
719 | newLenSet = i+1; |
720 | break; |
721 | } |
722 | JSValue*& valueSlot = ent->value; |
723 | bool hadValue = valueSlot; |
724 | valueSlot = 0; |
725 | ent->value = 0; |
726 | storage->m_numValuesInVector -= hadValue; |
727 | } |
728 | } |
729 | } |
730 | |
731 | if (SparseArrayValueMap* map = storage->m_sparseValueMap) { |
732 | SparseArrayValueMap copy = *map; |
733 | SparseArrayValueMap::iterator end = copy.end(); |
734 | for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) { |
735 | if (it->first >= newLength) { |
736 | if (it->second.attributes & DontDelete) { |
737 | newLenSet = it->first + 1; |
738 | } |
739 | } |
740 | } |
741 | |
742 | for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) { |
743 | if (it->first >= newLenSet) { |
744 | map->remove(it->first); |
745 | } |
746 | } |
747 | |
748 | if (map->isEmpty()) { |
749 | delete map; |
750 | storage->m_sparseValueMap = 0; |
751 | } |
752 | } |
753 | } |
754 | |
755 | m_length = newLenSet; |
756 | } |
757 | |
758 | void ArrayInstance::mark() |
759 | { |
760 | JSObject::mark(); |
761 | |
762 | ArrayStorage* storage = m_storage; |
763 | |
764 | unsigned usedVectorLength = min(m_length, m_vectorLength); |
765 | for (unsigned i = 0; i < usedVectorLength; ++i) { |
766 | ArrayEntity* ent = &storage->m_vector[i]; |
767 | if (ent->value && !ent->value->marked()) |
768 | ent->value->mark(); |
769 | } |
770 | |
771 | if (SparseArrayValueMap* map = storage->m_sparseValueMap) { |
772 | SparseArrayValueMap::iterator end = map->end(); |
773 | for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) { |
774 | ArrayEntity* ent = &it->second; |
775 | if (!ent->value->marked()) |
776 | ent->value->mark(); |
777 | } |
778 | } |
779 | } |
780 | |
781 | static ExecState* execForCompareByStringForQSort; |
782 | |
783 | static int compareByStringForQSort(const void* a, const void* b) |
784 | { |
785 | ExecState* exec = execForCompareByStringForQSort; |
786 | |
787 | const ArrayEntity* va = static_cast<const ArrayEntity*>(a); |
788 | const ArrayEntity* vb = static_cast<const ArrayEntity*>(b); |
789 | |
790 | ASSERT(va->value && !va->value->isUndefined()); |
791 | ASSERT(vb->value && !vb->value->isUndefined()); |
792 | |
793 | return compare(va->value->toString(exec), vb->value->toString(exec)); |
794 | } |
795 | |
796 | void ArrayInstance::sort(ExecState* exec) |
797 | { |
798 | unsigned lengthNotIncludingUndefined = compactForSorting(); |
799 | |
800 | ExecState* oldExec = execForCompareByStringForQSort; |
801 | execForCompareByStringForQSort = exec; |
802 | |
803 | #if HAVE(MERGESORT) |
804 | // Because mergesort usually does fewer compares, it is faster than qsort here. |
805 | // However, because it requires extra copies of the storage buffer, don't use it for very |
806 | // large arrays. |
807 | |
808 | // FIXME: Since we sort by string value, a fast algorithm might be to convert all the |
809 | // values to string once up front, and then use a radix sort. That would be O(N) rather |
810 | // than O(N log N). |
811 | |
812 | if (lengthNotIncludingUndefined < mergeSortCutoff) { |
813 | // During the sort, we could do a garbage collect, and it's important to still |
814 | // have references to every object in the array for ArrayInstance::mark. |
815 | // The mergesort algorithm does not guarantee this, so we sort a copy rather |
816 | // than the original. |
817 | size_t size = storageSize(m_vectorLength); |
818 | ArrayStorage* copy = static_cast<ArrayStorage*>(fastMalloc(size)); |
819 | memcpy(copy, m_storage, size); |
820 | mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(ArrayEntity), compareByStringForQSort); |
821 | fastFree(m_storage); |
822 | m_storage = copy; |
823 | execForCompareByStringForQSort = oldExec; |
824 | return; |
825 | } |
826 | #endif |
827 | |
828 | qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(ArrayEntity), compareByStringForQSort); |
829 | execForCompareByStringForQSort = oldExec; |
830 | } |
831 | |
832 | struct CompareWithCompareFunctionArguments { |
833 | CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf) |
834 | : exec(e) |
835 | , compareFunction(cf) |
836 | , globalObject(e->dynamicInterpreter()->globalObject()) |
837 | { |
838 | } |
839 | |
840 | ExecState *exec; |
841 | JSObject *compareFunction; |
842 | List arguments; |
843 | JSObject *globalObject; |
844 | }; |
845 | |
846 | static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments; |
847 | |
848 | static int compareWithCompareFunctionForQSort(const void* a, const void* b) |
849 | { |
850 | CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments; |
851 | |
852 | const ArrayEntity* va = static_cast<const ArrayEntity*>(a); |
853 | const ArrayEntity* vb = static_cast<const ArrayEntity*>(b); |
854 | |
855 | ASSERT(va->value && !va->value->isUndefined()); |
856 | ASSERT(vb->value && !vb->value->isUndefined()); |
857 | |
858 | args->arguments.clear(); |
859 | args->arguments.append(va->value); |
860 | args->arguments.append(vb->value); |
861 | double compareResult = args->compareFunction->call |
862 | (args->exec, args->globalObject, args->arguments)->toNumber(args->exec); |
863 | return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0; |
864 | } |
865 | |
866 | void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction) |
867 | { |
868 | size_t lengthNotIncludingUndefined = compactForSorting(); |
869 | |
870 | CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments; |
871 | CompareWithCompareFunctionArguments args(exec, compareFunction); |
872 | compareWithCompareFunctionArguments = &args; |
873 | |
874 | #if HAVE(MERGESORT) |
875 | // Because mergesort usually does fewer compares, it is faster than qsort here. |
876 | // However, because it requires extra copies of the storage buffer, don't use it for very |
877 | // large arrays. |
878 | |
879 | // FIXME: A tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even |
880 | // better job of minimizing compares. |
881 | |
882 | if (lengthNotIncludingUndefined < mergeSortCutoff) { |
883 | // During the sort, we could do a garbage collect, and it's important to still |
884 | // have references to every object in the array for ArrayInstance::mark. |
885 | // The mergesort algorithm does not guarantee this, so we sort a copy rather |
886 | // than the original. |
887 | size_t size = storageSize(m_vectorLength); |
888 | ArrayStorage* copy = static_cast<ArrayStorage*>(fastMalloc(size)); |
889 | memcpy(copy, m_storage, size); |
890 | mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(ArrayEntity), compareWithCompareFunctionForQSort); |
891 | fastFree(m_storage); |
892 | m_storage = copy; |
893 | compareWithCompareFunctionArguments = oldArgs; |
894 | return; |
895 | } |
896 | #endif |
897 | |
898 | qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(ArrayEntity), compareWithCompareFunctionForQSort); |
899 | compareWithCompareFunctionArguments = oldArgs; |
900 | } |
901 | |
902 | |
903 | unsigned ArrayInstance::compactForSorting() |
904 | { |
905 | ArrayStorage* storage = m_storage; |
906 | |
907 | unsigned usedVectorLength = min(m_length, m_vectorLength); |
908 | |
909 | unsigned numDefined = 0; |
910 | unsigned numUndefined = 0; |
911 | |
912 | // This compacts normal values (e.g. not undefined) in a contiguous run |
913 | // at the beginning of the array, and then puts any set undefined values |
914 | // at the end |
915 | |
916 | // count the first contiguous run of defined values in the vector store |
917 | for (; numDefined < usedVectorLength; ++numDefined) { |
918 | ArrayEntity* v = &storage->m_vector[numDefined]; |
919 | if (!v->value || v->value->isUndefined()) |
920 | break; |
921 | } |
922 | |
923 | // compact the rest, counting along the way |
924 | for (unsigned i = numDefined; i < usedVectorLength; ++i) { |
925 | ArrayEntity v = storage->m_vector[i]; |
926 | if (!v.value || v.value->isUndefined()) |
927 | ++numUndefined; |
928 | else |
929 | storage->m_vector[numDefined++] = storage->m_vector[i]; |
930 | } |
931 | |
932 | unsigned newUsedVectorLength = numDefined + numUndefined; |
933 | |
934 | if (SparseArrayValueMap* map = storage->m_sparseValueMap) { |
935 | newUsedVectorLength += map->size(); |
936 | if (newUsedVectorLength > m_vectorLength) { |
937 | increaseVectorLength(newUsedVectorLength); |
938 | storage = m_storage; |
939 | } |
940 | |
941 | SparseArrayValueMap::iterator end = map->end(); |
942 | for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) |
943 | storage->m_vector[numDefined++] = it->second; |
944 | |
945 | delete map; |
946 | storage->m_sparseValueMap = 0; |
947 | } |
948 | |
949 | for (unsigned i = numDefined; i < newUsedVectorLength; ++i) |
950 | storage->m_vector[i].value = 0; |
951 | for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) |
952 | storage->m_vector[i].value = 0; |
953 | |
954 | return numDefined; |
955 | } |
956 | |
957 | bool KJS::ArrayInstance::anyItemHasAttribute(unsigned int attributes) const |
958 | { |
959 | ArrayStorage* storage = m_storage; |
960 | |
961 | unsigned usedVectorLength = min(m_length, m_vectorLength); |
962 | for (unsigned i = 0; i < usedVectorLength; ++i) { |
963 | if (storage->m_vector[i].value && storage->m_vector[i].attributes & attributes) |
964 | return true; |
965 | } |
966 | |
967 | if (SparseArrayValueMap* map = storage->m_sparseValueMap) { |
968 | SparseArrayValueMap::iterator end = map->end(); |
969 | for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) |
970 | if ((*it).second.attributes & attributes) |
971 | return true; |
972 | } |
973 | |
974 | return false; |
975 | } |
976 | |
977 | } |
978 | // kate: indent-width 4; replace-tabs on; tab-width 4; space-indent on; hl c++; |
979 | |