jsarray.c

来自「java script test programing source code」· C语言 代码 · 共 1,865 行 · 第 1/4 页

}

JSClass js_ArrayClass = {
    "Array",
    JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
    array_addProperty, JS_PropertyStub,   JS_PropertyStub,   JS_PropertyStub,
    JS_EnumerateStub,  JS_ResolveStub,    array_convert,     JS_FinalizeStub,
    JSCLASS_NO_OPTIONAL_MEMBERS
};

enum ArrayToStringOp {
    TO_STRING,
    TO_LOCALE_STRING,
    TO_SOURCE
};

/*
 * When op is TO_STRING or TO_LOCALE_STRING sep indicates a separator to use
 * or "," when sep is NULL.
 * When op is TO_SOURCE sep must be NULL.
 */
static JSBool
array_join_sub(JSContext *cx, JSObject *obj, enum ArrayToStringOp op,
               JSString *sep, jsval *rval)
{
    JSBool ok, hole;
    jsuint length, index;
    jschar *chars, *ochars;
    size_t nchars, growth, seplen, tmplen, extratail;
    const jschar *sepstr;
    JSString *str;
    JSHashEntry *he;
    JSTempValueRooter tvr;
    JSAtom *atom;
    int stackDummy;

    if (!JS_CHECK_STACK_SIZE(cx, stackDummy)) {
        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_OVER_RECURSED);
        return JS_FALSE;
    }

    ok = js_GetLengthProperty(cx, obj, &length);
    if (!ok)
        return JS_FALSE;

    he = js_EnterSharpObject(cx, obj, NULL, &chars);
    if (!he)
        return JS_FALSE;
#ifdef DEBUG
    growth = (size_t) -1;
#endif

    if (op == TO_SOURCE) {
        if (IS_SHARP(he)) {
#if JS_HAS_SHARP_VARS
            nchars = js_strlen(chars);
#else
            chars[0] = '[';
            chars[1] = ']';
            chars[2] = 0;
            nchars = 2;
#endif
            goto make_string;
        }

        /*
         * Always allocate 2 extra chars for closing ']' and terminating 0
         * and then preallocate 1 + extratail to include starting '['.
         */
        extratail = 2;
        growth = (1 + extratail) * sizeof(jschar);
        if (!chars) {
            nchars = 0;
            chars = (jschar *) malloc(growth);
            if (!chars)
                goto done;
        } else {
            MAKE_SHARP(he);
            nchars = js_strlen(chars);
            growth += nchars * sizeof(jschar);
            chars = (jschar *)realloc((ochars = chars), growth);
            if (!chars) {
                free(ochars);
                goto done;
            }
        }
        chars[nchars++] = '[';
        JS_ASSERT(sep == NULL);
        sepstr = NULL;  /* indicates to use ", " as separator */
        seplen = 2;
    } else {
        /*
         * Free any sharp variable definition in chars.  Normally, we would
         * MAKE_SHARP(he) so that only the first sharp variable annotation is
         * a definition, and all the rest are references, but in the current
         * case of (op != TO_SOURCE), we don't need chars at all.
         */
        if (chars)
            JS_free(cx, chars);
        chars = NULL;
        nchars = 0;
        extratail = 1;  /* allocate extra char for terminating 0 */

        /* Return the empty string on a cycle as well as on empty join. */
        if (IS_BUSY(he) || length == 0) {
            js_LeaveSharpObject(cx, NULL);
            *rval = JS_GetEmptyStringValue(cx);
            return ok;
        }

        /* Flag he as BUSY so we can distinguish a cycle from a join-point. */
        MAKE_BUSY(he);

        if (sep) {
            sepstr = JSSTRING_CHARS(sep);
            seplen = JSSTRING_LENGTH(sep);
        } else {
            sepstr = NULL;      /* indicates to use "," as separator */
            seplen = 1;
        }
    }

    /* Use rval to locally root each element value as we loop and convert. */
