Create new RefList and RefMap utility types

These types can be used by RefDatabase implementations to manage
the collection.

A RefList stores items sorted by their name, and is an immutable
type using copy-on-write semantics to perform modifications to
the collection.  Binary search is used to locate an existing item
by name, or to locate the proper insertion position if an item does
not exist.

A RefMap can merge up to 3 RefList collections at once during its
entry iteration, allowing items in the resolved or loose RefList
to override items by the same name in the packed RefList.

The RefMap's goal is O(log N) lookup time, and O(N) iteration time,
which is suitable for returning from a RefDatabase.  By relying on
the immutable RefList we might be able to make map construction
nearly constant, making Repository.getAllRefs() an inexpensive
operation if the caches are current.  Since modification is not
common, changes require up to O(N + log N) time to copy the internal
list and collapse or expand the list's array.  As most changes
are made to the loose collection and not the packed collection,
in practice most changes would require less than the full O(N)
time, due to a significantly smaller N in the loose list.

Almost complete test coverage is included in the corresponding
unit tests.  A handful of methods on RefMap are not tested in this
change, as writing the proper test depends on a future refactoring
of how the Ref class represents symbolic reference names.

Change-Id: Ic2095274000336556f719edd75a5c5dd6dd1d857
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

0 files changed, 0 insertions, 0 deletions