From f52ca292fa8e09b9921fba9a848906fefa0baf14 Mon Sep 17 00:00:00 2001 From: Keith Bostic Date: Wed, 4 Sep 1991 18:36:43 -0800 Subject: [PATCH] break db(3) up into multiple manual pages SCCS-vsn: lib/libc/db/man/dbopen.3 5.17 SCCS-vsn: lib/libc/db/man/btree.3 5.1 SCCS-vsn: lib/libc/db/man/hash.3 5.1 SCCS-vsn: lib/libc/db/man/mpool.3 5.1 SCCS-vsn: lib/libc/db/man/recno.3 5.1 --- usr/src/lib/libc/db/man/btree.3 | 184 ++++++++++++ usr/src/lib/libc/db/man/dbopen.3 | 500 ++++++------------------------- usr/src/lib/libc/db/man/hash.3 | 125 ++++++++ usr/src/lib/libc/db/man/mpool.3 | 193 ++++++++++++ usr/src/lib/libc/db/man/recno.3 | 125 ++++++++ 5 files changed, 712 insertions(+), 415 deletions(-) create mode 100644 usr/src/lib/libc/db/man/btree.3 create mode 100644 usr/src/lib/libc/db/man/hash.3 create mode 100644 usr/src/lib/libc/db/man/mpool.3 create mode 100644 usr/src/lib/libc/db/man/recno.3 diff --git a/usr/src/lib/libc/db/man/btree.3 b/usr/src/lib/libc/db/man/btree.3 new file mode 100644 index 0000000000..0b07fe8a1e --- /dev/null +++ b/usr/src/lib/libc/db/man/btree.3 @@ -0,0 +1,184 @@ +.\" Copyright (c) 1990 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" %sccs.include.redist.man% +.\" +.\" @(#)btree.3 5.1 (Berkeley) %G% +.\" +.TH BTREE 3 "" +.UC 7 +.SH NAME +btree \- btree database access method +.SH SYNOPSIS +.nf +.ft B +#include +#include +.ft R +.fi +.SH DESCRIPTION +The routine +.IR dbopen +is the library interface to database files. +One of the supported file formats is btree files. +The general description of the database access methods is in +.IR dbopen (3), +this manual page describes only the btree specific information. +.PP +The btree data structure is a sorted, balanced tree structure storing +associated key/data pairs. +.PP +The btree access method specific data structure provided to +.I dbopen +is defined in the include file as follows: +.PP +typedef struct { +.RS +u_long flags; +.br +u_int cachesize; +.br +index_t psize; +.br +int lorder; +.br +int maxkeypage; +.br +int minkeypage; +.br +int (*compare)(const DBT *key1, const DBT *key2); +.br +int (*prefix)(const DBT *key1, const DBT *key2); +.RE +} BTREEINFO; +.PP +The elements of this structure are as follows: +.TP +flags +The flag value is specified by +.IR or 'ing +any of the following values: +.RS +.TP +R_DUP +Permit insertion if the key to be inserted already exists in the tree. +This flag permits duplicate keys in the tree. +By default, duplicates are not permitted, and attempts to insert them will +fail. +The order of retrieval of key/data pairs with duplicate keys is undefined, +although a sequential retrieval call with the R_CURSOR flag set will always +return the logical ``first'' of any group of duplicate keys. +.RE +.TP +cachesize +A suggested maximum size (in bytes) of the memory cache. +This value is +.B only +advisory, and the access method will allocate more memory rather than fail. +Since every search examines the root page of the tree, caching the most +recently used pages substantially improves access time. +In addition, physical writes are delayed as long as possible, so a moderate +cache can reduce the number of I/O operations significantly. +Obviously, using a cache increases (but only increases) the likelihood of +corruption or lost data if the system crashes while a tree is being modified. +If +.I cachesize +is 0 (no size is specified) a default cache is used. +.TP +psize +Page size is the size (in bytes) of the pages used for nodes in the tree. +The minimum page size is 512 bytes and the maximum page size is 64K. +If +.I psize +is 0 (no page size is specified) a page size is chosen based on the +underlying file system I/O block size. +.TP +lorder +The byte order for integers in the stored database metadata. +The number should represent the order as an integer; for example, +big endian order would be the number 4,321. +If +.I lorder +is 0 (no order is specified) the current host order is used. +.TP +maxkeypage +The maximum number of keys which will be stored on any single page. +Because of the way the btree data structure works, +.I maxkeypage +must always be greater than or equal to 2. +If +.I maxkeypage +is 0 (no maximum number of keys is specified) the page fill factor is +made as large as possible (which is almost invariably what is wanted). +.TP +minkeypage +The minimum number of keys which will be stored on any single page. +This value is used to determine which keys will be stored on overflow +pages, i.e. if a key or data item is longer than the pagesize divided +by the minkeypage value, it will be stored on overflow pages instead +of in the page itself. +If +.I minkeypage +is 0 (no minimum number of keys is specified) a value of 2 is used. +.TP +compare +Compare is the key comparison function. +It must return an integer less than, equal to, or greater than zero if the +first key argument is considered to be respectively less than, equal to, +or greater than the second key argument. +The same comparison function must be used on a given tree every time it +is opened. +If +.I compare +is NULL (no comparison function is specified), the keys are compared +lexically, with shorter keys considered less than longer keys. +.TP +prefix +Prefix is the prefix comparison function. +If specified, this routine must return the number of bytes of the second key +argument which are necessary to determine that it is greater than the first +key argument. +If the keys are equal, the key length should be returned. +Note, the usefulness of this routine is very data dependent, but, in some +data sets can produce significantly reduced tree sizes and search times. +If +.I prefix +is NULL (no prefix function is specified), +.B and +no comparison function is specified, a default lexical comparison routine +is used. +If +.I prefix +is NULL and a comparison routine is specified, no prefix comparison is +done. +.PP +If the file already exists (and the O_TRUNC flag is not specified), the +values specified for the parameters flags, lorder and psize are ignored +in favor of the values used when the tree was created. +.PP +Forward sequential scans of a tree are from the least key to the greatest. +.PP +Space freed up by deleting key/data pairs from the tree is never reclaimed, +although it is normally made available for reuse. +This means that the btree storage structure is grow-only. +The only solutions are to avoid excessive deletions, or to create a fresh +tree periodically from a scan of an existing one. +.PP +Searches, insertions, and deletions in a btree will all complete in +O lg base N where base is the average fill factor. +Often, inserting ordered data into btrees results in a low fill factor. +This implementation has been modified to make ordered insertion the best +case, resulting in a much better than normal page fill factor. +.SH "SEE ALSO" +.IR dbopen (3), +.IR hash (3), +.IR mpool (3), +.IR recno (3) +.br +.IR "The Ubiquitous B-tree" , +Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138. +.br +.IR "The Art of Computer Programming Vol. 3: Sorting and Searching" , +D.E. Knuth, 1968, pp 471-480. +.SH BUGS +Only big and little endian byte order is supported. diff --git a/usr/src/lib/libc/db/man/dbopen.3 b/usr/src/lib/libc/db/man/dbopen.3 index a17a696aa6..cd8120a39e 100644 --- a/usr/src/lib/libc/db/man/dbopen.3 +++ b/usr/src/lib/libc/db/man/dbopen.3 @@ -5,52 +5,44 @@ .\" .\" @(#)dbopen.3 5.17 (Berkeley) %G% .\" -.TH DB 3 "" +.TH DB 3 "" .UC 7 .SH NAME -btree_open, hash_open, recno_open \- database access methods +dbopen \- database access methods .SH SYNOPSIS .nf .ft B #include +#include #include DB * -btree_open(const char *file, int flags, int mode, +dbopen(const char *file, int flags, int mode, DBTYPE type, .ti +5 -const BTREEINFO * openinfo); - -DB * -hash_open(const char *file, int flags, int mode, -.ti +5 -const HASHINFO * openinfo); - -DB * -recno_open(const char *file, int flags, int mode, -.ti +5 -const RECNOINFO * openinfo); +const void *openinfo); .ft R .fi .SH DESCRIPTION -.IR Btree_open , -.IR hash_open , -and -.I recno_open -are access method interfaces to database files in btree, hashed, and -flat-file formats, respectively. +.IR Dbopen +is the library interface to database files. +The supported file formats are btree, hashed and record oriented. The btree format is a representation of a sorted, balanced tree structure. The hashed format is an extensible, dynamic hashing scheme. -The flat-file format is a UNIX file with fixed or variable length -lines. -These formats are described in more detail below. -.PP -Access to all file types is based on key/data pairs. +The flat-file format is a byte stream file with fixed or variable length +records. +The formats and file format specific information are described in detail +in their respective manual pages +.IR btree (3), +.IR hash (3) +and +.IR recno (3). .PP -Each routine opens +Dbopen opens .I file for reading and/or writing. -Databases never intended to be preserved on disk may be created by setting +Files never intended to be preserved on disk may be created by setting the file parameter to NULL. +.PP The .I flags and @@ -59,51 +51,60 @@ are as specified to the .IR open (2) routine, however, only the O_CREAT, O_EXCL, O_RDONLY, O_RDWR, O_TRUNC and O_WRONLY flags are meaningful. -The argument +.PP +The +.I type +argument is of type DBTYPE (as defined in the include file) and +may be set to DB_BTREE, DB_HASH or DB_RECNO. +.PP +The .I openinfo -is a pointer to an access method specific structure described below. +argument is a pointer to an access method specific structure described +in the access method's manual page. +If +.I openinfo +is NULL, each access method will use defaults appropriate for the system +and the access method. .PP -The open routines return a pointer to a DB structure on success and NULL -on error. -The DB structure contains at least the following fields: +.I Dbopen +returns a pointer to a DB structure on success and NULL on error. +The DB structure is defined in the include file, and contains at +least the following fields: .sp .nf typedef struct { .RS +DBTYPE type; int (*close)(const DB *db); -int (*sync)(const DB *db); int (*del)(const DB *db, const DBT *key, u_int flags); int (*get)(const DB *db, DBT *key, DBT *data, u_int flags); int (*put)(const DB *db, const DBT *key, const DBT *data, .ti +5 u_int flags); +int (*sync)(const DB *db); int (*seq)(const DB *db, DBT *key, DBT *data, u_int flags); -int type; -void *openinfo; .RE } DB; .fi .PP -The elements of this structure consist of a pointer to an access method -specific structure and a set of routines which perform various functions. -All of these routines take a pointer to a structure as returned by -one of the open routines, one or more pointers to key/data structures, -and, optionally, a flag value. -.TP -openinfo -A pointer to an internal structure specific to the access method. +These elements a database type and a set of functions performing various +actions. +These functions take a pointer to a structure as returned by +.IR dbopen , +and sometimes one or more pointers to key/data structures and a flag value. .TP type -The type of the underlying access method; either DB_BTREE, DB_HASH -or DB_RECNO. +The type of the underlying access method (and file format). .TP close A pointer to a routine to flush any cached information to disk, free any -allocated resources, and close the database file. -Since key/data pairs may be cached in memory, failing to close the -file with a +allocated resources, and close the underlying file(s). +Since key/data pairs may be cached in memory, failing to sync the file +with a .I close -routine may result in inconsistent or lost information. +or +.I sync +function may result in inconsistent or lost information. .I Close routines return -1 on error (setting .IR errno ) @@ -111,6 +112,16 @@ and 0 on success. .TP del A pointer to a routine to remove key/data pairs from the database. +.IP +The parameter +.I flag +may be set to the following value: +.RS +.TP +R_CURSOR +Delete the record referenced by the cursor. +.RE +.IP .I Delete routines return -1 on error (setting .IR errno ), @@ -146,9 +157,7 @@ Append the data immediately after the data referenced by creating a new key/data pair. (This implies that the access method is able to create new keys, i.e. the keys are ordered and independent, for example, record numbers. -Applicable only to the -.B RECNO -access method.) +Applicable only to the DB_RECNO access method.) .TP R_IBEFORE Insert the data immediately before the data referenced by @@ -156,17 +165,17 @@ Insert the data immediately before the data referenced by creating a new key/data pair. (This implies that the access method is able to create new keys, i.e. the keys are ordered and independent, for example, record numbers. -Applicable only to the -.B RECNO -access method.) +Applicable only to the DB_RECNO access method.) .TP R_NOOVERWRITE Enter the new key/data pair only if the key does not previously exist. -.TP -R_PUT -Enter the new key/data pair and replace any previously existing key. .RE .IP +The default behavior of the +.I put +routines is to enter the new key/data pair, replacing any previously +existing key. +.IP .I Put routines return -1 on error (setting .IR errno ), @@ -208,11 +217,7 @@ routines in that it sets the ``cursor'' to the location of the key as well. (This implies that the access method has a implicit order which does not change. -Applicable only to the -.B BTREE -and -.B RECNO -access methods.) +Applicable only to the DB_BTREE and DB_RECNO access methods.) .TP R_FIRST The first key/data pair of the database is returned. @@ -221,11 +226,7 @@ R_LAST The last key/data pair of the database is returned. (This implies that the access method has a implicit order which does not change. -Applicable only to the -.B BTREE -and -.B RECNO -access methods.) +Applicable only to the DB_BTREE and DB_RECNO access methods.) .TP R_NEXT Retrieve the key/data pair immediately after the key/data pair most recently @@ -252,21 +253,16 @@ is set to R_PREV the first time the routine is called, the last key/data pair of the database is returned. (This implies that the access method has a implicit order which does not change. -Applicable only to the -.B BTREE -and -.B RECNO -access methods.) +Applicable only to the DB_BTREE and DB_RECNO access methods.) .RE .IP .I Seq routines return -1 on error (setting .IR errno ), 0 on success, 1 if there are no more key/data pairs available. -If the -.B RECNO -access method is being used, and if the database file is a character special -file and no complete key/data pairs are currently available, the +If the DB_RECNO access method is being used, and if the database file +is a character special file and no complete key/data pairs are currently +available, the .I seq routines return 2. .TP @@ -299,336 +295,15 @@ A pointer to a byte string. size The length of the byte string. .PP -Key/data strings must fit into available memory. -.SH BTREE -One of the access methods is a btree: a sorted, balanced tree structure -with associated key/data pairs. -.PP -The access method specific data structure provided to -.I btree_open -is as follows: -.PP -typedef struct { -.RS -u_long flags; -.br -u_int psize; -.br -u_int cachesize; -.br -int (*compare)(const void *, const void *); -.br -int lorder; -.RE -} BTREEINFO; -.PP -The elements of this structure are defined as follows: -.TP -flags -The flag value is specified by -.IR or 'ing -any of the following values: -.RS -.TP -R_DUP -On insertion, -if the key to be inserted already exists, -permit insertion anyway. -This flag permits duplicate keys in the tree. -By default, -duplicates are not permitted, -and attempts to insert them will fail. -Note, the order of retrieval of key/data pairs with duplicate keys is -undefined. -.RE -.TP -cachesize -A suggested maximum size, in bytes, of the memory cache. -Setting this value to zero specifies that an appropriate amount of memory -should be used. -Since every search examines the root page of the tree, caching the most -recently used pages substantially improves access time. -In addition, physical writes are delayed as long as possible, so a moderate -cache can reduce the number of I/O operations significantly. -Obviously, using a cache increases the likelihood of corruption or lost data -if the system crashes while a tree is being modified. -However, caching 10 -pages decreases the creation time of a large tree by between two and three -orders of magnitude. -.TP -compare -Compare is a user defined comparison function. -It must return an integer less than, equal to, or greater than zero if the -first argument is considered to be respectively less than, equal to, or -greater than the second. -The same comparison function must be used on a given tree every time it -is opened. -If no comparison function is specified, -.IR strcmp (3) -is used. -.TP -lorder -The byte order for 4-byte integers in the stored database metadata. -The number should represent the order as an integer; for example, -big endian order would be the number 4,321. -If -.I lorder -is 0 (no order is specified) the current host order is used. -If the file already exists, the specified value is ignored and the -value specified when the tree was created is used. -(Obviously, portability of the data forming the key/data pairs is the -concern of the application program.) -.TP -psize -Page size is the size in bytes of the pages used for nodes in the tree. -If the file already exists, the specified value is ignored and the -value specified when the tree was created is used. -If -.I psize -is zero, an appropriate page size is chosen (based on the system memory -and/or file system constraints), but will never be less than 512 bytes. -.PP -If the pointer to the -.I openinfo -data structure is NULL, the -.I btree_open -routine will use appropriate values. -.PP -If the database file already exists, and the O_TRUNC flag is not specified -to -.IR btree_open , -the parameter -.I psize -ignored. -.PP -Key structures may reference byte strings of slightly less than one-half the -tree's page size only (see -.IR psize ). -Data structures may reference byte strings of essentially unlimited length. -.PP -Searches, insertions, and deletions in a btree will all complete in -O lg N. -.PP -Forward sequential scans of a tree are from the least key to the greatest. -.PP -Space freed up by deleting key/data pairs from a btree is never reclaimed, -although it is normally made available for reuse. -The exception to this is that space occupied by large data items (those -greater than one quarter the size of a page) is neither reclaimed nor reused. -This means that the btree storage structure is grow-only. -The only solutions are to avoid excessive deletions, or to create a fresh -tree periodically from a scan of an existing one. -.SH HASH -One of the access methods is hashed access and storage. -The access method specific data structure provided to -.I hash_open -is as follows: -.sp -typedef struct { -.RS -u_long (*hash)(const void *, const size_t); -.br -u_int cachesize; -.br -int bsize; -.br -int ffactor; -.br -int lorder; -.br -int nelem; -.RE -} HASHINFO; -.PP -The elements of this structure are defined as follows: -.TP -bsize -.I Bsize -defines the hash table bucket size, and is, by default, 256 bytes. -It may be preferable to increase the page size for disk-resident tables and -tables with large data items. -.TP -cachesize -A suggested maximum size, in bytes, of the memory cache. -Setting this value to zero specifies that an appropriate amount of memory -should be used. -.TP -ffactor -.I Ffactor -indicates a desired density within the hash table. -It is an approximation of the number of keys allowed to accumulate in any -one bucket, determining when the hash table grows or shrinks. -The default value is 8. -.TP -hash -.I Hash -is a user defined hash function. -Since no hash function performs equally well on all possible data, the -user may find that the built-in hash function does poorly on a particular -data set. -User specified hash functions must take two arguments (a pointer to a byte -string and a length) and return an u_long to be used as the hash value. -.TP -lorder -The byte order for 4-byte integers in the stored database metadata. -The number should represent the order as an integer; for example, -big endian order would be the number 4,321. -If -.I lorder -is 0 (no order is specified) the current host order is used. -If the file already exists, the specified value is ignored and the -value specified when the tree was created is used. -(Obviously, portability of the data forming the key/data pairs is the -concern of the application program.) -.TP -nelem -.I Nelem -is an estimate of the final size of the hash table. -If not set, the default value is 1. -If not set or set too low, hash tables will expand gracefully as keys -are entered, although a slight performance degradation may be noticed. -.PP -If the pointer to the -.I openinfo -data structure is NULL, the -.I hash_open -routine will use appropriate values. -.PP -If the hash table already exists, and the O_TRUNC flag is not -specified to -.IR hash_open , -the parameters -.IR bsize , -.IR ffactor , -and -.I nelem -are ignored. -.PP -If a hash function is specified, -.I hash_open -will attempt to determine if the hash function specified is the same as -the one with which the database was created, and will fail if it is not. -.PP -Both key and data structures may reference byte strings of essentially -unlimited length. -.PP -Backward compatible interfaces to the routines described in -.IR dbm (3), -.IR hsearch (3), -and -.IR ndbm (3) -are provided, however, these interfaces are not compatible with -previous file formats. -.SH RECNO -One of the access methods is either variable or fixed-length records, -the former delimited by a specific byte value. -The access method specific data structure provided to -.I recno_open -is as follows: -.sp -typedef struct { -.RS -u_long flags; -.br -u_int cachesize; -.br -size_t reclen; -.br -u_char bval; -.RE -} RECNOINFO; -.PP -The elements of this structure are defined as follows: -.TP -flags -The flag value is specified by -.IR or 'ing -any of the following values: -.RS -.TP -R_FIXEDLEN -The records are fixed-length, not byte delimited. -The structure element -.I reclen -specifies the length of the record, and the structure element -.I bval -is used as the pad character. -.TP -R_SNAPSHOT -This flag requires that a snapshot of the file be taken when -.I recno_open -is called, instead of permitting any unmodified records to be -read from the original file. -.RE -.TP -cachesize -A suggested maximum size, in bytes, of the memory cache. -Setting this value to zero specifies that an appropriate amount of memory -should be used. -.TP -reclen -The length of a fixed-length record. -.TP -bval -The delimiting byte to be used to mark the end of a record for -variable-length records, and the pad character for fixed-length -records. -.PP -Variable-length and fixed-length data files require -.I key -structures to reference the following structure: -.sp -typedef struct { -.RS -u_long length; -.br -u_long number; -.br -u_long offset; -.br -u_char valid; -.RE -} RECNOKEY; -.PP -The elements of this structure are defined as follows: -.TP -length -The length of the record. -.TP -number -The record number. -.TP -offset -The offset in the file at which the record is located. -.TP -valid -A flag value which indicates the validity of the other fields in the -structure. -The flag value is specified by -.IR or 'ing -one or more of the following values: -.RS -.TP -R_LENGTH -The record length is valid. -.TP -R_NUMBER -The record number is valid. -.TP -R_OFFSET -The byte offset is valid. -.RE -.PP -If the record retrieval is successful, the record number, byte offset and -record length are set in the RECNOKEY structure referenced by the caller's -.I key -structure. -.PP -Data structures may reference byte strings of essentially unlimited length. +Key and data byte strings may reference strings of essentially unlimited +length although any two of them must fit into available memory at the same +time. +It should be noted that the access methods provide no guarantees about +byte string alignment. .SH ERRORS The -.I open -routines may fail and set +.I dbopen +routine may fail and set .I errno for any of the errors specified for the library routines .IR open (2) @@ -637,9 +312,7 @@ and or the following: .TP [EFTYPE] -A file used by one of the -.I open -routines is incorrectly formatted. +A file is incorrectly formatted. .TP [EINVAL] A parameter has been specified (hash function, pad byte etc.) that is @@ -680,16 +353,13 @@ routines may fail and set for any of the errors specified for the library routine .IR fsync (2). .SH "SEE ALSO" -.IR "Dynamic Hash Tables" , -Per-Ake Larson, Communications of the ACM, April 1988. -.br -.IR "A New Hash Package for UNIX" , -Margo Seltzer, USENIX Proceedings, Winter 1991. +.IR btree (3), +.IR hash (3), +.IR mpool (3), +.IR recno (3) .SH BUGS The typedef DBT is a mnemonic for ``data base thang'', and was used because noone could think of a reasonable name that wasn't already used. .PP None of the access methods provide any form of concurrent access, locking, or transactions. -.PP -Only big and little endian byte order is supported. diff --git a/usr/src/lib/libc/db/man/hash.3 b/usr/src/lib/libc/db/man/hash.3 new file mode 100644 index 0000000000..21dbd594f9 --- /dev/null +++ b/usr/src/lib/libc/db/man/hash.3 @@ -0,0 +1,125 @@ +.\" Copyright (c) 1990 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" %sccs.include.redist.man% +.\" +.\" @(#)hash.3 5.1 (Berkeley) %G% +.\" +.TH HASH 3 "" +.UC 7 +.SH NAME +hash \- hash database access method +.SH SYNOPSIS +.nf +.ft B +#include +#include +.ft R +.fi +.SH DESCRIPTION +The routine +.IR dbopen +is the library interface to database files. +One of the supported file formats is hash files. +The general description of the database access methods is in +.IR dbopen (3), +this manual page describes only the hash specific information. +.PP +The hash data structure is an extensible, dynamic hashing scheme. +.PP +The access method specific data structure provided to +.I dbopen +is defined in the include file as follows: +.sp +typedef struct { +.RS +int bsize; +.br +u_int cachesize; +.br +int ffactor; +.br +u_long (*hash)(const void *, const size_t); +.br +int lorder; +.br +int nelem; +.RE +} HASHINFO; +.PP +The elements of this structure are as follows: +.TP +bsize +.I Bsize +defines the hash table bucket size, and is, by default, 256 bytes. +It may be preferable to increase the page size for disk-resident tables +and tables with large data items. +.TP +cachesize +A suggested maximum size, in bytes, of the memory cache. +This value is +.B only +advisory, and the access method will allocate more memory rather +than fail. +.TP +ffactor +.I Ffactor +indicates a desired density within the hash table. +It is an approximation of the number of keys allowed to accumulate in any +one bucket, determining when the hash table grows or shrinks. +The default value is 8. +.TP +hash +.I Hash +is a user defined hash function. +Since no hash function performs equally well on all possible data, the +user may find that the built-in hash function does poorly on a particular +data set. +User specified hash functions must take two arguments (a pointer to a byte +string and a length) and return an u_long to be used as the hash value. +.TP +lorder +The byte order for integers in the stored database metadata. +The number should represent the order as an integer; for example, +big endian order would be the number 4,321. +If +.I lorder +is 0 (no order is specified) the current host order is used. +If the file already exists, the specified value is ignored and the +value specified when the tree was created is used. +.TP +nelem +.I Nelem +is an estimate of the final size of the hash table. +If not set or set too low, hash tables will expand gracefully as keys +are entered, although a slight performance degradation may be noticed. +The default value is 1. +.PP +If the file already exists (and the O_TRUNC flag is not specified), the +values specified for the parameters bsize, ffactor, lorder and nelem are +ignored and the values specified when the tree was created are used. +.PP +If a hash function is specified, +.I hash_open +will attempt to determine if the hash function specified is the same as +the one with which the database was created, and will fail if it is not. +.PP +Backward compatible interfaces to the routines described in +.IR dbm (3), +and +.IR ndbm (3) +are provided, however, these interfaces are not compatible with +previous file formats. +.SH "SEE ALSO" +.IR btree (3), +.IR dbopen (3), +.IR mpool (3), +.IR recno (3) +.br +.IR "Dynamic Hash Tables" , +Per-Ake Larson, Communications of the ACM, April 1988. +.br +.IR "A New Hash Package for UNIX" , +Margo Seltzer, USENIX Proceedings, Winter 1991. +.SH BUGS +Only big and little endian byte order is supported. diff --git a/usr/src/lib/libc/db/man/mpool.3 b/usr/src/lib/libc/db/man/mpool.3 new file mode 100644 index 0000000000..e6ff2e8631 --- /dev/null +++ b/usr/src/lib/libc/db/man/mpool.3 @@ -0,0 +1,193 @@ +.\" Copyright (c) 1990 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" %sccs.include.redist.man% +.\" +.\" @(#)mpool.3 5.1 (Berkeley) %G% +.\" +.TH MPOOL 3 "" +.UC 7 +.SH NAME +mpool \- shared memory buffer pool +.SH SYNOPSIS +.nf +.ft B +#include +#include + +MPOOL * +mpool_open (DBT *key, int fd, pgno_t pagesize, pgno_t maxcache); + +void +mpool_filter (MPOOL *mp, void (*pgin)(void *, pgno_t, void *), +.ti +5 +void (*pgout)(void *, pgno_t, void *), void *pgcookie); + +void * +mpool_new (MPOOL *mp, pgno_t *pgnoaddr); + +void * +mpool_get (MPOOL *mp, pgno_t pgno, u_int flags); + +int +mpool_put (MPOOL *mp, void *pgaddr, u_int flags); + +int +mpool_sync (MPOOL *mp); + +int +mpool_close (MPOOL *mp); +.ft R +.fi +.SH DESCRIPTION +.IR Mpool +is the library interface intended to provide page oriented buffer management +of files. +The buffers may be shared between processes. +.PP +The function +.I mpool_open +initializes a memory pool. +The +.I key +argument is the byte string used to negotiate between multiple +processes wishing to share buffers. +If the file buffers are mapped in shared memory, all processes using +the same key will share the buffers. +If +.I key +is NULL, the buffers are mapped into private memory. +The +.I fd +argument is a file descriptor for the underlying file, which must be seekable. +If +.I key +is non-NULL and matches a file already being mapped, the +.I fd +argument is ignored. +.PP +The +.I pagesize +argument is the size, in bytes, of the pages into which the file is broken up. +The +.I maxcache +argument is the maximum number of pages from the underlying file to cache +at any one time. +This value is not relative to the number of processes which share a file's +buffers, but will be the largest value specified by any of the processes +sharing the file. +.PP +The +.I mpool_filter +function is intended to make transparent input and output processing of the +pages possible. +If the +.I pgin +function is specified, it is called each time a buffer is read into the memory +pool from the backing file. +If the +.I pgout +function is specified, it is called each time a buffer is written into the +backing file. +Both functions are are called with the +.I pgcookie +pointer, the page number and a pointer to the page to being read or written. +.PP +The function +.I mpool_new +takes an MPOOL pointer and an address as arguments. +If a new page can be allocated, a pointer to the page is returned and +the page number is stored into the +.I pgnoaddr +address. +Otherwise, NULL is returned and errno is set. +.PP +The function +.I mpool_get +takes a MPOOL pointer and a page number as arguments. +If the page exists, a pointer to the page is returned. +Otherwise, NULL is returned and errno is set. +The flags parameter is not currently used. +.PP +The function +.I mpool_put +unpins the page referenced by +.IR pgaddr . +.I Pgaddr +must be an address previously returned by +.I mpool_get +or +.IR mpool_new . +The flag value is specified by +.IR or 'ing +any of the following values: +.TP +MPOOL_DIRTY +The page has been modified and needs to be written to the backing file. +.PP +.I Mpool_put +returns 0 on success and -1 if an error occurs. +.PP +The function +.I mpool_sync +writes all modified pages associated with the MPOOL pointer to the +backing file. +.I Mpool_sync +returns 0 on success and -1 if an error occurs. +.PP +The +.I mpool_close +function free's up any allocated memory associated with the memory pool +cookie. +Modified pages are +.B not +written to the backing file. +.I Mpool_close +returns 0 on success and -1 if an error occurs. +.SH ERRORS +The +.I mpool_open +function may fail and set +.I errno +for any of the errors specified for the library routine +.IR malloc (3). +.PP +The +.I mpool_get +function may fail and set +.I errno +for the following: +.TP 15 +[EINVAL] +The requested record doesn't exist. +.PP +The +.I mpool_new +and +.I mpool_get +functions may fail and set +.I errno +for any of the errors specified for the library routines +.IR read (2) , +.IR write (2) , +and +.IR malloc (3). +.PP +The +.I mpool_sync +function may fail and set +.I errno +for any of the errors specified for the library routine +.IR write (2). +.PP +The +.I mpool_close +function may fail and set +.I errno +for any of the errors specified for the library routine +.IR free (3). +.SH "SEE ALSO" +.IR db (3), +.IR btree (3), +.IR hash (3), +.IR recno (3) diff --git a/usr/src/lib/libc/db/man/recno.3 b/usr/src/lib/libc/db/man/recno.3 new file mode 100644 index 0000000000..b9f3523365 --- /dev/null +++ b/usr/src/lib/libc/db/man/recno.3 @@ -0,0 +1,125 @@ +.\" Copyright (c) 1990 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" %sccs.include.redist.man% +.\" +.\" @(#)recno.3 5.1 (Berkeley) %G% +.\" +.TH RECNO 3 "" +.UC 7 +.SH NAME +recno \- record number database access method +.SH SYNOPSIS +.nf +.ft B +#include +#include +.ft R +.fi +.SH DESCRIPTION +The routine +.IR dbopen +is the library interface to database files. +One of the supported file formats is record number files. +The general description of the database access methods is in +.IR dbopen (3), +this manual page describes only the recno specific information. +.PP +The record number data structure is either variable or fixed-length +records stored in a flat-file format. +.PP +The recno access method specific data structure provided to +.I dbopen +is defined in the include file as follows: +.PP +typedef struct { +.RS +u_char bval; +.br +u_int cachesize; +.br +u_long flags; +.br +int lorder; +.br +size_t reclen; +.RE +} RECNOINFO; +.PP +The elements of this structure are defined as follows: +.TP +bval +The delimiting byte to be used to mark the end of a record for +variable-length records, and the pad character for fixed-length +records. +If no value is specified, newlines (``\en'') are used to mark the end +of variable-length records and fixed-length records are padded with +spaces. +.TP +cachesize +A suggested maximum size, in bytes, of the memory cache. +This value is +.B only +advisory, and the access method will allocate more memory rather than fail. +.TP +flags +The flag value is specified by +.IR or 'ing +any of the following values: +.RS +.TP +R_FIXEDLEN +The records are fixed-length, not byte delimited. +The structure element +.I reclen +specifies the length of the record, and the structure element +.I bval +is used as the pad character. +.TP +R_NOKEY +In the interface specified by +.IR dbopen , +the sequential record retrieval fills in both the caller's key and +data structures. +If the R_NOKEY flag is specified, the +.I cursor +routines are not required to fill in the key structure. +This permits applications to retrieve records at the end of files without +reading all of the intervening records. +.TP +R_SNAPSHOT +This flag requires that a snapshot of the file be taken when +.I dbopen +is called, instead of permitting any unmodified records to be read from +the original file. +.RE +.TP +lorder +The byte order for integers in the stored database metadata. +The number should represent the order as an integer; for example, +big endian order would be the number 4,321. +If +.I lorder +is 0 (no order is specified) the current host order is used. +.TP +reclen +The length of a fixed-length record. +.PP +In the interface specified by +.IR dbopen , +using the +.I put +interface to create a new record may cause the creation of multiple, +empty records if the record number is more than one greater than the +largest record currently in the database. +.SH "SEE ALSO" +.IR dbopen (3), +.IR hash (3), +.IR mpool (3), +.IR recno (3) +.br +.IR "Document Processing in a Relational Database System" , +Michael Stonebraker, Heidi Stettner, Joseph Kalash, Antonin Guttman, +Nadene Lynn, Memorandum No. UCB/ERL M82/32, May 1982. +.SH BUGS +Only big and little endian byte order is supported. -- 2.20.1