[PATCH 0/1] MR6690: sort: New program.

[PATCH 1/1] sort: New program.

[Hans Leidekker]

From: Hans Leidekker

---
 configure.ac              |   1 +
 programs/sort/Makefile.in |   6 +
 programs/sort/main.c      | 344 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 351 insertions(+)
 create mode 100644 programs/sort/Makefile.in
 create mode 100644 programs/sort/main.c

diff --git a/configure.ac b/configure.ac
index f5f7c0201f1..730ef2471ed 100644
--- a/configure.ac
+++ b/configure.ac
@@ -3489,6 +3489,7 @@ WINE_CONFIG_MAKEFILE(programs/services)
 WINE_CONFIG_MAKEFILE(programs/services/tests)
 WINE_CONFIG_MAKEFILE(programs/setx)
 WINE_CONFIG_MAKEFILE(programs/shutdown)
+WINE_CONFIG_MAKEFILE(programs/sort)
 WINE_CONFIG_MAKEFILE(programs/spoolsv)
 WINE_CONFIG_MAKEFILE(programs/start)
 WINE_CONFIG_MAKEFILE(programs/subst)
diff --git a/programs/sort/Makefile.in b/programs/sort/Makefile.in
new file mode 100644
index 00000000000..ab6ead595d4
--- /dev/null
+++ b/programs/sort/Makefile.in
@@ -0,0 +1,6 @@
+MODULE    = sort.exe
+
+EXTRADLLFLAGS = -mconsole -municode
+
+SOURCES = \
+	main.c
diff --git a/programs/sort/main.c b/programs/sort/main.c
new file mode 100644
index 00000000000..78069c81923
--- /dev/null
+++ b/programs/sort/main.c
@@ -0,0 +1,344 @@
+/*
+ * Copyright 2024 Hans Leidekker for CodeWeavers
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
+ */
+
+#include <stdarg.h>
+#include <unistd.h>
+
+#include <windef.h>
+#include <winbase.h>
+#include <winnls.h>
+#include <consoleapi.h>
+
+#include "wine/debug.h"
+
+WINE_DEFAULT_DEBUG_CHANNEL(sort);
+
+static BOOL option_unique;
+static BOOL option_c_locale;
+static BOOL option_reverse;
+
+struct line
+{
+    unsigned int start; /* offset into input buffer */
+    unsigned int len;
+};
+
+struct sorted_lines
+{
+    unsigned int count;     /* number of lines */
+    unsigned int capacity;  /* size of line array */
+    struct line *entry;     /* sorted line array */
+    char *buf;              /* input buffer */
+    unsigned int bufsize;
+};
+
+static inline int compare_string( const char *line, unsigned int len, const char *line2, unsigned int len2 )
+{
+    unsigned int i;
+
+    for (i = 0; i < min( len, len2 ); i++)
+    {
+        char a = tolower( line[i] ), b = tolower( line2[i] );
+        if (a > b) return 1;
+        if (a < b) return -1;
+    }
+    if (len > len2) return 1;
+    if (len < len2) return -1;
+    return 0;
+}
+
+static BOOL find_line( const struct sorted_lines *sorted, const char *line, unsigned int len, int *idx )
+{
+    int i, c, min = 0, max = sorted->count - 1;
+    const char *ptr;
+
+    while (min <= max)
+    {
+        i = (min + max) / 2;
+        ptr = sorted->buf + sorted->entry[i].start;
+
+        if (option_c_locale)
+            c = compare_string( ptr, sorted->entry[i].len, line, len );
+        else
+            c = CompareStringA( LOCALE_SYSTEM_DEFAULT, NORM_IGNORECASE, ptr, sorted->entry[i].len, line, len ) - 2;
+        if (option_reverse) c = -c;
+
+        if (c > 0) max = i - 1;
+        else if (c < 0) min = i + 1;
+        else
+        {
+            *idx = i;
+            return TRUE;
+        }
+    }
+    *idx = max + 1;
+    return FALSE;
+}
+
+static int insert_line( struct sorted_lines *sorted, const char *start, unsigned int len )
+{
+    int idx;
+
+    if (find_line( sorted, start, len, &idx ))
+    {
+        if (option_unique) return 0;
+        idx++;
+    }
+    if (sorted->count >= sorted->capacity)
+    {
+        sorted->capacity = max( 1024, sorted->capacity * 2 );
+        if (!(sorted->entry = realloc( sorted->entry, sorted->capacity * sizeof(*sorted->entry) )))
+        {
+            wprintf( L"Out of memory.\n" );
+            return 1;
+        }
+    }
+    memmove( &sorted->entry[idx] + 1, &sorted->entry[idx], (sorted->count - idx) * sizeof(*sorted->entry) );
+    sorted->entry[idx].start = start - sorted->buf;
+    sorted->entry[idx].len = len;
+    sorted->count++;
+    return 0;
+}
+
+static int sort_lines( struct sorted_lines *sorted )
+{
+    const char *p = sorted->buf, *q = sorted->buf;
+    unsigned int size = sorted->bufsize;
+
+    while (size)
+    {
+        if (p[0] == '\n' || (p[0] == '\r' && p[1] == '\n'))
+        {
+            if (p[0] == '\r') { p++; size--; }
+            if (insert_line( sorted, q, p - q  + 1 )) return 1;
+            q = p + 1;
+        }
+        p++; size--;
+    }
+    if (p != q && insert_line( sorted, q, p - q )) return 1;
+    return 0;
+}
+
+static int write_lines( const struct sorted_lines *sorted, HANDLE handle )
+{
+    unsigned int i;
+
+    for (i = 0; i < sorted->count; i++)
+    {
+        const char *ptr = sorted->buf + sorted->entry[i].start;
+        DWORD count;
+
+        if (handle == GetStdHandle( STD_OUTPUT_HANDLE ) &&
+            WriteConsoleA( handle, ptr, sorted->entry[i].len, &count, NULL )) continue;
+
+        if (!WriteFile( handle, ptr, sorted->entry[i].len, &count, NULL )) return 1;
+    }
+    return 0;
+}
+
+#define MAX_LINE 4096
+static char *read_input( HANDLE handle, unsigned int *ret_size )
+{
+    DWORD buflen = 1024, offset = 0, count;
+    char *ret = malloc( buflen ), *line = malloc( MAX_LINE );
+    const char *ctrl_z = NULL;
+
+    *ret_size = 0;
+    if (!ret || !line)
+    {
+        wprintf( L"Out of memory.\n" );
+        return NULL;
+    }
+    for (;;)
+    {
+        count = 0;
+        if (ReadConsoleA( handle, line, MAX_LINE, &count, NULL ))
+        {
+            if ((ctrl_z = memchr( line, 0x1a, count ))) count = ctrl_z - line;
+        }
+        else ReadFile( handle, line, MAX_LINE, &count, NULL );
+        if (!count) break;
+
+        if (buflen - offset < count + 2)
+        {
+            buflen = max( buflen * 2, offset + count + 2 );
+            if (!(ret = realloc( ret, buflen )))
+            {
+                wprintf( L"Out of memory.\n" );
+                return NULL;
+            }
+        }
+        memcpy( ret + offset, line, count );
+        offset += count;
+        if (ctrl_z)
+        {
+            memcpy( ret + offset, "\r\n", 2 );
+            offset += 2;
+            break;
+        }
+    }
+    *ret_size = offset;
+    return ret;
+}
+
+static char no_data[] = "";
+
+static char *map_file( HANDLE handle, unsigned int *ret_size )
+{
+    HANDLE mapping;
+    char *ret;
+
+    if (!(*ret_size = GetFileSize( handle, NULL ))) return no_data;
+    if (!(mapping = CreateFileMappingW( handle, NULL, PAGE_READONLY, 0, 0, NULL ))) return NULL;
+    ret = MapViewOfFile( mapping, FILE_MAP_READ, 0, 0, 0 );
+    CloseHandle( mapping );
+    return ret;
+}
+
+static HANDLE create_tmpfile( WCHAR *tmpfile )
+{
+    WCHAR tmpdir[MAX_PATH];
+
+    GetTempPathW( ARRAY_SIZE(tmpdir), tmpdir );
+    GetTempFileNameW( tmpdir, L"srt", 0, tmpfile );
+    return CreateFileW( tmpfile, GENERIC_WRITE, FILE_SHARE_READ, NULL, OPEN_EXISTING, 0, NULL );
+}
+
+static int sort_file( const WCHAR *in_file, const WCHAR *out_file )
+{
+    HANDLE in_handle, out_handle;
+    struct sorted_lines sorted = {0};
+    WCHAR tmpfile[MAX_PATH] = {0};
+    int ret = 1;
+
+    if (!in_file)
+    {
+        in_handle = GetStdHandle( STD_INPUT_HANDLE );
+        if (!(sorted.buf = read_input( in_handle, &sorted.bufsize )))
+        {
+            wprintf( L"Can't read input.\n" );
+            return 1;
+        }
+    }
+    else
+    {
+        in_handle = CreateFileW( in_file, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, 0, NULL );
+        if (in_handle == INVALID_HANDLE_VALUE)
+        {
+            wprintf( L"Can't open input file.\n" );
+            return 1;
+        }
+        if (!(sorted.buf = map_file( in_handle, &sorted.bufsize )))
+        {
+            wprintf( L"Can't read input.\n" );
+            CloseHandle( in_handle );
+            return 1;
+        }
+    }
+
+    if (!out_file) out_handle = GetStdHandle( STD_OUTPUT_HANDLE );
+    else
+    {
+        out_handle = CreateFileW( out_file, GENERIC_WRITE, FILE_SHARE_READ, NULL, CREATE_ALWAYS, 0, NULL );
+        if (out_handle == INVALID_HANDLE_VALUE)
+        {
+            if (GetLastError() != ERROR_SHARING_VIOLATION)
+            {
+                wprintf( L"Can't open output file.\n" );
+                CloseHandle( in_handle );
+                return 1;
+            }
+            out_handle = create_tmpfile( tmpfile );
+            if (out_handle == INVALID_HANDLE_VALUE)
+            {
+                wprintf( L"Can't open temporary output file.\n" );
+                CloseHandle( in_handle );
+                return 1;
+            }
+        }
+    }
+
+    if (!(ret = sort_lines( &sorted ))) ret = write_lines( &sorted, out_handle );
+
+    if (!in_file) free( sorted.buf );
+    else if (sorted.buf != no_data) UnmapViewOfFile( sorted.buf );
+    CloseHandle( in_handle );
+    CloseHandle( out_handle );
+
+    if (tmpfile[0])
+    {
+        if (ret) DeleteFileW( tmpfile );
+        else if (!MoveFileExW( tmpfile, out_file, MOVEFILE_REPLACE_EXISTING ))
+        {
+            wprintf( L"Can't move temporary output file.\n" );
+            return 1;
+        }
+    }
+    return ret;
+}
+
+int __cdecl wmain( int argc, WCHAR *argv[] )
+{
+    const WCHAR *in_file = NULL, *out_file = NULL, *locale = NULL;
+    int i;
+
+    for (i = 1; i < argc; i++)
+    {
+        if (argv[i][0] == '/')
+        {
+            if (!wcsicmp( argv[i] + 1, L"unique" )) option_unique = TRUE;
+            else if (!wcsicmp( argv[i] + 1, L"r" ) || !wcsicmp( argv[i] + 1, L"reverse" )) option_reverse = TRUE;
+            else if (!wcsicmp( argv[i] + 1, L"l" ) || !wcsicmp( argv[i] + 1, L"locale" ))
+            {
+                if (argc < i + 2)
+                {
+                    wprintf( L"Expected locale specifier.\n" );
+                    return 1;
+                }
+                locale = argv[i + 1];
+            }
+            else if (!wcsicmp( argv[i] + 1, L"o" ))
+            {
+                if (argc < i + 2)
+                {
+                    wprintf( L"Expected output filename.\n" );
+                    return 1;
+                }
+                out_file = argv[i + 1];
+            }
+            else
+            {
+                FIXME( "Unsupported option %s.\n", debugstr_w(argv[i]) );
+                return 1;
+            }
+        }
+        else if (argv[i] != out_file && argv[i] != locale) in_file = argv[i];
+    }
+
+    if (locale)
+    {
+        if (wcscmp( locale, L"C" ))
+        {
+            wprintf( L"Invalid locale specifier.\n" );
+            return 1;
+        }
+        option_c_locale = TRUE;
+    }
+
+    return sort_file( in_file, out_file );
+}

[PATCH 1/1] sort: New program.

[Marvin]

Hi,

It looks like your patch introduced the new failures shown below.
Please investigate and fix them before resubmitting your patch.
If they are not new, fixing them anyway would help a lot. Otherwise
please ask for the known failures list to be updated.

The tests also ran into some preexisting test failures. If you know how
to fix them that would be helpful. See the TestBot job for the details:

The full results can be found at:
https://testbot.winehq.org/JobDetails.pl?Key=149066

Your paranoid android.

=== debian11b (64 bit WoW report) ===

user32:
input.c:4305: Test succeeded inside todo block: button_down_hwnd_todo 1: got MSG_TEST_WIN hwnd 0000000001DA00E2, msg WM_LBUTTONDOWN, wparam 0x1, lparam 0x320032

[Aida Jonikienė (＠DodoGTA)]

This should solve https://bugs.winehq.org/show_bug.cgi?id=27933 (so maybe you should add a Wine-Bug header to the commit?)