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