summaryrefslogtreecommitdiff
path: root/timsort.h
Commit message (Collapse)AuthorAgeFilesLines
* Large batch of typo fixesJared Yanovich2019-09-301-1/+1
| | | | Closes #109.
* Fix unsigned integer overflowNick Wellnhofer2019-05-201-1/+2
| | | | | It's defined behavior but -fsanitize=unsigned-integer-overflow is useful to discover bugs.
* timsort.h: support older GCCsJérôme Duval2019-05-011-1/+1
| | | cherry-pick upstream pull request: __builtin_clzll isn't available on older GCCs
* Fix mixed decls and code in timsort.hNick Wellnhofer2017-10-211-5/+5
|
* Upgrade timsort.h to latest revisionNick Wellnhofer2017-10-121-248/+331
| | | | | | | | Upgrade timsort.h to revision 05fd77bfec049ce8b7c408c4d3dd2d51ee061a15 from https://github.com/swenson/sort Removed all code unrelated to Timsort and made minor adjustments for cross-platform compatibility.
* Fix the Windows header messNick Wellnhofer2017-10-091-2/+2
| | | | | | | | | | | | Don't include windows.h and wsockcompat.h from config.h but only when needed. Don't define _WINSOCKAPI_ manually. This was apparently done to stop windows.h from including winsock.h which is a problem if winsock2.h wasn't included first. But on MinGW, this causes compiler warnings. Define WIN32_LEAN_AND_MEAN instead which has the same effect. Always use the compiler-defined _WIN32 macro instead of WIN32.
* Remove unused variablesNick Wellnhofer2016-10-121-2/+1
|
* Fix format string warningsNick Wellnhofer2016-10-121-1/+1
| | | | | | Also fixes bug #768199: https://bugzilla.gnome.org/show_bug.cgi?id=768199
* Fix timsort invariant loop re: Envisage articleChristopher Swenson2015-02-271-35/+39
| | | | | | | | | | | | | See http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ We use a "runLen" array of size 128, so it should be nearly impossible to have our implementation overflow. But in any case, the fix is relatively simple -- checking two extra conditions in the invariant calculation. I also took this opportunity to remove some redundancy in the left/right merge logic in the invariant loop.
* Portability fixPatrick Monnerat2013-12-121-6/+6
| | | | increase internal use of a portability macro
* Fix a portability issue for GCC < 3.4.0Daniel Veillard2012-10-291-1/+1
|
* Windows build fixesDaniel Richard2012-09-181-2/+10
| | | | | | | | | | | | | Building 2.9.0 on MSVC7.1 was failing This is because HAVE_CONFIG_H is not #defined The patch addresses the above, adds testrecurse.exe and the standard "make check" suite of tests to the MSVC makefile, and also fixes the following (MSVC7.1) warnings: buf.c(674) : warning C4028: formal parameter 1 different from declaration libxml2\timsort.h(71) : warning C4028: formal parameter 1 different from declaration
* Various cleanups to avoid compiler warningsDaniel Veillard2012-09-111-7/+8
|
* fix builds not having stdint.hRob Richards2012-08-271-0/+9
|
* Switching XPath node sorting to TimsortVojtech Fried2012-08-241-0/+496
I use libxml xpath engine on quite large (and mostly "flat") xml files. It seems that Shellsort, that is used in xmlXPathNodeSetSort is a performance bottleneck for my case. I have read some posts about sorting in libxml in the libxml archive, but I agree that qsort was not the way to go. I experimented with Timsort instead and my results were good for me. For about 10000 nodes, my test was about 5x faster with Timsort, for 1000 nodes about 10% faster, for small data files, the difference was not measurable. * timsort.h: the algorithm, kept in a separate header * xpath.c: plug in the new algorithm in xmlXPathNodeSetSort * Makefile.am: add the header to the EXTRA_DIST * doc/apibuild.py: avoid indexing the new header
View Lorry Controller Status