From d656d150905e8b24deb95707d675db60776c737f Mon Sep 17 00:00:00 2001 From: Jo-Philipp Wich Date: Sun, 28 May 2023 20:50:31 +0200 Subject: types: implement ucv_object_sort() Introduce a new function `ucv_object_sort()` which works similar to `ucv_array_sort()` and allows reordering the keys of an object. Signed-off-by: Jo-Philipp Wich --- include/ucode/types.h | 1 + types.c | 42 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 43 insertions(+) diff --git a/include/ucode/types.h b/include/ucode/types.h index 22fe9a9..9827db5 100644 --- a/include/ucode/types.h +++ b/include/ucode/types.h @@ -369,6 +369,7 @@ size_t ucv_array_length(uc_value_t *); uc_value_t *ucv_object_new(uc_vm_t *); uc_value_t *ucv_object_get(uc_value_t *, const char *, bool *); bool ucv_object_add(uc_value_t *, const char *, uc_value_t *); +void ucv_object_sort(uc_value_t *, int (*)(const void *, const void *)); bool ucv_object_delete(uc_value_t *, const char *); size_t ucv_object_length(uc_value_t *); diff --git a/types.c b/types.c index 7bb67a6..5758f74 100644 --- a/types.c +++ b/types.c @@ -956,6 +956,48 @@ ucv_object_add(uc_value_t *uv, const char *key, uc_value_t *val) return true; } +void +ucv_object_sort(uc_value_t *uv, int (*cmp)(const void *, const void *)) +{ + uc_object_t *object = (uc_object_t *)uv; + struct lh_table *t; + struct lh_entry *e; + size_t i; + + struct { + struct lh_entry **entries; + size_t count; + } keys = { 0 }; + + if (ucv_type(uv) != UC_OBJECT || lh_table_length(object->table) <= 1) + return; + + for (t = object->table, e = t->head; e; e = e->next) + uc_vector_push(&keys, e); + + if (!keys.entries) + return; + + qsort(keys.entries, keys.count, sizeof(keys.entries[0]), cmp); + + for (i = 0; i < keys.count; i++) { + e = keys.entries[i]; + + if (i == 0) { + t->head = t->tail = e; + e->next = e->prev = NULL; + } + else { + t->tail->next = e; + e->prev = t->tail; + e->next = NULL; + t->tail = e; + } + } + + uc_vector_clear(&keys); +} + bool ucv_object_delete(uc_value_t *uv, const char *key) { -- cgit v1.2.3 From d72eebeb168b8b350f3f9fb8cded8075464eef10 Mon Sep 17 00:00:00 2001 From: Jo-Philipp Wich Date: Sun, 28 May 2023 20:52:10 +0200 Subject: lib: support object ordering in `uc_sort()` Extend `uc_sort()` to utilize `ucv_object_sort()` in order to support reordering object keys. Signed-off-by: Jo-Philipp Wich --- README.md | 44 +++++++++++++++++++++++--- lib.c | 72 ++++++++++++++++++++++++++++++++++++------ tests/custom/03_stdlib/16_sort | 16 ++++++++-- 3 files changed, 117 insertions(+), 15 deletions(-) diff --git a/README.md b/README.md index c64d015..455bc86 100644 --- a/README.md +++ b/README.md @@ -916,16 +916,52 @@ array was empty or if a non-array argument was passed. Return the sine of x, where x is given in radians. -#### 6.31. `sort(arr, fn)` +#### 6.31. `sort(val, fn)` -Sort the given array according to the given sort function. If no sort -function is provided, a default ascending sort order is applied. +Sort the given array or object according to the given comparison function. +If no comparison function is provided, a default lexical sort order is +applied. + +Values are sorted in-place, the given array of object value is modified +by this function. + +Sorting of objects is performed by reordering the internal key sequence +without modifying or rehashing the contained values themselves. Since +ucode maintains insertion order of keys within object values, this is +useful to sort object keys for output purposes. + +The comparison function is repeatedly invoked until the array values +or object key sequence is fully sorted. It should return a numeric +value less than, equal to or greater than zero when the first item +is smaller, equal or larger than the second one respectively. + +When sorting array values, the comparison function is invoked with two +array value arguments to compare against each other. + +When sorting object values, the comparison function is invoked with four +arguments; two keys to compare to each other as well as their +corresponding object values. + +Returns the given, ordered array or object value. + +Returns `null` if the given argument was neither an array nor object. + +Throws an exception if a non-callable custom comparison function was +provided or if the comparison function triggered an exception. ```javascript sort([8, 1, 5, 9]) // [1, 5, 8, 9] sort(["Bean", "Orange", "Apple"], function(a, b) { - return length(a) < length(b); + return length(a) - length(b); }) // ["Bean", "Apple", "Orange"] + +sort({ qrx: 1, foo: 2, abc: 3 }) // { "abc": 3, "foo": 2, "qrx": 1 } +sort({ a: 5, b: 3, c: 2, d: 4, e: 1 }, function(k1, k2, v1, v2) { + return v1 - v2; +}) // { "e": 1, "c": 2, "b": 3, "d": 4, "a": 5 } +sort({ "Bean": true, "Orange": true, "Apple": true }, function(k1, k2) { + return length(k1) - length(k2); +}) // { "Bean": true, "Apple": true, "Orange": true } ``` #### 6.32. `splice(arr, off, len, ...)` diff --git a/lib.c b/lib.c index a0a1b9b..93ea022 100644 --- a/lib.c +++ b/lib.c @@ -404,11 +404,8 @@ uc_rindex(uc_vm_t *vm, size_t nargs) } static bool -assert_mutable_array(uc_vm_t *vm, uc_value_t *val) +assert_mutable(uc_vm_t *vm, uc_value_t *val) { - if (ucv_type(val) != UC_ARRAY) - return false; - if (ucv_is_constant(val)) { uc_vm_raise_exception(vm, EXCEPTION_TYPE, "%s value is immutable", @@ -420,6 +417,15 @@ assert_mutable_array(uc_vm_t *vm, uc_value_t *val) return true; } +static bool +assert_mutable_array(uc_vm_t *vm, uc_value_t *val) +{ + if (ucv_type(val) != UC_ARRAY) + return false; + + return assert_mutable(vm, val); +} + static uc_value_t * uc_push(uc_vm_t *vm, size_t nargs) { @@ -894,7 +900,7 @@ default_cmp(uc_value_t *v1, uc_value_t *v2) } static int -sort_fn(const void *k1, const void *k2) +array_sort_fn(const void *k1, const void *k2) { uc_value_t *rv, *null = ucv_int64_new(0); uc_value_t * const *v1 = k1; @@ -928,21 +934,69 @@ sort_fn(const void *k1, const void *k2) return res; } +static int +object_sort_fn(const void *k1, const void *k2) +{ + uc_value_t *rv, *null = ucv_int64_new(0); + struct lh_entry * const *e1 = k1; + struct lh_entry * const *e2 = k2; + int res; + + if (!sort_ctx.fn) + return strcmp((char *)lh_entry_k(*e1), (char *)lh_entry_k(*e2)); + + if (sort_ctx.ex) + return 0; + + uc_vm_ctx_push(sort_ctx.vm); + uc_vm_stack_push(sort_ctx.vm, ucv_get(sort_ctx.fn)); + uc_vm_stack_push(sort_ctx.vm, ucv_string_new((char *)lh_entry_k(*e1))); + uc_vm_stack_push(sort_ctx.vm, ucv_string_new((char *)lh_entry_k(*e2))); + uc_vm_stack_push(sort_ctx.vm, ucv_get((uc_value_t *)lh_entry_v(*e1))); + uc_vm_stack_push(sort_ctx.vm, ucv_get((uc_value_t *)lh_entry_v(*e2))); + + if (uc_vm_call(sort_ctx.vm, true, 4)) { + sort_ctx.ex = true; + + return 0; + } + + rv = uc_vm_stack_pop(sort_ctx.vm); + + ucv_compare(0, rv, null, &res); + + ucv_put(null); + ucv_put(rv); + + return res; +} + static uc_value_t * uc_sort(uc_vm_t *vm, size_t nargs) { - uc_value_t *arr = uc_fn_arg(0); + uc_value_t *val = uc_fn_arg(0); uc_value_t *fn = uc_fn_arg(1); - if (!assert_mutable_array(vm, arr)) + if (!assert_mutable(vm, val)) return NULL; sort_ctx.vm = vm; sort_ctx.fn = fn; - ucv_array_sort(arr, sort_fn); + switch (ucv_type(val)) { + case UC_ARRAY: + ucv_array_sort(val, array_sort_fn); + break; + + case UC_OBJECT: + ucv_object_sort(val, object_sort_fn); + break; + + default: + return NULL; + } - return sort_ctx.ex ? NULL : ucv_get(arr); + return sort_ctx.ex ? NULL : ucv_get(val); } static uc_value_t * diff --git a/tests/custom/03_stdlib/16_sort b/tests/custom/03_stdlib/16_sort index ac4a0e1..14d0e12 100644 --- a/tests/custom/03_stdlib/16_sort +++ b/tests/custom/03_stdlib/16_sort @@ -40,7 +40,16 @@ Returns `null` if the given input array value is not an array. return 1; return 0; - }) + }), + + // default lexical object key sort + sort({ qrx: 1, foo: 2, abc: 3 }), + + // object sort with custom callback (by value) + sort({ a: 5, b: 3, c: 2, d: 4, e: 1 }, (k1, k2, v1, v2) => v1 - v2), + + // object sort with custom callback (by key length) + sort({ "Bean": true, "Orange": true, "Apple": true }, (k1, k2) => length(k1) - length(k2)) ]), "\n"); %} -- End -- @@ -51,6 +60,9 @@ Returns `null` if the given input array value is not an array. [ 1, "2b", false, null, true ] [ "pear", "apple", "banana", "grapefruit" ] [ 1, 2, 4, 9, "a", "b", "q", "x" ] +{ "abc": 3, "foo": 2, "qrx": 1 } +{ "e": 1, "c": 2, "b": 3, "d": 4, "a": 5 } +{ "Bean": true, "Apple": true, "Orange": true } -- End -- @@ -73,7 +85,7 @@ In line 2, byte 34: -- End -- -Supplying an invalid array will yield `null`. +Supplying a non-array, non-object value will yield `null`. -- Testcase -- {% -- cgit v1.2.3