← Back to branch summary

~ubuntu-branches/ubuntu/karmic/webkit/karmic-proposed

« back to all changes in this revision

Viewing changes to JavaScriptCore/runtime/JSArray.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Gustavo Noronha Silva
  • Date: 2009-05-15 18:30:58 UTC
  • mfrom: (1.1.8 upstream)
  • Revision ID: james.westby@ubuntu.com-20090515183058-50q5exjo9b1kxy9s
Tags: 1.1.7-1
http://bugs.debian.org/526683
* New upstream release
* debian/libwebkit-1.0-2.symbols:
- updated with the new symbols in 1.1.7
* debian/libwebkit-dev.install, debian/libwebkit-dev.links,
  debian/rules:
- Build, and ship gtk-doc documentation (Closes: #526683)
* debian/copyright:
- updated.

Show diffs side-by-side

added added

removed removed

Lines of Context:
JavaScriptCore/runtime/JSArray.cpp
67
67
 
68
68
// The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
69
69
// function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
70
 
// size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(JSValuePtr)) +
71
 
// (vectorLength * sizeof(JSValuePtr)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
72
 
#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValuePtr))) / sizeof(JSValuePtr))
 
70
// size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(JSValue)) +
 
71
// (vectorLength * sizeof(JSValue)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
 
72
#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue))
73
73
 
74
74
// These values have to be macros to be used in max() and min() without introducing
75
75
// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
92
92
 
93
93
    // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
94
94
    // - as asserted above - the following calculation cannot overflow.
95
 
    size_t size = (sizeof(ArrayStorage) - sizeof(JSValuePtr)) + (vectorLength * sizeof(JSValuePtr));
 
95
    size_t size = (sizeof(ArrayStorage) - sizeof(JSValue)) + (vectorLength * sizeof(JSValue));
96
96
    // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
97
97
    // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
98
 
    ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValuePtr))) / sizeof(JSValuePtr) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValuePtr))));
 
98
    ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue))));
99
99
 
100
100
    return size;
101
101
}
151
151
    m_storage->m_vectorLength = initialCapacity;
152
152
    m_storage->m_length = initialLength;
153
153
 
154
 
    Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValuePtr));
 
154
    Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue));
155
155
 
156
156
    checkConsistency();
157
157
}
158
158
 
159
 
JSArray::JSArray(ExecState* exec, PassRefPtr<Structure> structure, const ArgList& list)
 
159
JSArray::JSArray(PassRefPtr<Structure> structure, const ArgList& list)
160
160
    : JSObject(structure)
161
161
{
162
162
    unsigned length = list.size();
173
173
    size_t i = 0;
174
174
    ArgList::const_iterator end = list.end();
175
175
    for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
176
 
        storage->m_vector[i] = (*it).jsValue(exec);
 
176
        storage->m_vector[i] = *it;
177
177
 
178
178
    m_storage = storage;
179
179
 
201
201
    }
202
202
 
203
203
    if (i < storage->m_vectorLength) {
204
 
        JSValuePtr& valueSlot = storage->m_vector[i];
 
204
        JSValue& valueSlot = storage->m_vector[i];
205
205
        if (valueSlot) {
206
206
            slot.setValueSlot(&valueSlot);
207
207
            return true;
235
235
}
236
236
 
237
237
// ECMA 15.4.5.1
238
 
void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValuePtr value, PutPropertySlot& slot)
 
238
void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
239
239
{
240
240
    bool isArrayIndex;
241
241
    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
257
257
    JSObject::put(exec, propertyName, value, slot);
258
258
}
259
259
 
260
 
void JSArray::put(ExecState* exec, unsigned i, JSValuePtr value)
 
260
void JSArray::put(ExecState* exec, unsigned i, JSValue value)
261
261
{
262
262
    checkConsistency();
263
263
 
268
268
    }
269
269
 
