Return to cdb.5 CVS log

Up to [cvs.NetBSD.org] / src / lib / libc / cdb

Annotation of src/lib/libc/cdb/cdb.5, Revision 1.5

1.5     ! riastrad    1: .\"    $NetBSD: cdb.5,v 1.3.16.1 2013/07/23 21:07:29 riastradh Exp $
1.1       joerg       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.
1.3       jruoho     31: .Dd April 27, 2010
1.1       joerg      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.
1.2       wiz        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
1.1       joerg      44: to validate matches.
                     45: The index structure is based on a minimal perfect hash table, so exactly
1.2       wiz        46: one entry has to be checked for a match.
1.1       joerg      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
1.3       jruoho     62: .Pp
1.1       joerg      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
1.2       wiz        72: The index records are followed by the start offsets of the entries,
1.1       joerg      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
1.2       wiz        86: file format is by design intended for a database that can be
1.1       joerg      87: mapped into memory.
1.2       wiz        88: The hard limit for the number of entries and keys is 3435973836.
1.1       joerg      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
1.4       wiz       104: .An Joerg Sonnenberger Aq Mt joerg@NetBSD.org .