os: KeyValueDB: re-implement (prefix) iter in terms of whole-space iter

In-a-nutshell-version: Create a whole-space iterator interface, and
implement the already existing, prefix-based iterator in terms of the
new whole-space iterator;

This patch introduces a significant change on the architecture of
KeyValueDB's iterator, although its interface remains the same.

Before this patch, KeyValueDB simply defined an interface for a
prefix-based interface, to be implemented by derivative classes. Being
constrained by a prefix-based approach to iterate over the store only makes
sense when we know which prefixes we want to iterate over, but for that we
must know about the prefixes beforehand. This approach didn't work when one
wanted to iterate over the whole key space, without any previous awareness
about the keys and their prefixes.

This patch introduces a new interface for a whole-space iterator, to be
implemented by derivative classes, which is prefix-independent. We also
define an abstract function to obtain this iterator, which must also be
implemented by the derivative class. With this interface in place, we are
then able to implement a prefix-dependent iterator in terms of the
whole-space iterator, which will be offered by the KeyValueDB class itself.

Furthermore, we implement these changes on LevelDBStore and KeyValueDBMemory,
the in-memory mock store, which leads to significant changes on both:

  * LevelDBStore
    - Substitute the previously existing LevelDBIteratorImpl, which
      followed a prefix-based iteration, for
      LevelDBWholeSpaceIteratorImpl, which now iterates over the whole
      key space of the store;

  * KeyValueDBMemory:
    - Substitute the previously existing MemIterator, which followed a
      prefix-based iteration, for WholeSpaceMemIterator, which now
      iterates over the whole key space of the in-memory mock store;
    - Change the in-memory mock store data structure. Previously, we
      used a map-of-maps, mapping prefixes to a key/value map; now we
      keep a single map, mapping (prefix,key) pairs to values.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
os: KeyValueDB: implement snapshot iterators

Create a set of functions, to be implemented by derivative classes of
KeyValueDB, responsible for returning an iterator with strong
read-consistency guarantees. How this iterator is implemented, or by what
is it backed up, is implementation specific, but it must guarantee that
all reads made using this iterator are as if there were no subsequent
writes to the store since we created the iterator.

For instance, LevelDBStore will back this iterator with a leveldb Snapshot,
while KeyValueDBMemory will perform a copy of its in-memory map.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
test: test_keyvaluedb_iterators: Test KeyValueDB implementations iterators

This set of tests focus on testing the expected behavior of LevelDBStore's
and KeyValueDBMemory's iterators.

We will test the following use cases:

  * Removing keys:
    - Using the whole-space iterator, both in LevelDBStore and
      KeyValueDBMemory;
    - Using the whole-space snapshot iterator, following the same use
      case as above;

  * Updating values:
    - Using the whole-space iterator, updating values during iteration
      and matching expected results, both in LevelDBStore and
      KeyValueDBMemory;
    - Using the whole-space snapshot iterator, following the same use
      case as above;

  * Bounds:
    - Using the whole-space iterator, checks if multiple usages of the
      lower_bound() function produces the correct results, both in
      LevelDBStore and KeyValueDBMemory;
    - Following the same use case as above, but focusing on the
      upper_bound() function;

  * Backwards iteration:
    - Checks if seeking to the last position and then iterating
      backwards produces the expected results, both in LevelDBStore and
      KeyValueDBMemory;

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
test: KeyValueDBMemory: Add note concerning snapshot iterators behavior

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>