src/Array.cpp
author David Anderson <dvander@alliedmods.net>
Sun Jan 06 13:52:21 2013 -0800 (2013-01-06)
changeset 256 3c184218462d
parent 247 7721042bdb67
child 263 ba85a47ee414
permissions -rw-r--r--
Initial implementation of module imports.
[email protected]
     1
/* vim: set ts=4 sw=4 tw=99 et:
[email protected]
     2
 *
[email protected]
     3
 * Copyright (C) 2012 David Anderson
[email protected]
     4
 *
[email protected]
     5
 * This file is part of SourcePawn.
[email protected]
     6
 *
[email protected]
     7
 * SourcePawn is free software: you can redistribute it and/or modify it under
[email protected]
     8
 * the terms of the GNU General Public License as published by the Free
[email protected]
     9
 * Software Foundation, either version 3 of the License, or (at your option)
[email protected]
    10
 * any later version.
[email protected]
    11
 * 
[email protected]
    12
 * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY
[email protected]
    13
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
[email protected]
    14
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
[email protected]
    15
 *
[email protected]
    16
 * You should have received a copy of the GNU General Public License along with
[email protected]
    17
 * SourcePawn. If not, see http://www.gnu.org/licenses/.
[email protected]
    18
 */
[email protected]
    19
#include <string.h>
[email protected]
    20
#include "Array.h"
[email protected]
    21
#include "FixedArray.h"
[email protected]
    22
#include "Heap.h"
[email protected]
    23
#include "Zone.h"
[email protected]
    24
#include "Structures.h"
[email protected]
    25
#include "Heap-inl.h"
[email protected]
    26
[email protected]
    27
using namespace ke;
[email protected]
    28
[email protected]
    29
ArrayMap *
[email protected]
    30
ArrayMap::New(Zone *zone, Handle<ArrayType> type)
[email protected]
    31
{
[email protected]
    32
    Local<Map> obj(zone, zone->allocateMap(MapKind_Array, sizeof(ArrayMap), MapKind_MetaArray));
[email protected]
    33
    if (!obj)
[email protected]
    34
        return NULL;
[email protected]
    35
[email protected]
    36
    Local<ArrayMap> map(zone, ArrayMap::cast(obj));
[email protected]
    37
    map->type_ = type;
[email protected]
    38
    return map;
[email protected]
    39
}
[email protected]
    40
[email protected]
    41
ArrayMap *
[email protected]
    42
ArrayMap::NewDependent(Zone *zone, Handle<ArrayType> type)
[email protected]
    43
{
[email protected]
    44
    Local<Map> obj(zone, zone->allocateMap(MapKind_DependentArray, sizeof(ArrayMap), MapKind_MetaArray));
[email protected]
    45
    if (!obj)
[email protected]
    46
        return NULL;
[email protected]
    47
[email protected]
    48
    Local<ArrayMap> map(zone, ArrayMap::cast(obj));
[email protected]
    49
    map->type_ = type;
[email protected]
    50
    return map;
[email protected]
    51
}
[email protected]
    52
[email protected]
    53
Array *
[email protected]
    54
