Cocoli DB - File Format
=======================

::

    cocoli = {
      db-header
    , db-state
    , [record]
    }
    
    db-header = { /* 8 octets */
      db-magic
    , db-version
    }
    db-magic   = "cocoli"
    db-version = 0 :: Word16
    
    /* 21 octets */
    db-state = clean-state
             | writing-state
             | compacting-state
    
    clean-state = {
      0 :: Word8
    , dummy 20 octets
    }
    
    writing-state = {
      1 :: Word8
    , last-file-size-when-the-db-was-clean :: Word64
    , dummy 12 octets
    }
    
    compacting-state = { /* 21 octets */
      2         :: Word8
    , move-from :: Word64
    , move-to   :: Word64
    , amount    :: Word32
    }
    
    record = hole | pair | necrology
    
    hole = { /* at a minimum of 9 octets */
      0         :: Word8
    , hole-size :: Word32
    , content   :: [Word8]
    , hole-size :: Word32
    }
    
    pair = {
      1            :: Word8
    , pair-size    :: Word32
    , key-size     :: Word32
    , value-size   :: Word32
    , key          :: [Word8]
    , value        :: [Word8]
    , padding      :: [Word8]
    , pair-size    :: Word32
    }
    
    necrology = {
      2              :: Word8
    , necrology-size :: Word32
    , key            :: [Word8]
    , necrology-size :: Word32
    }


----------
Operations
----------

Creating DB
~~~~~~~~~~~

1. Create an empty file.
2. Write a DB header and clean-state.


Opening DB
~~~~~~~~~~

1. Open the DB file.
2. See if the DB header is correct.
3. See if the file is at least 29 octets long.
4. Read the db-state and redo any interrupted operations.


Inserting a pair
~~~~~~~~~~~~~~~~

1. Write the current file size to the writing-state.
2. Write "1" to the beginning of db-state.
3. Append a new pair to the end of file.
4. Write "0" to the beginning of db-state.


Removing a pair
~~~~~~~~~~~~~~~

1. Write the current file size to the writing-state.
2. Write "1" to the beginning of db-state.
3. Append a new necrology to the end of file.
4. Write "0" to the beginning of db-state.


Finding a pair
~~~~~~~~~~~~~~

1. Seek to the end of file.
2. Find the first pair with the given key.


Compaction
~~~~~~~~~~

1. Find the first contiguous holes from the beginning of file, turning
   any inactive pairs and necrologies into holes at the same time.
2. Find the first active pair from the beginning of file.
3. If the contiguous holes is bigger than the active pair, move the
   pair to the beginning of holes.
4. If the contiguous holes is smaller than the active pair, move the
   pair to the end of file, then move it again to the beginning of
   holes.


Moving a pair
~~~~~~~~~~~~~

1. Write move-from, move-to, and amount to the compacting-state.
2. Write "2" to the db-state.
3. Copy the pair to the new location, eliminating padding octets if
   any. If the destination hole is at least 9 octets larger than the
   pair, turn the surplus into a new hole. If the surplus isn't large
   enough to be a hole, pad the pair to fill the surplus.
4. Turn the original pair into a hole by writing "0" to the beginning
   of pair.
5. Write "0" to the db-state.
6. If the original pair was at the end of file, truncate the file to
   remove the hole.


Recovering from a writing-state
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1. Truncate the file to the size information in the writing-state.
2. Write "0" to the db-state.


Recovering from a compacting-state
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1. Copy the pair to the new location as the same way as the move
   operation. Be aware that the original pair might already be turned
   into a hole.
2. Turn the original pair into a hole.
3. Write "0" to the db-state.
4. If the original pair was at the end of file, truncate the file to
   remove the hole.


-----------
Concurrency
-----------

Any operations involving db-state changes can not be performed
simultaneously.

It's possible to find a pair while inserting or removing another
pair. But it's impossible to do the compaction in that situation,
because the compaction process needs to tell active pairs from
inactive ones.

Finding a pair while doing the compaction is impossible, because the
compaction process may move an active pair back and forth.