1/* -*- mode: c; c-file-style: "k&r" -*- 2 3 strnatcmp.c -- Perform 'natural order' comparisons of strings in C. 4 Copyright (C) 2000, 2004 by Martin Pool <mbp sourcefrog net> 5 6 This software is provided 'as-is', without any express or implied 7 warranty. In no event will the authors be held liable for any damages 8 arising from the use of this software. 9 10 Permission is granted to anyone to use this software for any purpose, 11 including commercial applications, and to alter it and redistribute it 12 freely, subject to the following restrictions: 13 14 1. The origin of this software must not be misrepresented; you must not 15 claim that you wrote the original software. If you use this software 16 in a product, an acknowledgment in the product documentation would be 17 appreciated but is not required. 18 2. Altered source versions must be plainly marked as such, and must not be 19 misrepresented as being the original software. 20 3. This notice may not be removed or altered from any source distribution. 21*/ 22 23 24/* partial change history: 25 * 26 * 2004-10-10 mbp: Lift out character type dependencies into macros. 27 * 28 * Eric Sosman pointed out that ctype functions take a parameter whose 29 * value must be that of an unsigned int, even on platforms that have 30 * negative chars in their default char type. 31 */ 32 33#include <ctype.h> 34#include <string.h> 35#include <assert.h> 36#include <stdio.h> 37 38#include "strnatcmp.h" 39 40 41/* These are defined as macros to make it easier to adapt this code to 42 * different characters types or comparison functions. */ 43static inline int 44nat_isdigit(nat_char a) 45{ 46 return isdigit((unsigned char) a); 47} 48 49 50static inline int 51nat_isspace(nat_char a) 52{ 53 return isspace((unsigned char) a); 54} 55 56 57static inline nat_char 58nat_toupper(nat_char a) 59{ 60 return toupper((unsigned char) a); 61} 62 63 64 65static int 66compare_right(nat_char const *a, nat_char const *b) 67{ 68 int bias = 0; 69 70 /* The longest run of digits wins. That aside, the greatest 71 value wins, but we can't know that it will until we've scanned 72 both numbers to know that they have the same magnitude, so we 73 remember it in BIAS. */ 74 for (;; a++, b++) { 75 if (!nat_isdigit(*a) && !nat_isdigit(*b)) 76 return bias; 77 else if (!nat_isdigit(*a)) 78 return -1; 79 else if (!nat_isdigit(*b)) 80 return +1; 81 else if (*a < *b) { 82 if (!bias) 83 bias = -1; 84 } else if (*a > *b) { 85 if (!bias) 86 bias = +1; 87 } else if (!*a && !*b) 88 return bias; 89 } 90 91 return 0; 92} 93 94 95static int 96compare_left(nat_char const *a, nat_char const *b) 97{ 98 /* Compare two left-aligned numbers: the first to have a 99 different value wins. */ 100 for (;; a++, b++) { 101 if (!nat_isdigit(*a) && !nat_isdigit(*b)) 102 return 0; 103 else if (!nat_isdigit(*a)) 104 return -1; 105 else if (!nat_isdigit(*b)) 106 return +1; 107 else if (*a < *b) 108 return -1; 109 else if (*a > *b) 110 return +1; 111 } 112 113 return 0; 114} 115 116 117static int strnatcmp0(nat_char const *a, nat_char const *b, int fold_case) 118{ 119 int ai, bi; 120 nat_char ca, cb; 121 int fractional, result; 122 123 assert(a && b); 124 ai = bi = 0; 125 while (1) { 126 ca = a[ai]; cb = b[bi]; 127 128 /* skip over leading spaces or zeros */ 129 while (nat_isspace(ca)) 130 ca = a[++ai]; 131 132 while (nat_isspace(cb)) 133 cb = b[++bi]; 134 135 /* process run of digits */ 136 if (nat_isdigit(ca) && nat_isdigit(cb)) { 137 fractional = (ca == '0' || cb == '0'); 138 139 if (fractional) { 140 if ((result = compare_left(a+ai, b+bi)) != 0) 141 return result; 142 } else { 143 if ((result = compare_right(a+ai, b+bi)) != 0) 144 return result; 145 } 146 } 147 148 if (!ca && !cb) { 149 /* The strings compare the same. Perhaps the caller 150 will want to call strcmp to break the tie. */ 151 return 0; 152 } 153 154 if (fold_case) { 155 ca = nat_toupper(ca); 156 cb = nat_toupper(cb); 157 } 158 159 if (ca < cb) 160 return -1; 161 else if (ca > cb) 162 return +1; 163 164 ++ai; ++bi; 165 } 166} 167 168 169 170int strnatcmp(nat_char const *a, nat_char const *b) { 171 return strnatcmp0(a, b, 0); 172} 173 174 175/* Compare, recognizing numeric string and ignoring case. */ 176int strnatcasecmp(nat_char const *a, nat_char const *b) { 177 return strnatcmp0(a, b, 1); 178} 179