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
36using std::min;
37using std::max;
38
39
40namespace KJS {
41
42struct 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
59typedef HashMap<unsigned, ArrayEntity> SparseArrayValueMap;
60
61struct ArrayStorage {
62 unsigned m_numValuesInVector;
63 SparseArrayValueMap* m_sparseValueMap;
64 ArrayEntity m_vector[1];
65};
66
67// (2^32)-1
68static const unsigned maxArrayLength = 0xFFFFFFFFU;
69// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer
70static 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.
76static const unsigned sparseArrayCutoff = 10000;
77static const unsigned minDensityMultiplier = 8;
78
79static const unsigned mergeSortCutoff = 10000;
80
81const ClassInfo ArrayInstance::info = {"Array", 0, 0, 0};
82
83static inline size_t storageSize(unsigned vectorLength)
84{
85 return sizeof(ArrayStorage) - sizeof(ArrayEntity) + vectorLength * sizeof(ArrayEntity);
86}
87
88static inline unsigned increasedVectorLength(unsigned newLength)
89{
90 return (newLength * 3 + 1) / 2;
91}
92
93static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
94{
95 return length / minDensityMultiplier <= numValues;
96}
97
98ArrayInstance::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
111ArrayInstance::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
137ArrayInstance::~ArrayInstance()
138{
139 delete m_storage->m_sparseValueMap;
140 fastFree(m_storage);
141}
142
143JSValue* 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
153JSValue* ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)
154{
155 return jsNumber(static_cast<ArrayInstance*>(slot.slotBase())->m_length);
156}
157
158ALWAYS_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
184ArrayEntity* 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
206bool 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
221bool ArrayInstance::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
222{
223 return inlineGetOwnPropertySlot(exec, i, slot);
224}
225
226// ECMA 15.4.5.1
227void 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
252void 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
283bool 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
296bool 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
331void 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
360bool 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
382bool 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
480bool 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
496JSValue* 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
512void 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
627void 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
640void 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
653void 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
685void 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
705void 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
758void 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
781static ExecState* execForCompareByStringForQSort;
782
783static 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
796void 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
832struct 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
846static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments;
847
848static 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
866void 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
903unsigned 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
957bool 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