blob: c58cf34292a578ffb91d6ecf927a886fc0cae883 [file] [log] [blame]
/*
* 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, *c, *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) {
for (c = p; c > base && cmp(c, c - esize, ctx) < 0; c -= esize) {
swap(c, c - esize, esize);
}
}
}
}
#define njs_errno_case(e) \
case e: \
return #e;
const char*
njs_errno_string(int errnum)
{
switch (errnum) {
#ifdef EACCES
njs_errno_case(EACCES);
#endif
#ifdef EADDRINUSE
njs_errno_case(EADDRINUSE);
#endif
#ifdef EADDRNOTAVAIL
njs_errno_case(EADDRNOTAVAIL);
#endif
#ifdef EAFNOSUPPORT
njs_errno_case(EAFNOSUPPORT);
#endif
#ifdef EAGAIN
njs_errno_case(EAGAIN);
#endif
#ifdef EWOULDBLOCK
#if EAGAIN != EWOULDBLOCK
njs_errno_case(EWOULDBLOCK);
#endif
#endif
#ifdef EALREADY
njs_errno_case(EALREADY);
#endif
#ifdef EBADF
njs_errno_case(EBADF);
#endif
#ifdef EBADMSG
njs_errno_case(EBADMSG);
#endif
#ifdef EBUSY
njs_errno_case(EBUSY);
#endif
#ifdef ECANCELED
njs_errno_case(ECANCELED);
#endif
#ifdef ECHILD
njs_errno_case(ECHILD);
#endif
#ifdef ECONNABORTED
njs_errno_case(ECONNABORTED);
#endif
#ifdef ECONNREFUSED
njs_errno_case(ECONNREFUSED);
#endif
#ifdef ECONNRESET
njs_errno_case(ECONNRESET);
#endif
#ifdef EDEADLK
njs_errno_case(EDEADLK);
#endif
#ifdef EDESTADDRREQ
njs_errno_case(EDESTADDRREQ);
#endif
#ifdef EDOM
njs_errno_case(EDOM);
#endif
#ifdef EDQUOT
njs_errno_case(EDQUOT);
#endif
#ifdef EEXIST
njs_errno_case(EEXIST);
#endif
#ifdef EFAULT
njs_errno_case(EFAULT);
#endif
#ifdef EFBIG
njs_errno_case(EFBIG);
#endif
#ifdef EHOSTUNREACH
njs_errno_case(EHOSTUNREACH);
#endif
#ifdef EIDRM
njs_errno_case(EIDRM);
#endif
#ifdef EILSEQ
njs_errno_case(EILSEQ);
#endif
#ifdef EINPROGRESS
njs_errno_case(EINPROGRESS);
#endif
#ifdef EINTR
njs_errno_case(EINTR);
#endif
#ifdef EINVAL
njs_errno_case(EINVAL);
#endif
#ifdef EIO
njs_errno_case(EIO);
#endif
#ifdef EISCONN
njs_errno_case(EISCONN);
#endif
#ifdef EISDIR
njs_errno_case(EISDIR);
#endif
#ifdef ELOOP
njs_errno_case(ELOOP);
#endif
#ifdef EMFILE
njs_errno_case(EMFILE);
#endif
#ifdef EMLINK
njs_errno_case(EMLINK);
#endif
#ifdef EMSGSIZE
njs_errno_case(EMSGSIZE);
#endif
#ifdef EMULTIHOP
njs_errno_case(EMULTIHOP);
#endif
#ifdef ENAMETOOLONG
njs_errno_case(ENAMETOOLONG);
#endif
#ifdef ENETDOWN
njs_errno_case(ENETDOWN);
#endif
#ifdef ENETRESET
njs_errno_case(ENETRESET);
#endif
#ifdef ENETUNREACH
njs_errno_case(ENETUNREACH);
#endif
#ifdef ENFILE
njs_errno_case(ENFILE);
#endif
#ifdef ENOBUFS
njs_errno_case(ENOBUFS);
#endif
#ifdef ENODATA
njs_errno_case(ENODATA);
#endif
#ifdef ENODEV
njs_errno_case(ENODEV);
#endif
#ifdef ENOENT
njs_errno_case(ENOENT);
#endif
#ifdef ENOEXEC
njs_errno_case(ENOEXEC);
#endif
#ifdef ENOLINK
njs_errno_case(ENOLINK);
#endif
#ifdef ENOLCK
#if ENOLINK != ENOLCK
njs_errno_case(ENOLCK);
#endif
#endif
#ifdef ENOMEM
njs_errno_case(ENOMEM);
#endif
#ifdef ENOMSG
njs_errno_case(ENOMSG);
#endif
#ifdef ENOPROTOOPT
njs_errno_case(ENOPROTOOPT);
#endif
#ifdef ENOSPC
njs_errno_case(ENOSPC);
#endif
#ifdef ENOSR
njs_errno_case(ENOSR);
#endif
#ifdef ENOSTR
njs_errno_case(ENOSTR);
#endif
#ifdef ENOSYS
njs_errno_case(ENOSYS);
#endif
#ifdef ENOTCONN
njs_errno_case(ENOTCONN);
#endif
#ifdef ENOTDIR
njs_errno_case(ENOTDIR);
#endif
#ifdef ENOTEMPTY
#if ENOTEMPTY != EEXIST
njs_errno_case(ENOTEMPTY);
#endif
#endif
#ifdef ENOTSOCK
njs_errno_case(ENOTSOCK);
#endif
#ifdef ENOTSUP
njs_errno_case(ENOTSUP);
#else
#ifdef EOPNOTSUPP
njs_errno_case(EOPNOTSUPP);
#endif
#endif
#ifdef ENOTTY
njs_errno_case(ENOTTY);
#endif
#ifdef ENXIO
njs_errno_case(ENXIO);
#endif
#ifdef EOVERFLOW
njs_errno_case(EOVERFLOW);
#endif
#ifdef EPERM
njs_errno_case(EPERM);
#endif
#ifdef EPIPE
njs_errno_case(EPIPE);
#endif
#ifdef EPROTO
njs_errno_case(EPROTO);
#endif
#ifdef EPROTONOSUPPORT
njs_errno_case(EPROTONOSUPPORT);
#endif
#ifdef EPROTOTYPE
njs_errno_case(EPROTOTYPE);
#endif
#ifdef ERANGE
njs_errno_case(ERANGE);
#endif
#ifdef EROFS
njs_errno_case(EROFS);
#endif
#ifdef ESPIPE
njs_errno_case(ESPIPE);
#endif
#ifdef ESRCH
njs_errno_case(ESRCH);
#endif
#ifdef ESTALE
njs_errno_case(ESTALE);
#endif
#ifdef ETIME
njs_errno_case(ETIME);
#endif
#ifdef ETIMEDOUT
njs_errno_case(ETIMEDOUT);
#endif
#ifdef ETXTBSY
njs_errno_case(ETXTBSY);
#endif
#ifdef EXDEV
njs_errno_case(EXDEV);
#endif
default:
break;
}
return "UNKNOWN CODE";
}