270
270
    if (i < m_storage->m_vectorLength) {
271
 
        JSValuePtr& valueSlot = m_storage->m_vector[i];
 
271
        JSValue& valueSlot = m_storage->m_vector[i];
272
272
        if (valueSlot) {
273
273
            valueSlot = value;
274
274
            checkConsistency();
284
284
    putSlowCase(exec, i, value);
285
285
}
286
286
 
287
 
NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValuePtr value)
 
287
NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
288
288
{
289
289
    ArrayStorage* storage = m_storage;
290
290
    SparseArrayValueMap* map = storage->m_sparseValueMap;
355
355
 
356
356
    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
357
357
        for (unsigned j = vectorLength; j < newVectorLength; ++j)
358
 
            storage->m_vector[j] = noValue();
 
358
            storage->m_vector[j] = JSValue();
359
359
        if (i > MIN_SPARSE_ARRAY_INDEX)
360
360
            map->remove(i);
361
361
    } else {
362
362
        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
363
 
            storage->m_vector[j] = noValue();
 
363
            storage->m_vector[j] = JSValue();
364
364
        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
365
365
            storage->m_vector[j] = map->take(j);
366
366
    }
395
395
    ArrayStorage* storage = m_storage;
396
396
 
397
397
    if (i < storage->m_vectorLength) {
398
 
        JSValuePtr& valueSlot = storage->m_vector[i];
 
398
        JSValue& valueSlot = storage->m_vector[i];
399
399
        if (!valueSlot) {
400
400
            checkConsistency();
401
401
            return false;
402
402
        }
403
 
        valueSlot = noValue();
 
403
        valueSlot = JSValue();
404
404
        --storage->m_numValuesInVector;
405
405
        if (m_fastAccessCutoff > i)
406
406
            m_fastAccessCutoff = i;
470
470
    storage->m_vectorLength = newVectorLength;
471
471
 
472
472
    for (unsigned i = vectorLength; i < newVectorLength; ++i)
473
 
        storage->m_vector[i] = noValue();
 
473
        storage->m_vector[i] = JSValue();
474
474
 
475
475
    m_storage = storage;
476
476
    return true;
490
490
 
491
491
        unsigned usedVectorLength = min(length, storage->m_vectorLength);
492
492
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
493
 
            JSValuePtr& valueSlot = storage->m_vector[i];
 
493
            JSValue& valueSlot = storage->m_vector[i];
494
494
            bool hadValue = valueSlot;
495
 
            valueSlot = noValue();
 
495
            valueSlot = JSValue();
496
496
            storage->m_numValuesInVector -= hadValue;
497
497
        }
498
498
 
515
515
    checkConsistency();
516
516
}
517
517
 
518
 
JSValuePtr JSArray::pop()
 
