sort(1): Replace NetBSD version with Free/Open version
authorJohn Marino <draco@marino.st>
Tue, 28 Jul 2015 18:41:56 +0000 (20:41 +0200)
committerJohn Marino <draco@marino.st>
Tue, 28 Jul 2015 18:56:30 +0000 (20:56 +0200)
With my ongoing collation work, I discovered our sort was not locale
sensitive, but GNU sort was.  I replaced our ancient GNU sort with
NetBSD's version about 4 years ago.  NetBSD hasn't updated that version
since.  However, FreeBSD got rid of their GNU sort fairly recently and
replaced it with another BSD-licensed version.  Four months ago, it was
imported into OpenBSD, they made some corrections which were incorporated
back in FreeBSD in the April timeframe.

This version is locale sensitive and gives the same answers as GNU sort in
my (admittedly) very limited testing.

I fixed some minor issues that GCC5 was squawking about (mainly unused
variables) and I changed the --parallel option PTHREAD_MUTEX_ADAPTIVE_NP
behavior to PTHREAD_MUTEX_ERRORCHECK (the default POSIX behavior).  DF
does not have the former flag implemented.

26 files changed:
usr.bin/sort/Makefile
usr.bin/sort/append.c [deleted file]
usr.bin/sort/bwstring.c [new file with mode: 0644]
usr.bin/sort/bwstring.h [new file with mode: 0644]
usr.bin/sort/coll.c [new file with mode: 0644]
usr.bin/sort/coll.h [new file with mode: 0644]
usr.bin/sort/fields.c [deleted file]
usr.bin/sort/file.c [new file with mode: 0644]
usr.bin/sort/file.h [new file with mode: 0644]
usr.bin/sort/files.c [deleted file]
usr.bin/sort/fsort.c [deleted file]
usr.bin/sort/fsort.h [deleted file]
usr.bin/sort/init.c [deleted file]
usr.bin/sort/mem.c [new file with mode: 0644]
usr.bin/sort/mem.h [new file with mode: 0644]
usr.bin/sort/msort.c [deleted file]
usr.bin/sort/pathnames.h [deleted file]
usr.bin/sort/radix_sort.c [deleted file]
usr.bin/sort/radixsort.c [new file with mode: 0644]
usr.bin/sort/radixsort.h [new file with mode: 0644]
usr.bin/sort/sort.1
usr.bin/sort/sort.c
usr.bin/sort/sort.h
usr.bin/sort/tmp.c [deleted file]
usr.bin/sort/vsort.c [new file with mode: 0644]
usr.bin/sort/vsort.h [new file with mode: 0644]

index 74d9775..b0faaf5 100644 (file)
@@ -1,14 +1,19 @@
-#      $NetBSD: Makefile,v 1.7 2009/09/05 09:16:18 dsl Exp $
+# $FreeBSD: head/usr.bin/sort/Makefile 275042 2014-11-25 14:29:10Z bapt $
 
 PROG=  sort
-SRCS=  append.c \
-       fields.c \
-       files.c \
-       fsort.c \
-       init.c \
-       msort.c \
+SRCS=  bwstring.c \
+       coll.c \
+       file.c \
+       mem.c \
+       radixsort.c \
        sort.c \
-       tmp.c \
-       radix_sort.c
+       vsort.c
+
+DPADD= ${LIBMD}
+LDADD= -lmd
+
+DPADD+=        ${LIBPTHREAD}
+LDADD+=        -lpthread
+CFLAGS+=       -DSORT_THREADS
 
 .include <bsd.prog.mk>
