|
9b987f8c
|
2015-02-27T14:55:49
|
|
Fix timsort invariant loop re: Envisage article
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.
|
|
3a76bfed
|
2013-12-12T15:01:53
|
|
Portability fix
increase internal use of a portability macro
|
|
4ea74a44
|
2012-10-29T10:27:18
|
|
Fix a portability issue for GCC < 3.4.0
|
|
bbe19451
|
2012-09-18T11:15:06
|
|
Windows build fixes
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
|
|
|
7651606f
|
2012-09-11T14:02:08
|
|
Various cleanups to avoid compiler warnings
|
|
236ea1ea
|
2012-08-27T11:56:07
|
|
fix builds not having stdint.h
|
|
3e031b7d
|
2012-08-24T16:52:44
|
|
Switching XPath node sorting to Timsort
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
|