Natural Filename Sortingpatch-swanson_natural_sort

As per feature request 2951477, natural filename sorting is preferred by most humans.
This patch uses strnatcasecmp (for case insensitivity) from the suggested Natural Order
String Comparison (http://sourcefrog.net/projects/natsort/) which is ZLIb licensed and compatible with GPL.
However this doesn't help if a client subsequently resorts filenames itself...

Had a bit of fun finding out about scandir prototype changes and man page errors in
glibc (http://stackoverflow.com/questions/146291/manpage-scandir-prototype-weirdness).
This also changed in uClibc too and I'm not sure about testing for its change.

Note: committer changed from makefile to Scons

5 files changed, 168 insertions, 6 deletions

diff --git a/src/SConscript b/src/SConscript
index 36c5cd9..ef372ab 100644
--- a/src/SConscript
+++ b/src/SConscript
@@ -8,7 +8,7 @@ minidlna_sources = [
     "sql.c", "utils.c", "metadata.c", "scanner.c", "inotify.c",
     "tivo_utils.c", "tivo_beacon.c", "tivo_commands.c",
     "tagutils/textutils.c", "tagutils/misc.c", "tagutils/tagutils.c",
-    "playlist.c", "image_utils.c", "albumart.c", "log.c"
+    "playlist.c", "image_utils.c", "albumart.c", "log.c", "naturalsort.c"
 ]
 testupnpdescgen_sources = [ "testupnpdescgen.c", "upnpdescgen.c" ]
 
diff --git a/src/minidlna.c b/src/minidlna.c
index 4142c88..d9e44f6 100644
--- a/src/minidlna.c
+++ b/src/minidlna.c
@@ -80,6 +80,7 @@
 
 #include "upnpglobalvars.h"
 #include "sql.h"
+#include "naturalsort.h"
 #include "upnphttp.h"
 #include "upnpdescgen.h"
 #include "minidlnapath.h"
@@ -330,6 +331,7 @@ open_db(void)
 	sql_exec(db, "pragma journal_mode = OFF");
 	sql_exec(db, "pragma synchronous = OFF;");
 	sql_exec(db, "pragma default_cache_size = 8192;");
+	sqlite3_create_collation(db, "naturalsort", SQLITE_UTF8, NULL, naturalsort);
 	return new_db;
 }
 
diff --git a/src/naturalsort.c b/src/naturalsort.c
new file mode 100644
index 0000000..1283196
--- /dev/null
+++ b/src/naturalsort.c
@@ -0,0 +1,133 @@
+/* SQLite natural sort collation funtion
+ *
+ * Natural sort of strings, ignoring case and leading spaces.
+ * Alan Swanson <swanson@ukfsn.org> 2011
+ *
+ * strverscasecmp() function derived from uClibc 0.9.31 strverscmp() function
+ * by Hai Zaar, Codefidence Ltd <haizaar@codefidence.com>
+ * which in turn derived from from glibc 2.3.2 strverscmp() function
+ * by Jean-François Bignolles <bignolle@ecoledoc.ibp.fr>
+ * Copyright (C) 1997, 2002 Free Software Foundation, Inc.
+ *
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <string.h>
+#include <ctype.h>
+#include <stdint.h>
+
+/* states: S_N: normal, S_I: comparing integral part, S_F: comparing
+   fractional parts, S_Z: idem but with leading Zeroes only */
+#define  S_N    0x0
+#define  S_I    0x4
+#define  S_F    0x8
+#define  S_Z    0xC
+
+/* result_type: CMP: return diff; LEN: compare using len_diff/diff */
+#define  CMP    2
+#define  LEN    3
+
+/* using more efficient isdigit() */
+#undef isdigit
+#define isdigit(a) ((unsigned)((a) - '0') <= 9)
+
+/* Compare S1 and S2 as strings holding indices/version numbers,
+   returning less than, equal to or greater than zero if S1 is less than,
+   equal to or greater than S2 (for more info, see the texinfo doc).
+*/
+static int strverscasecmp (const char *s1, const char *s2)
+{
+  const unsigned char *p1 = (const unsigned char *) s1;
+  const unsigned char *p2 = (const unsigned char *) s2;
+  unsigned char c1, c2;
+  int state;
+  int diff;
+
+  /* Symbol(s)    0       [1-9]   others  (padding)
+     Transition   (10) 0  (01) d  (00) x  (11) -   */
+  static const uint8_t next_state[] =
+  {
+      /* state    x    d    0    - */
+      /* S_N */  S_N, S_I, S_Z, S_N,
+      /* S_I */  S_N, S_I, S_I, S_I,
+      /* S_F */  S_N, S_F, S_F, S_F,
+      /* S_Z */  S_N, S_F, S_Z, S_Z
+  };
+
+  static const int8_t result_type[] =
+  {
+      /* state   x/x  x/d  x/0  x/-  d/x  d/d  d/0  d/-
+                 0/x  0/d  0/0  0/-  -/x  -/d  -/0  -/- */
+
+      /* S_N */  CMP, CMP, CMP, CMP, CMP, LEN, CMP, CMP,
+                 CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP,
+      /* S_I */  CMP, -1,  -1,  CMP, +1,  LEN, LEN, CMP,
+                 +1,  LEN, LEN, CMP, CMP, CMP, CMP, CMP,
+      /* S_F */  CMP, CMP, CMP, CMP, CMP, LEN, CMP, CMP,
+                 CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP,
+      /* S_Z */  CMP, +1,  +1,  CMP, -1,  CMP, CMP, CMP,
+                 -1,  CMP, CMP, CMP
+  };
+
+  if (p1 == p2)
+    return 0;
+
+  c1 = *p1;
+  c2 = *p2;
+
+  /* Skip leading spaces. */
+  while (isspace(c1))
+    c1 = *++p1;
+  while (isspace(c2))
+    c2 = *++p2;
+
+  c1 = tolower(*p1++);
+  c2 = tolower(*p2++);
+  /* Hint: '0' is a digit too.  */
+  state = S_N | ((c1 == '0') + (isdigit (c1) != 0));
+
+  while ((diff = c1 - c2) == 0 && c1 != '\0')
+    {
+      state = next_state[state];
+      c1 = tolower(*p1++);
+      c2 = tolower(*p2++);
+      state |= (c1 == '0') + (isdigit (c1) != 0);
+    }
+
+  state = result_type[state << 2 | (((c2 == '0') + (isdigit (c2) != 0)))];
+
+  switch (state)
+  {
+    case CMP:
+      return diff;
+
+    case LEN:
+      while (isdigit (*p1++))
+	if (!isdigit (*p2++))
+	  return 1;
+
+      return isdigit (*p2) ? -1 : diff;
+
+    default:
+      return state;
+  }
+}
+
+int
+naturalsort(void *arg, int len1, const void *data1, int len2, const void *data2)
+{
+  return strverscasecmp((const char *)data1, (const char *)data2);
+}
diff --git a/src/naturalsort.h b/src/naturalsort.h
new file mode 100644
index 0000000..12b1bf0
--- /dev/null
+++ b/src/naturalsort.h
@@ -0,0 +1,23 @@
+/* SQLite natural sort collation function
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+#ifndef __NATURALSORT_H__
+#define __NATURALSORT_H__
+
+int naturalsort(void *arg, int len1, const void *data1, int len2, const void *data2);
+
+#endif /* __NATURALSORT_H__ */
diff --git a/src/upnpsoap.c b/src/upnpsoap.c
index 1af0f0c..4ed3d4a 100644
--- a/src/upnpsoap.c
+++ b/src/upnpsoap.c
@@ -511,7 +511,7 @@ parse_sort_criteria(char * sortCriteria, int * error)
 		}
 		else if( strcasecmp(item, "dc:title") == 0 )
 		{
-			strcat(order, "d.TITLE");
+			strcat(order, "d.TITLE COLLATE naturalsort");
 			title_sorted = 1;
 		}
 		else if( strcasecmp(item, "dc:date") == 0 )
