src/build/libshared/NaturalCompare.cpp

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