Array::NewRaw(Zone *zone, Handle<ArrayMap> map, unsigned nelements, Heap::Tenure tenure)
[email protected]
    55
{
[email protected]
    56
    assert(!map->type()->isFixedLength() || nelements == map->type()->fixedLength());
[email protected]
    57
[email protected]
    58
    if (nelements > (INT_MAX / SizeForElement(map->type()))) {
[email protected]
    59
        zone->reportError(Message_ArraySizeTooBig);
[email protected]
    60
        return NULL;
[email protected]
    61
    }
[email protected]
    62
[email protected]
    63
    size_t bytes = sizeof(Array);
[email protected]
    64
    if (map->type()->hasInlineElements())
[email protected]
    65
        bytes += SizeForElement(map->type()) * nelements;
[email protected]
    66
[email protected]
    67
    Local<Array> array(zone, Array::cast(zone->allocate(map, bytes, tenure)));
[email protected]
    68
    if (!array)
[email protected]
    69
        return NULL;
[email protected]
    70
[email protected]
    71
    array->length_ = 0;
[email protected]
    72
    array->elements_ = NULL;
[email protected]
    73
[email protected]
    74
    if (map->type()->hasInlineElements()) {
[email protected]
    75
        // This must be a fixed array containing no traceables.
[email protected]
    76
        assert(nelements > 0);
[email protected]
    77
        assert(map->type()->isFixedLength());
[email protected]
    78
        assert(!map->type()->contained()->isTraceable());
[email protected]
    79
[email protected]
    80
        // Compute an interior |elements_| pointer, such that if elements_
[email protected]
    81
        // is accessed like a FixedArray, we reach the appropriate vector.
[email protected]
    82
        array->elements_ = Address((Array *)array + 1) - ByteArray::offsetToElements();
[email protected]
    83
        array->length_ = nelements;
[email protected]
    84
        memset(array->bytes(), 0, SizeForElement(map->type()) * nelements);
[email protected]
    85
        return array;
[email protected]
    86
    }
[email protected]
    87
[email protected]
    88
    // If there is nothing to allocate, we don't bother creating elements yet.
[email protected]
    89
    if (!nelements)
[email protected]
    90
        return array;
[email protected]
    91
[email protected]
    92
    if (!map->type()->contained()->isTraceable()) {
[email protected]
    93
        size_t nbytes = SizeForElement(map->type()) * nelements;
[email protected]
    94
        Local<ByteArray> elements(zone, ByteArray::New(zone, nbytes, tenure));
[email protected]
    95
        if (!elements)
[email protected]
    96
            return NULL;
[email protected]
    97
[email protected]
    98
        array->updateLengthAndElements(zone, nelements, elements);
[email protected]
    99
        return array;
[email protected]
   100
    }
[email protected]
   101
[email protected]
   102
    Local<FixedArray> elements(zone, FixedArray::New(zone, nelements, tenure));
[email protected]
   103
    if (!elements)
[email protected]
   104
        return NULL;
[email protected]
   105
[email protected]
   106
    array->updateLengthAndElements(zone, nelements, elements);
[email protected]
   107
[email protected]
   108
    // If this is an array of structs, we're required to allocate those structs now.
[email protected]
   109
    if (map->type()->contained()->isStruct()) {
[email protected]
   110
        Local<StructType> childType(zone, StructType::cast(map->type()->contained()));
[email protected]
   111
        Local<StructMap> childMap(zone, childType->newMap());
[email protected]
   112
        Local<Struct> child(zone);
[email protected]
   113
        for (unsigned i = 0; i < nelements; i++) {
[email protected]
   114
            child = Struct::New(zone, childMap, tenure);
[email protected]
   115
            if (!child)
[email protected]
   116
                return NULL;
[email protected]
   117
[email protected]
   118
            elements->set(zone, i, child);
[email protected]
   119
        }
[email protected]
   120
    }
[email protected]
   121
[email protected]
   122
    return array;
[email protected]
   123
}
[email protected]
   124
[email protected]
   125
static Array *
[email protected]
   126
ConstructSizedArray(Zone *zone, Handle<ArrayMap> map, int dims[MAX_ARRAY_DEPTH],
[email protected]
   127
                    unsigned level, Heap::Tenure tenure)
[email protected]
   128
{
[email protected]
   129
    Local<Array> array(zone, Array::NewRaw(zone, map, dims[level], tenure));
[email protected]
   130
    if (!array)
[email protected]
   131
        return NULL;
[email protected]
   132
[email protected]
   133
    if (map->type()->contained()->isArray()) {
[email protected]
   134
        Local<ArrayType> childType(zone, ArrayType::cast(map->type()->contained()));
[email protected]
   135
        Local<ArrayMap> childMap(zone, childType->newMap());
[email protected]
   136
        Local<Array> child(zone);
[email protected]
   137
[email protected]
   138
        for (unsigned i = 0; i < unsigned(dims[level]); i++) {
[email protected]
   139
            child = ConstructSizedArray(zone, childMap, dims, level + 1, tenure);
[email protected]
   140
            if (!child)
[email protected]
   141
                return NULL;
[email protected]
   142
[email protected]
   143
            array->writeObject(zone, i, child);
[email protected]
   144
        }
[email protected]
   145
    }
[email protected]
   146
[email protected]
   147
    return array;
[email protected]
   148
}
[email protected]
   149
