Rework the binary heap, we use for expiry processing, to deal more gracefully with large number of objects.
Rework the binary heap, we use for expiry processing, to deal more
gracefully with large number of objects.

Previously we kept all objects in a single array which resultined
in increasingly infrequent but increasingly demanding calls to
calloc(3) with the consequent massive memory copies.  We also did
not release memory again if unused.

Now we stripe the array into rows of 64k objects each.

This number is a compromise between space wastage, max 1MB on a
64bit machine, and the desire to not add and delete rows all the
time.  With 64k objects in a row, even on a very busy server would
only add a new row every 5...10 seconds during ramp up.

Delete unused rows, but keep a hysteresis of an entire empty row
to avoid silly add-delete-add-delete-add-delete behaviour at row
boundaries.

Streamline some of the functions a bit.

Fixes #210




git-svn-id: 2c9807fa3ff65b17195bd55dc8a6c4261e10127b@3390 d4fa192b-c00b-0410-8231-f00ffab90ce4

ssm/pkg-varnish,ambernetas/varnish-cache,feld/Varnish-Cache,ssm/pkg-varnish,zhoualbeart/Varnish-Cache,1HLtd/Varnish-Cache,zhoualbeart/Varnish-Cache,drwilco/varnish-cache-old,ajasty-cavium/Varnish-Cache,wikimedia/operations-debs-varnish,alarky/varnish-cache-doc-ja,gquintard/Varnish-Cache,ajasty-cavium/Varnish-Cache,alarky/varnish-cache-doc-ja,mrhmouse/Varnish-Cache,feld/Varnish-Cache,wikimedia/operations-debs-varnish,mrhmouse/Varnish-Cache,alarky/varnish-cache-doc-ja,drwilco/varnish-cache-drwilco,ssm/pkg-varnish,franciscovg/Varnish-Cache,chrismoulton/Varnish-Cache,drwilco/varnish-cache-old,gauthier-delacroix/Varnish-Cache,franciscovg/Varnish-Cache,ambernetas/varnish-cache,feld/Varnish-Cache,zhoualbeart/Varnish-Cache,gauthier-delacroix/Varnish-Cache,alarky/varnish-cache-doc-ja,ambernetas/varnish-cache,ajasty-cavium/Varnish-Cache,drwilco/varnish-cache-drwilco,wikimedia/operations-debs-varnish,chrismoulton/Varnish-Cache,feld/Varnish-Cache,mrhmouse/Varnish-Cache,varnish/Varnish-Cache,ajasty-cavium/Varnish-Cache,franciscovg/Varnish-Cache,varnish/Varnish-Cache,alarky/varnish-cache-doc-ja,varnish/Varnish-Cache,gquintard/Varnish-Cache,chrismoulton/Varnish-Cache,gquintard/Varnish-Cache,drwilco/varnish-cache-old,varnish/Varnish-Cache,franciscovg/Varnish-Cache,wikimedia/operations-debs-varnish,ajasty-cavium/Varnish-Cache,wikimedia/operations-debs-varnish,varnish/Varnish-Cache,zhoualbeart/Varnish-Cache,gauthier-delacroix/Varnish-Cache,gauthier-delacroix/Varnish-Cache,franciscovg/Varnish-Cache,ssm/pkg-varnish,gauthier-delacroix/Varnish-Cache,1HLtd/Varnish-Cache,zhoualbeart/Varnish-Cache,drwilco/varnish-cache-drwilco,gquintard/Varnish-Cache,ssm/pkg-varnish,chrismoulton/Varnish-Cache,feld/Varnish-Cache,chrismoulton/Varnish-Cache,1HLtd/Varnish-Cache,mrhmouse/Varnish-Cache,mrhmouse/Varnish-Cache,1HLtd/Varnish-Cache