diff --git a/usr.bin/sort/append.c b/usr.bin/sort/append.c
deleted file mode 100644 (file)
index 5e4d3a8..0000000
+++ /dev/null
@@ -1,92 +0,0 @@
-/*     $NetBSD: append.c,v 1.22 2009/09/10 22:02:40 dsl Exp $  */
-
-/*-
- * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Ben Harris and Jaromir Dolecek.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*-
- * Copyright (c) 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Peter McIlroy.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#include "sort.h"
-
-#include <stdlib.h>
-
-/*
- * copy sorted lines to output
- * Ignore duplicates (marked with -ve keylen)
- */
-void
-append(RECHEADER **keylist, int nelem, FILE *fp, put_func_t put)
-{
-       RECHEADER **cpos, **lastkey;
-       RECHEADER *crec;
-
-       lastkey = keylist + nelem;
-       if (REVERSE) {
-               for (cpos = lastkey; cpos-- > keylist;) {
-                       crec = *cpos;
-                       if (crec->keylen >= 0)
-                               put(crec, fp);
-               }
-       } else {
-               for (cpos = keylist; cpos < lastkey; cpos++) {
-                       crec = *cpos;
-                       if (crec->keylen >= 0)
-                               put(crec, fp);
-               }
-       }
-}
diff --git a/usr.bin/sort/bwstring.c b/usr.bin/sort/bwstring.c
new file mode 100644 (file)
index 0000000..38e72e6
--- /dev/null
@@ -0,0 +1,1143 @@
+/*-
+ * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD: head/usr.bin/sort/bwstring.c 281181 2015-04-07 01:17:29Z pfg $
+ */
+
+
+#include <ctype.h>
+#include <errno.h>
+#include <err.h>
+#include <langinfo.h>
+#include <math.h>
+#include <stdlib.h>
+#include <string.h>
+#include <wchar.h>
+#include <wctype.h>
+
+#include "bwstring.h"
+#include "sort.h"
+
+bool byte_sort;
+
+static wchar_t **wmonths;
+static unsigned char **cmonths;
+
+/* initialise months */
+
+void
+initialise_months(void)
+{
+       const nl_item item[12] = { ABMON_1, ABMON_2, ABMON_3, ABMON_4,
+           ABMON_5, ABMON_6, ABMON_7, ABMON_8, ABMON_9, ABMON_10,
+           ABMON_11, ABMON_12 };
+       unsigned char *tmp;
+       size_t len;
+
+       if (MB_CUR_MAX == 1) {
+               if (cmonths == NULL) {
+                       unsigned char *m;
+
+                       cmonths = sort_malloc(sizeof(unsigned char*) * 12);
+                       for (int i = 0; i < 12; i++) {
+                               cmonths[i] = NULL;
+                               tmp = (unsigned char *) nl_langinfo(item[i]);
+                               if (debug_sort)
+                                       printf("month[%d]=%s\n", i, tmp);
+                               if (*tmp == '\0')
+                                       continue;
+                               m = sort_strdup(tmp);
+                               len = strlen(tmp);
+                               for (unsigned int j = 0; j < len; j++)
+                                       m[j] = toupper(m[j]);
+                               cmonths[i] = m;
+                       }
+               }
+
+       } else {
+               if (wmonths == NULL) {
+                       wchar_t *m;
+
+                       wmonths = sort_malloc(sizeof(wchar_t *) * 12);
+                       for (int i = 0; i < 12; i++) {
+                               wmonths[i] = NULL;
+                               tmp = (unsigned char *) nl_langinfo(item[i]);
+                               if (debug_sort)
+                                       printf("month[%d]=%s\n", i, tmp);
+                               if (*tmp == '\0')
+                                       continue;
+                               len = strlen(tmp);
+                               m = sort_malloc(SIZEOF_WCHAR_STRING(len + 1));
+                               if (mbstowcs(m, (char*)tmp, len) ==
+                                   ((size_t) - 1)) {
+                                       sort_free(m);
+                                       continue;
+                               }
+                               m[len] = L'\0';
+                               for (unsigned int j = 0; j < len; j++)
+                                       m[j] = towupper(m[j]);
+                               wmonths[i] = m;
+                       }
+               }
+       }
+}
+
+/*
+ * Compare two wide-character strings
+ */
+static int
+wide_str_coll(const wchar_t *s1, const wchar_t *s2)
+{
+       int ret = 0;
+
+       errno = 0;
+       ret = wcscoll(s1, s2);
+       if (errno == EILSEQ) {
+               errno = 0;
+               ret = wcscmp(s1, s2);
+               if (errno != 0) {
+                       for (size_t i = 0; ; ++i) {
+                               wchar_t c1 = s1[i];
+                               wchar_t c2 = s2[i];
+                               if (c1 == L'\0')
+                                       return ((c2 == L'\0') ? 0 : -1);
+                               if (c2 == L'\0')
+                                       return (+1);
+                               if (c1 == c2)
+                                       continue;
+                               return ((int)(c1 - c2));
+                       }
+               }
+       }
+       return (ret);
+}
+
+/* counterparts of wcs functions */
+
+void
+bwsprintf(FILE *f, struct bwstring *bws, const char *prefix, const char *suffix)
+{
+
+       if (MB_CUR_MAX == 1)
+               fprintf(f, "%s%s%s", prefix, bws->data.cstr, suffix);
+       else
+               fprintf(f, "%s%S%s", prefix, bws->data.wstr, suffix);
+}
+
+const void* bwsrawdata(const struct bwstring *bws)
+{
+
+       return (&(bws->data));
+}
+
+size_t bwsrawlen(const struct bwstring *bws)
+{
+
+       return ((MB_CUR_MAX == 1) ? bws->len : SIZEOF_WCHAR_STRING(bws->len));
+}
+
+size_t
+bws_memsize(const struct bwstring *bws)
+{
+
+       return ((MB_CUR_MAX == 1) ? (bws->len + 2 + sizeof(struct bwstring)) :
+           (SIZEOF_WCHAR_STRING(bws->len + 1) + sizeof(struct bwstring)));
+}
+
+void
+bws_setlen(struct bwstring *bws, size_t newlen)
+{
+
+       if (bws && newlen != bws->len && newlen <= bws->len) {
+               bws->len = newlen;
+               if (MB_CUR_MAX == 1)
+                       bws->data.cstr[newlen] = '\0';
+               else
+                       bws->data.wstr[newlen] = L'\0';
+       }
+}
+
+/*
+ * Allocate a new binary string of specified size
+ */
+struct bwstring *
+bwsalloc(size_t sz)
+{
+       struct bwstring *ret;
+
+       if (MB_CUR_MAX == 1)
+               ret = sort_malloc(sizeof(struct bwstring) + 1 + sz);
+       else
+               ret = sort_malloc(sizeof(struct bwstring) +
+                   SIZEOF_WCHAR_STRING(sz + 1));
+       ret->len = sz;
+
+       if (MB_CUR_MAX == 1)
+               ret->data.cstr[ret->len] = '\0';
+       else
+               ret->data.wstr[ret->len] = L'\0';
+
+       return (ret);
+}
+
+/*
+ * Create a copy of binary string.
+ * New string size equals the length of the old string.
+ */
+struct bwstring *
+bwsdup(const struct bwstring *s)
+{
+
+       if (s == NULL)
+               return (NULL);
+       else {
+               struct bwstring *ret = bwsalloc(s->len);
+
+               if (MB_CUR_MAX == 1)
+                       memcpy(ret->data.cstr, s->data.cstr, (s->len));
+               else
+                       memcpy(ret->data.wstr, s->data.wstr,
+                           SIZEOF_WCHAR_STRING(s->len));
+
+               return (ret);
+       }
+}
+
+/*
+ * Create a new binary string from a wide character buffer.
+ */
+struct bwstring *
+bwssbdup(const wchar_t *str, size_t len)
+{
+
+       if (str == NULL)
+               return ((len == 0) ? bwsalloc(0) : NULL);
+       else {
+               struct bwstring *ret;
+
+               ret = bwsalloc(len);
+
+               if (MB_CUR_MAX == 1)
+                       for (size_t i = 0; i < len; ++i)
+                               ret->data.cstr[i] = (unsigned char) str[i];
+               else
+                       memcpy(ret->data.wstr, str, SIZEOF_WCHAR_STRING(len));
+
+               return (ret);
+       }
+}
+
+/*
+ * Create a new binary string from a raw binary buffer.
+ */
+struct bwstring *
+bwscsbdup(const unsigned char *str, size_t len)
+{
+       struct bwstring *ret;
+
+       ret = bwsalloc(len);
+
+       if (str) {
+               if (MB_CUR_MAX == 1)
+                       memcpy(ret->data.cstr, str, len);
+               else {
+                       mbstate_t mbs;
+                       const char *s;
+                       size_t charlen, chars, cptr;
+
+                       charlen = chars = 0;
+                       cptr = 0;
+                       s = (const char *) str;
+
+                       memset(&mbs, 0, sizeof(mbs));
+
+                       while (cptr < len) {
+                               size_t n = MB_CUR_MAX;
+
+                               if (n > len - cptr)
+                                       n = len - cptr;
+                               charlen = mbrlen(s + cptr, n, &mbs);
+                               switch (charlen) {
+                               case 0:
+                                       /* FALLTHROUGH */
+                               case (size_t) -1:
+                                       /* FALLTHROUGH */
+                               case (size_t) -2:
+                                       ret->data.wstr[chars++] =
+                                           (unsigned char) s[cptr];
+                                       ++cptr;
+                                       break;
+                               default:
+                                       n = mbrtowc(ret->data.wstr + (chars++),
+                                           s + cptr, charlen, &mbs);
+                                       if ((n == (size_t)-1) || (n == (size_t)-2))
+                                               /* NOTREACHED */
+                                               err(2, "mbrtowc error");
+                                       cptr += charlen;
+                               };
+                       }
+
+                       ret->len = chars;
+                       ret->data.wstr[ret->len] = L'\0';
+               }
+       }
+       return (ret);
+}
+
+/*
+ * De-allocate object memory
+ */
+void
+bwsfree(const struct bwstring *s)
+{
+
+       if (s)
+               sort_free(s);
+}
+
+/*
+ * Copy content of src binary string to dst.
+ * If the capacity of the dst string is not sufficient,
+ * then the data is truncated.
+ */
+size_t
+bwscpy(struct bwstring *dst, const struct bwstring *src)
+{
+       size_t nums = src->len;
+
+       if (nums > dst->len)
+               nums = dst->len;
+       dst->len = nums;
+
+       if (MB_CUR_MAX == 1) {
+               memcpy(dst->data.cstr, src->data.cstr, nums);
+               dst->data.cstr[dst->len] = '\0';
+       } else {
+               memcpy(dst->data.wstr, src->data.wstr,
+                   SIZEOF_WCHAR_STRING(nums + 1));
+               dst->data.wstr[dst->len] = L'\0';
+       }
+
+       return (nums);
+}
+
+/*
+ * Copy content of src binary string to dst,
+ * with specified number of symbols to be copied.
+ * If the capacity of the dst string is not sufficient,
+ * then the data is truncated.
+ */
+struct bwstring *
+bwsncpy(struct bwstring *dst, const struct bwstring *src, size_t size)
+{
+       size_t nums = src->len;
+
+       if (nums > dst->len)
+               nums = dst->len;
+       if (nums > size)
+               nums = size;
+       dst->len = nums;
+
+       if (MB_CUR_MAX == 1) {
+               memcpy(dst->data.cstr, src->data.cstr, nums);
+               dst->data.cstr[dst->len] = '\0';
+       } else {
+               memcpy(dst->data.wstr, src->data.wstr,
+                   SIZEOF_WCHAR_STRING(nums + 1));
+               dst->data.wstr[dst->len] = L'\0';
+       }
+
+       return (dst);
+}
+
+/*
+ * Copy content of src binary string to dst,
+ * with specified number of symbols to be copied.
+ * An offset value can be specified, from the start of src string.
+ * If the capacity of the dst string is not sufficient,
+ * then the data is truncated.
+ */
+struct bwstring *
+bwsnocpy(struct bwstring *dst, const struct bwstring *src, size_t offset,
+    size_t size)
+{
+
+       if (offset >= src->len) {
+               dst->data.wstr[0] = 0;
+               dst->len = 0;
+       } else {
+               size_t nums = src->len - offset;
+
+               if (nums > dst->len)
+                       nums = dst->len;
+               if (nums > size)
+                       nums = size;
+               dst->len = nums;
+               if (MB_CUR_MAX == 1) {
+                       memcpy(dst->data.cstr, src->data.cstr + offset,
+                           (nums));
+                       dst->data.cstr[dst->len] = '\0';
+               } else {
+                       memcpy(dst->data.wstr, src->data.wstr + offset,
+                           SIZEOF_WCHAR_STRING(nums));
+                       dst->data.wstr[dst->len] = L'\0';
+               }
+       }
+       return (dst);
+}
+
+/*
+ * Write binary string to the file.
+ * The output is ended either with '\n' (nl == true)
+ * or '\0' (nl == false).
+ */
+size_t
+bwsfwrite(struct bwstring *bws, FILE *f, bool zero_ended)
+{
+
+       if (MB_CUR_MAX == 1) {
+               size_t len = bws->len;
+
+               if (!zero_ended) {
+                       bws->data.cstr[len] = '\n';
+
+                       if (fwrite(bws->data.cstr, len + 1, 1, f) < 1)
+                               err(2, NULL);
+
+                       bws->data.cstr[len] = '\0';
+               } else if (fwrite(bws->data.cstr, len + 1, 1, f) < 1)
+                       err(2, NULL);
+
+               return (len + 1);
+
+       } else {
+               wchar_t eols;
+               size_t printed = 0;
+
+               eols = zero_ended ? btowc('\0') : btowc('\n');
+
+               while (printed < BWSLEN(bws)) {
+                       const wchar_t *s = bws->data.wstr + printed;
+
+                       if (*s == L'\0') {
+                               int nums;
+
+                               nums = fwprintf(f, L"%lc", *s);
+
+                               if (nums != 1)
+                                       err(2, NULL);
+                               ++printed;
+                       } else {
+                               int nums;
+
+                               nums = fwprintf(f, L"%ls", s);
+
+                               if (nums < 1)
+                                       err(2, NULL);
+                               printed += nums;
+                       }
+               }
+               fwprintf(f, L"%lc", eols);
+               return (printed + 1);
+       }
+}
+
+/*
+ * Allocate and read a binary string from file.
+ * The strings are nl-ended or zero-ended, depending on the sort setting.
+ */
+struct bwstring *
+bwsfgetln(FILE *f, size_t *len, bool zero_ended, struct reader_buffer *rb)
+{
+       wint_t eols;
+
+       eols = zero_ended ? btowc('\0') : btowc('\n');
+
+       if (!zero_ended && (MB_CUR_MAX > 1)) {
+               wchar_t *ret;
+
+               ret = fgetwln(f, len);
+
+               if (ret == NULL) {
+                       if (!feof(f))
+                               err(2, NULL);
+                       return (NULL);
+               }
+               if (*len > 0) {
+                       if (ret[*len - 1] == (wchar_t)eols)
+                               --(*len);
+               }
+               return (bwssbdup(ret, *len));
+
+       } else if (!zero_ended && (MB_CUR_MAX == 1)) {
+               char *ret;
+
+               ret = fgetln(f, len);
+
+               if (ret == NULL) {
+                       if (!feof(f))
+                               err(2, NULL);
+                       return (NULL);
+               }
+               if (*len > 0) {
+                       if (ret[*len - 1] == '\n')
+                               --(*len);
+               }
+               return (bwscsbdup((unsigned char*)ret, *len));
+
+       } else {
+               *len = 0;
+
+               if (feof(f))
+                       return (NULL);
+
+               if (2 >= rb->fgetwln_z_buffer_size) {
+                       rb->fgetwln_z_buffer_size += 256;
+                       rb->fgetwln_z_buffer = sort_realloc(rb->fgetwln_z_buffer,
+                           sizeof(wchar_t) * rb->fgetwln_z_buffer_size);
+               }
+               rb->fgetwln_z_buffer[*len] = 0;
+
+               if (MB_CUR_MAX == 1)
+                       while (!feof(f)) {
+                               int c;
+
+                               c = fgetc(f);
+
+                               if (c == EOF) {
+                                       if (*len == 0)
+                                               return (NULL);
+                                       goto line_read_done;
+                               }
+                               if (c == eols)
+                                       goto line_read_done;
+
+                               if (*len + 1 >= rb->fgetwln_z_buffer_size) {
+                                       rb->fgetwln_z_buffer_size += 256;
+                                       rb->fgetwln_z_buffer = sort_realloc(rb->fgetwln_z_buffer,
+                                           SIZEOF_WCHAR_STRING(rb->fgetwln_z_buffer_size));
+                               }
+
+                               rb->fgetwln_z_buffer[*len] = c;
+                               rb->fgetwln_z_buffer[++(*len)] = 0;
+                       }
+               else
+                       while (!feof(f)) {
+                               wint_t c = 0;
+
+                               c = fgetwc(f);
+
+                               if (c == WEOF) {
+                                       if (*len == 0)
+                                               return (NULL);
+                                       goto line_read_done;
+                               }
+                               if (c == eols)
+                                       goto line_read_done;
+
+                               if (*len + 1 >= rb->fgetwln_z_buffer_size) {
+                                       rb->fgetwln_z_buffer_size += 256;
+                                       rb->fgetwln_z_buffer = sort_realloc(rb->fgetwln_z_buffer,
+                                           SIZEOF_WCHAR_STRING(rb->fgetwln_z_buffer_size));
+                               }
+
+                               rb->fgetwln_z_buffer[*len] = c;
+                               rb->fgetwln_z_buffer[++(*len)] = 0;
+                       }
+
+line_read_done:
+               /* we do not count the last 0 */
+               return (bwssbdup(rb->fgetwln_z_buffer, *len));
+       }
+}
+
+int
+bwsncmp(const struct bwstring *bws1, const struct bwstring *bws2,
+    size_t offset, size_t len)
+{
+       size_t cmp_len, len1, len2;
+       int res = 0;
+
+       cmp_len = 0;
+       len1 = bws1->len;
+       len2 = bws2->len;
+
+       if (len1 <= offset) {
+               return ((len2 <= offset) ? 0 : -1);
+       } else {
+               if (len2 <= offset)
+                       return (+1);
+               else {
+                       len1 -= offset;
+                       len2 -= offset;
+
+                       cmp_len = len1;
+
+                       if (len2 < cmp_len)
+                               cmp_len = len2;
+
+                       if (len < cmp_len)
+                               cmp_len = len;
+
+                       if (MB_CUR_MAX == 1) {
+                               const unsigned char *s1, *s2;
+
+                               s1 = bws1->data.cstr + offset;
+                               s2 = bws2->data.cstr + offset;
+
+                               res = memcmp(s1, s2, cmp_len);
+
+                       } else {
+                               const wchar_t *s1, *s2;
+
+                               s1 = bws1->data.wstr + offset;
+                               s2 = bws2->data.wstr + offset;
+
+                               res = memcmp(s1, s2, SIZEOF_WCHAR_STRING(cmp_len));
+                       }
+               }
+       }
+
+       if (res == 0) {
+               if (len1 < cmp_len && len1 < len2)
+                       res = -1;
+               else if (len2 < cmp_len && len2 < len1)
+                       res = +1;
+       }
+
+       return (res);
+}
+
+int
+bwscmp(const struct bwstring *bws1, const struct bwstring *bws2, size_t offset)
+{
+       size_t len1, len2, cmp_len;
+       int res;
+
+       len1 = bws1->len;
+       len2 = bws2->len;
+
+       len1 -= offset;
+       len2 -= offset;
+
+       cmp_len = len1;
+
+       if (len2 < cmp_len)
+               cmp_len = len2;
+
+       res = bwsncmp(bws1, bws2, offset, cmp_len);
+
+       if (res == 0) {
+               if( len1 < len2)
+                       res = -1;
+               else if (len2 < len1)
+                       res = +1;
+       }
+
+       return (res);
+}
+
+int
+bws_iterator_cmp(bwstring_iterator iter1, bwstring_iterator iter2, size_t len)
+{
+       wchar_t c1, c2;
+       size_t i = 0;
+
+       for (i = 0; i < len; ++i) {
+               c1 = bws_get_iter_value(iter1);
+               c2 = bws_get_iter_value(iter2);
+               if (c1 != c2)
+                       return (c1 - c2);
+               iter1 = bws_iterator_inc(iter1, 1);
+               iter2 = bws_iterator_inc(iter2, 1);
+       }
+
+       return (0);
+}
+
+int
+bwscoll(const struct bwstring *bws1, const struct bwstring *bws2, size_t offset)
+{
+       size_t len1, len2;
+
+       len1 = bws1->len;
+       len2 = bws2->len;
+
+       if (len1 <= offset)
+               return ((len2 <= offset) ? 0 : -1);
+       else {
+               if (len2 <= offset)
+                       return (+1);
+               else {
+                       len1 -= offset;
+                       len2 -= offset;
+
+                       if (MB_CUR_MAX == 1) {
+                               const unsigned char *s1, *s2;
+
+                               s1 = bws1->data.cstr + offset;
+                               s2 = bws2->data.cstr + offset;
+
+                               if (byte_sort) {
+                                       int res = 0;
+
+                                       if (len1 > len2) {
+                                               res = memcmp(s1, s2, len2);
+                                               if (!res)
+                                                       res = +1;
+                                       } else if (len1 < len2) {
+                                               res = memcmp(s1, s2, len1);
+                                               if (!res)
+                                                       res = -1;
+                                       } else
+                                               res = memcmp(s1, s2, len1);
+
+                                       return (res);
+
+                               } else {
+                                       int res = 0;
+                                       size_t i, maxlen;
+
+                                       i = 0;
+                                       maxlen = len1;
+
+                                       if (maxlen > len2)
+                                               maxlen = len2;
+
+                                       while (i < maxlen) {
+                                               /* goto next non-zero part: */
+                                               while ((i < maxlen) &&
+                                                   !s1[i] && !s2[i])
+                                                       ++i;
+
+                                               if (i >= maxlen)
+                                                       break;
+
+                                               if (s1[i] == 0) {
+                                                       if (s2[i] == 0)
+                                                               /* NOTREACHED */
+                                                               err(2, "bwscoll error 01");
+                                                       else
+                                                               return (-1);
+                                               } else if (s2[i] == 0)
+                                                       return (+1);
+
+                                               res = strcoll((const char*)(s1 + i), (const char*)(s2 + i));
+                                               if (res)
+                                                       return (res);
+
+                                               while ((i < maxlen) &&
+                                                   s1[i] && s2[i])
+                                                       ++i;
+
+                                               if (i >= maxlen)
+                                                       break;
+
+                                               if (s1[i] == 0) {
+                                                       if (s2[i] == 0) {
+                                                               ++i;
+                                                               continue;
+                                                       } else
+                                                               return (-1);
+                                               } else if (s2[i] == 0)
+                                                       return (+1);
+                                               else
+                                                       /* NOTREACHED */
+                                                       err(2, "bwscoll error 02");
+                                       }
+
+                                       if (len1 < len2)
+                                               return (-1);
+                                       else if (len1 > len2)
+                                               return (+1);
+
+                                       return (0);
+                               }
+                       } else {
+                               const wchar_t *s1, *s2;
+                               size_t i, maxlen;
+                               int res = 0;
+
+                               s1 = bws1->data.wstr + offset;
+                               s2 = bws2->data.wstr + offset;
+
+                               i = 0;
+                               maxlen = len1;
+
+                               if (maxlen > len2)
+                                       maxlen = len2;
+
+                               while (i < maxlen) {
+
+                                       /* goto next non-zero part: */
+                                       while ((i < maxlen) &&
+                                           !s1[i] && !s2[i])
+                                               ++i;
+
+                                       if (i >= maxlen)
+                                               break;
+
+                                       if (s1[i] == 0) {
+                                               if (s2[i] == 0)
+                                                       /* NOTREACHED */
+                                                       err(2, "bwscoll error 1");
+                                               else
+                                                       return (-1);
+                                       } else if (s2[i] == 0)
+                                               return (+1);
+
+                                       res = wide_str_coll(s1 + i, s2 + i);
+                                       if (res)
+                                               return (res);
+
+                                       while ((i < maxlen) && s1[i] && s2[i])
+                                               ++i;
+
+                                       if (i >= maxlen)
+                                               break;
+
+                                       if (s1[i] == 0) {
+                                               if (s2[i] == 0) {
+                                                       ++i;
+                                                       continue;
+                                               } else
+                                                       return (-1);
+                                       } else if (s2[i] == 0)
+                                               return (+1);
+                                       else
+                                               /* NOTREACHED */
+                                               err(2, "bwscoll error 2");
+                               }
+
+                               if (len1 < len2)
+                                       return (-1);
+                               else if (len1 > len2)
+                                       return (+1);
+
+                               return (0);
+                       }
+               }
+       }
+}
+
+/*
+ * Correction of the system API
+ */
+double
+bwstod(struct bwstring *s0, bool *empty)
+{
+       double ret = 0;
+
+       if (MB_CUR_MAX == 1) {
+               unsigned char *end, *s;
+               char *ep;
+
+               s = s0->data.cstr;
+               end = s + s0->len;
+               ep = NULL;
+
+               while (isblank(*s) && s < end)
+                       ++s;
+
+               if (!isprint(*s)) {
+                       *empty = true;
+                       return (0);
+               }
+
+               ret = strtod((char*)s, &ep);
+               if ((unsigned char*) ep == s) {
+                       *empty = true;
+                       return (0);
+               }
+       } else {
+               wchar_t *end, *ep, *s;
+
+               s = s0->data.wstr;
+               end = s + s0->len;
+               ep = NULL;
+
+               while (iswblank(*s) && s < end)
+                       ++s;
+
+               if (!iswprint(*s)) {
+                       *empty = true;
+                       return (0);
+               }
+
+               ret = wcstod(s, &ep);
+               if (ep == s) {
+                       *empty = true;
+                       return (0);
+               }
+       }
+
+       *empty = false;
+       return (ret);
+}
+
+/*
+ * A helper function for monthcoll.  If a line matches
+ * a month name, it returns (number of the month - 1),
+ * while if there is no match, it just return -1.
+ */
+
+int
+bws_month_score(const struct bwstring *s0)
+{
+
+       if (MB_CUR_MAX == 1) {
+               const unsigned char *end, *s;
+
+               s = s0->data.cstr;
+               end = s + s0->len;
+
+               while (isblank(*s) && s < end)
+                       ++s;
+
+               for (int i = 11; i >= 0; --i) {
+                       if (cmonths[i] &&
+                           (s == (unsigned char*)strstr((const char*)s, (char*)(cmonths[i]))))
+                               return (i);
+               }
+
+       } else {
+               const wchar_t *end, *s;
+
+               s = s0->data.wstr;
+               end = s + s0->len;
+
+               while (iswblank(*s) && s < end)
+                       ++s;
+
+               for (int i = 11; i >= 0; --i) {
+                       if (wmonths[i] && (s == wcsstr(s, wmonths[i])))
+                               return (i);
+               }
+       }
+
+       return (-1);
+}
+
+/*
+ * Rips out leading blanks (-b).
+ */
+struct bwstring *
+ignore_leading_blanks(struct bwstring *str)
+{
+
+       if (MB_CUR_MAX == 1) {
+               unsigned char *dst, *end, *src;
+
+               src = str->data.cstr;
+               dst = src;
+               end = src + str->len;
+
+               while (src < end && isblank(*src))
+                       ++src;
+
+               if (src != dst) {
+                       size_t newlen;
+
+                       newlen = BWSLEN(str) - (src - dst);
+
+                       while (src < end) {
+                               *dst = *src;
+                               ++dst;
+                               ++src;
+                       }
+                       bws_setlen(str, newlen);
+               }
+       } else {
+               wchar_t *dst, *end, *src;
+
+               src = str->data.wstr;
+               dst = src;
+               end = src + str->len;
+
+               while (src < end && iswblank(*src))
+                       ++src;
+
+               if (src != dst) {
+
+                       size_t newlen = BWSLEN(str) - (src - dst);
+
+                       while (src < end) {
+                               *dst = *src;
+                               ++dst;
+                               ++src;
+                       }
+                       bws_setlen(str, newlen);
+
+               }
+       }
+       return (str);
+}
+
+/*
+ * Rips out nonprinting characters (-i).
+ */
+struct bwstring *
+ignore_nonprinting(struct bwstring *str)
+{
+       size_t newlen = str->len;
+
+       if (MB_CUR_MAX == 1) {
+               unsigned char *dst, *end, *src;
+               unsigned char c;
+
+               src = str->data.cstr;
+               dst = src;
+               end = src + str->len;
+
+               while (src < end) {
+                       c = *src;
+                       if (isprint(c)) {
+                               *dst = c;
+                               ++dst;
+                               ++src;
+                       } else {
+                               ++src;
+                               --newlen;
+                       }
+               }
+       } else {
+               wchar_t *dst, *end, *src;
+               wchar_t c;
+
+               src = str->data.wstr;
+               dst = src;
+               end = src + str->len;
+
+               while (src < end) {
+                       c = *src;
+                       if (iswprint(c)) {
+                               *dst = c;
+                               ++dst;
+                               ++src;
+                       } else {
+                               ++src;
+                               --newlen;
+                       }
+               }
+       }
+       bws_setlen(str, newlen);
+
+       return (str);
+}
+
+/*
+ * Rips out any characters that are not alphanumeric characters
+ * nor blanks (-d).
+ */
+struct bwstring *
+dictionary_order(struct bwstring *str)
+{
+       size_t newlen = str->len;
+
+       if (MB_CUR_MAX == 1) {
+               unsigned char *dst, *end, *src;
+               unsigned char c;
+
+               src = str->data.cstr;
+               dst = src;
+               end = src + str->len;
+
+               while (src < end) {
+                       c = *src;
+                       if (isalnum(c) || isblank(c)) {
+                               *dst = c;
+                               ++dst;
+                               ++src;
+                       } else {
+                               ++src;
+                               --newlen;
+                       }
+               }
+       } else {
+               wchar_t *dst, *end, *src;
+               wchar_t c;
+
+               src = str->data.wstr;
+               dst = src;
+               end = src + str->len;
+
+               while (src < end) {
+                       c = *src;
+                       if (iswalnum(c) || iswblank(c)) {
+                               *dst = c;
+                               ++dst;
+                               ++src;
+                       } else {
+                               ++src;
+                               --newlen;
+                       }
+               }
+       }
+       bws_setlen(str, newlen);
+
+       return (str);
+}
+
+/*
+ * Converts string to lower case(-f).
+ */
+struct bwstring *
+ignore_case(struct bwstring *str)
+{
+
+       if (MB_CUR_MAX == 1) {
+               unsigned char *end, *s;
+
+               s = str->data.cstr;
+               end = s + str->len;
+
+               while (s < end) {
+                       *s = toupper(*s);
+                       ++s;
+               }
+       } else {
+               wchar_t *end, *s;
+
+               s = str->data.wstr;
+               end = s + str->len;
+
+               while (s < end) {
+                       *s = towupper(*s);
+                       ++s;
+               }
+       }
+       return (str);
+}
+
+void
+bws_disorder_warnx(struct bwstring *s, const char *fn, size_t pos)
+{
+
+       if (MB_CUR_MAX == 1)
+               warnx("%s:%zu: disorder: %s", fn, pos + 1, s->data.cstr);
+       else
+               warnx("%s:%zu: disorder: %ls", fn, pos + 1, s->data.wstr);
+}
diff --git a/usr.bin/sort/bwstring.h b/usr.bin/sort/bwstring.h
new file mode 100644 (file)
index 0000000..857de13
--- /dev/null
@@ -0,0 +1,142 @@
+/*     $FreeBSD: head/usr.bin/sort/bwstring.h 264744 2014-04-21 22:52:18Z pfg $        */
+
+/*-
+ * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if !defined(__BWSTRING_H__)
+#define        __BWSTRING_H__
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <errno.h>
+#include <sysexits.h>
+#include <wchar.h>
+
+#include "mem.h"
+
+extern bool byte_sort;
+
+/* wchar_t is of 4 bytes: */
+#define        SIZEOF_WCHAR_STRING(LEN) ((LEN)*sizeof(wchar_t))
+
+/*
+ * Binary "wide" string
+ */
+struct bwstring
+{
+       size_t                          len;
+       union
+       {
+               wchar_t         wstr[0];
+               unsigned char   cstr[0];
+       }                               data;
+};
+
+struct reader_buffer
+{
+       wchar_t                 *fgetwln_z_buffer;
+       size_t                   fgetwln_z_buffer_size;
+};
+
+typedef void *bwstring_iterator;
+
+#define        BWSLEN(s) ((s)->len)
+
+struct bwstring *bwsalloc(size_t sz);
+
+size_t bwsrawlen(const struct bwstring *bws);
+const void* bwsrawdata(const struct bwstring *bws);
+void bws_setlen(struct bwstring *bws, size_t newlen);
+size_t bws_memsize(const struct bwstring *bws);
+double bwstod(struct bwstring *s0, bool *empty);
+int bws_month_score(const struct bwstring *s0);
+
+struct bwstring *ignore_leading_blanks(struct bwstring *str);
+struct bwstring *ignore_nonprinting(struct bwstring *str);
+struct bwstring *dictionary_order(struct bwstring *str);
+struct bwstring *ignore_case(struct bwstring *str);
+
+void bwsprintf(FILE*, struct bwstring*, const char *prefix, const char *suffix);
+void bws_disorder_warnx(struct bwstring *s, const char *fn, size_t pos);
+
+struct bwstring *bwsdup(const struct bwstring *s);
+struct bwstring *bwssbdup(const wchar_t *str, size_t size);
+struct bwstring *bwscsbdup(const unsigned char *str, size_t size);
+void bwsfree(const struct bwstring *s);
+size_t bwscpy(struct bwstring *dst, const struct bwstring *src);
+struct bwstring *bwsncpy(struct bwstring *dst, const struct bwstring *src, size_t size);
+struct bwstring *bwsnocpy(struct bwstring *dst, const struct bwstring *src, size_t offset, size_t size);
+int bwscmp(const struct bwstring *bws1, const struct bwstring *bws2, size_t offset);
+int bwsncmp(const struct bwstring *bws1, const struct bwstring *bws2, size_t offset, size_t len);
+int bwscoll(const struct bwstring *bws1, const struct bwstring *bws2, size_t offset);
+size_t bwsfwrite(struct bwstring *bws, FILE *f, bool zero_ended);
+struct bwstring *bwsfgetln(FILE *file, size_t *len, bool zero_ended, struct reader_buffer *rb);
+
+static inline bwstring_iterator
+bws_begin(struct bwstring *bws)
+{
+
+       return (bwstring_iterator) (&(bws->data));
+}
+
+static inline bwstring_iterator
+bws_end(struct bwstring *bws)
+{
+
+       return ((MB_CUR_MAX == 1) ?
+           (bwstring_iterator) (bws->data.cstr + bws->len) :
+           (bwstring_iterator) (bws->data.wstr + bws->len));
+}
+
+static inline bwstring_iterator
+bws_iterator_inc(bwstring_iterator iter, size_t pos)
+{
+
+       if (MB_CUR_MAX == 1)
+               return ((unsigned char *) iter) + pos;
+       else
+               return ((wchar_t*) iter) + pos;
+}
+
+static inline wchar_t
+bws_get_iter_value(bwstring_iterator iter)
+{
+
+       if (MB_CUR_MAX == 1)
+               return *((unsigned char *) iter);
+       else
+               return *((wchar_t*) iter);
+}
+
+int
+bws_iterator_cmp(bwstring_iterator iter1, bwstring_iterator iter2, size_t len);
+
+#define        BWS_GET(bws, pos) ((MB_CUR_MAX == 1) ? ((bws)->data.cstr[(pos)]) : (bws)->data.wstr[(pos)])
+
+void initialise_months(void);
+
+#endif /* __BWSTRING_H__ */
diff --git a/usr.bin/sort/coll.c b/usr.bin/sort/coll.c
new file mode 100644 (file)
index 0000000..6c4efc9
--- /dev/null
@@ -0,0 +1,1302 @@
+/*-
+ * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD: head/usr.bin/sort/coll.c 281132 2015-04-06 02:35:55Z pfg $
+ */
+
+
+#include <sys/types.h>
+
+#include <errno.h>
+#include <err.h>
+#include <langinfo.h>
+#include <limits.h>
+#include <math.h>
+#include <md5.h>
+#include <stdlib.h>
+#include <string.h>
+#include <wchar.h>
+#include <wctype.h>
+
+#include "coll.h"
+#include "vsort.h"
+
+struct key_specs *keys;
+size_t keys_num = 0;
+
+wint_t symbol_decimal_point = L'.';
+/* there is no default thousands separator in collate rules: */
+wint_t symbol_thousands_sep = 0;
+wint_t symbol_negative_sign = L'-';
+wint_t symbol_positive_sign = L'+';
+
+static int wstrcoll(struct key_value *kv1, struct key_value *kv2, size_t offset);
+static int gnumcoll(struct key_value*, struct key_value *, size_t offset);
+static int monthcoll(struct key_value*, struct key_value *, size_t offset);
+static int numcoll(struct key_value*, struct key_value *, size_t offset);
+static int hnumcoll(struct key_value*, struct key_value *, size_t offset);
+static int randomcoll(struct key_value*, struct key_value *, size_t offset);
+static int versioncoll(struct key_value*, struct key_value *, size_t offset);
+
+/*
+ * Allocate keys array
+ */
+struct keys_array *
+keys_array_alloc(void)
+{
+       struct keys_array *ka;
+       size_t sz;
+
+       sz = keys_array_size();
+       ka = sort_malloc(sz);
+       memset(ka, 0, sz);
+
+       return (ka);
+}
+
+/*
+ * Calculate whether we need key hint space
+ */
+static size_t
+key_hint_size(void)
+{
+
+       return (need_hint ? sizeof(struct key_hint) : 0);
+}
+
+/*
+ * Calculate keys array size
+ */
+size_t
+keys_array_size(void)
+{
+
+       return (keys_num * (sizeof(struct key_value) + key_hint_size()));
+}
+
+/*
+ * Clean data of keys array
+ */
+void
+clean_keys_array(const struct bwstring *s, struct keys_array *ka)
+{
+
+       if (ka) {
+               for (size_t i = 0; i < keys_num; ++i)
+                       if (ka->key[i].k && ka->key[i].k != s)
+                               bwsfree(ka->key[i].k);
+               memset(ka, 0, keys_array_size());
+       }
+}
+
+/*
+ * Set value of a key in the keys set
+ */
+void
+set_key_on_keys_array(struct keys_array *ka, struct bwstring *s, size_t ind)
+{
+
+       if (ka && keys_num > ind) {
+               struct key_value *kv;
+
+               kv = &(ka->key[ind]);
+
+               if (kv->k && kv->k != s)
+                       bwsfree(kv->k);
+               kv->k = s;
+       }
+}
+
+/*
+ * Initialize a sort list item
+ */
+struct sort_list_item *
+sort_list_item_alloc(void)
+{
+       struct sort_list_item *si;
+       size_t sz;
+
+       sz = sizeof(struct sort_list_item) + keys_array_size();
+       si = sort_malloc(sz);
+       memset(si, 0, sz);
+
+       return (si);
+}
+
+size_t
+sort_list_item_size(struct sort_list_item *si)
+{
+       size_t ret = 0;
+
+       if (si) {
+               ret = sizeof(struct sort_list_item) + keys_array_size();
+               if (si->str)
+                       ret += bws_memsize(si->str);
+               for (size_t i = 0; i < keys_num; ++i) {
+                       struct key_value *kv;
+
+                       kv = &(si->ka.key[i]);
+
+                       if (kv->k != si->str)
+                               ret += bws_memsize(kv->k);
+               }
+       }
+       return (ret);
+}
+
+/*
+ * Calculate key for a sort list item
+ */
+static void
+sort_list_item_make_key(struct sort_list_item *si)
+{
+
+       preproc(si->str, &(si->ka));
+}
+
+/*
+ * Set value of a sort list item.
+ * Return combined string and keys memory size.
+ */
+void
+sort_list_item_set(struct sort_list_item *si, struct bwstring *str)
+{
+
+       if (si) {
+               clean_keys_array(si->str, &(si->ka));
+               if (si->str) {
+                       if (si->str == str) {
+                               /* we are trying to reset the same string */
+                               return;
+                       } else {
+                               bwsfree(si->str);
+                               si->str = NULL;
+                       }
+               }
+               si->str = str;
+               sort_list_item_make_key(si);
+       }
+}
+
+/*
+ * De-allocate a sort list item object memory
+ */
+void
+sort_list_item_clean(struct sort_list_item *si)
+{
+
+       if (si) {
+               clean_keys_array(si->str, &(si->ka));
+               if (si->str) {
+                       bwsfree(si->str);
+                       si->str = NULL;
+               }
+       }
+}
+
+/*
+ * Skip columns according to specs
+ */
+static size_t
+skip_cols_to_start(const struct bwstring *s, size_t cols, size_t start,
+    bool skip_blanks, bool *empty_key)
+{
+       if (cols < 1)
+               return (BWSLEN(s) + 1);
+
+       if (skip_blanks)
+               while (start < BWSLEN(s) && iswblank(BWS_GET(s,start)))
+                       ++start;
+
+       while (start < BWSLEN(s) && cols > 1) {
+               --cols;
+               ++start;
+       }
+
+       if (start >= BWSLEN(s))
+               *empty_key = true;
+
+       return (start);
+}
+
+/*
+ * Skip fields according to specs
+ */
+static size_t
+skip_fields_to_start(const struct bwstring *s, size_t fields, bool *empty_field)
+{
+
+       if (fields < 2) {
+               if (BWSLEN(s) == 0)
+                       *empty_field = true;
+               return (0);
+       } else if (!(sort_opts_vals.tflag)) {
+               size_t cpos = 0;
+               bool pb = true;
+
+               while (cpos < BWSLEN(s)) {
+                       bool isblank;
+
+                       isblank = iswblank(BWS_GET(s, cpos));
+
+                       if (isblank && !pb) {
+                               --fields;
+                               if (fields <= 1)
+                                       return (cpos);
+                       }
+                       pb = isblank;
+                       ++cpos;
+               }
+               if (fields > 1)
+                       *empty_field = true;
+               return (cpos);
+       } else {
+               size_t cpos = 0;
+
+               while (cpos < BWSLEN(s)) {
+                       if (BWS_GET(s,cpos) == (wchar_t)sort_opts_vals.field_sep) {
+                               --fields;
+                               if (fields <= 1)
+                                       return (cpos + 1);
+                       }
+                       ++cpos;
+               }
+               if (fields > 1)
+                       *empty_field = true;
+               return (cpos);
+       }
+}
+
+/*
+ * Find fields start
+ */
+static void
+find_field_start(const struct bwstring *s, struct key_specs *ks,
+    size_t *field_start, size_t *key_start, bool *empty_field, bool *empty_key)
+{
+
+       *field_start = skip_fields_to_start(s, ks->f1, empty_field);
+       if (!*empty_field)
+               *key_start = skip_cols_to_start(s, ks->c1, *field_start,
+                   ks->pos1b, empty_key);
+       else
+               *empty_key = true;
+}
+
+/*
+ * Find end key position
+ */
+static size_t
+find_field_end(const struct bwstring *s, struct key_specs *ks)
+{
+       size_t f2, next_field_start, pos_end;
+       bool empty_field, empty_key;
+
+       pos_end = 0;
+       next_field_start = 0;
+       empty_field = false;
+       empty_key = false;
+       f2 = ks->f2;
+
+       if (f2 == 0)
+               return (BWSLEN(s) + 1);
+       else {
+               if (ks->c2 == 0) {
+                       next_field_start = skip_fields_to_start(s, f2 + 1,
+                           &empty_field);
+                       if ((next_field_start > 0) && sort_opts_vals.tflag &&
+                           ((wchar_t)sort_opts_vals.field_sep == BWS_GET(s,
+                           next_field_start - 1)))
+                               --next_field_start;
+               } else
+                       next_field_start = skip_fields_to_start(s, f2,
+                           &empty_field);
+       }
+
+       if (empty_field || (next_field_start >= BWSLEN(s)))
+               return (BWSLEN(s) + 1);
+
+       if (ks->c2) {
+               pos_end = skip_cols_to_start(s, ks->c2, next_field_start,
+                   ks->pos2b, &empty_key);
+               if (pos_end < BWSLEN(s))
+                       ++pos_end;
+       } else
+               pos_end = next_field_start;
+
+       return (pos_end);
+}
+
+/*
+ * Cut a field according to the key specs
+ */
+static struct bwstring *
+cut_field(const struct bwstring *s, struct key_specs *ks)
+{
+       struct bwstring *ret = NULL;
+
+       if (s && ks) {
+               size_t field_start, key_end, key_start, sz;
+               bool empty_field, empty_key;
+
+               field_start = 0;
+               key_start = 0;
+               empty_field = false;
+               empty_key = false;
+
+               find_field_start(s, ks, &field_start, &key_start,
+                   &empty_field, &empty_key);
+
+               if (empty_key)
+                       sz = 0;
+               else {
+                       key_end = find_field_end(s, ks);
+                       sz = (key_end < key_start) ? 0 : (key_end - key_start);
+               }
+
+               ret = bwsalloc(sz);
+               if (sz)
+                       bwsnocpy(ret, s, key_start, sz);
+       } else
+               ret = bwsalloc(0);
+
+       return (ret);
+}
+
+/*
+ * Preprocesses a line applying the necessary transformations
+ * specified by command line options and returns the preprocessed
+ * string, which can be used to compare.
+ */
+int
+preproc(struct bwstring *s, struct keys_array *ka)
+{
+
+       if (sort_opts_vals.kflag)
+               for (size_t i = 0; i < keys_num; i++) {
+                       struct bwstring *key;
+                       struct key_specs *kspecs;
+                       struct sort_mods *sm;
+
+                       kspecs = &(keys[i]);
+                       key = cut_field(s, kspecs);
+
+                       sm = &(kspecs->sm);
+                       if (sm->dflag)
+                               key = dictionary_order(key);
+                       else if (sm->iflag)
+                               key = ignore_nonprinting(key);
+                       if (sm->fflag || sm->Mflag)
+                               key = ignore_case(key);
+
+                       set_key_on_keys_array(ka, key, i);
+               }
+       else {
+               struct bwstring *ret = NULL;
+               struct sort_mods *sm = default_sort_mods;
+
+               if (sm->bflag) {
+                       if (ret == NULL)
+                               ret = bwsdup(s);
+                       ret = ignore_leading_blanks(ret);
+               }
+               if (sm->dflag) {
+                       if (ret == NULL)
+                               ret = bwsdup(s);
+                       ret = dictionary_order(ret);
+               } else if (sm->iflag) {
+                       if (ret == NULL)
+                               ret = bwsdup(s);
+                       ret = ignore_nonprinting(ret);
+               }
+               if (sm->fflag || sm->Mflag) {
+                       if (ret == NULL)
+                               ret = bwsdup(s);
+                       ret = ignore_case(ret);
+               }
+               if (ret == NULL)
+                       set_key_on_keys_array(ka, s, 0);
+               else
+                       set_key_on_keys_array(ka, ret, 0);
+       }
+
+       return 0;
+}
+
+cmpcoll_t
+get_sort_func(struct sort_mods *sm)
+{
+
+       if (sm->nflag)
+               return (numcoll);
+       else if (sm->hflag)
+               return (hnumcoll);
+       else if (sm->gflag)
+               return (gnumcoll);
+       else if (sm->Mflag)
+               return (monthcoll);
+       else if (sm->Rflag)
+               return (randomcoll);
+       else if (sm->Vflag)
+               return (versioncoll);
+       else
+               return (wstrcoll);
+}
+
+/*
+ * Compares the given strings.  Returns a positive number if
+ * the first precedes the second, a negative number if the second is
+ * the preceding one, and zero if they are equal.  This function calls
+ * the underlying collate functions, which done the actual comparison.
+ */
+int
+key_coll(struct keys_array *ps1, struct keys_array *ps2, size_t offset)
+{
+       struct sort_mods *sm;
+       int res = 0;
+
+       for (size_t i = 0; i < keys_num; ++i) {
+               sm = &(keys[i].sm);
+
+               if (sm->rflag)
+                       res = sm->func(&(ps2->key[i]), &(ps1->key[i]), offset);
+               else
+                       res = sm->func(&(ps1->key[i]), &(ps2->key[i]), offset);
+
+               if (res)
+                       break;
+
+               /* offset applies to only the first key */
+               offset = 0;
+       }
+       return (res);
+}
+
+/*
+ * Compare two strings.
+ * Plain symbol-by-symbol comparison.
+ */
+int
+top_level_str_coll(const struct bwstring *s1, const struct bwstring *s2)
+{
+
+       if (default_sort_mods->rflag) {
+               const struct bwstring *tmp;
+
+               tmp = s1;
+               s1 = s2;
+               s2 = tmp;
+       }
+
+       return (bwscoll(s1, s2, 0));
+}
+
+/*
+ * Compare a string and a sort list item, according to the sort specs.
+ */
+int
+str_list_coll(struct bwstring *str1, struct sort_list_item **ss2)
+{
+       struct keys_array *ka1;
+       int ret = 0;
+
+       ka1 = keys_array_alloc();
+
+       preproc(str1, ka1);
+
+       sort_list_item_make_key(*ss2);
+
+       if (debug_sort) {
+               bwsprintf(stdout, str1, "; s1=<", ">");
+               bwsprintf(stdout, (*ss2)->str, ", s2=<", ">");
+       }
+
+       ret = key_coll(ka1, &((*ss2)->ka), 0);
+
+       if (debug_sort)
+               printf("; cmp1=%d", ret);
+
+       clean_keys_array(str1, ka1);
+       sort_free(ka1);
+
+       if ((ret == 0) && !(sort_opts_vals.sflag) && sort_opts_vals.complex_sort) {
+               ret = top_level_str_coll(str1, ((*ss2)->str));
+               if (debug_sort)
+                       printf("; cmp2=%d", ret);
+       }
+
+       if (debug_sort)
+               printf("\n");
+
+       return (ret);
+}
+
+/*
+ * Compare two sort list items, according to the sort specs.
+ */
+int
+list_coll_offset(struct sort_list_item **ss1, struct sort_list_item **ss2,
+    size_t offset)
+{
+       int ret;
+
+       ret = key_coll(&((*ss1)->ka), &((*ss2)->ka), offset);
+
+       if (debug_sort) {
+               if (offset)
+                       printf("; offset=%d", (int) offset);
+               bwsprintf(stdout, ((*ss1)->str), "; s1=<", ">");
+               bwsprintf(stdout, ((*ss2)->str), ", s2=<", ">");
+               printf("; cmp1=%d\n", ret);
+       }
+
+       if (ret)
+               return (ret);
+
+       if (!(sort_opts_vals.sflag) && sort_opts_vals.complex_sort) {
+               ret = top_level_str_coll(((*ss1)->str), ((*ss2)->str));
+               if (debug_sort)
+                       printf("; cmp2=%d\n", ret);
+       }
+
+       return (ret);
+}
+
+/*
+ * Compare two sort list items, according to the sort specs.
+ */
+int
+list_coll(struct sort_list_item **ss1, struct sort_list_item **ss2)
+{
+
+       return (list_coll_offset(ss1, ss2, 0));
+}
+
+#define        LSCDEF(N)                                                       \
+static int                                                             \
+list_coll_##N(struct sort_list_item **ss1, struct sort_list_item **ss2)        \
+{                                                                      \
+                                                                       \
+       return (list_coll_offset(ss1, ss2, N));                         \
+}
+
+LSCDEF(1)
+LSCDEF(2)
+LSCDEF(3)
+LSCDEF(4)
+LSCDEF(5)
+LSCDEF(6)
+LSCDEF(7)
+LSCDEF(8)
+LSCDEF(9)
+LSCDEF(10)
+LSCDEF(11)
+LSCDEF(12)
+LSCDEF(13)
+LSCDEF(14)
+LSCDEF(15)
+LSCDEF(16)
+LSCDEF(17)
+LSCDEF(18)
+LSCDEF(19)
+LSCDEF(20)
+
+listcoll_t
+get_list_call_func(size_t offset)
+{
+       static const listcoll_t lsarray[] = { list_coll, list_coll_1,
+           list_coll_2, list_coll_3, list_coll_4, list_coll_5,
+           list_coll_6, list_coll_7, list_coll_8, list_coll_9,
+           list_coll_10, list_coll_11, list_coll_12, list_coll_13,
+           list_coll_14, list_coll_15, list_coll_16, list_coll_17,
+           list_coll_18, list_coll_19, list_coll_20 };
+
+       if (offset <= 20)
+               return (lsarray[offset]);
+
+       return (list_coll);
+}
+
+/*
+ * Compare two sort list items, only by their original string.
+ */
+int
+list_coll_by_str_only(struct sort_list_item **ss1, struct sort_list_item **ss2)
+{
+
+       return (top_level_str_coll(((*ss1)->str), ((*ss2)->str)));
+}
+
+/*
+ * Maximum size of a number in the string (before or after decimal point)
+ */
+#define MAX_NUM_SIZE (128)
+
+/*
+ * Set suffix value
+ */
+static void setsuffix(wchar_t c, unsigned char *si)
+{
+       switch (c){
+       case L'k':
+       case L'K':
+               *si = 1;
+               break;
+       case L'M':
+               *si = 2;
+               break;
+       case L'G':
+               *si = 3;
+               break;
+       case L'T':
+               *si = 4;
+               break;
+       case L'P':
+               *si = 5;
+               break;
+       case L'E':
+               *si = 6;
+               break;
+       case L'Z':
+               *si = 7;
+               break;
+       case L'Y':
+               *si = 8;
+               break;
+       default:
+               *si = 0;
+       };
+}
+
+/*
+ * Read string s and parse the string into a fixed-decimal-point number.
+ * sign equals -1 if the number is negative (explicit plus is not allowed,
+ * according to GNU sort's "info sort".
+ * The number part before decimal point is in the smain, after the decimal
+ * point is in sfrac, tail is the pointer to the remainder of the string.
+ */
+static int
+read_number(struct bwstring *s0, int *sign, wchar_t *smain, size_t *main_len, wchar_t *sfrac, size_t *frac_len, unsigned char *si)
+{
+       bwstring_iterator s;
+
+       s = bws_begin(s0);
+
+       /* always end the fraction with zero, even if we have no fraction */
+       sfrac[0] = 0;
+
+       while (iswblank(bws_get_iter_value(s)))
+               s = bws_iterator_inc(s, 1);
+
+       if (bws_get_iter_value(s) == (wchar_t)symbol_negative_sign) {
+               *sign = -1;
+               s = bws_iterator_inc(s, 1);
+       }
+
+       // This is '0', not '\0', do not change this
+       while (iswdigit(bws_get_iter_value(s)) &&
+           (bws_get_iter_value(s) == L'0'))
+               s = bws_iterator_inc(s, 1);
+
+       while (bws_get_iter_value(s) && *main_len < MAX_NUM_SIZE) {
+               if (iswdigit(bws_get_iter_value(s))) {
+                       smain[*main_len] = bws_get_iter_value(s);
+                       s = bws_iterator_inc(s, 1);
+                       *main_len += 1;
+               } else if (symbol_thousands_sep &&
+                   (bws_get_iter_value(s) == (wchar_t)symbol_thousands_sep))
+                       s = bws_iterator_inc(s, 1);
+               else
+                       break;
+       }
+
+       smain[*main_len] = 0;
+
+       if (bws_get_iter_value(s) == (wchar_t)symbol_decimal_point) {
+               s = bws_iterator_inc(s, 1);
+               while (iswdigit(bws_get_iter_value(s)) &&
+                   *frac_len < MAX_NUM_SIZE) {
+                       sfrac[*frac_len] = bws_get_iter_value(s);
+                       s = bws_iterator_inc(s, 1);
+                       *frac_len += 1;
+               }
+               sfrac[*frac_len] = 0;
+
+               while (*frac_len > 0 && sfrac[*frac_len - 1] == L'0') {
+                       --(*frac_len);
+                       sfrac[*frac_len] = L'\0';
+               }
+       }
+
+       setsuffix(bws_get_iter_value(s),si);
+
+       if ((*main_len + *frac_len) == 0)
+               *sign = 0;
+
+       return (0);
+}
+
+/*
+ * Implements string sort.
+ */
+static int
+wstrcoll(struct key_value *kv1, struct key_value *kv2, size_t offset)
+{
+
+       if (debug_sort) {
+               if (offset)
+                       printf("; offset=%d\n", (int) offset);
+               bwsprintf(stdout, kv1->k, "; k1=<", ">");
+               printf("(%zu)", BWSLEN(kv1->k));
+               bwsprintf(stdout, kv2->k, ", k2=<", ">");
+               printf("(%zu)", BWSLEN(kv2->k));
+       }
+
+       return (bwscoll(kv1->k, kv2->k, offset));
+}
+
+/*
+ * Compare two suffixes
+ */
+static inline int
+cmpsuffix(unsigned char si1, unsigned char si2)
+{
+
+       return ((char)si1 - (char)si2);
+}
+
+/*
+ * Implements numeric sort for -n and -h.
+ */
+static int
+numcoll_impl(struct key_value *kv1, struct key_value *kv2,
+    size_t offset __unused, bool use_suffix)
+{
+       struct bwstring *s1, *s2;
+       wchar_t sfrac1[MAX_NUM_SIZE + 1], sfrac2[MAX_NUM_SIZE + 1];
+       wchar_t smain1[MAX_NUM_SIZE + 1], smain2[MAX_NUM_SIZE + 1];
+       int cmp_res, sign1, sign2;
+       size_t frac1, frac2, main1, main2;
+       unsigned char SI1, SI2;
+       bool e1, e2, key1_read, key2_read;
+
+       s1 = kv1->k;
+       s2 = kv2->k;
+       sign1 = sign2 = 0;
+       main1 = main2 = 0;
+       frac1 = frac2 = 0;
+
+       cmp_res = 0;
+       key1_read = key2_read = false;
+
+       if (debug_sort) {
+               bwsprintf(stdout, s1, "; k1=<", ">");
+               bwsprintf(stdout, s2, ", k2=<", ">");
+       }
+
+       if (s1 == s2)
+               return (0);
+
+       if (kv1->hint->status == HS_UNINITIALIZED) {
+               /* read the number from the string */
+               read_number(s1, &sign1, smain1, &main1, sfrac1, &frac1, &SI1);
+               key1_read = true;
+               kv1->hint->v.nh.n1 = wcstoull(smain1, NULL, 10);
+               if(main1 < 1 && frac1 < 1)
+                       kv1->hint->v.nh.empty=true;
+               kv1->hint->v.nh.si = SI1;
+               kv1->hint->status = (kv1->hint->v.nh.n1 != ULLONG_MAX) ?
+                   HS_INITIALIZED : HS_ERROR;
+               kv1->hint->v.nh.neg = (sign1 < 0) ? true : false;
+       }
+
+       if (kv2->hint->status == HS_UNINITIALIZED) {
+               /* read the number from the string */
+               read_number(s2, &sign2, smain2, &main2, sfrac2, &frac2,&SI2);
+               key2_read = true;
+               kv2->hint->v.nh.n1 = wcstoull(smain2, NULL, 10);
+               if(main2 < 1 && frac2 < 1)
+                       kv2->hint->v.nh.empty=true;
+               kv2->hint->v.nh.si = SI2;
+               kv2->hint->status = (kv2->hint->v.nh.n1 != ULLONG_MAX) ?
+                   HS_INITIALIZED : HS_ERROR;
+               kv2->hint->v.nh.neg = (sign2 < 0) ? true : false;
+       }
+
+       if (kv1->hint->status == HS_INITIALIZED && kv2->hint->status ==
+           HS_INITIALIZED) {
+               unsigned long long n1, n2;
+               bool neg1, neg2;
+
+               e1 = kv1->hint->v.nh.empty;
+               e2 = kv2->hint->v.nh.empty;
+
+               if (e1 && e2)
+                       return (0);
+
+               neg1 = kv1->hint->v.nh.neg;
+               neg2 = kv2->hint->v.nh.neg;
+
+               if (neg1 && !neg2)
+                       return (-1);
+               if (neg2 && !neg1)
+                       return (+1);
+
+               if (e1)
+                       return (neg2 ? +1 : -1);
+               else if (e2)
+                       return (neg1 ? -1 : +1);
+
+
+               if (use_suffix) {
+                       cmp_res = cmpsuffix(kv1->hint->v.nh.si, kv2->hint->v.nh.si);
+                       if (cmp_res)
+                               return (neg1 ? -cmp_res : cmp_res);
+               }
+
+               n1 = kv1->hint->v.nh.n1;
+               n2 = kv2->hint->v.nh.n1;
+               if (n1 < n2)
+                       return (neg1 ? +1 : -1);
+               else if (n1 > n2)
+                       return (neg1 ? -1 : +1);
+       }
+
+       /* read the numbers from the strings */
+       if (!key1_read)
+               read_number(s1, &sign1, smain1, &main1, sfrac1, &frac1, &SI1);
+       if (!key2_read)
+               read_number(s2, &sign2, smain2, &main2, sfrac2, &frac2, &SI2);
+
+       e1 = ((main1 + frac1) == 0);
+       e2 = ((main2 + frac2) == 0);
+
+       if (e1 && e2)
+               return (0);
+
+       /* we know the result if the signs are different */
+       if (sign1 < 0 && sign2 >= 0)
+               return (-1);
+       if (sign1 >= 0 && sign2 < 0)
+               return (+1);
+
+       if (e1)
+               return ((sign2 < 0) ? +1 : -1);
+       else if (e2)
+               return ((sign1 < 0) ? -1 : +1);
+
+       if (use_suffix) {
+               cmp_res = cmpsuffix(SI1, SI2);
+               if (cmp_res)
+                       return ((sign1 < 0) ? -cmp_res : cmp_res);
+       }
+
+       /* if both numbers are empty assume that the strings are equal */
+       if (main1 < 1 && main2 < 1 && frac1 < 1 && frac2 < 1)
+               return (0);
+
+       /*
+        * if the main part is of different size, we know the result
+        * (because the leading zeros are removed)
+        */
+       if (main1 < main2)
+               cmp_res = -1;
+       else if (main1 > main2)
+               cmp_res = +1;
+       /* if the sizes are equal then simple non-collate string compare gives the correct result */
+       else
+               cmp_res = wcscmp(smain1, smain2);
+
+       /* check fraction */
+       if (!cmp_res)
+               cmp_res = wcscmp(sfrac1, sfrac2);
+
+       if (!cmp_res)
+               return (0);
+
+       /* reverse result if the signs are negative */
+       if (sign1 < 0 && sign2 < 0)
+               cmp_res = -cmp_res;
+
+       return (cmp_res);
+}
+
+/*
+ * Implements numeric sort (-n).
+ */
+static int
+numcoll(struct key_value *kv1, struct key_value *kv2, size_t offset)
+{
+
+       return (numcoll_impl(kv1, kv2, offset, false));
+}
+
+/*
+ * Implements 'human' numeric sort (-h).
+ */
+static int
+hnumcoll(struct key_value *kv1, struct key_value *kv2, size_t offset)
+{
+
+       return (numcoll_impl(kv1, kv2, offset, true));
+}
+
+/*
+ * Implements random sort (-R).
+ */
+static int
+randomcoll(struct key_value *kv1, struct key_value *kv2,
+    size_t offset __unused)
+{
+       struct bwstring *s1, *s2;
+       MD5_CTX ctx1, ctx2;
+       char *b1, *b2;
+
+       s1 = kv1->k;
+       s2 = kv2->k;
+
+       if (debug_sort) {
+               bwsprintf(stdout, s1, "; k1=<", ">");
+               bwsprintf(stdout, s2, ", k2=<", ">");
+       }
+
+       if (s1 == s2)
+               return (0);
+
+       memcpy(&ctx1,&md5_ctx,sizeof(MD5_CTX));
+       memcpy(&ctx2,&md5_ctx,sizeof(MD5_CTX));
+
+       MD5Update(&ctx1, bwsrawdata(s1), bwsrawlen(s1));
+       MD5Update(&ctx2, bwsrawdata(s2), bwsrawlen(s2));
+       b1 = MD5End(&ctx1, NULL);
+       b2 = MD5End(&ctx2, NULL);
+       if (b1 == NULL) {
+               if (b2 == NULL)
+                       return (0);
+               else {
+                       sort_free(b2);
+                       return (-1);
+               }
+       } else if (b2 == NULL) {
+               sort_free(b1);
+               return (+1);
+       } else {
+               int cmp_res;
+
+               cmp_res = strcmp(b1,b2);
+               sort_free(b1);
+               sort_free(b2);
+
+               if (!cmp_res)
+                       cmp_res = bwscoll(s1, s2, 0);
+
+               return (cmp_res);
+       }
+}
+
+/*
+ * Implements version sort (-V).
+ */
+static int
+versioncoll(struct key_value *kv1, struct key_value *kv2,
+    size_t offset __unused)
+{
+       struct bwstring *s1, *s2;
+
+       s1 = kv1->k;
+       s2 = kv2->k;
+
+       if (debug_sort) {
+               bwsprintf(stdout, s1, "; k1=<", ">");
+               bwsprintf(stdout, s2, ", k2=<", ">");
+       }
+
+       if (s1 == s2)
+               return (0);
+
+       return (vcmp(s1, s2));
+}
+
+/*
+ * Check for minus infinity
+ */
+static inline bool
+huge_minus(double d, int err1)
+{
+
+       if (err1 == ERANGE)
+               if (d == -HUGE_VAL || d == -HUGE_VALF || d == -HUGE_VALL)
+                       return (+1);
+
+       return (0);
+}
+
+/*
+ * Check for plus infinity
+ */
+static inline bool
+huge_plus(double d, int err1)
+{
+
+       if (err1 == ERANGE)
+               if (d == HUGE_VAL || d == HUGE_VALF || d == HUGE_VALL)
+                       return (+1);
+
+       return (0);
+}
+
+/*
+ * Check whether a function is a NAN
+ */
+static bool
+is_nan(double d)
+{
+
+       return ((d == NAN) || (isnan(d)));
+}
+
+/*
+ * Compare two NANs
+ */
+static int
+cmp_nans(double d1, double d2)
+{
+
+       if (d1 < d2)
+               return (-1);
+       if (d2 > d2)
+               return (+1);
+       return (0);
+}
+
+/*
+ * Implements general numeric sort (-g).
+ */
+static int
+gnumcoll(struct key_value *kv1, struct key_value *kv2,
+    size_t offset __unused)
+{
+       double d1, d2;
+       int err1, err2;
+       bool empty1, empty2, key1_read, key2_read;
+
+       d1 = d2 = 0;
+       err1 = err2 = 0;
+       key1_read = key2_read = false;
+
+       if (debug_sort) {
+               bwsprintf(stdout, kv1->k, "; k1=<", ">");
+               bwsprintf(stdout, kv2->k, "; k2=<", ">");
+       }
+
+       if (kv1->hint->status == HS_UNINITIALIZED) {
+               errno = 0;
+               d1 = bwstod(kv1->k, &empty1);
+               err1 = errno;
+
+               if (empty1)
+                       kv1->hint->v.gh.notnum = true;
+               else if (err1 == 0) {
+                       kv1->hint->v.gh.d = d1;
+                       kv1->hint->v.gh.nan = is_nan(d1);
+                       kv1->hint->status = HS_INITIALIZED;
+               } else
+                       kv1->hint->status = HS_ERROR;
+
+               key1_read = true;
+       }
+
+       if (kv2->hint->status == HS_UNINITIALIZED) {
+               errno = 0;
+               d2 = bwstod(kv2->k, &empty2);
+               err2 = errno;
+
+               if (empty2)
+                       kv2->hint->v.gh.notnum = true;
+               else if (err2 == 0) {
+                       kv2->hint->v.gh.d = d2;
+                       kv2->hint->v.gh.nan = is_nan(d2);
+                       kv2->hint->status = HS_INITIALIZED;
+               } else
+                       kv2->hint->status = HS_ERROR;
+
+               key2_read = true;
+       }
+
+       if (kv1->hint->status == HS_INITIALIZED &&
+           kv2->hint->status == HS_INITIALIZED) {
+               if (kv1->hint->v.gh.notnum)
+                       return ((kv2->hint->v.gh.notnum) ? 0 : -1);
+               else if (kv2->hint->v.gh.notnum)
+                       return (+1);
+
+               if (kv1->hint->v.gh.nan)
+                       return ((kv2->hint->v.gh.nan) ?
+                           cmp_nans(kv1->hint->v.gh.d, kv2->hint->v.gh.d) :
+                           -1);
+               else if (kv2->hint->v.gh.nan)
+                       return (+1);
+
+               d1 = kv1->hint->v.gh.d;
+               d2 = kv2->hint->v.gh.d;
+
+               if (d1 < d2)
+                       return (-1);
+               else if (d1 > d2)
+                       return (+1);
+               else
+                       return (0);
+       }
+
+       if (!key1_read) {
+               errno = 0;
+               d1 = bwstod(kv1->k, &empty1);
+               err1 = errno;
+       }
+
+       if (!key2_read) {
+               errno = 0;
+               d2 = bwstod(kv2->k, &empty2);
+               err2 = errno;
+       }
+
+       /* Non-value case: */
+       if (empty1)
+               return (empty2 ? 0 : -1);
+       else if (empty2)
+               return (+1);
+
+       /* NAN case */
+       if (is_nan(d1))
+               return (is_nan(d2) ? cmp_nans(d1, d2) : -1);
+       else if (is_nan(d2))
+               return (+1);
+
+       /* Infinities */
+       if (err1 == ERANGE || err2 == ERANGE) {
+               /* Minus infinity case */
+               if (huge_minus(d1, err1)) {
+                       if (huge_minus(d2, err2)) {
+                               if (d1 < d2)
+                                       return (-1);
+                               if (d1 > d2)
+                                       return (+1);
+                               return (0);
+                       } else
+                               return (-1);
+
+               } else if (huge_minus(d2, err2)) {
+                       if (huge_minus(d1, err1)) {
+                               if (d1 < d2)
+                                       return (-1);
+                               if (d1 > d2)
+                                       return (+1);
+                               return (0);
+                       } else
+                               return (+1);
+               }
+
+               /* Plus infinity case */
+               if (huge_plus(d1, err1)) {
+                       if (huge_plus(d2, err2)) {
+                               if (d1 < d2)
+                                       return (-1);
+                               if (d1 > d2)
+                                       return (+1);
+                               return (0);
+                       } else
+                               return (+1);
+               } else if (huge_plus(d2, err2)) {
+                       if (huge_plus(d1, err1)) {
+                               if (d1 < d2)
+                                       return (-1);
+                               if (d1 > d2)
+                                       return (+1);
+                               return (0);
+                       } else
+                               return (-1);
+               }
+       }
+
+       if (d1 < d2)
+               return (-1);
+       if (d1 > d2)
+               return (+1);
+
+       return (0);
+}
+
+/*
+ * Implements month sort (-M).
+ */
+static int
+monthcoll(struct key_value *kv1, struct key_value *kv2, size_t offset __unused)
+{
+       int val1, val2;
+       bool key1_read, key2_read;
+
+       val1 = val2 = 0;
+       key1_read = key2_read = false;
+
+       if (debug_sort) {
+               bwsprintf(stdout, kv1->k, "; k1=<", ">");
+               bwsprintf(stdout, kv2->k, "; k2=<", ">");
+       }
+
+       if (kv1->hint->status == HS_UNINITIALIZED) {
+               kv1->hint->v.Mh.m = bws_month_score(kv1->k);
+               key1_read = true;
+               kv1->hint->status = HS_INITIALIZED;
+       }
+
+       if (kv2->hint->status == HS_UNINITIALIZED) {
+               kv2->hint->v.Mh.m = bws_month_score(kv2->k);
+               key2_read = true;
+               kv2->hint->status = HS_INITIALIZED;
+       }
+
+       if (kv1->hint->status == HS_INITIALIZED) {
+               val1 = kv1->hint->v.Mh.m;
+               key1_read = true;
+       }
+
+       if (kv2->hint->status == HS_INITIALIZED) {
+               val2 = kv2->hint->v.Mh.m;
+               key2_read = true;
+       }
+
+       if (!key1_read)
+               val1 = bws_month_score(kv1->k);
+       if (!key2_read)
+               val2 = bws_month_score(kv2->k);
+
+       if (val1 == val2) {
+               return (0);
+       }
+       if (val1 < val2)
+               return (-1);
+       return (+1);
+}
diff --git a/usr.bin/sort/coll.h b/usr.bin/sort/coll.h
new file mode 100644 (file)
index 0000000..3f2a356
--- /dev/null
@@ -0,0 +1,167 @@
+/*     $FreeBSD: head/usr.bin/sort/coll.h 264744 2014-04-21 22:52:18Z pfg $    */
+
+/*-
+ * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if !defined(__COLL_H__)
+#define        __COLL_H__
+
+#include "bwstring.h"
+#include "sort.h"
+
+/*
+ * Sort hint data for -n
+ */
+struct n_hint
+{
+       unsigned long long       n1;
+       unsigned char            si;
+       bool                     empty;
+       bool                     neg;
+};
+
+/*
+ * Sort hint data for -g
+ */
+struct g_hint
+{
+       double                   d;
+       bool                     nan;
+       bool                     notnum;
+};
+
+/*
+ * Sort hint data for -M
+ */
+struct M_hint
+{
+       int                      m;
+};
+
+/*
+ * Status of a sort hint object
+ */
+typedef enum
+{
+       HS_ERROR = -1, HS_UNINITIALIZED = 0, HS_INITIALIZED = 1
+} hint_status;
+
+/*
+ * Sort hint object
+ */
+struct key_hint
+{
+       hint_status             status;
+       union
+       {
+               struct n_hint           nh;
+               struct g_hint           gh;
+               struct M_hint           Mh;
+       }                       v;
+};
+
+/*
+ * Key value
+ */
+struct key_value
+{
+       struct bwstring         *k; /* key string */
+       struct key_hint          hint[0]; /* key sort hint */
+};
+
+/*
+ * Set of keys container object.
+ */
+struct keys_array
+{
+       struct key_value         key[0];
+};
+
+/*
+ * Parsed -k option data
+ */
+struct key_specs
+{
+       struct sort_mods         sm;
+       size_t                   c1;
+       size_t                   c2;
+       size_t                   f1;
+       size_t                   f2;
+       bool                     pos1b;
+       bool                     pos2b;
+};
+
+/*
+ * Single entry in sort list.
+ */
+struct sort_list_item
+{
+       struct bwstring         *str;
+       struct keys_array        ka;
+};
+
+/*
+ * Function type, used to compare two list objects
+ */
+typedef int (*listcoll_t)(struct sort_list_item **ss1, struct sort_list_item **ss2);
+
+extern struct key_specs *keys;
+extern size_t keys_num;
+
+/*
+ * Main localised symbols. These must be wint_t as they may hold WEOF.
+ */
+extern wint_t symbol_decimal_point;
+extern wint_t symbol_thousands_sep;
+extern wint_t symbol_negative_sign;
+extern wint_t symbol_positive_sign;
+
+/* funcs */
+
+cmpcoll_t get_sort_func(struct sort_mods *sm);
+
+struct keys_array *keys_array_alloc(void);
+size_t keys_array_size(void);
+void set_key_on_keys_array(struct keys_array *ka, struct bwstring *s, size_t ind);
+void clean_keys_array(const struct bwstring *s, struct keys_array *ka);
+
+struct sort_list_item *sort_list_item_alloc(void);
+void sort_list_item_set(struct sort_list_item *si, struct bwstring *str);
+void sort_list_item_clean(struct sort_list_item *si);
+size_t sort_list_item_size(struct sort_list_item *si);
+
+int preproc(struct bwstring *s, struct keys_array *ka);
+int top_level_str_coll(const struct bwstring *, const struct bwstring *);
+int key_coll(struct keys_array *ks1, struct keys_array *ks2, size_t offset);
+int str_list_coll(struct bwstring *str1, struct sort_list_item **ss2);
+int list_coll_by_str_only(struct sort_list_item **ss1, struct sort_list_item **ss2);
+int list_coll(struct sort_list_item **ss1, struct sort_list_item **ss2);
+int list_coll_offset(struct sort_list_item **ss1, struct sort_list_item **ss2, size_t offset);
+
+listcoll_t get_list_call_func(size_t offset);
+
+#endif /* __COLL_H__ */
diff --git a/usr.bin/sort/fields.c b/usr.bin/sort/fields.c
deleted file mode 100644 (file)
index 34bde7a..0000000
+++ /dev/null
@@ -1,375 +0,0 @@
-/*     $NetBSD: fields.c,v 1.31 2009/11/06 18:34:22 joerg Exp $        */
-
-/*-
- * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Ben Harris and Jaromir Dolecek.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*-
- * Copyright (c) 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Peter McIlroy.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-/* Subroutines to generate sort keys. */
-
-#include "sort.h"
-
-#define SKIP_BLANKS(ptr) {                                     \
-       if (BLANK & d_mask[*(ptr)])                             \
-               while (BLANK & d_mask[*(++(ptr))]);             \
-}
-
-#define NEXTCOL(pos) {                                         \
-       if (!SEP_FLAG)                                          \
-               while (BLANK & l_d_mask[*(++pos)]);             \
-       while ((*(pos+1) != '\0') && !((FLD_D | REC_D_F) & l_d_mask[*++pos]));\
-}
-               
-static u_char *enterfield(u_char *, const u_char *, struct field *, int);
-static u_char *number(u_char *, const u_char *, u_char *, u_char *, int);
-static u_char *length(u_char *, const u_char *, u_char *, u_char *, int);
-
-#define DECIMAL_POINT '.'
-
-/*
- * constructs sort key with leading recheader, followed by the key,
- * followed by the original line.
- */
-length_t
-enterkey(RECHEADER *keybuf, const u_char *keybuf_end, u_char *line_data,
-    size_t line_size, struct field fieldtable[])
-       /* keybuf:       pointer to start of key */
-{
-       int i;
-       u_char *l_d_mask;
-       u_char *lineend, *pos;
-       const u_char *endkey;
-       u_char *keypos;
-       struct coldesc *clpos;
-       int col = 1;
-       struct field *ftpos;
-
-       l_d_mask = d_mask;
-       pos = line_data - 1;
-       lineend = line_data + line_size-1;
-                               /* don't include rec_delimiter */
-
-       for (i = 0; i < ncols; i++) {
-               clpos = clist + i;
-               for (; (col < clpos->num) && (pos < lineend); col++) {
-                       NEXTCOL(pos);
-               }
-               if (pos >= lineend)
-                       break;
-               clpos->start = SEP_FLAG ? pos + 1 : pos;
-               NEXTCOL(pos);
-               clpos->end = pos;
-               col++;
-               if (pos >= lineend) {
-                       clpos->end = lineend;
-                       i++;
-                       break;
-               }
-       }
-       for (; i <= ncols; i++)
-               clist[i].start = clist[i].end = lineend;
-       if (clist[0].start < line_data)
-               clist[0].start++;
-
-       /*
-        * We write the sort keys (concatenated) followed by the
-        * original line data (for output) as the 'keybuf' data.
-        * keybuf->length is the number of key bytes + data bytes.
-        * keybuf->offset is the number of key bytes.
-        * We add a record separator weight after the key in case
-        * (as is usual) we need to preserve the order of equal lines,
-        * and for 'sort -u'.
-        * The key itself will have had the correct weight applied.
-        */
-       keypos = keybuf->data;
-       endkey = keybuf_end - line_size - 1;
-       if (endkey <= keypos)
-               /* No room for any key bytes */
-               return 1;
-
-       for (ftpos = fieldtable + 1; ftpos->icol.num; ftpos++) {
-               if ((keypos = enterfield(keypos, endkey, ftpos,
-                   fieldtable->flags)) == NULL)
-                       return (1);
-       }
-
-       keybuf->offset = keypos - keybuf->data;
-       keybuf->length = keybuf->offset + line_size;
-
-       /*
-        * Posix requires that equal keys be further sorted by the
-        * entire original record.
-        * NetBSD has (at least for some time) kept equal keys in
-        * their original order.
-        * For 'sort -u' posix_sort is unset.
-        */
-       keybuf->keylen = posix_sort ? keybuf->length : keybuf->offset;
-
-       memcpy(keypos, line_data, line_size);
-       return (0);
-}
-
-/*
- * constructs a field (as defined by -k) within a key
- */
-static u_char *
-enterfield(u_char *tablepos, const u_char *endkey, struct field *cur_fld,
-    int __attribute__ ((unused)) gflags)
-{
-       u_char *start, *end, *lineend, *mask, *lweight;
-       struct column icol, tcol;
-       u_int flags;
-
-       icol = cur_fld->icol;
-       tcol = cur_fld->tcol;
-       flags = cur_fld->flags;
-       start = icol.p->start;
-       lineend = clist[ncols].end;
-       if (flags & BI)
-               SKIP_BLANKS(start);
-       start += icol.indent;
-       start = min(start, lineend);
-
-       if (!tcol.num)
-               end = lineend;
-       else {
-               if (tcol.indent) {
-                       end = tcol.p->start;
-                       if (flags & BT)
-                               SKIP_BLANKS(end);
-                       end += tcol.indent;
-                       end = min(end, lineend);
-               } else
-                       end = tcol.p->end;
-       }
-
-       if (flags & L)
-               return length(tablepos, endkey, start, end, flags);
-       if (flags & N)
-               return number(tablepos, endkey, start, end, flags);
-
-       /* Bound check space - assuming nothing is skipped */
-       if (tablepos + (end - start) + 1 >= endkey)
-               return NULL;
-
-       mask = cur_fld->mask;
-       lweight = cur_fld->weights;     
-       for (; start < end; start++) {
-               if (!mask || mask[*start]) {
-                       *tablepos++ = lweight[*start];
-               }
-       }
-       /* Add extra byte (absent from lweight) to sort short keys correctly */
-       *tablepos++ = lweight[REC_D];
-       return tablepos;
-}
-
-/*
- * Numbers are converted to a floating point format (exponent & mantissa)
- * so that they compare correctly as sequence of unsigned bytes.
- * Bytes 0x00 and 0xff are used to terminate positive and negative numbers
- * to ensure that 0.123 sorts after 0.12 and -0.123 sorts before -0.12.
- *
- * The first byte contain the overall sign, exponent sign and some of the
- * exponent. These have to be ordered (-ve value, decreasing exponent),
- * zero, (+ve value, increasing exponent).
- *
- * The first byte is 0x80 for zero, 0xc0 for +ve with exponent 0.
- * -ve values are the 1's compliments (so 0x7f isn't used!).
- *
- * This only leaves 63 byte values for +ve exponents - which isn't enough.
- * The largest 4 exponent values are used to hold a byte count of the
- * number of following bytes that contain 8 exponent bits per byte,
- * This lets us sort exponents from -2^31 to +2^31.
- *
- * The mantissa is stored 2 digits per byte offset by 0x40, for negative
- * numbers the order must be reversed (they are bit inverted).
- *
- * Reverse sorts are done by inverting the sign of the number.
- */
-#define MAX_EXP_ENC  ((int)sizeof(int))
-
-static u_char *
-number(u_char *pos, const u_char *bufend, u_char *line, u_char *lineend,
-    int reverse)
-{
-       int exponent = -1;
-       int had_dp = 0;
-       u_char *tline;
-       char ch;
-       unsigned int val;
-       u_char *last_nz_pos;
-       u_char negate;
-
-       if (reverse & R)
-               negate = 0xff;
-       else
-               negate = 0;
-
-       /* Give ourselves space for the key terminator */
-       bufend--;
-
-       /* Ensure we have enough space for the exponent */
-       if (pos + 1 + MAX_EXP_ENC > bufend)
-               return (NULL);
-
-       SKIP_BLANKS(line);
-       if (*line == '-') {     /* set the sign */
-               negate ^= 0xff;
-               line++;
-       }
-       /* eat initial zeroes */
-       for (; *line == '0' && line < lineend; line++)
-               continue;
-
-       /* calculate exponents */
-       if (*line == DECIMAL_POINT) {
-               /* Decimal fraction */
-               had_dp = 1;
-               while (*++line == '0' && line < lineend)
-                       exponent--;
-       } else {
-               /* Large (absolute) value, count digits */
-               for (tline = line; *tline >= '0' && 
-                   *tline <= '9' && tline < lineend; tline++)
-                       exponent++;
-       }
-
-       /* If the first/next character isn't a digit, value is zero */
-       if (*line < '1' || *line > '9' || line >= lineend) {
-               /* This may be "0", "0.00", "000" or "fubar" but sorts as 0 */
-               /* XXX what about NaN, NAN, inf and INF */
-               *pos++ = 0x80;
-               return pos;
-       }
-
-       /* Maybe here we should allow for e+12 (etc) */
-
-       if (exponent < 0x40 - MAX_EXP_ENC && -exponent < 0x40 - MAX_EXP_ENC) {
-               /* Value ok for simple encoding */
-               /* exponent 0 is 0xc0 for +ve numbers and 0x40 for -ve ones */
-               exponent += 0xc0;
-               *pos++ = negate ^ exponent;
-       } else {
-               /* Out or range for a single byte */
-               int c, t;
-               t = exponent > 0 ? exponent : -exponent;
-               /* Count how many 8-bit bytes are needed */
-               for (c = 0; ; c++) {
-                       t >>= 8;
-                       if (t == 0)
-                               break;
-               }
-               /* 'c' better be 0..3 here - but probably 0..1 */
-               /* Offset just outside valid range */
-               t = c + 0x40 - MAX_EXP_ENC;
-               if (exponent < 0)
-                       t = -t;
-               *pos++ = negate ^ (t + 0xc0);
-               /* now add each byte, most significant first */
-               for (; c >= 0; c--)
-                       *pos++ = negate ^ (exponent >> (c * 8));
-       }
-
-       /* Finally add mantissa, 2 digits per byte */
-       for (last_nz_pos = pos; line < lineend; ) {
-               if (pos >= bufend)
-                       return NULL;
-               ch = *line++;
-               val = (ch - '0') * 10;
-               if (val > 90) {
-                       if (ch == DECIMAL_POINT && !had_dp) {
-                               had_dp = 1;
-                               continue;
-                       }
-                       break;
-               }
-               while (line < lineend) {
-                       ch = *line++;
-                       if (ch == DECIMAL_POINT && !had_dp) {
-                               had_dp = 1;
-                               continue;
-                       }
-                       if (ch < '0' || ch > '9')
-                               line = lineend;
-                       else
-                               val += ch - '0';
-                       break;
-               }
-               *pos++ = negate ^ (val + 0x40);
-               if (val != 0)
-                       last_nz_pos = pos;
-       }
-
-       /* Add key terminator, deleting any trailing "00" */
-       *last_nz_pos++ = negate;
-
-       return (last_nz_pos);
-}
-
-static u_char *
-length(u_char *pos, const u_char *bufend, u_char *line, u_char *lineend,
-    int flag)
-{
-       u_char buf[32];
-       int l;
-       SKIP_BLANKS(line);
-       l = snprintf((char *)buf, sizeof(buf), "%td", lineend - line);
-       return number(pos, bufend, buf, buf + l, flag);
-}
diff --git a/usr.bin/sort/file.c b/usr.bin/sort/file.c
new file mode 100644 (file)
index 0000000..c0b18d5
--- /dev/null
@@ -0,0 +1,1597 @@
+/*-
+ * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD: head/usr.bin/sort/file.c 281182 2015-04-07 01:17:49Z pfg $
+ */
+
+
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <sys/queue.h>
+
+#include <err.h>
+#include <fcntl.h>
+#if defined(SORT_THREADS)
+#include <pthread.h>
+#endif
+#include <semaphore.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <wchar.h>
+#include <wctype.h>
+
+#include "coll.h"
+#include "file.h"
+#include "radixsort.h"
+
+unsigned long long free_memory = 1000000;
+unsigned long long available_free_memory = 1000000;
+
+bool use_mmap;
+
+const char *tmpdir = "/var/tmp";
+const char *compress_program;
+
+size_t max_open_files = 16;
+
+/*
+ * How much space we read from file at once
+ */
+#define READ_CHUNK (4096)
+
+/*
+ * File reader structure
+ */
+struct file_reader
+{
+       struct reader_buffer     rb;
+       FILE                    *file;
+       char                    *fname;
+       unsigned char           *buffer;
+       unsigned char           *mmapaddr;
+       unsigned char           *mmapptr;
+       size_t                   bsz;
+       size_t                   cbsz;
+       size_t                   mmapsize;
+       size_t                   strbeg;
+       int                      fd;
+       char                     elsymb;
+};
+
+/*
+ * Structure to be used in file merge process.
+ */
+struct file_header
+{
+       struct file_reader              *fr;
+       struct sort_list_item           *si; /* current top line */
+       size_t                           file_pos;
+};
+
+/*
+ * List elements of "cleanable" files list.
+ */
+struct CLEANABLE_FILE
+{
+       char                            *fn;
+       LIST_ENTRY(CLEANABLE_FILE)       files;
+};
+
+/*
+ * List header of "cleanable" files list.
+ */
+static LIST_HEAD(CLEANABLE_FILES,CLEANABLE_FILE) tmp_files;
+
+/*
+ * Semaphore to protect the tmp file list.
+ * We use semaphore here because it is signal-safe, according to POSIX.
+ * And semaphore does not require pthread library.
+ */
+static sem_t tmp_files_sem;
+
+static void mt_sort(struct sort_list *list,
+    int (*sort_func)(void *, size_t, size_t,
+    int (*)(const void *, const void *)), const char* fn);
+
+/*
+ * Init tmp files list
+ */
+void
+init_tmp_files(void)
+{
+
+       LIST_INIT(&tmp_files);
+       sem_init(&tmp_files_sem, 0, 1);
+}
+
+/*
+ * Save name of a tmp file for signal cleanup
+ */
+void
+tmp_file_atexit(const char *tmp_file)
+{
+
+       if (tmp_file) {
+               sem_wait(&tmp_files_sem);
+               struct CLEANABLE_FILE *item =
+                   sort_malloc(sizeof(struct CLEANABLE_FILE));
+               item->fn = sort_strdup(tmp_file);
+               LIST_INSERT_HEAD(&tmp_files, item, files);
+               sem_post(&tmp_files_sem);
+       }
+}
+
+/*
+ * Clear tmp files
+ */
+void
+clear_tmp_files(void)
+{
+       struct CLEANABLE_FILE *item;
+
+       sem_wait(&tmp_files_sem);
+       LIST_FOREACH(item,&tmp_files,files) {
+               if ((item) && (item->fn))
+                       unlink(item->fn);
+       }
+       sem_post(&tmp_files_sem);
+}
+
+/*
+ * Check whether a file is a temporary file
+ */
+static bool
+file_is_tmp(const char* fn)
+{
+       struct CLEANABLE_FILE *item;
+       bool ret = false;
+
+       if (fn) {
+               sem_wait(&tmp_files_sem);
+               LIST_FOREACH(item,&tmp_files,files) {
+                       if ((item) && (item->fn))
+                               if (strcmp(item->fn, fn) == 0) {
+                                       ret = true;
+                                       break;
+                               }
+               }
+               sem_post(&tmp_files_sem);
+       }
+
+       return (ret);
+}
+
+/*
+ * Generate new temporary file name
+ */
+char *
+new_tmp_file_name(void)
+{
+       static size_t tfcounter = 0;
+       static const char *fn = ".bsdsort.";
+       char *ret;
+       size_t sz;
+
+       sz = strlen(tmpdir) + 1 + strlen(fn) + 32 + 1;
+       ret = sort_malloc(sz);
+
+       sprintf(ret, "%s/%s%d.%lu", tmpdir, fn, (int) getpid(), (unsigned long)(tfcounter++));
+       tmp_file_atexit(ret);
+       return (ret);
+}
+
+/*
+ * Initialize file list
+ */
+void
+file_list_init(struct file_list *fl, bool tmp)
+{
+
+       if (fl) {
+               fl->count = 0;
+               fl->sz = 0;
+               fl->fns = NULL;
+               fl->tmp = tmp;
+       }
+}
+
+/*
+ * Add a file name to the list
+ */
+void
+file_list_add(struct file_list *fl, char *fn, bool allocate)
+{
+
+       if (fl && fn) {
+               if (fl->count >= fl->sz || (fl->fns == NULL)) {
+                       fl->sz = (fl->sz) * 2 + 1;
+                       fl->fns = sort_realloc(fl->fns, fl->sz *
+                           sizeof(char *));
+               }
+               fl->fns[fl->count] = allocate ? sort_strdup(fn) : fn;
+               fl->count += 1;
+       }
+}
+
+/*
+ * Populate file list from array of file names
+ */
+void
+file_list_populate(struct file_list *fl, int argc, char **argv, bool allocate)
+{
+
+       if (fl && argv) {
+               int i;
+
+               for (i = 0; i < argc; i++)
+                       file_list_add(fl, argv[i], allocate);
+       }
+}
+
+/*
+ * Clean file list data and delete the files,
+ * if this is a list of temporary files
+ */
+void
+file_list_clean(struct file_list *fl)
+{
+
+       if (fl) {
+               if (fl->fns) {
+                       size_t i;
+
+                       for (i = 0; i < fl->count; i++) {
+                               if (fl->fns[i]) {
+                                       if (fl->tmp)
+                                               unlink(fl->fns[i]);
+                                       sort_free(fl->fns[i]);
+                                       fl->fns[i] = 0;
+                               }
+                       }
+                       sort_free(fl->fns);
+                       fl->fns = NULL;
+               }
+               fl->sz = 0;
+               fl->count = 0;
+               fl->tmp = false;
+       }
+}
+
+/*
+ * Init sort list
+ */
+void
+sort_list_init(struct sort_list *l)
+{
+
+       if (l) {
+               l->count = 0;
+               l->size = 0;
+               l->memsize = sizeof(struct sort_list);
+               l->list = NULL;
+       }
+}
+
+/*
+ * Add string to sort list
+ */
+void
+sort_list_add(struct sort_list *l, struct bwstring *str)
+{
+
+       if (l && str) {
+               size_t indx = l->count;
+
+               if ((l->list == NULL) || (indx >= l->size)) {
+                       size_t newsize = (l->size + 1) + 1024;
+
+                       l->list = sort_realloc(l->list,
+                           sizeof(struct sort_list_item*) * newsize);
+                       l->memsize += (newsize - l->size) *
+                           sizeof(struct sort_list_item*);
+                       l->size = newsize;
+               }
+               l->list[indx] = sort_list_item_alloc();
+               sort_list_item_set(l->list[indx], str);
+               l->memsize += sort_list_item_size(l->list[indx]);
+               l->count += 1;
+       }
+}
+
+/*
+ * Clean sort list data
+ */
+void
+sort_list_clean(struct sort_list *l)
+{
+
+       if (l) {
+               if (l->list) {
+                       size_t i;
+
+                       for (i = 0; i < l->count; i++) {
+                               struct sort_list_item *item;
+
+                               item = l->list[i];
+
+                               if (item) {
+                                       sort_list_item_clean(item);
+                                       sort_free(item);
+                                       l->list[i] = NULL;
+                               }
+                       }
+                       sort_free(l->list);
+                       l->list = NULL;
+               }
+               l->count = 0;
+               l->size = 0;
+               l->memsize = sizeof(struct sort_list);
+       }
+}
+
+/*
+ * Write sort list to file
+ */
+void
+sort_list_dump(struct sort_list *l, const char *fn)
+{
+
+       if (l && fn) {
+               FILE *f;
+
+               f = openfile(fn, "w");
+               if (f == NULL)
+                       err(2, NULL);
+
+               if (l->list) {
+                       size_t i;
+                       if (!(sort_opts_vals.uflag)) {
+                               for (i = 0; i < l->count; ++i)
+                                       bwsfwrite(l->list[i]->str, f,
+                                           sort_opts_vals.zflag);
+                       } else {
+                               struct sort_list_item *last_printed_item = NULL;
+                               struct sort_list_item *item;
+                               for (i = 0; i < l->count; ++i) {
+                                       item = l->list[i];
+                                       if ((last_printed_item == NULL) ||
+                                           list_coll(&last_printed_item, &item)) {
+                                               bwsfwrite(item->str, f, sort_opts_vals.zflag);
+                                               last_printed_item = item;
+                                       }
+                               }
+                       }
+               }
+
+               closefile(f, fn);
+       }
+}
+
+/*
+ * Checks if the given file is sorted.  Stops at the first disorder,
+ * prints the disordered line and returns 1.
+ */
+int
+check(const char *fn)
+{
+       struct bwstring *s1, *s2, *s1disorder, *s2disorder;
+       struct file_reader *fr;
+       struct keys_array *ka1, *ka2;
+       int res;
+       size_t pos, posdisorder;
+
+       s1 = s2 = s1disorder = s2disorder = NULL;
+       ka1 = ka2 = NULL;
+
+       fr = file_reader_init(fn);
+
+       res = 0;
+       pos = 1;
+       posdisorder = 1;
+
+       if (fr == NULL) {
+               err(2, NULL);
+               goto end;
+       }
+
+       s1 = file_reader_readline(fr);
+       if (s1 == NULL)
+               goto end;
+
+       ka1 = keys_array_alloc();
+       preproc(s1, ka1);
+
+       s2 = file_reader_readline(fr);
+       if (s2 == NULL)
+               goto end;
+
+       ka2 = keys_array_alloc();
+       preproc(s2, ka2);
+
+       for (;;) {
+
+               if (debug_sort) {
+                       bwsprintf(stdout, s2, "s1=<", ">");
+                       bwsprintf(stdout, s1, "s2=<", ">");
+               }
+               int cmp = key_coll(ka2, ka1, 0);
+               if (debug_sort)
+                       printf("; cmp1=%d", cmp);
+
+               if (!cmp && sort_opts_vals.complex_sort &&
+                   !(sort_opts_vals.uflag) && !(sort_opts_vals.sflag)) {
+                       cmp = top_level_str_coll(s2, s1);
+                       if (debug_sort)
+                               printf("; cmp2=%d", cmp);
+               }
+               if (debug_sort)
+                       printf("\n");
+
+               if ((sort_opts_vals.uflag && (cmp <= 0)) || (cmp < 0)) {
+                       if (!(sort_opts_vals.csilentflag)) {
+                               s2disorder = bwsdup(s2);
+                               posdisorder = pos;
+                               if (debug_sort)
+                                       s1disorder = bwsdup(s1);
+                       }
+                       res = 1;
+                       goto end;
+               }
+
+               pos++;
+
+               clean_keys_array(s1, ka1);
+               sort_free(ka1);
+               ka1 = ka2;
+               ka2 = NULL;
+
+               bwsfree(s1);
+               s1 = s2;
+
+               s2 = file_reader_readline(fr);
+               if (s2 == NULL)
+                       goto end;
+
+               ka2 = keys_array_alloc();
+               preproc(s2, ka2);
+       }
+
+end:
+       if (ka1) {
+               clean_keys_array(s1, ka1);
+               sort_free(ka1);
+       }
+
+       if (s1)
+               bwsfree(s1);
+
+       if (ka2) {
+               clean_keys_array(s2, ka2);
+               sort_free(ka2);
+       }
+
+       if (s2)
+               bwsfree(s2);
+
+       if ((fn == NULL) || (*fn == 0) || (strcmp(fn, "-") == 0)) {
+               for (;;) {
+                       s2 = file_reader_readline(fr);
+                       if (s2 == NULL)
+                               break;
+                       bwsfree(s2);
+               }
+       }
+
+       file_reader_free(fr);
+
+       if (s2disorder) {
+               bws_disorder_warnx(s2disorder, fn, posdisorder);
+               if (s1disorder) {
+                       bws_disorder_warnx(s1disorder, fn, posdisorder);
+                       if (s1disorder != s2disorder)
+                               bwsfree(s1disorder);
+               }
+               bwsfree(s2disorder);
+               s1disorder = NULL;
+               s2disorder = NULL;
+       }
+
+       if (res)
+               exit(res);
+
+       return (0);
+}
+
+/*
+ * Opens a file.  If the given filename is "-", stdout will be
+ * opened.
+ */
+FILE *
+openfile(const char *fn, const char *mode)
+{
+       FILE *file;
+
+       if (strcmp(fn, "-") == 0) {
+               return ((mode && mode[0] == 'r') ? stdin : stdout);
+       } else {
+               mode_t orig_file_mask = 0;
+               int is_tmp = file_is_tmp(fn);
+
+               if (is_tmp && (mode[0] == 'w'))
+                       orig_file_mask = umask(S_IWGRP | S_IWOTH |
+                           S_IRGRP | S_IROTH);
+
+               if (is_tmp && (compress_program != NULL)) {
+                       char *cmd;
+                       size_t cmdsz;
+
+                       cmdsz = strlen(fn) + 128;
+                       cmd = sort_malloc(cmdsz);
+
+                       fflush(stdout);
+
+                       if (mode[0] == 'r')
+                               snprintf(cmd, cmdsz - 1, "cat %s | %s -d",
+                                   fn, compress_program);
+                       else if (mode[0] == 'w')
+                               snprintf(cmd, cmdsz - 1, "%s > %s",
+                                   compress_program, fn);
+                       else
+                               err(2, "%s", getstr(7));
+
+                       if ((file = popen(cmd, mode)) == NULL)
+                               err(2, NULL);
+
+                       sort_free(cmd);
+
+               } else
+                       if ((file = fopen(fn, mode)) == NULL)
+                               err(2, NULL);
+
+               if (is_tmp && (mode[0] == 'w'))
+                       umask(orig_file_mask);
+       }
+
+       return (file);
+}
+
+/*
+ * Close file
+ */
+void
+closefile(FILE *f, const char *fn)
+{
+       if (f == NULL) {
+               ;
+       } else if (f == stdin) {
+               ;
+       } else if (f == stdout) {
+               fflush(f);
+       } else {
+               if (file_is_tmp(fn) && compress_program != NULL) {
+                       if(pclose(f)<0)
+                               err(2,NULL);
+               } else
+                       fclose(f);
+       }
+}
+
+/*
+ * Reads a file into the internal buffer.
+ */
+struct file_reader *
+file_reader_init(const char *fsrc)
+{
+       struct file_reader *ret;
+
+       if (fsrc == NULL)
+               fsrc = "-";
+
+       ret = sort_malloc(sizeof(struct file_reader));
+       memset(ret, 0, sizeof(struct file_reader));
+
+       ret->elsymb = '\n';
+       if (sort_opts_vals.zflag)
+               ret->elsymb = 0;
+
+       ret->fname = sort_strdup(fsrc);
+
+       if (strcmp(fsrc, "-") && (compress_program == NULL) && use_mmap) {
+
+               do {
+                       struct stat stat_buf;
+                       void *addr;
+                       size_t sz = 0;
+                       int fd, flags;
+
+                       flags = MAP_NOCORE | MAP_NOSYNC;
+                       addr = MAP_FAILED;
+
+                       fd = open(fsrc, O_RDONLY);
+                       if (fd < 0)
+                               err(2, NULL);
+
+                       if (fstat(fd, &stat_buf) < 0) {
+                               close(fd);
+                               break;
+                       }
+
+                       sz = stat_buf.st_size;
+
+#if defined(MAP_PREFAULT_READ)
+                       flags |= MAP_PREFAULT_READ;
+#endif
+
+                       addr = mmap(NULL, sz, PROT_READ, flags, fd, 0);
+                       if (addr == MAP_FAILED) {
+                               close(fd);
+                               break;
+                       }
+
+                       ret->fd = fd;
+                       ret->mmapaddr = addr;
+                       ret->mmapsize = sz;
+                       ret->mmapptr = ret->mmapaddr;
+
+               } while (0);
+       }
+
+       if (ret->mmapaddr == NULL) {
+               ret->file = openfile(fsrc, "r");
+               if (ret->file == NULL)
+                       err(2, NULL);
+
+               if (strcmp(fsrc, "-")) {
+                       ret->cbsz = READ_CHUNK;
+                       ret->buffer = sort_malloc(ret->cbsz);
+                       ret->bsz = 0;
+                       ret->strbeg = 0;
+
+                       ret->bsz = fread(ret->buffer, 1, ret->cbsz, ret->file);
+                       if (ret->bsz == 0) {
+                               if (ferror(ret->file))
+                                       err(2, NULL);
+                       }
+               }
+       }
+
+       return (ret);
+}
+
+struct bwstring *
+file_reader_readline(struct file_reader *fr)
+{
+       struct bwstring *ret = NULL;
+
+       if (fr->mmapaddr) {
+               unsigned char *mmapend;
+
+               mmapend = fr->mmapaddr + fr->mmapsize;
+               if (fr->mmapptr >= mmapend)
+                       return (NULL);
+               else {
+                       unsigned char *strend;
+                       size_t sz;
+
+                       sz = mmapend - fr->mmapptr;
+                       strend = memchr(fr->mmapptr, fr->elsymb, sz);
+
+                       if (strend == NULL) {
+                               ret = bwscsbdup(fr->mmapptr, sz);
+                               fr->mmapptr = mmapend;
+                       } else {
+                               ret = bwscsbdup(fr->mmapptr, strend -
+                                   fr->mmapptr);
+                               fr->mmapptr = strend + 1;
+                       }
+               }
+
+       } else if (fr->file != stdin) {
+               unsigned char *strend;
+               size_t bsz1, remsz, search_start;
+
+               search_start = 0;
+               remsz = 0;
+               strend = NULL;
+
+               if (fr->bsz > fr->strbeg)
+                       remsz = fr->bsz - fr->strbeg;
+
+               /* line read cycle */
+               for (;;) {
+                       if (remsz > search_start)
+                               strend = memchr(fr->buffer + fr->strbeg +
+                                   search_start, fr->elsymb, remsz -
+                                   search_start);
+                       else
+                               strend = NULL;
+
+                       if (strend)
+                               break;
+                       if (feof(fr->file))
+                               break;
+
+                       if (fr->bsz != fr->cbsz)
+                               /* NOTREACHED */
+                               err(2, "File read software error 1");
+
+                       if (remsz > (READ_CHUNK >> 1)) {
+                               search_start = fr->cbsz - fr->strbeg;
+                               fr->cbsz += READ_CHUNK;
+                               fr->buffer = sort_realloc(fr->buffer,
+                                   fr->cbsz);
+                               bsz1 = fread(fr->buffer + fr->bsz, 1,
+                                   READ_CHUNK, fr->file);
+                               if (bsz1 == 0) {
+                                       if (ferror(fr->file))
+                                               err(2, NULL);
+                                       break;
+                               }
+                               fr->bsz += bsz1;
+                               remsz += bsz1;
+                       } else {
+                               if (remsz > 0 && fr->strbeg>0)
+                                       bcopy(fr->buffer + fr->strbeg,
+                                           fr->buffer, remsz);
+
+                               fr->strbeg = 0;
+                               search_start = remsz;
+                               bsz1 = fread(fr->buffer + remsz, 1,
+                                   fr->cbsz - remsz, fr->file);
+                               if (bsz1 == 0) {
+                                       if (ferror(fr->file))
+                                               err(2, NULL);
+                                       break;
+                               }
+                               fr->bsz = remsz + bsz1;
+                               remsz = fr->bsz;
+                       }
+               }
+
+               if (strend == NULL)
+                       strend = fr->buffer + fr->bsz;
+
+               if ((fr->buffer + fr->strbeg <= strend) &&
+                   (fr->strbeg < fr->bsz) && (remsz>0))
+                       ret = bwscsbdup(fr->buffer + fr->strbeg, strend -
+                           fr->buffer - fr->strbeg);
+
+               fr->strbeg = (strend - fr->buffer) + 1;
+
+       } else {
+               size_t len = 0;
+
+               ret = bwsfgetln(fr->file, &len, sort_opts_vals.zflag,
+                   &(fr->rb));
+       }
+
+       return (ret);
+}
+
+static void
+file_reader_clean(struct file_reader *fr)
+{
+
+       if (fr) {
+               if (fr->mmapaddr)
+                       munmap(fr->mmapaddr, fr->mmapsize);
+
+               if (fr->fd)
+                       close(fr->fd);
+
+               if (fr->buffer)
+                       sort_free(fr->buffer);
+
+               if (fr->file)
+                       if (fr->file != stdin)
+                               closefile(fr->file, fr->fname);
+
+               if(fr->fname)
+                       sort_free(fr->fname);
+
+               memset(fr, 0, sizeof(struct file_reader));
+       }
+}
+
+void
+file_reader_free(struct file_reader *fr)
+{
+
+       if (fr) {
+               file_reader_clean(fr);
+               sort_free(fr);
+       }
+}
+
+int
+procfile(const char *fsrc, struct sort_list *list, struct file_list *fl)
+{
+       struct file_reader *fr;
+
+       fr = file_reader_init(fsrc);
+       if (fr == NULL)
+               err(2, NULL);
+
+       /* file browse cycle */
+       for (;;) {
+               struct bwstring *bws;
+
+               bws = file_reader_readline(fr);
+
+               if (bws == NULL)
+                       break;
+
+               sort_list_add(list, bws);
+
+               if (list->memsize >= available_free_memory) {
+                       char *fn;
+
+                       fn = new_tmp_file_name();
+                       sort_list_to_file(list, fn);
+                       file_list_add(fl, fn, false);
+                       sort_list_clean(list);
+               }
+       }
+
+       file_reader_free(fr);
+
+       return (0);
+}
+
+/*
+ * Compare file headers. Files with EOF always go to the end of the list.
+ */
+static int
+file_header_cmp(struct file_header *f1, struct file_header *f2)
+{
+
+       if (f1 == f2)
+               return (0);
+       else {
+               if (f1->fr == NULL) {
+                       return ((f2->fr == NULL) ? 0 : +1);
+               } else if (f2->fr == NULL)
+                       return (-1);
+               else {
+                       int ret;
+
+                       ret = list_coll(&(f1->si), &(f2->si));
+                       if (!ret)
+                               return ((f1->file_pos < f2->file_pos) ? -1 : +1);
+                       return (ret);
+               }
+       }
+}
+
+/*
+ * Allocate and init file header structure
+ */
+static void
+file_header_init(struct file_header **fh, const char *fn, size_t file_pos)
+{
+
+       if (fh && fn) {
+               struct bwstring *line;
+
+               *fh = sort_malloc(sizeof(struct file_header));
+               (*fh)->file_pos = file_pos;
+               (*fh)->fr = file_reader_init(fn);
+               if ((*fh)->fr == NULL) {
+                       perror(fn);
+                       err(2, "%s", getstr(8));
+               }
+               line = file_reader_readline((*fh)->fr);
+               if (line == NULL) {
+                       file_reader_free((*fh)->fr);
+                       (*fh)->fr = NULL;
+                       (*fh)->si = NULL;
+               } else {
+                       (*fh)->si = sort_list_item_alloc();
+                       sort_list_item_set((*fh)->si, line);
+               }
+       }
+}
+
+/*
+ * Close file
+ */
+static void
+file_header_close(struct file_header **fh)
+{
+
+       if (fh && *fh) {
+               if ((*fh)->fr) {
+                       file_reader_free((*fh)->fr);
+                       (*fh)->fr = NULL;
+               }
+               if ((*fh)->si) {
+                       sort_list_item_clean((*fh)->si);
+                       sort_free((*fh)->si);
+                       (*fh)->si = NULL;
+               }
+               sort_free(*fh);
+               *fh = NULL;
+       }
+}
+
+/*
+ * Swap two array elements
+ */
+static void
+file_header_swap(struct file_header **fh, size_t i1, size_t i2)
+{
+       struct file_header *tmp;
+
+       tmp = fh[i1];
+       fh[i1] = fh[i2];
+       fh[i2] = tmp;
+}
+
+/* heap algorithm ==>> */
+
+/*
+ * See heap sort algorithm
+ * "Raises" last element to its right place
+ */
+static void
+file_header_heap_swim(struct file_header **fh, size_t indx)
+{
+
+       if (indx > 0) {
+               size_t parent_index;
+
+               parent_index = (indx - 1) >> 1;
+
+               if (file_header_cmp(fh[indx], fh[parent_index]) < 0) {
+                       /* swap child and parent and continue */
+                       file_header_swap(fh, indx, parent_index);
+                       file_header_heap_swim(fh, parent_index);
+               }
+       }
+}
+
+/*
+ * Sink the top element to its correct position
+ */
+static void
+file_header_heap_sink(struct file_header **fh, size_t indx, size_t size)
+{
+       size_t left_child_index;
+       size_t right_child_index;
+
+       left_child_index = indx + indx + 1;
+       right_child_index = left_child_index + 1;
+
+       if (left_child_index < size) {
+               size_t min_child_index;
+
+               min_child_index = left_child_index;
+
+               if ((right_child_index < size) &&
+                   (file_header_cmp(fh[left_child_index],
+                   fh[right_child_index]) > 0))
+                       min_child_index = right_child_index;
+               if (file_header_cmp(fh[indx], fh[min_child_index]) > 0) {
+                       file_header_swap(fh, indx, min_child_index);
+                       file_header_heap_sink(fh, min_child_index, size);
+               }
+       }
+}
+
+/* <<== heap algorithm */
+
+/*
+ * Adds element to the "left" end
+ */
+static void
+file_header_list_rearrange_from_header(struct file_header **fh, size_t size)
+{
+
+       file_header_heap_sink(fh, 0, size);
+}
+
+/*
+ * Adds element to the "right" end
+ */
+static void
+file_header_list_push(struct file_header *f, struct file_header **fh, size_t size)
+{
+
+       fh[size++] = f;
+       file_header_heap_swim(fh, size - 1);
+}
+
+struct last_printed
+{
+       struct bwstring *str;
+};
+
+/*
+ * Prints the current line of the file
+ */
+static void
+file_header_print(struct file_header *fh, FILE *f_out, struct last_printed *lp)
+{
+
+       if (fh && fh->fr && f_out && fh->si && fh->si->str) {
+               if (sort_opts_vals.uflag) {
+                       if ((lp->str == NULL) || (str_list_coll(lp->str, &(fh->si)))) {
+                               bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);
+                               if (lp->str)
+                                       bwsfree(lp->str);
+                               lp->str = bwsdup(fh->si->str);
+                       }
+               } else
+                       bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);
+       }
+}
+
+/*
+ * Read next line
+ */
+static void
+file_header_read_next(struct file_header *fh)
+{
+
+       if (fh && fh->fr) {
+               struct bwstring *tmp;
+
+               tmp = file_reader_readline(fh->fr);
+               if (tmp == NULL) {
+                       file_reader_free(fh->fr);
+                       fh->fr = NULL;
+                       if (fh->si) {
+                               sort_list_item_clean(fh->si);
+                               sort_free(fh->si);
+                               fh->si = NULL;
+                       }
+               } else {
+                       if (fh->si == NULL)
+                               fh->si = sort_list_item_alloc();
+                       sort_list_item_set(fh->si, tmp);
+               }
+       }
+}
+
+/*
+ * Merge array of "files headers"
+ */
+static void
+file_headers_merge(size_t fnum, struct file_header **fh, FILE *f_out)
+{
+       struct last_printed lp;
+       size_t i;
+
+       memset(&lp, 0, sizeof(lp));
+
+       /*
+        * construct the initial sort structure
+        */
+       for (i = 0; i < fnum; i++)
+               file_header_list_push(fh[i], fh, i);
+
+       while (fh[0]->fr) { /* unfinished files are always in front */
+               /* output the smallest line: */
+               file_header_print(fh[0], f_out, &lp);
+               /* read a new line, if possible: */
+               file_header_read_next(fh[0]);
+               /* re-arrange the list: */
+               file_header_list_rearrange_from_header(fh, fnum);
+       }
+
+       if (lp.str)
+               bwsfree(lp.str);
+}
+
+/*
+ * Merges the given files into the output file, which can be
+ * stdout.
+ */
+static void
+merge_files_array(size_t argc, char **argv, const char *fn_out)
+{
+
+       if (argv && fn_out) {
+               struct file_header **fh;
+               FILE *f_out;
+               size_t i;
+
+               f_out = openfile(fn_out, "w");
+
+               if (f_out == NULL)
+                       err(2, NULL);
+
+               fh = sort_malloc((argc + 1) * sizeof(struct file_header *));
+
+               for (i = 0; i < argc; i++)
+                       file_header_init(fh + i, argv[i], (size_t) i);
+
+               file_headers_merge(argc, fh, f_out);
+
+               for (i = 0; i < argc; i++)
+                       file_header_close(fh + i);
+
+               sort_free(fh);
+
+               closefile(f_out, fn_out);
+       }
+}
+
+/*
+ * Shrinks the file list until its size smaller than max number of opened files
+ */
+static int
+shrink_file_list(struct file_list *fl)
+{
+
+       if ((fl == NULL) || (size_t) (fl->count) < max_open_files)
+               return (0);
+       else {
+               struct file_list new_fl;
+               size_t indx = 0;
+
+               file_list_init(&new_fl, true);
+               while (indx < fl->count) {
+                       char *fnew;
+                       size_t num;
+
+                       num = fl->count - indx;
+                       fnew = new_tmp_file_name();
+
+                       if ((size_t) num >= max_open_files)
+                               num = max_open_files - 1;
+                       merge_files_array(num, fl->fns + indx, fnew);
+                       if (fl->tmp) {
+                               size_t i;
+
+                               for (i = 0; i < num; i++)
+                                       unlink(fl->fns[indx + i]);
+                       }
+                       file_list_add(&new_fl, fnew, false);
+                       indx += num;
+               }
+               fl->tmp = false; /* already taken care of */
+               file_list_clean(fl);
+
+               fl->count = new_fl.count;
+               fl->fns = new_fl.fns;
+               fl->sz = new_fl.sz;
+               fl->tmp = new_fl.tmp;
+
+               return (1);
+       }
+}
+
+/*
+ * Merge list of files
+ */
+void
+merge_files(struct file_list *fl, const char *fn_out)
+{
+
+       if (fl && fn_out) {
+               while (shrink_file_list(fl));
+
+               merge_files_array(fl->count, fl->fns, fn_out);
+       }
+}
+
+static const char *
+get_sort_method_name(int sm)
+{
+
+       if (sm == SORT_MERGESORT)
+               return "mergesort";
+       else if (sort_opts_vals.sort_method == SORT_RADIXSORT)
+               return "radixsort";
+       else if (sort_opts_vals.sort_method == SORT_HEAPSORT)
+               return "heapsort";
+       else
+               return "quicksort";
+}
+
+/*
+ * Wrapper for qsort
+ */
+static int sort_qsort(void *list, size_t count, size_t elem_size,
+    int (*cmp_func)(const void *, const void *))
+{
+
+       qsort(list, count, elem_size, cmp_func);
+       return (0);
+}
+
+/*
+ * Sort list of lines and writes it to the file
+ */
+void
+sort_list_to_file(struct sort_list *list, const char *outfile)
+{
+       struct sort_mods *sm = &(keys[0].sm);
+
+       if (!(sm->Mflag) && !(sm->Rflag) && !(sm->Vflag) && !(sm->Vflag) &&
+           !(sm->gflag) && !(sm->hflag) && !(sm->nflag)) {
+               if ((sort_opts_vals.sort_method == SORT_DEFAULT) && byte_sort)
+                       sort_opts_vals.sort_method = SORT_RADIXSORT;
+
+       } else if (sort_opts_vals.sort_method == SORT_RADIXSORT)
+               err(2, "%s", getstr(9));
+
+       /*
+        * to handle stable sort and the unique cases in the
+        * right order, we need stable basic algorithm
+        */
+       if (sort_opts_vals.sflag) {
+               switch (sort_opts_vals.sort_method){
+               case SORT_MERGESORT:
+                       break;
+               case SORT_RADIXSORT:
+                       break;
+               case SORT_DEFAULT:
+                       sort_opts_vals.sort_method = SORT_MERGESORT;
+                       break;
+               default:
+                       errx(2, "%s", getstr(10));
+               };
+       }
+
+       if (sort_opts_vals.sort_method == SORT_DEFAULT)
+               sort_opts_vals.sort_method = DEFAULT_SORT_ALGORITHM;
+
+       if (debug_sort)
+               printf("sort_method=%s\n",
+                   get_sort_method_name(sort_opts_vals.sort_method));
+
+       switch (sort_opts_vals.sort_method){
+       case SORT_RADIXSORT:
+               rxsort(list->list, list->count);
+               sort_list_dump(list, outfile);
+               break;
+       case SORT_MERGESORT:
+               mt_sort(list, mergesort, outfile);
+               break;
+       case SORT_HEAPSORT:
+               mt_sort(list, heapsort, outfile);
+               break;
+       case SORT_QSORT:
+               mt_sort(list, sort_qsort, outfile);
+               break;
+       default:
+               mt_sort(list, DEFAULT_SORT_FUNC, outfile);
+               break;
+       }
+}
+
+/******************* MT SORT ************************/
+
+#if defined(SORT_THREADS)
+/* semaphore to count threads */
+static sem_t mtsem;
+
+/* current system sort function */
+static int (*g_sort_func)(void *, size_t, size_t,
+    int(*)(const void *, const void *));
+
+/*
+ * Sort cycle thread (in multi-threaded mode)
+ */
+static void*
+mt_sort_thread(void* arg)
+{
+       struct sort_list *list = arg;
+
+       g_sort_func(list->list, list->count, sizeof(struct sort_list_item *),
+           (int(*)(const void *, const void *)) list_coll);
+
+       sem_post(&mtsem);
+
+       return (arg);
+}
+
+/*
+ * Compare sub-lists. Empty sub-lists always go to the end of the list.
+ */
+static int
+sub_list_cmp(struct sort_list *l1, struct sort_list *l2)
+{
+
+       if (l1 == l2)
+               return (0);
+       else {
+               if (l1->count == 0) {
+                       return ((l2->count == 0) ? 0 : +1);
+               } else if (l2->count == 0) {
+                       return (-1);
+               } else {
+                       int ret;
+
+                       ret = list_coll(&(l1->list[0]), &(l2->list[0]));
+                       if (!ret)
+                               return ((l1->sub_list_pos < l2->sub_list_pos) ?
+                                   -1 : +1);
+                       return (ret);
+               }
+       }
+}
+
+/*
+ * Swap two array elements
+ */
+static void
+sub_list_swap(struct sort_list **sl, size_t i1, size_t i2)
+{
+       struct sort_list *tmp;
+
+       tmp = sl[i1];
+       sl[i1] = sl[i2];
+       sl[i2] = tmp;
+}
+
+/* heap algorithm ==>> */
+
+/*
+ * See heap sort algorithm
+ * "Raises" last element to its right place
+ */
+static void
+sub_list_swim(struct sort_list **sl, size_t indx)
+{
+
+       if (indx > 0) {
+               size_t parent_index;
+
+               parent_index = (indx - 1) >> 1;
+
+               if (sub_list_cmp(sl[indx], sl[parent_index]) < 0) {
+                       /* swap child and parent and continue */
+                       sub_list_swap(sl, indx, parent_index);
+                       sub_list_swim(sl, parent_index);
+               }
+       }
+}
+
+/*
+ * Sink the top element to its correct position
+ */
+static void
+sub_list_sink(struct sort_list **sl, size_t indx, size_t size)
+{
+       size_t left_child_index;
+       size_t right_child_index;
+
+       left_child_index = indx + indx + 1;
+       right_child_index = left_child_index + 1;
+
+       if (left_child_index < size) {
+               size_t min_child_index;
+
+               min_child_index = left_child_index;
+
+               if ((right_child_index < size) &&
+                   (sub_list_cmp(sl[left_child_index],
+                   sl[right_child_index]) > 0))
+                       min_child_index = right_child_index;
+               if (sub_list_cmp(sl[indx], sl[min_child_index]) > 0) {
+                       sub_list_swap(sl, indx, min_child_index);
+                       sub_list_sink(sl, min_child_index, size);
+               }
+       }
+}
+
+/* <<== heap algorithm */
+
+/*
+ * Adds element to the "right" end
+ */
+static void
+sub_list_push(struct sort_list *s, struct sort_list **sl, size_t size)
+{
+
+       sl[size++] = s;
+       sub_list_swim(sl, size - 1);
+}
+
+struct last_printed_item
+{
+       struct sort_list_item *item;
+};
+
+/*
+ * Prints the current line of the file
+ */
+static void
+sub_list_header_print(struct sort_list *sl, FILE *f_out,
+    struct last_printed_item *lp)
+{
+
+       if (sl && sl->count && f_out && sl->list[0]->str) {
+               if (sort_opts_vals.uflag) {
+                       if ((lp->item == NULL) || (list_coll(&(lp->item),
+                           &(sl->list[0])))) {
+                               bwsfwrite(sl->list[0]->str, f_out,
+                                   sort_opts_vals.zflag);
+                               lp->item = sl->list[0];
+                       }
+               } else
+                       bwsfwrite(sl->list[0]->str, f_out,
+                           sort_opts_vals.zflag);
+       }
+}
+
+/*
+ * Read next line
+ */
+static void
+sub_list_next(struct sort_list *sl)
+{
+
+       if (sl && sl->count) {
+               sl->list += 1;
+               sl->count -= 1;
+       }
+}
+
+/*
+ * Merge sub-lists to a file
+ */
+static void
+merge_sub_lists(struct sort_list **sl, size_t n, FILE* f_out)
+{
+       struct last_printed_item lp;
+       size_t i;
+
+       memset(&lp,0,sizeof(lp));
+
+       /* construct the initial list: */
+       for (i = 0; i < n; i++)
+               sub_list_push(sl[i], sl, i);
+
+       while (sl[0]->count) { /* unfinished lists are always in front */
+               /* output the smallest line: */
+               sub_list_header_print(sl[0], f_out, &lp);
+               /* move to a new line, if possible: */
+               sub_list_next(sl[0]);
+               /* re-arrange the list: */
+               sub_list_sink(sl, 0, n);
+       }
+}
+
+/*
+ * Merge sub-lists to a file
+ */
+static void
+merge_list_parts(struct sort_list **parts, size_t n, const char *fn)
+{
+       FILE* f_out;
+
+       f_out = openfile(fn,"w");
+
+       merge_sub_lists(parts, n, f_out);
+
+       closefile(f_out, fn);
+}
+
+#endif /* defined(SORT_THREADS) */
+/*
+ * Multi-threaded sort algorithm "driver"
+ */
+static void
+mt_sort(struct sort_list *list,
+    int(*sort_func)(void *, size_t, size_t, int(*)(const void *, const void *)),
+    const char* fn)
+{
+#if defined(SORT_THREADS)
+       if (nthreads < 2 || list->count < MT_SORT_THRESHOLD) {
+               size_t nthreads_save = nthreads;
+               nthreads = 1;
+#endif
+               /* if single thread or small data, do simple sort */
+               sort_func(list->list, list->count,
+                   sizeof(struct sort_list_item *),
+                   (int(*)(const void *, const void *)) list_coll);
+               sort_list_dump(list, fn);
+#if defined(SORT_THREADS)
+               nthreads = nthreads_save;
+       } else {
+               /* multi-threaded sort */
+               struct sort_list **parts;
+               size_t avgsize, cstart, i;
+
+               /* array of sub-lists */
+               parts = sort_malloc(sizeof(struct sort_list*) * nthreads);
+               cstart = 0;
+               avgsize = list->count / nthreads;
+
+               /* set global system sort function */
+               g_sort_func = sort_func;
+
+               /* set sublists */
+               for (i = 0; i < nthreads; ++i) {
+                       size_t sz = 0;
+
+                       parts[i] = sort_malloc(sizeof(struct sort_list));
+                       parts[i]->list = list->list + cstart;
+                       parts[i]->memsize = 0;
+                       parts[i]->sub_list_pos = i;
+
+                       sz = (i == nthreads - 1) ? list->count - cstart :
+                           avgsize;
+
+                       parts[i]->count = sz;
+
+                       parts[i]->size = parts[i]->count;
+
+                       cstart += sz;
+               }
+
+               /* init threads counting semaphore */
+               sem_init(&mtsem, 0, 0);
+
+               /* start threads */
+               for (i = 0; i < nthreads; ++i) {
+                       pthread_t pth;
+                       pthread_attr_t attr;
+
+                       pthread_attr_init(&attr);
+                       pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
+
+                       for (;;) {
+                               int res = pthread_create(&pth, &attr,
+                                   mt_sort_thread, parts[i]);
+
+                               if (res >= 0)
+                                       break;
+                               if (errno == EAGAIN) {
+                                       pthread_yield();
+                                       continue;
+                               }
+                               err(2, NULL);
+                       }
+
+                       pthread_attr_destroy(&attr);
+               }
+
+               /* wait for threads completion */
+               for (i = 0; i < nthreads; ++i) {
+                       sem_wait(&mtsem);
+               }
+               /* destroy the semaphore - we do not need it anymore */
+               sem_destroy(&mtsem);
+
+               /* merge sorted sub-lists to the file */
+               merge_list_parts(parts, nthreads, fn);
+
+               /* free sub-lists data */
+               for (i = 0; i < nthreads; ++i) {
+                       sort_free(parts[i]);
+               }
+               sort_free(parts);
+       }
+#endif /* defined(SORT_THREADS) */
+}
diff --git a/usr.bin/sort/file.h b/usr.bin/sort/file.h
new file mode 100644 (file)
index 0000000..9fe0e99
--- /dev/null
@@ -0,0 +1,126 @@
+/*     $FreeBSD: head/usr.bin/sort/file.h 281182 2015-04-07 01:17:49Z pfg $    */
+
+/*-
+ * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if !defined(__SORT_FILE_H__)
+#define        __SORT_FILE_H__
+
+#include "coll.h"
+#include "sort.h"
+
+#define        SORT_DEFAULT    0
+#define        SORT_QSORT      1
+#define        SORT_MERGESORT  2
+#define        SORT_HEAPSORT   3
+#define        SORT_RADIXSORT  4
+
+#define        DEFAULT_SORT_ALGORITHM SORT_HEAPSORT
+#define        DEFAULT_SORT_FUNC heapsort
+
+/*
+ * List of data to be sorted.
+ */
+struct sort_list
+{
+       struct sort_list_item   **list;
+       unsigned long long       memsize;
+       size_t                   count;
+       size_t                   size;
+       size_t                   sub_list_pos;
+};
+
+/*
+ * File reader object
+ */
+struct file_reader;
+
+/*
+ * List of files to be sorted
+ */
+struct file_list
+{
+       char                    **fns;
+       size_t                   count;
+       size_t                   sz;
+       bool                     tmp;
+};
+
+/* memory */
+
+/**/
+
+extern unsigned long long free_memory;
+extern unsigned long long available_free_memory;
+
+/* Are we using mmap ? */
+extern bool use_mmap;
+
+/* temporary file dir */
+
+extern const char *tmpdir;
+
+/*
+ * Max number of simultaneously open files (including the output file).
+ */
+extern size_t max_open_files;
+
+/*
+ * Compress program
+ */
+extern const char* compress_program;
+
+/* funcs */
+
+struct file_reader *file_reader_init(const char *fsrc);
+struct bwstring *file_reader_readline(struct file_reader *fr);
+void file_reader_free(struct file_reader *fr);
+
+void init_tmp_files(void);
+void clear_tmp_files(void);
+char *new_tmp_file_name(void);
+void tmp_file_atexit(const char *tmp_file);
+
+void file_list_init(struct file_list *fl, bool tmp);
+void file_list_add(struct file_list *fl, char *fn, bool allocate);
+void file_list_populate(struct file_list *fl, int argc, char **argv, bool allocate);
+void file_list_clean(struct file_list *fl);
+
+int check(const char *);
+void merge_files(struct file_list *fl, const char *fn_out);
+FILE *openfile(const char *, const char *);
+void closefile(FILE *, const char *);
+int procfile(const char *fn, struct sort_list *list, struct file_list *fl);
+
+void sort_list_init(struct sort_list *l);
+void sort_list_add(struct sort_list *l, struct bwstring *str);
+void sort_list_clean(struct sort_list *l);
+void sort_list_dump(struct sort_list *l, const char *fn);
+
+void sort_list_to_file(struct sort_list *list, const char *outfile);
+
+#endif /* __SORT_FILE_H__ */
diff --git a/usr.bin/sort/files.c b/usr.bin/sort/files.c
deleted file mode 100644 (file)
index 631a398..0000000
+++ /dev/null
@@ -1,276 +0,0 @@
-/*     $NetBSD: files.c,v 1.40 2009/10/07 21:03:29 dsl Exp $   */
-
-/*-
- * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Ben Harris and Jaromir Dolecek.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*-
- * Copyright (c) 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Peter McIlroy.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#include "sort.h"
-#include "fsort.h"
-
-#include <string.h>
-
-/* Align records in temporary files to avoid misaligned copies */
-#define REC_ROUNDUP(n) roundup2(n, sizeof(long))
-
-static ssize_t seq(FILE *, u_char **);
-
-/*
- * this is called when there is no special key. It's only called
- * in the first fsort pass.
- */
-
-static u_char *opos;
-static size_t osz;
-
-void
-makeline_copydown(RECHEADER *recbuf)
-{
-       memmove(recbuf->data, opos, osz);
-}
-
-int
-makeline(FILE *fp, RECHEADER *recbuf, u_char *bufend,
-  struct field __attribute ((unused)) *dummy2)
-{
-       u_char *pos;
-       int c;
-
-       pos = recbuf->data;
-       if (osz != 0) {
-               /*
-                * Buffer shortage is solved by either of two ways:
-                * o flush previous buffered data and start using the
-                *   buffer from start.
-                *   makeline_copydown() above must be called.
-                * o realloc buffer
-                * 
-                * This code has relied on realloc changing 'bufend',
-                * but that isn't necessarily true.
-                */
-               pos += osz;
-               osz = 0;
-       }
-
-       while (pos < bufend) {
-               c = getc(fp);
-               if (c == EOF) {
-                       if (pos == recbuf->data) {
-                               FCLOSE(fp);
-                               return EOF;
-                       }
-                       /* Add terminator to partial line */
-                       c = REC_D;
-               }
-               *pos++ = c;
-               if (c == REC_D) {
-                       recbuf->offset = 0;
-                       recbuf->length = pos - recbuf->data;
-                       recbuf->keylen = recbuf->length - 1;
-                       return (0);
-               }
-       }
-
-       /* Ran out of buffer space... */
-       if (recbuf->data < bufend) {
-               /* Remember where the partial record is */
-               osz = pos - recbuf->data;
-               opos = recbuf->data;
-       }
-       return (BUFFEND);
-}
-
-/*
- * This generates keys. It's only called in the first fsort pass
- */
-int
-makekey(FILE *fp, RECHEADER *recbuf, u_char *bufend, struct field *ftbl)
-{
-       static u_char *line_data;
-       static ssize_t line_size;
-       static int overflow = 0;
-
-       /* We get re-entered after returning BUFFEND - save old data */
-       if (overflow) {
-               overflow = enterkey(recbuf, bufend, line_data, line_size, ftbl);
-               return overflow ? BUFFEND : 0;
-       }
-
-       line_size = seq(fp, &line_data);
-       if (line_size == 0) {
-               FCLOSE(fp);
-               return EOF;
-       }
-
-       if (line_size > bufend - recbuf->data) {
-               overflow = 1;
-       } else {
-               overflow = enterkey(recbuf, bufend, line_data, line_size, ftbl);
-       }
-       return overflow ? BUFFEND : 0;
-}
-
-/*
- * get a line of input from fp
- */
-static ssize_t
-seq(FILE *fp, u_char **line)
-{
-       static u_char *buf;
-       static size_t buf_size = DEFLLEN;
-       u_char *end, *pos;
-       int c;
-       u_char *new_buf;
-
-       if (!buf) {
-               /* one-time initialization */
-               buf = malloc(buf_size);
-               if (!buf)
-                   err(2, "malloc of linebuf for %zu bytes failed",
-                           buf_size);
-       }
-
-       end = buf + buf_size;
-       pos = buf;
-       while ((c = getc(fp)) != EOF) {
-               *pos++ = c;
-               if (c == REC_D) {
-                       *line = buf;
-                       return pos - buf;
-               }
-               if (pos == end) {
-                       /* Long line - double size of buffer */
-                       /* XXX: Check here for stupidly long lines */
-                       buf_size *= 2;
-                       new_buf = realloc(buf, buf_size);
-                       if (!new_buf)
-                               err(2, "realloc of linebuf to %zu bytes failed",
-                                       buf_size);
-               
-                       end = new_buf + buf_size;
-                       pos = new_buf + (pos - buf);
-                       buf = new_buf;
-               }
-       }
-
-       if (pos != buf) {
-               /* EOF part way through line - add line terminator */
-               *pos++ = REC_D;
-               *line = buf;
-               return pos - buf;
-       }
-
-       return 0;
-}
-
-/*
- * write a key/line pair to a temporary file
- */
-void
-putrec(const RECHEADER *rec, FILE *fp)
-{
-       EWRITE(rec, 1, REC_ROUNDUP(offsetof(RECHEADER, data) + rec->length), fp);
-}
-
-/*
- * write a line to output
- */
-void
-putline(const RECHEADER *rec, FILE *fp)
-{
-       EWRITE(rec->data+rec->offset, 1, rec->length - rec->offset, fp);
-}
-
-/*
- * write dump of key to output (for -Dk)
- */
-void
-putkeydump(const RECHEADER *rec, FILE *fp)
-{
-       EWRITE(rec, 1, REC_ROUNDUP(offsetof(RECHEADER, data) + rec->offset), fp);
-}
-
-/*
- * get a record from a temporary file. (Used by merge sort.)
- */
-int
-geteasy(FILE *fp, RECHEADER *rec, u_char *end,
-  struct field __attribute__ ((unused)) *dummy2)
-{
-       length_t file_len;
-       int i;
-
-       (void)sizeof (char[offsetof(RECHEADER, length) == 0 ? 1 : -1]);
-
-       if ((u_char *)(rec + 1) > end)
-               return (BUFFEND);
-       if (!fread(&rec->length, 1, sizeof rec->length, fp)) {
-               fclose(fp);
-               return (EOF);
-       }
-       file_len = REC_ROUNDUP(offsetof(RECHEADER, data) + rec->length);
-       if (end - rec->data < (ptrdiff_t)file_len) {
-               for (i = sizeof rec->length - 1; i >= 0;  i--)
-                       ungetc(*((char *) rec + i), fp);
-               return (BUFFEND);
-       }
-
-       fread(&rec->length + 1, file_len - sizeof rec->length, 1, fp);
-       return (0);
-}
diff --git a/usr.bin/sort/fsort.c b/usr.bin/sort/fsort.c
deleted file mode 100644 (file)
index 5668c9b..0000000
+++ /dev/null
@@ -1,200 +0,0 @@
-/*     $NetBSD: fsort.c,v 1.46 2009/11/06 18:34:22 joerg Exp $ */
-
-/*-
- * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Ben Harris and Jaromir Dolecek.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*-
- * Copyright (c) 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Peter McIlroy.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-/*
- * Read in a block of records (until 'enough').
- * sort, write to temp file.
- * Merge sort temp files into output file
- * Small files miss out the temp file stage.
- * Large files might get multiple merges.
- */
-#include "sort.h"
-#include "fsort.h"
-
-#include <stdlib.h>
-#include <string.h>
-
-#define SALIGN(n) roundup2(n, sizeof(length_t))
-
-void
-fsort(struct filelist *filelist, int nfiles, FILE *outfp, struct field *ftbl)
-{
-       RECHEADER **keylist;
-       RECHEADER **keypos, **keyp;
-       RECHEADER *buffer;
-       size_t bufsize = DEFBUFSIZE;
-       u_char *bufend;
-       int mfct = 0;
-       int c, nelem;
-       get_func_t get;
-       RECHEADER *crec;
-       RECHEADER *nbuffer;
-       FILE *fp, *tmp_fp;
-       int file_no;
-       int max_recs = DEBUG('m') ? 16 : MAXNUM;
-
-       buffer = allocrec(NULL, bufsize);
-       bufend = (u_char *)buffer + bufsize;
-       /* Allocate double length keymap for radix_sort */
-       keylist = malloc(2 * max_recs * sizeof(*keylist));
-       if (buffer == NULL || keylist == NULL)
-               err(2, "failed to malloc initial buffer or keylist");
-
-       if (SINGL_FLD)
-               /* Key and data are one! */
-               get = makeline;
-       else
-               /* Key (merged key fields) added before data */
-               get = makekey;
-
-       file_no = 0;
-       fp = fopen(filelist->names[0], "r");
-       if (fp == NULL)
-               err(2, "%s", filelist->names[0]);
-
-       /* Loop through reads of chunk of input files that get sorted
-        * and then merged together. */
-       for (;;) {
-               keypos = keylist;
-               nelem = 0;
-               crec = buffer;
-               makeline_copydown(crec);
-
-               /* Loop reading records */
-               for (;;) {
-                       c = get(fp, crec, bufend, ftbl);
-                       /* 'c' is 0, EOF or BUFFEND */
-                       if (c == 0) {
-                               /* Save start of key in input buffer */
-                               *keypos++ = crec;
-                               if (++nelem == max_recs) {
-                                       c = BUFFEND;
-                                       break;
-                               }
-                               crec = (RECHEADER *)(crec->data + SALIGN(crec->length));
-                               continue;
-                       }
-                       if (c == EOF) {
-                               /* try next file */
-                               if (++file_no >= nfiles)
-                                       /* no more files */
-                                       break;
-                               fp = fopen(filelist->names[file_no], "r");
-                               if (fp == NULL)
-                                       err(2, "%s", filelist->names[file_no]);
-                               continue;
-                       }
-                       if (nelem >= max_recs
-                           || (bufsize >= MAXBUFSIZE && nelem > 8))
-                               /* Need to sort and save this lot of data */
-                               break;
-
-                       /* c == BUFFEND, and we can process more data */
-                       /* Allocate a larger buffer for this lot of data */
-                       bufsize *= 2;
-                       nbuffer = allocrec(buffer, bufsize);
-                       if (!nbuffer) {
-                               err(2, "failed to realloc buffer to %zu bytes",
-                                       bufsize);
-                       }
-
-                       /* patch up keylist[] */
-                       for (keyp = &keypos[-1]; keyp >= keylist; keyp--)
-                               *keyp = nbuffer + (*keyp - buffer);
-
-                       crec = nbuffer + (crec - buffer);
-                       buffer = nbuffer;
-                       bufend = (u_char *)buffer + bufsize;
-               }
-
-               /* Sort this set of records */
-               radix_sort(keylist, keylist + max_recs, nelem);
-
-               if (c == EOF && mfct == 0) {
-                       /* all the data is (sorted) in the buffer */
-                       append(keylist, nelem, outfp,
-                           DEBUG('k') ? putkeydump : putline);
-                       break;
-               }
-
-               /* Save current data to a temporary file for a later merge */
-               if (nelem != 0) {
-                       tmp_fp = ftmp();
-                       append(keylist, nelem, tmp_fp, putrec);
-                       save_for_merge(tmp_fp, geteasy, ftbl);
-               }
-               mfct = 1;
-
-               if (c == EOF) {
-                       /* merge to output file */
-                       merge_sort(outfp, 
-                           DEBUG('k') ? putkeydump : putline, ftbl);
-                       break;
-               }
-       }
-
-       free(keylist);
-       keylist = NULL;
-       free(buffer);
-       buffer = NULL;
-}
diff --git a/usr.bin/sort/fsort.h b/usr.bin/sort/fsort.h
deleted file mode 100644 (file)
index 7610cc6..0000000
+++ /dev/null
@@ -1,78 +0,0 @@
-/*     $NetBSD: fsort.h,v 1.16 2009/09/05 12:00:25 dsl Exp $   */
-
-/*-
- * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Ben Harris and Jaromir Dolecek.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*-
- * Copyright (c) 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Peter McIlroy.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- *     @(#)fsort.h     8.1 (Berkeley) 6/6/93
- */
-
-#define BUFSIZE                (1<<20)
-#define MAXNUM         131072          /* low guess at average record count */
-#define BUFFEND                (EOF-2)
-#define MAXFCT         1000
-#define DEFLLEN                65536
-
-/*
- * Default (initial) and maximum size of record buffer for fsort().
- * Note that no more than MAXNUM records are stored in the buffer,
- * even if the buffer is not full yet.
- */
-#define DEFBUFSIZE     (1 << 20)       /* 1MB */
-#define MAXBUFSIZE     (8 << 20)       /* 10 MB */
diff --git a/usr.bin/sort/init.c b/usr.bin/sort/init.c
deleted file mode 100644 (file)
index d860fa6..0000000
+++ /dev/null
@@ -1,444 +0,0 @@
-/*     $NetBSD: init.c,v 1.27 2010/06/06 00:00:33 wiz Exp $    */
-
-/*-
- * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Ben Harris and Jaromir Dolecek.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*-
- * Copyright (c) 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Peter McIlroy.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#include "sort.h"
-
-#include <ctype.h>
-#include <string.h>
-
-static void insertcol(struct field *);
-static const char *setcolumn(const char *, struct field *);
-
-/*
- * masks of ignored characters.
- */
-static u_char dtable[NBINS], itable[NBINS];
-
-/*
- * parsed key options
- */
-struct coldesc *clist = NULL;
-int ncols = 0;
-
-/*
- * clist (list of columns which correspond to one or more icol or tcol)
- * is in increasing order of columns.
- * Fields are kept in increasing order of fields.
- */
-
-/* 
- * keep clist in order--inserts a column in a sorted array
- */
-static void
-insertcol(struct field *field)
-{
-       int i;
-       struct coldesc *p;
-
-       /* Make space for new item */
-       p = realloc(clist, (ncols + 2) * sizeof(*clist));
-       if (!p)
-               err(1, "realloc");
-       clist = p;
-       memset(&clist[ncols], 0, sizeof(clist[ncols]));
-
-       for (i = 0; i < ncols; i++)
-               if (field->icol.num <= clist[i].num)
-                       break;
-       if (field->icol.num != clist[i].num) {
-               memmove(clist+i+1, clist+i, sizeof(COLDESC)*(ncols-i));
-               clist[i].num = field->icol.num;
-               ncols++;
-       }
-       if (field->tcol.num && field->tcol.num != field->icol.num) {
-               for (i = 0; i < ncols; i++)
-                       if (field->tcol.num <= clist[i].num)
-                               break;
-               if (field->tcol.num != clist[i].num) {
-                       memmove(clist+i+1, clist+i,sizeof(COLDESC)*(ncols-i));
-                       clist[i].num = field->tcol.num;
-                       ncols++;
-               }
-       }
-}
-
-/*
- * matches fields with the appropriate columns--n^2 but who cares?
- */
-void
-fldreset(struct field *fldtab)
-{
-       int i;
-
-       fldtab[0].tcol.p = clist + ncols - 1;
-       for (++fldtab; fldtab->icol.num; ++fldtab) {
-               for (i = 0; fldtab->icol.num != clist[i].num; i++)
-                       ;
-               fldtab->icol.p = clist + i;
-               if (!fldtab->tcol.num)
-                       continue;
-               for (i = 0; fldtab->tcol.num != clist[i].num; i++)
-                       ;
-               fldtab->tcol.p = clist + i;
-       }
-}
-
-/*
- * interprets a column in a -k field
- */
-static const char *
-setcolumn(const char *pos, struct field *cur_fld)
-{
-       struct column *col;
-       char *npos;
-       int tmp;
-       col = cur_fld->icol.num ? (&cur_fld->tcol) : (&cur_fld->icol);
-       col->num = (int) strtol(pos, &npos, 10);
-       pos = npos;
-       if (col->num <= 0 && !(col->num == 0 && col == &(cur_fld->tcol)))
-               errx(2, "field numbers must be positive");
-       if (*pos == '.') {
-               if (!col->num)
-                       errx(2, "cannot indent end of line");
-               ++pos;
-               col->indent = (int) strtol(pos, &npos, 10);
-               pos = npos;
-               if (&cur_fld->icol == col)
-                       col->indent--;
-               if (col->indent < 0)
-                       errx(2, "illegal offset");
-       }
-       for(; (tmp = optval(*pos, cur_fld->tcol.num)); pos++)
-               cur_fld->flags |= tmp;
-       if (cur_fld->icol.num == 0)
-               cur_fld->icol.num = 1;
-       return (pos);
-}
-
-int
-setfield(const char *pos, struct field *cur_fld, int gflag)
-{
-       cur_fld->mask = NULL;
-
-       pos = setcolumn(pos, cur_fld);
-       if (*pos == '\0')                       /* key extends to EOL. */
-               cur_fld->tcol.num = 0;
-       else {
-               if (*pos != ',')
-                       errx(2, "illegal field descriptor");
-               setcolumn((++pos), cur_fld);
-       }
-       if (!cur_fld->flags)
-               cur_fld->flags = gflag;
-       if (REVERSE)
-               /* A local 'r' doesn't invert the global one */
-               cur_fld->flags &= ~R;
-
-       /* Assign appropriate mask table and weight table. */
-       cur_fld->weights = weight_tables[cur_fld->flags & (R | F)];
-       if (cur_fld->flags & I)
-               cur_fld->mask = itable;
-       else if (cur_fld->flags & D)
-               cur_fld->mask = dtable;
-
-       cur_fld->flags |= (gflag & (BI | BT));
-       if (!cur_fld->tcol.indent)      /* BT has no meaning at end of field */
-               cur_fld->flags &= ~BT;
-
-       if (cur_fld->tcol.num
-           && !(!(cur_fld->flags & BI) && cur_fld->flags & BT)
-           && (cur_fld->tcol.num <= cur_fld->icol.num
-                   /* indent if 0 -> end of field, i.e. okay */
-                   && cur_fld->tcol.indent != 0
-                   && cur_fld->tcol.indent < cur_fld->icol.indent))
-               errx(2, "fields out of order");
-
-       insertcol(cur_fld);
-       return (cur_fld->tcol.num);
-}
-
-int
-optval(int desc, int tcolflag)
-{
-       switch(desc) {
-       case 'b':
-               if (!tcolflag)
-                       return BI;
-               else
-                       return BT;
-       case 'd': return D;
-       case 'f': return F;
-       case 'i': return I;
-       case 'l': return L;
-       case 'n': return N;
-       case 'r': return R;
-       default:  return 0;
-       }
-}
-
-/*
- * Return true if the options found in ARG, according to the getopt
- * spec in OPTS, require an additional argv word as an option
- * argument.
- */
-static int
-options_need_argument(const char *arg, const char *opts)
-{
-       size_t pos;
-       const char *s;
-
-       /*assert(arg[0] == '-');*/
-
-       pos = 1;
-       while (arg[pos]) {
-               s = strchr(opts, arg[pos]);
-               if (s == NULL) {
-                       /* invalid option */
-                       return 0;
-               }
-               if (s[1] == ':') {
-                       /* option requires argument */
-                       if (arg[pos+1] == '\0') {
-                               /* no argument in this arg */
-                               return 1;
-                       }
-                       else {
-                               /* argument is in this arg; no more options */
-                               return 0;
-                       }
-               }
-               pos++;
-       }
-       return 0;
-}
-
-/*
- * Replace historic +SPEC arguments with appropriate -kSPEC.
- *
- * The form can be either a single +SPEC or a pair +SPEC -SPEC.
- * The following -SPEC is not recognized unless it follows
- * immediately.
- */ 
-void
-fixit(int *argc, char **argv, const char *opts)
-{
-       int i, j, sawplus;
-       char *vpos, *tpos, spec[20];
-       int col, indent;
-
-       sawplus = 0;
-       for (i = 1; i < *argc; i++) {
-               /*
-                * This loop must stop exactly where getopt will stop.
-                * Otherwise it turns e.g. "sort x +3" into "sort x
-                * -k4.1", which will croak if +3 was in fact really a
-                * file name. In order to do this reliably we need to
-                * be able to identify argv words that are option
-                * arguments.
-                */
-
-               if (!strcmp(argv[i], "--")) {
-                       /* End of options; stop. */
-                       break;
-               }
-
-               if (argv[i][0] == '+') {
-                       /* +POS argument */
-                       sawplus = 1;
-               } else if (argv[i][0] == '-' && sawplus &&
-                          isdigit((unsigned char)argv[i][1])) {
-                       /* -POS argument */
-                       sawplus = 0;
-               } else if (argv[i][0] == '-') {
-                       /* other option */
-                       sawplus = 0;
-                       if (options_need_argument(argv[i], opts)) {
-                               /* skip over the argument */
-                               i++;
-                       }
-                       continue;
-               } else {
-                       /* not an option at all; stop */
-                       sawplus = 0;
-                       break;
-               }
-
-               /*
-                * At this point argv[i] is an old-style spec. The
-                * sawplus flag used by the above loop logic also
-                * tells us if it's a +SPEC or -SPEC.
-                */
-               
-               /* parse spec */
-               tpos = argv[i]+1;
-               col = (int)strtol(tpos, &tpos, 10);
-               if (*tpos == '.') {
-                       ++tpos;
-                       indent = (int) strtol(tpos, &tpos, 10);
-               } else
-                       indent = 0;
-               /* tpos now points to the optional flags */
-
-               /*
-                * In the traditional form, x.0 means beginning of line;
-                * in the new form, x.0 means end of line. Adjust the
-                * value of INDENT accordingly.
-                */
-               if (sawplus) {
-                       /* +POS */
-                       col += 1;
-                       indent += 1;
-               } else {
-                       /* -POS */
-                       if (indent > 0)
-                               col += 1;
-               }
-
-               /* make the new style spec */
-               snprintf(spec, sizeof(spec), "%d.%d%s", col, indent, tpos);
-
-               if (sawplus) {
-                       /* Replace the +POS argument with new-style -kSPEC */
-                       asprintf(&vpos, "-k%s", spec);
-                       argv[i] = vpos;
-               } else {
-                       /*
-                        * Append the spec to the one from the
-                        * preceding +POS argument, and remove the
-                        * current argv element entirely.
-                        */
-                       asprintf(&vpos, "%s,%s", argv[i-1], spec);
-                       free(argv[i-1]);
-                       argv[i-1] = vpos;
-                       for (j=i; j < *argc; j++)
-                               argv[j] = argv[j+1];
-                       *argc -= 1;
-                       i--;
-               }
-       }
-}
-
-/*
- * ascii, Rascii, Ftable, and RFtable map
- *
- * Sorting 'weight' tables.
- * Convert 'ascii' characters into their sort order.
- * The 'F' variants fold lower case to upper equivalent
- * The 'R' variants are for reverse sorting.
- *
- * The record separator (REC_D) never needs a weight, this frees one
- * byte value as an 'end of key' marker. This must be 0 for normal
- * weight tables, and 0xff for reverse weight tables - and is used
- * to terminate keys so that short keys sort before (after if reverse)
- * longer keys.
- *
- * The field separator has a normal weight - although it cannot occur
- * within a key unless it is the default (space+tab).
- *
- * All other bytes map to the appropriate value for the sort order.
- * Numeric sorts don't need any tables, they are reversed by negation.
- *
- * Global reverse sorts are done by writing the sorted keys in reverse
- * order - the sort itself is stil forwards.
- * This means that weights are only ever used when generating keys, any
- * sort of the original data bytes is always forwards and unweighted.
- *
- * Note: this is only good for ASCII sorting.  For different LC 's,
- * all bets are off.
- *
- * itable[] and dtable[] are the masks for -i (ignore non-printables)
- * and -d (only sort blank and alphanumerics).
- */
-void
-settables(void)
-{
-       int i;
-       int next_weight = 1;
-       int rev_weight = 254;
-
-       ascii[REC_D] = 0;
-       Rascii[REC_D] = 255;
-       Ftable[REC_D] = 0;
-       RFtable[REC_D] = 255;
-
-       for (i = 0; i < 256; i++) {
-               if (i == REC_D)
-                       continue;
-               ascii[i] = next_weight;
-               Rascii[i] = rev_weight;
-               if (Ftable[i] == 0) {
-                       Ftable[i] = next_weight;
-                       RFtable[i] = rev_weight;
-                       Ftable[tolower(i)] = next_weight;
-                       RFtable[tolower(i)] = rev_weight;
-               }
-               next_weight++;
-               rev_weight--;
-
-               if (i == '\n' || isprint(i))
-                       itable[i] = 1;
-
-               if (i == '\n' || i == '\t' || i == ' ' || isalnum(i))
-                       dtable[i] = 1;
-       }
-}
diff --git a/usr.bin/sort/mem.c b/usr.bin/sort/mem.c
new file mode 100644 (file)
index 0000000..c8e9546
--- /dev/null
@@ -0,0 +1,81 @@
+/*-
+ * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD: head/usr.bin/sort/mem.c 281132 2015-04-06 02:35:55Z pfg $
+ */
+
+
+#include <err.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "mem.h"
+
+/*
+ * malloc() wrapper.
+ */
+void *
+sort_malloc(size_t size)
+{
+       void *ptr;
+
+       if ((ptr = malloc(size)) == NULL)
+               err(2, NULL);
+       return (ptr);
+}
+
+/*
+ * free() wrapper.
+ */
+void
+sort_free(const void *ptr)
+{
+
+       if (ptr)
+               free(__DECONST(void *, ptr));
+}
+
+/*
+ * realloc() wrapper.
+ */
+void *
+sort_realloc(void *ptr, size_t size)
+{
+
+       if ((ptr = realloc(ptr, size)) == NULL)
+               err(2, NULL);
+       return (ptr);
+}
+
+char *
+sort_strdup(const char *str)
+{
+       char *dup;
+
+       if ((dup = strdup(str)) == NULL)
+               err(2, NULL);
+       return (dup);
+}
diff --git a/usr.bin/sort/mem.h b/usr.bin/sort/mem.h
new file mode 100644 (file)
index 0000000..95ab1ac
--- /dev/null
@@ -0,0 +1,45 @@
+/*     $FreeBSD: head/usr.bin/sort/mem.h 264744 2014-04-21 22:52:18Z pfg $     */
+
+/*-
+ * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if !defined(__SORT_MEM_H__)
+#define        __SORT_MEM_H__
+
+#include <errno.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+/*
+ * mem.c
+ */
+void *sort_malloc(size_t);
+void sort_free(const void *ptr);
+void *sort_realloc(void *, size_t);
+char *sort_strdup(const char *);
+
+#endif /* __SORT_MEM_H__ */
diff --git a/usr.bin/sort/msort.c b/usr.bin/sort/msort.c
deleted file mode 100644 (file)
index a9f7986..0000000
+++ /dev/null
@@ -1,424 +0,0 @@
-/*     $NetBSD: msort.c,v 1.29 2009/11/06 18:34:22 joerg Exp $ */
-
-/*-
- * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Ben Harris and Jaromir Dolecek.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*-
- * Copyright (c) 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Peter McIlroy.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#include "sort.h"
-#include "fsort.h"
-
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-
-/* Subroutines using comparisons: merge sort and check order */
-#define DELETE (1)
-
-typedef struct mfile {
-       FILE         *fp;
-       get_func_t   get;
-       RECHEADER    *rec;
-       u_char       *end;
-} MFILE;
-
-static int cmp(RECHEADER *, RECHEADER *);
-static int insert(struct mfile **, struct mfile *, int, int);
-static void merge_sort_fstack(FILE *, put_func_t, struct field *);
-
-/*
- * Number of files merge() can merge in one pass.
- */
-#define MERGE_FNUM      16
-
-static struct mfile fstack[MERGE_FNUM];
-static struct mfile fstack_1[MERGE_FNUM];
-static struct mfile fstack_2[MERGE_FNUM];
-static int fstack_count, fstack_1_count, fstack_2_count;
-
-void
-save_for_merge(FILE *fp, get_func_t get, struct field *ftbl)
-{
-       FILE *mfp, *mfp1, *mfp2;
-
-       if (fstack_count == MERGE_FNUM) {
-               /* Must reduce the number of temporary files */
-               mfp = ftmp();
-               merge_sort_fstack(mfp, putrec, ftbl);
-               /* Save output in next layer */
-               if (fstack_1_count == MERGE_FNUM) {
-                       mfp1 = ftmp();
-                       memcpy(fstack, fstack_1, sizeof fstack);
-                       merge_sort_fstack(mfp1, putrec, ftbl);
-                       if (fstack_2_count == MERGE_FNUM) {
-                               /* More than 4096 files! */
-                               mfp2 = ftmp();
-                               memcpy(fstack, fstack_2, sizeof fstack);
-                               merge_sort_fstack(mfp2, putrec, ftbl);
-                               fstack_2[0].fp = mfp2;
-                               fstack_2_count = 1;
-                       }
-                       fstack_2[fstack_2_count].fp = mfp1;
-                       fstack_2[fstack_2_count].get = geteasy;
-                       fstack_2_count++;
-                       fstack_1_count = 0;
-               }
-               fstack_1[fstack_1_count].fp = mfp;
-               fstack_1[fstack_1_count].get = geteasy;
-               fstack_1_count++;
-               fstack_count = 0;
-       }
-
-       fstack[fstack_count].fp = fp;
-       fstack[fstack_count++].get = get;
-}
-
-void
-fmerge(struct filelist *filelist, int nfiles, FILE *outfp, struct field *ftbl)
-{
-       get_func_t get = SINGL_FLD ? makeline : makekey;
-       FILE *fp;
-       int i;
-
-       for (i = 0; i < nfiles; i++) {
-               fp = fopen(filelist->names[i], "r");
-               if (fp == NULL)
-                       err(2, "%s", filelist->names[i]);
-               save_for_merge(fp, get, ftbl);
-       }
-
-       merge_sort(outfp, putline, ftbl);
-}
-
-void
-merge_sort(FILE *outfp, put_func_t put, struct field *ftbl)
-{
-       int count = fstack_1_count + fstack_2_count;
-       FILE *mfp;
-       int i;
-
-       if (count == 0) {
-               /* All files in initial array */
-               merge_sort_fstack(outfp, put, ftbl);
-               return;
-       }
-
-       count += fstack_count;
-
-       /* Too many files for one merge sort */
-       for (;;) {
-               /* Sort latest 16 files */
-               i = count;
-               if (i > MERGE_FNUM)
-                       i = MERGE_FNUM;
-               while (fstack_count > 0)
-                       fstack[--i] = fstack[--fstack_count];
-               while (i > 0 && fstack_1_count > 0)
-                       fstack[--i] = fstack_1[--fstack_1_count];
-               while (i > 0)
-                       fstack[--i] = fstack_2[--fstack_2_count];
-               if (count <= MERGE_FNUM) {
-                       /* Got all the data */
-                       fstack_count = count;
-                       merge_sort_fstack(outfp, put, ftbl);
-                       return;
-               }
-               mfp = ftmp();
-               fstack_count = count > MERGE_FNUM ? MERGE_FNUM : count;
-               merge_sort_fstack(mfp, putrec, ftbl);
-               fstack[0].fp = mfp;
-               fstack[0].get = geteasy;
-               fstack_count = 1;
-               count -= MERGE_FNUM - 1;
-       }
-}
-
-static void
-merge_sort_fstack(FILE *outfp, put_func_t put, struct field *ftbl)
-{
-       struct mfile *flistb[MERGE_FNUM], **flist = flistb, *cfile;
-       RECHEADER *new_rec;
-       u_char *new_end;
-       void *tmp;
-       int c, i, nfiles;
-       size_t sz;
-
-       /* Read one record from each file (read again if a duplicate) */
-       for (nfiles = i = 0; i < fstack_count; i++) {
-               cfile = &fstack[i];
-               if (cfile->rec == NULL) {
-                       cfile->rec = allocrec(NULL, DEFLLEN);
-                       cfile->end = (u_char *)cfile->rec + DEFLLEN;
-               }
-               rewind(cfile->fp);
-
-               for (;;) {
-                       c = cfile->get(cfile->fp, cfile->rec, cfile->end, ftbl);
-                       if (c == EOF)
-                               break;
-
-                       if (c == BUFFEND) {
-                               /* Double buffer size */
-                               sz = (cfile->end - (u_char *)cfile->rec) * 2;
-                               cfile->rec = allocrec(cfile->rec, sz);
-                               cfile->end = (u_char *)cfile->rec + sz;
-                               continue;
-                       }
-
-                       if (nfiles != 0) {
-                               if (insert(flist, cfile, nfiles, !DELETE))
-                                       /* Duplicate removed */
-                                       continue;
-                       } else
-                               flist[0] = cfile;
-                       nfiles++;
-                       break;
-               }
-       }
-
-       if (nfiles == 0)
-               return;
-
-       /*
-        * We now loop reading a new record from the file with the
-        * 'sorted first' existing record.
-        * As each record is added, the 'first' record is written to the
-        * output file - maintaining one record from each file in the sorted
-        * list.
-        */
-       new_rec = allocrec(NULL, DEFLLEN);
-       new_end = (u_char *)new_rec + DEFLLEN;
-       for (;;) {
-               cfile = flist[0];
-               c = cfile->get(cfile->fp, new_rec, new_end, ftbl);
-               if (c == EOF) {
-                       /* Write out last record from now-empty input */
-                       put(cfile->rec, outfp);
-                       if (--nfiles == 0)
-                               break;
-                       /* Replace from file with now-first sorted record. */
-                       /* (Moving base 'flist' saves copying everything!) */
-                       flist++;
-                       continue;
-               }
-               if (c == BUFFEND) {
-                       /* Buffer not large enough - double in size */
-                       sz = (new_end - (u_char *)new_rec) * 2;
-                       new_rec = allocrec(new_rec, sz);
-                       new_end = (u_char *)new_rec +sz;
-                       continue;
-               }
-
-               /* Swap in new buffer, saving old */
-               tmp = cfile->rec;
-               cfile->rec = new_rec;
-               new_rec = tmp;
-               tmp = cfile->end;
-               cfile->end = new_end;
-               new_end = tmp;
-
-               /* Add into sort, removing the original first entry */
-               c = insert(flist, cfile, nfiles, DELETE);
-               if (c != 0 || (UNIQUE && cfile == flist[0]
-                           && cmp(new_rec, cfile->rec) == 0)) {
-                       /* Was an unwanted duplicate, restore buffer */
-                       tmp = cfile->rec;
-                       cfile->rec = new_rec;
-                       new_rec = tmp;
-                       tmp = cfile->end;
-                       cfile->end = new_end;
-                       new_end = tmp;
-                       continue;
-               }
-
-               /* Write out 'old' record */
-               put(new_rec, outfp);
-       }
-
-       free(new_rec);
-}
-
-/*
- * if delete: inserts rec in flist, deletes flist[0];
- * otherwise just inserts *rec in flist.
- * Returns 1 if record is a duplicate to be ignored.
- */
-static int
-insert(struct mfile **flist, struct mfile *rec, int ttop, int delete)
-{
-       int mid, top = ttop, bot = 0, cmpv = 1;
-
-       for (mid = top / 2; bot + 1 != top; mid = (bot + top) / 2) {
-               cmpv = cmp(rec->rec, flist[mid]->rec);
-               if (cmpv == 0 ) {
-                       if (UNIQUE)
-                               /* Duplicate key, read another record */
-                               /* NB: This doesn't guarantee to keep any
-                                * particular record. */
-                               return 1;
-                       /*
-                        * Apply sort by input file order.
-                        * We could truncate the sort is the fileno are
-                        * adjacent - but that is all too hard!
-                        * The fileno cannot be equal, since we only have one
-                        * record from each file (+ flist[0] which never
-                        * comes here).
-                        */
-                       cmpv = rec < flist[mid] ? -1 : 1;
-                       if (REVERSE)
-                               cmpv = -cmpv;
-               }
-               if (cmpv < 0)
-                       top = mid;
-               else
-                       bot = mid;
-       }
-
-       /* At this point we haven't yet compared against flist[0] */
-
-       if (delete) {
-               /* flist[0] is ourselves, only the caller knows the old data */
-               if (bot != 0) {
-                       memmove(flist, flist + 1, bot * sizeof(MFILE *));
-                       flist[bot] = rec;
-               }
-               return 0;
-       }
-
-       /* Inserting original set of records */
-
-       if (bot == 0 && cmpv != 0) {
-               /* Doesn't match flist[1], must compare with flist[0] */
-               cmpv = cmp(rec->rec, flist[0]->rec);
-               if (cmpv == 0 && UNIQUE)
-                       return 1;
-               /* Add matching keys in file order (ie new is later) */
-               if (cmpv < 0)
-                       bot = -1;
-       }
-       bot++;
-       memmove(flist + bot + 1, flist + bot, (ttop - bot) * sizeof(MFILE *));
-       flist[bot] = rec;
-       return 0;
-}
-
-/*
- * check order on one file
- */
-void
-order(struct filelist *filelist, struct field *ftbl)
-{
-       get_func_t get = SINGL_FLD ? makeline : makekey;
-       RECHEADER *crec, *prec, *trec;
-       u_char *crec_end, *prec_end, *trec_end;
-       FILE *fp;
-       int c;
-
-       fp = fopen(filelist->names[0], "r");
-       if (fp == NULL)
-               err(2, "%s", filelist->names[0]);
-
-       crec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
-       crec_end = crec->data + DEFLLEN;
-       prec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
-       prec_end = prec->data + DEFLLEN;
-
-       /* XXX this does exit(0) for overlong lines */
-       if (get(fp, prec, prec_end, ftbl) != 0)
-               exit(0);
-       while (get(fp, crec, crec_end, ftbl) == 0) {
-               if (0 < (c = cmp(prec, crec))) {
-                       crec->data[crec->length-1] = 0;
-                       errx(1, "found disorder: %s", crec->data+crec->offset);
-               }
-               if (UNIQUE && !c) {
-                       crec->data[crec->length-1] = 0;
-                       errx(1, "found non-uniqueness: %s",
-                           crec->data+crec->offset);
-               }
-               /*
-                * Swap pointers so that this record is on place pointed
-                * to by prec and new record is read to place pointed to by
-                * crec.
-                */ 
-               trec = prec;
-               prec = crec;
-               crec = trec;
-               trec_end = prec_end;
-               prec_end = crec_end;
-               crec_end = trec_end;
-       }
-       exit(0);
-}
-
-static int
-cmp(RECHEADER *rec1, RECHEADER *rec2)
-{
-       int len;
-       int r;
-
-       /* key is weights */
-       len = min(rec1->keylen, rec2->keylen);
-       r = memcmp(rec1->data, rec2->data, len);
-       if (r == 0)
-               r = rec1->keylen - rec2->keylen;
-       if (REVERSE)
-               r = -r;
-       return r;
-}
diff --git a/usr.bin/sort/pathnames.h b/usr.bin/sort/pathnames.h
deleted file mode 100644 (file)
index 6d0656a..0000000
+++ /dev/null
@@ -1,66 +0,0 @@
-/*     $NetBSD: pathnames.h,v 1.5 2003/08/07 11:32:34 jdolecek Exp $   */
-
-/*-
- * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Ben Harris and Jaromir Dolecek.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*-
- * Copyright (c) 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Peter McIlroy.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- *     @(#)pathnames.h 8.1 (Berkeley) 6/6/93
- */
-
-#define         _PATH_STDIN            "/dev/stdin"
diff --git a/usr.bin/sort/radix_sort.c b/usr.bin/sort/radix_sort.c
deleted file mode 100644 (file)
index 67d3428..0000000
+++ /dev/null
@@ -1,216 +0,0 @@
-/*     @(#)radixsort.c 8.2 (Berkeley) 4/28/95                          */
-/*     $NetBSD: radix_sort.c,v 1.3 2009/09/10 22:02:40 dsl Exp $       */
-
-/*-
- * Copyright (c) 1990, 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Peter McIlroy and by Dan Bernstein at New York University, 
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-/*
- * 'stable' radix sort initially from libc/stdlib/radixsort.c
- */
-
-#include <sys/types.h>
-
-#include <assert.h>
-#include <errno.h>
-#include "sort.h"
-
-typedef struct {
-       RECHEADER **sa;         /* Base of saved area */
-       int sn;                 /* Number of entries */
-       int si;                 /* index into data for compare */
-} stack;
-
-static void simplesort(RECHEADER **, int, int);
-
-#define        THRESHOLD       20              /* Divert to simplesort(). */
-
-#define empty(s)       (s >= sp)
-#define pop(a, n, i)   a = (--sp)->sa, n = sp->sn, i = sp->si
-#define push(a, n, i)  sp->sa = a, sp->sn = n, (sp++)->si = i
-#define swap(a, b, t)  t = a, a = b, b = t
-
-void
-radix_sort(RECHEADER **a, RECHEADER **ta, int n)
-{
-       u_int count[256], nc, bmin;
-       u_int c;
-       RECHEADER **ak, **tai, **lim;
-       RECHEADER *hdr;
-       int stack_size = 512;
-       stack *s, *sp, *sp0, *sp1, temp;
-       RECHEADER **top[256];
-       u_int *cp, bigc;
-       size_t alloc_size;
-       int data_index = 0;
-
-       if (n < THRESHOLD && !DEBUG('r')) {
-               simplesort(a, n, 0);
-               return;
-       }
-
-       alloc_size = stack_size * sizeof *s;
-       s = malloc(alloc_size);
-       if (s == NULL)
-               err(1, "Cannot allocate %zu bytes", alloc_size);
-       memset(&count, 0, sizeof count);
-       /* Technically 'top' doesn't need zeroing */
-       memset(&top, 0, sizeof top);
-
-       sp = s;
-       push(a, n, data_index);
-       while (!empty(s)) {
-               pop(a, n, data_index);
-               if (n < THRESHOLD && !DEBUG('r')) {
-                       simplesort(a, n, data_index);
-                       continue;
-               }
-
-               /* Count number of times each 'next byte' occurs */
-               nc = 0;
-               bmin = 255;
-               lim = a + n;
-               for (ak = a, tai = ta; ak < lim; ak++) {
-                       hdr = *ak;
-                       if (data_index >= hdr->keylen) {
-                               /* Short key, copy to start of output */
-                               if (UNIQUE && a != sp->sa)
-                                       /* Stop duplicate being written out */
-                                       hdr->keylen = -1;
-                               *a++ = hdr;
-                               n--;
-                               continue;
-                       }
-                       /* Save in temp buffer for distribute */
-                       *tai++ = hdr;
-                       c = hdr->data[data_index];
-                       if (++count[c] == 1) {
-                               if (c < bmin)
-                                       bmin = c;
-                               nc++;
-                       }
-               }
-               /*
-                * We need save the bounds for each 'next byte' that
-                * occurs more so we can sort each block.
-                */
-               if (sp + nc > s + stack_size) {
-                       stack_size *= 2;
-                       alloc_size = stack_size * sizeof *s;
-                       sp1 = realloc(s, alloc_size);
-                       if (sp1 == NULL)
-                               err(1, "Cannot re-allocate %zu bytes",
-                                   alloc_size);
-                       sp = sp1 + (sp - s);
-                       s = sp1;
-               }
-
-               /* Minor optimisation to do the largest set last */
-               sp0 = sp1 = sp;
-               bigc = 2;
-               /* Convert 'counts' positions, saving bounds for later sorts */
-               ak = a;
-               for (cp = count + bmin; nc > 0; cp++) {
-                       while (*cp == 0)
-                               cp++;
-                       if ((c = *cp) > 1) {
-                               if (c > bigc) {
-                                       bigc = c;
-                                       sp1 = sp;
-                               }
-                               push(ak, c, data_index+1);
-                       }
-                       ak += c;
-                       top[cp-count] = ak;
-                       *cp = 0;                        /* Reset count[]. */
-                       nc--;
-               }
-               swap(*sp0, *sp1, temp);
-
-               for (ak = ta+n; --ak >= ta;)            /* Deal to piles. */
-                       *--top[(*ak)->data[data_index]] = *ak;
-       }
-
-       free(s);
-}
-
-/* insertion sort, short records are sorted before long ones */
-static void
-simplesort(RECHEADER **a, int n, int data_index)
-{
-       RECHEADER **ak, **ai;
-       RECHEADER *akh;
-       RECHEADER **lim = a + n;
-       const u_char *s, *t;
-       int s_len, t_len;
-       int i;
-       int r;
-
-       if (n <= 1)
-               return;
-
-       for (ak = a+1; ak < lim; ak++) {
-               akh = *ak;
-               s = akh->data;
-               s_len = akh->keylen;
-               for (ai = ak; ;) {
-                       ai--;
-                       t_len = (*ai)->keylen;
-                       if (t_len != -1) {
-                               t = (*ai)->data;
-                               for (i = data_index; ; i++) {
-                                       if (i >= s_len || i >= t_len) {
-                                               r = s_len - t_len;
-                                               break;
-                                       }
-                                       r =  s[i]  - t[i];
-                                       if (r != 0)
-                                               break;
-                               }
-                               if (r >= 0) {
-                                       if (r == 0 && UNIQUE) {
-                                               /* Put record below existing */
-                                               ai[1] = ai[0];
-                                               /* Mark as duplicate - ignore */
-                                               akh->keylen = -1;
-                                       } else {
-                                               ai++;
-                                       }
-                                       break;
-                               }
-                       }
-                       ai[1] = ai[0];
-                       if (ai == a)
-                               break;
-               }
-               ai[0] = akh;
-       }
-}
diff --git a/usr.bin/sort/radixsort.c b/usr.bin/sort/radixsort.c
new file mode 100644 (file)
index 0000000..e1d9869
--- /dev/null
@@ -0,0 +1,691 @@
+/*-
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
+ * Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD: head/usr.bin/sort/radixsort.c 281133 2015-04-06 03:02:20Z pfg $
+ */
+
+
+#include <errno.h>
+#include <err.h>
+#include <langinfo.h>
+#include <math.h>
+#if defined(SORT_THREADS)
+#include <pthread.h>
+#include <semaphore.h>
+#endif
+#include <stdlib.h>
+#include <string.h>
+#include <wchar.h>
+#include <wctype.h>
+#include <unistd.h>
+
+#include "coll.h"
+#include "radixsort.h"
+
+#define DEFAULT_SORT_FUNC_RADIXSORT mergesort
+
+#define TINY_NODE(sl) ((sl)->tosort_num < 65)
+#define SMALL_NODE(sl) ((sl)->tosort_num < 5)
+
+/* are we sorting in reverse order ? */
+static bool reverse_sort;
+
+/* sort sub-levels array size */
+static const size_t slsz = 256 * sizeof(struct sort_level*);
+
+/* one sort level structure */
+struct sort_level
+{
+       struct sort_level       **sublevels;
+       struct sort_list_item   **leaves;
+       struct sort_list_item   **sorted;
+       struct sort_list_item   **tosort;
+       size_t                    leaves_num;
+       size_t                    leaves_sz;
+       size_t                    level;
+       size_t                    real_sln;
+       size_t                    start_position;
+       size_t                    sln;
+       size_t                    tosort_num;
+       size_t                    tosort_sz;
+};
+
+/* stack of sort levels ready to be sorted */
+struct level_stack {
+       struct level_stack       *next;
+       struct sort_level        *sl;
+};
+
+static struct level_stack *g_ls;
+
+#if defined(SORT_THREADS)
+/* stack guarding mutex */
+static pthread_mutex_t g_ls_mutex;
+
+/* counter: how many items are left */
+static size_t sort_left;
+/* guarding mutex */
+static pthread_mutex_t sort_left_mutex;
+
+/* semaphore to count threads */
+static sem_t mtsem;
+
+/*
+ * Decrement items counter
+ */
+static inline void
+sort_left_dec(size_t n)
+{
+
+       pthread_mutex_lock(&sort_left_mutex);
+       sort_left -= n;
+       pthread_mutex_unlock(&sort_left_mutex);
+}
+
+/*
+ * Do we have something to sort ?
+ */
+static inline bool
+have_sort_left(void)
+{
+       bool ret;
+
+       pthread_mutex_lock(&sort_left_mutex);
+       ret = (sort_left > 0);
+       pthread_mutex_unlock(&sort_left_mutex);
+       return (ret);
+}
+
+#else
+
+#define sort_left_dec(n)
+
+#endif /* SORT_THREADS */
+
+/*
+ * Push sort level to the stack
+ */
+static inline void
+push_ls(struct sort_level *sl)
+{
+       struct level_stack *new_ls;
+
+       new_ls = sort_malloc(sizeof(struct level_stack));
+       new_ls->sl = sl;
+
+#if defined(SORT_THREADS)
+       if (nthreads > 1)
+               pthread_mutex_lock(&g_ls_mutex);
+#endif
+
+       new_ls->next = g_ls;
+       g_ls = new_ls;
+
+#if defined(SORT_THREADS)
+       if (nthreads > 1)
+               pthread_mutex_unlock(&g_ls_mutex);
+#endif
+}
+
+/*
+ * Pop sort level from the stack (single-threaded style)
+ */
+static inline struct sort_level*
+pop_ls_st(void)
+{
+       struct sort_level *sl;
+
+       if (g_ls) {
+               struct level_stack *saved_ls;
+
+               sl = g_ls->sl;
+               saved_ls = g_ls;
+               g_ls = g_ls->next;
+               sort_free(saved_ls);
+       } else
+               sl = NULL;
+
+       return (sl);
+}
+
+#if defined(SORT_THREADS)
+
+/*
+ * Pop sort level from the stack (multi-threaded style)
+ */
+static inline struct sort_level*
+pop_ls_mt(void)
+{
+       struct level_stack *saved_ls;
+       struct sort_level *sl;
+
+       pthread_mutex_lock(&g_ls_mutex);
+
+       if (g_ls) {
+               sl = g_ls->sl;
+               saved_ls = g_ls;
+               g_ls = g_ls->next;
+       } else {
+               sl = NULL;
+               saved_ls = NULL;
+       }
+
+       pthread_mutex_unlock(&g_ls_mutex);
+
+       sort_free(saved_ls);
+
+       return (sl);
+}
+
+#endif /* defined(SORT_THREADS) */
+
+static void
+add_to_sublevel(struct sort_level *sl, struct sort_list_item *item, size_t indx)
+{
+       struct sort_level *ssl;
+
+       ssl = sl->sublevels[indx];
+
+       if (ssl == NULL) {
+               ssl = sort_malloc(sizeof(struct sort_level));
+               memset(ssl, 0, sizeof(struct sort_level));
+
+               ssl->level = sl->level + 1;
+               sl->sublevels[indx] = ssl;
+
+               ++(sl->real_sln);
+       }
+
+       if (++(ssl->tosort_num) > ssl->tosort_sz) {
+               ssl->tosort_sz = ssl->tosort_num + 128;
+               ssl->tosort = sort_realloc(ssl->tosort,
+                   sizeof(struct sort_list_item*) * (ssl->tosort_sz));
+       }
+
+       ssl->tosort[ssl->tosort_num - 1] = item;
+}
+
+static inline void
+add_leaf(struct sort_level *sl, struct sort_list_item *item)
+{
+
+       if (++(sl->leaves_num) > sl->leaves_sz) {
+               sl->leaves_sz = sl->leaves_num + 128;
+               sl->leaves = sort_realloc(sl->leaves,
+                   (sizeof(struct sort_list_item*) * (sl->leaves_sz)));
+       }
+       sl->leaves[sl->leaves_num - 1] = item;
+}
+
+static inline int
+get_wc_index(struct sort_list_item *sli, size_t level)
+{
+       const struct bwstring *bws;
+
+       bws = sli->ka.key[0].k;
+
+       if ((BWSLEN(bws) > level))
+               return (unsigned char) BWS_GET(bws,level);
+       return (-1);
+}
+
+static void
+place_item(struct sort_level *sl, size_t item)
+{
+       struct sort_list_item *sli;
+       int c;
+
+       sli = sl->tosort[item];
+       c = get_wc_index(sli, sl->level);
+
+       if (c == -1)
+               add_leaf(sl, sli);
+       else
+               add_to_sublevel(sl, sli, c);
+}
+
+static void
+free_sort_level(struct sort_level *sl)
+{
+
+       if (sl) {
+               if (sl->leaves)
+                       sort_free(sl->leaves);
+
+               if (sl->level > 0)
+                       sort_free(sl->tosort);
+
+               if (sl->sublevels) {
+                       struct sort_level *slc;
+                       size_t sln;
+
+                       sln = sl->sln;
+
+                       for (size_t i = 0; i < sln; ++i) {
+                               slc = sl->sublevels[i];
+                               if (slc)
+                                       free_sort_level(slc);
+                       }
+
+                       sort_free(sl->sublevels);
+               }
+
+               sort_free(sl);
+       }
+}
+
+static void
+run_sort_level_next(struct sort_level *sl)
+{
+       struct sort_level *slc;
+       size_t i, sln, tosort_num;
+
+       if (sl->sublevels) {
+               sort_free(sl->sublevels);
+               sl->sublevels = NULL;
+       }
+
+       switch (sl->tosort_num) {
+       case 0:
+               goto end;
+       case (1):
+               sl->sorted[sl->start_position] = sl->tosort[0];
+               sort_left_dec(1);
+               goto end;
+       case (2):
+               if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
+                   sl->level) > 0) {
+                       sl->sorted[sl->start_position++] = sl->tosort[1];
+                       sl->sorted[sl->start_position] = sl->tosort[0];
+               } else {
+                       sl->sorted[sl->start_position++] = sl->tosort[0];
+                       sl->sorted[sl->start_position] = sl->tosort[1];
+               }
+               sort_left_dec(2);
+
+               goto end;
+       default:
+               if (TINY_NODE(sl) || (sl->level > 15)) {
+                       listcoll_t func;
+
+                       func = get_list_call_func(sl->level);
+
+                       sl->leaves = sl->tosort;
+                       sl->leaves_num = sl->tosort_num;
+                       sl->leaves_sz = sl->leaves_num;
+                       sl->leaves = sort_realloc(sl->leaves,
+                           (sizeof(struct sort_list_item *) *
+                           (sl->leaves_sz)));
+                       sl->tosort = NULL;
+                       sl->tosort_num = 0;
+                       sl->tosort_sz = 0;
+                       sl->sln = 0;
+                       sl->real_sln = 0;
+                       if (sort_opts_vals.sflag) {
+                               if (mergesort(sl->leaves, sl->leaves_num,
+                                   sizeof(struct sort_list_item *),
+                                   (int(*)(const void *, const void *)) func) == -1)
+                                       /* NOTREACHED */
+                                       err(2, "Radix sort error 3");
+                       } else
+                               DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
+                                   sizeof(struct sort_list_item *),
+                                   (int(*)(const void *, const void *)) func);
+
+                       memcpy(sl->sorted + sl->start_position,
+                           sl->leaves, sl->leaves_num *
+                           sizeof(struct sort_list_item*));
+
+                       sort_left_dec(sl->leaves_num);
+
+                       goto end;
+               } else {
+                       sl->tosort_sz = sl->tosort_num;
+                       sl->tosort = sort_realloc(sl->tosort,
+                           sizeof(struct sort_list_item*) * (sl->tosort_sz));
+               }
+       }
+
+       sl->sln = 256;
+       sl->sublevels = sort_malloc(slsz);
+       memset(sl->sublevels, 0, slsz);
+
+       sl->real_sln = 0;
+
+       tosort_num = sl->tosort_num;
+       for (i = 0; i < tosort_num; ++i)
+               place_item(sl, i);
+
+       sort_free(sl->tosort);
+       sl->tosort = NULL;
+       sl->tosort_num = 0;
+       sl->tosort_sz = 0;
+
+       if (sl->leaves_num > 1) {
+               if (keys_num > 1) {
+                       if (sort_opts_vals.sflag) {
+                               mergesort(sl->leaves, sl->leaves_num,
+                                   sizeof(struct sort_list_item *),
+                                   (int(*)(const void *, const void *)) list_coll);
+                       } else {
+                               DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
+                                   sizeof(struct sort_list_item *),
+                                   (int(*)(const void *, const void *)) list_coll);
+                       }
+               } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
+                       DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
+                           sizeof(struct sort_list_item *),
+                           (int(*)(const void *, const void *)) list_coll_by_str_only);
+               }
+       }
+
+       sl->leaves_sz = sl->leaves_num;
+       sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) *
+           (sl->leaves_sz)));
+
+       if (!reverse_sort) {
+               memcpy(sl->sorted + sl->start_position, sl->leaves,
+                   sl->leaves_num * sizeof(struct sort_list_item*));
+               sl->start_position += sl->leaves_num;
+               sort_left_dec(sl->leaves_num);
+
+               sort_free(sl->leaves);
+               sl->leaves = NULL;
+               sl->leaves_num = 0;
+               sl->leaves_sz = 0;
+
+               sln = sl->sln;
+
+               for (i = 0; i < sln; ++i) {
+                       slc = sl->sublevels[i];
+
+                       if (slc) {
+                               slc->sorted = sl->sorted;
+                               slc->start_position = sl->start_position;
+                               sl->start_position += slc->tosort_num;
+                               if (SMALL_NODE(slc))
+                                       run_sort_level_next(slc);
+                               else
+                                       push_ls(slc);
+                               sl->sublevels[i] = NULL;
+                       }
+               }
+
+       } else {
+               size_t n;
+
+               sln = sl->sln;
+
+               for (i = 0; i < sln; ++i) {
+                       n = sln - i - 1;
+                       slc = sl->sublevels[n];
+
+                       if (slc) {
+                               slc->sorted = sl->sorted;
+                               slc->start_position = sl->start_position;
+                               sl->start_position += slc->tosort_num;
+                               if (SMALL_NODE(slc))
+                                       run_sort_level_next(slc);
+                               else
+                                       push_ls(slc);
+                               sl->sublevels[n] = NULL;
+                       }
+               }
+
+               memcpy(sl->sorted + sl->start_position, sl->leaves,
+                   sl->leaves_num * sizeof(struct sort_list_item*));
+               sort_left_dec(sl->leaves_num);
+       }
+
+end:
+       free_sort_level(sl);
+}
+
+/*
+ * Single-threaded sort cycle
+ */
+static void
+run_sort_cycle_st(void)
+{
+       struct sort_level *slc;
+
+       for (;;) {
+               slc = pop_ls_st();
+               if (slc == NULL) {
+                       break;
+               }
+               run_sort_level_next(slc);
+       }
+}
+
+#if defined(SORT_THREADS)
+
+/*
+ * Multi-threaded sort cycle
+ */
+static void
+run_sort_cycle_mt(void)
+{
+       struct sort_level *slc;
+
+       for (;;) {
+               slc = pop_ls_mt();
+               if (slc == NULL) {
+                       if (have_sort_left()) {
+                               pthread_yield();
+                               continue;
+                       }
+                       break;
+               }
+               run_sort_level_next(slc);
+       }
+}
+
+/*
+ * Sort cycle thread (in multi-threaded mode)
+ */
+static void*
+sort_thread(void* arg)
+{
+
+       run_sort_cycle_mt();
+
+       sem_post(&mtsem);
+
+       return (arg);
+}
+
+#endif /* defined(SORT_THREADS) */
+
+static void
+run_top_sort_level(struct sort_level *sl)
+{
+       struct sort_level *slc;
+
+       reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
+           default_sort_mods->rflag;
+
+       sl->start_position = 0;
+       sl->sln = 256;
+       sl->sublevels = sort_malloc(slsz);
+       memset(sl->sublevels, 0, slsz);
+
+       for (size_t i = 0; i < sl->tosort_num; ++i)
+               place_item(sl, i);
+
+       if (sl->leaves_num > 1) {
+               if (keys_num > 1) {
+                       if (sort_opts_vals.sflag) {
+                               mergesort(sl->leaves, sl->leaves_num,
+                                   sizeof(struct sort_list_item *),
+                                   (int(*)(const void *, const void *)) list_coll);
+                       } else {
+                               DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
+                                   sizeof(struct sort_list_item *),
+                                   (int(*)(const void *, const void *)) list_coll);
+                       }
+               } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
+                       DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
+                           sizeof(struct sort_list_item *),
+                           (int(*)(const void *, const void *)) list_coll_by_str_only);
+               }
+       }
+
+       if (!reverse_sort) {
+               memcpy(sl->tosort + sl->start_position, sl->leaves,
+                   sl->leaves_num * sizeof(struct sort_list_item*));
+               sl->start_position += sl->leaves_num;
+               sort_left_dec(sl->leaves_num);
+
+               for (size_t i = 0; i < sl->sln; ++i) {
+                       slc = sl->sublevels[i];
+
+                       if (slc) {
+                               slc->sorted = sl->tosort;
+                               slc->start_position = sl->start_position;
+                               sl->start_position += slc->tosort_num;
+                               push_ls(slc);
+                               sl->sublevels[i] = NULL;
+                       }
+               }
+
+       } else {
+               size_t n;
+
+               for (size_t i = 0; i < sl->sln; ++i) {
+
+                       n = sl->sln - i - 1;
+                       slc = sl->sublevels[n];
+
+                       if (slc) {
+                               slc->sorted = sl->tosort;
+                               slc->start_position = sl->start_position;
+                               sl->start_position += slc->tosort_num;
+                               push_ls(slc);
+                               sl->sublevels[n] = NULL;
+                       }
+               }
+
+               memcpy(sl->tosort + sl->start_position, sl->leaves,
+                   sl->leaves_num * sizeof(struct sort_list_item*));
+
+               sort_left_dec(sl->leaves_num);
+       }
+
+#if defined(SORT_THREADS)
+       if (nthreads < 2) {
+#endif
+               run_sort_cycle_st();
+#if defined(SORT_THREADS)
+       } else {
+               size_t i;
+
+               for(i = 0; i < nthreads; ++i) {
+                       pthread_attr_t attr;
+                       pthread_t pth;
+
+                       pthread_attr_init(&attr);
+                       pthread_attr_setdetachstate(&attr,
+                           PTHREAD_DETACHED);
+
+                       for (;;) {
+                               int res = pthread_create(&pth, &attr,
+                                   sort_thread, NULL);
+                               if (res >= 0)
+                                       break;
+                               if (errno == EAGAIN) {
+                                       pthread_yield();
+                                       continue;
+                               }
+                               err(2, NULL);
+                       }
+
+                       pthread_attr_destroy(&attr);
+               }
+
+               for(i = 0; i < nthreads; ++i)
+                       sem_wait(&mtsem);
+       }
+#endif /* defined(SORT_THREADS) */
+}
+
+static void
+run_sort(struct sort_list_item **base, size_t nmemb)
+{
+       struct sort_level *sl;
+
+#if defined(SORT_THREADS)
+       size_t nthreads_save = nthreads;
+       if (nmemb < MT_SORT_THRESHOLD)
+               nthreads = 1;
+
+       if (nthreads > 1) {
+               pthread_mutexattr_t mattr;
+
+               pthread_mutexattr_init(&mattr);
+               pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ERRORCHECK);
+
+               pthread_mutex_init(&g_ls_mutex, &mattr);
+               pthread_mutex_init(&sort_left_mutex, &mattr);
+
+               pthread_mutexattr_destroy(&mattr);
+
+               sem_init(&mtsem, 0, 0);
+
+       }
+#endif
+
+       sl = sort_malloc(sizeof(struct sort_level));
+       memset(sl, 0, sizeof(struct sort_level));
+
+       sl->tosort = base;
+       sl->tosort_num = nmemb;
+       sl->tosort_sz = nmemb;
+
+#if defined(SORT_THREADS)
+       sort_left = nmemb;
+#endif
+
+       run_top_sort_level(sl);
+
+       free_sort_level(sl);
+
+#if defined(SORT_THREADS)
+       if (nthreads > 1) {
+               sem_destroy(&mtsem);
+               pthread_mutex_destroy(&g_ls_mutex);
+               pthread_mutex_destroy(&sort_left_mutex);
+       }
+       nthreads = nthreads_save;
+#endif
+}
+
+void
+rxsort(struct sort_list_item **base, size_t nmemb)
+{
+
+       run_sort(base, nmemb);
+}
diff --git a/usr.bin/sort/radixsort.h b/usr.bin/sort/radixsort.h
new file mode 100644 (file)
index 0000000..b534bf0
--- /dev/null
@@ -0,0 +1,38 @@
+/*     $FreeBSD: head/usr.bin/sort/radixsort.h 264744 2014-04-21 22:52:18Z pfg $       */
+
+/*-
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
+ * Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if !defined(__SORT_RADIX_H__)
+#define        __SORT_RADIX_H__
+
+#include "coll.h"
+#include "sort.h"
+
+void rxsort(struct sort_list_item **base, size_t nmemb);
+
+#endif /* __SORT_RADIX_H__ */
index c354f32..f0d23ce 100644 (file)
@@ -1,31 +1,5 @@
-.\"    $NetBSD: sort.1,v 1.31 2010/12/18 23:09:48 christos Exp $
-.\"
-.\" Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
-.\" All rights reserved.
-.\"
-.\" This code is derived from software contributed to The NetBSD Foundation
-.\" by Ben Harris and Jaromir Dolecek.
-.\"
-.\" Redistribution and use in source and binary forms, with or without
-.\" modification, are permitted provided that the following conditions
-.\" are met:
-.\" 1. Redistributions of source code must retain the above copyright
-.\"    notice, this list of conditions and the following disclaimer.
-.\" 2. Redistributions in binary form must reproduce the above copyright
-.\"    notice, this list of conditions and the following disclaimer in the
-.\"    documentation and/or other materials provided with the distribution.
-.\"
-.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
-.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
-.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
-.\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
-.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
-.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
-.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
-.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
-.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
-.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-.\" POSSIBILITY OF SUCH DAMAGE.
+.\"    $OpenBSD: sort.1,v 1.45 2015/03/19 13:51:10 jmc Exp $
+.\"    $FreeBSD: head/usr.bin/sort/sort.1.in 281123 2015-04-05 22:22:43Z pfg $
 .\"
 .\" Copyright (c) 1991, 1993
 .\"    The Regents of the University of California.  All rights reserved.
 .\"
 .\"     @(#)sort.1     8.1 (Berkeley) 6/6/93
 .\"
