NAME

       cdb - Constant DataBase file format

DESCRIPTION

       A  cdb  database  is  a  single file used to map `keys' to `values', having records of (key,value) pairs.
       File consists of 3 parts: toc (table of contents), data and index (hash tables).

       Toc has fixed length of 2048 bytes, containing 256 pointers to hash tables inside index sections.   Every
       pointer  consists of position of a hash table in bytes from the beginning of a file, and a size of a hash
       table in entries, both are 4-bytes (32 bits) unsigned integers in little-endian form.  Hash table  length
       may have zero length, meaning that corresponding hash table is empty.

       Right  after  toc section, data section follows without any alingment.  It consists of series of records,
       each is a key length, value (data) length, key and  value.   Again,  key  and  value  length  are  4-byte
       unsigned integers.  Each next record follows previous without any special alignment.

       After  data section, index (hash tables) section follows.  It should be looked to in conjunction with toc
       section, where each of max 256 hash tables are defined.  Index section consists of series of hash tables,
       with starting position and length defined in toc section.  Every hash table is a sequence of records each
       holds two numbers: key's hash value and record position inside data section (bytes from the beginning  of
       a  file  to  first byte of key length starting data record).  If record position is zero, then this is an
       empty hash table slot, pointed to nowhere.

       CDB hash function is
         hv = ((hv << 5) + hv) ^ c
       for every single c byte of a key, starting with hv = 5381.

       Toc section indexed by (hv % 256), i.e. hash value modulo 256 (number of entries in toc section).

       In order to find a record, one should: first, compute the hash value (hv) of a key.  Second, look to hash
       table number hv modulo 256.  If it is empty, then there is no such key exists.  If it is not empty,  then
       third,  loop  by  slots  inside  that hash table, starting from slot with number hv divided by 256 modulo
       length of that table, or ((hv / 256) % htlen), searching for this hv in hash table.  Stop search on empty
       slot (if record position is zero) or when all slots was probed (note cyclic search, jumping from  end  to
       beginning  of a table).  When hash value in question is found in hash table, look to key of corresponding
       record, comparing it with key in question.  If them of the same length and equals  to  each  other,  then
       record is found, overwise, repeat with next hash table slot.  Note that there may be several records with
       the same key.

SEE ALSO

       cdb(1), cdb(3).

AUTHOR

       The tinycdb package written by Michael Tokarev <mjt+cdb@corpit.ru>, based on ideas and shares file format
       with original cdb library by Dan Bernstein.

LICENSE

       Tinycdb is licensed under MIT license.

                                                    Apr, 2005                                             cdb(5)