Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

XML: Backuped incomplete XML parser. Changes mostly from friday.

UCW: Added inlined functions for reading/writing of UTF-16.

HashTables:
The allocator should be initialized before we make the initial array allocation.

XML: Backuped unfinished XML parser.

Branched off v3.12.1.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

MergeImages: Just small improvements.

sanitize_char(): Allowed tabulators.

Added a missing "inline" keyword.

ucwlib: Added a function for checking "regular" unicode values.

MergeImages: Added several config options.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

Just backuped unfinished detector of image duplicates.

Simplify temporary file deletion in the tester.

The advantage of doing a wildcard rm instead of deleting the files
individually is that you can use $n for temporary files, which are
not mentioned as explicit inputs or outputs in the test case.

Let the tester create its tmp directory if it doesn't exist.

Name test cases in the longest suites.

A new unit test module.

Explicit input and output files can be defined now, the expected
exit code of the process can be set and, last but not least, test
cases can be named to simplify orientation in long test suites.

The `run' directory is no longer hard-wired, the tester now accepts
--verbose and --rundir switches.

The makefiles now pass --rundir=run and also $TESTERFLAGS, allowing
to turn on the verbose mode at request.

Backuped experiments with image duplicates.

images: Fixed trailing spaces and invalid indentation.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

Mainline has set forth towards v3.13.

Set TESTING_DEPS in the example customization, so that `make tests' works.

Perform threaded imagelib tests only with CONFIG_UCW_THREADS.

Allow direct I/O parametrized fastbufs only with CONFIG_UCW_THREADS
enabled, otherwise die with an error.

fixed the compilation of parametrized fastbufs with disabled CONFIG_UCW_THREADS

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#v3.11

No need to report negative sorter speeds.

Patrik needs lib/binsearch.h in the library package.

get rid of the 'register' keyword

ucwlib: default.cfg should return success

ucwlib: unset DEFAULT_CONFIG and ENV_VAR_CONFIG by default

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

sorter: fixed the previous bugfix... all tests now pass

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

sorter: fixed buffer allocation in s-internal, the workspace was too small

Merge with git+ssh://cvs.ucw.cz/projects/sherlock/GIT/sherlock.git

fixed bug in bugfix :-)

Fixed buggy switching of buffers in the internal sorter.

Fixed a bug in fixint sorter.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

Fixed a typo.

The graph tests are able to generate empty input now.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

Do not die on ASSERT when sorting an empty input with custom presorter.

We have test that not only the join bucket is available, but that the join
has actually happened, because custom presorters do not implement automatic
joining.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

Added a very brief introduction to ASIO.

Added copyright messages.

Documented the changes in dev-sorter.

Polished the introductory comments in sorter.h.

Fix the swapping bug, this time correctly.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter

Fixed a bug in s-internal, which caused it to write bogus records
when the array sorter decided to swap buffers.

Honor SORT_DEBUG_KEEP_BUCKETS when swapping in a bucket.

Print item counts as %u's.

Array sorter thresholds are now configured as 64-bit numbers of bytes,
but they are recalculated to the number of elements internally with
proper clamping to ~0U.

Removed a reference to the old sorter.

Added another note.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter

Fixed a silly bug in the parallel radix-sorter.

fixed a memory leak

removed a traling whitespace

Fixed a nasty bug in the threaded radix-sorter.

Use large thread stack.

Adjust thread stack size according to radix sorter parameters.

Cleaned up tracing levels. Array sorter now has its own control knob.

Use a different file access method for small inputs.

Made terminology of the parallel radix-sort consistent with the sequential one.

Intelligent switching of radix-sort buffers.

Do not make retros by default, since it does not compile on all CPU's
(it uses SSE intrinsics).

Auto-tune radix-sort width according to CPU type.

Sweeping over TODO.

Another minor optimization: Added AddRadixBits.

Yet another sorter tuning utility.

Oops, some typos have crept in.

Redefined RadixThreshold to bound the array size instead of the number
of elements -- the switching point seems to be related more to cache
effects than decision performance.

Rewritten handling of small chunks in the parallel radix-sorter.

They are now immediately submitted to the worker thread instead of keeping
them in a list of delayed chunks for the whole course of the algorithm.
This avoids memory usage explosions caused by queueing lots of smallish
chunks. We prefer to wait for the small chunks to complete before starting
the next large chunk.

Let eltpools maintain the number of allocated items. The overhead
is minimal and it helps debugging.

Implemented ThreadChunk limit.

Made radix-sorting threshold configurable and let radix-tune-bits
help find the optimum.

Fixed several bugs in swapping of buffers in the threaded radix-sorter,
which caused it to malfunction with some bit widths.

Added a simple utility for tuning the radix-sorter width.

A subset of tests can be requested now. Also, the radix sort width
can be overridden by making with `CEXTRA="-DFORCE_RADIX_BITS=n"'.

Radix sort bit width is now controlled by the configure script.

Fixed a typo in usage text.

Added CEXTRA and LEXTRA, which can be used to add new compilation/linking
flags without removing the original ones.

We want to keep the results of retros benchmarking, but the rest of BENCH
is obsolete.

Slightly improved user interface of {asio,file}-test and renamed them
to radix-*.

Removed sorter_presort_bufsize, it was no longer used.

Clean up #undef's.

Explain why we don't need the join hack for custom presorting.

Convert the most important users of arraysort.h to sorter/array.h.

So far, I didn't have used radix-sorting, because I want to save memory,
but if any of these sorters will turn up on the profiles, I will convert it
later.

Changed the interface of the array sorter: the buffer and hash_bits parameters
are passed only if hashing is enabled.

Moved the last few relevant NOTES to TODO.

Install API of the new sorter.

I had to get rid of the $(?F) construct, because did not work with includes
in subdirectories (like sorter has). I have replaced it by a direct reference
to the include list macro, which also allows to add the missing dependency
on autoconf.h.

The old sorter is gone.

Cleanup FIXME's.

Shaved off a couple of items from the TODO.

Both quicksort and radix-sort can be parallelized to multiple threads now.

Improved heuristics for internal sorter capacity estimation.