From 2d99ce1a154fb40c8044a3a534f1b2b0434e73e7 Mon Sep 17 00:00:00 2001 From: Igor Sysoev Date: Thu, 11 Aug 2016 10:58:29 +0300 Subject: [PATCH] Array.sort() function. --- njs/njs_array.c | 159 +++++++++++++++++++++++++++++++++++++++ njs/test/njs_unit_test.c | 31 ++++++++ 2 files changed, 190 insertions(+) diff --git a/njs/njs_array.c b/njs/njs_array.c index 292c5457..b280a82f 100644 --- a/njs/njs_array.c +++ b/njs/njs_array.c @@ -51,6 +51,23 @@ typedef struct { } njs_array_iter_t; +typedef struct { + union { + njs_continuation_t cont; + u_char padding[NJS_CONTINUATION_SIZE]; + } u; + /* + * This retval value must be aligned so the continuation is padded + * to aligned size. + */ + njs_value_t retval; + + njs_function_t *function; + int32_t index; + uint32_t current; +} njs_array_sort_t; + + static njs_ret_t njs_array_prototype_to_string_continuation(njs_vm_t *vm, njs_value_t *args, nxt_uint_t nargs, njs_index_t retval); @@ -81,6 +98,8 @@ static nxt_noinline uint32_t njs_array_iterator_next(njs_array_t *array, static nxt_noinline njs_ret_t njs_array_iterator_apply(njs_vm_t *vm, njs_array_iter_t *iter, njs_value_t *args, nxt_uint_t nargs); static uint32_t njs_array_reduce_right_next(njs_array_t *array, int32_t n); +static njs_ret_t njs_array_prototype_sort_cont(njs_vm_t *vm, njs_value_t *args, + nxt_uint_t nargs, njs_index_t unused); nxt_noinline njs_array_t * @@ -1477,6 +1496,139 @@ njs_array_reduce_right_next(njs_array_t *array, int32_t n) } +static njs_ret_t +njs_array_string_sort(njs_vm_t *vm, njs_value_t *args, + nxt_uint_t nargs, njs_index_t unused) +{ + nxt_int_t ret; + nxt_uint_t i; + + for (i = 1; i < nargs; i++) { + if (!njs_is_string(&args[i])) { + vm->frame->trap_scratch.data.u.value = &args[i]; + return NJS_TRAP_STRING_ARG; + } + } + + ret = njs_string_cmp(&args[1], &args[2]); + + njs_number_set(&vm->retval, ret); + + return NXT_OK; +} + + +static const njs_function_t njs_array_string_sort_function = { + .object.shared = 1, + .native = 1, + .continuation_size = NJS_CONTINUATION_SIZE, + .args_types = { NJS_SKIP_ARG, NJS_STRING_ARG, NJS_STRING_ARG }, + .args_offset = 1, + .u.native = njs_array_string_sort, +}; + + +static njs_ret_t +njs_array_prototype_sort(njs_vm_t *vm, njs_value_t *args, + nxt_uint_t nargs, njs_index_t unused) +{ + njs_array_sort_t *sort; + + if (njs_is_array(&args[0]) && args[0].data.u.array->length > 1) { + + sort = njs_continuation(vm->frame); + sort->u.cont.function = njs_array_prototype_sort_cont; + sort->current = 0; + sort->retval = njs_value_zero; + + if (nargs > 1 && njs_is_function(&args[1])) { + sort->function = args[1].data.u.function; + + } else { + sort->function = (njs_function_t *) &njs_array_string_sort_function; + } + + return njs_array_prototype_sort_cont(vm, args, nargs, unused); + } + + vm->retval = args[0]; + + return NXT_OK; +} + + +static njs_ret_t +njs_array_prototype_sort_cont(njs_vm_t *vm, njs_value_t *args, + nxt_uint_t nargs, njs_index_t unused) +{ + nxt_int_t n; + njs_array_t *array; + njs_value_t value, *start, arguments[3]; + njs_array_sort_t *sort; + + array = args[0].data.u.array; + start = array->start; + + sort = njs_continuation(vm->frame); + + if (njs_is_number(&sort->retval)) { + + /* + * The sort function is impelemented with the insertion sort algorithm. + * Its worst and average computational complexity is O^2. This point + * should be considired as return point from comparison function so + * "goto next" moves control to the appropriate step of the algorithm. + * The first iteration also goes there because sort->retval is zero. + */ + if (sort->retval.data.u.number <= 0) { + goto next; + } + + n = sort->index; + + swap: + + value = start[n]; + start[n] = start[n - 1]; + n--; + start[n] = value; + + do { + if (n > 0) { + + if (njs_is_valid(&start[n]) && njs_is_valid(&start[n - 1])) { + arguments[0] = njs_value_void; + + /* GC: array elt, array */ + arguments[1] = start[n - 1]; + arguments[2] = start[n]; + + sort->index = n; + + return njs_function_apply(vm, sort->function, arguments, 3, + (njs_index_t) &sort->retval); + } + + if (!njs_is_valid(&start[n - 1]) && njs_is_valid(&start[n])) { + /* Move invalid values to the end of array. */ + goto swap; + } + } + + next: + + sort->current++; + n = sort->current; + + } while (sort->current < array->length); + } + + vm->retval = args[0]; + + return NXT_OK; +} + + static const njs_object_prop_t njs_array_prototype_properties[] = { { @@ -1613,6 +1765,13 @@ static const njs_object_prop_t njs_array_prototype_properties[] = .value = njs_native_function(njs_array_prototype_reduce_right, njs_continuation_size(njs_array_iter_t), 0), }, + + { + .type = NJS_METHOD, + .name = njs_string("sort"), + .value = njs_native_function(njs_array_prototype_sort, + njs_continuation_size(njs_array_iter_t), 0), + }, }; diff --git a/njs/test/njs_unit_test.c b/njs/test/njs_unit_test.c index d191e7ec..e6c91db6 100644 --- a/njs/test/njs_unit_test.c +++ b/njs/test/njs_unit_test.c @@ -2517,6 +2517,37 @@ static njs_unit_test_t njs_test[] = " { a.shift(); return p + v }, 10)"), nxt_string("19") }, + { nxt_string("var a = ['1','2','3','4','5','6']; a.sort()"), + nxt_string("1,2,3,4,5,6") }, + + { nxt_string("var o = { toString: function() { return 5 } }" + "var a = [6,o,4,3,2,1]; a.sort()"), + nxt_string("1,2,3,4,5,6") }, + + { nxt_string("var a = [1,2,3,4,5,6];" + "a.sort(function(x, y) { return x - y })"), + nxt_string("1,2,3,4,5,6") }, + + { nxt_string("var a = [6,5,4,3,2,1];" + "a.sort(function(x, y) { return x - y })"), + nxt_string("1,2,3,4,5,6") }, + + { nxt_string("var a = [2,2,2,1,1,1];" + "a.sort(function(x, y) { return x - y })"), + nxt_string("1,1,1,2,2,2") }, + + { nxt_string("var a = [,,,2,2,2,1,1,1];" + "a.sort(function(x, y) { return x - y })"), + nxt_string("1,1,1,2,2,2,,,") }, + + { nxt_string("var a = [,,,,];" + "a.sort(function(x, y) { return x - y })"), + nxt_string(",,,") }, + + { nxt_string("var a = [1,,];" + "a.sort(function(x, y) { return x - y })"), + nxt_string("1,") }, + /* Strings. */ { nxt_string("var a = '0123456789' + '012345'" -- 2.47.3