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 38The 39.Nm 40database format provides a space-efficient (key,value) database. 41The format doesn't allow updates in any convenient form. 42The file overhead is around 5 bytes per key and 5 bytes per entry. 43Keys are not stored and it is the responsibility of the caller 44to validate matches. 45The index structure is based on a minimal perfect hash table, so exactly 46one entry has to be checked for a match. 47.Ss General Format 48The header record of a 49.Nm 50database consists of the following: 51.Bd -literal -offset indent 52struct 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 63All fields are in Little Endian byte order. 64.Pp 65This is followed by a description of the hash function of 66.Va entries_index 67records. 68The size of each index entry is the logarithm of 69.Va entries 70to base 256, rounded up. 71.Pp 72The index records are followed by the start offsets of the entries, 73followed by 74.Va data_size . 75The offsets are relative to the end of the offset record table and are 76monotically increasing. 77The size of each offset record is the logarithm of 78.Va data_size 79to base 256, rounded up. 80.Pp 81The offset table is followed by the entries in order. 82No separation or padding is added. 83.Ss Limitations 84The 85.Nm 86file format is by design intended for a database that can be 87mapped into memory. 88The hard limit for the number of entries and keys is 3435973836. 89The 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 94Support for the 95.Nm cdb 96format first appeared in 97.Nx 6.0 . 98.Sh AUTHORS 99The 100.Nm cdbr 101and 102.Nm cdbw 103functions have been written by 104.An Joerg Sonnenberger Aq joerg@NetBSD.org . 105