518
JSValue JSArray::pop()
519
519
{
520
520
    checkConsistency();
521
521
 
525
525
 
526
526
    --length;
527
527
 
528
 
    JSValuePtr result;
 
528
    JSValue result;
529
529
 
530
530
    if (m_fastAccessCutoff > length) {
531
 
        JSValuePtr& valueSlot = m_storage->m_vector[length];
 
531
        JSValue& valueSlot = m_storage->m_vector[length];
532
532
        result = valueSlot;
533
533
        ASSERT(result);
534
 
        valueSlot = noValue();
 
534
        valueSlot = JSValue();
535
535
        --m_storage->m_numValuesInVector;
536
536
        m_fastAccessCutoff = length;
537
537
    } else if (length < m_storage->m_vectorLength) {
538
 
        JSValuePtr& valueSlot = m_storage->m_vector[length];
 
538
        JSValue& valueSlot = m_storage->m_vector[length];
539
539
        result = valueSlot;
540
 
        valueSlot = noValue();
 
540
        valueSlot = JSValue();
541
541
        if (result)
542
542
            --m_storage->m_numValuesInVector;
543
543
        else
564
564
    return result;
565
565
}
566
566
 
567
 
void JSArray::push(ExecState* exec, JSValuePtr value)
 
567
void JSArray::push(ExecState* exec, JSValue value)
568
568
{
569
569
    checkConsistency();
570
570
 
604
604
 
605
605
    unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
606
606
    for (unsigned i = 0; i < usedVectorLength; ++i) {
607
 
        JSValuePtr value = storage->m_vector[i];
 
607
        JSValue value = storage->m_vector[i];
608
608
        if (value && !value.marked())
609
609
            value.mark();
610
610
    }
612
612
    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
613
613
        SparseArrayValueMap::iterator end = map->end();
614
614
        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
615
 
            JSValuePtr value = it->second;
 
615
            JSValue value = it->second;
616
616
            if (!value.marked())
617
617
                value.mark();
618
618
        }
621
621
 
622
622
static int compareNumbersForQSort(const void* a, const void* b)
623
623
{
624
 
    double da = static_cast<const JSValuePtr*>(a)->uncheckedGetNumber();
625
 
    double db = static_cast<const JSValuePtr*>(b)->uncheckedGetNumber();
 
624
    double da = static_cast<const JSValue*>(a)->uncheckedGetNumber();
 
625
    double db = static_cast<const JSValue*>(b)->uncheckedGetNumber();
626
626
    return (da > db) - (da < db);
627
627
}
628
628
 
629
 
typedef std::pair<JSValuePtr, UString> ValueStringPair;
 
629
typedef std::pair<JSValue, UString> ValueStringPair;
630
630
 
631
631
static int compareByStringPairForQSort(const void* a, const void* b)
632
632
{
635
635
    return compare(va->second, vb->second);
636
636
}
637
637
 
638
 
void JSArray::sortNumeric(ExecState* exec, JSValuePtr compareFunction, CallType callType, const CallData& callData)
 
638
void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
639
639
{
640
640
    unsigned lengthNotIncludingUndefined = compactForSorting();
641
641
    if (m_storage->m_sparseValueMap) {
661
661
    // For numeric comparison, which is fast, qsort is faster than mergesort. We
662
662
    // also don't require mergesort's stability, since there's no user visible
663
663
    // side-effect from swapping the order of equal primitive values.
664
 
    qsort(m_storage->m_vector, size, sizeof(JSValuePtr), compareNumbersForQSort);
 
664
    qsort(m_storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
665
665
 
666
666
    checkConsistency(SortConsistencyCheck);
667
667
}
689
689
    }
690
690
 
691
691
    for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
692
 
        JSValuePtr value = m_storage->m_vector[i];
 
692
        JSValue value = m_storage->m_vector[i];
693
693
        ASSERT(!value.isUndefined());
694
694
        values[i].first = value;
695
695
    }
727
727
}
728
728
 
729
729
struct AVLTreeNodeForArrayCompare {
730
 
    JSValuePtr value;
 
730
    JSValue value;
731
731
 
732
732
    // Child pointers.  The high bit of gt is robbed and used as the
733
733
    // balance factor sign.  The high bit of lt is robbed and used as
738
738
 
739
739
struct AVLTreeAbstractorForArrayCompare {
740
740
    typedef int32_t handle; // Handle is an index into m_nodes vector.
741
 
    typedef JSValuePtr key;
 
741
    typedef JSValue key;
742
742
    typedef int32_t size;
743
743
 
744
744
    Vector<AVLTreeNodeForArrayCompare> m_nodes;
745
745
    ExecState* m_exec;
746
 
    JSValuePtr m_compareFunction;
 
746
    JSValue m_compareFunction;
747
747
    CallType m_compareCallType;
748
748
    const CallData* m_compareCallData;
749
 
    JSValuePtr m_globalThisValue;
 
749
    JSValue m_globalThisValue;
750
750
    OwnPtr<CachedCall> m_cachedCall;
751
751
 
752
752
    handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
790
790
            m_cachedCall->setArgument(1, vb);
791
791
            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame());
792
792
        } else {
793
 
            ArgList arguments;
 
793
            MarkedArgumentBuffer arguments;
794
794
            arguments.append(va);
795
795
            arguments.append(vb);
796
796
            compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments).toNumber(m_exec);
804
804
    static handle null() { return 0x7FFFFFFF; }
