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 / big.c next >
Text File  |  1993-05-22  |  8KB  |  345 lines
  1.  
  2. #include <types.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include "db.h"
  6. #include "btree.h"
  7.  
  8. /*
  9.  *  _BT_GETBIG -- Get big data from indirect pages.
  10.  *
  11.  *    This routine chases indirect blocks for the big object at the 
  12.  *    specified page to a buffer, and return the address of the buffer.
  13.  *
  14.  *    Parameters:
  15.  *        t -- btree with the indirect blocks
  16.  *        pgno -- page number that starts the chain
  17.  *        p -- (char **) to get the address of the buffer containing
  18.  *             the key or datum.
  19.  *        sz -- pointer to an int to get the size of the instantiated
  20.  *              object.
  21.  *
  22.  *    Returns:
  23.  *        RET_SUCCESS, RET_ERROR.
  24.  *
  25.  *    Side Effects:
  26.  *        None.
  27.  */
  28.  
  29. int
  30. _bt_getbig(t, pgno, p, sz)
  31.     BTREE_P t;
  32.     pgno_t pgno;
  33.     char **p;
  34.     int *sz;
  35. {
  36.     pgno_t save;
  37.     size_t nbytes;
  38.     size_t nhere;
  39.     BTHEADER *h;
  40.     char *top, *from, *where;
  41.  
  42.     save = t->bt_curpage->h_pgno;
  43.     if (_bt_getpage(t, pgno) == RET_ERROR)
  44.         return (RET_ERROR);
  45.  
  46.     h = t->bt_curpage;
  47.  
  48.     bcopy((char *) &(h->h_linp[0]),
  49.           (char *) &nbytes,
  50.           (size_t) sizeof(nbytes));
  51.  
  52.     if ((*p = (char *) cbMALLOC(nbytes)) == (char *) NULL)
  53.         return (RET_ERROR);
  54.  
  55.     *sz = nbytes;
  56.     from = ((char *) (&h->h_linp[0])) + sizeof(nbytes);
  57.     top = ((char *) h) + t->bt_psize;
  58.  
  59.     /* need more space for data? */
  60.  
  61.     where = *p;
  62.  
  63.     while (nbytes > 0) {
  64.         nhere = (int) (top - from);
  65.         if (nhere > nbytes) {
  66.             bcopy(from, where, (size_t) nbytes);
  67.             nbytes = 0;
  68.         } else {
  69.             bcopy(from, where, nhere);
  70.             where += nhere;
  71.             nbytes -= nhere;
  72.             if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  73.                 return (RET_ERROR);
  74.             h = t->bt_curpage;
  75.             top = ((char *) h) + t->bt_psize;
  76.             from = (char *) &(h->h_linp[0]);
  77.         }
  78.     }
  79.  
  80.     if (_bt_getpage(t, save) == RET_ERROR)
  81.         return (RET_ERROR);
  82.  
  83.     return (RET_SUCCESS);
  84. }
  85.  
  86. /*
  87.  *  _BT_DELINDIR -- Delete a chain of indirect blocks from the btree.
  88.  *
  89.  *    When a large item is deleted from the tree, this routine puts the
  90.  *    space that it occupied onto the free list for later reuse.  The
  91.  *    bt_free entry in the btree structure points at the head of this list.
  92.  *    This value is also stored on disk in the btree's metadata.
  93.  *
  94.  *    Parameters:
  95.  *        t -- btree from which to delete pages
  96.  *        chain -- page number that starts the chain.
  97.  *
  98.  *    Returns:
  99.  *        RET_SUCCESS, RET_ERROR.
  100.  *
  101.  *    Side Effects:
  102.  *        Invalidates the current on-disk version of the btree's
  103.  *        metadata (if any), and updates the free list appropriately.
  104.  */
  105.  
  106. int
  107. _bt_delindir(t, chain)
  108.     BTREE_P t;
  109.     pgno_t chain;
  110. {
  111.     BTHEADER *h;
  112.     pgno_t save;
  113.     pgno_t oldfree;
  114.  
  115.     h = t->bt_curpage;
  116.     save = h->h_pgno;
  117.     if (_bt_getpage(t, chain) == RET_ERROR)
  118.         return (RET_ERROR);
  119.  
  120.     /*
  121.      *  If some internal node is pointing at this chain, don't
  122.      *  delete it.
  123.      */
  124.  
  125.     if (t->bt_curpage->h_flags & F_PRESERVE) {
  126.         if (_bt_getpage(t, save) == RET_ERROR)
  127.             return (RET_ERROR);
  128.         return (RET_SUCCESS);
  129.     }
  130.  
  131.     /* if there's nothing on the free list, this is easy... */
  132.     if (t->bt_free == P_NONE) {
  133.         t->bt_free = chain;
  134.     } else {
  135.         oldfree = t->bt_free;
  136.  
  137.         /* find the end of the data chain for the deleted datum */
  138.         t->bt_free = chain;
  139.         do {
  140.             if (_bt_getpage(t, chain) == RET_ERROR)
  141.                 return (RET_ERROR);
  142.             h = t->bt_curpage;
  143.             if (h->h_nextpg != P_NONE)
  144.                 chain = h->h_nextpg;
  145.         } while (h->h_nextpg != P_NONE);
  146.  
  147.         /* link freed pages into free list */
  148.         h->h_nextpg = oldfree;
  149.         if (_bt_write(t, h, RELEASE) == RET_ERROR)
  150.             return (RET_ERROR);
  151.         if (_bt_getpage(t, oldfree) == RET_ERROR)
  152.             return (RET_ERROR);
  153.         h = t->bt_curpage;
  154.         h->h_prevpg = chain;
  155.         if (_bt_write(t, h, RELEASE) == RET_ERROR)
  156.             return (RET_ERROR);
  157.     }
  158.  
  159.     /* restore the tree's current page pointer */
  160.     if (_bt_getpage(t, save) == RET_ERROR)
  161.         return (RET_ERROR);
  162.  
  163.     /* we have trashed the tree metadata; rewrite it later */
  164.     t->bt_flags &= ~BTF_METAOK;
  165.  
  166.     return (RET_SUCCESS);
  167. }
  168.  
  169. /*
  170.  *  _BT_INDIRECT -- Write a series of indirect pages for big objects.
  171.  *
  172.  *    A chain of indirect pages looks like
  173.  *
  174.  *       +-------------------+   +---------------------+
  175.  *       |hdr|size|           |   |hdr|         |
  176.  *       +---+----+           |   +---+         |
  177.  *       |   ... data ...    |   |   ... data ...     |    ...
  178.  *       |               |   |             |
  179.  *       +-------------------+   +---------------------+
  180.  *
  181.  *    where hdr is a standard btree page header (with the indirect bit
  182.  *    set), size on the first page is the real size of the datum, and
  183.  *    data are bytes of the datum, split across as many pages as necessary.
  184.  *    Indirect pages are chained together with the h_prevpg and h_nextpg
  185.  *    entries of the page header struct.
  186.  *
  187.  *    A single DBT is written per chain, so space on the last page is
  188.  *    wasted.
  189.  *
  190.  *    We return the page number of the start of the chain.
  191.  *
  192.  *    When a big object is deleted from a tree, the space that it occupied
  193.  *    is placed on a free list for later reuse.  This routine checks that
  194.  *    free list before allocating new pages to the big datum being inserted.
  195.  *
  196.  *    Parameters:
  197.  *        t -- btree in which to store indirect blocks
  198.  *        data -- DBT with the big datum in it
  199.  *        pgno -- place to put the starting page number of the chain
  200.  *
  201.  *    Returns:
  202.  *        RET_SUCCESS, RET_ERROR.
  203.  *
  204.  *    Side Effects:
  205.  *        Current page is changed on return.
  206.  */
  207.  
  208. int
  209. _bt_indirect(t, data, pgno)
  210.     BTREE_P t;
  211.     DBT *data;
  212.     pgno_t *pgno;
  213. {
  214.     pgno_t prev;
  215.     char *top;
  216.     char *where;
  217.     char *from;
  218.     size_t dsize;
  219.     pgno_t nextchn;
  220.     int ischain;
  221.     BTHEADER *cur;
  222.  
  223.     /* get set for first page in chain */
  224.     prev = P_NONE;
  225.     dsize = data->size;
  226.     from = (char *) data->data;
  227.  
  228.     /* if there are blocks on the free list, use them first */
  229.     if ((*pgno = t->bt_free) == P_NONE) {
  230.         if ((cur = _bt_allocpg(t)) == (BTHEADER *) NULL)
  231.             return (RET_ERROR);
  232.  
  233.         ischain = 0;
  234.         *pgno = cur->h_pgno = ++(t->bt_npages);
  235.     } else {
  236.         if (_bt_getpage(t, *pgno) == RET_ERROR)
  237.             return (RET_ERROR);
  238.         ischain = 1;
  239.         cur = t->bt_curpage;
  240.     }
  241.  
  242.     cur->h_flags = F_CONT|F_LEAF;
  243.     bcopy((char *) &dsize, (char *) &cur->h_linp[0], sizeof(size_t));
  244.     where = ((char *) (&cur->h_linp[0])) + sizeof(size_t);
  245.  
  246.     /* fill and write pages in the chain */
  247.     for (;;) {
  248.         int nhere;
  249.  
  250.         top = ((char *) cur) + t->bt_psize;
  251.         cur->h_prevpg = prev;
  252.         nextchn = cur->h_nextpg;
  253.         nhere = (int) (top - where);
  254.  
  255.         if (nhere >= dsize) {
  256.             bcopy(from, where, (int) dsize);
  257.             cur->h_nextpg = P_NONE;
  258.             dsize = 0;
  259.         } else {
  260.             bcopy(from, where, (int) nhere);
  261.             dsize -= nhere;
  262.             from += nhere;
  263.             if (nextchn == P_NONE)
  264.                 cur->h_nextpg = t->bt_npages + 1;
  265.             prev = cur->h_pgno;
  266.         }
  267.  
  268.         /* current page is ready to go; write it out */
  269.         if (_bt_write(t, cur, RELEASE) == RET_ERROR)
  270.             return (RET_ERROR);
  271.  
  272.         /* free the current page, if appropriate */
  273.         if (ISDISK(t) && !ISCACHE(t) && !ischain) {
  274.             FREE ((char *) cur);
  275.         }
  276.  
  277.         /* done? */
  278.         if (dsize == 0)
  279.             break;
  280.  
  281.         /* allocate another page */
  282.         if (nextchn == P_NONE) {
  283.             if ((cur = _bt_allocpg(t)) == (BTHEADER *) NULL)
  284.                 return (RET_ERROR);
  285.             ischain = 0;
  286.             cur->h_pgno = ++(t->bt_npages);
  287.         } else {
  288.             if (_bt_getpage(t, nextchn) == RET_ERROR)
  289.                 return (RET_ERROR);
  290.             ischain = 1;
  291.             cur = t->bt_curpage;
  292.         }
  293.         cur->h_flags = F_LEAF | F_CONT;
  294.  
  295.         where = (char *) (&cur->h_linp[0]);
  296.     }
  297.  
  298.     /* if we used pages from the free list, record changes to it */
  299.     if (*pgno == t->bt_free) {
  300.         t->bt_free = nextchn;
  301.         t->bt_flags &= ~BTF_METAOK;
  302.     }
  303.  
  304.     return (RET_SUCCESS);
  305. }
  306.  
  307. /*
  308.  *  _BT_MARKCHAIN -- Mark a chain of pages as used by an internal node.
  309.  *
  310.  *    Chains of indirect blocks pointed to by leaf nodes get reclaimed
  311.  *    when the item that points to them gets deleted.  Chains pointed
  312.  *    to by internal nodes never get deleted.  This routine marks a
  313.  *    chain as pointed to by an internal node.
  314.  *
  315.  *    Parameters:
  316.  *        t -- tree in which to mark
  317.  *        chain -- number of first page in chain
  318.  *
  319.  *    Returns:
  320.  *        RET_SUCCESS, RET_ERROR.
  321.  *
  322.  *    Side Effects:
  323.  *        None.
  324.  */
  325.  
  326. int
  327. _bt_markchain(t, chain)
  328.     BTREE_P t;
  329.     pgno_t chain;
  330. {
  331.     pgno_t save;
  332.  
  333.     save = t->bt_curpage->h_pgno;
  334.  
  335.     if (_bt_getpage(t, chain) == RET_ERROR)
  336.         return (RET_ERROR);
  337.  
  338.     t->bt_curpage->h_flags |= (F_DIRTY|F_PRESERVE);
  339.  
  340.     if (_bt_getpage(t, save) == RET_ERROR)
  341.         return (RET_ERROR);
  342.  
  343.     return (RET_SUCCESS);
  344. }
  345.