[email protected]
   150
Array *
[email protected]
   151
Array::NewSized(Zone *zone, Handle<ArrayMap> map, int dims[MAX_ARRAY_DEPTH], Heap::Tenure tenure)
[email protected]
   152
{
[email protected]
   153
    for (size_t i = 0; i < map->type()->levels(); i++) {
[email protected]
   154
        if (dims[i] < 0) {
[email protected]
   155
            zone->reportError(Message_InvalidDimensionSize, dims[i], i);
[email protected]
   156
            return NULL;
[email protected]
   157
        }
[email protected]
   158
    }
[email protected]
   159
[email protected]
   160
    return ConstructSizedArray(zone, map, dims, 0, tenure);
[email protected]87
   161
}
[email protected]
   162
[email protected]
   163
static Array *
[email protected]
   164
ConstructFixedArray(Zone *zone, Handle<ArrayMap> map, Heap::Tenure tenure)
[email protected]
   165
{
[email protected]
   166
    unsigned length = map->type()->fixedLength();
[email protected]
   167
    Local<Array> array(zone, Array::NewRaw(zone, map, length, tenure));
[email protected]
   168
    if (!array)
[email protected]
   169
        return NULL;
[email protected]
   170
[email protected]
   171
    if (map->type()->contained()->isArray()) {
[email protected]
   172
        Local<ArrayType> childType(zone, ArrayType::cast(map->type()->contained()));
[email protected]
   173
        Local<ArrayMap> childMap(zone, childType->newMap());
[email protected]
   174
        Local<Array> child(zone);
[email protected]
   175
[email protected]
   176
        if (childMap->type()->isFixedLength()) {
[email protected]
   177
            for (unsigned i = 0; i < length; i++) {
[email protected]
   178
                child = ConstructFixedArray(zone, childMap, tenure);
[email protected]
   179
                if (!child)
[email protected]
   180
                    return NULL;
[email protected]
   181
[email protected]
   182
                array->writeObject(zone, i, child);
[email protected]
   183
            }
[email protected]
   184
        } else {
[email protected]
   185
            for (unsigned i = 0; i < length; i++) {
[email protected]
   186
                child = Array::NewRaw(zone, childMap, 0, tenure);
[email protected]
   187
                if (!child)
[email protected]
   188
                    return NULL;
[email protected]
   189
[email protected]
   190
                array->writeObject(zone, i, child);
[email protected]
   191
            }
[email protected]
   192
        }
[email protected]
   193
    }
[email protected]
   194
[email protected]
   195
    return array;
[email protected]
   196
}
[email protected]
   197
[email protected]
   198
Array *
[email protected]
   199
Array::NewFixed(Zone *zone, Handle<ArrayMap> map, Heap::Tenure tenure)
[email protected]
   200
{
[email protected]
   201
    return ConstructFixedArray(zone, map, tenure);
[email protected]
   202
}
[email protected]
   203
[email protected]
   204
Array *
[email protected]
   205
Array::NewString(Zone *zone, Handle<ArrayMap> map, char *buffer, size_t length, Heap::Tenure tenure)
[email protected]
   206
{
[email protected]
   207
    assert(map->type()->isCharArray());
[email protected]
   208
[email protected]
   209
    Local<Array> array(zone);
[email protected]
   210
    
[email protected]
   211
    if (map->type()->isFixedLength())
[email protected]
   212
        array = Array::NewFixed(zone, map, tenure);
[email protected]
   213
    else
[email protected]
   214
        array = Array::New1D(zone, map, length + 1, tenure);
[email protected]
   215
    if (!array)
[email protected]
   216
        return NULL;
[email protected]
   217
[email protected]
   218
    assert(array->length() >= length + 1);
[email protected]
   219
    memcpy(array->chars(), buffer, length + 1);
[email protected]
   220
    return array;
[email protected]
   221
}
[email protected]
   222
[email protected]
   223
Array *
[email protected]
   224
Array::New1D(Zone *zone, Handle<ArrayMap> map, uint32 elements, Heap::Tenure tenure)
[email protected]
   225
{
[email protected]
   226
    assert(map->type()->levels());
[email protected]
   227
    return Array::NewRaw(zone, map, elements, tenure);
[email protected]
   228
}
[email protected]
   229
