lib/libc/cdb/cdb.5

   1 .\"     $NetBSD: cdb.5,v 1.3 2010/04/27 14:26:52 jruoho Exp $
   2 .\"
   3 .\" Copyright (c) 2010 The NetBSD Foundation, Inc.
   4 .\" All rights reserved.
   5 .\"
   6 .\" This code is derived from software contributed to The NetBSD Foundation
   7 .\" by Joerg Sonnenberger.
   8 .\" Redistribution and use in source and binary forms, with or without
   9 .\" modification, are permitted provided that the following conditions
  10 .\" are met:
  11 .\"
  12 .\" 1. Redistributions of source code must retain the above copyright
  13 .\"    notice, this list of conditions and the following disclaimer.
  14 .\" 2. Redistributions in binary form must reproduce the above copyright
  15 .\"    notice, this list of conditions and the following disclaimer in
  16 .\"    the documentation and/or other materials provided with the
  17 .\"    distribution.
  18 .\"
  19 .\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21 .\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  22 .\" FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  23 .\" COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  24 .\" INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  25 .\" BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26 .\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  27 .\" AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28 .\" OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29 .\" OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30 .\" SUCH DAMAGE.
  31 .Dd April 27, 2010
  32 .Dt CDB 5
  33 .Os
  34 .Sh NAME
  35 .Nm cdb
  36 .Nd format of the constant database
  37 .Sh DESCRIPTION
  38 The
  39 .Nm
  40 database format provides a space-efficient (key,value) database.
  41 The format doesn't allow updates in any convenient form.
  42 The file overhead is around 5 bytes per key and 5 bytes per entry.
  43 Keys are not stored and it is the responsibility of the caller
  44 to validate matches.
  45 The index structure is based on a minimal perfect hash table, so exactly
  46 one entry has to be checked for a match.
  47 .Ss General Format
  48 The header record of a
  49 .Nm
  50 database consists of the following:
  51 .Bd -literal -offset indent
  52 struct header_cdb {
  53         uint8_t magic[7];
  54         uint8_t version;
  55         uint8_t description[16];
  56         uint32_t data_size;
  57         uint32_t entries;
  58         uint32_t entries_index;
  59         uint32_t seed;
  60 };
  61 .Ed
  62 .Pp
  63 All fields are in Little Endian byte order.
  64 .Pp
  65 This is followed by a description of the hash function of
  66 .Va entries_index
  67 records.
  68 The size of each index entry is the logarithm of
  69 .Va entries
  70 to base 256, rounded up.
  71 .Pp
  72 The index records are followed by the start offsets of the entries,
  73 followed by
  74 .Va data_size .
  75 The offsets are relative to the end of the offset record table and are
  76 monotically increasing.
  77 The size of each offset record is the logarithm of
  78 .Va data_size
  79 to base 256, rounded up.
  80 .Pp
  81 The offset table is followed by the entries in order.
  82 No separation or padding is added.
  83 .Ss Limitations
  84 The
  85 .Nm
  86 file format is by design intended for a database that can be
  87 mapped into memory.
  88 The hard limit for the number of entries and keys is 3435973836.
  89 The total size of all values must be smaller than 4GiB.
  90 .Sh SEE ALSO
  91 .Xr cdbr 3 ,
  92 .Xr cdbw 3
  93 .Sh HISTORY
  94 Support for the
  95 .Nm cdb
  96 format first appeared in
  97 .Nx 6.0 .
  98 .Sh AUTHORS
  99 The
 100 .Nm cdbr
 101 and
 102 .Nm cdbw
 103 functions have been written by
 104 .An Joerg Sonnenberger Aq joerg@NetBSD.org .