805
805
};
806
806
 
807
 
void JSArray::sort(ExecState* exec, JSValuePtr compareFunction, CallType callType, const CallData& callData)
 
807
void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
808
808
{
809
809
    checkConsistency();
810
810
 
845
845
 
846
846
    // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
847
847
    for (; numDefined < usedVectorLength; ++numDefined) {
848
 
        JSValuePtr v = m_storage->m_vector[numDefined];
 
848
        JSValue v = m_storage->m_vector[numDefined];
849
849
        if (!v || v.isUndefined())
850
850
            break;
851
851
        tree.abstractor().m_nodes[numDefined].value = v;
852
852
        tree.insert(numDefined);
853
853
    }
854
854
    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
855
 
        JSValuePtr v = m_storage->m_vector[i];
 
855
        JSValue v = m_storage->m_vector[i];
856
856
        if (v) {
857
857
            if (v.isUndefined())
858
858
                ++numUndefined;
906
906
 
907
907
    // Ensure that unused values in the vector are zeroed out.
908
908
    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
909
 
        m_storage->m_vector[i] = noValue();
 
909
        m_storage->m_vector[i] = JSValue();
910
910
 
911
911
    m_fastAccessCutoff = newUsedVectorLength;
912
912
    m_storage->m_numValuesInVector = newUsedVectorLength;
914
914
    checkConsistency(SortConsistencyCheck);
915
915
}
916
916
 
917
 
void JSArray::fillArgList(ExecState* exec, ArgList& args)
 
917
void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
918
918
{
919
919
    unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff);
920
920
    unsigned i = 0;
949
949
    unsigned numUndefined = 0;
950
950
 
951
951
    for (; numDefined < usedVectorLength; ++numDefined) {
952
 
        JSValuePtr v = storage->m_vector[numDefined];
 
952
        JSValue v = storage->m_vector[numDefined];
953
953
        if (!v || v.isUndefined())
954
954
            break;
955
955
    }
956
956
    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
957
 
        JSValuePtr v = storage->m_vector[i];
 
957
        JSValue v = storage->m_vector[i];
958
958
        if (v) {
959
959
            if (v.isUndefined())
960
960
                ++numUndefined;
986
986
    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
987
987
        storage->m_vector[i] = jsUndefined();
988
988
    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
989
 
        storage->m_vector[i] = noValue();
 
989
        storage->m_vector[i] = JSValue();
990
990
 
991
991
    m_fastAccessCutoff = newUsedVectorLength;
992
992
    storage->m_numValuesInVector = newUsedVectorLength;
1019
1019
 
1020
1020
    unsigned numValuesInVector = 0;
1021
1021
    for (unsigned i = 0; i < m_storage->m_vectorLength; ++i) {
1022
 
        if (JSValuePtr value = m_storage->m_vector[i]) {
 
1022
        if (JSValue value = m_storage->m_vector[i]) {
1023
1023
            ASSERT(i < m_storage->m_length);
1024
1024
            if (type != DestructorConsistencyCheck)
1025
1025
                value->type(); // Likely to crash if the object was deallocated.
1058
1058
    return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), initialLength);
1059
1059
}
1060
1060
 
1061
 
JSArray* constructArray(ExecState* exec, JSValuePtr singleItemValue)
 
1061
JSArray* constructArray(ExecState* exec, JSValue singleItemValue)
1062
1062
{
1063
 
    ArgList values;
 
1063
    MarkedArgumentBuffer values;
1064
1064
    values.append(singleItemValue);
1065
 
    return new (exec) JSArray(exec, exec->lexicalGlobalObject()->arrayStructure(), values);
 
1065
    return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), values);
1066
1066
}
1067
1067
 
1068
1068
JSArray* constructArray(ExecState* exec, const ArgList& values)
1069
1069
{
1070
 
    return new (exec) JSArray(exec, exec->lexicalGlobalObject()->arrayStructure(), values);
 
1070
    return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), values);
1071
1071
}
1072
1072
 
1073
1073
} // namespace JSC