[email protected]
   230
Array *
[email protected]
   231
Array::NewEmpty(Zone *zone, Handle<ArrayMap> map, Heap::Tenure tenure)
[email protected]
   232
{
[email protected]
   233
    assert(!map->type()->isFixedLength());
[email protected]
   234
[email protected]
   235
    return Array::NewRaw(zone, map, 0, tenure);
[email protected]
   236
}
[email protected]
   237
[email protected]
   238
Array *
[email protected]
   239
Array::NewExternal(Zone *zone, Handle<ArrayMap> map, void *buffer, unsigned length,
[email protected]
   240
                   Heap::Tenure tenure)
[email protected]
   241
{
[email protected]
   242
    Local<Array> array(zone, Array::cast(zone->allocate(map, sizeof(Array), tenure)));
[email protected]
   243
    if (!array)
[email protected]
   244
        return NULL;
[email protected]
   245
[email protected]
   246
    array->length_ = length;
[email protected]
   247
    array->elements_ = Address(buffer) - ByteArray::offsetToElements();
[email protected]
   248
    return array;
[email protected]
   249
}
[email protected]
   250
[email protected]
   251
static bool
[email protected]
   252
CopyArrayElements(Zone *zone, Handle<Type> contained, Handle<Array> dest, Handle<Array> source)
[email protected]
   253
{
[email protected]
   254
    if (contained->isTraceable()) {
[email protected]
   255
        if (contained->isStruct()) {
[email protected]
   256
            assert(dest->type()->contained() == contained);
[email protected]
   257
            assert(source->length() == dest->length());
[email protected]
   258
[email protected]
   259
            Local<Struct> left(zone);
[email protected]
   260
            Local<Struct> right(zone);
[email protected]
   261
            for (unsigned i = 0; i < source->length(); i++) {
[email protected]
   262
                left = Struct::cast(dest->readObject(i));
[email protected]
   263
                right = Struct::cast(source->readObject(i));
[email protected]
   264
                if (!Struct::Copy(zone, left, right))
[email protected]
   265
                    return false;
[email protected]
   266
            }
[email protected]
   267
        } else if (contained->isArray() && ArrayType::cast(contained)->isFixedLength()) {
[email protected]
   268
            assert(ArrayType::cast(source->type())->fixedLength() ==
[email protected]
   269
                   ArrayType::cast(contained)->fixedLength());
[email protected]
   270
[email protected]
   271
            Local<Array> left(zone);
[email protected]
   272
            Local<Array> right(zone);
[email protected]
   273
            for (unsigned i = 0; i < source->length(); i++) {
[email protected]
   274
                left = Array::cast(dest->readObject(i));
[email protected]
   275
                right = Array::cast(source->readObject(i));
[email protected]
   276
                if (!Array::ShallowCopy(zone, left, right))
[email protected]
   277
                    return false;
[email protected]
   278
            }
[email protected]
   279
        } else {
[email protected]
   280
            assert(dest->length() == source->length());
[email protected]
   281
            for (unsigned i = 0; i < source->length(); i++)
[email protected]
   282
                dest->writeObject(zone, i, source->readObject(i));
[email protected]
   283
        }
[email protected]
   284
    } else {
[email protected]
   285
        assert(contained->pod() == dest->type()->contained()->pod());
[email protected]
   286
        assert(contained->pod() == PrimitiveType_Char
[email protected]
   287
               ? source->length() <= dest->length()
[email protected]
   288
               : source->length() == dest->length());
[email protected]
   289
    
[email protected]
   290
        assert(dest->length());
[email protected]
   291
        memcpy(dest->bytes(), source->bytes(), source->length() * Array::SizeForElement(dest->type()));
[email protected]
   292
    }
[email protected]
   293
    return true;
[email protected]
   294
}
[email protected]
   295
[email protected]
   296
// Shallow copy an array. Fixed slots in the destination are copied from
[email protected]
   297
// the source, but otherwise, references are assigned.
[email protected]
   298
bool
[email protected]
   299
Array::ShallowCopy(Zone *zone, Handle<Array> dest, Handle<Array> source)
[email protected]
   300
{
[email protected]
   301
    Local<Type> contained(zone, dest->type()->contained());
[email protected]
   302
[email protected]
   303
    return CopyArrayElements(zone, contained, dest, source);
[email protected]
   304
}
[email protected]
   305
