Log Message: |
Make the svn_bit_array__* code use less memory when accessed sparsely.
This also reduces the initialization overhead when bits are set at
high indexes.
The basic idea is to replace the one-dimensional array with a two-
dimensional one where the second dimension ("blocks") gets lazily
allocated - allowing for a sparse layout.
* subversion/libsvn_subr/bit_array.c
(BLOCK_SIZE,
BLOCK_SIZE_BITS,
INITIAL_BLOCK_COUNT): Define granularity constants.
(svn_bit_array__t): Document the two-dimensional storage scheme.
Rename "data" to "blocks".
(select_data_size): We are talking block granularity instead of
byte granularity now on dimension 1.
(svn_bit_array__create): Update initialization code.
(svn_bit_array__set,
svn_bit_array__get): Have "block" as intermediate step in the
addressing / auto-allocation scheme.
* subversion/tests/libsvn_subr/bit-array-test.c
(test_zero_defaults,
test_get_set): Test behavior with indexes around the new default array
size to cover auto-allocation / -growth code.
Suggested by: ivan
|