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