| blob | 8d93c38ad4037b0b06f687bbd2a740470123842d |
1 .\" Copyright (c) 1990 The Regents of the University of California.
2 .\" All rights reserved.
3 .\"
4 .\" Redistribution and use in source and binary forms, with or without
5 .\" modification, are permitted provided that the following conditions
6 .\" are met:
7 .\" 1. Redistributions of source code must retain the above copyright
8 .\" notice, this list of conditions and the following disclaimer.
9 .\" 2. Redistributions in binary form must reproduce the above copyright
10 .\" notice, this list of conditions and the following disclaimer in the
11 .\" documentation and/or other materials provided with the distribution.
12 .\" 3. All advertising materials mentioning features or use of this software
13 .\" must display the following acknowledgement:
14 .\" This product includes software developed by the University of
15 .\" California, Berkeley and its contributors.
16 .\" 4. Neither the name of the University nor the names of its contributors
17 .\" may be used to endorse or promote products derived from this software
18 .\" without specific prior written permission.
19 .\"
20 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 .\" SUCH DAMAGE.
31 .\"
32 .\" @(#)db.3 5.16 (Berkeley) 4/2/91
33 .\"
34 .TH DB 3 "April 2, 1991"
35 .UC 7
36 .SH NAME
37 btree_open, hash_open, recno_open \- database access methods
38 .SH SYNOPSIS
39 .nf
40 .ft B
41 #include <sys/types.h>
42 #include <db.h>
44 DB *
45 btree_open(const char *file, int flags, int mode,
46 .ti +5
47 const BTREEINFO * openinfo);
49 DB *
50 hash_open(const char *file, int flags, int mode,
51 .ti +5
52 const HASHINFO * openinfo);
54 DB *
55 recno_open(const char *file, int flags, int mode,
56 .ti +5
57 const RECNOINFO * openinfo);
58 .ft R
59 .fi
60 .SH DESCRIPTION
61 .IR Btree_open ,
62 .IR hash_open ,
63 and
64 .I recno_open
65 are access method interfaces to database files in btree, hashed, and
66 flat-file formats, respectively.
67 The btree format is a representation of a sorted, balanced tree structure.
68 The hashed format is an extensible, dynamic hashing scheme.
69 The flat-file format is a UNIX file with fixed or variable length
70 lines.
71 These formats are described in more detail below.
72 .PP
73 Access to all file types is based on key/data pairs.
74 .PP
75 Each routine opens
76 .I file
77 for reading and/or writing.
78 Databases never intended to be preserved on disk may be created by setting
79 the file parameter to NULL.
80 The
81 .I flags
82 and
83 .I mode arguments
84 are as specified to the
85 .IR open (2)
86 routine, however, only the O_CREAT, O_EXCL, O_RDONLY, O_RDWR, O_TRUNC
87 and O_WRONLY flags are meaningful.
88 The argument
89 .I openinfo
90 is a pointer to an access method specific structure described below.
91 .PP
92 The open routines return a pointer to a DB structure on success and NULL
93 on error.
94 The DB structure contains at least the following fields:
95 .sp
96 .nf
97 typedef struct {
98 .RS
99 int (*close)(const DB *db);
100 int (*sync)(const DB *db);
101 int (*del)(const DB *db, const DBT *key, u_int flags);
102 int (*get)(const DB *db, DBT *key, DBT *data, u_int flags);
103 int (*put)(const DB *db, const DBT *key, const DBT *data,
104 .ti +5
105 u_int flags);
106 int (*seq)(const DB *db, DBT *key, DBT *data, u_int flags);
107 int type;
108 void *openinfo;
109 .RE
110 } DB;
111 .fi
112 .PP
113 The elements of this structure consist of a pointer to an access method
114 specific structure and a set of routines which perform various functions.
115 All of these routines take a pointer to a structure as returned by
116 one of the open routines, one or more pointers to key/data structures,
117 and, optionally, a flag value.
118 .TP
119 openinfo
120 A pointer to an internal structure specific to the access method.
121 .TP
122 type
123 The type of the underlying access method; either DB_BTREE, DB_HASH
124 or DB_RECNO.
125 .TP
126 close
127 A pointer to a routine to flush any cached information to disk, free any
128 allocated resources, and close the database file.
129 Since key/data pairs may be cached in memory, failing to close the
130 file with a
131 .I close
132 routine may result in inconsistent or lost information.
133 .I Close
134 routines return -1 on error (setting
135 .IR errno )
136 and 0 on success.
137 .TP
138 del
139 A pointer to a routine to remove key/data pairs from the database.
140 .I Delete
141 routines return -1 on error (setting
142 .IR errno ),
143 0 on success, and 1 if the specified
144 .I key
145 was not in the file.
146 .TP
147 get
148 A pointer to a routine which is the interface for keyed retrieval from
149 the database.
150 The address and length of the data associated with the specified
151 .I key
152 are returned in the structure referenced by
153 .IR data .
154 .I Get
155 routines return -1 on error (setting
156 .IR errno ),
157 0 on success, and 1 if the
158 .I key
159 was not in the file.
160 .TP
161 put
162 A pointer to a routine to store key/data pairs in the database.
163 .IP
164 The parameter
165 .I flag
166 must be set to one of the following values:
167 .RS
168 .TP
169 R_IAFTER
170 Append the data immediately after the data referenced by
171 .IR key ,
172 creating a new key/data pair.
173 (This implies that the access method is able to create new keys,
174 i.e. the keys are ordered and independent, for example, record numbers.
175 Applicable only to the
176 .B RECNO
177 access method.)
178 .TP
179 R_IBEFORE
180 Insert the data immediately before the data referenced by
181 .IR key ,
182 creating a new key/data pair.
183 (This implies that the access method is able to create new keys,
184 i.e. the keys are ordered and independent, for example, record numbers.
185 Applicable only to the
186 .B RECNO
187 access method.)
188 .TP
189 R_NOOVERWRITE
190 Enter the new key/data pair only if the key does not previously exist.
191 .TP
192 R_PUT
193 Enter the new key/data pair and replace any previously existing key.
194 .RE
195 .IP
196 .I Put
197 routines return -1 on error (setting
198 .IR errno ),
199 0 on success, and 1 if the R_NOOVERWRITE
200 .I flag
201 was set and the key already exists in the file.
202 .TP
203 seq
204 A pointer to a routine which is the interface for sequential
205 retrieval from the database.
206 The address and length of the key are returned in the structure
207 referenced by
208 .IR key ,
209 and the address and length of the data are returned in the
210 structure referenced
211 by
212 .IR data .
213 .IP
214 Sequential key/data pair retrieval may begin at any time, and the
215 position of the ``cursor'' is not affected by calls to the
216 .IR del ,
217 .IR get ,
218 .IR put ,
219 or
220 .I sync
221 routines.
222 Modifications to the database during a sequential scan will be reflected
223 in the scan, i.e. records inserted behind the cursor will not be returned
224 while records inserted in front of the cursor will be returned.
225 .IP
226 The flag value must be set to one of the following values:
227 .RS
228 .TP
229 R_CURSOR
230 The data associated with the specified key is returned.
231 This differs from the
232 .I get
233 routines in that it sets the ``cursor'' to the location of the
234 key as well.
235 (This implies that the access method has a implicit order which does
236 not change.
237 Applicable only to the
238 .B BTREE
239 and
240 .B RECNO
241 access methods.)
242 .TP
243 R_FIRST
244 The first key/data pair of the database is returned.
245 .TP
246 R_LAST
247 The last key/data pair of the database is returned.
248 (This implies that the access method has a implicit order which does
249 not change.
250 Applicable only to the
251 .B BTREE
252 and
253 .B RECNO
254 access methods.)
255 .TP
256 R_NEXT
257 Retrieve the key/data pair immediately after the key/data pair most recently
258 retrieved using the
259 .I seq
260 routine.
261 The cursor is moved to the returned key/data pair.
262 If
263 .I flag
264 is set to R_NEXT the first time the
265 .I seq
266 routine is called, the first key/data pair of the database is returned.
267 .TP
268 R_PREV
269 Retrieve the key/data pair immediately before the key/data pair most recently
270 retrieved using the
271 .I seq
272 routine.
273 The cursor is moved to the returned key/data pair.
274 If
275 .I flag
276 is set to R_PREV the first time the
277 .I seq
278 routine is called, the last key/data pair of the database is returned.
279 (This implies that the access method has a implicit order which does
280 not change.
281 Applicable only to the
282 .B BTREE
283 and
284 .B RECNO
285 access methods.)
286 .RE
287 .IP
288 .I Seq
289 routines return -1 on error (setting
290 .IR errno ),
291 0 on success, 1 if there are no more key/data pairs available.
292 If the
293 .B RECNO
294 access method is being used, and if the database file is a character special
295 file and no complete key/data pairs are currently available, the
296 .I seq
297 routines return 2.
298 .TP
299 sync
300 A pointer to a routine to flush any cached information to disk.
301 If the database is in memory only, the
302 .I sync
303 routine has no effect and will always succeed.
304 .I Sync
305 routines return -1 on error (setting
306 .IR errno )
307 and 0 on success.
308 .SH "KEY/DATA PAIRS"
309 Access to all file types is based on key/data pairs.
310 Both keys and data are represented by the following data structure:
311 .PP
312 typedef struct {
313 .RS
314 void *data;
315 .br
316 size_t size;
317 .RE
318 } DBT;
319 .PP
320 The elements of the DBT structure are defined as follows:
321 .TP
322 data
323 A pointer to a byte string.
324 .TP
325 size
326 The length of the byte string.
327 .PP
328 Key/data strings must fit into available memory.
329 .SH BTREE
330 One of the access methods is a btree: a sorted, balanced tree structure
331 with associated key/data pairs.
332 .PP
333 The access method specific data structure provided to
334 .I btree_open
335 is as follows:
336 .PP
337 typedef struct {
338 .RS
339 u_long flags;
340 .br
341 u_int psize;
342 .br
343 u_int cachesize;
344 .br
345 int (*compare)(const void *, const void *);
346 .br
347 int lorder;
348 .RE
349 } BTREEINFO;
350 .PP
351 The elements of this structure are defined as follows:
352 .TP
353 flags
354 The flag value is specified by
355 .IR or 'ing
356 any of the following values:
357 .RS
358 .TP
359 R_DUP
360 On insertion,
361 if the key to be inserted already exists,
362 permit insertion anyway.
363 This flag permits duplicate keys in the tree.
364 By default,
365 duplicates are not permitted,
366 and attempts to insert them will fail.
367 Note, the order of retrieval of key/data pairs with duplicate keys is
368 undefined.
369 .RE
370 .TP
371 cachesize
372 A suggested maximum size, in bytes, of the memory cache.
373 Setting this value to zero specifies that an appropriate amount of memory
374 should be used.
375 Since every search examines the root page of the tree, caching the most
376 recently used pages substantially improves access time.
377 In addition, physical writes are delayed as long as possible, so a moderate
378 cache can reduce the number of I/O operations significantly.
379 Obviously, using a cache increases the likelihood of corruption or lost data
380 if the system crashes while a tree is being modified.
381 However, caching 10
382 pages decreases the creation time of a large tree by between two and three
383 orders of magnitude.
384 .TP
385 compare
386 Compare is a user defined comparison function.
387 It must return an integer less than, equal to, or greater than zero if the
388 first argument is considered to be respectively less than, equal to, or
389 greater than the second.
390 The same comparison function must be used on a given tree every time it
391 is opened.
392 If no comparison function is specified,
393 .IR strcmp (3)
394 is used.
395 .TP
396 lorder
397 The byte order for 4-byte integers in the stored database metadata.
398 The number should represent the order as an integer; for example,
399 big endian order would be the number 4,321.
400 If
401 .I lorder
402 is 0 (no order is specified) the current host order is used.
403 If the file already exists, the specified value is ignored and the
404 value specified when the tree was created is used.
405 (Obviously, portability of the data forming the key/data pairs is the
406 concern of the application program.)
407 .TP
408 psize
409 Page size is the size in bytes of the pages used for nodes in the tree.
410 If the file already exists, the specified value is ignored and the
411 value specified when the tree was created is used.
412 If
413 .I psize
414 is zero, an appropriate page size is chosen (based on the system memory
415 and/or file system constraints), but will never be less than 512 bytes.
416 .PP
417 If the pointer to the
418 .I openinfo
419 data structure is NULL, the
420 .I btree_open
421 routine will use appropriate values.
422 .PP
423 If the database file already exists, and the O_TRUNC flag is not specified
424 to
425 .IR btree_open ,
426 the parameter
427 .I psize
428 ignored.
429 .PP
430 Key structures may reference byte strings of slightly less than one-half the
431 tree's page size only (see
432 .IR psize ).
433 Data structures may reference byte strings of essentially unlimited length.
434 .PP
435 Searches, insertions, and deletions in a btree will all complete in
436 O lg N.
437 .PP
438 Forward sequential scans of a tree are from the least key to the greatest.
439 .PP
440 Space freed up by deleting key/data pairs from a btree is never reclaimed,
441 although it is normally made available for reuse.
442 The exception to this is that space occupied by large data items (those
443 greater than one quarter the size of a page) is neither reclaimed nor reused.
444 This means that the btree storage structure is grow-only.
445 The only solutions are to avoid excessive deletions, or to create a fresh
446 tree periodically from a scan of an existing one.
447 .SH HASH
448 One of the access methods is hashed access and storage.
449 The access method specific data structure provided to
450 .I hash_open
451 is as follows:
452 .sp
453 typedef struct {
454 .RS
455 u_long (*hash)(const void *, const size_t);
456 .br
457 u_int cachesize;
458 .br
459 int bsize;
460 .br
461 int ffactor;
462 .br
463 int lorder;
464 .br
465 int nelem;
466 .RE
467 } HASHINFO;
468 .PP
469 The elements of this structure are defined as follows:
470 .TP
471 bsize
472 .I Bsize
473 defines the hash table bucket size, and is, by default, 256 bytes.
474 It may be preferable to increase the page size for disk-resident tables and
475 tables with large data items.
476 .TP
477 cachesize
478 A suggested maximum size, in bytes, of the memory cache.
479 Setting this value to zero specifies that an appropriate amount of memory
480 should be used.
481 .TP
482 ffactor
483 .I Ffactor
484 indicates a desired density within the hash table.
485 It is an approximation of the number of keys allowed to accumulate in any
486 one bucket, determining when the hash table grows or shrinks.
487 The default value is 8.
488 .TP
489 hash
490 .I Hash
491 is a user defined hash function.
492 Since no hash function performs equally well on all possible data, the
493 user may find that the built-in hash function does poorly on a particular
494 data set.
495 User specified hash functions must take two arguments (a pointer to a byte
496 string and a length) and return an u_long to be used as the hash value.
497 .TP
498 lorder
499 The byte order for 4-byte integers in the stored database metadata.
500 The number should represent the order as an integer; for example,
501 big endian order would be the number 4,321.
502 If
503 .I lorder
504 is 0 (no order is specified) the current host order is used.
505 If the file already exists, the specified value is ignored and the
506 value specified when the tree was created is used.
507 (Obviously, portability of the data forming the key/data pairs is the
508 concern of the application program.)
509 .TP
510 nelem
511 .I Nelem
512 is an estimate of the final size of the hash table.
513 If not set, the default value is 1.
514 If not set or set too low, hash tables will expand gracefully as keys
515 are entered, although a slight performance degradation may be noticed.
516 .PP
517 If the pointer to the
518 .I openinfo
519 data structure is NULL, the
520 .I hash_open
521 routine will use appropriate values.
522 .PP
523 If the hash table already exists, and the O_TRUNC flag is not
524 specified to
525 .IR hash_open ,
526 the parameters
527 .IR bsize ,
528 .IR ffactor ,
529 and
530 .I nelem
531 are ignored.
532 .PP
533 If a hash function is specified,
534 .I hash_open
535 will attempt to determine if the hash function specified is the same as
536 the one with which the database was created, and will fail if it is not.
537 .PP
538 Both key and data structures may reference byte strings of essentially
539 unlimited length.
540 .PP
541 Backward compatible interfaces to the routines described in
542 .IR dbm (3),
543 .IR hsearch (3),
544 and
545 .IR ndbm (3)
546 are provided, however, these interfaces are not compatible with
547 previous file formats.
548 .SH RECNO
549 One of the access methods is either variable or fixed-length records,
550 the former delimited by a specific byte value.
551 The access method specific data structure provided to
552 .I recno_open
553 is as follows:
554 .sp
555 typedef struct {
556 .RS
557 u_long flags;
558 .br
559 u_int cachesize;
560 .br
561 size_t reclen;
562 .br
563 u_char bval;
564 .RE
565 } RECNOINFO;
566 .PP
567 The elements of this structure are defined as follows:
568 .TP
569 flags
570 The flag value is specified by
571 .IR or 'ing
572 any of the following values:
573 .RS
574 .TP
575 R_FIXEDLEN
576 The records are fixed-length, not byte delimited.
577 The structure element
578 .I reclen
579 specifies the length of the record, and the structure element
580 .I bval
581 is used as the pad character.
582 .TP
583 R_SNAPSHOT
584 This flag requires that a snapshot of the file be taken when
585 .I recno_open
586 is called, instead of permitting any unmodified records to be
587 read from the original file.
588 .RE
589 .TP
590 cachesize
591 A suggested maximum size, in bytes, of the memory cache.
592 Setting this value to zero specifies that an appropriate amount of memory
593 should be used.
594 .TP
595 reclen
596 The length of a fixed-length record.
597 .TP
598 bval
599 The delimiting byte to be used to mark the end of a record for
600 variable-length records, and the pad character for fixed-length
601 records.
602 .PP
603 Variable-length and fixed-length data files require
604 .I key
605 structures to reference the following structure:
606 .sp
607 typedef struct {
608 .RS
609 u_long length;
610 .br
611 u_long number;
612 .br
613 u_long offset;
614 .br
615 u_char valid;
616 .RE
617 } RECNOKEY;
618 .PP
619 The elements of this structure are defined as follows:
620 .TP
621 length
622 The length of the record.
623 .TP
624 number
625 The record number.
626 .TP
627 offset
628 The offset in the file at which the record is located.
629 .TP
630 valid
631 A flag value which indicates the validity of the other fields in the
632 structure.
633 The flag value is specified by
634 .IR or 'ing
635 one or more of the following values:
636 .RS
637 .TP
638 R_LENGTH
639 The record length is valid.
640 .TP
641 R_NUMBER
642 The record number is valid.
643 .TP
644 R_OFFSET
645 The byte offset is valid.
646 .RE
647 .PP
648 If the record retrieval is successful, the record number, byte offset and
649 record length are set in the RECNOKEY structure referenced by the caller's
650 .I key
651 structure.
652 .PP
653 Data structures may reference byte strings of essentially unlimited length.
654 .SH ERRORS
655 The
656 .I open
657 routines may fail and set
658 .I errno
659 for any of the errors specified for the library routines
660 .IR open (2)
661 and
662 .IR malloc (3)
663 or the following:
664 .TP
665 [EFTYPE]
666 A file used by one of the
667 .I open
668 routines is incorrectly formatted.
669 .TP
670 [EINVAL]
671 A parameter has been specified (hash function, pad byte etc.) that is
672 incompatible with the current file specification or there is a mismatch
673 between the version number of file and the software.
674 .PP
675 The
676 .I close
677 routines may fail and set
678 .I errno
679 for any of the errors specified for the library routines
680 .IR close (2),
681 .IR read (2),
682 .IR write (2),
683 .IR free (3),
684 or
685 .IR fsync (2).
686 .PP
687 The
688 .IR del ,
689 .IR get ,
690 .I put
691 and
692 .I seq
693 routines may fail and set
694 .I errno
695 for any of the errors specified for the library routines
696 .IR read (2),
697 .IR write (2),
698 .IR free (3)
699 or
700 .IR malloc (3).
701 .PP
702 The
703 .I sync
704 routines may fail and set
705 .I errno
706 for any of the errors specified for the library routine
707 .IR fsync (2).
708 .SH "SEE ALSO"
709 .IR "Dynamic Hash Tables" ,
710 Per-Ake Larson, Communications of the ACM, April 1988.
711 .br
712 .IR "A New Hash Package for UNIX" ,
713 Margo Seltzer, USENIX Proceedings, Winter 1991.
714 .SH BUGS
715 The typedef DBT is a mnemonic for ``data base thang'', and was used
716 because noone could think of a reasonable name that wasn't already used.
717 .PP
718 None of the access methods provide any form of concurrent access,
719 locking, or transactions.
720 .PP
721 Only big and little endian byte order is supported.