[email protected]
   306
Array *
[email protected]
   307
Array::DeepCopy(Zone *zone, Handle<Array> source, Heap::Tenure tenure)
[email protected]
   308
{
[email protected]
   309
    Local<ArrayMap> map(zone, ArrayMap::cast(source->map()));
[email protected]
   310
[email protected]
   311
    Local<Array> dest(zone, Array::NewRaw(zone, map, source->length(), tenure));
[email protected]
   312
    if (!dest)
[email protected]
   313
        return NULL;
[email protected]
   314
[email protected]
   315
    Local<Type> contained(zone, source->type()->contained());
[email protected]
   316
    if (contained->isArray()) {
[email protected]
   317
        assert(false);
[email protected]
   318
        Local<Array> sub(zone);
[email protected]
   319
        for (size_t i = 0; i < source->length(); i++) {
[email protected]
   320
            sub = Array::cast(source->readObject(i));
[email protected]
   321
            sub = DeepCopy(zone, sub, tenure);
[email protected]
   322
            if (!sub)
[email protected]
   323
                return NULL;
[email protected]
   324
            dest->writeObject(zone, i, sub);
[email protected]
   325
        }
[email protected]
   326
    } else {
[email protected]
   327
        if (!CopyArrayElements(zone, contained, dest, source))
[email protected]
   328
            return NULL;
[email protected]
   329
    }
[email protected]
   330
[email protected]
   331
    return dest;
[email protected]
   332
}
[email protected]
   333
[email protected]
   334
Array *
[email protected]
   335
DependentArray::New(Zone *zone, Handle<Array> source, Handle<ArrayMap> map, unsigned index)
[email protected]
   336
{
[email protected]
   337
    Local<ArrayType> sourcetype(zone, source->type());
[email protected]
   338
[email protected]
   339
    // Right now we only support char arrays, to avoid nasty deep cloning
[email protected]
   340
    // and to maybe cut off this feature as far as we can.
[email protected]
   341
    assert(sourcetype->isCharArray());
[email protected]
   342
    assert(map->type()->isCharArray());
[email protected]
   343
[email protected]
   344
    // We allow taking 0-length dependent strings. It's safe because any reads
[email protected]
   345
    // or writes will fail.
[email protected]
   346
    assert(index <= source->length());
[email protected]
   347
[email protected]
   348
    unsigned newlen = source->length() - index;
[email protected]
   349
    unsigned eltsize = SizeForElement(sourcetype);
[email protected]
   350
    
[email protected]
   351
    if (!sourcetype->isFixedLength()) {
[email protected]
   352
        // Simple case, just copy the array.
[email protected]
   353
        Local<ArrayMap> map(zone, sourcetype->newMap());
[email protected]
   354
        
[email protected]
   355
        Local<Array> dest(zone, Array::NewRaw(zone, map, newlen, Heap::Tenure_Default));
[email protected]
   356
        if (!dest)
[email protected]
   357
            return NULL;
[email protected]
   358
[email protected]
   359
        memcpy(dest->bytes(),
[email protected]
   360
               (Address)source->bytes() + (index * eltsize),
[email protected]
   361
               newlen * eltsize);
[email protected]
   362
        return dest;
[email protected]
   363
    }
[email protected]
   364
[email protected]
   365
    Local<DependentArray> array(zone, DependentArray::cast(zone->allocate(map, sizeof(DependentArray), Heap::Tenure_Default)));
[email protected]
   366
    if (!array)
[email protected]
   367
        return NULL;
[email protected]
   368
[email protected]
   369
    // :GC: This is currently not safe for moving GC! Although we will mark
[email protected]
   370
    // the object owning the interior pointer, the interior pointer could be
[email protected]
   371
    // moved later. We will eventually need some way of dealing with this.
[email protected]
   372
    Address elements = Address(source->bytes()) + (index * eltsize);
[email protected]
   373
[email protected]
   374
    array->root_ = source;
[email protected]
   375
    array->length_ = newlen;
[email protected]
   376
    array->elements_ = elements - ByteArray::offsetToElements();
[email protected]
   377
    return array;
[email protected]
   378
}