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 / storage.c < prev    next >
Text File  |  1993-05-22  |  14KB  |  630 lines
  1.  
  2. #include "db.h"
  3. #include <fcntl.h>
  4. #include <errno.h>
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include "btree.h"
  9.  
  10. /*
  11.  *  BT_GETPAGE -- Make pgno the current page of the btree.
  12.  *
  13.  *    This routine is just a wrapper that decides whether to call the
  14.  *    memory or disk-based routine to do the work.
  15.  *
  16.  *    Parameters:
  17.  *        t -- btree in which to get page
  18.  *        pgno -- page number to get
  19.  *
  20.  *    Returns:
  21.  *        RET_SUCCESS or RET_ERROR.
  22.  */
  23.  
  24. int
  25. _bt_getpage(t, pgno)
  26.     BTREE_P t;
  27.     pgno_t pgno;
  28. {
  29. #ifdef DEBUG
  30.     if (pgno == P_NONE)
  31.         _punt();
  32. #endif /* DEBUG */
  33.  
  34.     /* see if we can get away without doing any work */
  35.     if (t->bt_curpage != (BTHEADER *) NULL) {
  36.         if (t->bt_curpage->h_pgno == pgno)
  37.             return (RET_SUCCESS);
  38.     }
  39.  
  40.     if (t->bt_fname == (char *) NULL)
  41.         return (_bt_getmpage(t, pgno));
  42.     else
  43.         return (_bt_getdpage(t, pgno));
  44. }
  45.  
  46. /*
  47.  *  _BT_GETMPAGE -- Make pgno the current page of the btree.
  48.  *
  49.  *    This routine gets pages for in-memory btrees.
  50.  *
  51.  *    Parameters:
  52.  *        t -- btree in which to get page
  53.  *        pgno -- page number to get
  54.  *
  55.  *    Returns:
  56.  *        RET_SUCCESS or RET_ERROR.
  57.  */
  58.  
  59. int
  60. _bt_getmpage(t, pgno)
  61.     register BTREE_P t;
  62.     pgno_t pgno;
  63. {
  64.     int htindex;
  65.     BTHEADER *h;
  66.     HTBUCKET *b;
  67.  
  68.     if (t->bt_curpage == (BTHEADER *) NULL) {
  69.         if (pgno != P_ROOT) {
  70.             errno = EBADF;
  71.             return (RET_ERROR);
  72.         }
  73.  
  74.         t->bt_npages++;
  75.         h = (BTHEADER *) cbMALLOC((unsigned) t->bt_psize);
  76.         if (h == (BTHEADER *) NULL)
  77.             return (RET_ERROR);
  78.  
  79.         h->h_pgno = P_ROOT;
  80.         h->h_flags = F_LEAF;
  81.         h->h_lower = (index_t)
  82.                 (((char *) &(h->h_linp[0])) - ((char *) h));
  83.         h->h_upper = t->bt_psize;
  84.         h->h_prevpg = h->h_nextpg = P_NONE;
  85.  
  86.         t->bt_curpage = h;
  87.  
  88.         /* get the root page into the hash table */
  89.         if (_bt_write(t, h, RELEASE) == RET_ERROR)
  90.             return (RET_ERROR);
  91.     }
  92.  
  93.     htindex = HASHKEY(pgno);
  94.  
  95.     for (b = t->bt_s.bt_ht[htindex];
  96.          b != (HTBUCKET *) NULL;
  97.          b = b->ht_next) {
  98.         if (b->ht_pgno == pgno) {
  99.             t->bt_curpage = b->ht_page;
  100.             return (RET_SUCCESS);
  101.         }
  102.     }
  103.     return (RET_ERROR);
  104. }
  105.  
  106. /*
  107.  *  _BT_GETDPAGE -- Make pgno the current page of the btree.
  108.  *
  109.  *    This routine gets pages for disk btrees.
  110.  *
  111.  *    Because disk btree pages must be readable across machine architectures,
  112.  *    the btree code writes integers out in network format.  This routine
  113.  *    converts them back to host format before returning the page.
  114.  *
  115.  *    Parameters:
  116.  *        t -- btree in which to get page
  117.  *        pgno -- page number to get
  118.  *
  119.  *    Returns:
  120.  *        RET_SUCCESS, RET_ERROR.
  121.  */
  122.  
  123. int
  124. _bt_getdpage(t, pgno)
  125.     register BTREE_P t;
  126.     pgno_t pgno;
  127. {
  128.     BTHEADER *h;
  129.     char *cache;
  130.     long pos, seekpos;
  131.     int n, nbytes;
  132.  
  133.     /* if we have an lru cache, let the cache code do the work */
  134.     if (ISCACHE(t)) {
  135.         cache = t->bt_s.bt_d.d_cache;
  136.  
  137.         /* release the old page */
  138.         if (t->bt_curpage != (BTHEADER *) NULL) {
  139.             pgno_t opgno = t->bt_curpage->h_pgno;
  140.             t->bt_curpage->h_flags &= ~F_DIRTY;
  141.  
  142.             if (lruwrite(cache, (int) opgno) < 0)
  143.                 return (RET_ERROR);
  144.  
  145.             if (lrurelease(cache, (int) opgno) < 0)
  146.                 return (RET_ERROR);
  147.         }
  148.  
  149.         if (pgno > t->bt_npages) {
  150.             if ((h = (BTHEADER *) lrugetnew(cache, (int)pgno, &nbytes))
  151.                 == (BTHEADER *) NULL)
  152.                 return (RET_ERROR);
  153.             t->bt_npages = pgno;
  154.         } else {
  155.             if ((h = (BTHEADER *) lruget(cache, (int)pgno, &nbytes))
  156.                 == (BTHEADER *) NULL)
  157.                 return (RET_ERROR);
  158.         }
  159.  
  160.         /* init this page, if necessary */
  161.         if (nbytes == 0) {
  162.             h->h_pgno = pgno;
  163.             h->h_flags = F_LEAF;
  164.             h->h_lower = (index_t)
  165.                 (((char *) &(h->h_linp[0])) - ((char *) h));
  166.             h->h_upper = t->bt_psize;
  167.             h->h_prevpg = h->h_nextpg = P_NONE;
  168.         }
  169.  
  170.         t->bt_curpage = h;
  171.  
  172.         return (RET_SUCCESS);
  173.     }
  174.  
  175.     /* sync the current page, if necessary */
  176.     if (t->bt_curpage != (BTHEADER *) NULL) {
  177.         if (t->bt_curpage->h_flags & F_DIRTY)
  178.             if (_bt_write(t, t->bt_curpage, RELEASE) == RET_ERROR)
  179.                 {
  180.                 return (RET_ERROR);
  181.                 }
  182.     } else {
  183.         if (t->bt_npages == 0)
  184.             t->bt_npages = 1;
  185.  
  186.         /* if no current page, get space for one */
  187.         if ((t->bt_curpage = (BTHEADER *) cbMALLOC((unsigned) t->bt_psize))
  188.             == (BTHEADER *) NULL) {
  189.             return (RET_ERROR);
  190.         }
  191.     }
  192.  
  193.     n = t->bt_psize;
  194.     pos = (long) (pgno * n);
  195.  
  196.     /* seek to correct location in file */
  197.     seekpos = ck_lseek(t->bt_s.bt_d.d_fd, pos, SEEK_SET);
  198.     if (seekpos != pos)
  199.         {
  200.         return (RET_ERROR);
  201.         }
  202.  
  203.     /* read the page */
  204.     if ((nbytes = read(t->bt_s.bt_d.d_fd, (char *)t->bt_curpage, n)) < n) {
  205.  
  206.         /*
  207.          *  If we didn't get a full page, we must have gotten no
  208.          *  data at all -- in which case we're trying to read a
  209.          *  root page that doesn't exist yet.  This is the only
  210.          *  case in which this is okay.  If this happens, construct
  211.          *  an empty root page by hand.
  212.          */
  213.         if (nbytes != 0 || pgno != P_ROOT) {
  214.             errno = EBADF;
  215.             return (RET_ERROR);
  216.         }
  217.  
  218.         h = (BTHEADER *) t->bt_curpage;
  219.         h->h_pgno = pgno;
  220.         h->h_flags = F_LEAF;
  221.         h->h_lower = (index_t)
  222.                 (((char *) &(h->h_linp[0])) - ((char *) h));
  223.         h->h_upper = t->bt_psize;
  224.         h->h_prevpg = h->h_nextpg = P_NONE;
  225.     } else
  226.         (void) _bt_pgin(t->bt_curpage, (char *) t->bt_lorder);
  227.  
  228.     return (RET_SUCCESS);
  229. }
  230.  
  231. /*
  232.  *  _BT_PGOUT, _BT_PGIN -- Convert host-specific number layout to/from
  233.  *               the host-independent format stored on disk.
  234.  *
  235.  *    Parameters:
  236.  *        h -- page to convert
  237.  *        _lorder -- byte order for pages (stored as a char * in the
  238.  *               cache, and passed around as a magic cookie).
  239.  *
  240.  *    Returns:
  241.  *        RET_SUCCESS (lru code requires a return value).
  242.  *
  243.  *    Side Effects:
  244.  *        Layout of tree metadata on the page is changed in place.
  245.  *
  246.  *    Warnings:
  247.  *        Everywhere else in the code, the types pgno_t and index_t
  248.  *        are opaque.  These two routines know what they really
  249.  *        are.
  250.  */
  251.  
  252. int
  253. _bt_pgout(h, _lorder)
  254.     BTHEADER *h;
  255.     char *_lorder;
  256. {
  257.     int i;
  258.     int top;
  259.     int lorder;
  260.     DATUM *d;
  261.     IDATUM *id;
  262.     size_t chain;
  263.  
  264.     lorder = (int) _lorder;
  265.     if (lorder == BYTE_ORDER)
  266.         return (RET_SUCCESS);
  267.  
  268.     if (h->h_flags & F_LEAF) {
  269.         if (h->h_flags & F_CONT) {
  270.             if (h->h_prevpg == P_NONE) {
  271.                 size_t longsz;
  272.  
  273.                 (void) bcopy((char *) &(h->h_linp[0]),
  274.                           (char *) &longsz,
  275.                           sizeof(longsz));
  276.                 BLSWAP(longsz);
  277.                 (void) bcopy((char *) &longsz,
  278.                           (char *) &(h->h_linp[0]),
  279.                           sizeof(longsz));
  280.             }
  281.         } else {
  282.             top = NEXTINDEX(h);
  283.             for (i = 0; i < top; i++) {
  284.                 d = (DATUM *) GETDATUM(h, i);
  285.                 if (d->d_flags & D_BIGKEY) {
  286.                     (void) bcopy((char *) &(d->d_bytes[0]),
  287.                               (char *) &chain,
  288.                               sizeof(chain));
  289.                     BLSWAP(chain);
  290.                     (void) bcopy((char *) &chain,
  291.                               (char *) &(d->d_bytes[0]),
  292.                               sizeof(chain));
  293.                 }
  294.                 if (d->d_flags & D_BIGDATA) {
  295.                     (void) bcopy((char *) &(d->d_bytes[d->d_ksize]),
  296.                               (char *) &chain,
  297.                               sizeof(chain));
  298.                     BLSWAP(chain);
  299.                     (void) bcopy((char *) &chain,
  300.                               (char *) &(d->d_bytes[d->d_ksize]),
  301.                               sizeof(chain));
  302.                 }
  303.                 BLSWAP(d->d_dsize);
  304.                 BLSWAP(d->d_ksize);
  305.                 BLSWAP(d->d_flags);
  306.                 BLSWAP(h->h_linp[i]);
  307.             }
  308.         }
  309.     } else {
  310.         top = NEXTINDEX(h);
  311.         for (i = 0; i < top; i++) {
  312.             id = (IDATUM *) GETDATUM(h, i);
  313.             BLSWAP(id->i_size);
  314.             BLSWAP(id->i_pgno);
  315.             BLSWAP(id->i_flags);
  316.             if (id->i_flags & D_BIGKEY) {
  317.                 (void) bcopy((char *) &(id->i_bytes[0]),
  318.                           (char *) &chain,
  319.                           sizeof(chain));
  320.                 BLSWAP(chain);
  321.                 (void) bcopy((char *) &chain,
  322.                           (char *) &(id->i_bytes[0]),
  323.                           sizeof(chain));
  324.             }
  325.             BLSWAP(h->h_linp[i]);
  326.         }
  327.     }
  328.     BLSWAP(h->h_flags);
  329.     BLSWAP(h->h_pgno);
  330.     BLSWAP(h->h_prevpg);
  331.     BLSWAP(h->h_nextpg);
  332.     BLSWAP(h->h_lower);
  333.     BLSWAP(h->h_upper);
  334.  
  335.     return (RET_SUCCESS);
  336. }
  337.  
  338. int
  339. _bt_pgin(h, _lorder)
  340.     BTHEADER *h;
  341.     char *_lorder;
  342. {
  343.     int i;
  344.     int top;
  345.     int lorder;
  346.     DATUM *d;
  347.     IDATUM *id;
  348.     size_t chain;
  349.  
  350.     /*
  351.      *  If btree pages are to be stored in the host byte order, don't
  352.      *  bother swapping.
  353.      */
  354.     lorder = (int) _lorder;
  355.     if (lorder == BYTE_ORDER)
  356.         return (RET_SUCCESS);
  357.  
  358.     BLSWAP(h->h_upper);
  359.     BLSWAP(h->h_lower);
  360.     BLSWAP(h->h_nextpg);
  361.     BLSWAP(h->h_prevpg);
  362.     BLSWAP(h->h_pgno);
  363.     BLSWAP(h->h_flags);
  364.  
  365.     if (h->h_flags & F_LEAF) {
  366.         if (h->h_flags & F_CONT) {
  367.             if (h->h_prevpg == P_NONE) {
  368.                 size_t longsz;
  369.  
  370.                 (void) bcopy((char *) &(h->h_linp[0]),
  371.                           (char *) &longsz,
  372.                           sizeof(longsz));
  373.                 BLSWAP(longsz);
  374.                 (void) bcopy((char *) &longsz,
  375.                           (char *) &(h->h_linp[0]),
  376.                           sizeof(longsz));
  377.             }
  378.         } else {
  379.             top = NEXTINDEX(h);
  380.             for (i = 0; i < top; i++) {
  381.                 BLSWAP(h->h_linp[i]);
  382.                 d = (DATUM *) GETDATUM(h, i);
  383.                 BLSWAP(d->d_dsize);
  384.                 BLSWAP(d->d_ksize);
  385.                 BLSWAP(d->d_flags);
  386.                 if (d->d_flags & D_BIGKEY) {
  387.                     (void) bcopy((char *) &(d->d_bytes[0]),
  388.                               (char *) &chain,
  389.                               sizeof(chain));
  390.                     BLSWAP(chain);
  391.                     (void) bcopy((char *) &chain,
  392.                               (char *) &(d->d_bytes[0]),
  393.                               sizeof(chain));
  394.                 }
  395.                 if (d->d_flags & D_BIGDATA) {
  396.                     (void) bcopy((char *) &(d->d_bytes[d->d_ksize]),
  397.                               (char *) &chain,
  398.                               sizeof(chain));
  399.                     BLSWAP(chain);
  400.                     (void) bcopy((char *) &chain,
  401.                               (char *) &(d->d_bytes[d->d_ksize]),
  402.                               sizeof(chain));
  403.                 }
  404.             }
  405.         }
  406.     } else {
  407.         top = NEXTINDEX(h);
  408.         for (i = 0; i < top; i++) {
  409.             BLSWAP(h->h_linp[i]);
  410.             id = (IDATUM *) GETDATUM(h, i);
  411.             BLSWAP(id->i_size);
  412.             BLSWAP(id->i_pgno);
  413.             BLSWAP(id->i_flags);
  414.             if (id->i_flags & D_BIGKEY) {
  415.                 (void) bcopy((char *) &(id->i_bytes[0]),
  416.                           (char *) &chain,
  417.                           sizeof(chain));
  418.                 BLSWAP(chain);
  419.                 (void) bcopy((char *) &chain,
  420.                           (char *) &(id->i_bytes[0]),
  421.                           sizeof(chain));
  422.             }
  423.         }
  424.     }
  425.     return (RET_SUCCESS);
  426. }
  427.  
  428. /*
  429.  *  _BT_ALLOCPG -- allocate a new page in the btree.
  430.  *
  431.  *    This is called when we split a page, to get space to do the split.
  432.  *    For disk btrees, these pages are released when the split is done.
  433.  *    For memory btrees, they are not.
  434.  *
  435.  *    Parameters:
  436.  *        t -- tree in which to do split
  437.  *
  438.  *    Returns:
  439.  *        Pointer to the newly-allocated page
  440.  */
  441.  
  442. BTHEADER *
  443. _bt_allocpg(t)
  444.     BTREE_P t;
  445. {
  446.     BTHEADER *h = t->bt_curpage;
  447.     BTHEADER *nh;
  448.     int nbytes;
  449.  
  450.     /* if we have a cache, let the cache code do the work */
  451.     if (ISDISK(t) && ISCACHE(t)) {
  452.         nh = (BTHEADER *) lrugetnew(t->bt_s.bt_d.d_cache,
  453.                         (int) (t->bt_npages + 1),
  454.                         &nbytes);
  455.     } else {
  456.         nh = (BTHEADER *) cbMALLOC((unsigned) t->bt_psize);
  457.     }
  458.  
  459.     if (nh != (BTHEADER *) NULL) {
  460.         nh->h_pgno = nh->h_prevpg = nh->h_nextpg = P_NONE;
  461.         nh->h_flags = h->h_flags;
  462.         nh->h_lower = (index_t)
  463.                 (((char *) &(nh->h_linp[0])) - ((char *) nh));
  464.         nh->h_upper = t->bt_psize;
  465.     }
  466.  
  467.     return (nh);
  468. }
  469.  
  470. /*
  471.  *  _BT_WRITE -- Write a specific page to a btree file.
  472.  *
  473.  *    Parameters:
  474.  *        t -- btree to get the page
  475.  *        h -- page to write
  476.  *        relflag -- (int) this page may/may not be released
  477.  *
  478.  *    Returns:
  479.  *        RET_SUCCESS, RET_ERROR.
  480.  *
  481.  *    Side Effects:
  482.  *        Writes a metadata page if none has been written yet.
  483.  */
  484.  
  485. int
  486. _bt_write(t, h, relflag)
  487.     BTREE_P t;
  488.     BTHEADER *h;
  489.     int relflag;
  490. {
  491.     long pos;
  492.     int htindex;
  493.     HTBUCKET *b;
  494.     char *cache;
  495.     pgno_t pgno;
  496.  
  497.     h->h_flags &= ~F_DIRTY;
  498.     if (ISDISK(t)) {
  499.  
  500.         /* if we haven't done so yet, write the metadata */
  501.         if (!(t->bt_flags & BTF_METAOK)) {
  502.             if (_bt_wrtmeta(t) == RET_ERROR)
  503.                 return (RET_ERROR);
  504.         }
  505.  
  506.         pgno = h->h_pgno;
  507.  
  508.  
  509.         /* if we have a cache, let the cache code do the work */
  510.         if ((cache = t->bt_s.bt_d.d_cache) != (char *) NULL) {
  511.             if (lruwrite(cache, (int) pgno) < 0)
  512.                 return (RET_ERROR);
  513.             if (relflag && lrurelease(cache, (int) pgno) < 0)
  514.                 return (RET_ERROR);
  515.                 
  516.         } else {
  517.             (void) _bt_pgout(h, (char *) t->bt_lorder);
  518.             /* now write the current page */
  519.             pos = (long) (pgno * t->bt_psize);
  520.             if (ck_lseek(t->bt_s.bt_d.d_fd, pos, SEEK_SET) != pos)
  521.                 return (RET_ERROR);
  522.             if (write(t->bt_s.bt_d.d_fd, (char *) h, (int) t->bt_psize)
  523.                 < t->bt_psize)
  524.                 return (RET_ERROR);
  525.             if (!relflag)
  526.                 (void) _bt_pgin(h, (char *) t->bt_lorder);
  527.         }
  528.     } else {
  529.         /* in-memory btree */
  530.         htindex = HASHKEY(h->h_pgno);
  531.  
  532.         /* see if we need to overwrite existing entry */
  533.         for (b = t->bt_s.bt_ht[htindex];
  534.              b != (HTBUCKET *) NULL;
  535.              b = b->ht_next) {
  536.             if (b->ht_pgno == h->h_pgno) {
  537.                 b->ht_page = h;
  538.                 return (RET_SUCCESS);
  539.             }
  540.         }
  541.  
  542.         /* new entry, write it */
  543.         b = (HTBUCKET *) cbMALLOC((unsigned) sizeof (HTBUCKET));
  544.         if (b == (HTBUCKET *) NULL)
  545.             return (RET_ERROR);
  546.  
  547.         b->ht_pgno = h->h_pgno;
  548.         b->ht_page = h;
  549.         b->ht_next = t->bt_s.bt_ht[htindex];
  550.         t->bt_s.bt_ht[htindex] = b;
  551.     }
  552.     return (RET_SUCCESS);
  553. }
  554.  
  555. /*
  556.  *  _BT_RELEASE -- Release a locked-down cache page
  557.  *
  558.  *    During page splits, we want to force pages out to the cache
  559.  *    before we actually release them, in some cases.  This routine
  560.  *    releases such a page when it is no longer needed.
  561.  *
  562.  *    Parameters:
  563.  *        t -- btree in which to release page
  564.  *        h -- page to release
  565.  *
  566.  *    Returns:
  567.  *        RET_SUCCESS, RET_ERROR.
  568.  *
  569.  *    Side Effects:
  570.  *        None.
  571.  */
  572.  
  573. int
  574. _bt_release(t, h)
  575.     BTREE_P t;
  576.     BTHEADER *h;
  577. {
  578.     if (ISDISK(t) && ISCACHE(t)) {
  579.         if (lrurelease(t->bt_s.bt_d.d_cache, (int) (h->h_pgno)) < 0)
  580.             return (RET_ERROR);
  581.     }
  582.     return (RET_SUCCESS);
  583. }
  584.  
  585. /*
  586.  *  _BT_WRTMETA -- Write metadata to the btree.
  587.  *
  588.  *    Parameters:
  589.  *        t -- tree to which to write
  590.  *
  591.  *    Returns:
  592.  *        RET_SUCCESS, RET_ERROR.
  593.  */
  594.  
  595. int
  596. _bt_wrtmeta(t)
  597.     BTREE_P t;
  598. {
  599.     BTMETA m;
  600.  
  601.     if (ck_lseek(t->bt_s.bt_d.d_fd, 0l, SEEK_SET) != 0l)
  602.         return (RET_ERROR);
  603.  
  604.     /* lorder has to be in host-independent format */
  605.     m.m_lorder = (u_long) htonl((long) t->bt_lorder);
  606.  
  607.     m.m_magic = BTREEMAGIC;
  608.     m.m_version = BTREEVERSION;
  609.     m.m_psize = t->bt_psize;
  610.     m.m_free = t->bt_free;
  611.     m.m_flags = t->bt_flags & BTF_NODUPS;
  612.  
  613.     if (t->bt_lorder != BYTE_ORDER) {
  614.         BLSWAP(m.m_magic);
  615.         BLSWAP(m.m_version);
  616.         BLSWAP(m.m_psize);
  617.         BLSWAP(m.m_free);
  618.         BLSWAP(m.m_flags);
  619.     }
  620.  
  621.     if (write(t->bt_s.bt_d.d_fd, (char *) &m, sizeof(m))
  622.         != sizeof(m)) {
  623.         return (RET_ERROR);
  624.     }
  625.  
  626.     t->bt_flags |= BTF_METAOK;
  627.  
  628.     return (RET_SUCCESS);
  629. }
  630.