summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAdrien Destugues <pulkomandy@pulkomandy.tk>2017-05-29 11:29:33 (GMT)
committerAdrien Destugues <pulkomandy@pulkomandy.tk>2017-05-29 12:04:44 (GMT)
commit3ec770177938efc5a7fee54d03b45fa593a57988 (patch)
treea136ed22844387e36f07b4fd135c466e5046c330
parent2b204c565cb41999b449b5ec4bf2720787345f7c (diff)
NaturalCompare: implement using locale kitHEADhrev51188master
The non-locale aware version is kept in src/build/libshared for use on the host system and in packagefs (kernel add-on). In both cases, ICU is not available. Fixes #8192
-rw-r--r--src/add-ons/kernel/file_systems/packagefs/Jamfile2
-rw-r--r--src/build/libshared/NaturalCompare.cpp151
-rw-r--r--src/kits/shared/NaturalCompare.cpp129
-rw-r--r--src/tests/kits/shared/NaturalCompareTest.cpp16
4 files changed, 175 insertions, 123 deletions
diff --git a/src/add-ons/kernel/file_systems/packagefs/Jamfile b/src/add-ons/kernel/file_systems/packagefs/Jamfile
index be1f260..52aebe0 100644
--- a/src/add-ons/kernel/file_systems/packagefs/Jamfile
+++ b/src/add-ons/kernel/file_systems/packagefs/Jamfile
@@ -140,7 +140,7 @@ SEARCH on [ FGristFiles $(HAIKU_PACKAGE_FS_PACKAGE_READER_SOURCES) ]
SEARCH on [ FGristFiles $(HAIKU_PACKAGE_FS_PACKAGE_READER_SOURCES_V1) ]
+= [ FDirName $(HAIKU_TOP) src kits package hpkg v1 ] ;
SEARCH on [ FGristFiles $(libSharedSources) ]
- += [ FDirName $(HAIKU_TOP) src kits shared ] ;
+ += [ FDirName $(HAIKU_TOP) src build libshared ] ;
SEARCH on [ FGristFiles $(storageKitSources) ]
+= [ FDirName $(HAIKU_TOP) src kits storage ] ;
SEARCH on [ FGristFiles $(supportKitSources) ]
diff --git a/src/build/libshared/NaturalCompare.cpp b/src/build/libshared/NaturalCompare.cpp
new file mode 100644
index 0000000..9b2256f
--- /dev/null
+++ b/src/build/libshared/NaturalCompare.cpp
@@ -0,0 +1,151 @@
+/*
+ * Copyright 2009, Dana Burkart
+ * Copyright 2009, Stephan Aßmus <superstippi@gmx.de>
+ * Copyright 2010, Axel Dörfler, axeld@pinc-software.de
+ * Copyright 2010, Rene Gollent (anevilyak@gmail.com)
+ * Distributed under the terms of the MIT License.
+ */
+
+
+#include <NaturalCompare.h>
+
+#include <ctype.h>
+#include <string.h>
+#include <strings.h>
+
+#include <StorageDefs.h>
+#include <SupportDefs.h>
+
+
+namespace BPrivate {
+
+
+// #pragma mark - Natural sorting
+
+
+struct natural_chunk {
+ enum chunk_type {
+ NUMBER,
+ ASCII,
+ END
+ };
+ chunk_type type;
+ char buffer[B_FILE_NAME_LENGTH];
+ int32 length;
+};
+
+
+inline int32
+FetchNaturalChunk(natural_chunk& chunk, const char* source)
+{
+ if (chunk.type == natural_chunk::ASCII) {
+ // string chunk
+ int32 pos = 0;
+ while (!isdigit(source[pos]) && !isspace(source[pos])
+ && source[pos] != '\0') {
+ pos++;
+ }
+ strlcpy(chunk.buffer, source, pos + 1);
+ chunk.length = pos;
+ return pos;
+ }
+
+ // Skip leading zeros and whitespace characters
+ int32 skip = 0;
+ while (source[0] == '0' || isspace(source[0])) {
+ source++;
+ skip++;
+ }
+
+ // Number chunk (stop at next white space)
+ int32 pos = 0;
+ while (isdigit(source[pos])) {
+ pos++;
+ }
+
+ strlcpy(chunk.buffer, source, pos + 1);
+ chunk.length = pos;
+
+ // Skip trailing whitespace as well
+ while (isspace(source[pos])) {
+ source++;
+ skip++;
+ }
+
+ return pos + skip;
+}
+
+
+//! Compares two strings naturally, as opposed to lexicographically
+int
+NaturalCompare(const char* stringA, const char* stringB)
+{
+ if (stringA == NULL)
+ return stringB == NULL ? 0 : -1;
+ if (stringB == NULL)
+ return 1;
+
+ natural_chunk a;
+ natural_chunk b;
+
+ uint32 indexA = 0;
+ uint32 indexB = 0;
+
+ while (true) {
+ // Determine type of next chunks in each string based on first char
+ if (stringA[indexA] == '\0')
+ a.type = natural_chunk::END;
+ else if (isdigit(stringA[indexA]) || isspace(stringA[indexA]))
+ a.type = natural_chunk::NUMBER;
+ else
+ a.type = natural_chunk::ASCII;
+
+ if (stringB[indexB] == '\0')
+ b.type = natural_chunk::END;
+ else if (isdigit(stringB[indexB]) || isspace(stringB[indexB]))
+ b.type = natural_chunk::NUMBER;
+ else
+ b.type = natural_chunk::ASCII;
+
+ // Check if we reached the end of either string
+ if (a.type == natural_chunk::END)
+ return b.type == natural_chunk::END ? 0 : -1;
+ if (b.type == natural_chunk::END)
+ return 1;
+
+ if (a.type != b.type) {
+ // Different chunk types, just compare the remaining strings
+ return strcasecmp(&stringA[indexA], &stringB[indexB]);
+ }
+
+ // Fetch the next chunks
+ indexA += FetchNaturalChunk(a, &stringA[indexA]);
+ indexB += FetchNaturalChunk(b, &stringB[indexB]);
+
+ // Compare the two chunks based on their type
+ if (a.type == natural_chunk::ASCII) {
+ // String chunks
+ int result = strcasecmp(a.buffer, b.buffer);
+ if (result != 0)
+ return result;
+ } else {
+ // Number chunks - they are compared as strings to allow an
+ // almost arbitrary number of digits.
+ if (a.length > b.length)
+ return 1;
+ if (a.length < b.length)
+ return -1;
+
+ int result = strcmp(a.buffer, b.buffer);
+ if (result != 0)
+ return result;
+ }
+
+ // The chunks were equal, proceed with the next chunk
+ }
+
+ return 0;
+}
+
+
+} // namespace BPrivate
diff --git a/src/kits/shared/NaturalCompare.cpp b/src/kits/shared/NaturalCompare.cpp
index 9b2256f..6c60b75 100644
--- a/src/kits/shared/NaturalCompare.cpp
+++ b/src/kits/shared/NaturalCompare.cpp
@@ -13,8 +13,8 @@
#include <string.h>
#include <strings.h>
-#include <StorageDefs.h>
-#include <SupportDefs.h>
+#include <Collator.h>
+#include <Locale.h>
namespace BPrivate {
@@ -23,128 +23,21 @@ namespace BPrivate {
// #pragma mark - Natural sorting
-struct natural_chunk {
- enum chunk_type {
- NUMBER,
- ASCII,
- END
- };
- chunk_type type;
- char buffer[B_FILE_NAME_LENGTH];
- int32 length;
-};
-
-
-inline int32
-FetchNaturalChunk(natural_chunk& chunk, const char* source)
-{
- if (chunk.type == natural_chunk::ASCII) {
- // string chunk
- int32 pos = 0;
- while (!isdigit(source[pos]) && !isspace(source[pos])
- && source[pos] != '\0') {
- pos++;
- }
- strlcpy(chunk.buffer, source, pos + 1);
- chunk.length = pos;
- return pos;
- }
-
- // Skip leading zeros and whitespace characters
- int32 skip = 0;
- while (source[0] == '0' || isspace(source[0])) {
- source++;
- skip++;
- }
-
- // Number chunk (stop at next white space)
- int32 pos = 0;
- while (isdigit(source[pos])) {
- pos++;
- }
-
- strlcpy(chunk.buffer, source, pos + 1);
- chunk.length = pos;
-
- // Skip trailing whitespace as well
- while (isspace(source[pos])) {
- source++;
- skip++;
- }
-
- return pos + skip;
-}
-
-
//! Compares two strings naturally, as opposed to lexicographically
int
NaturalCompare(const char* stringA, const char* stringB)
{
- if (stringA == NULL)
- return stringB == NULL ? 0 : -1;
- if (stringB == NULL)
- return 1;
-
- natural_chunk a;
- natural_chunk b;
-
- uint32 indexA = 0;
- uint32 indexB = 0;
-
- while (true) {
- // Determine type of next chunks in each string based on first char
- if (stringA[indexA] == '\0')
- a.type = natural_chunk::END;
- else if (isdigit(stringA[indexA]) || isspace(stringA[indexA]))
- a.type = natural_chunk::NUMBER;
- else
- a.type = natural_chunk::ASCII;
-
- if (stringB[indexB] == '\0')
- b.type = natural_chunk::END;
- else if (isdigit(stringB[indexB]) || isspace(stringB[indexB]))
- b.type = natural_chunk::NUMBER;
- else
- b.type = natural_chunk::ASCII;
-
- // Check if we reached the end of either string
- if (a.type == natural_chunk::END)
- return b.type == natural_chunk::END ? 0 : -1;
- if (b.type == natural_chunk::END)
- return 1;
-
- if (a.type != b.type) {
- // Different chunk types, just compare the remaining strings
- return strcasecmp(&stringA[indexA], &stringB[indexB]);
- }
-
- // Fetch the next chunks
- indexA += FetchNaturalChunk(a, &stringA[indexA]);
- indexB += FetchNaturalChunk(b, &stringB[indexB]);
-
- // Compare the two chunks based on their type
- if (a.type == natural_chunk::ASCII) {
- // String chunks
- int result = strcasecmp(a.buffer, b.buffer);
- if (result != 0)
- return result;
- } else {
- // Number chunks - they are compared as strings to allow an
- // almost arbitrary number of digits.
- if (a.length > b.length)
- return 1;
- if (a.length < b.length)
- return -1;
-
- int result = strcmp(a.buffer, b.buffer);
- if (result != 0)
- return result;
- }
-
- // The chunks were equal, proceed with the next chunk
+ static BCollator* collator = NULL;
+
+ if (collator == NULL)
+ {
+ collator = new BCollator();
+ BLocale::Default()->GetCollator(collator);
+ collator->SetStrength(B_COLLATE_SECONDARY);
+ collator->SetNumericSorting(true);
}
- return 0;
+ return collator->Compare(stringA, stringB);
}
diff --git a/src/tests/kits/shared/NaturalCompareTest.cpp b/src/tests/kits/shared/NaturalCompareTest.cpp
index f3b9580..3bf17cf 100644
--- a/src/tests/kits/shared/NaturalCompareTest.cpp
+++ b/src/tests/kits/shared/NaturalCompareTest.cpp
@@ -36,23 +36,31 @@ void
NaturalCompareTest::TestSome()
{
static const Sample samples[] = {
+ // NULL in either side of the comparison
{NULL, NULL, 0},
{NULL, "A", -1},
+ {"A", NULL, 1},
+ // Case insensitive
{"a", "A", 0},
+ {"é", "É", 0},
+ // Handling of accented characters
{"ä", "a", 1},
+ // Natural number ordering
{"3", "99", -1},
{"9", "19", -1},
{"13", "99", -1},
{"9", "111", -1},
{"00000009", "111", -1},
+ // Natural number ordering, ignoring leading space
{"Hallo2", "hallo12", -1},
{"Hallo 2", "hallo12", -1},
{"Hallo 2", "hallo12", -1},
{"Hallo 2 ", "hallo12", -1},
- {"12 äber 42", "12aber42", 1},
- {"12 äber 42", "12aber43", 1},
- {"12 äber 44", "12aber43", 1},
- {"12 äber 44", "12 aber45", 1},
+ // A mix of everything
+ {"12 äber 42", "12aber42", -1},
+ {"12 äber 42", "12aber43", -1},
+ {"12 äber 44", "12aber43", -1},
+ {"12 äber 44", "12 aber45", -1},
};
_RunTests(samples, sizeof(samples) / sizeof(Sample));
}