-.Dd December 18, 2010
+.Dd March 19 2015
 .Dt SORT 1
 .Os
 .Sh NAME
 .Nm sort
-.Nd sort or merge text files
+.Nd sort or merge records (lines) of text and binary files
 .Sh SYNOPSIS
-.Nm
-.Op Fl bcdfHilmnrSsu
-.Oo
-.Fl k
-.Ar field1 Ns Op Li \&, Ns Ar field2
-.Oc
-.Op Fl o Ar output
-.Op Fl R Ar char
+.Nm sort
+.Bk -words
+.Op Fl bcCdfghiRMmnrsuVz
+.Sm off
+.Op Fl k\ \& Ar field1 Op , Ar field2
+.Sm on
+.Op Fl S Ar memsize
+.Ek
 .Op Fl T Ar dir
 .Op Fl t Ar char
-.Op Ar
+.Op Fl o Ar output
+.Op Ar file ...
+.Nm sort
+.Fl Fl help
+.Nm sort
+.Fl Fl version
 .Sh DESCRIPTION
 The
 .Nm
-utility sorts text files by lines.
-Comparisons are based on one or more sort keys extracted
-from each line of input, and are performed lexicographically.
+utility sorts text and binary files by lines.
+A line is a record separated from the subsequent record by a
+newline (default) or NUL \'\\0\' character (-z option).
+A record can contain any printable or unprintable characters.
+Comparisons are based on one or more sort keys extracted from
+each line of input, and are performed lexicographically,
+according to the current locale's collating rules and the
+specified command-line options that can tune the actual
+sorting behavior.
 By default, if keys are not given,
 .Nm
