Login or Register to Ask a Question and Join Our Community

Linux and UNIX Man Pages

Linux & Unix Commands - Search Man Pages

cdb(5) [debian man page]

cdb(5)								File Formats Manual							    cdb(5)

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 begin-
       ning  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@corpit.ru>, based on ideas and shares file format with  original  cdb  library  by  Dan
       Bernstein.

LICENSE

       Public domain.

								     Apr, 2005								    cdb(5)

Check Out this Related Man Page

hsearch(3)						     Library Functions Manual							hsearch(3)

Name
       hsearch, hcreate, hdestroy - manage hash search tables

Syntax
       #include <search.h>

       ENTRY *hsearch (item, action)
       ENTRY item;
       ACTION action;

       int hcreate (nel)
       unsigned nel;

       void hdestroy ( )

Description
       The  subroutine is a hash-table search routine generalized from Knuth (6.4) Algorithm D.  It returns a pointer into a hash table indicating
       the location at which an entry can be found.  The item is a structure of type ENTRY (defined in the <search.h> header file) containing  two
       pointers: item.key points to the comparison key, and item.data points to any other data to be associated with that key.	(Pointers to types
       other than character should be cast to pointer-to-character.)  The action is a member of an enumeration type ACTION indicating the disposi-
       tion  of  the  entry  if  it cannot be found in the table.  ENTER indicates that the item should be inserted in the table at an appropriate
       point.  FIND indicates that no entry should be made.  Unsuccessful resolution is indicated by the return of a NULL pointer.

       The subroutine allocates sufficient space for the table, and must be called before is used.  The nel is an estimate of the  maximum  number
       of  entries  that  the  table  will contain.  This number may be adjusted upward by the algorithm in order to obtain certain mathematically
       favorable circumstances.

       The subroutine destroys the search table, and may be followed by another call to

Restrictions
       Only one hash search table may be active at any given time.

Diagnostics
       The subroutine returns a NULL pointer if either the action is FIND and the item could not be found or the action is ENTER and the table	is
       full.

       The subroutine returns zero if it cannot allocate sufficient space for the table.

See Also
       bsearch(3), lsearch(3), string(3), tsearch(3)

																	hsearch(3)
Man Page