summaryrefslogtreecommitdiff
path: root/package/firefox/patches
diff options
context:
space:
mode:
Diffstat (limited to 'package/firefox/patches')
-rw-r--r--package/firefox/patches/patch-configure63
-rw-r--r--package/firefox/patches/patch-gfx_angle_src_common_angleutils_cpp10
-rw-r--r--package/firefox/patches/patch-gfx_layers_BufferUnrotate_cpp10
-rw-r--r--package/firefox/patches/patch-ipc_chromium_src_base_debug_util_posix_cc13
-rw-r--r--package/firefox/patches/patch-ipc_chromium_src_base_file_util_h10
-rw-r--r--package/firefox/patches/patch-ipc_chromium_src_base_file_util_posix_cc48
-rw-r--r--package/firefox/patches/patch-js_src_Makefile_in14
-rw-r--r--package/firefox/patches/patch-js_src_assembler_wtf_Platform_h12
-rw-r--r--package/firefox/patches/patch-js_src_configure31
-rw-r--r--package/firefox/patches/patch-js_src_yarr_BumpPointerAllocator_h11
-rw-r--r--package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c43
-rw-r--r--package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_stun_h12
-rw-r--r--package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py23
-rw-r--r--package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py26
-rw-r--r--package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_audio_device_impl_cc11
-rw-r--r--package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_linux_audio_device_alsa_linux_cc11
-rw-r--r--package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_linux_audio_mixer_manager_alsa_linux_cc11
-rw-r--r--package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc23
-rw-r--r--package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp3385
-rw-r--r--package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_bsd_addr_c15
-rw-r--r--package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_os_userspace_h22
-rw-r--r--package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_pcb_c25
-rw-r--r--package/firefox/patches/patch-netwerk_sctp_src_user_environment_c14
-rw-r--r--package/firefox/patches/patch-netwerk_sctp_src_user_queue_h12
-rw-r--r--package/firefox/patches/patch-python_mozbuild_mozbuild_backend_recursivemake_py10
-rw-r--r--package/firefox/patches/patch-tools_profiler_platform-linux_cc12
-rw-r--r--package/firefox/patches/patch-tools_profiler_shared-libraries-linux_cc11
-rw-r--r--package/firefox/patches/patch-xpcom_ds_nsMathUtils_h22
-rw-r--r--package/firefox/patches/patch-xpcom_io_nsLocalFileUnix_cpp31
-rw-r--r--package/firefox/patches/patch-xpcom_threads_nsThread_cpp17
30 files changed, 94 insertions, 3864 deletions
diff --git a/package/firefox/patches/patch-configure b/package/firefox/patches/patch-configure
index 884cea4dd..52210624e 100644
--- a/package/firefox/patches/patch-configure
+++ b/package/firefox/patches/patch-configure
@@ -1,30 +1,41 @@
---- mozilla-release.orig/configure 2013-12-05 17:08:46.000000000 +0100
-+++ mozilla-release/configure 2014-01-06 18:17:43.008094174 +0100
-@@ -9787,27 +9787,6 @@ if test -z "$GNU_CC"; then
- esac
+--- mozilla-release.orig/configure 2015-01-09 05:39:04.000000000 +0100
++++ mozilla-release/configure 2015-02-04 11:49:00.000000000 +0100
+@@ -8156,38 +8156,6 @@ EOF
+
fi
--if test "$GNU_CC" -a -n "$DEVELOPER_OPTIONS"; then
-- if $CC -Wl,--version 2>&1 | grep -q "GNU ld"; then
-- GOLD=$($CC -print-prog-name=ld.gold)
-- case "$GOLD" in
-- /*)
-- ;;
-- *)
-- GOLD=$(which $GOLD)
-- ;;
-- esac
-- if test -n "$GOLD"; then
-- mkdir -p $_objdir/build/unix/gold
-- ln -s "$GOLD" $_objdir/build/unix/gold/ld
-- if $CC -B $_objdir/build/unix/gold -Wl,--version 2>&1 | grep -q "GNU gold"; then
-- LDFLAGS="$LDFLAGS -B $_objdir/build/unix/gold"
-- else
-- rm -rf $_objdir/build/unix/gold
-- fi
-- fi
-- fi
+-MOZ_ENABLE_PROFILER_SPS=1
+-
+-case "${OS_TARGET}" in
+-Android)
+- case "${CPU_ARCH}" in
+- x86 | arm) ;;
+- *)
+- MOZ_ENABLE_PROFILER_SPS=
+- esac
+- ;;
+-Linux)
+- case "${CPU_ARCH}" in
+- x86 | x86_64) ;;
+- *)
+- MOZ_ENABLE_PROFILER_SPS=
+- esac
+- ;;
+-WINNT|Darwin) ;;
+-*)
+- MOZ_ENABLE_PROFILER_SPS=
+- ;;
+-esac
+-
+-if test -n "$MOZ_ENABLE_PROFILER_SPS"; then
+- cat >> confdefs.pytmp <<\EOF
+- (''' MOZ_ENABLE_PROFILER_SPS ''', ' 1 ')
+-EOF
+-cat >> confdefs.h <<\EOF
+-#define MOZ_ENABLE_PROFILER_SPS 1
+-EOF
+-
-fi
- if test "$GNU_CC"; then
- if test -z "$DEVELOPER_OPTIONS"; then
+ # Check whether --enable-shark or --disable-shark was given.
+ if test "${enable_shark+set}" = set; then
diff --git a/package/firefox/patches/patch-gfx_angle_src_common_angleutils_cpp b/package/firefox/patches/patch-gfx_angle_src_common_angleutils_cpp
new file mode 100644
index 000000000..bcf9ac30a
--- /dev/null
+++ b/package/firefox/patches/patch-gfx_angle_src_common_angleutils_cpp
@@ -0,0 +1,10 @@
+--- mozilla-release.orig/gfx/angle/src/common/angleutils.cpp 2015-01-09 05:38:28.000000000 +0100
++++ mozilla-release/gfx/angle/src/common/angleutils.cpp 2015-02-03 04:42:10.000000000 +0100
+@@ -7,6 +7,7 @@
+ #include "common/angleutils.h"
+
+ #include <vector>
++#include <cstdio>
+
+ std::string FormatString(const char *fmt, va_list vararg)
+ {
diff --git a/package/firefox/patches/patch-gfx_layers_BufferUnrotate_cpp b/package/firefox/patches/patch-gfx_layers_BufferUnrotate_cpp
deleted file mode 100644
index 0a96d2259..000000000
--- a/package/firefox/patches/patch-gfx_layers_BufferUnrotate_cpp
+++ /dev/null
@@ -1,10 +0,0 @@
---- mozilla-release.orig/gfx/layers/BufferUnrotate.cpp 2013-12-05 17:07:31.000000000 +0100
-+++ mozilla-release/gfx/layers/BufferUnrotate.cpp 2014-01-06 21:27:39.000000000 +0100
-@@ -8,6 +8,7 @@
- #include <stdint.h>
- #include <stdio.h>
- #include <stdlib.h>
-+#include <string.h>
-
- void BufferUnrotate(uint8_t* aBuffer, int aByteWidth, int aHeight,
- int aByteStride, int aXBoundary, int aYBoundary)
diff --git a/package/firefox/patches/patch-ipc_chromium_src_base_debug_util_posix_cc b/package/firefox/patches/patch-ipc_chromium_src_base_debug_util_posix_cc
deleted file mode 100644
index 8537bed9a..000000000
--- a/package/firefox/patches/patch-ipc_chromium_src_base_debug_util_posix_cc
+++ /dev/null
@@ -1,13 +0,0 @@
---- mozilla-release.orig/ipc/chromium/src/base/debug_util_posix.cc 2013-09-11 01:15:04.000000000 +0200
-+++ mozilla-release/ipc/chromium/src/base/debug_util_posix.cc 2013-10-23 16:28:38.000000000 +0200
-@@ -5,7 +5,9 @@
- #include "build/build_config.h"
- #include "base/debug_util.h"
-
--#define MOZ_HAVE_EXECINFO_H (defined(OS_LINUX) && !defined(ANDROID))
-+#include <features.h>
-+
-+#define MOZ_HAVE_EXECINFO_H (defined(OS_LINUX) && !defined(ANDROID) && !defined(__UCLIBC__)) && defined(__GLIBC__)
-
- #include <errno.h>
- #include <fcntl.h>
diff --git a/package/firefox/patches/patch-ipc_chromium_src_base_file_util_h b/package/firefox/patches/patch-ipc_chromium_src_base_file_util_h
deleted file mode 100644
index 5f7e30a10..000000000
--- a/package/firefox/patches/patch-ipc_chromium_src_base_file_util_h
+++ /dev/null
@@ -1,10 +0,0 @@
---- mozilla-release.orig/ipc/chromium/src/base/file_util.h 2013-12-05 17:07:35.000000000 +0100
-+++ mozilla-release/ipc/chromium/src/base/file_util.h 2014-01-02 15:01:42.000000000 +0100
-@@ -16,7 +16,6 @@
- #include <sys/stat.h>
- #elif defined(OS_POSIX)
- #include <sys/types.h>
--#include <fts.h>
- #include <sys/stat.h>
- #endif
-
diff --git a/package/firefox/patches/patch-ipc_chromium_src_base_file_util_posix_cc b/package/firefox/patches/patch-ipc_chromium_src_base_file_util_posix_cc
deleted file mode 100644
index 7680a29c4..000000000
--- a/package/firefox/patches/patch-ipc_chromium_src_base_file_util_posix_cc
+++ /dev/null
@@ -1,48 +0,0 @@
---- mozilla-release.orig/ipc/chromium/src/base/file_util_posix.cc 2013-12-05 17:07:35.000000000 +0100
-+++ mozilla-release/ipc/chromium/src/base/file_util_posix.cc 2014-01-02 14:53:44.000000000 +0100
-@@ -8,13 +8,16 @@
- #include <errno.h>
- #include <fcntl.h>
- #include <fnmatch.h>
--#ifndef ANDROID
-+#ifndef __GLIBC__
-+#define NO_FTS
-+#endif
-+#ifndef NO_FTS
- #include <fts.h>
- #endif
- #include <libgen.h>
- #include <stdio.h>
- #include <string.h>
--#include <sys/errno.h>
-+#include <errno.h>
- #include <sys/mman.h>
- #define _DARWIN_USE_64_BIT_INODE // Use 64-bit inode data structures
- #include <sys/stat.h>
-@@ -67,7 +70,7 @@ bool Delete(const FilePath& path, bool r
- if (!recursive)
- return (rmdir(path_str) == 0);
-
--#ifdef ANDROID
-+#ifdef NO_FTS
- // XXX Need ftsless impl for bionic
- return false;
- #else
-@@ -140,7 +143,7 @@ bool CopyDirectory(const FilePath& from_
- return false;
- }
-
--#ifdef ANDROID
-+#ifdef NO_FTS
- // XXX Need ftsless impl for bionic
- return false;
- #else
-@@ -333,7 +336,7 @@ bool CreateNewTempDirectory(const FilePa
- return false;
- tmpdir = tmpdir.Append(kTempFileName);
- std::string tmpdir_string = tmpdir.value();
--#ifdef ANDROID
-+#ifdef NO_FTS
- char* dtemp = NULL;
- #else
- // this should be OK since mkdtemp just replaces characters in place
diff --git a/package/firefox/patches/patch-js_src_Makefile_in b/package/firefox/patches/patch-js_src_Makefile_in
index d4acee98c..b536ab3f5 100644
--- a/package/firefox/patches/patch-js_src_Makefile_in
+++ b/package/firefox/patches/patch-js_src_Makefile_in
@@ -1,11 +1,11 @@
---- mozilla-release.orig/js/src/Makefile.in 2013-12-05 17:07:35.000000000 +0100
-+++ mozilla-release/js/src/Makefile.in 2014-01-02 14:53:44.000000000 +0100
-@@ -103,7 +103,7 @@ ifdef JS_HAS_CTYPES
- VPATH += $(srcdir)/ctypes
+--- mozilla-release.orig/js/src/Makefile.in 2015-01-09 05:38:17.000000000 +0100
++++ mozilla-release/js/src/Makefile.in 2015-01-29 17:03:28.000000000 +0100
+@@ -21,7 +21,7 @@ NO_EXPAND_LIBS = 1
+ ifdef JS_HAS_CTYPES
ifdef MOZ_NATIVE_FFI
-LOCAL_INCLUDES = $(MOZ_FFI_CFLAGS)
-+LOCAL_INCLUDES =
- else
- LOCAL_INCLUDES = -Ictypes/libffi/include
++LOCAL_INCLUDES =
endif
+
+ # Windows needs this to be linked with a static library.
diff --git a/package/firefox/patches/patch-js_src_assembler_wtf_Platform_h b/package/firefox/patches/patch-js_src_assembler_wtf_Platform_h
deleted file mode 100644
index 68a7adf0a..000000000
--- a/package/firefox/patches/patch-js_src_assembler_wtf_Platform_h
+++ /dev/null
@@ -1,12 +0,0 @@
---- mozilla-release.orig/js/src/assembler/wtf/Platform.h 2013-09-11 01:15:04.000000000 +0200
-+++ mozilla-release/js/src/assembler/wtf/Platform.h 2013-10-28 12:43:50.000000000 +0100
-@@ -139,8 +139,7 @@
-
- /* WTF_CPU_MIPS - MIPS 32-bit */
- /* Note: Only O32 ABI is tested, so we enable it for O32 ABI for now. */
--#if (defined(mips) || defined(__mips__) || defined(MIPS) || defined(_MIPS_)) \
-- && defined(_ABIO32)
-+#if (defined(mips) || defined(__mips__) || defined(MIPS) || defined(_MIPS_))
- #define WTF_CPU_MIPS 1
- #if defined(__MIPSEB__)
- #define WTF_CPU_BIG_ENDIAN 1
diff --git a/package/firefox/patches/patch-js_src_configure b/package/firefox/patches/patch-js_src_configure
deleted file mode 100644
index c37f501e4..000000000
--- a/package/firefox/patches/patch-js_src_configure
+++ /dev/null
@@ -1,31 +0,0 @@
---- mozilla-release.orig/js/src/configure 2013-12-05 17:08:46.000000000 +0100
-+++ mozilla-release/js/src/configure 2014-01-07 19:30:38.660353287 +0100
-@@ -8652,28 +8652,6 @@ if test -z "$GNU_CC"; then
- esac
- fi
-
--if test "$GNU_CC" -a -n "$DEVELOPER_OPTIONS"; then
-- if $CC -Wl,--version 2>&1 | grep -q "GNU ld"; then
-- GOLD=$($CC -print-prog-name=ld.gold)
-- case "$GOLD" in
-- /*)
-- ;;
-- *)
-- GOLD=$(which $GOLD)
-- ;;
-- esac
-- if test -n "$GOLD"; then
-- mkdir -p $_objdir/build/unix/gold
-- ln -s "$GOLD" $_objdir/build/unix/gold/ld
-- if $CC -B $_objdir/build/unix/gold -Wl,--version 2>&1 | grep -q "GNU gold"; then
-- LDFLAGS="$LDFLAGS -B $_objdir/build/unix/gold"
-- else
-- rm -rf $_objdir/build/unix/gold
-- fi
-- fi
-- fi
--fi
--
- if test "$GNU_CC"; then
- if test -z "$DEVELOPER_OPTIONS"; then
- CFLAGS="$CFLAGS -ffunction-sections -fdata-sections"
diff --git a/package/firefox/patches/patch-js_src_yarr_BumpPointerAllocator_h b/package/firefox/patches/patch-js_src_yarr_BumpPointerAllocator_h
deleted file mode 100644
index 1697dfddd..000000000
--- a/package/firefox/patches/patch-js_src_yarr_BumpPointerAllocator_h
+++ /dev/null
@@ -1,11 +0,0 @@
---- mozilla-release.orig/js/src/yarr/BumpPointerAllocator.h 2013-09-11 01:15:09.000000000 +0200
-+++ mozilla-release/js/src/yarr/BumpPointerAllocator.h 2013-10-28 12:44:10.000000000 +0100
-@@ -38,6 +38,8 @@ namespace WTF {
- #define MINIMUM_BUMP_POOL_SIZE 0x2000
- #elif WTF_CPU_IA64
- #define MINIMUM_BUMP_POOL_SIZE 0x4000
-+#elif WTF_CPU_MIPS
-+#define MINIMUM_BUMP_POOL_SIZE 0x4000
- #else
- #define MINIMUM_BUMP_POOL_SIZE 0x1000
- #endif
diff --git a/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c b/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c
deleted file mode 100644
index f2b55cd6a..000000000
--- a/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c
+++ /dev/null
@@ -1,43 +0,0 @@
---- mozilla-release.orig/media/mtransport/third_party/nICEr/src/stun/addrs.c 2013-12-05 17:07:48.000000000 +0100
-+++ mozilla-release/media/mtransport/third_party/nICEr/src/stun/addrs.c 2014-03-16 18:41:03.000000000 +0100
-@@ -45,7 +45,9 @@ static char *RCSSTRING __UNUSED__="$Id:
- #include <sys/param.h>
- #include <sys/socket.h>
- #ifndef ANDROID
-+#ifdef __GLIBC__
- #include <sys/sysctl.h>
-+#endif
- #include <sys/syslog.h>
- #else
- #include <syslog.h>
-@@ -53,7 +55,9 @@ static char *RCSSTRING __UNUSED__="$Id:
- #undef __unused
- #include <linux/sysctl.h>
- #endif
-+#if defined(__GLIBC__)
- #include <net/if.h>
-+#endif
- #ifndef LINUX
- #if !defined(__OpenBSD__) && !defined(__NetBSD__)
- #include <net/if_var.h>
-@@ -61,14 +65,17 @@ static char *RCSSTRING __UNUSED__="$Id:
- #include <net/if_dl.h>
- #include <net/if_types.h>
- #include <sys/sockio.h>
--#else
-+#elif defined(__GLIBC__)
- #include <linux/sockios.h>
- #include <linux/if.h>
- #include <linux/kernel.h>
- #include <linux/wireless.h>
--#ifndef ANDROID
- #include <linux/ethtool.h>
--#endif
-+#else
-+#include <linux/sockios.h>
-+#include <linux/kernel.h>
-+#include <linux/wireless.h>
-+#include <linux/ethtool.h>
- #endif
- #include <net/route.h>
-
diff --git a/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_stun_h b/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_stun_h
deleted file mode 100644
index 7877d65cc..000000000
--- a/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_stun_h
+++ /dev/null
@@ -1,12 +0,0 @@
---- mozilla-release.orig/media/mtransport/third_party/nICEr/src/stun/stun.h 2013-12-05 17:07:48.000000000 +0100
-+++ mozilla-release/media/mtransport/third_party/nICEr/src/stun/stun.h 2014-01-03 17:19:05.000000000 +0100
-@@ -39,7 +39,9 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- #else
- #include <sys/param.h>
- #include <sys/socket.h>
-+#if defined(__GLIBC__)
- #include <net/if.h>
-+#endif
- #ifndef LINUX
- #if !defined(__OpenBSD__) && !defined(__NetBSD__)
- #include <net/if_var.h>
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py
deleted file mode 100644
index 60d33bb2e..000000000
--- a/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py
+++ /dev/null
@@ -1,23 +0,0 @@
---- mozilla-release.orig/media/webrtc/trunk/tools/gyp/pylib/gyp/common.py 2013-12-05 17:07:48.000000000 +0100
-+++ mozilla-release/media/webrtc/trunk/tools/gyp/pylib/gyp/common.py 2014-02-05 08:12:49.000000000 +0100
-@@ -364,20 +364,6 @@ def WriteOnDiff(filename):
-
- def GetFlavor(params):
- """Returns |params.flavor| if it's set, the system's default flavor else."""
-- flavors = {
-- 'cygwin': 'win',
-- 'win32': 'win',
-- 'darwin': 'mac',
-- }
--
-- if 'flavor' in params:
-- return params['flavor']
-- if sys.platform in flavors:
-- return flavors[sys.platform]
-- if sys.platform.startswith('sunos'):
-- return 'solaris'
-- if sys.platform.startswith('freebsd'):
-- return 'freebsd'
-
- return 'linux'
-
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py
deleted file mode 100644
index 452d380f0..000000000
--- a/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py
+++ /dev/null
@@ -1,26 +0,0 @@
---- mozilla-release.orig/media/webrtc/trunk/tools/gyp/pylib/gyp/generator/mozmake.py 2013-12-05 17:07:48.000000000 +0100
-+++ mozilla-release/media/webrtc/trunk/tools/gyp/pylib/gyp/generator/mozmake.py 2014-02-05 08:13:30.000000000 +0100
-@@ -118,23 +118,6 @@ def ensure_directory_exists(path):
-
- def GetFlavor(params):
- """Returns |params.flavor| if it's set, the system's default flavor else."""
-- system = platform.system().lower()
-- flavors = {
-- 'microsoft': 'win',
-- 'windows' : 'win',
-- 'cygwin' : 'win',
-- 'darwin' : 'mac',
-- 'sunos' : 'solaris',
-- 'dragonfly': 'dragonfly',
-- 'freebsd' : 'freebsd',
-- 'netbsd' : 'netbsd',
-- 'openbsd' : 'openbsd',
-- }
--
-- if 'flavor' in params:
-- return params['flavor']
-- if system in flavors:
-- return flavors[system]
-
- return 'linux'
-
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_audio_device_impl_cc b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_audio_device_impl_cc
deleted file mode 100644
index 0ef4e5714..000000000
--- a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_audio_device_impl_cc
+++ /dev/null
@@ -1,11 +0,0 @@
---- mozilla-release.orig/media/webrtc/trunk/webrtc/modules/audio_device/audio_device_impl.cc 2013-09-11 01:15:17.000000000 +0200
-+++ mozilla-release/media/webrtc/trunk/webrtc/modules/audio_device/audio_device_impl.cc 2013-10-23 16:28:38.000000000 +0200
-@@ -8,6 +8,8 @@
- * be found in the AUTHORS file in the root of the source tree.
- */
-
-+#define _POSIX_SOURCE
-+
- #include "audio_device_impl.h"
- #include "audio_device_config.h"
- #include "common_audio/signal_processing/include/signal_processing_library.h"
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_linux_audio_device_alsa_linux_cc b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_linux_audio_device_alsa_linux_cc
deleted file mode 100644
index a5fd50511..000000000
--- a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_linux_audio_device_alsa_linux_cc
+++ /dev/null
@@ -1,11 +0,0 @@
---- mozilla-release.orig/media/webrtc/trunk/webrtc/modules/audio_device/linux/audio_device_alsa_linux.cc 2013-09-11 01:15:17.000000000 +0200
-+++ mozilla-release/media/webrtc/trunk/webrtc/modules/audio_device/linux/audio_device_alsa_linux.cc 2013-10-23 16:28:38.000000000 +0200
-@@ -8,6 +8,8 @@
- * be found in the AUTHORS file in the root of the source tree.
- */
-
-+#define _POSIX_SOURCE
-+
- #include <cassert>
-
- #include "audio_device_utility.h"
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_linux_audio_mixer_manager_alsa_linux_cc b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_linux_audio_mixer_manager_alsa_linux_cc
deleted file mode 100644
index 2544d6c08..000000000
--- a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_modules_audio_device_linux_audio_mixer_manager_alsa_linux_cc
+++ /dev/null
@@ -1,11 +0,0 @@
---- mozilla-release.orig/media/webrtc/trunk/webrtc/modules/audio_device/linux/audio_mixer_manager_alsa_linux.cc 2013-09-11 01:15:17.000000000 +0200
-+++ mozilla-release/media/webrtc/trunk/webrtc/modules/audio_device/linux/audio_mixer_manager_alsa_linux.cc 2013-10-23 16:28:38.000000000 +0200
-@@ -8,6 +8,8 @@
- * be found in the AUTHORS file in the root of the source tree.
- */
-
-+#define _POSIX_SOURCE
-+
- #include <cassert>
-
- #include "audio_mixer_manager_alsa_linux.h"
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc
deleted file mode 100644
index 5e066a88a..000000000
--- a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc
+++ /dev/null
@@ -1,23 +0,0 @@
---- mozilla-release.orig/media/webrtc/trunk/webrtc/system_wrappers/source/cpu_info.cc 2013-12-05 17:07:50.000000000 +0100
-+++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/cpu_info.cc 2014-03-16 10:56:09.000000000 +0100
-@@ -36,11 +36,6 @@ uint32_t CpuInfo::DetectNumberOfCores()
- WEBRTC_TRACE(kTraceStateInfo, kTraceUtility, -1,
- "Available number of cores:%d", number_of_cores_);
-
--#elif defined(WEBRTC_LINUX) && !defined(WEBRTC_ANDROID) && !defined(WEBRTC_GONK)
-- number_of_cores_ = static_cast<uint32_t>(sysconf(_SC_NPROCESSORS_ONLN));
-- WEBRTC_TRACE(kTraceStateInfo, kTraceUtility, -1,
-- "Available number of cores:%d", number_of_cores_);
--
- #elif defined(WEBRTC_BSD) || defined(WEBRTC_MAC)
- int name[] = {
- CTL_HW,
-@@ -61,8 +56,6 @@ uint32_t CpuInfo::DetectNumberOfCores()
- "Failed to get number of cores");
- number_of_cores_ = 1;
- }
--#elif defined(_SC_NPROCESSORS_ONLN)
-- number_of_cores_ = sysconf(_SC_NPROCESSORS_ONLN);
- #else
- WEBRTC_TRACE(kTraceWarning, kTraceUtility, -1,
- "No function to get number of cores");
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp
deleted file mode 100644
index 95cfd56ba..000000000
--- a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp
+++ /dev/null
@@ -1,3385 +0,0 @@
---- mozilla-release.orig/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp 2013-12-05 17:07:50.000000000 +0100
-+++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp 2014-02-05 09:52:11.000000000 +0100
-@@ -1,1688 +1,1694 @@
--//Templated spread_sort library
--
--// Copyright Steven J. Ross 2001 - 2009.
--// Distributed under the Boost Software License, Version 1.0.
--// (See accompanying file LICENSE_1_0.txt or copy at
--// http://www.boost.org/LICENSE_1_0.txt)
--
--// See http://www.boost.org/ for updates, documentation, and revision history.
--
--/*
--Some improvements suggested by:
--Phil Endecott and Frank Gennari
--Cygwin fix provided by:
--Scott McMurray
--*/
--
--#ifndef BOOST_SPREAD_SORT_H
--#define BOOST_SPREAD_SORT_H
--#include <algorithm>
--#include <cstring>
--#include <vector>
--#include "webrtc/system_wrappers/source/spreadsortlib/constants.hpp"
--
--namespace boost {
-- namespace detail {
-- //This only works on unsigned data types
-- template <typename T>
-- inline unsigned
-- rough_log_2_size(const T& input)
-- {
-- unsigned result = 0;
-- //The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance
-- while((input >> result) && (result < (8*sizeof(T)))) ++result;
-- return result;
-- }
--
-- //Gets the maximum size which we'll call spread_sort on to control worst-case performance
-- //Maintains both a minimum size to recurse and a check of distribution size versus count
-- //This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead
-- inline size_t
-- get_max_count(unsigned log_range, size_t count)
-- {
-- unsigned divisor = rough_log_2_size(count);
-- //Making sure the divisor is positive
-- if(divisor > LOG_MEAN_BIN_SIZE)
-- divisor -= LOG_MEAN_BIN_SIZE;
-- else
-- divisor = 1;
-- unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor);
-- //Don't try to bitshift more than the size of an element
-- if((8*sizeof(size_t)) <= relative_width)
-- relative_width = (8*sizeof(size_t)) - 1;
-- return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ?
-- (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) : relative_width);
-- }
--
-- //Find the minimum and maximum using <
-- template <class RandomAccessIter>
-- inline void
-- find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min)
-- {
-- min = max = current;
-- //Start from the second item, as max and min are initialized to the first
-- while(++current < last) {
-- if(*max < *current)
-- max = current;
-- else if(*current < *min)
-- min = current;
-- }
-- }
--
-- //Uses a user-defined comparison operator to find minimum and maximum
-- template <class RandomAccessIter, class compare>
-- inline void
-- find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp)
-- {
-- min = max = current;
-- while(++current < last) {
-- if(comp(*max, *current))
-- max = current;
-- else if(comp(*current, *min))
-- min = current;
-- }
-- }
--
-- //Gets a non-negative right bit shift to operate as a logarithmic divisor
-- inline int
-- get_log_divisor(size_t count, unsigned log_range)
-- {
-- int log_divisor;
-- //If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so
-- if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS)
-- log_divisor = 0;
-- else {
-- //otherwise divide the data into an optimized number of pieces
-- log_divisor += LOG_MEAN_BIN_SIZE;
-- if(log_divisor < 0)
-- log_divisor = 0;
-- //Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically
-- if((log_range - log_divisor) > MAX_SPLITS)
-- log_divisor = log_range - MAX_SPLITS;
-- }
-- return log_divisor;
-- }
--
-- template <class RandomAccessIter>
-- inline RandomAccessIter *
-- size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
-- {
-- //Assure space for the size of each bin, followed by initializing sizes
-- if(bin_count > bin_sizes.size())
-- bin_sizes.resize(bin_count);
-- for(size_t u = 0; u < bin_count; u++)
-- bin_sizes[u] = 0;
-- //Make sure there is space for the bins
-- cache_end = cache_offset + bin_count;
-- if(cache_end > bin_cache.size())
-- bin_cache.resize(cache_end);
-- return &(bin_cache[cache_offset]);
-- }
--
-- //Implementation for recursive integer sorting
-- template <class RandomAccessIter, class div_type, class data_type>
-- inline void
-- spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-- , std::vector<size_t> &bin_sizes)
-- {
-- //This step is roughly 10% of runtime, but it helps avoid worst-case behavior and improve behavior with real data
-- //If you know the maximum and minimum ahead of time, you can pass those values in and skip this step for the first iteration
-- RandomAccessIter max, min;
-- find_extremes(first, last, max, min);
-- //max and min will be the same (the first item) iff all values are equivalent
-- if(max == min)
-- return;
-- RandomAccessIter * target_bin;
-- unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0)));
-- div_type div_min = *min >> log_divisor;
-- div_type div_max = *max >> log_divisor;
-- unsigned bin_count = div_max - div_min + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
--
-- //Calculating the size of each bin; this takes roughly 10% of runtime
-- for (RandomAccessIter current = first; current != last;)
-- bin_sizes[(*(current++) >> log_divisor) - div_min]++;
-- //Assign the bin positions
-- bins[0] = first;
-- for(unsigned u = 0; u < bin_count - 1; u++)
-- bins[u + 1] = bins[u] + bin_sizes[u];
--
-- //Swap into place
-- //This dominates runtime, mostly in the swap and bin lookups
-- RandomAccessIter nextbinstart = first;
-- for(unsigned u = 0; u < bin_count - 1; ++u) {
-- RandomAccessIter * local_bin = bins + u;
-- nextbinstart += bin_sizes[u];
-- //Iterating over each element in this bin
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //Swapping elements in current into place until the correct element has been swapped in
-- for(target_bin = (bins + ((*current >> log_divisor) - div_min)); target_bin != local_bin;
-- target_bin = bins + ((*current >> log_divisor) - div_min)) {
-- //3-way swap; this is about 1% faster than a 2-way swap with integers
-- //The main advantage is less copies are involved per item put in the correct place
-- data_type tmp;
-- RandomAccessIter b = (*target_bin)++;
-- RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);
-- if (b_bin != local_bin) {
-- RandomAccessIter c = (*b_bin)++;
-- tmp = *c;
-- *c = *b;
-- }
-- else
-- tmp = *b;
-- *b = *current;
-- *current = tmp;
-- }
-- }
-- *local_bin = nextbinstart;
-- }
-- bins[bin_count - 1] = last;
--
-- //If we've bucketsorted, the array is sorted and we should skip recursion
-- if(!log_divisor)
-- return;
--
-- //Recursing; log_divisor is the remaining range
-- size_t max_count = get_max_count(log_divisor, last - first);
-- RandomAccessIter lastPos = first;
-- for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- //don't sort unless there are at least two items to compare
-- if(count < 2)
-- continue;
-- //using std::sort if its worst-case is better
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[u]);
-- else
-- spread_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
-- }
-- }
--
-- //Generic bitshift-based 3-way swapping code
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-- inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
-- , const unsigned log_divisor, const div_type div_min)
-- {
-- RandomAccessIter * local_bin = bins + ii;
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min)); target_bin != local_bin;
-- target_bin = bins + (shift(*current, log_divisor) - div_min)) {
-- data_type tmp;
-- RandomAccessIter b = (*target_bin)++;
-- RandomAccessIter * b_bin = bins + (shift(*b, log_divisor) - div_min);
-- //Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
-- if (b_bin != local_bin) {
-- RandomAccessIter c = (*b_bin)++;
-- tmp = *c;
-- *c = *b;
-- }
-- //Note: we could increment current once the swap is done in this case, but that seems to impair performance
-- else
-- tmp = *b;
-- *b = *current;
-- *current = tmp;
-- }
-- }
-- *local_bin = nextbinstart;
-- }
--
-- //Standard swapping wrapper for ascending values
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-- inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
-- , const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min)
-- {
-- nextbinstart += bin_sizes[ii];
-- inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min);
-- }
--
-- //Functor implementation for recursive sorting
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-- inline void
-- spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-- , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
-- {
-- RandomAccessIter max, min;
-- find_extremes(first, last, max, min, comp);
-- if(max == min)
-- return;
-- unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
-- div_type div_min = shift(*min, log_divisor);
-- div_type div_max = shift(*max, log_divisor);
-- unsigned bin_count = div_max - div_min + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
--
-- //Calculating the size of each bin
-- for (RandomAccessIter current = first; current != last;)
-- bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-- bins[0] = first;
-- for(unsigned u = 0; u < bin_count - 1; u++)
-- bins[u + 1] = bins[u] + bin_sizes[u];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- for(unsigned u = 0; u < bin_count - 1; ++u)
-- swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);
-- bins[bin_count - 1] = last;
--
-- //If we've bucketsorted, the array is sorted and we should skip recursion
-- if(!log_divisor)
-- return;
--
-- //Recursing
-- size_t max_count = get_max_count(log_divisor, last - first);
-- RandomAccessIter lastPos = first;
-- for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[u], comp);
-- else
-- spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
-- }
-- }
--
-- //Functor implementation for recursive sorting with only Shift overridden
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-- inline void
-- spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-- , std::vector<size_t> &bin_sizes, right_shift shift)
-- {
-- RandomAccessIter max, min;
-- find_extremes(first, last, max, min);
-- if(max == min)
-- return;
-- unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
-- div_type div_min = shift(*min, log_divisor);
-- div_type div_max = shift(*max, log_divisor);
-- unsigned bin_count = div_max - div_min + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
--
-- //Calculating the size of each bin
-- for (RandomAccessIter current = first; current != last;)
-- bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-- bins[0] = first;
-- for(unsigned u = 0; u < bin_count - 1; u++)
-- bins[u + 1] = bins[u] + bin_sizes[u];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- for(unsigned ii = 0; ii < bin_count - 1; ++ii)
-- swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
-- bins[bin_count - 1] = last;
--
-- //If we've bucketsorted, the array is sorted and we should skip recursion
-- if(!log_divisor)
-- return;
--
-- //Recursing
-- size_t max_count = get_max_count(log_divisor, last - first);
-- RandomAccessIter lastPos = first;
-- for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[u]);
-- else
-- spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
-- }
-- }
--
-- //Holds the bin vector and makes the initial recursive call
-- template <class RandomAccessIter, class div_type, class data_type>
-- inline void
-- spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes);
-- }
--
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-- inline void
-- spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);
-- }
--
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-- inline void
-- spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
-- }
-- }
--
-- //Top-level sorting call for integers
-- template <class RandomAccessIter>
-- inline void integer_sort(RandomAccessIter first, RandomAccessIter last)
-- {
-- //Don't sort if it's too small to optimize
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last);
-- else
-- detail::spread_sort(first, last, *first >> 0, *first);
-- }
--
-- //integer_sort with functors
-- template <class RandomAccessIter, class right_shift, class compare>
-- inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
-- right_shift shift, compare comp) {
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last, comp);
-- else
-- detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp);
-- }
--
-- //integer_sort with right_shift functor
-- template <class RandomAccessIter, class right_shift>
-- inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
-- right_shift shift) {
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last);
-- else
-- detail::spread_sort(first, last, shift(*first, 0), *first, shift);
-- }
--
-- //------------------------------------------------------ float_sort source --------------------------------------
-- //Casts a RandomAccessIter to the specified data type
-- template<class cast_type, class RandomAccessIter>
-- inline cast_type
-- cast_float_iter(const RandomAccessIter & floatiter)
-- {
-- cast_type result;
-- std::memcpy(&result, &(*floatiter), sizeof(cast_type));
-- return result;
-- }
--
-- //Casts a data element to the specified datinner_float_a type
-- template<class data_type, class cast_type>
-- inline cast_type
-- mem_cast(const data_type & data)
-- {
-- cast_type result;
-- std::memcpy(&result, &data, sizeof(cast_type));
-- return result;
-- }
--
-- namespace detail {
-- template <class RandomAccessIter, class div_type, class right_shift>
-- inline void
-- find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)
-- {
-- min = max = shift(*current, 0);
-- while(++current < last) {
-- div_type value = shift(*current, 0);
-- if(max < value)
-- max = value;
-- else if(value < min)
-- min = value;
-- }
-- }
--
-- //Specialized swap loops for floating-point casting
-- template <class RandomAccessIter, class div_type, class data_type>
-- inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii
-- , const unsigned log_divisor, const div_type div_min)
-- {
-- RandomAccessIter * local_bin = bins + ii;
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)); target_bin != local_bin;
-- target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {
-- data_type tmp;
-- RandomAccessIter b = (*target_bin)++;
-- RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min);
-- //Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
-- if (b_bin != local_bin) {
-- RandomAccessIter c = (*b_bin)++;
-- tmp = *c;
-- *c = *b;
-- }
-- else
-- tmp = *b;
-- *b = *current;
-- *current = tmp;
-- }
-- }
-- *local_bin = nextbinstart;
-- }
--
-- template <class RandomAccessIter, class div_type, class data_type>
-- inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii
-- , const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min)
-- {
-- nextbinstart += bin_sizes[ii];
-- inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min);
-- }
--
-- template <class RandomAccessIter, class cast_type>
-- inline void
-- find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)
-- {
-- min = max = cast_float_iter<cast_type, RandomAccessIter>(current);
-- while(++current < last) {
-- cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current);
-- if(max < value)
-- max = value;
-- else if(value < min)
-- min = value;
-- }
-- }
--
-- //Special-case sorting of positive floats with casting instead of a right_shift
-- template <class RandomAccessIter, class div_type, class data_type>
-- inline void
-- positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-- , std::vector<size_t> &bin_sizes)
-- {
-- div_type max, min;
-- find_extremes(first, last, max, min);
-- if(max == min)
-- return;
-- unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-- div_type div_min = min >> log_divisor;
-- div_type div_max = max >> log_divisor;
-- unsigned bin_count = div_max - div_min + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
--
-- //Calculating the size of each bin
-- for (RandomAccessIter current = first; current != last;)
-- bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
-- bins[0] = first;
-- for(unsigned u = 0; u < bin_count - 1; u++)
-- bins[u + 1] = bins[u] + bin_sizes[u];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- for(unsigned u = 0; u < bin_count - 1; ++u)
-- float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
-- bins[bin_count - 1] = last;
--
-- //Return if we've completed bucketsorting
-- if(!log_divisor)
-- return;
--
-- //Recursing
-- size_t max_count = get_max_count(log_divisor, last - first);
-- RandomAccessIter lastPos = first;
-- for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[u]);
-- else
-- positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
-- }
-- }
--
-- //Sorting negative_ float_s
-- //Note that bins are iterated in reverse order because max_neg_float = min_neg_int
-- template <class RandomAccessIter, class div_type, class data_type>
-- inline void
-- negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-- , std::vector<size_t> &bin_sizes)
-- {
-- div_type max, min;
-- find_extremes(first, last, max, min);
-- if(max == min)
-- return;
-- unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-- div_type div_min = min >> log_divisor;
-- div_type div_max = max >> log_divisor;
-- unsigned bin_count = div_max - div_min + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
--
-- //Calculating the size of each bin
-- for (RandomAccessIter current = first; current != last;)
-- bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
-- bins[bin_count - 1] = first;
-- for(int ii = bin_count - 2; ii >= 0; --ii)
-- bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- //The last bin will always have the correct elements in it
-- for(int ii = bin_count - 1; ii > 0; --ii)
-- float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
-- //Since we don't process the last bin, we need to update its end position
-- bin_cache[cache_offset] = last;
--
-- //Return if we've completed bucketsorting
-- if(!log_divisor)
-- return;
--
-- //Recursing
-- size_t max_count = get_max_count(log_divisor, last - first);
-- RandomAccessIter lastPos = first;
-- for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
-- size_t count = bin_cache[ii] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[ii]);
-- else
-- negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
-- }
-- }
--
-- //Sorting negative_ float_s
-- //Note that bins are iterated in reverse order because max_neg_float = min_neg_int
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-- inline void
-- negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-- , std::vector<size_t> &bin_sizes, right_shift shift)
-- {
-- div_type max, min;
-- find_extremes(first, last, max, min, shift);
-- if(max == min)
-- return;
-- unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-- div_type div_min = min >> log_divisor;
-- div_type div_max = max >> log_divisor;
-- unsigned bin_count = div_max - div_min + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
--
-- //Calculating the size of each bin
-- for (RandomAccessIter current = first; current != last;)
-- bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-- bins[bin_count - 1] = first;
-- for(int ii = bin_count - 2; ii >= 0; --ii)
-- bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- //The last bin will always have the correct elements in it
-- for(int ii = bin_count - 1; ii > 0; --ii)
-- swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
-- //Since we don't process the last bin, we need to update its end position
-- bin_cache[cache_offset] = last;
--
-- //Return if we've completed bucketsorting
-- if(!log_divisor)
-- return;
--
-- //Recursing
-- size_t max_count = get_max_count(log_divisor, last - first);
-- RandomAccessIter lastPos = first;
-- for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
-- size_t count = bin_cache[ii] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[ii]);
-- else
-- negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
-- }
-- }
--
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-- inline void
-- negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-- , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
-- {
-- div_type max, min;
-- find_extremes(first, last, max, min, shift);
-- if(max == min)
-- return;
-- unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-- div_type div_min = min >> log_divisor;
-- div_type div_max = max >> log_divisor;
-- unsigned bin_count = div_max - div_min + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
--
-- //Calculating the size of each bin
-- for (RandomAccessIter current = first; current != last;)
-- bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-- bins[bin_count - 1] = first;
-- for(int ii = bin_count - 2; ii >= 0; --ii)
-- bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- //The last bin will always have the correct elements in it
-- for(int ii = bin_count - 1; ii > 0; --ii)
-- swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
-- //Since we don't process the last bin, we need to update its end position
-- bin_cache[cache_offset] = last;
--
-- //Return if we've completed bucketsorting
-- if(!log_divisor)
-- return;
--
-- //Recursing
-- size_t max_count = get_max_count(log_divisor, last - first);
-- RandomAccessIter lastPos = first;
-- for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
-- size_t count = bin_cache[ii] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[ii], comp);
-- else
-- negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
-- }
-- }
--
-- //Casting special-case for floating-point sorting
-- template <class RandomAccessIter, class div_type, class data_type>
-- inline void
-- float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-- , std::vector<size_t> &bin_sizes)
-- {
-- div_type max, min;
-- find_extremes(first, last, max, min);
-- if(max == min)
-- return;
-- unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-- div_type div_min = min >> log_divisor;
-- div_type div_max = max >> log_divisor;
-- unsigned bin_count = div_max - div_min + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
--
-- //Calculating the size of each bin
-- for (RandomAccessIter current = first; current != last;)
-- bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
-- //The index of the first positive bin
-- div_type first_positive = (div_min < 0) ? -div_min : 0;
-- //Resetting if all bins are negative
-- if(cache_offset + first_positive > cache_end)
-- first_positive = cache_end - cache_offset;
-- //Reversing the order of the negative bins
-- //Note that because of the negative/positive ordering direction flip
-- //We can not depend upon bin order and positions matching up
-- //so bin_sizes must be reused to contain the end of the bin
-- if(first_positive > 0) {
-- bins[first_positive - 1] = first;
-- for(int ii = first_positive - 2; ii >= 0; --ii) {
-- bins[ii] = first + bin_sizes[ii + 1];
-- bin_sizes[ii] += bin_sizes[ii + 1];
-- }
-- //Handling positives following negatives
-- if((unsigned)first_positive < bin_count) {
-- bins[first_positive] = first + bin_sizes[0];
-- bin_sizes[first_positive] += bin_sizes[0];
-- }
-- }
-- else
-- bins[0] = first;
-- for(unsigned u = first_positive; u < bin_count - 1; u++) {
-- bins[u + 1] = first + bin_sizes[u];
-- bin_sizes[u + 1] += bin_sizes[u];
-- }
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- for(unsigned u = 0; u < bin_count; ++u) {
-- nextbinstart = first + bin_sizes[u];
-- inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min);
-- }
--
-- if(!log_divisor)
-- return;
--
-- //Handling negative values first
-- size_t max_count = get_max_count(log_divisor, last - first);
-- RandomAccessIter lastPos = first;
-- for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
-- size_t count = bin_cache[ii] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[ii]);
-- //sort negative values using reversed-bin spread_sort
-- else
-- negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
-- }
--
-- for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[u]);
-- //sort positive values using normal spread_sort
-- else
-- positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
-- }
-- }
--
-- //Functor implementation for recursive sorting
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-- inline void
-- float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-- , std::vector<size_t> &bin_sizes, right_shift shift)
-- {
-- div_type max, min;
-- find_extremes(first, last, max, min, shift);
-- if(max == min)
-- return;
-- unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-- div_type div_min = min >> log_divisor;
-- div_type div_max = max >> log_divisor;
-- unsigned bin_count = div_max - div_min + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
--
-- //Calculating the size of each bin
-- for (RandomAccessIter current = first; current != last;)
-- bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-- //The index of the first positive bin
-- div_type first_positive = (div_min < 0) ? -div_min : 0;
-- //Resetting if all bins are negative
-- if(cache_offset + first_positive > cache_end)
-- first_positive = cache_end - cache_offset;
-- //Reversing the order of the negative bins
-- //Note that because of the negative/positive ordering direction flip
-- //We can not depend upon bin order and positions matching up
-- //so bin_sizes must be reused to contain the end of the bin
-- if(first_positive > 0) {
-- bins[first_positive - 1] = first;
-- for(int ii = first_positive - 2; ii >= 0; --ii) {
-- bins[ii] = first + bin_sizes[ii + 1];
-- bin_sizes[ii] += bin_sizes[ii + 1];
-- }
-- //Handling positives following negatives
-- if((unsigned)first_positive < bin_count) {
-- bins[first_positive] = first + bin_sizes[0];
-- bin_sizes[first_positive] += bin_sizes[0];
-- }
-- }
-- else
-- bins[0] = first;
-- for(unsigned u = first_positive; u < bin_count - 1; u++) {
-- bins[u + 1] = first + bin_sizes[u];
-- bin_sizes[u + 1] += bin_sizes[u];
-- }
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- for(unsigned u = 0; u < bin_count; ++u) {
-- nextbinstart = first + bin_sizes[u];
-- inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
-- }
--
-- //Return if we've completed bucketsorting
-- if(!log_divisor)
-- return;
--
-- //Handling negative values first
-- size_t max_count = get_max_count(log_divisor, last - first);
-- RandomAccessIter lastPos = first;
-- for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
-- size_t count = bin_cache[ii] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[ii]);
-- //sort negative values using reversed-bin spread_sort
-- else
-- negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
-- }
--
-- for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[u]);
-- //sort positive values using normal spread_sort
-- else
-- spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
-- }
-- }
--
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-- inline void
-- float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-- , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
-- {
-- div_type max, min;
-- find_extremes(first, last, max, min, shift);
-- if(max == min)
-- return;
-- unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-- div_type div_min = min >> log_divisor;
-- div_type div_max = max >> log_divisor;
-- unsigned bin_count = div_max - div_min + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
--
-- //Calculating the size of each bin
-- for (RandomAccessIter current = first; current != last;)
-- bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-- //The index of the first positive bin
-- div_type first_positive = (div_min < 0) ? -div_min : 0;
-- //Resetting if all bins are negative
-- if(cache_offset + first_positive > cache_end)
-- first_positive = cache_end - cache_offset;
-- //Reversing the order of the negative bins
-- //Note that because of the negative/positive ordering direction flip
-- //We can not depend upon bin order and positions matching up
-- //so bin_sizes must be reused to contain the end of the bin
-- if(first_positive > 0) {
-- bins[first_positive - 1] = first;
-- for(int ii = first_positive - 2; ii >= 0; --ii) {
-- bins[ii] = first + bin_sizes[ii + 1];
-- bin_sizes[ii] += bin_sizes[ii + 1];
-- }
-- //Handling positives following negatives
-- if((unsigned)first_positive < bin_count) {
-- bins[first_positive] = first + bin_sizes[0];
-- bin_sizes[first_positive] += bin_sizes[0];
-- }
-- }
-- else
-- bins[0] = first;
-- for(unsigned u = first_positive; u < bin_count - 1; u++) {
-- bins[u + 1] = first + bin_sizes[u];
-- bin_sizes[u + 1] += bin_sizes[u];
-- }
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- for(unsigned u = 0; u < bin_count; ++u) {
-- nextbinstart = first + bin_sizes[u];
-- inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
-- }
--
-- //Return if we've completed bucketsorting
-- if(!log_divisor)
-- return;
--
-- //Handling negative values first
-- size_t max_count = get_max_count(log_divisor, last - first);
-- RandomAccessIter lastPos = first;
-- for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
-- size_t count = bin_cache[ii] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[ii]);
-- //sort negative values using reversed-bin spread_sort
-- else
-- negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
-- }
--
-- for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- if(count < 2)
-- continue;
-- if(count < max_count)
-- std::sort(lastPos, bin_cache[u]);
-- //sort positive values using normal spread_sort
-- else
-- spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
-- }
-- }
--
-- template <class RandomAccessIter, class cast_type, class data_type>
-- inline void
-- float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes);
-- }
--
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-- inline void
-- float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
-- }
--
-- template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-- inline void
-- float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift, comp);
-- }
-- }
--
-- //float_sort with casting
-- //The cast_type must be equal in size to the data type, and must be a signed integer
-- template <class RandomAccessIter, class cast_type>
-- inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal)
-- {
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last);
-- else
-- detail::float_Sort(first, last, cVal, *first);
-- }
--
-- //float_sort with casting to an int
-- //Only use this with IEEE floating-point numbers
-- template <class RandomAccessIter>
-- inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last)
-- {
-- int cVal = 0;
-- float_sort_cast(first, last, cVal);
-- }
--
-- //float_sort with functors
-- template <class RandomAccessIter, class right_shift>
-- inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift)
-- {
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last);
-- else
-- detail::float_Sort(first, last, shift(*first, 0), *first, shift);
-- }
--
-- template <class RandomAccessIter, class right_shift, class compare>
-- inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp)
-- {
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last, comp);
-- else
-- detail::float_Sort(first, last, shift(*first, 0), *first, shift, comp);
-- }
--
-- //------------------------------------------------- string_sort source ---------------------------------------------
-- namespace detail {
-- //Offsetting on identical characters. This function works a character at a time for optimal worst-case performance.
-- template<class RandomAccessIter>
-- inline void
-- update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)
-- {
-- unsigned nextOffset = char_offset;
-- bool done = false;
-- while(!done) {
-- RandomAccessIter curr = first;
-- do {
-- //ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
-- if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) {
-- done = true;
-- break;
-- }
-- } while(++curr != finish);
-- if(!done)
-- ++nextOffset;
-- }
-- char_offset = nextOffset;
-- }
--
-- //Offsetting on identical characters. This function works a character at a time for optimal worst-case performance.
-- template<class RandomAccessIter, class get_char, class get_length>
-- inline void
-- update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)
-- {
-- unsigned nextOffset = char_offset;
-- bool done = false;
-- while(!done) {
-- RandomAccessIter curr = first;
-- do {
-- //ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
-- if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) {
-- done = true;
-- break;
-- }
-- } while(++curr != finish);
-- if(!done)
-- ++nextOffset;
-- }
-- char_offset = nextOffset;
-- }
--
-- //A comparison functor for strings that assumes they are identical up to char_offset
-- template<class data_type, class unsignedchar_type>
-- struct offset_lessthan {
-- offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
-- inline bool operator()(const data_type &x, const data_type &y) const
-- {
-- unsigned minSize = std::min(x.size(), y.size());
-- for(unsigned u = fchar_offset; u < minSize; ++u) {
-- if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u]))
-- return true;
-- else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u]))
-- return false;
-- }
-- return x.size() < y.size();
-- }
-- unsigned fchar_offset;
-- };
--
-- //A comparison functor for strings that assumes they are identical up to char_offset
-- template<class data_type, class unsignedchar_type>
-- struct offset_greaterthan {
-- offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){}
-- inline bool operator()(const data_type &x, const data_type &y) const
-- {
-- unsigned minSize = std::min(x.size(), y.size());
-- for(unsigned u = fchar_offset; u < minSize; ++u) {
-- if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u]))
-- return true;
-- else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u]))
-- return false;
-- }
-- return x.size() > y.size();
-- }
-- unsigned fchar_offset;
-- };
--
-- //A comparison functor for strings that assumes they are identical up to char_offset
-- template<class data_type, class get_char, class get_length>
-- struct offset_char_lessthan {
-- offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
-- inline bool operator()(const data_type &x, const data_type &y) const
-- {
-- unsigned minSize = std::min(length(x), length(y));
-- for(unsigned u = fchar_offset; u < minSize; ++u) {
-- if(getchar(x, u) < getchar(y, u))
-- return true;
-- else if(getchar(y, u) < getchar(x, u))
-- return false;
-- }
-- return length(x) < length(y);
-- }
-- unsigned fchar_offset;
-- get_char getchar;
-- get_length length;
-- };
--
-- //String sorting recursive implementation
-- template <class RandomAccessIter, class data_type, class unsignedchar_type>
-- inline void
-- string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-- , unsigned cache_offset, std::vector<size_t> &bin_sizes)
-- {
-- //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-- //Iterate to the end of the empties. If all empty, return
-- while((*first).size() <= char_offset) {
-- if(++first == last)
-- return;
-- }
-- RandomAccessIter finish = last - 1;
-- //Getting the last non-empty
-- for(;(*finish).size() <= char_offset; --finish) { }
-- ++finish;
-- //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
-- update_offset(first, finish, char_offset);
--
-- const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-- //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-- const unsigned max_size = bin_count;
-- const unsigned membin_count = bin_count + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
--
-- //Calculating the size of each bin; this takes roughly 10% of runtime
-- for (RandomAccessIter current = first; current != last; ++current) {
-- if((*current).size() <= char_offset) {
-- bin_sizes[0]++;
-- }
-- else
-- bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++;
-- }
-- //Assign the bin positions
-- bin_cache[cache_offset] = first;
-- for(unsigned u = 0; u < membin_count - 1; u++)
-- bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- //handling empty bins
-- RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
-- nextbinstart += bin_sizes[0];
-- RandomAccessIter * target_bin;
-- //Iterating over each element in the bin of empties
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //empties belong in this bin
-- while((*current).size() > char_offset) {
-- target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);
-- iter_swap(current, (*target_bin)++);
-- }
-- }
-- *local_bin = nextbinstart;
-- //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-- unsigned last_bin = bin_count - 1;
-- for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
-- //This dominates runtime, mostly in the swap and bin lookups
-- for(unsigned u = 0; u < last_bin; ++u) {
-- local_bin = bins + u;
-- nextbinstart += bin_sizes[u + 1];
-- //Iterating over each element in this bin
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //Swapping elements in current into place until the correct element has been swapped in
-- for(target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]); target_bin != local_bin;
-- target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]))
-- iter_swap(current, (*target_bin)++);
-- }
-- *local_bin = nextbinstart;
-- }
-- bins[last_bin] = last;
-- //Recursing
-- RandomAccessIter lastPos = bin_cache[cache_offset];
-- //Skip this loop for empties
-- for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- //don't sort unless there are at least two items to compare
-- if(count < 2)
-- continue;
-- //using std::sort if its worst-case is better
-- if(count < max_size)
-- std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1));
-- else
-- string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
-- }
-- }
--
-- //Sorts strings in reverse order, with empties at the end
-- template <class RandomAccessIter, class data_type, class unsignedchar_type>
-- inline void
-- reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-- , unsigned cache_offset, std::vector<size_t> &bin_sizes)
-- {
-- //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-- RandomAccessIter curr = first;
-- //Iterate to the end of the empties. If all empty, return
-- while((*curr).size() <= char_offset) {
-- if(++curr == last)
-- return;
-- }
-- //Getting the last non-empty
-- while((*(--last)).size() <= char_offset) { }
-- ++last;
-- //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
-- update_offset(curr, last, char_offset);
-- RandomAccessIter * target_bin;
--
-- const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-- //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-- const unsigned max_size = bin_count;
-- const unsigned membin_count = bin_count + 1;
-- const unsigned max_bin = bin_count - 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
-- RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]);
--
-- //Calculating the size of each bin; this takes roughly 10% of runtime
-- for (RandomAccessIter current = first; current != last; ++current) {
-- if((*current).size() <= char_offset) {
-- bin_sizes[bin_count]++;
-- }
-- else
-- bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++;
-- }
-- //Assign the bin positions
-- bin_cache[cache_offset] = first;
-- for(unsigned u = 0; u < membin_count - 1; u++)
-- bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = last;
-- //handling empty bins
-- RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
-- RandomAccessIter lastFull = *local_bin;
-- //Iterating over each element in the bin of empties
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //empties belong in this bin
-- while((*current).size() > char_offset) {
-- target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);
-- iter_swap(current, (*target_bin)++);
-- }
-- }
-- *local_bin = nextbinstart;
-- nextbinstart = first;
-- //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-- unsigned last_bin = max_bin;
-- for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
-- //This dominates runtime, mostly in the swap and bin lookups
-- for(unsigned u = 0; u < last_bin; ++u) {
-- local_bin = bins + u;
-- nextbinstart += bin_sizes[u];
-- //Iterating over each element in this bin
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //Swapping elements in current into place until the correct element has been swapped in
-- for(target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]); target_bin != local_bin;
-- target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]))
-- iter_swap(current, (*target_bin)++);
-- }
-- *local_bin = nextbinstart;
-- }
-- bins[last_bin] = lastFull;
-- //Recursing
-- RandomAccessIter lastPos = first;
-- //Skip this loop for empties
-- for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- //don't sort unless there are at least two items to compare
-- if(count < 2)
-- continue;
-- //using std::sort if its worst-case is better
-- if(count < max_size)
-- std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1));
-- else
-- reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
-- }
-- }
--
-- //String sorting recursive implementation
-- template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length>
-- inline void
-- string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-- , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length)
-- {
-- //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-- //Iterate to the end of the empties. If all empty, return
-- while(length(*first) <= char_offset) {
-- if(++first == last)
-- return;
-- }
-- RandomAccessIter finish = last - 1;
-- //Getting the last non-empty
-- for(;length(*finish) <= char_offset; --finish) { }
-- ++finish;
-- update_offset(first, finish, char_offset, getchar, length);
--
-- const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-- //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-- const unsigned max_size = bin_count;
-- const unsigned membin_count = bin_count + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
--
-- //Calculating the size of each bin; this takes roughly 10% of runtime
-- for (RandomAccessIter current = first; current != last; ++current) {
-- if(length(*current) <= char_offset) {
-- bin_sizes[0]++;
-- }
-- else
-- bin_sizes[getchar((*current), char_offset) + 1]++;
-- }
-- //Assign the bin positions
-- bin_cache[cache_offset] = first;
-- for(unsigned u = 0; u < membin_count - 1; u++)
-- bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- //handling empty bins
-- RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
-- nextbinstart += bin_sizes[0];
-- RandomAccessIter * target_bin;
-- //Iterating over each element in the bin of empties
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //empties belong in this bin
-- while(length(*current) > char_offset) {
-- target_bin = bins + getchar((*current), char_offset);
-- iter_swap(current, (*target_bin)++);
-- }
-- }
-- *local_bin = nextbinstart;
-- //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-- unsigned last_bin = bin_count - 1;
-- for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
-- //This dominates runtime, mostly in the swap and bin lookups
-- for(unsigned ii = 0; ii < last_bin; ++ii) {
-- local_bin = bins + ii;
-- nextbinstart += bin_sizes[ii + 1];
-- //Iterating over each element in this bin
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //Swapping elements in current into place until the correct element has been swapped in
-- for(target_bin = bins + getchar((*current), char_offset); target_bin != local_bin;
-- target_bin = bins + getchar((*current), char_offset))
-- iter_swap(current, (*target_bin)++);
-- }
-- *local_bin = nextbinstart;
-- }
-- bins[last_bin] = last;
--
-- //Recursing
-- RandomAccessIter lastPos = bin_cache[cache_offset];
-- //Skip this loop for empties
-- for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- //don't sort unless there are at least two items to compare
-- if(count < 2)
-- continue;
-- //using std::sort if its worst-case is better
-- if(count < max_size)
-- std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1));
-- else
-- string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length);
-- }
-- }
--
-- //String sorting recursive implementation
-- template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
-- inline void
-- string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-- , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
-- {
-- //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-- //Iterate to the end of the empties. If all empty, return
-- while(length(*first) <= char_offset) {
-- if(++first == last)
-- return;
-- }
-- RandomAccessIter finish = last - 1;
-- //Getting the last non-empty
-- for(;length(*finish) <= char_offset; --finish) { }
-- ++finish;
-- update_offset(first, finish, char_offset, getchar, length);
--
-- const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-- //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-- const unsigned max_size = bin_count;
-- const unsigned membin_count = bin_count + 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
--
-- //Calculating the size of each bin; this takes roughly 10% of runtime
-- for (RandomAccessIter current = first; current != last; ++current) {
-- if(length(*current) <= char_offset) {
-- bin_sizes[0]++;
-- }
-- else
-- bin_sizes[getchar((*current), char_offset) + 1]++;
-- }
-- //Assign the bin positions
-- bin_cache[cache_offset] = first;
-- for(unsigned u = 0; u < membin_count - 1; u++)
-- bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = first;
-- //handling empty bins
-- RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
-- nextbinstart += bin_sizes[0];
-- RandomAccessIter * target_bin;
-- //Iterating over each element in the bin of empties
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //empties belong in this bin
-- while(length(*current) > char_offset) {
-- target_bin = bins + getchar((*current), char_offset);
-- iter_swap(current, (*target_bin)++);
-- }
-- }
-- *local_bin = nextbinstart;
-- //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-- unsigned last_bin = bin_count - 1;
-- for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
-- //This dominates runtime, mostly in the swap and bin lookups
-- for(unsigned u = 0; u < last_bin; ++u) {
-- local_bin = bins + u;
-- nextbinstart += bin_sizes[u + 1];
-- //Iterating over each element in this bin
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //Swapping elements in current into place until the correct element has been swapped in
-- for(target_bin = bins + getchar((*current), char_offset); target_bin != local_bin;
-- target_bin = bins + getchar((*current), char_offset))
-- iter_swap(current, (*target_bin)++);
-- }
-- *local_bin = nextbinstart;
-- }
-- bins[last_bin] = last;
--
-- //Recursing
-- RandomAccessIter lastPos = bin_cache[cache_offset];
-- //Skip this loop for empties
-- for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- //don't sort unless there are at least two items to compare
-- if(count < 2)
-- continue;
-- //using std::sort if its worst-case is better
-- if(count < max_size)
-- std::sort(lastPos, bin_cache[u], comp);
-- else
-- string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
-- , bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
-- }
-- }
--
-- //Sorts strings in reverse order, with empties at the end
-- template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
-- inline void
-- reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-- , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
-- {
-- //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-- RandomAccessIter curr = first;
-- //Iterate to the end of the empties. If all empty, return
-- while(length(*curr) <= char_offset) {
-- if(++curr == last)
-- return;
-- }
-- //Getting the last non-empty
-- while(length(*(--last)) <= char_offset) { }
-- ++last;
-- //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
-- update_offset(first, last, char_offset, getchar, length);
--
-- const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-- //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-- const unsigned max_size = bin_count;
-- const unsigned membin_count = bin_count + 1;
-- const unsigned max_bin = bin_count - 1;
-- unsigned cache_end;
-- RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
-- RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]);
--
-- //Calculating the size of each bin; this takes roughly 10% of runtime
-- for (RandomAccessIter current = first; current != last; ++current) {
-- if(length(*current) <= char_offset) {
-- bin_sizes[bin_count]++;
-- }
-- else
-- bin_sizes[max_bin - getchar((*current), char_offset)]++;
-- }
-- //Assign the bin positions
-- bin_cache[cache_offset] = first;
-- for(unsigned u = 0; u < membin_count - 1; u++)
-- bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
--
-- //Swap into place
-- RandomAccessIter nextbinstart = last;
-- //handling empty bins
-- RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
-- RandomAccessIter lastFull = *local_bin;
-- RandomAccessIter * target_bin;
-- //Iterating over each element in the bin of empties
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //empties belong in this bin
-- while(length(*current) > char_offset) {
-- target_bin = end_bin - getchar((*current), char_offset);
-- iter_swap(current, (*target_bin)++);
-- }
-- }
-- *local_bin = nextbinstart;
-- nextbinstart = first;
-- //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-- unsigned last_bin = max_bin;
-- for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
-- //This dominates runtime, mostly in the swap and bin lookups
-- for(unsigned u = 0; u < last_bin; ++u) {
-- local_bin = bins + u;
-- nextbinstart += bin_sizes[u];
-- //Iterating over each element in this bin
-- for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-- //Swapping elements in current into place until the correct element has been swapped in
-- for(target_bin = end_bin - getchar((*current), char_offset); target_bin != local_bin;
-- target_bin = end_bin - getchar((*current), char_offset))
-- iter_swap(current, (*target_bin)++);
-- }
-- *local_bin = nextbinstart;
-- }
-- bins[last_bin] = lastFull;
-- //Recursing
-- RandomAccessIter lastPos = first;
-- //Skip this loop for empties
-- for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
-- size_t count = bin_cache[u] - lastPos;
-- //don't sort unless there are at least two items to compare
-- if(count < 2)
-- continue;
-- //using std::sort if its worst-case is better
-- if(count < max_size)
-- std::sort(lastPos, bin_cache[u], comp);
-- else
-- reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
-- , bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
-- }
-- }
--
-- //Holds the bin vector and makes the initial recursive call
-- template <class RandomAccessIter, class data_type, class unsignedchar_type>
-- inline void
-- string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
-- }
--
-- //Holds the bin vector and makes the initial recursive call
-- template <class RandomAccessIter, class data_type, class unsignedchar_type>
-- inline void
-- reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
-- }
--
-- //Holds the bin vector and makes the initial recursive call
-- template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type>
-- inline void
-- string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);
-- }
--
-- //Holds the bin vector and makes the initial recursive call
-- template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
-- inline void
-- string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
-- }
--
-- //Holds the bin vector and makes the initial recursive call
-- template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
-- inline void
-- reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
-- {
-- std::vector<size_t> bin_sizes;
-- std::vector<RandomAccessIter> bin_cache;
-- reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
-- }
-- }
--
-- //Allows character-type overloads
-- template <class RandomAccessIter, class unsignedchar_type>
-- inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused)
-- {
-- //Don't sort if it's too small to optimize
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last);
-- else
-- detail::string_sort(first, last, *first, unused);
-- }
--
-- //Top-level sorting call; wraps using default of unsigned char
-- template <class RandomAccessIter>
-- inline void string_sort(RandomAccessIter first, RandomAccessIter last)
-- {
-- unsigned char unused = '\0';
-- string_sort(first, last, unused);
-- }
--
-- //Allows character-type overloads
-- template <class RandomAccessIter, class compare, class unsignedchar_type>
-- inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused)
-- {
-- //Don't sort if it's too small to optimize
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last, comp);
-- else
-- detail::reverse_string_sort(first, last, *first, unused);
-- }
--
-- //Top-level sorting call; wraps using default of unsigned char
-- template <class RandomAccessIter, class compare>
-- inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp)
-- {
-- unsigned char unused = '\0';
-- reverse_string_sort(first, last, comp, unused);
-- }
--
-- template <class RandomAccessIter, class get_char, class get_length>
-- inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length)
-- {
-- //Don't sort if it's too small to optimize
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last);
-- else {
-- //skipping past empties at the beginning, which allows us to get the character type
-- //.empty() is not used so as not to require a user declaration of it
-- while(!length(*first)) {
-- if(++first == last)
-- return;
-- }
-- detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0));
-- }
-- }
--
-- template <class RandomAccessIter, class get_char, class get_length, class compare>
-- inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp)
-- {
-- //Don't sort if it's too small to optimize
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last, comp);
-- else {
-- //skipping past empties at the beginning, which allows us to get the character type
-- //.empty() is not used so as not to require a user declaration of it
-- while(!length(*first)) {
-- if(++first == last)
-- return;
-- }
-- detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
-- }
-- }
--
-- template <class RandomAccessIter, class get_char, class get_length, class compare>
-- inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp)
-- {
-- //Don't sort if it's too small to optimize
-- if(last - first < detail::MIN_SORT_SIZE)
-- std::sort(first, last, comp);
-- else {
-- //skipping past empties at the beginning, which allows us to get the character type
-- //.empty() is not used so as not to require a user declaration of it
-- while(!length(*(--last))) {
-- //Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order
-- if(first == last)
-- return;
-- }
-- //making last just after the end of the non-empty part of the array
-- ++last;
-- detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
-- }
-- }
--}
--
--#endif
-+//Templated spread_sort library
-+
-+// Copyright Steven J. Ross 2001 - 2009.
-+// Distributed under the Boost Software License, Version 1.0.
-+// (See accompanying file LICENSE_1_0.txt or copy at
-+// http://www.boost.org/LICENSE_1_0.txt)
-+
-+// See http://www.boost.org/ for updates, documentation, and revision history.
-+
-+/*
-+Some improvements suggested by:
-+Phil Endecott and Frank Gennari
-+Cygwin fix provided by:
-+Scott McMurray
-+*/
-+
-+#ifndef BOOST_SPREAD_SORT_H
-+#define BOOST_SPREAD_SORT_H
-+#include <algorithm>
-+#include <cstring>
-+#include <vector>
-+#include "webrtc/system_wrappers/source/spreadsortlib/constants.hpp"
-+
-+#include <features.h>
-+#if defined(__UCLIBC__)
-+#undef getchar
-+#endif
-+
-+
-+namespace boost {
-+ namespace detail {
-+ //This only works on unsigned data types
-+ template <typename T>
-+ inline unsigned
-+ rough_log_2_size(const T& input)
-+ {
-+ unsigned result = 0;
-+ //The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance
-+ while((input >> result) && (result < (8*sizeof(T)))) ++result;
-+ return result;
-+ }
-+
-+ //Gets the maximum size which we'll call spread_sort on to control worst-case performance
-+ //Maintains both a minimum size to recurse and a check of distribution size versus count
-+ //This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead
-+ inline size_t
-+ get_max_count(unsigned log_range, size_t count)
-+ {
-+ unsigned divisor = rough_log_2_size(count);
-+ //Making sure the divisor is positive
-+ if(divisor > LOG_MEAN_BIN_SIZE)
-+ divisor -= LOG_MEAN_BIN_SIZE;
-+ else
-+ divisor = 1;
-+ unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor);
-+ //Don't try to bitshift more than the size of an element
-+ if((8*sizeof(size_t)) <= relative_width)
-+ relative_width = (8*sizeof(size_t)) - 1;
-+ return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ?
-+ (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) : relative_width);
-+ }
-+
-+ //Find the minimum and maximum using <
-+ template <class RandomAccessIter>
-+ inline void
-+ find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min)
-+ {
-+ min = max = current;
-+ //Start from the second item, as max and min are initialized to the first
-+ while(++current < last) {
-+ if(*max < *current)
-+ max = current;
-+ else if(*current < *min)
-+ min = current;
-+ }
-+ }
-+
-+ //Uses a user-defined comparison operator to find minimum and maximum
-+ template <class RandomAccessIter, class compare>
-+ inline void
-+ find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp)
-+ {
-+ min = max = current;
-+ while(++current < last) {
-+ if(comp(*max, *current))
-+ max = current;
-+ else if(comp(*current, *min))
-+ min = current;
-+ }
-+ }
-+
-+ //Gets a non-negative right bit shift to operate as a logarithmic divisor
-+ inline int
-+ get_log_divisor(size_t count, unsigned log_range)
-+ {
-+ int log_divisor;
-+ //If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so
-+ if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS)
-+ log_divisor = 0;
-+ else {
-+ //otherwise divide the data into an optimized number of pieces
-+ log_divisor += LOG_MEAN_BIN_SIZE;
-+ if(log_divisor < 0)
-+ log_divisor = 0;
-+ //Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically
-+ if((log_range - log_divisor) > MAX_SPLITS)
-+ log_divisor = log_range - MAX_SPLITS;
-+ }
-+ return log_divisor;
-+ }
-+
-+ template <class RandomAccessIter>
-+ inline RandomAccessIter *
-+ size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
-+ {
-+ //Assure space for the size of each bin, followed by initializing sizes
-+ if(bin_count > bin_sizes.size())
-+ bin_sizes.resize(bin_count);
-+ for(size_t u = 0; u < bin_count; u++)
-+ bin_sizes[u] = 0;
-+ //Make sure there is space for the bins
-+ cache_end = cache_offset + bin_count;
-+ if(cache_end > bin_cache.size())
-+ bin_cache.resize(cache_end);
-+ return &(bin_cache[cache_offset]);
-+ }
-+
-+ //Implementation for recursive integer sorting
-+ template <class RandomAccessIter, class div_type, class data_type>
-+ inline void
-+ spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-+ , std::vector<size_t> &bin_sizes)
-+ {
-+ //This step is roughly 10% of runtime, but it helps avoid worst-case behavior and improve behavior with real data
-+ //If you know the maximum and minimum ahead of time, you can pass those values in and skip this step for the first iteration
-+ RandomAccessIter max, min;
-+ find_extremes(first, last, max, min);
-+ //max and min will be the same (the first item) iff all values are equivalent
-+ if(max == min)
-+ return;
-+ RandomAccessIter * target_bin;
-+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0)));
-+ div_type div_min = *min >> log_divisor;
-+ div_type div_max = *max >> log_divisor;
-+ unsigned bin_count = div_max - div_min + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-+
-+ //Calculating the size of each bin; this takes roughly 10% of runtime
-+ for (RandomAccessIter current = first; current != last;)
-+ bin_sizes[(*(current++) >> log_divisor) - div_min]++;
-+ //Assign the bin positions
-+ bins[0] = first;
-+ for(unsigned u = 0; u < bin_count - 1; u++)
-+ bins[u + 1] = bins[u] + bin_sizes[u];
-+
-+ //Swap into place
-+ //This dominates runtime, mostly in the swap and bin lookups
-+ RandomAccessIter nextbinstart = first;
-+ for(unsigned u = 0; u < bin_count - 1; ++u) {
-+ RandomAccessIter * local_bin = bins + u;
-+ nextbinstart += bin_sizes[u];
-+ //Iterating over each element in this bin
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //Swapping elements in current into place until the correct element has been swapped in
-+ for(target_bin = (bins + ((*current >> log_divisor) - div_min)); target_bin != local_bin;
-+ target_bin = bins + ((*current >> log_divisor) - div_min)) {
-+ //3-way swap; this is about 1% faster than a 2-way swap with integers
-+ //The main advantage is less copies are involved per item put in the correct place
-+ data_type tmp;
-+ RandomAccessIter b = (*target_bin)++;
-+ RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);
-+ if (b_bin != local_bin) {
-+ RandomAccessIter c = (*b_bin)++;
-+ tmp = *c;
-+ *c = *b;
-+ }
-+ else
-+ tmp = *b;
-+ *b = *current;
-+ *current = tmp;
-+ }
-+ }
-+ *local_bin = nextbinstart;
-+ }
-+ bins[bin_count - 1] = last;
-+
-+ //If we've bucketsorted, the array is sorted and we should skip recursion
-+ if(!log_divisor)
-+ return;
-+
-+ //Recursing; log_divisor is the remaining range
-+ size_t max_count = get_max_count(log_divisor, last - first);
-+ RandomAccessIter lastPos = first;
-+ for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ //don't sort unless there are at least two items to compare
-+ if(count < 2)
-+ continue;
-+ //using std::sort if its worst-case is better
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[u]);
-+ else
-+ spread_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
-+ }
-+ }
-+
-+ //Generic bitshift-based 3-way swapping code
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-+ inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
-+ , const unsigned log_divisor, const div_type div_min)
-+ {
-+ RandomAccessIter * local_bin = bins + ii;
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min)); target_bin != local_bin;
-+ target_bin = bins + (shift(*current, log_divisor) - div_min)) {
-+ data_type tmp;
-+ RandomAccessIter b = (*target_bin)++;
-+ RandomAccessIter * b_bin = bins + (shift(*b, log_divisor) - div_min);
-+ //Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
-+ if (b_bin != local_bin) {
-+ RandomAccessIter c = (*b_bin)++;
-+ tmp = *c;
-+ *c = *b;
-+ }
-+ //Note: we could increment current once the swap is done in this case, but that seems to impair performance
-+ else
-+ tmp = *b;
-+ *b = *current;
-+ *current = tmp;
-+ }
-+ }
-+ *local_bin = nextbinstart;
-+ }
-+
-+ //Standard swapping wrapper for ascending values
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-+ inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
-+ , const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min)
-+ {
-+ nextbinstart += bin_sizes[ii];
-+ inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min);
-+ }
-+
-+ //Functor implementation for recursive sorting
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-+ inline void
-+ spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-+ , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
-+ {
-+ RandomAccessIter max, min;
-+ find_extremes(first, last, max, min, comp);
-+ if(max == min)
-+ return;
-+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
-+ div_type div_min = shift(*min, log_divisor);
-+ div_type div_max = shift(*max, log_divisor);
-+ unsigned bin_count = div_max - div_min + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-+
-+ //Calculating the size of each bin
-+ for (RandomAccessIter current = first; current != last;)
-+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-+ bins[0] = first;
-+ for(unsigned u = 0; u < bin_count - 1; u++)
-+ bins[u + 1] = bins[u] + bin_sizes[u];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ for(unsigned u = 0; u < bin_count - 1; ++u)
-+ swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);
-+ bins[bin_count - 1] = last;
-+
-+ //If we've bucketsorted, the array is sorted and we should skip recursion
-+ if(!log_divisor)
-+ return;
-+
-+ //Recursing
-+ size_t max_count = get_max_count(log_divisor, last - first);
-+ RandomAccessIter lastPos = first;
-+ for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[u], comp);
-+ else
-+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
-+ }
-+ }
-+
-+ //Functor implementation for recursive sorting with only Shift overridden
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-+ inline void
-+ spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-+ , std::vector<size_t> &bin_sizes, right_shift shift)
-+ {
-+ RandomAccessIter max, min;
-+ find_extremes(first, last, max, min);
-+ if(max == min)
-+ return;
-+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
-+ div_type div_min = shift(*min, log_divisor);
-+ div_type div_max = shift(*max, log_divisor);
-+ unsigned bin_count = div_max - div_min + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-+
-+ //Calculating the size of each bin
-+ for (RandomAccessIter current = first; current != last;)
-+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-+ bins[0] = first;
-+ for(unsigned u = 0; u < bin_count - 1; u++)
-+ bins[u + 1] = bins[u] + bin_sizes[u];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ for(unsigned ii = 0; ii < bin_count - 1; ++ii)
-+ swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
-+ bins[bin_count - 1] = last;
-+
-+ //If we've bucketsorted, the array is sorted and we should skip recursion
-+ if(!log_divisor)
-+ return;
-+
-+ //Recursing
-+ size_t max_count = get_max_count(log_divisor, last - first);
-+ RandomAccessIter lastPos = first;
-+ for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[u]);
-+ else
-+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
-+ }
-+ }
-+
-+ //Holds the bin vector and makes the initial recursive call
-+ template <class RandomAccessIter, class div_type, class data_type>
-+ inline void
-+ spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes);
-+ }
-+
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-+ inline void
-+ spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);
-+ }
-+
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-+ inline void
-+ spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
-+ }
-+ }
-+
-+ //Top-level sorting call for integers
-+ template <class RandomAccessIter>
-+ inline void integer_sort(RandomAccessIter first, RandomAccessIter last)
-+ {
-+ //Don't sort if it's too small to optimize
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last);
-+ else
-+ detail::spread_sort(first, last, *first >> 0, *first);
-+ }
-+
-+ //integer_sort with functors
-+ template <class RandomAccessIter, class right_shift, class compare>
-+ inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
-+ right_shift shift, compare comp) {
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last, comp);
-+ else
-+ detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp);
-+ }
-+
-+ //integer_sort with right_shift functor
-+ template <class RandomAccessIter, class right_shift>
-+ inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
-+ right_shift shift) {
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last);
-+ else
-+ detail::spread_sort(first, last, shift(*first, 0), *first, shift);
-+ }
-+
-+ //------------------------------------------------------ float_sort source --------------------------------------
-+ //Casts a RandomAccessIter to the specified data type
-+ template<class cast_type, class RandomAccessIter>
-+ inline cast_type
-+ cast_float_iter(const RandomAccessIter & floatiter)
-+ {
-+ cast_type result;
-+ std::memcpy(&result, &(*floatiter), sizeof(cast_type));
-+ return result;
-+ }
-+
-+ //Casts a data element to the specified datinner_float_a type
-+ template<class data_type, class cast_type>
-+ inline cast_type
-+ mem_cast(const data_type & data)
-+ {
-+ cast_type result;
-+ std::memcpy(&result, &data, sizeof(cast_type));
-+ return result;
-+ }
-+
-+ namespace detail {
-+ template <class RandomAccessIter, class div_type, class right_shift>
-+ inline void
-+ find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)
-+ {
-+ min = max = shift(*current, 0);
-+ while(++current < last) {
-+ div_type value = shift(*current, 0);
-+ if(max < value)
-+ max = value;
-+ else if(value < min)
-+ min = value;
-+ }
-+ }
-+
-+ //Specialized swap loops for floating-point casting
-+ template <class RandomAccessIter, class div_type, class data_type>
-+ inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii
-+ , const unsigned log_divisor, const div_type div_min)
-+ {
-+ RandomAccessIter * local_bin = bins + ii;
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)); target_bin != local_bin;
-+ target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {
-+ data_type tmp;
-+ RandomAccessIter b = (*target_bin)++;
-+ RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min);
-+ //Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
-+ if (b_bin != local_bin) {
-+ RandomAccessIter c = (*b_bin)++;
-+ tmp = *c;
-+ *c = *b;
-+ }
-+ else
-+ tmp = *b;
-+ *b = *current;
-+ *current = tmp;
-+ }
-+ }
-+ *local_bin = nextbinstart;
-+ }
-+
-+ template <class RandomAccessIter, class div_type, class data_type>
-+ inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii
-+ , const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min)
-+ {
-+ nextbinstart += bin_sizes[ii];
-+ inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min);
-+ }
-+
-+ template <class RandomAccessIter, class cast_type>
-+ inline void
-+ find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)
-+ {
-+ min = max = cast_float_iter<cast_type, RandomAccessIter>(current);
-+ while(++current < last) {
-+ cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current);
-+ if(max < value)
-+ max = value;
-+ else if(value < min)
-+ min = value;
-+ }
-+ }
-+
-+ //Special-case sorting of positive floats with casting instead of a right_shift
-+ template <class RandomAccessIter, class div_type, class data_type>
-+ inline void
-+ positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-+ , std::vector<size_t> &bin_sizes)
-+ {
-+ div_type max, min;
-+ find_extremes(first, last, max, min);
-+ if(max == min)
-+ return;
-+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-+ div_type div_min = min >> log_divisor;
-+ div_type div_max = max >> log_divisor;
-+ unsigned bin_count = div_max - div_min + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-+
-+ //Calculating the size of each bin
-+ for (RandomAccessIter current = first; current != last;)
-+ bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
-+ bins[0] = first;
-+ for(unsigned u = 0; u < bin_count - 1; u++)
-+ bins[u + 1] = bins[u] + bin_sizes[u];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ for(unsigned u = 0; u < bin_count - 1; ++u)
-+ float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
-+ bins[bin_count - 1] = last;
-+
-+ //Return if we've completed bucketsorting
-+ if(!log_divisor)
-+ return;
-+
-+ //Recursing
-+ size_t max_count = get_max_count(log_divisor, last - first);
-+ RandomAccessIter lastPos = first;
-+ for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[u]);
-+ else
-+ positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
-+ }
-+ }
-+
-+ //Sorting negative_ float_s
-+ //Note that bins are iterated in reverse order because max_neg_float = min_neg_int
-+ template <class RandomAccessIter, class div_type, class data_type>
-+ inline void
-+ negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-+ , std::vector<size_t> &bin_sizes)
-+ {
-+ div_type max, min;
-+ find_extremes(first, last, max, min);
-+ if(max == min)
-+ return;
-+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-+ div_type div_min = min >> log_divisor;
-+ div_type div_max = max >> log_divisor;
-+ unsigned bin_count = div_max - div_min + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-+
-+ //Calculating the size of each bin
-+ for (RandomAccessIter current = first; current != last;)
-+ bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
-+ bins[bin_count - 1] = first;
-+ for(int ii = bin_count - 2; ii >= 0; --ii)
-+ bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ //The last bin will always have the correct elements in it
-+ for(int ii = bin_count - 1; ii > 0; --ii)
-+ float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
-+ //Since we don't process the last bin, we need to update its end position
-+ bin_cache[cache_offset] = last;
-+
-+ //Return if we've completed bucketsorting
-+ if(!log_divisor)
-+ return;
-+
-+ //Recursing
-+ size_t max_count = get_max_count(log_divisor, last - first);
-+ RandomAccessIter lastPos = first;
-+ for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
-+ size_t count = bin_cache[ii] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[ii]);
-+ else
-+ negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
-+ }
-+ }
-+
-+ //Sorting negative_ float_s
-+ //Note that bins are iterated in reverse order because max_neg_float = min_neg_int
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-+ inline void
-+ negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-+ , std::vector<size_t> &bin_sizes, right_shift shift)
-+ {
-+ div_type max, min;
-+ find_extremes(first, last, max, min, shift);
-+ if(max == min)
-+ return;
-+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-+ div_type div_min = min >> log_divisor;
-+ div_type div_max = max >> log_divisor;
-+ unsigned bin_count = div_max - div_min + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-+
-+ //Calculating the size of each bin
-+ for (RandomAccessIter current = first; current != last;)
-+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-+ bins[bin_count - 1] = first;
-+ for(int ii = bin_count - 2; ii >= 0; --ii)
-+ bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ //The last bin will always have the correct elements in it
-+ for(int ii = bin_count - 1; ii > 0; --ii)
-+ swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
-+ //Since we don't process the last bin, we need to update its end position
-+ bin_cache[cache_offset] = last;
-+
-+ //Return if we've completed bucketsorting
-+ if(!log_divisor)
-+ return;
-+
-+ //Recursing
-+ size_t max_count = get_max_count(log_divisor, last - first);
-+ RandomAccessIter lastPos = first;
-+ for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
-+ size_t count = bin_cache[ii] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[ii]);
-+ else
-+ negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
-+ }
-+ }
-+
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-+ inline void
-+ negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-+ , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
-+ {
-+ div_type max, min;
-+ find_extremes(first, last, max, min, shift);
-+ if(max == min)
-+ return;
-+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-+ div_type div_min = min >> log_divisor;
-+ div_type div_max = max >> log_divisor;
-+ unsigned bin_count = div_max - div_min + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-+
-+ //Calculating the size of each bin
-+ for (RandomAccessIter current = first; current != last;)
-+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-+ bins[bin_count - 1] = first;
-+ for(int ii = bin_count - 2; ii >= 0; --ii)
-+ bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ //The last bin will always have the correct elements in it
-+ for(int ii = bin_count - 1; ii > 0; --ii)
-+ swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
-+ //Since we don't process the last bin, we need to update its end position
-+ bin_cache[cache_offset] = last;
-+
-+ //Return if we've completed bucketsorting
-+ if(!log_divisor)
-+ return;
-+
-+ //Recursing
-+ size_t max_count = get_max_count(log_divisor, last - first);
-+ RandomAccessIter lastPos = first;
-+ for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
-+ size_t count = bin_cache[ii] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[ii], comp);
-+ else
-+ negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
-+ }
-+ }
-+
-+ //Casting special-case for floating-point sorting
-+ template <class RandomAccessIter, class div_type, class data_type>
-+ inline void
-+ float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-+ , std::vector<size_t> &bin_sizes)
-+ {
-+ div_type max, min;
-+ find_extremes(first, last, max, min);
-+ if(max == min)
-+ return;
-+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-+ div_type div_min = min >> log_divisor;
-+ div_type div_max = max >> log_divisor;
-+ unsigned bin_count = div_max - div_min + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-+
-+ //Calculating the size of each bin
-+ for (RandomAccessIter current = first; current != last;)
-+ bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
-+ //The index of the first positive bin
-+ div_type first_positive = (div_min < 0) ? -div_min : 0;
-+ //Resetting if all bins are negative
-+ if(cache_offset + first_positive > cache_end)
-+ first_positive = cache_end - cache_offset;
-+ //Reversing the order of the negative bins
-+ //Note that because of the negative/positive ordering direction flip
-+ //We can not depend upon bin order and positions matching up
-+ //so bin_sizes must be reused to contain the end of the bin
-+ if(first_positive > 0) {
-+ bins[first_positive - 1] = first;
-+ for(int ii = first_positive - 2; ii >= 0; --ii) {
-+ bins[ii] = first + bin_sizes[ii + 1];
-+ bin_sizes[ii] += bin_sizes[ii + 1];
-+ }
-+ //Handling positives following negatives
-+ if((unsigned)first_positive < bin_count) {
-+ bins[first_positive] = first + bin_sizes[0];
-+ bin_sizes[first_positive] += bin_sizes[0];
-+ }
-+ }
-+ else
-+ bins[0] = first;
-+ for(unsigned u = first_positive; u < bin_count - 1; u++) {
-+ bins[u + 1] = first + bin_sizes[u];
-+ bin_sizes[u + 1] += bin_sizes[u];
-+ }
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ for(unsigned u = 0; u < bin_count; ++u) {
-+ nextbinstart = first + bin_sizes[u];
-+ inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min);
-+ }
-+
-+ if(!log_divisor)
-+ return;
-+
-+ //Handling negative values first
-+ size_t max_count = get_max_count(log_divisor, last - first);
-+ RandomAccessIter lastPos = first;
-+ for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
-+ size_t count = bin_cache[ii] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[ii]);
-+ //sort negative values using reversed-bin spread_sort
-+ else
-+ negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
-+ }
-+
-+ for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[u]);
-+ //sort positive values using normal spread_sort
-+ else
-+ positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
-+ }
-+ }
-+
-+ //Functor implementation for recursive sorting
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-+ inline void
-+ float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-+ , std::vector<size_t> &bin_sizes, right_shift shift)
-+ {
-+ div_type max, min;
-+ find_extremes(first, last, max, min, shift);
-+ if(max == min)
-+ return;
-+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-+ div_type div_min = min >> log_divisor;
-+ div_type div_max = max >> log_divisor;
-+ unsigned bin_count = div_max - div_min + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-+
-+ //Calculating the size of each bin
-+ for (RandomAccessIter current = first; current != last;)
-+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-+ //The index of the first positive bin
-+ div_type first_positive = (div_min < 0) ? -div_min : 0;
-+ //Resetting if all bins are negative
-+ if(cache_offset + first_positive > cache_end)
-+ first_positive = cache_end - cache_offset;
-+ //Reversing the order of the negative bins
-+ //Note that because of the negative/positive ordering direction flip
-+ //We can not depend upon bin order and positions matching up
-+ //so bin_sizes must be reused to contain the end of the bin
-+ if(first_positive > 0) {
-+ bins[first_positive - 1] = first;
-+ for(int ii = first_positive - 2; ii >= 0; --ii) {
-+ bins[ii] = first + bin_sizes[ii + 1];
-+ bin_sizes[ii] += bin_sizes[ii + 1];
-+ }
-+ //Handling positives following negatives
-+ if((unsigned)first_positive < bin_count) {
-+ bins[first_positive] = first + bin_sizes[0];
-+ bin_sizes[first_positive] += bin_sizes[0];
-+ }
-+ }
-+ else
-+ bins[0] = first;
-+ for(unsigned u = first_positive; u < bin_count - 1; u++) {
-+ bins[u + 1] = first + bin_sizes[u];
-+ bin_sizes[u + 1] += bin_sizes[u];
-+ }
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ for(unsigned u = 0; u < bin_count; ++u) {
-+ nextbinstart = first + bin_sizes[u];
-+ inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
-+ }
-+
-+ //Return if we've completed bucketsorting
-+ if(!log_divisor)
-+ return;
-+
-+ //Handling negative values first
-+ size_t max_count = get_max_count(log_divisor, last - first);
-+ RandomAccessIter lastPos = first;
-+ for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
-+ size_t count = bin_cache[ii] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[ii]);
-+ //sort negative values using reversed-bin spread_sort
-+ else
-+ negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
-+ }
-+
-+ for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[u]);
-+ //sort positive values using normal spread_sort
-+ else
-+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
-+ }
-+ }
-+
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-+ inline void
-+ float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-+ , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
-+ {
-+ div_type max, min;
-+ find_extremes(first, last, max, min, shift);
-+ if(max == min)
-+ return;
-+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-+ div_type div_min = min >> log_divisor;
-+ div_type div_max = max >> log_divisor;
-+ unsigned bin_count = div_max - div_min + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-+
-+ //Calculating the size of each bin
-+ for (RandomAccessIter current = first; current != last;)
-+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-+ //The index of the first positive bin
-+ div_type first_positive = (div_min < 0) ? -div_min : 0;
-+ //Resetting if all bins are negative
-+ if(cache_offset + first_positive > cache_end)
-+ first_positive = cache_end - cache_offset;
-+ //Reversing the order of the negative bins
-+ //Note that because of the negative/positive ordering direction flip
-+ //We can not depend upon bin order and positions matching up
-+ //so bin_sizes must be reused to contain the end of the bin
-+ if(first_positive > 0) {
-+ bins[first_positive - 1] = first;
-+ for(int ii = first_positive - 2; ii >= 0; --ii) {
-+ bins[ii] = first + bin_sizes[ii + 1];
-+ bin_sizes[ii] += bin_sizes[ii + 1];
-+ }
-+ //Handling positives following negatives
-+ if((unsigned)first_positive < bin_count) {
-+ bins[first_positive] = first + bin_sizes[0];
-+ bin_sizes[first_positive] += bin_sizes[0];
-+ }
-+ }
-+ else
-+ bins[0] = first;
-+ for(unsigned u = first_positive; u < bin_count - 1; u++) {
-+ bins[u + 1] = first + bin_sizes[u];
-+ bin_sizes[u + 1] += bin_sizes[u];
-+ }
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ for(unsigned u = 0; u < bin_count; ++u) {
-+ nextbinstart = first + bin_sizes[u];
-+ inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
-+ }
-+
-+ //Return if we've completed bucketsorting
-+ if(!log_divisor)
-+ return;
-+
-+ //Handling negative values first
-+ size_t max_count = get_max_count(log_divisor, last - first);
-+ RandomAccessIter lastPos = first;
-+ for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
-+ size_t count = bin_cache[ii] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[ii]);
-+ //sort negative values using reversed-bin spread_sort
-+ else
-+ negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
-+ }
-+
-+ for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ if(count < 2)
-+ continue;
-+ if(count < max_count)
-+ std::sort(lastPos, bin_cache[u]);
-+ //sort positive values using normal spread_sort
-+ else
-+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
-+ }
-+ }
-+
-+ template <class RandomAccessIter, class cast_type, class data_type>
-+ inline void
-+ float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes);
-+ }
-+
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-+ inline void
-+ float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
-+ }
-+
-+ template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-+ inline void
-+ float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift, comp);
-+ }
-+ }
-+
-+ //float_sort with casting
-+ //The cast_type must be equal in size to the data type, and must be a signed integer
-+ template <class RandomAccessIter, class cast_type>
-+ inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal)
-+ {
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last);
-+ else
-+ detail::float_Sort(first, last, cVal, *first);
-+ }
-+
-+ //float_sort with casting to an int
-+ //Only use this with IEEE floating-point numbers
-+ template <class RandomAccessIter>
-+ inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last)
-+ {
-+ int cVal = 0;
-+ float_sort_cast(first, last, cVal);
-+ }
-+
-+ //float_sort with functors
-+ template <class RandomAccessIter, class right_shift>
-+ inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift)
-+ {
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last);
-+ else
-+ detail::float_Sort(first, last, shift(*first, 0), *first, shift);
-+ }
-+
-+ template <class RandomAccessIter, class right_shift, class compare>
-+ inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp)
-+ {
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last, comp);
-+ else
-+ detail::float_Sort(first, last, shift(*first, 0), *first, shift, comp);
-+ }
-+
-+ //------------------------------------------------- string_sort source ---------------------------------------------
-+ namespace detail {
-+ //Offsetting on identical characters. This function works a character at a time for optimal worst-case performance.
-+ template<class RandomAccessIter>
-+ inline void
-+ update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)
-+ {
-+ unsigned nextOffset = char_offset;
-+ bool done = false;
-+ while(!done) {
-+ RandomAccessIter curr = first;
-+ do {
-+ //ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
-+ if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) {
-+ done = true;
-+ break;
-+ }
-+ } while(++curr != finish);
-+ if(!done)
-+ ++nextOffset;
-+ }
-+ char_offset = nextOffset;
-+ }
-+
-+ //Offsetting on identical characters. This function works a character at a time for optimal worst-case performance.
-+ template<class RandomAccessIter, class get_char, class get_length>
-+ inline void
-+ update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)
-+ {
-+ unsigned nextOffset = char_offset;
-+ bool done = false;
-+ while(!done) {
-+ RandomAccessIter curr = first;
-+ do {
-+ //ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
-+ if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) {
-+ done = true;
-+ break;
-+ }
-+ } while(++curr != finish);
-+ if(!done)
-+ ++nextOffset;
-+ }
-+ char_offset = nextOffset;
-+ }
-+
-+ //A comparison functor for strings that assumes they are identical up to char_offset
-+ template<class data_type, class unsignedchar_type>
-+ struct offset_lessthan {
-+ offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
-+ inline bool operator()(const data_type &x, const data_type &y) const
-+ {
-+ unsigned minSize = std::min(x.size(), y.size());
-+ for(unsigned u = fchar_offset; u < minSize; ++u) {
-+ if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u]))
-+ return true;
-+ else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u]))
-+ return false;
-+ }
-+ return x.size() < y.size();
-+ }
-+ unsigned fchar_offset;
-+ };
-+
-+ //A comparison functor for strings that assumes they are identical up to char_offset
-+ template<class data_type, class unsignedchar_type>
-+ struct offset_greaterthan {
-+ offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){}
-+ inline bool operator()(const data_type &x, const data_type &y) const
-+ {
-+ unsigned minSize = std::min(x.size(), y.size());
-+ for(unsigned u = fchar_offset; u < minSize; ++u) {
-+ if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u]))
-+ return true;
-+ else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u]))
-+ return false;
-+ }
-+ return x.size() > y.size();
-+ }
-+ unsigned fchar_offset;
-+ };
-+
-+ //A comparison functor for strings that assumes they are identical up to char_offset
-+ template<class data_type, class get_char, class get_length>
-+ struct offset_char_lessthan {
-+ offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
-+ inline bool operator()(const data_type &x, const data_type &y) const
-+ {
-+ unsigned minSize = std::min(length(x), length(y));
-+ for(unsigned u = fchar_offset; u < minSize; ++u) {
-+ if(getchar(x, u) < getchar(y, u))
-+ return true;
-+ else if(getchar(y, u) < getchar(x, u))
-+ return false;
-+ }
-+ return length(x) < length(y);
-+ }
-+ unsigned fchar_offset;
-+ get_char getchar;
-+ get_length length;
-+ };
-+
-+ //String sorting recursive implementation
-+ template <class RandomAccessIter, class data_type, class unsignedchar_type>
-+ inline void
-+ string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-+ , unsigned cache_offset, std::vector<size_t> &bin_sizes)
-+ {
-+ //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-+ //Iterate to the end of the empties. If all empty, return
-+ while((*first).size() <= char_offset) {
-+ if(++first == last)
-+ return;
-+ }
-+ RandomAccessIter finish = last - 1;
-+ //Getting the last non-empty
-+ for(;(*finish).size() <= char_offset; --finish) { }
-+ ++finish;
-+ //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
-+ update_offset(first, finish, char_offset);
-+
-+ const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-+ //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-+ const unsigned max_size = bin_count;
-+ const unsigned membin_count = bin_count + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
-+
-+ //Calculating the size of each bin; this takes roughly 10% of runtime
-+ for (RandomAccessIter current = first; current != last; ++current) {
-+ if((*current).size() <= char_offset) {
-+ bin_sizes[0]++;
-+ }
-+ else
-+ bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++;
-+ }
-+ //Assign the bin positions
-+ bin_cache[cache_offset] = first;
-+ for(unsigned u = 0; u < membin_count - 1; u++)
-+ bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ //handling empty bins
-+ RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
-+ nextbinstart += bin_sizes[0];
-+ RandomAccessIter * target_bin;
-+ //Iterating over each element in the bin of empties
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //empties belong in this bin
-+ while((*current).size() > char_offset) {
-+ target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);
-+ iter_swap(current, (*target_bin)++);
-+ }
-+ }
-+ *local_bin = nextbinstart;
-+ //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-+ unsigned last_bin = bin_count - 1;
-+ for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
-+ //This dominates runtime, mostly in the swap and bin lookups
-+ for(unsigned u = 0; u < last_bin; ++u) {
-+ local_bin = bins + u;
-+ nextbinstart += bin_sizes[u + 1];
-+ //Iterating over each element in this bin
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //Swapping elements in current into place until the correct element has been swapped in
-+ for(target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]); target_bin != local_bin;
-+ target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]))
-+ iter_swap(current, (*target_bin)++);
-+ }
-+ *local_bin = nextbinstart;
-+ }
-+ bins[last_bin] = last;
-+ //Recursing
-+ RandomAccessIter lastPos = bin_cache[cache_offset];
-+ //Skip this loop for empties
-+ for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ //don't sort unless there are at least two items to compare
-+ if(count < 2)
-+ continue;
-+ //using std::sort if its worst-case is better
-+ if(count < max_size)
-+ std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1));
-+ else
-+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
-+ }
-+ }
-+
-+ //Sorts strings in reverse order, with empties at the end
-+ template <class RandomAccessIter, class data_type, class unsignedchar_type>
-+ inline void
-+ reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-+ , unsigned cache_offset, std::vector<size_t> &bin_sizes)
-+ {
-+ //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-+ RandomAccessIter curr = first;
-+ //Iterate to the end of the empties. If all empty, return
-+ while((*curr).size() <= char_offset) {
-+ if(++curr == last)
-+ return;
-+ }
-+ //Getting the last non-empty
-+ while((*(--last)).size() <= char_offset) { }
-+ ++last;
-+ //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
-+ update_offset(curr, last, char_offset);
-+ RandomAccessIter * target_bin;
-+
-+ const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-+ //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-+ const unsigned max_size = bin_count;
-+ const unsigned membin_count = bin_count + 1;
-+ const unsigned max_bin = bin_count - 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
-+ RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]);
-+
-+ //Calculating the size of each bin; this takes roughly 10% of runtime
-+ for (RandomAccessIter current = first; current != last; ++current) {
-+ if((*current).size() <= char_offset) {
-+ bin_sizes[bin_count]++;
-+ }
-+ else
-+ bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++;
-+ }
-+ //Assign the bin positions
-+ bin_cache[cache_offset] = first;
-+ for(unsigned u = 0; u < membin_count - 1; u++)
-+ bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = last;
-+ //handling empty bins
-+ RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
-+ RandomAccessIter lastFull = *local_bin;
-+ //Iterating over each element in the bin of empties
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //empties belong in this bin
-+ while((*current).size() > char_offset) {
-+ target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);
-+ iter_swap(current, (*target_bin)++);
-+ }
-+ }
-+ *local_bin = nextbinstart;
-+ nextbinstart = first;
-+ //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-+ unsigned last_bin = max_bin;
-+ for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
-+ //This dominates runtime, mostly in the swap and bin lookups
-+ for(unsigned u = 0; u < last_bin; ++u) {
-+ local_bin = bins + u;
-+ nextbinstart += bin_sizes[u];
-+ //Iterating over each element in this bin
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //Swapping elements in current into place until the correct element has been swapped in
-+ for(target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]); target_bin != local_bin;
-+ target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]))
-+ iter_swap(current, (*target_bin)++);
-+ }
-+ *local_bin = nextbinstart;
-+ }
-+ bins[last_bin] = lastFull;
-+ //Recursing
-+ RandomAccessIter lastPos = first;
-+ //Skip this loop for empties
-+ for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ //don't sort unless there are at least two items to compare
-+ if(count < 2)
-+ continue;
-+ //using std::sort if its worst-case is better
-+ if(count < max_size)
-+ std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1));
-+ else
-+ reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
-+ }
-+ }
-+
-+ //String sorting recursive implementation
-+ template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length>
-+ inline void
-+ string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-+ , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length)
-+ {
-+ //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-+ //Iterate to the end of the empties. If all empty, return
-+ while(length(*first) <= char_offset) {
-+ if(++first == last)
-+ return;
-+ }
-+ RandomAccessIter finish = last - 1;
-+ //Getting the last non-empty
-+ for(;length(*finish) <= char_offset; --finish) { }
-+ ++finish;
-+ update_offset(first, finish, char_offset, getchar, length);
-+
-+ const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-+ //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-+ const unsigned max_size = bin_count;
-+ const unsigned membin_count = bin_count + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
-+
-+ //Calculating the size of each bin; this takes roughly 10% of runtime
-+ for (RandomAccessIter current = first; current != last; ++current) {
-+ if(length(*current) <= char_offset) {
-+ bin_sizes[0]++;
-+ }
-+ else
-+ bin_sizes[getchar((*current), char_offset) + 1]++;
-+ }
-+ //Assign the bin positions
-+ bin_cache[cache_offset] = first;
-+ for(unsigned u = 0; u < membin_count - 1; u++)
-+ bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ //handling empty bins
-+ RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
-+ nextbinstart += bin_sizes[0];
-+ RandomAccessIter * target_bin;
-+ //Iterating over each element in the bin of empties
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //empties belong in this bin
-+ while(length(*current) > char_offset) {
-+ target_bin = bins + getchar((*current), char_offset);
-+ iter_swap(current, (*target_bin)++);
-+ }
-+ }
-+ *local_bin = nextbinstart;
-+ //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-+ unsigned last_bin = bin_count - 1;
-+ for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
-+ //This dominates runtime, mostly in the swap and bin lookups
-+ for(unsigned ii = 0; ii < last_bin; ++ii) {
-+ local_bin = bins + ii;
-+ nextbinstart += bin_sizes[ii + 1];
-+ //Iterating over each element in this bin
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //Swapping elements in current into place until the correct element has been swapped in
-+ for(target_bin = bins + getchar((*current), char_offset); target_bin != local_bin;
-+ target_bin = bins + getchar((*current), char_offset))
-+ iter_swap(current, (*target_bin)++);
-+ }
-+ *local_bin = nextbinstart;
-+ }
-+ bins[last_bin] = last;
-+
-+ //Recursing
-+ RandomAccessIter lastPos = bin_cache[cache_offset];
-+ //Skip this loop for empties
-+ for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ //don't sort unless there are at least two items to compare
-+ if(count < 2)
-+ continue;
-+ //using std::sort if its worst-case is better
-+ if(count < max_size)
-+ std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1));
-+ else
-+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length);
-+ }
-+ }
-+
-+ //String sorting recursive implementation
-+ template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
-+ inline void
-+ string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-+ , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
-+ {
-+ //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-+ //Iterate to the end of the empties. If all empty, return
-+ while(length(*first) <= char_offset) {
-+ if(++first == last)
-+ return;
-+ }
-+ RandomAccessIter finish = last - 1;
-+ //Getting the last non-empty
-+ for(;length(*finish) <= char_offset; --finish) { }
-+ ++finish;
-+ update_offset(first, finish, char_offset, getchar, length);
-+
-+ const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-+ //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-+ const unsigned max_size = bin_count;
-+ const unsigned membin_count = bin_count + 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
-+
-+ //Calculating the size of each bin; this takes roughly 10% of runtime
-+ for (RandomAccessIter current = first; current != last; ++current) {
-+ if(length(*current) <= char_offset) {
-+ bin_sizes[0]++;
-+ }
-+ else
-+ bin_sizes[getchar((*current), char_offset) + 1]++;
-+ }
-+ //Assign the bin positions
-+ bin_cache[cache_offset] = first;
-+ for(unsigned u = 0; u < membin_count - 1; u++)
-+ bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = first;
-+ //handling empty bins
-+ RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
-+ nextbinstart += bin_sizes[0];
-+ RandomAccessIter * target_bin;
-+ //Iterating over each element in the bin of empties
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //empties belong in this bin
-+ while(length(*current) > char_offset) {
-+ target_bin = bins + getchar((*current), char_offset);
-+ iter_swap(current, (*target_bin)++);
-+ }
-+ }
-+ *local_bin = nextbinstart;
-+ //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-+ unsigned last_bin = bin_count - 1;
-+ for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
-+ //This dominates runtime, mostly in the swap and bin lookups
-+ for(unsigned u = 0; u < last_bin; ++u) {
-+ local_bin = bins + u;
-+ nextbinstart += bin_sizes[u + 1];
-+ //Iterating over each element in this bin
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //Swapping elements in current into place until the correct element has been swapped in
-+ for(target_bin = bins + getchar((*current), char_offset); target_bin != local_bin;
-+ target_bin = bins + getchar((*current), char_offset))
-+ iter_swap(current, (*target_bin)++);
-+ }
-+ *local_bin = nextbinstart;
-+ }
-+ bins[last_bin] = last;
-+
-+ //Recursing
-+ RandomAccessIter lastPos = bin_cache[cache_offset];
-+ //Skip this loop for empties
-+ for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ //don't sort unless there are at least two items to compare
-+ if(count < 2)
-+ continue;
-+ //using std::sort if its worst-case is better
-+ if(count < max_size)
-+ std::sort(lastPos, bin_cache[u], comp);
-+ else
-+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
-+ , bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
-+ }
-+ }
-+
-+ //Sorts strings in reverse order, with empties at the end
-+ template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
-+ inline void
-+ reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-+ , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
-+ {
-+ //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-+ RandomAccessIter curr = first;
-+ //Iterate to the end of the empties. If all empty, return
-+ while(length(*curr) <= char_offset) {
-+ if(++curr == last)
-+ return;
-+ }
-+ //Getting the last non-empty
-+ while(length(*(--last)) <= char_offset) { }
-+ ++last;
-+ //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
-+ update_offset(first, last, char_offset, getchar, length);
-+
-+ const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-+ //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-+ const unsigned max_size = bin_count;
-+ const unsigned membin_count = bin_count + 1;
-+ const unsigned max_bin = bin_count - 1;
-+ unsigned cache_end;
-+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
-+ RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]);
-+
-+ //Calculating the size of each bin; this takes roughly 10% of runtime
-+ for (RandomAccessIter current = first; current != last; ++current) {
-+ if(length(*current) <= char_offset) {
-+ bin_sizes[bin_count]++;
-+ }
-+ else
-+ bin_sizes[max_bin - getchar((*current), char_offset)]++;
-+ }
-+ //Assign the bin positions
-+ bin_cache[cache_offset] = first;
-+ for(unsigned u = 0; u < membin_count - 1; u++)
-+ bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
-+
-+ //Swap into place
-+ RandomAccessIter nextbinstart = last;
-+ //handling empty bins
-+ RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
-+ RandomAccessIter lastFull = *local_bin;
-+ RandomAccessIter * target_bin;
-+ //Iterating over each element in the bin of empties
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //empties belong in this bin
-+ while(length(*current) > char_offset) {
-+ target_bin = end_bin - getchar((*current), char_offset);
-+ iter_swap(current, (*target_bin)++);
-+ }
-+ }
-+ *local_bin = nextbinstart;
-+ nextbinstart = first;
-+ //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-+ unsigned last_bin = max_bin;
-+ for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
-+ //This dominates runtime, mostly in the swap and bin lookups
-+ for(unsigned u = 0; u < last_bin; ++u) {
-+ local_bin = bins + u;
-+ nextbinstart += bin_sizes[u];
-+ //Iterating over each element in this bin
-+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-+ //Swapping elements in current into place until the correct element has been swapped in
-+ for(target_bin = end_bin - getchar((*current), char_offset); target_bin != local_bin;
-+ target_bin = end_bin - getchar((*current), char_offset))
-+ iter_swap(current, (*target_bin)++);
-+ }
-+ *local_bin = nextbinstart;
-+ }
-+ bins[last_bin] = lastFull;
-+ //Recursing
-+ RandomAccessIter lastPos = first;
-+ //Skip this loop for empties
-+ for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
-+ size_t count = bin_cache[u] - lastPos;
-+ //don't sort unless there are at least two items to compare
-+ if(count < 2)
-+ continue;
-+ //using std::sort if its worst-case is better
-+ if(count < max_size)
-+ std::sort(lastPos, bin_cache[u], comp);
-+ else
-+ reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
-+ , bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
-+ }
-+ }
-+
-+ //Holds the bin vector and makes the initial recursive call
-+ template <class RandomAccessIter, class data_type, class unsignedchar_type>
-+ inline void
-+ string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
-+ }
-+
-+ //Holds the bin vector and makes the initial recursive call
-+ template <class RandomAccessIter, class data_type, class unsignedchar_type>
-+ inline void
-+ reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
-+ }
-+
-+ //Holds the bin vector and makes the initial recursive call
-+ template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type>
-+ inline void
-+ string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);
-+ }
-+
-+ //Holds the bin vector and makes the initial recursive call
-+ template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
-+ inline void
-+ string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
-+ }
-+
-+ //Holds the bin vector and makes the initial recursive call
-+ template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
-+ inline void
-+ reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
-+ {
-+ std::vector<size_t> bin_sizes;
-+ std::vector<RandomAccessIter> bin_cache;
-+ reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
-+ }
-+ }
-+
-+ //Allows character-type overloads
-+ template <class RandomAccessIter, class unsignedchar_type>
-+ inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused)
-+ {
-+ //Don't sort if it's too small to optimize
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last);
-+ else
-+ detail::string_sort(first, last, *first, unused);
-+ }
-+
-+ //Top-level sorting call; wraps using default of unsigned char
-+ template <class RandomAccessIter>
-+ inline void string_sort(RandomAccessIter first, RandomAccessIter last)
-+ {
-+ unsigned char unused = '\0';
-+ string_sort(first, last, unused);
-+ }
-+
-+ //Allows character-type overloads
-+ template <class RandomAccessIter, class compare, class unsignedchar_type>
-+ inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused)
-+ {
-+ //Don't sort if it's too small to optimize
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last, comp);
-+ else
-+ detail::reverse_string_sort(first, last, *first, unused);
-+ }
-+
-+ //Top-level sorting call; wraps using default of unsigned char
-+ template <class RandomAccessIter, class compare>
-+ inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp)
-+ {
-+ unsigned char unused = '\0';
-+ reverse_string_sort(first, last, comp, unused);
-+ }
-+
-+ template <class RandomAccessIter, class get_char, class get_length>
-+ inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length)
-+ {
-+ //Don't sort if it's too small to optimize
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last);
-+ else {
-+ //skipping past empties at the beginning, which allows us to get the character type
-+ //.empty() is not used so as not to require a user declaration of it
-+ while(!length(*first)) {
-+ if(++first == last)
-+ return;
-+ }
-+ detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0));
-+ }
-+ }
-+
-+ template <class RandomAccessIter, class get_char, class get_length, class compare>
-+ inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp)
-+ {
-+ //Don't sort if it's too small to optimize
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last, comp);
-+ else {
-+ //skipping past empties at the beginning, which allows us to get the character type
-+ //.empty() is not used so as not to require a user declaration of it
-+ while(!length(*first)) {
-+ if(++first == last)
-+ return;
-+ }
-+ detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
-+ }
-+ }
-+
-+ template <class RandomAccessIter, class get_char, class get_length, class compare>
-+ inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp)
-+ {
-+ //Don't sort if it's too small to optimize
-+ if(last - first < detail::MIN_SORT_SIZE)
-+ std::sort(first, last, comp);
-+ else {
-+ //skipping past empties at the beginning, which allows us to get the character type
-+ //.empty() is not used so as not to require a user declaration of it
-+ while(!length(*(--last))) {
-+ //Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order
-+ if(first == last)
-+ return;
-+ }
-+ //making last just after the end of the non-empty part of the array
-+ ++last;
-+ detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
-+ }
-+ }
-+}
-+
-+#endif
diff --git a/package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_bsd_addr_c b/package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_bsd_addr_c
deleted file mode 100644
index b64787d88..000000000
--- a/package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_bsd_addr_c
+++ /dev/null
@@ -1,15 +0,0 @@
---- mozilla-release.orig/netwerk/sctp/src/netinet/sctp_bsd_addr.c 2013-09-11 01:15:20.000000000 +0200
-+++ mozilla-release/netwerk/sctp/src/netinet/sctp_bsd_addr.c 2013-10-23 16:28:38.000000000 +0200
-@@ -49,11 +49,10 @@ __FBSDID("$FreeBSD: head/sys/netinet/sct
- #include <netinet/sctp_sysctl.h>
- #include <netinet/sctp_indata.h>
- #if !defined(__Userspace_os_Windows)
-+#include <unistd.h>
- #if defined(ANDROID)
- #include <unistd.h>
- #include <ifaddrs-android-ext.h>
--#else
--#include <sys/unistd.h>
- #endif
- #endif
-
diff --git a/package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_os_userspace_h b/package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_os_userspace_h
deleted file mode 100644
index c3965834f..000000000
--- a/package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_os_userspace_h
+++ /dev/null
@@ -1,22 +0,0 @@
---- mozilla-release.orig/netwerk/sctp/src/netinet/sctp_os_userspace.h 2013-09-11 01:15:20.000000000 +0200
-+++ mozilla-release/netwerk/sctp/src/netinet/sctp_os_userspace.h 2013-10-23 16:28:38.000000000 +0200
-@@ -381,9 +381,8 @@ struct udphdr {
- };
-
- #else /* !defined(Userspace_os_Windows) */
--#include <sys/cdefs.h> /* needed? added from old __FreeBSD__ */
- #include <sys/socket.h>
--#if defined(__Userspace_os_FreeBSD) || defined(__Userspace_os_OpenBSD) || defined(ANDROID)
-+#if defined(__Userspace_os_FreeBSD) || defined(__Userspace_os_OpenBSD) || defined(ANDROID) || 1
- #include <pthread.h>
- #endif
- typedef pthread_mutex_t userland_mutex_t;
-@@ -406,7 +405,7 @@ struct sx {int dummy;};
- /* #include <sys/param.h> in FreeBSD defines MSIZE */
- /* #include <sys/ktr.h> */
- /* #include <sys/systm.h> */
--#if defined(__Userspace_os_Windows)
-+#if defined(__Userspace_os_Windows) || 1
- #include <user_queue.h>
- #else
- #include <sys/queue.h>
diff --git a/package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_pcb_c b/package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_pcb_c
deleted file mode 100644
index bee5b1c64..000000000
--- a/package/firefox/patches/patch-netwerk_sctp_src_netinet_sctp_pcb_c
+++ /dev/null
@@ -1,25 +0,0 @@
---- mozilla-release.orig/netwerk/sctp/src/netinet/sctp_pcb.c 2013-09-11 01:15:20.000000000 +0200
-+++ mozilla-release/netwerk/sctp/src/netinet/sctp_pcb.c 2013-10-23 16:28:38.000000000 +0200
-@@ -30,6 +30,8 @@
- * THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-+#define _BSD_SOURCE /* for IPPORT_RESERVED */
-+
- #ifdef __FreeBSD__
- #include <sys/cdefs.h>
- __FBSDID("$FreeBSD: head/sys/netinet/sctp_pcb.c 246687 2013-02-11 21:02:49Z tuexen $");
-@@ -69,11 +71,10 @@ __FBSDID("$FreeBSD: head/sys/netinet/sct
- #endif
- #if defined(__Userspace__)
- #if !defined(__Userspace_os_Windows)
--#if defined(ANDROID)
-+#include <netdb.h>
- #include <unistd.h>
-+#if defined(ANDROID)
- #include <ifaddrs-android-ext.h>
--#else
--#include <sys/unistd.h>
- #endif
- #endif
- #include <user_socketvar.h>
diff --git a/package/firefox/patches/patch-netwerk_sctp_src_user_environment_c b/package/firefox/patches/patch-netwerk_sctp_src_user_environment_c
deleted file mode 100644
index a31543c75..000000000
--- a/package/firefox/patches/patch-netwerk_sctp_src_user_environment_c
+++ /dev/null
@@ -1,14 +0,0 @@
---- mozilla-release.orig/netwerk/sctp/src/user_environment.c 2013-12-05 17:07:52.000000000 +0100
-+++ mozilla-release/netwerk/sctp/src/user_environment.c 2014-03-16 17:53:08.000000000 +0100
-@@ -35,9 +35,11 @@
- #include <stdint.h>
- #if !defined(__Userspace_os_FreeBSD)
- #if !defined(ANDROID)
-+#if defined(__GLIBC__)
- #include <sys/sysctl.h>
- #endif
- #endif
-+#endif
- #include <netinet/sctp_os_userspace.h>
- #endif
- #include <user_environment.h>
diff --git a/package/firefox/patches/patch-netwerk_sctp_src_user_queue_h b/package/firefox/patches/patch-netwerk_sctp_src_user_queue_h
deleted file mode 100644
index 0a5f30d28..000000000
--- a/package/firefox/patches/patch-netwerk_sctp_src_user_queue_h
+++ /dev/null
@@ -1,12 +0,0 @@
---- mozilla-release.orig/netwerk/sctp/src/user_queue.h 2013-09-11 01:15:20.000000000 +0200
-+++ mozilla-release/netwerk/sctp/src/user_queue.h 2013-10-23 16:28:38.000000000 +0200
-@@ -31,9 +31,6 @@
- #ifndef _USER_QUEUE_H_
- #define _USER_QUEUE_H_
-
--#if !defined (__Userspace_os_Windows)
--#include <sys/cdefs.h>
--#endif
- /*
- * This file defines four types of data structures: singly-linked lists,
- * singly-linked tail queues, lists and tail queues.
diff --git a/package/firefox/patches/patch-python_mozbuild_mozbuild_backend_recursivemake_py b/package/firefox/patches/patch-python_mozbuild_mozbuild_backend_recursivemake_py
index 30f5edd57..3f9aa337d 100644
--- a/package/firefox/patches/patch-python_mozbuild_mozbuild_backend_recursivemake_py
+++ b/package/firefox/patches/patch-python_mozbuild_mozbuild_backend_recursivemake_py
@@ -1,11 +1,11 @@
---- mozilla-release.orig/python/mozbuild/mozbuild/backend/recursivemake.py 2013-12-05 17:07:53.000000000 +0100
-+++ mozilla-release/python/mozbuild/mozbuild/backend/recursivemake.py 2014-01-04 17:58:26.000000000 +0100
-@@ -421,7 +421,7 @@ class RecursiveMakeBackend(CommonBackend
+--- mozilla-release.orig/python/mozbuild/mozbuild/backend/recursivemake.py 2015-01-09 05:38:28.000000000 +0100
++++ mozilla-release/python/mozbuild/mozbuild/backend/recursivemake.py 2015-01-29 16:46:28.000000000 +0100
+@@ -940,7 +940,7 @@ INSTALL_TARGETS += %(prefix)s
def _handle_idl_manager(self, manager):
- build_files = self._purge_manifests['xpidl']
+ build_files = self._install_manifests['xpidl']
- for p in ('Makefile', 'backend.mk', '.deps/.mkdir.done',
+ for p in ('Makefile.in', 'Makefile', 'backend.mk', '.deps/.mkdir.done',
'xpt/.mkdir.done'):
- build_files.add(p)
+ build_files.add_optional_exists(p)
diff --git a/package/firefox/patches/patch-tools_profiler_platform-linux_cc b/package/firefox/patches/patch-tools_profiler_platform-linux_cc
index a331e87fe..96b97381b 100644
--- a/package/firefox/patches/patch-tools_profiler_platform-linux_cc
+++ b/package/firefox/patches/patch-tools_profiler_platform-linux_cc
@@ -1,6 +1,6 @@
---- mozilla-release.orig/tools/profiler/platform-linux.cc 2013-12-05 17:07:58.000000000 +0100
-+++ mozilla-release/tools/profiler/platform-linux.cc 2014-01-02 14:59:20.000000000 +0100
-@@ -58,7 +58,7 @@
+--- mozilla-release.orig/tools/profiler/platform-linux.cc 2015-01-09 05:38:28.000000000 +0100
++++ mozilla-release/tools/profiler/platform-linux.cc 2015-01-29 16:46:28.000000000 +0100
+@@ -57,7 +57,7 @@
#include <fcntl.h> // open
#include <unistd.h> // sysconf
#include <semaphore.h>
@@ -9,7 +9,7 @@
#include <execinfo.h> // backtrace, backtrace_symbols
#endif // def __GLIBC__
#include <strings.h> // index
-@@ -84,14 +84,12 @@
+@@ -92,14 +92,12 @@
#define SIGNAL_SAVE_PROFILE SIGUSR2
@@ -23,5 +23,5 @@
}
-#endif
- #if !defined(ANDROID)
- // Keep track of when any of our threads calls fork(), so we can
+ /* static */ Thread::tid_t
+ Thread::GetCurrentId()
diff --git a/package/firefox/patches/patch-tools_profiler_shared-libraries-linux_cc b/package/firefox/patches/patch-tools_profiler_shared-libraries-linux_cc
deleted file mode 100644
index 40b8b594d..000000000
--- a/package/firefox/patches/patch-tools_profiler_shared-libraries-linux_cc
+++ /dev/null
@@ -1,11 +0,0 @@
---- mozilla-release.orig/tools/profiler/shared-libraries-linux.cc 2013-12-05 17:07:58.000000000 +0100
-+++ mozilla-release/tools/profiler/shared-libraries-linux.cc 2014-01-02 15:00:00.000000000 +0100
-@@ -14,7 +14,7 @@
- #include "platform.h"
- #include "shared-libraries.h"
-
--#if !defined(__GLIBC__) && ANDROID_VERSION < 18
-+#if 0
- /* a crapy version of getline, because it's not included in old bionics */
- static ssize_t getline(char **lineptr, size_t *n, FILE *stream)
- {
diff --git a/package/firefox/patches/patch-xpcom_ds_nsMathUtils_h b/package/firefox/patches/patch-xpcom_ds_nsMathUtils_h
index b275a14ec..0b3a738bb 100644
--- a/package/firefox/patches/patch-xpcom_ds_nsMathUtils_h
+++ b/package/firefox/patches/patch-xpcom_ds_nsMathUtils_h
@@ -1,20 +1,20 @@
---- mozilla-release.orig/xpcom/ds/nsMathUtils.h 2013-09-11 01:15:27.000000000 +0200
-+++ mozilla-release/xpcom/ds/nsMathUtils.h 2013-10-23 16:28:38.000000000 +0200
-@@ -98,12 +98,16 @@ inline NS_HIDDEN_(bool) NS_finite(double
+--- mozilla-release.orig/xpcom/ds/nsMathUtils.h 2015-01-09 05:38:29.000000000 +0100
++++ mozilla-release/xpcom/ds/nsMathUtils.h 2015-01-29 21:37:27.000000000 +0100
+@@ -104,12 +104,16 @@ NS_finite(double aNum)
#ifdef WIN32
- // NOTE: '!!' casts an int to bool without spamming MSVC warning C4800.
- return !!_finite(d);
+ // NOTE: '!!' casts an int to bool without spamming MSVC warning C4800.
+ return !!_finite(aNum);
-#elif defined(XP_DARWIN)
+#elif defined(XP_DARWIN) || defined(__UCLIBC__)
- // Darwin has deprecated |finite| and recommends |isfinite|. The former is
- // not present in the iOS SDK.
- return std::isfinite(d);
+ // Darwin has deprecated |finite| and recommends |isfinite|. The former is
+ // not present in the iOS SDK.
+ return std::isfinite(aNum);
#else
-- return finite(d);
+- return finite(aNum);
+#ifdef _GLIBCXX_CMATH
-+ return std::isfinite(d);
++ return std::isfinite(d);
+#else
-+ return isfinite(d);
++ return isfinite(d);
+#endif
#endif
}
diff --git a/package/firefox/patches/patch-xpcom_io_nsLocalFileUnix_cpp b/package/firefox/patches/patch-xpcom_io_nsLocalFileUnix_cpp
index 868ad69d4..71899d1a6 100644
--- a/package/firefox/patches/patch-xpcom_io_nsLocalFileUnix_cpp
+++ b/package/firefox/patches/patch-xpcom_io_nsLocalFileUnix_cpp
@@ -1,16 +1,21 @@
---- mozilla-release.orig/xpcom/io/nsLocalFileUnix.cpp 2013-12-05 17:08:00.000000000 +0100
-+++ mozilla-release/xpcom/io/nsLocalFileUnix.cpp 2014-01-02 14:53:47.000000000 +0100
-@@ -1234,8 +1234,13 @@ nsLocalFile::GetDiskSpaceAvailable(int64
- && dq.dqb_bhardlimit)
- {
- int64_t QuotaSpaceAvailable = 0;
+--- mozilla-release.orig/xpcom/io/nsLocalFileUnix.cpp 2015-01-09 05:38:29.000000000 +0100
++++ mozilla-release/xpcom/io/nsLocalFileUnix.cpp 2015-01-30 14:13:49.000000000 +0100
+@@ -1407,10 +1407,18 @@ nsLocalFile::GetDiskSpaceAvailable(int64
+ #endif
+ && dq.dqb_bhardlimit) {
+ int64_t QuotaSpaceAvailable = 0;
+#if defined(__UCLIBC__)
-+ if (dq.dqb_bhardlimit > dq.dqb_curblocks)
-+ QuotaSpaceAvailable = PRInt64(fs_buf.f_bsize * (dq.dqb_bhardlimit - dq.dqb_curblocks));
++ if (dq.dqb_bhardlimit > dq.dqb_curblocks) {
++ QuotaSpaceAvailable =
++ int64_t(fs_buf.F_BSIZE * (dq.dqb_bhardlimit - dq.dqb_curblocks));
++ }
+#else
- if (dq.dqb_bhardlimit > dq.dqb_curspace)
- QuotaSpaceAvailable = int64_t(fs_buf.F_BSIZE * (dq.dqb_bhardlimit - dq.dqb_curspace));
+ if (dq.dqb_bhardlimit > dq.dqb_curspace) {
+ QuotaSpaceAvailable =
+ int64_t(fs_buf.F_BSIZE * (dq.dqb_bhardlimit - dq.dqb_curspace));
+ }
+#endif
- if(QuotaSpaceAvailable < *aDiskSpaceAvailable) {
- *aDiskSpaceAvailable = QuotaSpaceAvailable;
- }
++
+ if (QuotaSpaceAvailable < *aDiskSpaceAvailable) {
+ *aDiskSpaceAvailable = QuotaSpaceAvailable;
+ }
diff --git a/package/firefox/patches/patch-xpcom_threads_nsThread_cpp b/package/firefox/patches/patch-xpcom_threads_nsThread_cpp
deleted file mode 100644
index 0f40d736a..000000000
--- a/package/firefox/patches/patch-xpcom_threads_nsThread_cpp
+++ /dev/null
@@ -1,17 +0,0 @@
---- mozilla-release.orig/xpcom/threads/nsThread.cpp 2013-12-05 17:08:00.000000000 +0100
-+++ mozilla-release/xpcom/threads/nsThread.cpp 2014-01-02 14:53:47.000000000 +0100
-@@ -23,11 +23,13 @@
- _XOPEN_SOURCE && _XOPEN_SOURCE_EXTENDED) && \
- !(_POSIX_C_SOURCE >= 200809L || _XOPEN_SOURCE >= 700)
-
-+#include <features.h>
- #if defined(XP_UNIX) && !defined(ANDROID) && !defined(DEBUG) && HAVE_UALARM \
- && defined(_GNU_SOURCE)
--# define MOZ_CANARY
- # include <unistd.h>
-+#if !defined(__UCLIBC__)
- # include <execinfo.h>
-+#endif
- # include <signal.h>
- # include <fcntl.h>
- # include "nsXULAppAPI.h"