-regards each input line as a single field.
+uses entire lines for comparison.
 .Pp
-The following options are available:
-.Bl -tag -width Fl
-.It Fl c
+The command line options are as follows:
+.Bl -tag -width Ds
+.It Fl c, Fl Fl check, Fl C, Fl Fl check=silent|quiet
 Check that the single input file is sorted.
 If the file is not sorted,
 .Nm
-produces the appropriate error messages and exits with code 1; otherwise,
-.Nm
-returns 0.
+produces the appropriate error messages and exits with code 1,
+otherwise returns 0.
+If
+.Fl C
+or
+.Fl Fl check=silent
+is specified,
 .Nm
-.Fl c
 produces no output.
-.It Fl H
-Ignored for compatibility with earlier versions of
-.Nm .
-.It Fl m
-Merge only; the input files are assumed to be pre-sorted.
-.It Fl o Ar output
-The argument given is the name of an
+This is a "silent" version of
+.Fl c.
+.It Fl m , Fl Fl merge
+Merge only.
+The input files are assumed to be pre-sorted.
+If they are not sorted the output order is undefined.
+.It Fl o Ar output , Fl Fl output Ns = Ns Ar output
+Print the output to the
 .Ar output
-file to be used instead of the standard output.
-This file can be the same as one of the input files.
-.It Fl S
-Don't use stable sort.
-Default is to use stable sort.
-.It Fl s
-Use stable sort, keeps records with equal keys in their original order.
-This is the default.
-Provided for compatibility with other
-.Nm
-implementations only.
-.It Fl T Ar dir
+file instead of the standard output.
+.It Fl S Ar size, Fl Fl buffer-size Ns = Ns Ar size
 Use