#define v (*rval)

    for (index = 0; index < length; index++) {
        ok = GetArrayElement(cx, obj, index, &hole, &v);
        if (!ok)
            goto done;
        if (hole ||
            (op != TO_SOURCE && (JSVAL_IS_VOID(v) || JSVAL_IS_NULL(v)))) {
            str = cx->runtime->emptyString;
        } else {
            if (op == TO_LOCALE_STRING) {
                atom = cx->runtime->atomState.toLocaleStringAtom;
                JS_PUSH_TEMP_ROOT_OBJECT(cx, NULL, &tvr);
                ok = js_ValueToObject(cx, v, &tvr.u.object) &&
                     js_TryMethod(cx, tvr.u.object, atom, 0, NULL, &v);
                JS_POP_TEMP_ROOT(cx, &tvr);
                if (!ok)
                    goto done;
                str = js_ValueToString(cx, v);
            } else if (op == TO_STRING) {
                str = js_ValueToString(cx, v);
            } else {
                JS_ASSERT(op == TO_SOURCE);
                str = js_ValueToSource(cx, v);
            }
            if (!str) {
                ok = JS_FALSE;
                goto done;
            }
        }

        /*
         * Do not append separator after the last element unless it is a hole
         * and we are in toSource. In that case we append single ",".
         */
        if (index + 1 == length)
            seplen = (hole && op == TO_SOURCE) ? 1 : 0;

        /* Allocate 1 at end for closing bracket and zero. */
        tmplen = JSSTRING_LENGTH(str);
        growth = nchars + tmplen + seplen + extratail;
        if (nchars > growth || tmplen > growth ||
            growth > (size_t)-1 / sizeof(jschar)) {
            if (chars) {
                free(chars);
                chars = NULL;
            }
            goto done;
        }
        growth *= sizeof(jschar);
        if (!chars) {
            chars = (jschar *) malloc(growth);
            if (!chars)
                goto done;
        } else {
            chars = (jschar *) realloc((ochars = chars), growth);
            if (!chars) {
                free(ochars);
                goto done;
            }
        }

        js_strncpy(&chars[nchars], JSSTRING_CHARS(str), tmplen);
        nchars += tmplen;

        if (seplen) {
            if (sepstr) {
                js_strncpy(&chars[nchars], sepstr, seplen);
            } else {
                JS_ASSERT(seplen == 1 || seplen == 2);
                chars[nchars] = ',';
                if (seplen == 2)
                    chars[nchars + 1] = ' ';
            }
            nchars += seplen;
        }
    }

  done:
    if (op == TO_SOURCE) {
        if (chars)
            chars[nchars++] = ']';
    } else {
        CLEAR_BUSY(he);
    }
    js_LeaveSharpObject(cx, NULL);
    if (!ok) {
        if (chars)
            free(chars);
        return ok;
    }

#undef v

  make_string:
    if (!chars) {
        JS_ReportOutOfMemory(cx);
        return JS_FALSE;
    }
    chars[nchars] = 0;
    JS_ASSERT(growth == (size_t)-1 || (nchars + 1) * sizeof(jschar) == growth);
    str = js_NewString(cx, chars, nchars, 0);
    if (!str) {
        free(chars);
        return JS_FALSE;
    }
    *rval = STRING_TO_JSVAL(str);
    return JS_TRUE;
}

#if JS_HAS_TOSOURCE
static JSBool
array_toSource(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
               jsval *rval)
{
    return array_join_sub(cx, obj, TO_SOURCE, NULL, rval);
}
#endif

static JSBool
array_toString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
               jsval *rval)
{
    return array_join_sub(cx, obj, TO_STRING, NULL, rval);
}

static JSBool
array_toLocaleString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
               jsval *rval)
{
    /*
     *  Passing comma here as the separator. Need a way to get a
     *  locale-specific version.
     */
    return array_join_sub(cx, obj, TO_LOCALE_STRING, NULL, rval);
}

static JSBool
InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint end,
                  jsval *vector)
{
    while (start != end) {
        if (!SetArrayElement(cx, obj, start++, *vector++))
            return JS_FALSE;
    }
    return JS_TRUE;
}

static JSBool
InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, jsval *vector)
{
    jsval v;
    jsid id;

    if (!IndexToValue(cx, length, &v))
        return JS_FALSE;
    id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
    if (!OBJ_DEFINE_PROPERTY(cx, obj, id, v,
                             array_length_getter, array_length_setter,
                             JSPROP_PERMANENT,
                             NULL)) {
          return JS_FALSE;
    }
    if (!vector)
        return JS_TRUE;
    return InitArrayElements(cx, obj, 0, length, vector);
}

/*
 * Perl-inspired join, reverse, and sort.
 */
