1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
// *****************************************************************************
// * This file is part of the FreeFileSync project. It is distributed under *
// * GNU General Public License: http://www.gnu.org/licenses/gpl-3.0 *
// * Copyright (C) Zenju (zenju AT freefilesync DOT org) - All Rights Reserved *
// *****************************************************************************
#include "zstring.h"
#include <stdexcept>
#include "utf.h"
using namespace zen;
/*
MSDN "Handling Sorting in Your Applications": https://msdn.microsoft.com/en-us/library/windows/desktop/dd318144
Perf test: compare strings 10 mio times; 64 bit build
-----------------------------------------------------
string a = "Fjk84$%kgfj$%T\\\\Gffg\\gsdgf\\fgsx----------d-"
string b = "fjK84$%kgfj$%T\\\\gfFg\\gsdgf\\fgSy----------dfdf"
Windows (UTF16 wchar_t)
4 ns | wcscmp
67 ns | CompareStringOrdinalFunc+ + bIgnoreCase
314 ns | LCMapString + wmemcmp
OS X (UTF8 char)
6 ns | strcmp
98 ns | strcasecmp
120 ns | strncasecmp + std::min(sizeLhs, sizeRhs);
856 ns | CFStringCreateWithCString + CFStringCompare(kCFCompareCaseInsensitive)
1110 ns | CFStringCreateWithCStringNoCopy + CFStringCompare(kCFCompareCaseInsensitive)
________________________
time per call | function
*/
namespace
{
int compareNoCaseUtf8(const char* lhs, size_t lhsLen, const char* rhs, size_t rhsLen)
{
//- strncasecmp implements ASCII CI-comparsion only! => signature is broken for UTF8-input; toupper() similarly doesn't support Unicode
//- wcsncasecmp: https://opensource.apple.com/source/Libc/Libc-763.12/string/wcsncasecmp-fbsd.c
// => re-implement comparison based on towlower() to avoid memory allocations
using namespace zen::implementation;
UtfDecoder<char> decL(lhs, lhsLen);
UtfDecoder<char> decR(rhs, rhsLen);
for (;;)
{
const Opt<CodePoint> cpL = decL.getNext();
const Opt<CodePoint> cpR = decR.getNext();
if (!cpL || !cpR)
return static_cast<int>(!cpR) - static_cast<int>(!cpL);
static_assert(sizeof(wchar_t) == sizeof(CodePoint), "");
const wchar_t charL = ::towlower(static_cast<wchar_t>(*cpL)); //ordering: towlower() converts to higher code points than towupper()
const wchar_t charR = ::towlower(static_cast<wchar_t>(*cpR)); //uses LC_CTYPE category of current locale
if (charL != charR)
return static_cast<unsigned int>(charL) - static_cast<unsigned int>(charR); //unsigned char-comparison is the convention!
//unsigned underflow is well-defined!
}
}
}
int cmpStringNaturalLinux(const char* lhs, size_t lhsLen, const char* rhs, size_t rhsLen)
{
const char* const lhsEnd = lhs + lhsLen;
const char* const rhsEnd = rhs + rhsLen;
/*
- compare strings after conceptually creating blocks of whitespace/numbers/text
- implement strict weak ordering!
- don't follow broken "strnatcasecmp": https://github.com/php/php-src/blob/master/ext/standard/strnatcmp.c
1. incorrect non-ASCII CI-comparison
2. incorrect bounds checks
3. incorrect trimming of *all* whitespace
4. arbitrary handling of leading 0 only at string begin
5. incorrect handling of whitespace following a number
6. code is a mess
*/
for (;;)
{
if (lhs == lhsEnd || rhs == rhsEnd)
return static_cast<int>(lhs != lhsEnd) - static_cast<int>(rhs != rhsEnd); //"nothing" before "something"
//note: "something" never would have been condensed to "nothing" further below => can finish evaluation here
const bool wsL = isWhiteSpace(*lhs);
const bool wsR = isWhiteSpace(*rhs);
if (wsL != wsR)
return static_cast<int>(!wsL) - static_cast<int>(!wsR); //whitespace before non-ws!
if (wsL)
{
++lhs, ++rhs;
while (lhs != lhsEnd && isWhiteSpace(*lhs)) ++lhs;
while (rhs != rhsEnd && isWhiteSpace(*rhs)) ++rhs;
continue;
}
const bool digitL = isDigit(*lhs);
const bool digitR = isDigit(*rhs);
if (digitL != digitR)
return static_cast<int>(!digitL) - static_cast<int>(!digitR); //number before chars!
if (digitL)
{
while (lhs != lhsEnd && *lhs == '0') ++lhs;
while (rhs != rhsEnd && *rhs == '0') ++rhs;
int rv = 0;
for (;; ++lhs, ++rhs)
{
const bool endL = lhs == lhsEnd || !isDigit(*lhs);
const bool endR = rhs == rhsEnd || !isDigit(*rhs);
if (endL != endR)
return static_cast<int>(!endL) - static_cast<int>(!endR); //more digits means bigger number
if (endL)
break; //same number of digits
if (rv == 0 && *lhs != *rhs)
rv = *lhs - *rhs; //found first digit difference comparing from left
}
if (rv != 0)
return rv;
continue;
}
//compare full junks of text: consider unicode encoding!
const char* textBeginL = lhs++;
const char* textBeginR = rhs++; //current char is neither white space nor digit at this point!
while (lhs != lhsEnd && !isWhiteSpace(*lhs) && !isDigit(*lhs)) ++lhs;
while (rhs != rhsEnd && !isWhiteSpace(*rhs) && !isDigit(*rhs)) ++rhs;
const int rv = compareNoCaseUtf8(textBeginL, lhs - textBeginL, textBeginR, rhs - textBeginR);
if (rv != 0)
return rv;
}
}
namespace
{
}
int CmpNaturalSort::operator()(const Zchar* lhs, size_t lhsLen, const Zchar* rhs, size_t rhsLen) const
{
//auto strL = utfTo<std::string>(Zstring(lhs, lhsLen));
//auto strR = utfTo<std::string>(Zstring(rhs, rhsLen));
//return cmpStringNaturalLinux(strL.c_str(), strL.size(), strR.c_str(), strR.size());
return cmpStringNaturalLinux(lhs, lhsLen, rhs, rhsLen);
}
|
