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.

A few improvements of sort-test.

Save cache misses by keeping a copy of the hash value next to the pointer.

This trades cache efficiency for extra memory, but it seems to be very well
worth it (e.g., graph sorting in sort-test is 8 times faster now).

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

Added basic threading parameters.

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

Added a debugging hack.

Introduced ARRAY_LONG_HASH and unrolled radix-sorting primitives.

Also tuned ASORT_RADIX_BITS for P4 Xeon (Sherlock3) -- the L1 cache is
so small there that it is better to tune radix-sort for L2 cache size.

Added numbering of tests.

Cleanup of array sorter interface and added quicksplit.

A few bits of commentary.

More bits of the array sorter: radix-sort implemented.

Fixed multi-way sorting with custom presorting.

Added a sketch of a new array sorter implementation.

The interface is already hopefully fixed, I am going to add the missing bits
of implementation soon.

Added a simple allocator for fixed-size objects.

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

Unified top-level Makefile with main-line.

We don't need this as 2-way merging is used rarely.

bugfix in the installer

New TODO notes.

A couple of things done.

Join in the rare case that presorting creates a single run, which is
not known in advance to be final.

Cleaned up joining logic and implemented joins in multi-way merges.

Added decision logic which switches between 2-way merges, n-way merges
and radix splits.

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

The GCC bug (I hope I have ruled out all possibilities of a bug at my side)
turned out to bite even in GCC 4.2.1, so I have reported it and enabled
the workaround for all compiler versions.

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

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

Better (and correct) handling of joins and empty buckets.

Cleanup and commentary.

Added a work-around for nasty GCC bug.

Yet another swap-out.

Fixed the yesterday's mysterious bug.

Presorting for multi-way merge should swap out the buckets.

So far buggy support for multi-way unification.

Fixed bug in error message.

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

Fixed a bug.

Added options for gcc 4.2.x.

Bugfix in keywords module -- fb-dir does not support appending to an
unaligned file.

format_size() no longer exists.

Multi-way merges work fine in simple cases.
I am going to give them a try on large data to see if they are viable.

Setting of LIBS is no longer necessary.

Updated TODO.

Dependencies of test programs are no longer hard-wired in the rules.

Cosmetics.

Shared file handles now use is_temp_file == 2 instead of -1
to avoid collisions with negative return values of bconfig()
meaning "not supported".

Cleanup of file fastbufs.

  o  Common parts of close code moved to bclose_file_helper().
  o  Compatibility wrappers moved to fb-param.c.
  o  Everything related to temp files moved to fb-temp.c.
  o  Several byte -> char conversions.
  o  Better comments.
  o  Testing code compiles again.

bopen_tmp_file(NULL) works.

Use bfix_tmp_file() whereever possible.

Implemented bfix_tmp_file(), which turns a temporary file fastbuf
to a permanent one.

Let bconfig() return the original value.

Removed obsolete comment.

Fixed a typo.

LIBUCW needs to be declared early, because it is used by sub-Makefiles.

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

Hand-merged:

  debug/Makefile
  lib/Makefile
  gather/shepherd/shep-select.c

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

Shell utilities should link with libucw, not libsh.

Commented more libucw configuration switches.

Use lib/default.cfg and get the version string from there.
Avoid sherlock/autoconf.cfg.

Moved default settings of the UCW library to a separate config file.
This config file also contains the master version number.

Renamed both instances of `defconfig' to `default.cfg' to keep the names
in line with the rest of the configuration files.

Mention doc/configure.

Updated documentation on using libraries.

Moved the tests of linking with Sherlock libraries to free/libs/examples/.

The separate library distribution now compiles.

Moved the rule for cf/library to lib/Makefile and the default empty
rule for extras to build/Maketop.

An unfinished experiment in making a separate release of all libraries.

Comments must not be indented, otherwise they are passed to the shell.

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

Comment on optionality of UCW::CGI::error_hook.