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 / btree.c < prev    next >
Text File  |  1993-05-22  |  17KB  |  754 lines
  1. /*
  2.  *  btree.c -- implementation of btree access method for 4.4BSD.
  3.  *
  4.  *    The design here is based on that of the btree access method used
  5.  *    in the Postgres database system at UC Berkeley.  The implementation
  6.  *    is wholly independent of the Postgres code.
  7.  *
  8.  *    This implementation supports btrees on disk (supply a filename) or
  9.  *    in memory (don't).  Public interfaces defined here are:
  10.  *
  11.  *        btree_open()    -- wrapper; returns a filled DB struct for
  12.  *                   a btree.
  13.  *
  14.  *        bt_open()    -- open a new or existing btree.
  15.  *        bt_get()    -- fetch data from a tree by key.
  16.  *        bt_seq()    -- do a sequential scan on a tree.
  17.  *        bt_put()    -- add data to a tree by key.
  18.  *        bt_delete()    -- remove data from a tree by key.
  19.  *        bt_close()    -- close a btree.
  20.  *        bt_sync()    -- force btree pages to disk (disk trees only).
  21.  */
  22.  
  23. /* #include <sys/param.h> */
  24. #include <stat.h>
  25. /* #include <signal.h> */
  26. #include <errno.h>
  27. #include <fcntl.h>
  28. #include "db.h"
  29. #include <stdio.h>
  30. #include <stdlib.h>
  31. #include <string.h>
  32. /* #include <unistd.h> */
  33. #include "btree.h"
  34.  
  35. BTREEINFO _DefaultBTInfo = {
  36.     0,    /* flags */
  37.     0,    /* cachesize */
  38.     0,    /* psize */
  39.     strcmp,    /* compare */
  40.     0
  41. };
  42.  
  43. /*
  44.  *  BTREE_OPEN -- Wrapper routine to open a btree.
  45.  *
  46.  *    Creates and fills a DB struct, and calls the routine that actually
  47.  *    opens the btree.
  48.  *
  49.  *    Parameters:
  50.  *        f:  filename to open
  51.  *        flags:  flag bits passed to open
  52.  *        mode:  permission bits, used if O_CREAT specified
  53.  *        b:  BTREEINFO pointer
  54.  *
  55.  *    Returns:
  56.  *        Filled-in DBT on success; NULL on failure, with errno
  57.  *        set as appropriate.
  58.  *
  59.  *    Side Effects:
  60.  *        Allocates memory for the DB struct.
  61.  */
  62.  
  63. DB *
  64. btree_open(f, flags, mode, b)
  65.     const char *f;
  66.     int flags;
  67.     int mode;
  68.     const BTREEINFO *b;
  69. {
  70.     DB *db;
  71.     BTREE t;
  72.  
  73.     if ((db = (DB *) cbMALLOC((unsigned) sizeof(DB))) == (DB *) NULL)
  74.         return ((DB *) NULL);
  75.  
  76.     if ((t = bt_open(f, flags, mode, b)) == (BTREE) NULL) {
  77.         FREE ((char *) db);
  78.         return ((DB *) NULL);
  79.     }
  80.  
  81.     db->internal = (char *) t;
  82.     db->close = bt_close;
  83.     db->del = bt_delete;
  84.     db->get = bt_get;
  85.     db->put = bt_put;
  86.     db->seq = bt_seq;
  87.     db->sync = bt_sync;
  88.     db->type = DB_BTREE;
  89.  
  90.     return (db);
  91. }
  92.  
  93. /*
  94.  *  BT_OPEN -- Open a btree.
  95.  *
  96.  *    This routine creates the correct kind (disk or in-memory) of
  97.  *    btree and initializes it as required.
  98.  *
  99.  *    Parameters:
  100.  *        f -- name of btree (NULL for in-memory btrees)
  101.  *        flags -- flags passed to open()
  102.  *        mode -- mode passed to open ()
  103.  *        b -- BTREEINFO structure, describing btree
  104.  *
  105.  *    Returns:
  106.  *        (Opaque) pointer to the btree.  On failure, returns NULL
  107.  *        with errno set as appropriate.
  108.  *
  109.  *    Side Effects:
  110.  *        Allocates memory, opens files.
  111.  */
  112.  
  113. BTREE
  114. bt_open(f, flags, mode, b)
  115.     char *f;
  116.     int flags;
  117.     int mode;
  118.     BTREEINFO *b;
  119. {
  120.     BTREE_P t;
  121.     HTABLE ht;
  122.     int nbytes;
  123.     int fd;
  124.     CURSOR *c;
  125.     BTMETA m;
  126.     struct stat buf;
  127. #pragma unused(mode)
  128.  
  129.     /* use the default info if none was provided */
  130.     if (b == (BTREEINFO *) NULL)
  131.         b = &_DefaultBTInfo;
  132.  
  133.     if ((t = (BTREE_P) cbMALLOC((unsigned) sizeof *t)) == (BTREE_P) NULL)
  134.         return ((BTREE) NULL);
  135.  
  136.     if (b->compare)
  137.         t->bt_compare = b->compare;
  138.     else
  139.         t->bt_compare = strcmp;
  140.  
  141.     t->bt_fname = f;
  142.     t->bt_curpage = (BTHEADER *) NULL;
  143.     t->bt_free = P_NONE;
  144.     c = &(t->bt_cursor);
  145.     c->c_pgno = P_NONE;
  146.     c->c_index = 0;
  147.     c->c_flags = (u_char) NULL;
  148.     c->c_key = (char *) NULL;
  149.     t->bt_stack = (BTSTACK *) NULL;
  150.     t->bt_flags = 0;
  151.  
  152.     /*
  153.      *  If no file name was supplied, this is an in-memory btree.
  154.      *  Otherwise, it's a disk-based btree.
  155.      */
  156.     if (f == (char *) NULL) {
  157.         /* in memory */
  158.         if ((t->bt_psize = b->psize) < MINPSIZE) {
  159.             if (t->bt_psize != 0) {
  160.                 FREE ((char *) t);
  161.                 errno = EINVAL;
  162.                 return ((BTREE) NULL);
  163.             }
  164.             t->bt_psize = getpagesize();
  165.         }
  166.  
  167.         nbytes = HTSIZE * sizeof(HTBUCKET *);
  168.         if ((ht = (HTABLE) cbMALLOC((unsigned) nbytes))
  169.             == (HTABLE) NULL) {
  170.             FREE((char *) t);
  171.             return ((BTREE) NULL);
  172.         }
  173.         bzero((char *) ht, nbytes);
  174.         t->bt_s.bt_ht = ht;
  175.         t->bt_npages = 0;
  176.         t->bt_lorder = BYTE_ORDER;
  177.         if (!(b->flags & R_DUP))
  178.             t->bt_flags |= BTF_NODUPS;
  179.     } else {
  180.         /* on disk */
  181.         if ((fd = open(f, O_RDONLY)) < 0) {
  182.             /* doesn't exist yet, be sure page is big enough */
  183.             if ((t->bt_psize = b->psize) < sizeof(BTHEADER)
  184.                 && b->psize != 0) {
  185.                 FREE((char *) t);
  186.                 errno = EINVAL;
  187.                 return ((BTREE) NULL);
  188.             }
  189.             if (b->lorder == 0)
  190.                 b->lorder = BYTE_ORDER;
  191.  
  192.             if (b->lorder != BIG_ENDIAN
  193.                 && b->lorder != LITTLE_ENDIAN) {
  194.                 FREE((char *) t);
  195.                 errno = EINVAL;
  196.                 return ((BTREE) NULL);
  197.             }
  198.             t->bt_lorder = b->lorder;
  199.             if (!(b->flags & R_DUP))
  200.                 t->bt_flags |= BTF_NODUPS;
  201.         } else {
  202.             /* exists, get page size from file */
  203.             if (read(fd, (char *)&m, sizeof(m)) < sizeof(m)) {
  204.                 close(fd);
  205.                 FREE((char *) t);
  206.                 errno = EINVAL;
  207.                 return ((BTREE) NULL);
  208.             }
  209.  
  210.             /* lorder always stored in host-independent format */
  211.             /* NTOHL(m.m_lorder); */
  212.             if (m.m_lorder != BIG_ENDIAN
  213.                 && m.m_lorder != LITTLE_ENDIAN) {
  214.                 FREE((char *) t);
  215.                 errno = EINVAL;
  216.                 return ((BTREE) NULL);
  217.             }
  218.             t->bt_lorder = m.m_lorder;
  219.  
  220.             if (t->bt_lorder != BYTE_ORDER) {
  221.                 BLSWAP(m.m_magic);
  222.                 BLSWAP(m.m_version);
  223.                 BLSWAP(m.m_psize);
  224.                 BLSWAP(m.m_free);
  225.                 BLSWAP(m.m_flags);
  226.             }
  227.  
  228.             if (m.m_magic != BTREEMAGIC
  229.                 || m.m_version != BTREEVERSION
  230.                 || m.m_psize < MINPSIZE) {
  231.                 close(fd);
  232.                 FREE((char *) t);
  233. #ifndef EFTYPE
  234. #define EFTYPE    -100
  235. #endif
  236.                 errno = EFTYPE;
  237.                 return ((BTREE) NULL);
  238.             }
  239.             t->bt_psize = m.m_psize;
  240.             t->bt_free = m.m_free;
  241.             t->bt_flags |= (m.m_flags & BTF_NODUPS) | BTF_METAOK;
  242.             close(fd);
  243.         }
  244.  
  245.         /* now open the file the way the user wanted it */
  246.         if ((t->bt_s.bt_d.d_fd = open(f, flags/* , mode */)) < 0) {
  247.             FREE ((char *) t);
  248.             return ((BTREE) NULL);
  249.         }
  250.  
  251. #ifdef NEVER_DEFINED
  252.         /* access method files are always close-on-exec */
  253.         if (fcntl(t->bt_s.bt_d.d_fd, F_SETFL, 1) == -1) {
  254.             close(t->bt_s.bt_d.d_fd);
  255.             FREE ((char *) t);
  256.             return ((BTREE) NULL);
  257.         }
  258. #endif
  259.  
  260.         /* get number of pages, page size if necessary */
  261.         fstat(t->bt_s.bt_d.d_fd, &buf);
  262.         if (t->bt_psize == 0)
  263.             t->bt_psize = buf.st_blksize;
  264.         t->bt_npages = (pgno_t) (buf.st_size / t->bt_psize);
  265.  
  266.         /* page zero is metadata, doesn't count */
  267.         if (t->bt_npages > 0)
  268.             --(t->bt_npages);
  269.  
  270.         if (b->cachesize == 0)
  271.             b->cachesize = DEFCACHE;
  272.  
  273.         /* get an lru buffer cache, if the user asked for one */
  274.         if ((b->cachesize / t->bt_psize) > 0) {
  275.             BTDISK *d = &(t->bt_s.bt_d);
  276.  
  277.             d->d_cache = lruinit(d->d_fd,
  278.                          (int) (b->cachesize / t->bt_psize),
  279.                          (int) t->bt_psize,
  280.                          (char *) t->bt_lorder,
  281.                          _bt_pgin, _bt_pgout);
  282.  
  283.             if (d->d_cache == (char *) NULL) {
  284.                 FREE((char *) t);
  285.                 return ((BTREE) NULL);
  286.             }
  287.         }
  288.     }
  289.  
  290.     /* remember if tree was opened for write */
  291.     if (((flags & O_WRONLY) == O_WRONLY)
  292.         || ((flags & O_RDWR) == O_RDWR))
  293.         t->bt_flags |= BTF_ISWRITE;
  294.  
  295.     return ((BTREE) t);
  296. }
  297.  
  298. /*
  299.  *  BT_GET -- Get an entry from a btree.
  300.  *
  301.  *    Does a key lookup in the tree to find the specified key, and returns
  302.  *    the key/data pair found.
  303.  *
  304.  *    Parameters:
  305.  *        tree -- btree in which to do lookup
  306.  *        key -- key to find
  307.  *        data -- pointer to DBT in which to return data
  308.  *        flag -- ignored
  309.  *
  310.  *    Returns:
  311.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if the key is not
  312.  *        found.  If key is not found, nothing is stored in the
  313.  *        return DBT 'data'.
  314.  *
  315.  *    Side Effects:
  316.  *        None.
  317.  *
  318.  *    Warnings:
  319.  *        Return data is statically allocated, and will be overwritten
  320.  *        at the next call.
  321.  */
  322.  
  323. int
  324. bt_get(dbp, key, data, flag)
  325.     DB *dbp; 
  326.     DBT *key, *data;
  327.     u_long flag;
  328. {
  329.     BTREE_P t = (BTREE_P) (dbp->internal);
  330.     BTHEADER *h;
  331.     DATUM *d;
  332.     BTITEM *item;
  333. #pragma unused(flag)
  334.  
  335. #ifdef lint
  336.     flag = flag;
  337. #endif /* lint */
  338.  
  339.     /* lookup */
  340.     item = _bt_search(t, key);
  341.  
  342.     /* clear parent pointer stack */
  343.     while (_bt_pop(t) != P_NONE)
  344.         continue;
  345.  
  346.     if (item == (BTITEM *) NULL)
  347.         return (RET_ERROR);
  348.  
  349.     h = (BTHEADER *) t->bt_curpage;
  350.     data->size = 0;
  351.     data->data = (u_char *) NULL;
  352.  
  353.     /* match? */
  354.     if (VALIDITEM(t, item)
  355.         && _bt_cmp(t, key->data, item->bti_index) == 0) {
  356.         d = (DATUM *) GETDATUM(h, item->bti_index);
  357.         return (_bt_buildret(t, d, data, key));
  358.     }
  359.  
  360.     /* nope */
  361.     return (RET_SPECIAL);
  362. }
  363.  
  364. /*
  365.  *  BT_PUT -- Add an entry to a btree.
  366.  *
  367.  *    The specified (key, data) pair is added to the tree.  If the tree
  368.  *    was created for unique keys only, then duplicates will not be
  369.  *    entered.  If the requested key exists in the tree, it will be over-
  370.  *    written unless the flags parameter is R_NOOVERWRITE, in which case
  371.  *    the update will not be done.  If duplicate keys are permitted in the
  372.  *    tree, duplicates will be inserted and will not overwrite existing
  373.  *    keys.  Nodes are split as required.
  374.  *
  375.  *    Parameters:
  376.  *        tree -- btree in which to put the new entry
  377.  *        key -- key component to add
  378.  *        data -- data corresponding to key
  379.  *        flag -- R_NOOVERWRITE or zero.
  380.  *
  381.  *    Returns:
  382.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if the
  383.  *        NOOVERWRITE flag was set and the specified key exists
  384.  *        in the database.
  385.  *
  386.  *    Side Effects:
  387.  *        None.
  388.  */
  389.  
  390. int
  391. bt_put(dbp, key, data, flag)
  392.     DB *dbp;
  393.     DBT *key, *data;
  394.     u_long flag;
  395. {
  396.     BTREE_P t;
  397.  
  398.     t = (BTREE_P)dbp->internal;
  399.     
  400.     return _bt_put(t, key, data, flag);
  401.     }
  402.  
  403. int
  404. _bt_put(t, key, data, flag)
  405.     BTREE_P t;
  406.     DBT *key, *data;
  407.     u_long flag;
  408. {
  409.     int    result;
  410.     BTITEM *item;
  411.  
  412.     /* look for this key in the tree */
  413.     item = _bt_search(t, key);
  414.  
  415.     /*
  416.      *  If this tree was originally created without R_DUP, then duplicate
  417.      *  keys are not allowed.  We need to check this at insertion time.
  418.      */
  419.  
  420.     if (VALIDITEM(t, item) && _bt_cmp(t, key->data, item->bti_index) == 0) {
  421.         if ((t->bt_flags & BTF_NODUPS) && flag == R_NOOVERWRITE) {
  422.             if (_bt_delone(t, item->bti_index) == RET_ERROR) {        
  423.                 while (_bt_pop(t) != P_NONE)
  424.                     continue;
  425.                 return (RET_ERROR);
  426.             }
  427.         }
  428.     }
  429.  
  430.     result = _bt_insert(t, item, key, data, flag);
  431.     return result;
  432. }
  433.  
  434. /*
  435.  *  BT_DELETE -- delete a key from the tree.
  436.  *
  437.  *    Deletes all keys (and their associated data items) matching the
  438.  *    supplied key from the tree.  If the flags entry is R_CURSOR, then
  439.  *    the current item in the active scan is deleted.
  440.  *
  441.  *    Parameters:
  442.  *        tree -- btree from which to delete key
  443.  *        key -- key to delete
  444.  *        flags -- R_CURSOR or zero
  445.  *
  446.  *    Returns:
  447.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if the specified
  448.  *        key was not in the tree.
  449.  *
  450.  *    Side Effects:
  451.  *        None.
  452.  */
  453.  
  454. int
  455. bt_delete(dbp, key, flags)
  456.     DB *dbp;
  457.     DBT *key;
  458.     u_long flags;
  459. {
  460.     BTREE_P t;
  461.     BTHEADER *h;
  462.     BTITEM *item;
  463.     int ndel = 0;
  464.  
  465.     t = (BTREE_P)dbp->internal;
  466.  
  467.     if (flags == R_CURSOR)
  468.         return (_bt_crsrdel(t));
  469.  
  470.     /* find the first matching key in the tree */
  471.     item = _bt_first(t, key);
  472.     h = t->bt_curpage;
  473.  
  474.     /* don't need the descent stack for deletes */
  475.     while (_bt_pop(t) != P_NONE)
  476.         continue;
  477.  
  478.     /* delete all matching keys */
  479.     for (;;) {
  480.         while (VALIDITEM(t, item)
  481.                && (_bt_cmp(t, key->data, item->bti_index) == 0)) {
  482.             if (_bt_delone(t, item->bti_index) == RET_ERROR)
  483.                 return (RET_ERROR);
  484.             ndel++;
  485.         }
  486.  
  487.         if (VALIDITEM(t, item) || h->h_nextpg == P_NONE)
  488.             break;
  489.  
  490.         /* next page, if necessary */
  491.         do {
  492.             if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  493.                 return (RET_ERROR);
  494.             h = t->bt_curpage;
  495.         } while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE);
  496.  
  497.         item->bti_pgno = h->h_pgno;
  498.         item->bti_index = 0;
  499.  
  500.         if (!VALIDITEM(t, item)
  501.             || _bt_cmp(t, key->data, item->bti_index) != 0)
  502.             break;
  503.     }
  504.  
  505.     /* flush changes to disk */
  506.     if (ISDISK(t)) {
  507.         if (h->h_flags & F_DIRTY) {
  508.             if (_bt_write(t, t->bt_curpage, NORELEASE) == RET_ERROR)
  509.                 return (RET_ERROR);
  510.         }
  511.     }
  512.  
  513.     if (ndel == 0)
  514.         return (RET_SPECIAL);
  515.  
  516.     return (RET_SUCCESS);
  517. }
  518.  
  519. /*
  520.  *  BT_SYNC -- sync the btree to disk.
  521.  *
  522.  *    Parameters:
  523.  *        tree -- btree to sync.
  524.  *
  525.  *    Returns:
  526.  *        RET_SUCCESS, RET_ERROR.
  527.  */
  528.  
  529. bt_sync(dbp)
  530.     DB *dbp;
  531. {
  532.     BTREE_P t;
  533.     BTHEADER *h;
  534.     pgno_t pgno;
  535.  
  536.     t = (BTREE_P)dbp->internal;
  537.  
  538.     /* if this is an in-memory btree, syncing is a no-op */
  539.     if (!ISDISK(t))
  540.         return (RET_SUCCESS);
  541.  
  542.     h = (BTHEADER *) t->bt_curpage;
  543.     h->h_flags &= ~F_DIRTY;
  544.  
  545.     if (ISCACHE(t)) {
  546.         pgno = t->bt_curpage->h_pgno;
  547.         if (_bt_write(t, h, RELEASE) == RET_ERROR)
  548.             return(RET_ERROR);
  549.         if (lrusync(t->bt_s.bt_d.d_cache) < RET_ERROR)
  550.             return (RET_ERROR);
  551.         if (_bt_getpage(t, pgno) == RET_ERROR)
  552.             return (RET_ERROR);
  553.     } else {
  554.         if (_bt_write(t, h, NORELEASE) == RET_ERROR)
  555.             return (RET_ERROR);
  556.     }
  557.  
  558.     return RET_SUCCESS/*(fsync(t->bt_s.bt_d.d_fd))*/;
  559. }
  560.  
  561. /*
  562.  *  BT_SEQ -- Sequential scan interface.
  563.  *
  564.  *    This routine supports sequential scans on the btree.  If called with
  565.  *    flags set to R_CURSOR, or if no seq scan has been initialized in the
  566.  *    current tree, we initialize the scan.  Otherwise, we advance the scan
  567.  *    and return the next item.
  568.  *
  569.  *    Scans can be either keyed or non-keyed.  Keyed scans basically have
  570.  *    a starting point somewhere in the middle of the tree.  Non-keyed
  571.  *    scans start at an endpoint.  Also, scans can be backward (descending
  572.  *    order), forward (ascending order), or no movement (keep returning
  573.  *    the same item).
  574.  *
  575.  *    Flags is checked every time we enter the routine, so the user can
  576.  *    change directions on an active scan if desired.  The key argument
  577.  *    is examined only when we initialize the scan, in order to position
  578.  *    it properly.
  579.  *
  580.  *    Items are returned via the key and data arguments passed in.
  581.  *
  582.  *    Parameters:
  583.  *        tree -- btree in which to do scan
  584.  *        key -- key, used to position scan on initialization, and
  585.  *               used to return key components to the user.
  586.  *        data -- used to return data components to the user.
  587.  *        flags -- specify R_CURSOR, R_FIRST, R_LAST, R_NEXT, or
  588.  *             R_PREV.
  589.  *
  590.  *    Returns:
  591.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if no more data
  592.  *        exists in the tree in the specified direction.
  593.  *
  594.  *    Side Effects:
  595.  *        Changes the btree's notion of the current position in the
  596.  *        scan.
  597.  *
  598.  *    Warnings:
  599.  *        The key and data items returned are static and will be
  600.  *        overwritten by the next bt_get or bt_seq.
  601.  */
  602.  
  603. int
  604. bt_seq(dbp, key, data, flags)
  605.     DB *dbp;
  606.     DBT *key, *data;
  607.     u_long flags;
  608. {
  609.     BTREE_P t;
  610.     BTHEADER *h;
  611.     DATUM *d;
  612.     int status;
  613.  
  614.     t = (BTREE_P)dbp->internal;
  615.  
  616.     /* do we need to initialize the scan? */
  617.     if (flags == R_CURSOR || flags == R_LAST || flags == R_FIRST
  618.         || !(t->bt_flags & BTF_SEQINIT)) {
  619.  
  620.         /* initialize it */
  621.         status = _bt_seqinit(t, key, flags);
  622.     } else {
  623.         /* just advance the current scan pointer */
  624.         status = _bt_seqadvance(t, flags);
  625.     }
  626.  
  627.     key->size = data->size = 0;
  628.     key->data = data->data = (u_char *) NULL;
  629.  
  630.     h = t->bt_curpage;
  631.  
  632.     /* is there a valid item at the current scan location? */
  633.     if (status == RET_SPECIAL) {
  634.         if (flags == R_NEXT) {
  635.             if (t->bt_cursor.c_index >= NEXTINDEX(h)) {
  636.                 if (NEXTINDEX(h) > 0)
  637.                     t->bt_cursor.c_index = NEXTINDEX(h) - 1;
  638.                 else
  639.                     t->bt_cursor.c_index = 0;
  640.             }
  641.         } else {
  642.             t->bt_cursor.c_index = 0;
  643.         }
  644.         return (RET_SPECIAL);
  645.     } else if (status == RET_ERROR)
  646.         return (RET_ERROR);
  647.  
  648.     /* okay, return the data */
  649.     d = (DATUM *) GETDATUM(h, t->bt_cursor.c_index);
  650.  
  651.     return (_bt_buildret(t, d, data, key));
  652. }
  653.  
  654. /*
  655.  *  BT_CLOSE -- Close a btree
  656.  *
  657.  *    Parameters:
  658.  *        tree -- tree to close
  659.  *
  660.  *    Returns:
  661.  *        RET_SUCCESS, RET_ERROR.
  662.  *
  663.  *    Side Effects:
  664.  *        Frees space occupied by the tree.
  665.  */
  666.  
  667. int
  668. bt_close(dbp)
  669. DB *dbp;
  670.     {
  671.     struct HTBUCKET *b, *sb;
  672.     BTREE_P t;
  673.     BTHEADER *h;
  674.     HTABLE ht;
  675.     int fd, i;
  676.     char *cache;
  677.  
  678.     t = (BTREE_P)dbp->internal;
  679.  
  680.     if (t->bt_cursor.c_key != (char *) NULL)
  681.         {
  682.         FREE(t->bt_cursor.c_key);
  683.         }
  684.     
  685.     if (! ISDISK(t))
  686.         {
  687.         /* in-memory tree, release hash table memory */
  688.         ht = t->bt_s.bt_ht;
  689.         for (i = 0; i < HTSIZE; i++) {
  690.             if ((b = ht[i]) == (struct HTBUCKET *) NULL)
  691.                 break;
  692.             do {
  693.                 sb = b;
  694.                 FREE((char *) b->ht_page);
  695.                 b = b->ht_next;
  696.                 FREE((char *) sb);
  697.             } while (b != (struct HTBUCKET *) NULL);
  698.         }
  699.         FREE ((char *) ht);
  700.         FREE ((char *) t);
  701.         return (RET_SUCCESS);
  702.     }
  703.  
  704.     if ((t->bt_flags & BTF_ISWRITE) && !(t->bt_flags & BTF_METAOK))
  705.         {
  706.         if (_bt_wrtmeta(t) == RET_ERROR)
  707.             {
  708.             return (RET_ERROR);
  709.             }
  710.         }
  711.  
  712.     if (t->bt_curpage != (BTHEADER *) NULL)
  713.         {
  714.         h = t->bt_curpage;
  715.         if (h->h_flags & F_DIRTY)
  716.             {
  717.             if (_bt_write(t, h, RELEASE) == RET_ERROR)
  718.                 return (RET_ERROR);
  719.             }
  720.         else {
  721.             if (_bt_release(t, h) == RET_ERROR)
  722.                 return (RET_ERROR);
  723.             }
  724.  
  725.         /* flush and free the cache, if there is one */
  726.         if (ISCACHE(t))
  727.             {
  728.             cache = t->bt_s.bt_d.d_cache;
  729.             if (lrucheckbuf(cache, h))
  730.                 {
  731.                 h = NULL;
  732.                 }
  733.             if (lrusync(cache) == RET_ERROR)
  734.                 {
  735.                 return (RET_ERROR);
  736.                 }
  737.             lrufree(cache);
  738.             }
  739.         
  740.         if (h)
  741.             FREE((char *) h);
  742.         }
  743.  
  744.     fd = t->bt_s.bt_d.d_fd;
  745.     
  746.     _bt_clear_stack(t);        /* TGE */
  747.     
  748.     _bt_free_ret();            /* TGE * Free the static spaces... */
  749.     
  750.     FREE ((char *) t);
  751.     
  752.     return (close(fd));
  753.     }
  754.