-.Ar dir
-as the directory for temporary files.
-The default is the value specified in the environment variable
-.Ev TMPDIR or
-.Pa /tmp
+.Ar size
+for the maximum size of the memory buffer.
+Size modifiers %,b,K,M,G,T,P,E,Z,Y can be used.
+If a memory limit is not explicitly specified,
+.Nm
+takes up to about 90% of available memory.
+If the file size is too big to fit into the memory buffer,
+the temporary disk files are used to perform the sorting.
+.It Fl T Ar dir , Fl Fl temporary-directory Ns = Ns Ar dir
+Store temporary files in the directory
+.Ar dir .
+The default path is the value of the environment variable
+.Ev TMPDIR
+or
+.Pa /var/tmp
 if
 .Ev TMPDIR
 is not defined.
-.It Fl u
-Unique: suppress all but one in each set of lines having equal keys.
-If used with the
+.It Fl u , Fl Fl unique
+Unique keys.
+Suppress all lines that have a key that is equal to an already
+processed one.
+This option, similarly to
+.Fl s ,
+implies a stable sort.
+If used with
 .Fl c
-option, check that there are no lines with duplicate keys.
+or
+.Fl C ,
+.Nm
+also checks that there are no lines with duplicate keys.
+.It Fl s
+Stable sort.
+This option maintains the original record order of records that have
+and equal key.
+This is a non-standard feature, but it is widely accepted and used.
+.It Fl Fl version
+Print the version and silently exits.
+.It Fl Fl help
+Print the help text and silently exits.
 .El
 .Pp
 The following options override the default ordering rules.
