1 /* 2 * Copyright 2009, Dana Burkart 3 * Copyright 2009, Stephan Aßmus <superstippi@gmx.de> 4 * Copyright 2010, Axel Dörfler, axeld@pinc-software.de 5 * Copyright 2010, Rene Gollent (anevilyak@gmail.com) 6 * Distributed under the terms of the MIT License. 7 */ 8 9 10 #include <NaturalCompare.h> 11 12 #include <ctype.h> 13 #include <string.h> 14 15 #include <StorageDefs.h> 16 #include <SupportDefs.h> 17 18 19 namespace BPrivate { 20 21 22 // #pragma mark - Natural sorting 23 24 25 struct natural_chunk { 26 enum chunk_type { 27 NUMBER, 28 ASCII, 29 END 30 }; 31 chunk_type type; 32 char buffer[B_FILE_NAME_LENGTH]; 33 int32 length; 34 }; 35 36 37 inline int32 38 FetchNaturalChunk(natural_chunk& chunk, const char* source) 39 { 40 if (chunk.type == natural_chunk::ASCII) { 41 // string chunk 42 int32 pos = 0; 43 while (!isdigit(source[pos]) && !isspace(source[pos]) 44 && source[pos] != '\0') { 45 pos++; 46 } 47 strlcpy(chunk.buffer, source, pos + 1); 48 chunk.length = pos; 49 return pos; 50 } 51 52 // skip leading zeros and whitespace characters 53 int32 skip = 0; 54 while (source[0] == '0' || isspace(source[0])) { 55 source++; 56 skip++; 57 } 58 59 // number chunk (stop at next white space) 60 int32 pos = 0; 61 while (isdigit(source[pos]) && source[pos] != '\0') { 62 pos++; 63 } 64 strlcpy(&chunk.buffer[sizeof(chunk.buffer) - 1 - pos], source, pos + 1); 65 chunk.length = pos; 66 67 return pos + skip; 68 } 69 70 71 //! Makes sure both number strings have the same size 72 inline void 73 NormalizeNumberChunks(natural_chunk& a, natural_chunk& b) 74 { 75 if (a.length > b.length) { 76 memset(&b.buffer[sizeof(b.buffer) - 1 - a.length], ' ', 77 a.length - b.length); 78 b.length = a.length; 79 } else if (b.length > a.length) { 80 memset(&a.buffer[sizeof(a.buffer) - 1 - b.length], ' ', 81 b.length - a.length); 82 a.length = b.length; 83 } 84 } 85 86 87 //! Compares two strings naturally, as opposed to lexicographically 88 int 89 NaturalCompare(const char* stringA, const char* stringB) 90 { 91 natural_chunk a; 92 natural_chunk b; 93 94 uint32 indexA = 0; 95 uint32 indexB = 0; 96 97 while (true) { 98 // Determine type of next chunks in each string based on first char 99 if (stringA[indexA] == '\0') 100 a.type = natural_chunk::END; 101 else if (isdigit(stringA[indexA]) || isspace(stringA[indexA])) 102 a.type = natural_chunk::NUMBER; 103 else 104 a.type = natural_chunk::ASCII; 105 106 if (stringB[indexB] == '\0') 107 b.type = natural_chunk::END; 108 else if (isdigit(stringB[indexB]) || isspace(stringB[indexB])) 109 b.type = natural_chunk::NUMBER; 110 else 111 b.type = natural_chunk::ASCII; 112 113 // Check if we reached the end of either string 114 if (a.type == natural_chunk::END) 115 return b.type == natural_chunk::END ? 0 : -1; 116 if (b.type == natural_chunk::END) 117 return 1; 118 119 if (a.type != b.type) { 120 // Different chunk types, just compare the remaining strings 121 return strcasecmp(&stringA[indexA], &stringB[indexB]); 122 } 123 124 // Fetch the next chunks 125 indexA += FetchNaturalChunk(a, &stringA[indexA]); 126 indexB += FetchNaturalChunk(b, &stringB[indexB]); 127 128 // Compare the two chunks based on their type 129 if (a.type == natural_chunk::ASCII) { 130 // String chunks 131 int result = strcasecmp(a.buffer, b.buffer); 132 if (result != 0) 133 return result; 134 } else { 135 // Number chunks - they are compared as strings to allow an 136 // arbitrary number of digits. 137 NormalizeNumberChunks(a, b); 138 139 int result = strcmp(a.buffer - 1 + sizeof(a.buffer) - a.length, 140 b.buffer - 1 + sizeof(b.buffer) - b.length); 141 if (result != 0) 142 return result; 143 } 144 145 // The chunks were equal, proceed with the next chunk 146 } 147 148 return 0; 149 } 150 151 152 } // namespace BPrivate 153