diff options
| author | Waldemar Brodkorb <wbx@openadk.org> | 2014-02-09 11:53:06 +0100 |
|---|---|---|
| committer | Waldemar Brodkorb <wbx@openadk.org> | 2014-02-09 11:53:06 +0100 |
| commit | ecf3290a88183d946e731b2fb3992dc5c3222a0f (patch) | |
| tree | f41a6b067eacec9f941345cc5764c97ce140f35b /package | |
| parent | 4e93572589af66eee723efafa3939f6c5e0dd7cc (diff) | |
| parent | 108dbac584a1ffc505dc2d02d95ebb2c5e3ddaf7 (diff) | |
merge
Diffstat (limited to 'package')
27 files changed, 3558 insertions, 73 deletions
diff --git a/package/base-files/Makefile b/package/base-files/Makefile index f1e0d0666..10e914178 100644 --- a/package/base-files/Makefile +++ b/package/base-files/Makefile @@ -6,7 +6,7 @@ include $(TOPDIR)/mk/rootfs.mk PKG_NAME:= base-files PKG_VERSION:= 1.0 -PKG_RELEASE:= 63 +PKG_RELEASE:= 64 PKG_SECTION:= base PKG_DESCR:= basic files and scripts PKG_BUILDDEP:= pkgconf-host file-host diff --git a/package/base-files/src/lib/mdev/init b/package/base-files/src/lib/mdev/init index f2b7125b8..a478abecd 100644 --- a/package/base-files/src/lib/mdev/init +++ b/package/base-files/src/lib/mdev/init @@ -1,19 +1,4 @@ #!/bin/sh -if [ "$SUBSYSTEM" == "firmware" ];then - logger "Firmware load for $FIRMWARE requested" - if [ "$ACTION" == "add" ];then - if [ -e "/lib/firmware/$FIRMWARE" ];then - logger "Firmware loading ..." - echo 1 > /sys$DEVPATH/loading - cat "/lib/firmware/$FIRMWARE" > /sys$DEVPATH/data - echo 0 > /sys$DEVPATH/loading - logger "finished." - else - logger "Firmware file $FIRMWARE not found" - echo -1 > /sys$DEVPATH/loading - fi - fi -fi if [ "$SUBSYSTEM" == "pcmcia_socket" ];then logger "Setting up PCMCIA socket resource database" if [ "$ACTION" == "add" ];then diff --git a/package/busybox/Makefile b/package/busybox/Makefile index 0cde4bca5..1d50365e3 100644 --- a/package/busybox/Makefile +++ b/package/busybox/Makefile @@ -5,7 +5,7 @@ include $(TOPDIR)/rules.mk PKG_NAME:= busybox PKG_VERSION:= 1.21.1 -PKG_RELEASE:= 2 +PKG_RELEASE:= 3 PKG_MD5SUM:= 795394f83903b5eec6567d51eebb417e PKG_DESCR:= core utilities for embedded systems PKG_SECTION:= base diff --git a/package/busybox/config/networking/Config.in b/package/busybox/config/networking/Config.in index 74069af13..e350a1b16 100644 --- a/package/busybox/config/networking/Config.in +++ b/package/busybox/config/networking/Config.in @@ -1017,7 +1017,7 @@ source package/busybox/config/networking/udhcp/Config.in config BUSYBOX_IFUPDOWN_UDHCPC_CMD_OPTIONS string "ifup udhcpc command line options" - default "-R -n" + default "-R -b" depends on BUSYBOX_IFUPDOWN && BUSYBOX_UDHCPC help Command line options to pass to udhcpc from ifup. diff --git a/package/busybox/config/util-linux/Config.in b/package/busybox/config/util-linux/Config.in index baf6beb26..aafc795b1 100644 --- a/package/busybox/config/util-linux/Config.in +++ b/package/busybox/config/util-linux/Config.in @@ -69,6 +69,7 @@ config BUSYBOX_FEATURE_MDEV_LOAD_FIRMWARE These devices will request userspace look up the files in /lib/firmware/ and if it exists, send it to the kernel for loading into the hardware. + config BUSYBOX_REV bool "rev" default n diff --git a/package/cups/Makefile b/package/cups/Makefile index 4d83cf472..f67813494 100644 --- a/package/cups/Makefile +++ b/package/cups/Makefile @@ -15,6 +15,7 @@ PKG_URL:= http://www.cups.org/ PKG_SITES:= http://www.cups.org/software/${PKG_VERSION}/ PKG_NEED_CXX:= 1 PKG_OPTS:= dev +PKG_NOPARALLEL:= 1 DISTFILES:= ${PKG_NAME}-${PKG_VERSION}-source.tar.bz2 @@ -32,6 +33,7 @@ HOST_STYLE:= auto HOST_CONFIGURE_ARGS+= --disable-tcp-wrappers \ --disable-webif \ --disable-gssapi \ + --disable-avahi \ --disable-pam \ --disable-dbus \ --without-java \ @@ -46,10 +48,12 @@ HOST_CONFIGURE_ARGS+= --disable-tcp-wrappers \ --with-components=core \ --with-rcdir=$(STAGING_HOST_DIR)/etc CONFIGURE_ENV+= ac_cv_func_sigset=no \ - OPTIM='-fPIC' + OPTIM='-fPIC -std=c89' CONFIGURE_ARGS+= --with-cups-user=cups \ --with-cups-group=cups \ + --disable-static \ + --disable-avahi \ --disable-webif \ --disable-tcp-wrappers \ --disable-gssapi \ @@ -68,11 +72,6 @@ CONFIGURE_ARGS+= --with-cups-user=cups \ --with-rcdir=$(STAGING_TARGET_DIR)/etc FAKE_FLAGS+= DSTROOT="${WRKINST}" STRIP="/bin/true" -ifeq ($(ADK_TOOLCHAIN_GCC_USE_SSP),y) -XAKE_FLAGS+= OPTIM='-fPIC -fstack-protector' -else -XAKE_FLAGS+= OPTIM='-fPIC' -endif cups-install: ${INSTALL_DIR} ${IDIR_CUPS}/usr/lib diff --git a/package/cups/patches/patch-Makedefs_in b/package/cups/patches/patch-Makedefs_in new file mode 100644 index 000000000..1a8f91894 --- /dev/null +++ b/package/cups/patches/patch-Makedefs_in @@ -0,0 +1,10 @@ +--- cups-1.7.1.orig/Makedefs.in 2013-07-17 17:21:18.000000000 +0200 ++++ cups-1.7.1/Makedefs.in 2014-01-31 08:40:55.000000000 +0100 +@@ -238,7 +238,6 @@ DBUSDIR = @DBUSDIR@ + # Rules... + # + +-.SILENT: + .SUFFIXES: .1 .1.gz .1m .1m.gz .3 .3.gz .5 .5.gz .7 .7.gz .8 .8.gz .a .c .cxx .h .man .o .gz + + .c.o: diff --git a/package/cups/patches/patch-configure b/package/cups/patches/patch-configure index 19c9f6092..3a4974140 100644 --- a/package/cups/patches/patch-configure +++ b/package/cups/patches/patch-configure @@ -1,11 +1,14 @@ --- cups-1.7.1.orig/configure 2014-01-08 17:26:27.000000000 +0100 -+++ cups-1.7.1/configure 2014-01-24 18:05:03.000000000 +0100 -@@ -5792,7 +5792,7 @@ fi ++++ cups-1.7.1/configure 2014-01-31 16:48:50.000000000 +0100 +@@ -2490,9 +2490,8 @@ ac_compiler_gnu=$ac_cv_c_compiler_gnu - case "$COMPONENTS" in - all) -- BUILDDIRS="filter backend berkeley cgi-bin monitor notifier ppdc scheduler systemv conf data desktop locale man doc examples templates" -+ BUILDDIRS="filter backend berkeley monitor notifier ppdc conf data" - ;; - core) + +-uname=`uname` +-uversion=`uname -r | sed -e '1,$s/^[^0-9]*\([0-9]*\)\.\([0-9]*\).*/\1\2/'` +-uarch=`uname -m` ++uname=Linux ++uversion=3.0 + + case "$uname" in + Darwin*) diff --git a/package/firefox/Makefile b/package/firefox/Makefile index 054541334..e4b69591d 100644 --- a/package/firefox/Makefile +++ b/package/firefox/Makefile @@ -30,6 +30,7 @@ DISTFILES:= ${PKG_NAME}-${PKG_VERSION}.source.tar.bz2 WRKDIST= ${WRKDIR}/mozilla-release include $(TOPDIR)/mk/package.mk +include $(TOPDIR)/mk/python.mk $(eval $(call PKG_template,FIREFOX,firefox,$(PKG_VERSION)-${PKG_RELEASE},${PKG_DEPENDS},${PKG_DESCR},${PKG_SECTION})) @@ -41,6 +42,7 @@ endif CONFIGURE_ENV+= CROSS_COMPILE=1 \ + PYTHON="$(PYTHON)" \ HOST_CC="${CC_FOR_BUILD}" \ HOST_CPPFLAGS="${CPPFLAGS_FOR_BUILD}" \ HOST_CFLAGS="${CFLAGS_FOR_BUILD}" \ 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 index bf6c335de..3a79329a3 100644 --- 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 @@ -1,6 +1,6 @@ --- 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-01-03 13:06:22.000000000 +0100 -@@ -53,7 +53,9 @@ static char *RCSSTRING __UNUSED__="$Id: ++++ mozilla-release/media/mtransport/third_party/nICEr/src/stun/addrs.c 2014-02-05 07:19:01.000000000 +0100 +@@ -53,7 +53,9 @@ static char *RCSSTRING __UNUSED__="$Id: #undef __unused #include <linux/sysctl.h> #endif @@ -10,7 +10,7 @@ #ifndef LINUX #if !defined(__OpenBSD__) && !defined(__NetBSD__) #include <net/if_var.h> -@@ -61,14 +63,17 @@ static char *RCSSTRING __UNUSED__="$Id: +@@ -61,14 +63,17 @@ static char *RCSSTRING __UNUSED__="$Id: #include <net/if_dl.h> #include <net/if_types.h> #include <sys/sockio.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 new file mode 100644 index 000000000..60d33bb2e --- /dev/null +++ b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py @@ -0,0 +1,23 @@ +--- 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 new file mode 100644 index 000000000..452d380f0 --- /dev/null +++ b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py @@ -0,0 +1,26 @@ +--- 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_system_wrappers_source_cpu_info_cc b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc index 3ee2e0fdc..809dff52a 100644 --- 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 @@ -1,6 +1,6 @@ --- 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-01-02 14:58:37.000000000 +0100 -@@ -36,11 +36,6 @@ uint32_t CpuInfo::DetectNumberOfCores() ++++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/cpu_info.cc 2014-02-05 07:19:01.000000000 +0100 +@@ -36,11 +36,6 @@ uint32_t CpuInfo::DetectNumberOfCores() WEBRTC_TRACE(kTraceStateInfo, kTraceUtility, -1, "Available number of cores:%d", number_of_cores_); @@ -12,7 +12,7 @@ #elif defined(WEBRTC_BSD) || defined(WEBRTC_MAC) int name[] = { CTL_HW, -@@ -61,8 +56,6 @@ uint32_t CpuInfo::DetectNumberOfCores() +@@ -61,8 +56,6 @@ uint32_t CpuInfo::DetectNumberOfCores() "Failed to get number of cores"); number_of_cores_ = 1; } 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 index ac1d23267..95cfd56ba 100644 --- 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 @@ -1,14 +1,3385 @@ --- 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-01-02 14:53:44.000000000 +0100 -@@ -21,6 +21,11 @@ Scott McMurray - #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
++++ 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/gcc/patches/4.7.3/patch-libgcc_unwind-arm-common_inc b/package/gcc/patches/4.7.3/patch-libgcc_unwind-arm-common_inc new file mode 100644 index 000000000..beeba8148 --- /dev/null +++ b/package/gcc/patches/4.7.3/patch-libgcc_unwind-arm-common_inc @@ -0,0 +1,14 @@ +--- gcc-4.7.3.orig/libgcc/unwind-arm-common.inc 2011-12-20 21:54:25.000000000 +0100 ++++ gcc-4.7.3/libgcc/unwind-arm-common.inc 2014-02-05 15:10:25.000000000 +0100 +@@ -25,11 +25,6 @@ + #include "tsystem.h" + #include "unwind.h" + +-/* Used for SystemTap unwinder probe. */ +-#ifdef HAVE_SYS_SDT_H +-#include <sys/sdt.h> +-#endif +- + /* We add a prototype for abort here to avoid creating a dependency on + target headers. */ + extern void abort (void); diff --git a/package/gpsd/Makefile b/package/gpsd/Makefile index 3bed165ab..a161d860f 100644 --- a/package/gpsd/Makefile +++ b/package/gpsd/Makefile @@ -4,9 +4,9 @@ include ${TOPDIR}/rules.mk PKG_NAME:= gpsd -PKG_VERSION:= 3.9 +PKG_VERSION:= 3.10 PKG_RELEASE:= 1 -PKG_MD5SUM:= 53a88f24a0973d23427e82e9a8914f19 +PKG_MD5SUM:= fc5b03aae38b9b5b6880b31924d0ace3 PKG_DESCR:= An interface daemon for GPS receivers PKG_SECTION:= misc PKG_DEPENDS:= libpthread @@ -27,8 +27,8 @@ BUILD_STYLE:= manual INSTALL_STYLE:= manual do-install: - (cd $(WRKBUILD); PATH='$(TARGET_PATH)' CCFLAGS='' \ - scons install prefix=$(WRKINST)/usr python=no chrpath=no bluez=no usb=no libgpsmm=no) + (cd $(WRKBUILD); env PATH='$(TARGET_PATH)' CCFLAGS='' \ + scons install prefix=$(WRKINST)/usr platform=linux python=no chrpath=no bluez=no usb=no libgpsmm=no) gpsd-install: ${INSTALL_DIR} ${IDIR_GPSD}/usr/lib ${IDIR_GPSD}/usr/sbin diff --git a/package/gpsd/patches/patch-SConstruct b/package/gpsd/patches/patch-SConstruct new file mode 100644 index 000000000..0937d9f67 --- /dev/null +++ b/package/gpsd/patches/patch-SConstruct @@ -0,0 +1,12 @@ +--- gpsd-3.10.orig/SConstruct 2013-11-22 14:10:01.000000000 +0100 ++++ gpsd-3.10/SConstruct 2014-02-07 19:33:32.000000000 +0100 +@@ -231,6 +231,9 @@ for (name, default, help) in pathopts: + + env['VERSION'] = gpsd_version + env['PYTHON'] = sys.executable ++env['PLATFORM'] = "posix" ++env['SHLIBSUFFIX'] = ".so" ++env['SHLINKFLAGS'] = "-shared" + + # Set defaults from environment. Note that scons doesn't cope well + # with multi-word CPPFLAGS/LDFLAGS/SHLINKFLAGS values; you'll have to diff --git a/package/heimdal/Makefile b/package/heimdal/Makefile index 3bdb29cba..b59a545ca 100644 --- a/package/heimdal/Makefile +++ b/package/heimdal/Makefile @@ -17,6 +17,8 @@ PKG_NOPARALLEL:= 1 PKG_LIBNAME:= libheimdal PKG_OPTS:= dev +PKG_HOST_DEPENDS:= !darwin + PKG_SUBPKGS:= HEIMDAL_SERVER LIBHEIMDAL PKGSD_LIBHEIMDAL:= Kerberos 5 libraries PKGSC_LIBHEIMDAL:= libs diff --git a/package/libtirpc/Makefile b/package/libtirpc/Makefile index bda186efb..84f85a703 100644 --- a/package/libtirpc/Makefile +++ b/package/libtirpc/Makefile @@ -13,7 +13,7 @@ PKG_DEPENDS:= libgssglue PKG_BUILDDEP:= libgssglue PKG_URL:= http://sourceforge.net/projects/libtirpc/ PKG_SITES:= ${MASTER_SITE_SOURCEFORGE:=libtirpc/} -PKG_OPTS: dev +PKG_OPTS:= dev PKG_LIBC_DEPENDS:= uclibc eglibc glibc diff --git a/package/linux-atm/Makefile b/package/linux-atm/Makefile index 8e40dcf40..eaa2db1eb 100644 --- a/package/linux-atm/Makefile +++ b/package/linux-atm/Makefile @@ -9,6 +9,7 @@ PKG_RELEASE:= 3 PKG_MD5SUM:= 9560b0e1f410a05b849dfdab465dd758 PKG_DESCR:= ATM library for Linux PKG_SECTION:= libs +PKG_BUILDDEP:= flex-host PKG_URL:= http://linux-atm.sourceforge.net/ PKG_SITES:= ${MASTER_SITE_SOURCEFORGE:=linux-atm/} PKG_NOPARALLEL:= 1 diff --git a/package/linux-atm/patches/patch-src_qgen_Makefile_in b/package/linux-atm/patches/patch-src_qgen_Makefile_in index 71ecf3f15..9ed7ec3de 100644 --- a/package/linux-atm/patches/patch-src_qgen_Makefile_in +++ b/package/linux-atm/patches/patch-src_qgen_Makefile_in @@ -1,6 +1,6 @@ --- linux-atm-2.5.1.orig/src/qgen/Makefile.in 2009-11-30 17:21:18.000000000 +0100 -+++ linux-atm-2.5.1/src/qgen/Makefile.in 2010-02-05 22:35:31.371836598 +0100 -@@ -57,14 +57,14 @@ DEFAULT_INCLUDES = -I.@am__isrc@ -I$(top ++++ linux-atm-2.5.1/src/qgen/Makefile.in 2014-02-07 21:40:48.000000000 +0100 +@@ -57,15 +57,15 @@ DEFAULT_INCLUDES = -I.@am__isrc@ -I$(top depcomp = $(SHELL) $(top_srcdir)/depcomp am__depfiles_maybe = depfiles am__mv = mv -f @@ -14,10 +14,12 @@ CCLD = $(CC) LINK = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \ - --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \ -+ --mode=link $(CC_FOR_BUILD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \ - $(LDFLAGS) -o $@ +- $(LDFLAGS) -o $@ ++ --mode=link $(CC_FOR_BUILD) $(AM_CFLAGS) $(CFLAGS_FOR_BUILD) $(AM_LDFLAGS) \ ++ $(LDFLAGS_FOR_BUILD) -o $@ LEXCOMPILE = $(LEX) $(LFLAGS) $(AM_LFLAGS) LTLEXCOMPILE = $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \ + --mode=compile $(LEX) $(LFLAGS) $(AM_LFLAGS) @@ -91,7 +91,7 @@ CC_FOR_BUILD = @CC_FOR_BUILD@ CFLAGS = @CFLAGS_FOR_BUILD@ CFLAGS_FOR_BUILD = @CFLAGS_FOR_BUILD@ diff --git a/package/python2/patches/patch-setup_py b/package/python2/patches/patch-setup_py index 3a80230c2..4973a91b2 100644 --- a/package/python2/patches/patch-setup_py +++ b/package/python2/patches/patch-setup_py @@ -1,5 +1,5 @@ --- Python-2.7.5.orig/setup.py 2013-05-12 05:32:54.000000000 +0200 -+++ Python-2.7.5/setup.py 2013-11-01 14:53:38.000000000 +0100 ++++ Python-2.7.5/setup.py 2014-02-03 17:07:52.000000000 +0100 @@ -74,7 +74,7 @@ def find_file(filename, std_dirs, paths) 'paths' is a list of additional locations to check; if the file is found in one of them, the resulting list will contain the directory. @@ -119,12 +119,3 @@ # This should work on any unixy platform ;-) # If the user has bothered specifying additional -I and -L flags # in OPT and LDFLAGS we might as well use them here. -@@ -837,7 +847,7 @@ class PyBuildExt(build_ext): - openssl_ver >= min_openssl_ver) - - if have_any_openssl: -- if have_usable_openssl: -+ if have_usable_openssl and host_platform != 'darwin': - # The _hashlib module wraps optimized implementations - # of hash functions from the OpenSSL library. - exts.append( Extension('_hashlib', ['_hashopenssl.c'], diff --git a/package/realtek-firmware/Makefile b/package/realtek-firmware/Makefile new file mode 100644 index 000000000..368a4cf89 --- /dev/null +++ b/package/realtek-firmware/Makefile @@ -0,0 +1,27 @@ +# This file is part of the OpenADK project. OpenADK is copyrighted +# material, please see the LICENCE file in the top-level directory. + +include ${TOPDIR}/rules.mk + +PKG_NAME:= realtek-firmware +PKG_VERSION:= 1.0 +PKG_RELEASE:= 1 +PKG_MD5SUM:= 85a7d1d1386143fad312a5a82c422380 +PKG_DESCR:= firmware for realtek wireless cards +PKG_SECTION:= wifi +PKG_SITES:= http://www.openadk.org/distfiles/ + +include ${TOPDIR}/mk/package.mk + +$(eval $(call PKG_template,REALTEK_FIRMWARE,realtek-firmware,${PKG_VERSION}-${PKG_RELEASE},${PKG_DEPENDS},${PKG_DESCR},${PKG_SECTION})) + +CONFIG_STYLE:= manual +BUILD_STYLE:= manual +INSTALL_STYLE:= manual + +do-install: + ${INSTALL_DIR} ${IDIR_REALTEK_FIRMWARE}/lib/firmware/rtlwifi + ${CP} ${WRKBUILD}/*.bin \ + ${IDIR_REALTEK_FIRMWARE}/lib/firmware/rtlwifi + +include ${TOPDIR}/mk/pkg-bottom.mk diff --git a/package/squeezelite/Makefile b/package/squeezelite/Makefile index f200cfee4..aee2b2b70 100644 --- a/package/squeezelite/Makefile +++ b/package/squeezelite/Makefile @@ -5,7 +5,7 @@ include $(TOPDIR)/rules.mk PKG_NAME:= squeezelite PKG_VERSION:= 1.5 -PKG_RELEASE:= 2 +PKG_RELEASE:= 3 PKG_MD5SUM:= 7605af4d64291495645f88575a564475 PKG_DESCR:= headless squeezebox emulator PKG_SECTION:= multimedia @@ -22,6 +22,7 @@ include $(TOPDIR)/mk/package.mk $(eval $(call PKG_template,SQUEEZELITE,squeezelite,$(PKG_VERSION)-${PKG_RELEASE},${PKG_DEPENDS},${PKG_DESCR},${PKG_SECTION})) +TARGET_CPPFLAGS+= -D_GNU_SOURCE -D_POSIX_SOURCE CONFIG_STYLE:= manual INSTALL_STYLE:= manual diff --git a/package/squeezelite/patches/patch-output_alsa_c b/package/squeezelite/patches/patch-output_alsa_c new file mode 100644 index 000000000..7a3e8f836 --- /dev/null +++ b/package/squeezelite/patches/patch-output_alsa_c @@ -0,0 +1,13 @@ +--- squeezelite-1.5.orig/output_alsa.c 2014-01-24 11:24:16.000000000 +0100 ++++ squeezelite-1.5/output_alsa.c 2014-02-08 13:36:12.000000000 +0100 +@@ -670,8 +670,10 @@ void output_init_alsa(log_level level, c + LOG_INFO("memory locked"); + } + ++#if defined(__GLIBC__) + mallopt(M_TRIM_THRESHOLD, -1); + mallopt(M_MMAP_MAX, 0); ++#endif + + touch_memory(silencebuf, MAX_SILENCE_FRAMES * BYTES_PER_FRAME); + touch_memory(outputbuf->buf, outputbuf->size); diff --git a/package/watchdog/Makefile b/package/watchdog/Makefile index 2f67c4012..df586c8c0 100644 --- a/package/watchdog/Makefile +++ b/package/watchdog/Makefile @@ -5,10 +5,12 @@ include ${TOPDIR}/rules.mk PKG_NAME:= watchdog PKG_VERSION:= 5.7 -PKG_RELEASE:= 2 +PKG_RELEASE:= 3 PKG_MD5SUM:= 31766450ecfc9aff70fe966c0b9df06d PKG_DESCR:= watchdog daemon PKG_SECTION:= utils +PKG_DEPENDS:= libtirpc +PKG_BUILDDEP:= libtirpc PKG_SITES:= ${MASTER_SITE_SOURCEFORGE:=watchdog/} include ${TOPDIR}/mk/package.mk diff --git a/package/xinput_calibrator/Makefile b/package/xinput_calibrator/Makefile index 14785c271..e4db834c3 100644 --- a/package/xinput_calibrator/Makefile +++ b/package/xinput_calibrator/Makefile @@ -10,7 +10,7 @@ PKG_MD5SUM:= 20da0a2055a5a75962add8c6b44f60fa PKG_DESCR:= X11 input calibration utility PKG_SECTION:= x11/apps PKG_DEPENDS:= libstdcxx -PKG_URL:= https://github.com/tias/xinput_calibrator +PKG_URL:= http://github.com/downloads/tias/xinput_calibrator/ PKG_SITES:= http://openadk.org/distfiles/ include $(TOPDIR)/mk/package.mk |