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)

hsearch(3)						     Library Functions Manual							hsearch(3)

NAME

       hsearch, hcreate, hdestroy, hsearch_r, hcreate_r, hdestroy_r - Manage hash tables

LIBRARY

       Standard C Library (libc)

SYNOPSIS

       #include <search.h>

       ENTRY *hsearch(	    ENTRY item,      ACTION action);

       int hcreate(	 size_t nel);

       void hdestroy(void);

       int hsearch_r(	   ENTRY item,	    ACTION action,	ENTRY **target,      struct hsearch_data *hsearch_data);

       int hcreate_r(	   size_t nel,	    struct hsearch_data *hsearch_data);

       void hdestroy_r(      struct hsearch_data *hsearch_data);

STANDARDS

       Interfaces documented on this reference page conform to industry standards as follows:

       hsearch(), hcreate(), hdestroy(): XSH4.2

       Refer to the standards(5) reference page for more information about industry standards and associated tags.

PARAMETERS

       Identifies  a  structure  of  the type ENTRY as defined in the search.h header file. It contains two pointers: Points to the comparison key
       string.	Points to any other data associated with the char *key parameter.

	      Pointers to types other than char should be cast as char *.  Specifies a value for an ACTION enum type, which indicates what  is	to
	      be  done with an item key when it cannot be found in the hash table.  The following two actions can be specified for this parameter:
	      Enter the key specified by the item parameter into the hash table at the appropriate place.  When the table is full, a null  pointer
	      is  returned.   Do not enter the item key into the table, but return a null pointer when an item key cannot be found in the hash ta-
	      ble.  Specifies an estimate of the maximum number of entries that the hash table will contain. Under some circumstances,	the  hcre-
	      ate()  function  may  make the hash table larger than specified to obtain mathematically favorable conditions for access to the hash
	      table.  Points to the item actually found.  Consists of data for the hash table.

DESCRIPTION

       The hsearch(), hcreate(), and hdestroy() functions are used to manage hash table operations: The hcreate() function  initializes  the  hash
       table.  You  must  call	the  hcreate()	function before calling the hsearch() function.  The hsearch() function searches a hash table.	It
       returns a pointer into a hash table that indicates where a given entry can be found. The hsearch() function uses  open  addressing  with  a
       hash  function.	 The  hdestroy() function deletes the hash table.  This allows you to start a new hash table because only one table may be
       active at a time. After the call to hdestroy(), the hash table data should no longer be considered accessible.

       [Tru64 UNIX]  The hsearch_r(), hcreate_r(), and hdestroy_r() functions are reentrant versions  of  hsearch(),  hcreate(),  and  hdestroy().
       Upon successful completion, the hsearch_r() function returns 0 (zero).  Upon failure, it returns -1 and sets errno.

       [Tru64  UNIX]  Threads  can share hash tables by using the hcreate_r, hsearch_r, and hdestroy_r functions with a common hsearch_data value.
       To prevent corruption of data when sharing a hash table, locks must be used around calls that use the common hsearch_data value.

RETURN VALUES

       The hsearch() function returns a null pointer when the action parameter is FIND and the key pointed to by item cannot be found or when  the
       specified action is ENTER and the hash table is full.

       Upon  successful completion, the hcreate() function returns a nonzero value. Otherwise, when sufficient space for the table cannot be allo-
       cated, the hcreate() function returns a value of 0 (zero).

ERRORS

       If any of the following conditions occur, the hsearch() function sets errno  to	the  corresponding  value:  The  table	is  full.   [Tru64
       UNIX]  The search failed.

RELATED INFORMATION

       Functions: bsearch(3), lsearch(3), tsearch(3), qsort(3)

       Standards: standards(5) delim off

																	hsearch(3)