static JSBool
array_join(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
{
    JSString *str;

    if (JSVAL_IS_VOID(argv[0])) {
        str = NULL;
    } else {
        str = js_ValueToString(cx, argv[0]);
        if (!str)
            return JS_FALSE;
        argv[0] = STRING_TO_JSVAL(str);
    }
    return array_join_sub(cx, obj, TO_STRING, str, rval);
}

static JSBool
array_reverse(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
              jsval *rval)
{
    jsuint len, half, i;
    JSBool hole, hole2;
    jsval *tmproot, *tmproot2;

    if (!js_GetLengthProperty(cx, obj, &len))
        return JS_FALSE;

    /*
     * Use argv[argc] and argv[argc + 1] as local roots to hold temporarily
     * array elements for GC-safe swap.
     */
    tmproot = argv + argc;
    tmproot2 = argv + argc + 1;
    half = len / 2;
    for (i = 0; i < half; i++) {
        if (!GetArrayElement(cx, obj, i, &hole, tmproot) ||
            !GetArrayElement(cx, obj, len - i - 1, &hole2, tmproot2) ||
            !SetOrDeleteArrayElement(cx, obj, len - i - 1, hole, *tmproot) ||
            !SetOrDeleteArrayElement(cx, obj, i, hole2, *tmproot2)) {
            return JS_FALSE;
        }
    }
    *rval = OBJECT_TO_JSVAL(obj);
    return JS_TRUE;
}

typedef struct HSortArgs {
    void         *vec;
    size_t       elsize;
    void         *pivot;
    JSComparator cmp;
    void         *arg;
    JSBool       fastcopy;
} HSortArgs;

static JSBool
sort_compare(void *arg, const void *a, const void *b, int *result);

static int
sort_compare_strings(void *arg, const void *a, const void *b, int *result);

static JSBool
HeapSortHelper(JSBool building, HSortArgs *hsa, size_t lo, size_t hi)
{
    void *pivot, *vec, *vec2, *arg, *a, *b;
    size_t elsize;
    JSComparator cmp;
    JSBool fastcopy;
    size_t j, hiDiv2;
    int cmp_result;

    pivot = hsa->pivot;
    vec = hsa->vec;
    elsize = hsa->elsize;
    vec2 =  (char *)vec - 2 * elsize;
    cmp = hsa->cmp;
    arg = hsa->arg;

    fastcopy = hsa->fastcopy;
#define MEMCPY(p,q,n) \
    (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
#define CALL_CMP(a, b) \
    if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;

    if (lo == 1) {
        j = 2;
        b = (char *)vec + elsize;
        if (j < hi) {
            CALL_CMP(vec, b);
            if (cmp_result < 0)
                j++;
        }
        a = (char *)vec + (hi - 1) * elsize;
        b = (char *)vec2 + j * elsize;

        /*
         * During sorting phase b points to a member of heap that cannot be
         * bigger then biggest of vec[0] and vec[1], and cmp(a, b, arg) <= 0
         * always holds.
         */
        if (building || hi == 2) {
            CALL_CMP(a, b);
            if (cmp_result >= 0)
                return JS_TRUE;
        }

        MEMCPY(pivot, a, elsize);
        MEMCPY(a, b, elsize);
        lo = j;
    } else {
        a = (char *)vec2 + lo * elsize;
        MEMCPY(pivot, a, elsize);
    }

    hiDiv2 = hi/2;
    while (lo <= hiDiv2) {
        j = lo + lo;
        a = (char *)vec2 + j * elsize;
        b = (char *)vec + (j - 1) * elsize;
        if (j < hi) {
            CALL_CMP(a, b);
            if (cmp_result < 0)
                j++;
        }
        b = (char *)vec2 + j * elsize;
        CALL_CMP(pivot, b);
        if (cmp_result >= 0)
            break;

        a = (char *)vec2 + lo * elsize;
        MEMCPY(a, b, elsize);
        lo = j;
    }

    a = (char *)vec2 + lo * elsize;
    MEMCPY(a, pivot, elsize);

    return JS_TRUE;

#undef CALL_CMP
#undef MEMCPY

}

JSBool
js_HeapSort(void *vec, size_t nel, void *pivot, size_t elsize,
            JSComparator cmp, void *arg)
{
    HSortArgs hsa;
    size_t i;

    hsa.vec = vec;
    hsa.elsize = elsize;
    hsa.pivot = pivot;
    hsa.cmp = cmp;
    hsa.arg = arg;
    hsa.fastcopy = (cmp == sort_compare || cmp == sort_compare_strings);

    for (i = nel/2; i != 0; i--) {
        if (!HeapSortHelper(JS_TRUE, &hsa, i, nel))
            return JS_FALSE;
    }
    while (nel > 2) {
        if (!HeapSortHelper(JS_FALSE, &hsa, 1, --nel))
            return JS_FALSE;
    }

    return JS_TRUE;
}

typedef struct CompareArgs {
    JSContext   *context;
    jsval       fval;