os: KeyValueDB: Add virtual prefix() function to the key's prefix

If we were to use solely the key() function, whenever we had a key with,
say, prefix 'Foo' and key 'Bar', the key() function would return something
similar to 'Foo<separator>Bar'. Therefore, obtaining the prefix and the key
would require one to be aware of the separator used, and, since that is
implementation specific, we can't rely on such prior knowledge.

This new function must then be implemented by any derivative class of
KeyValueDB, and is expected to return the key's prefix for the
current iterator's position.

Signed-off-by: Joao Eduardo Luis <joao.luis@inktank.com>
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 test a grand total of six use cases, each one with several test
units, being tested for both the LevelDBStore and the in-memory mock
(totalling 48 test units, plus two disabled by default):

 * Removing keys:
  - Using both the whole-space iterator and the whole-space snapshot
    iterator
  - Tests key removal while iterating the store, either by prefix or by
    removing specific (prefix,key) pairs

 * Setting keys:
  - Using both the whole-space iterator and the whole-space snapshot
    iterator
  - Tests key insertion while iterating the store
  - Tests value update while iterating the store
  - This use case has two disabled tests: one when setting keys, other
    when updating values, both on LevelDBStore and using the whole-space
    iterator; this is because they will fail, unlike when using the
    in-memory mock implementation, because leveldb implicitely creates
    an iterator that will read from a snapshot instead of directly from
    the underlying store.

 * Using Upper/Lower Bounds:
  - Using the whole-space iterator (we don't modify the store's state,
    so there is no need to also test the whole-space snapshot iterator)
  - Tests upper/lower bounds when the key, the prefix or both are empty
  - Tests upper/lower bounds when both the key and the prefix are set

 * Seeking:
  - Using the whole-space iterator (we don't modify the store's state,
    so there is no need to also test the whole-space snapshot iterator)
  - Tests seeking to first and to last
  - Tests seeking to first and to last using a prefix

 * Key-Space Iteration:
  - Using the whole-space iterator (we don't modify the store's state,
    so there is no need to also test the whole-space snapshot iterator)
  - Tests forward and backward iteration over the key-space

 * Empty Store:
  - Using the whole-space iterator (we don't modify the store's state,
    so there is no need to also test the whole-space snapshot iterator)
  - Tests seeking and using bounds functions when the store is empty

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