@@ -547,7 +547,7 @@ parse_sort_criteria(char * sortCriteria, int * error)
 	}
 	/* Add a "tiebreaker" sort order */
 	if( !title_sorted )
-		strcat(order, ", TITLE ASC");
+		strcat(order, ", d.TITLE COLLATE naturalsort ASC");
 
 	return order;
 }
@@ -1088,7 +1088,7 @@ BrowseContentDirectory(struct upnphttp * h, const char * action)
 			if( strncmp(ObjectID, MUSIC_PLIST_ID, strlen(MUSIC_PLIST_ID)) == 0 )
 			{
 				if( strcmp(ObjectID, MUSIC_PLIST_ID) == 0 )
-					asprintf(&orderBy, "order by d.TITLE");
+					asprintf(&orderBy, "order by d.TITLE COLLATE naturalsort");
 				else
 					asprintf(&orderBy, "order by length(OBJECT_ID), OBJECT_ID");
 			}
@@ -1097,7 +1097,7 @@ BrowseContentDirectory(struct upnphttp * h, const char * action)
 #ifdef __sparc__
 				if( totalMatches < 10000 )
 #endif
-				asprintf(&orderBy, "order by o.CLASS, d.DISC, d.TRACK, d.TITLE");
+				asprintf(&orderBy, "order by o.CLASS, d.DISC, d.TRACK, d.TITLE COLLATE naturalsort");
 			}
 		}
 		/* If it's a DLNA client, return an error for bad sort criteria */
@@ -1324,7 +1324,11 @@ SearchContentDirectory(struct upnphttp * h, const char * action)
 	ret = 0;
 	if( totalMatches < 10000 )
 #endif
-		orderBy = parse_sort_criteria(SortCriteria, &ret);
+		if ( SortCriteria )
+			orderBy = parse_sort_criteria(SortCriteria, &ret);
+		else
+			asprintf(&orderBy, "order by d.TITLE COLLATE naturalsort");
+
 	/* If it's a DLNA client, return an error for bad sort criteria */
 	if( (args.flags & FLAG_DLNA) && ret )
 	{