[njs] Introduced quick sort implementation.
Dmitry Volyntsev
xeioex at nginx.com
Mon May 25 14:23:49 UTC 2020
details: https://hg.nginx.org/njs/rev/4fe4575ff3de
branches:
changeset: 1394:4fe4575ff3de
user: Dmitry Volyntsev <xeioex at nginx.com>
date: Mon May 25 14:21:20 2020 +0000
description:
Introduced quick sort implementation.
diffstat:
auto/sources | 1 +
src/njs_array.c | 6 +-
src/njs_main.h | 1 +
src/njs_utils.c | 330 ++++++++++++++++++++++++++++++++++++++++++++
src/njs_utils.h | 16 ++
src/test/njs_unit_test.c | 130 +++++++++++++++++
src/test/rbtree_unit_test.c | 6 +-
7 files changed, 484 insertions(+), 6 deletions(-)
diffs (576 lines):
diff -r ab19ee68d945 -r 4fe4575ff3de auto/sources
--- a/auto/sources Mon May 25 14:21:14 2020 +0000
+++ b/auto/sources Mon May 25 14:21:20 2020 +0000
@@ -20,6 +20,7 @@ NJS_LIB_SRCS=" \
src/njs_malloc.c \
src/njs_mp.c \
src/njs_sprintf.c \
+ src/njs_utils.c \
src/njs_chb.c \
src/njs_value.c \
src/njs_vm.c \
diff -r ab19ee68d945 -r 4fe4575ff3de src/njs_array.c
--- a/src/njs_array.c Mon May 25 14:21:14 2020 +0000
+++ b/src/njs_array.c Mon May 25 14:21:20 2020 +0000
@@ -1522,7 +1522,7 @@ njs_array_prototype_join(njs_vm_t *vm, n
static int
-njs_array_indices_handler(const void *first, const void *second)
+njs_array_indices_handler(const void *first, const void *second, void *ctx)
{
double num1, num2;
int64_t diff;
@@ -1572,8 +1572,8 @@ njs_array_keys(njs_vm_t *vm, njs_value_t
return NULL;
}
- qsort(keys->start, keys->length, sizeof(njs_value_t),
- njs_array_indices_handler);
+ njs_qsort(keys->start, keys->length, sizeof(njs_value_t),
+ njs_array_indices_handler, NULL);
return keys;
}
diff -r ab19ee68d945 -r 4fe4575ff3de src/njs_main.h
--- a/src/njs_main.h Mon May 25 14:21:14 2020 +0000
+++ b/src/njs_main.h Mon May 25 14:21:20 2020 +0000
@@ -32,6 +32,7 @@
#include <njs_mp.h>
#include <njs_arr.h>
#include <njs_chb.h>
+#include <njs_utils.h>
#include <njs_sprintf.h>
#include <njs_pcre.h>
diff -r ab19ee68d945 -r 4fe4575ff3de src/njs_utils.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/njs_utils.c Mon May 25 14:21:20 2020 +0000
@@ -0,0 +1,330 @@
+
+/*
+ * Copyright (C) Dmitry Volyntsev
+ * Copyright (C) NGINX, Inc.
+ */
+
+
+#include <njs_main.h>
+
+
+typedef void (*njs_swap_t) (void *a, void *b, size_t size);
+
+
+njs_inline void
+njs_swap_u8(void *a, void *b, size_t size)
+{
+ uint8_t u, *au, *bu;
+
+ au = (uint8_t *) a;
+ bu = (uint8_t *) b;
+
+ u = au[0];
+ au[0] = bu[0];
+ bu[0] = u;
+}
+
+
+njs_inline void
+njs_swap_u16(void *a, void *b, size_t size)
+{
+ uint16_t u, *au, *bu;
+
+ au = (uint16_t *) a;
+ bu = (uint16_t *) b;
+
+ u = au[0];
+ au[0] = bu[0];
+ bu[0] = u;
+}
+
+
+njs_inline void
+njs_swap_u32(void *a, void *b, size_t size)
+{
+ uint32_t u, *au, *bu;
+
+ au = (uint32_t *) a;
+ bu = (uint32_t *) b;
+
+ u = au[0];
+ au[0] = bu[0];
+ bu[0] = u;
+}
+
+
+njs_inline void
+njs_swap_u64(void *a, void *b, size_t size)
+{
+ uint64_t u, *au, *bu;
+
+ au = (uint64_t *) a;
+ bu = (uint64_t *) b;
+
+ u = au[0];
+ au[0] = bu[0];
+ bu[0] = u;
+}
+
+
+njs_inline void
+njs_swap_u128(void *a, void *b, size_t size)
+{
+ uint64_t u, v, *au, *bu;
+
+ au = (uint64_t *) a;
+ bu = (uint64_t *) b;
+
+ u = au[0];
+ v = au[1];
+ au[0] = bu[0];
+ au[1] = bu[1];
+ bu[0] = u;
+ bu[1] = v;
+}
+
+
+njs_inline void
+njs_swap_u128x(void *a, void *b, size_t size)
+{
+ uint64_t u, v, *au, *bu;
+
+ au = (uint64_t *) a;
+ bu = (uint64_t *) b;
+
+ do {
+ u = au[0];
+ v = au[1];
+ au[0] = bu[0];
+ au[1] = bu[1];
+ bu[0] = u;
+ bu[1] = v;
+
+ size -= sizeof(uint64_t) * 2;
+
+ au += 2;
+ bu += 2;
+ } while (size != 0);
+}
+
+
+njs_inline void
+njs_swap_bytes(void *a, void *b, size_t size)
+{
+ uint8_t u, *au, *bu;
+
+ au = (uint8_t *) a;
+ bu = (uint8_t *) b;
+
+ while (size-- != 0) {
+ u = *au;
+ *au++ = *bu;
+ *bu++ = u;
+ }
+}
+
+
+njs_inline njs_swap_t
+njs_choose_swap(size_t size)
+{
+ switch (size) {
+ case 2:
+ return njs_swap_u16;
+ case 4:
+ return njs_swap_u32;
+ case 8:
+ return njs_swap_u64;
+ case 16:
+ return njs_swap_u128;
+ default:
+ if ((size % 16) == 0) {
+ return njs_swap_u128x;
+ }
+
+ if (size == 1) {
+ return njs_swap_u8;
+ }
+ }
+
+ return njs_swap_bytes;
+}
+
+
+njs_inline void
+njs_sift_down(u_char *base, njs_sort_cmp_t cmp, njs_swap_t swap, size_t n,
+ size_t esize, void *ctx, njs_uint_t i)
+{
+ njs_uint_t c, m;
+
+ m = i;
+
+ while (1) {
+ c = 2 * i + esize;
+
+ if (c < n && cmp(base + m, base + c, ctx) < 0) {
+ m = c;
+ }
+
+ c += esize;
+
+ if (c < n && cmp(base + m, base + c, ctx) < 0) {
+ m = c;
+ }
+
+ if (m == i) {
+ break;
+ }
+
+ swap(base + i, base + m, esize);
+ i = m;
+ }
+}
+
+
+static void
+njs_heapsort(u_char *base, size_t n, size_t esize, njs_swap_t swap,
+ njs_sort_cmp_t cmp, void *ctx)
+{
+ njs_uint_t i;
+
+ i = (n / 2) * esize;
+ n = n * esize;
+
+ for ( ;; ) {
+ njs_sift_down(base, cmp, swap, n, esize, ctx, i);
+
+ if (i == 0) {
+ break;
+ }
+
+ i -= esize;
+ }
+
+ while (n > esize) {
+ swap(base, base + n - esize, esize);
+ n -= esize;
+
+ njs_sift_down(base, cmp, swap, n, esize, ctx, 0);
+ }
+}
+
+
+njs_inline void *
+njs_pivot(void *a, void *b, void *c, njs_sort_cmp_t cmp, void *ctx)
+{
+ if (cmp(a, c, ctx) < 0) {
+ if (cmp(b, c, ctx) < 0) {
+ return (cmp(a, b, ctx) < 0) ? b : a;
+ }
+
+ return c;
+ }
+
+ if (cmp(b, a, ctx) < 0) {
+ return (cmp(b, c, ctx) < 0) ? c : b;
+ }
+
+ return a;
+}
+
+
+typedef struct {
+ u_char *base;
+ njs_uint_t elems;
+} njs_qsort_state_t;
+
+
+#define NJS_MAX_DEPTH 16
+
+
+void
+njs_qsort(void *arr, size_t n, size_t esize, njs_sort_cmp_t cmp, void *ctx)
+{
+ int r;
+ u_char *base, *lt, *gt, *p, *end;
+ njs_uint_t m4;
+ njs_swap_t swap;
+ njs_qsort_state_t stack[NJS_MAX_DEPTH], *sp;
+
+ if (n < 2) {
+ return;
+ }
+
+ swap = njs_choose_swap(esize);
+
+ sp = stack;
+ sp->base = arr;
+ sp->elems = n;
+ sp++;
+
+ while (sp-- > stack) {
+ base = sp->base;
+ n = sp->elems;
+ end = base + n * esize;
+
+ while (n > 6) {
+ if (njs_slow_path(sp == &stack[NJS_MAX_DEPTH - 1])) {
+ njs_heapsort(base, n, esize, swap, cmp, ctx);
+ end = base;
+ break;
+ }
+
+ m4 = (n / 4) * esize;
+ p = njs_pivot(base + m4, base + 2 * m4, base + 3 * m4, cmp, ctx);
+ swap(base, p, esize);
+
+ /**
+ * Partition
+ * < mid | == mid | unprocessed | mid >
+ * lt p gt
+ */
+
+ lt = base;
+ gt = end;
+ p = lt + esize;
+
+ while (p < gt) {
+ r = cmp(p, lt, ctx);
+
+ if (r <= 0) {
+ if (r < 0) {
+ swap(lt, p, esize);
+ lt += esize;
+ }
+
+ p += esize;
+ continue;
+ }
+
+ swap(gt - esize, p, esize);
+ gt -= esize;
+ }
+
+ if (lt - base > end - gt) {
+ sp->base = base;
+ sp->elems = (lt - base) / esize;
+
+ base = gt;
+ n = (end - gt) / esize;
+
+ } else {
+ sp->base = gt;
+ sp->elems = (end - gt) / esize;
+
+ n = (lt - base) / esize;
+ }
+
+ end = base + n * esize;
+ sp++;
+ }
+
+ /* Insertion sort. */
+
+ for (p = base + esize; p < end; p += esize) {
+ while (p > base && cmp(p, p - esize, ctx) < 0) {
+ swap(p, p - esize, esize);
+ p -= esize;
+ }
+ }
+ }
+}
diff -r ab19ee68d945 -r 4fe4575ff3de src/njs_utils.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/njs_utils.h Mon May 25 14:21:20 2020 +0000
@@ -0,0 +1,16 @@
+
+/*
+ * Copyright (C) Dmitry Volyntsev
+ * Copyright (C) NGINX, Inc.
+ */
+
+#ifndef _NJS_UTILS_H_INCLUDED_
+#define _NJS_UTILS_H_INCLUDED_
+
+
+typedef int (*njs_sort_cmp_t)(const void *, const void *, void *ctx);
+
+void njs_qsort(void *base, size_t n, size_t size, njs_sort_cmp_t cmp,
+ void *ctx);
+
+#endif /* _NJS_UTILS_H_INCLUDED_ */
diff -r ab19ee68d945 -r 4fe4575ff3de src/test/njs_unit_test.c
--- a/src/test/njs_unit_test.c Mon May 25 14:21:14 2020 +0000
+++ b/src/test/njs_unit_test.c Mon May 25 14:21:20 2020 +0000
@@ -17917,6 +17917,134 @@ done:
}
+typedef struct {
+ size_t size;
+ uint32_t array[32];
+ size_t esize;
+ uint32_t expected[32];
+} njs_sort_test_t;
+
+
+static int
+njs_sort_cmp(const void *a, const void *b, void *ctx)
+{
+ njs_sort_test_t *c;
+
+ c = ctx;
+
+ switch (c->esize) {
+ case 1:
+ return *((uint8_t *) a) - *((uint8_t *) b);
+ case 2:
+ return *((uint16_t *) a) - *((uint16_t *) b);
+ case 4:
+ default:
+ return *((uint32_t *) a) - *((uint32_t *) b);
+ }
+}
+
+
+static njs_int_t
+njs_sort_test(njs_vm_t *vm, njs_opts_t *opts, njs_stat_t *stat)
+{
+ u_char *p;
+ njs_uint_t i, j, k;
+ njs_sort_test_t *t;
+ u_char array[sizeof(t->array)];
+ uint32_t sorted[sizeof(t->array) / sizeof(t->array[0])];
+
+ static const njs_sort_test_t tests[] = {
+ { 1, { 5 }, 1, { 5 } },
+ { 3, { 3, 2, 1 }, 1, { 1, 2, 3 } },
+ { 4, { 4, 3, 2, 1 }, 1, { 1, 2, 3, 4 } },
+ { 5, { 5, 4, 3, 2, 1 }, 1, { 1, 2, 3, 4, 5 } },
+ { 5, { 1, 0, 9, 1, 8 }, 1, { 0, 1, 1, 8, 9 } },
+ { 8, { 0, 0, 0, 0, 0, 0, 0, 0 }, 1, { 0, 0, 0, 0, 0, 0, 0, 0 } },
+ { 8, { 4, 5, 1, 4, 2, 5, 5, 6 }, 1, { 1, 2, 4, 4, 5, 5, 5, 6 } },
+ { 4, { 512, 100, 65535, 0 }, 2, { 0, 100, 512, 65535 } },
+ { 3, { 65536, 3, 262141 }, 4, { 3, 65536, 262141 } },
+ };
+
+ for (i = 0; i < njs_nitems(tests); i++) {
+ t = (njs_sort_test_t *) &tests[i];
+
+ p = array;
+ for (k = 0; k < t->size; k++) {
+ switch (t->esize) {
+ case 1:
+ *p = (uint8_t) t->array[k];
+ break;
+ case 2:
+ *(uint16_t *) p = (uint16_t) t->array[k];
+ break;
+ case 4:
+ default:
+ *(uint32_t *) p = (uint32_t) t->array[k];
+ break;
+ }
+
+ p += t->esize;
+ }
+
+ njs_qsort(array, t->size, t->esize, njs_sort_cmp, t);
+
+ p = array;
+ for (k = 0; k < t->size; k++) {
+ switch (t->esize) {
+ case 1:
+ sorted[k] = *p;
+ break;
+ case 2:
+ sorted[k] = *(uint16_t *) p;
+ break;
+ case 4:
+ default:
+ sorted[k] = *(uint32_t *) p;
+ break;
+ }
+
+ p += t->esize;
+ }
+
+
+ for (k = 0; k < t->size; k++) {
+ if (sorted[k] != t->expected[k]) {
+ goto failed;
+ }
+ }
+
+ stat->passed++;
+ continue;
+
+failed:
+
+ njs_printf("njs_sort_test([");
+ for (j = 0; j < t->size; j++) {
+ njs_printf("%uD%s", t->array[j],
+ (j < t->size - 1) ? "," : "");
+ }
+
+ njs_printf("]):\nexpected: [");
+ for (j = 0; j < t->size; j++) {
+ njs_printf("%uD%s", t->expected[j],
+ (j < t->size - 1) ? "," : "");
+ }
+
+ njs_printf("]\n got: [");
+ for (j = 0; j < t->size; j++) {
+ njs_printf("%uD%s", sorted[j],
+ (j < t->size - 1) ? "," : "");
+ }
+
+ njs_printf("]\n");
+
+ stat->failed++;
+ }
+
+ return NJS_OK;
+}
+
+
static njs_int_t
njs_string_to_index_test(njs_vm_t *vm, njs_opts_t *opts, njs_stat_t *stat)
{
@@ -18020,6 +18148,8 @@ njs_api_test(njs_opts_t *opts, njs_stat_
njs_str("njs_file_dirname_test") },
{ njs_chb_test,
njs_str("njs_chb_test") },
+ { njs_sort_test,
+ njs_str("njs_sort_test") },
{ njs_string_to_index_test,
njs_str("njs_string_to_index_test") },
};
diff -r ab19ee68d945 -r 4fe4575ff3de src/test/rbtree_unit_test.c
--- a/src/test/rbtree_unit_test.c Mon May 25 14:21:14 2020 +0000
+++ b/src/test/rbtree_unit_test.c Mon May 25 14:21:20 2020 +0000
@@ -18,7 +18,7 @@ static intptr_t rbtree_unit_test_compari
njs_rbtree_node_t *node2);
static njs_int_t rbtree_unit_test_compare(uint32_t key1, uint32_t key2);
static int njs_cdecl rbtree_unit_test_sort_cmp(const void *one,
- const void *two);
+ const void *two, void *ctx);
static njs_int_t
@@ -56,7 +56,7 @@ rbtree_unit_test(njs_uint_t n)
items[i].key = key;
}
- qsort(keys, n, sizeof(uint32_t), rbtree_unit_test_sort_cmp);
+ njs_qsort(keys, n, sizeof(uint32_t), rbtree_unit_test_sort_cmp, NULL);
for (i = 0; i < n; i++) {
njs_rbtree_insert(&tree, &items[i].node);
@@ -161,7 +161,7 @@ rbtree_unit_test_compare(uint32_t key1,
static int njs_cdecl
-rbtree_unit_test_sort_cmp(const void *one, const void *two)
+rbtree_unit_test_sort_cmp(const void *one, const void *two, void *ctx)
{
const uint32_t *first, *second;
More information about the nginx-devel
mailing list