-When ordering options appear independent of key field
-specifications, the requested field ordering rules are
-applied globally to all sort keys.
+When ordering options appear independently of key field
+specifications, they apply globally to all sort keys.
 When attached to a specific key (see
 .Fl k ) ,
-the ordering options override
-all global ordering options for that key.
-.Bl -tag -width Fl
-.It Fl d
-Only blank space and alphanumeric characters
-.\" according
-.\" to the current setting of LC_CTYPE
-are used
-in making comparisons.
-.It Fl f
-Considers all lowercase characters that have uppercase
-equivalents to be the same for purposes of comparison.
-.It Fl i
-Ignore all non-printable characters.
-.It Fl l
-Sort by the string length of the field, not by the field itself.
-.It Fl n
-An initial numeric string, consisting of optional blank space, optional
-minus sign, and zero or more digits (including decimal point)
-.\" with
-.\" optional radix character and thousands
-.\" separator
-.\" (as defined in the current locale),
-is sorted by arithmetic value.
-(The
+the ordering options override all global ordering options for
+the key they are attached to.
+.Bl -tag -width indent
+.It Fl b, Fl Fl ignore-leading-blanks
+Ignore leading blank characters when comparing lines.
+.It Fl d , Fl Fl dictionary-order
+Consider only blank spaces and alphanumeric characters in comparisons.
+.It Fl f , Fl Fl ignore-case
+Convert all lowercase characters to their uppercase equivalent
+before comparison, that is, perform case-independent sorting.
+.It Fl g, Fl Fl general-numeric-sort, Fl Fl sort=general-numeric
+Sort by general numerical value.
+As opposed to
+.Fl n ,
+this option handles general floating points.
+It has a more
+permissive format than that allowed by
 .Fl n
-option no longer implies the
-.Fl b
-option.)
-.It Fl r
-Reverse the sense of comparisons.
+but it has a significant performance drawback.
+.It Fl h, Fl Fl human-numeric-sort, Fl Fl sort=human-numeric
+Sort by numerical value, but take into account the SI suffix,
+if present.
+Sort first by numeric sign (negative, zero, or
+positive); then by SI suffix (either empty, or `k' or `K', or one
+of `MGTPEZY', in that order); and finally by numeric value.
+The SI suffix must immediately follow the number.
+For example, '12345K' sorts before '1M', because M is "larger" than K.
+This sort option is useful for sorting the output of a single invocation
+of 'df' command with
+.Fl h
+or
+.Fl H
+options (human-readable).
+.It Fl i , Fl Fl ignore-nonprinting
+Ignore all non-printable characters.
+.It Fl M, Fl Fl month-sort, Fl Fl sort=month
+Sort by month abbreviations.
+Unknown strings are considered smaller than the month names.
+.It Fl n , Fl Fl numeric-sort, Fl Fl sort=numeric
+Sort fields numerically by arithmetic value.
+Fields are supposed to have optional blanks in the beginning, an
+optional minus sign, zero or more digits (including decimal point and
+possible thousand separators).
+.It Fl R, Fl Fl random-sort, Fl Fl sort=random
+Sort by a random order.
+This is a random permutation of the inputs except that
+the equal keys sort together.
+It is implemented by hashing the input keys and sorting
+the hash values.
+The hash function is chosen randomly.
+The hash function is randomized by
+.Cm /dev/random
+content, or by file content if it is specified by
+.Fl Fl random-source .
+Even if multiple sort fields are specified,
+the same random hash function is used for all of them.
+.It Fl r , Fl Fl reverse
+Sort in reverse order.
+.It Fl V, Fl Fl version-sort
+Sort version numbers.
+The input lines are treated as file names in form
+PREFIX VERSION SUFFIX, where SUFFIX matches the regular expression
+"(\.([A-Za-z~][A-Za-z0-9~]*)?)*".
+The files are compared by their prefixes and versions (leading
+zeros are ignored in version numbers, see example below).
+If an input string does not match the pattern, then it is compared
+using the byte compare function.
+All string comparisons are performed in C locale, the locale
+environment setting is ignored.
+.Bl -tag -width indent
+.It Example:
+.It $ ls sort* | sort -V
+.It sort-1.022.tgz
+.It sort-1.23.tgz
+.It sort-1.23.1.tgz
+.It sort-1.024.tgz
+.It sort-1.024.003.
+.It sort-1.024.003.tgz
+.It sort-1.024.07.tgz
+.It sort-1.024.009.tgz
+.El
 .El
 .Pp
 The treatment of field separators can be altered using these options:
-.Bl -tag -width Fl
-.It Fl b
-Ignores leading blank space when determining the start
-and end of a restricted sort key.
-A
-.Fl b
-option specified before the first
+.Bl -tag -width indent
+.It Fl b , Fl Fl ignore-leading-blanks
+Ignore leading blank space when determining the start
+and end of a restricted sort key (see
 .Fl k
-option applies globally to all
+).
+If
+.Fl b
+is specified before the first
 .Fl k
-options.
-Otherwise, the
+option, it applies globally to all key specifications.
+Otherwise,
 .Fl b
-option can be attached independently to each
+can be attached independently to each
 .Ar field
-argument of the
+argument of the key specifications.
+.Fl b .
+.It Xo
+.Fl k Ar field1 Ns Op , Ns Ar field2 ,
+.Fl Fl key Ns = Ns Ar field1 Ns Op , Ns Ar field2
+.Xc
+Define a restricted sort key that has the starting position
+.Ar field1 ,
+and optional ending position
+.Ar field2
+of a key field.
+The
 .Fl k
-option (see below).
-Note that the
-.Fl b
-option has no effect unless key fields are specified.
-.It Fl t Ar char
+option may be specified multiple times,
+in which case subsequent keys are compared when earlier keys compare equal.
+The
+.Fl k
+option replaces the obsolete options
+.Cm \(pl Ns Ar pos1
+and
+.Fl Ns Ar pos2 ,
+but the old notation is also supported.
+.It Fl t Ar char , Fl Fl field-separator Ns = Ns Ar char
+Use
 .Ar char
-is used as the field separator character.
+as a field separator character.
 The initial
 .Ar char
-is not considered to be part of a field when determining
-key offsets (see below).
+is not considered to be part of a field when determining key offsets.
 Each occurrence of
 .Ar char
 is significant (for example,
@@ -211,252 +282,357 @@ delimits an empty field).
 If
 .Fl t
 is not specified, the default field separator is a sequence of
-blank-space characters, and consecutive blank spaces do
+blank space characters, and consecutive blank spaces do
 .Em not
-delimit an empty field; further, the initial blank space
+delimit an empty field, however, the initial blank space
 .Em is
 considered part of a field when determining key offsets.
-.It Fl R Ar char
-.Ar char
-is used as the record separator character.
-This should be used with discretion;
-.Fl R Ar \*[Lt]alphanumeric\*[Gt]
-usually produces undesirable results.
-The default record separator is newline.
-.It Fl k Ar field1 Ns Op Li \&, Ns Ar field2
-Designates the starting position,
-.Ar field1 ,
-and optional ending position,
-.Ar field2 ,
-of a key field.
-The
-.Fl k
-option replaces the obsolescent options
-.Cm \(pl Ns Ar pos1
+To use NUL as field separator, use
+.Fl t
+\'\\0\'.
+.It Fl z , Fl Fl zero-terminated
+Use NUL as record separator.
+By default, records in the files are supposed to be separated by
+the newline characters.
+With this option, NUL (\'\\0\') is used as a record separator character.
+.El
+.Pp
+Other options:
+.Bl -tag -width indent
+.It Fl Fl batch-size Ns = Ns Ar num
+Specify maximum number of files that can be opened by
+.Nm
+at once.
+This option affects behavior when having many input files or using
+temporary files.
+The default value is 16.
+.It Fl Fl compress-program Ns = Ns Ar PROGRAM
+Use PROGRAM to compress temporary files.
+PROGRAM must compress standard input to standard output, when called
+without arguments.
+When called with argument
+.Fl d
+it must decompress standard input to standard output.
+If PROGRAM fails,
+.Nm
+must exit with error.
+An example of PROGRAM that can be used here is bzip2.
+.It Fl Fl random-source Ns = Ns Ar filename
+In random sort, the file content is used as the source of the 'seed' data
+for the hash function choice.
+Two invocations of random sort with the same seed data will use
+the same hash function and will produce the same result if the input is
+also identical.
+By default, file
+.Cm /dev/random
+is used.
+.It Fl Fl debug
+Print some extra information about the sorting process to the
+standard output.
+.It Fl Fl parallel
+Set the maximum number of execution threads.
+Default number equals to the number of CPUs.
+.It Fl Fl files0-from Ns = Ns Ar filename
+Take the input file list from the file
+.Ar filename .
+The file names must be separated by NUL
+(like the output produced by the command "find ... -print0").
+.It Fl Fl radixsort
+Try to use radix sort, if the sort specifications allow.
+The radix sort can only be used for trivial locales (C and POSIX),
+and it cannot be used for numeric or month sort.
+Radix sort is very fast and stable.
+.It Fl Fl mergesort
+Use mergesort.
+This is a universal algorithm that can always be used,
+but it is not always the fastest.
+.It Fl Fl qsort
+Try to use quick sort, if the sort specifications allow.
+This sort algorithm cannot be used with
+.Fl u
+and
+.Fl s .
+.It Fl Fl heapsort
+Try to use heap sort, if the sort specifications allow.
+This sort algorithm cannot be used with
+.Fl u
 and
-.Fl Ns Ar pos2 .
+.Fl s .
+.It Fl Fl mmap
+Try to use file memory mapping system call.
+It may increase speed in some cases.
 .El
 .Pp
 The following operands are available:
-.Bl -tag -width Ar
+.Bl -tag -width indent
 .It Ar file
 The pathname of a file to be sorted, merged, or checked.
 If no
 .Ar file
-operands are specified, or if
-a
+operands are specified, or if a
 .Ar file
 operand is
 .Fl ,
 the standard input is used.
 .El
 .Pp
-A field is defined as a minimal sequence of characters followed by a
-field separator or a newline character.
-By default, the first
-blank space of a sequence of blank spaces acts as the field separator.
-All blank spaces in a sequence of blank spaces are considered
-as part of the next field; for example, all blank spaces at
-the beginning of a line are considered to be part of the
-first field.
+A field is defined as a maximal sequence of characters other than the
+field separator and record separator (newline by default).
+Initial blank spaces are included in the field unless
+.Fl b
+has been specified;
+the first blank space of a sequence of blank spaces acts as the field
+separator and is included in the field (unless
+.Fl t
+is specified).
+For example, all blank spaces at the beginning of a line are
+considered to be part of the first field.
 .Pp
-Fields are specified
-by the
-.Fl k
-.Ar field1 Ns Op \&, Ns Ar field2
-argument.
-A missing
+Fields are specified by the
+.Sm off
+.Fl k\ \& Ar field1 Op , Ar field2
+.Sm on
+command-line option.
+If
 .Ar field2
-argument defaults to the end of a line.
+is missing, the end of the key defaults to the end of the line.
 .Pp
 The arguments
 .Ar field1
 and
 .Ar field2
 have the form
-.Ar m Ns Li \&. Ns Ar n
-and can be followed by one or more of the letters
+.Em m.n
+.Em (m,n > 0)
+and can be followed by one or more of the modifiers
 .Cm b , d , f , i ,
-.Cm l , n ,
+.Cm n , g , M
 and
 .Cm r ,
 which correspond to the options discussed above.
+When
+.Cm b
+is specified it applies only to
+.Ar field1
+or
+.Ar field2
+where it is specified while the rest of the modifiers
+apply to the whole key field regardless if they are
+specified only with
+.Ar field1
+or
+.Ar field2
+or both.
 A
 .Ar field1
 position specified by
-.Ar m Ns Li \&. Ns Ar n
-.Pq Ar m , n No \*[Gt] 0
+.Em m.n
 is interpreted as the
-.Ar n Ns th
-character in the
-.Ar m Ns th
+.Em n Ns th
+character from the beginning of the
+.Em m Ns th
 field.
 A missing
-.Li \&. Ns Ar n
+.Em \&.n
 in
 .Ar field1
 means
 .Ql \&.1 ,
 indicating the first character of the
-.Ar m Ns th
+.Em m Ns th
 field; if the
 .Fl b
 option is in effect,
-.Ar n
+.Em n
 is counted from the first non-blank character in the
-.Ar m Ns th
+.Em m Ns th
 field;
-.Ar m Ns Li \&.1b
+.Em m Ns \&.1b
 refers to the first non-blank character in the
-.Ar m Ns th
+.Em m Ns th
 field.
+.No 1\&. Ns Em n
+refers to the
+.Em n Ns th
+character from the beginning of the line;
+if
+.Em n
+is greater than the length of the line, the field is taken to be empty.
+.Pp
+.Em n Ns th
+positions are always counted from the field beginning, even if the field
+is shorter than the number of specified positions.
+Thus, the key can really start from a position in a subsequent field.
 .Pp
 A
 .Ar field2
 position specified by
-.Ar m Ns Li \&. Ns Ar n
-is interpreted as
-the
-.Ar n Ns th
-character (including separators) of the
-.Ar m Ns th
+.Em m.n
+is interpreted as the
+.Em n Ns th
+character (including separators) from the beginning of the
+.Em m Ns th
 field.
 A missing
-.Li \&. Ns Ar n
+.Em \&.n
 indicates the last character of the
-.Ar m Ns th
+.Em m Ns th
 field;
-.Ar m
+.Em m
 = \&0
 designates the end of a line.
 Thus the option
-.Fl k
-.Sm off
-.Xo
-.Ar v Li \&. Ar x Li \&,
-.Ar w Li \&. Ar y
-.Xc
-.Sm on
-is synonymous with the obsolescent option
-.Sm off
-.Cm \(pl Ar v-\&1 Li \&. Ar x-\&1
-.Fl Ar w-\&1 Li \&. Ar y ;
-.Sm on
+.Fl k Ar v.x,w.y
+is synonymous with the obsolete option
+.Cm \(pl Ns Ar v-\&1.x-\&1
+.Fl Ns Ar w-\&1.y ;
 when
-.Ar y
+.Em y
 is omitted,
-.Fl k
-.Sm off
-.Ar v Li \&. Ar x Li \&, Ar w
-.Sm on
+.Fl k Ar v.x,w
 is synonymous with
-.Sm off
-.Cm \(pl Ar v-\&1 Li \&. Ar x-\&1
-.Fl Ar w+1 Li \&.0 .
-.Sm on
-The obsolescent
+.Cm \(pl Ns Ar v-\&1.x-\&1
+.Fl Ns Ar w\&.0 .
+The obsolete
 .Cm \(pl Ns Ar pos1
 .Fl Ns Ar pos2
 option is still supported, except for
-.Fl Ns Ar w Ns Li \&.0b ,
+.Fl Ns Ar w\&.0b ,
 which has no
 .Fl k
 equivalent.
 .Sh ENVIRONMENT
-If the following environment variable exists, it is used by
-.Nm .
-.Bl -tag -width Ev
-.It Ev TMPDIR
+.Bl -tag -width Fl
+.It Ev LC_COLLATE
+Locale settings to be used to determine the collation for
+sorting records.
+.It Ev LC_CTYPE
+Locale settings to be used to case conversion and classification
+of characters, that is, which characters are considered
+whitespaces, etc.
+.It Ev LC_MESSAGES
+Locale settings that determine the language of output messages
+that
 .Nm
-uses the contents of the
+prints out.
+.It Ev LC_NUMERIC
+Locale settings that determine the number format used in numeric sort.
+.It Ev LC_TIME
+Locale settings that determine the month format used in month sort.
+.It Ev LC_ALL
+Locale settings that override all of the above locale settings.
+This environment variable can be used to set all these settings
+to the same value at once.
+.It Ev LANG
+Used as a last resort to determine different kinds of locale-specific
+behavior if neither the respective environment variable, nor
+.Ev LC_ALL
+are set.
+%%NLS%%.It Ev NLSPATH
+%%NLS%%Path to NLS catalogs.
+.It Ev TMPDIR
+Path to the directory in which temporary files will be stored.
+Note that
 .Ev TMPDIR
-environment variable as the path in which to store
-temporary files.
+may be overridden by the
+.Fl T
+option.
+.It Ev GNUSORT_NUMERIC_COMPATIBILITY
+If defined
+.Fl t
+will not override the locale numeric symbols, that is, thousand
+separators and decimal separators.
+By default, if we specify
+.Fl t
+with the same symbol as the thousand separator or decimal point,
+the symbol will be treated as the field separator.
+Older behavior was less definite; the symbol was treated as both field
+separator and numeric separator, simultaneously.
+This environment variable enables the old behavior.
 .El
 .Sh FILES
-.Bl -tag -width outputNUMBER+some -compact
-.It Pa /tmp/sort.*
-Default temporary files.
-.It Ar output Ns NUMBER
-Temporary file which is used for output if
-.Ar output
-already exists.
-Once sorting is finished, this file replaces
-.Ar output
-(via
-.Xr link 2
-and
-.Xr unlink 2 ) .
+.Bl -tag -width Pa -compact
+.It Pa /var/tmp/.bsdsort.PID.*
+Temporary files.
+.It Pa /dev/random
+Default seed file for the random sort.
 .El
 .Sh EXIT STATUS
-Sort exits with one of the following values:
+The
+.Nm
+utility shall exit with one of the following values:
+.Pp
 .Bl -tag -width flag -compact
 .It 0
-Normal behavior.
+Successfully sorted the input files or if used with
+.Fl c
+or
+.Fl C ,
+the input file already met the sorting criteria.
 .It 1
 On disorder (or non-uniqueness) with the
 .Fl c
-option
+or
+.Fl C
+options.
 .It 2
 An error occurred.
 .El
 .Sh SEE ALSO
 .Xr comm 1 ,
 .Xr join 1 ,
-.Xr uniq 1 ,
-.Xr qsort 3 ,
-.Xr radixsort 3
+.Xr uniq 1
+.Sh STANDARDS
+The
+.Nm
+utility is compliant with the
+.St -p1003.1-2008
+specification.
+.Pp
+The flags
+.Op Fl ghRMSsTVz
+are extensions to the POSIX specification.
+.Pp
+All long options are extensions to the specification, some of them are
+provided for compatibility with GNU versions and some of them are
+own extensions.
+.Pp
+The old key notations
+.Cm \(pl Ns Ar pos1
+and
+.Fl Ns Ar pos2
+come from older versions of
+.Nm
+and are still supported but their use is highly discouraged.
 .Sh HISTORY
 A
 .Nm
-command appeared in
-.At v5 .
-This
-.Nm
-implementation appeared in
-.Bx 4.4
-and is used since
-.Nx 1.6 .
-.Sh BUGS
-Posix requires the locale's thousands separator be ignored in numbers.
-It may be faster to sort very large files in pieces and then explicitly
-merge them.
+command first appeared in
+.At v3 .
+.Sh AUTHORS
+.An Gabor Kovesdan Aq Mt gabor@FreeBSD.org ,
+.Pp
+.An Oleg Moskalenko Aq Mt mom040267@gmail.com
 .Sh NOTES
-This
+This implementation of
 .Nm
 has no limits on input line length (other than imposed by available
 memory) or any restrictions on bytes allowed within lines.
 .Pp
-To protect data
-.Nm
-.Fl o
-calls
-.Xr link 2
-and
-.Xr unlink 2 ,
-and thus fails on protected directories.
-.Pp
-Input files should be text files.
-If file doesn't end with record separator (which is typically newline), the
-.Nm
-utility silently supplies one.
+The performance depends highly on locale settings,
+efficient choice of sort keys and key complexity.
+The fastest sort is with locale C, on whole lines,
+with option
+.Fl s.
+In general, locale C is the fastest, then single-byte
+locales follow and multi-byte locales as the slowest but
+the correct collation order is always respected.
+As for the key specification, the simpler to process the
+lines the faster the search will be.
 .Pp
-The current
-.Nm
-uses lexicographic radix sorting, which requires
-that sort keys be kept in memory (as opposed to previous versions which used quick
-and merge sorts and did not.)
-Thus performance depends highly on efficient choice of sort keys, and the
-.Fl b
-option and the
-.Ar field2
-argument of the
-.Fl k
-option should be used whenever possible.
-Similarly,
-.Nm
-.Fl k1f
-is equivalent to
-.Nm
-.Fl f
-and may take twice as long.
+When sorting by arithmetic value, using
+.Fl n
+results in much better performance than
+.Fl g
+so its use is encouraged
+whenever possible.
index fc8e818..d534086 100644 (file)
@@ -1,41 +1,8 @@
-/*     $NetBSD: sort.c,v 1.59 2010/06/05 17:44:51 dholland Exp $       */
-
 /*-
- * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
+ * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
  * All rights reserved.
  *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Ben Harris and Jaromir Dolecek.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*-
- * Copyright (c) 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Peter McIlroy.
- *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
  *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
+ *
+ * $FreeBSD: head/usr.bin/sort/sort.c 281182 2015-04-07 01:17:49Z pfg $
  */
 
-/* Sort sorts a file using an optional user-defined key.
- * Sort uses radix sort for internal sorting, and allows
- * a choice of merge sort and radix sort for external sorting.
- */
 
 #include <sys/stat.h>
-#include "sort.h"
-#include "fsort.h"
-#include "pathnames.h"
-
+#include <sys/sysctl.h>
 #include <sys/types.h>
-#include <sys/time.h>
-#include <sys/resource.h>
 
-#include <paths.h>
+#include <err.h>
+#include <errno.h>
+#include <getopt.h>
+#include <limits.h>
+#include <locale.h>
+#include <md5.h>
+#include <regex.h>
 #include <signal.h>
+#include <stdbool.h>
+#include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
-#include <locale.h>
+#include <wchar.h>
+#include <wctype.h>
+
+#include "coll.h"
+#include "file.h"
+#include "sort.h"
 
-int REC_D = '\n';
-u_char d_mask[NBINS];          /* flags for rec_d, field_d, <blank> */
+#ifndef WITHOUT_NLS
+#include <nl_types.h>
+nl_catd catalog;
+#endif
+
+#define        OPTIONS "bcCdfghik:Mmno:RrsS:t:T:uVz"
+
+#define DEFAULT_RANDOM_SORT_SEED_FILE ("/dev/random")
+#define MAX_DEFAULT_RANDOM_SEED_DATA_SIZE (1024)
+
+static bool need_random;
+static const char *random_source = DEFAULT_RANDOM_SORT_SEED_FILE;
+static const void *random_seed;
+static size_t random_seed_size;
+
+MD5_CTX md5_ctx;
 
 /*
- * weight tables.  Gweights is one of ascii, Rascii..
- * modified to weight rec_d = 0 (or 255)
+ * Default messages to use when NLS is disabled or no catalogue
+ * is found.
  */
-u_char *const weight_tables[4] = { ascii, Rascii, Ftable, RFtable };
-u_char ascii[NBINS], Rascii[NBINS], RFtable[NBINS], Ftable[NBINS];
+const char *nlsstr[] = { "",
+/* 1*/"mutually exclusive flags",
+/* 2*/"extra argument not allowed with -c",
+/* 3*/"Unknown feature",
+/* 4*/"Wrong memory buffer specification",
+/* 5*/"0 field in key specs",
+/* 6*/"0 column in key specs",
+/* 7*/"Wrong file mode",
+/* 8*/"Cannot open file for reading",
+/* 9*/"Radix sort cannot be used with these sort options",
+/*10*/"The chosen sort method cannot be used with stable and/or unique sort",
+/*11*/"Invalid key position",
+/*12*/"Usage: %s [-bcCdfigMmnrsuz] [-kPOS1[,POS2] ... ] "
+      "[+POS1 [-POS2]] [-S memsize] [-T tmpdir] [-t separator] "
+      "[-o outfile] [--batch-size size] [--files0-from file] "
+      "[--heapsort] [--mergesort] [--radixsort] [--qsort] "
+      "[--mmap] "
+#if defined(SORT_THREADS)
+      "[--parallel thread_no] "
+#endif
+      "[--human-numeric-sort] "
+      "[--version-sort] [--random-sort [--random-source file]] "
+      "[--compress-program program] [file ...]\n" };
 
-int SINGL_FLD = 0, SEP_FLAG = 0, UNIQUE = 0;
-int REVERSE = 0;
-int posix_sort;
+struct sort_opts sort_opts_vals;
 
-unsigned int debug_flags = 0;
+bool debug_sort;
+bool need_hint;