home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / dbm / src / hash_buf.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  10.8 KB  |  415 lines
  1. /*-
  2.  * Copyright (c) 1990, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)hash_buf.c    8.5 (Berkeley) 7/15/94";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include "watcomfx.h"
  42.  
  43. /*
  44.  * PACKAGE: hash
  45.  *
  46.  * DESCRIPTION:
  47.  *    Contains buffer management
  48.  *
  49.  * ROUTINES:
  50.  * External
  51.  *    __buf_init
  52.  *    __get_buf
  53.  *    __buf_free
  54.  *    __reclaim_buf
  55.  * Internal
  56.  *    newbuf
  57.  */
  58. #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
  59. #include <sys/param.h>
  60. #endif
  61.  
  62. #include <errno.h>
  63. #include <stddef.h>
  64. #include <stdio.h>
  65. #include <stdlib.h>
  66. #include <string.h>
  67.  
  68. #ifdef DEBUG
  69. #include <assert.h>
  70. #endif
  71.  
  72. #include "mcom_db.h"
  73. #include "hash.h"
  74. #include "page.h"
  75. /* #include "extern.h" */
  76.  
  77. #ifndef NSPR20
  78. #if defined(__sun)
  79. # include "sunos4.h"
  80. #endif /* __sun */
  81. #endif /* NSPR20 */
  82.  
  83. static BUFHEAD *newbuf __P((HTAB *, uint32, BUFHEAD *));
  84.  
  85. /* Unlink B from its place in the lru */
  86. #define BUF_REMOVE(B) { \
  87.     (B)->prev->next = (B)->next; \
  88.     (B)->next->prev = (B)->prev; \
  89. }
  90.  
  91. /* Insert B after P */
  92. #define BUF_INSERT(B, P) { \
  93.     (B)->next = (P)->next; \
  94.     (B)->prev = (P); \
  95.     (P)->next = (B); \
  96.     (B)->next->prev = (B); \
  97. }
  98.  
  99. #define    MRU    hashp->bufhead.next
  100. #define    LRU    hashp->bufhead.prev
  101.  
  102. #define MRU_INSERT(B)    BUF_INSERT((B), &hashp->bufhead)
  103. #define LRU_INSERT(B)    BUF_INSERT((B), LRU)
  104.  
  105. /*
  106.  * We are looking for a buffer with address "addr".  If prev_bp is NULL, then
  107.  * address is a bucket index.  If prev_bp is not NULL, then it points to the
  108.  * page previous to an overflow page that we are trying to find.
  109.  *
  110.  * CAVEAT:  The buffer header accessed via prev_bp's ovfl field may no longer
  111.  * be valid.  Therefore, you must always verify that its address matches the
  112.  * address you are seeking.
  113.  */
  114. extern BUFHEAD *
  115. __get_buf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp, int newpage)
  116. /* If prev_bp set, indicates a new overflow page. */
  117. {
  118.     register BUFHEAD *bp;
  119.     register uint32 is_disk_mask;
  120.     register int is_disk, segment_ndx;
  121.     SEGMENT segp;
  122.  
  123.     is_disk = 0;
  124.     is_disk_mask = 0;
  125.     if (prev_bp) {
  126.         bp = prev_bp->ovfl;
  127.         if (!bp || (bp->addr != addr))
  128.             bp = NULL;
  129.         if (!newpage)
  130.             is_disk = BUF_DISK;
  131.     } else {
  132.         /* Grab buffer out of directory */
  133.         segment_ndx = addr & (hashp->SGSIZE - 1);
  134.  
  135.         /* valid segment ensured by __call_hash() */
  136.         segp = hashp->dir[addr >> hashp->SSHIFT];
  137. #ifdef DEBUG
  138.         assert(segp != NULL);
  139. #endif  
  140.  
  141.         bp = PTROF(segp[segment_ndx]);
  142.  
  143.         is_disk_mask = ISDISK(segp[segment_ndx]);
  144.         is_disk = is_disk_mask || !hashp->new_file;
  145.     }
  146.  
  147.     if (!bp) {
  148.         bp = newbuf(hashp, addr, prev_bp);
  149.         if (!bp)
  150.             return(NULL);
  151.         if(__get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0))
  152.           {
  153.             /* free bp and its page */
  154.             if(prev_bp)
  155.               {
  156.                 /* if prev_bp is set then the new page that
  157.                  * failed is hooked onto prev_bp as an overflow page.
  158.                  * if we don't remove the pointer to the bad page
  159.                  * we may try and access it later and we will die
  160.                  * horribly because it will have already been
  161.                  * free'd and overwritten with bogus data.
  162.                  */
  163.                 prev_bp->ovfl = NULL;
  164.               }
  165.             BUF_REMOVE(bp);
  166.             free(bp->page);
  167.             free(bp);
  168.             return (NULL);
  169.           }
  170.  
  171.         if (!prev_bp)            
  172.           {
  173. #if 0
  174.             /* 16 bit windows and mac can't handle the
  175.              * oring of the is disk flag.
  176.               */            
  177.             segp[segment_ndx] =
  178.                 (BUFHEAD *)((ptrdiff_t)bp | is_disk_mask);
  179. #else   
  180.             /* set the is_disk thing inside the structure
  181.              */
  182.             bp->is_disk = is_disk_mask;
  183.             segp[segment_ndx] = bp;
  184. #endif
  185.           }
  186.     } else {  
  187.         BUF_REMOVE(bp);
  188.         MRU_INSERT(bp);                 
  189.     }
  190.     return (bp);
  191. }
  192.  
  193. /*
  194.  * We need a buffer for this page. Either allocate one, or evict a resident
  195.  * one (if we have as many buffers as we're allowed) and put this one in.
  196.  *
  197.  * If newbuf finds an error (returning NULL), it also sets errno.
  198.  */
  199. static BUFHEAD *
  200. newbuf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp)
  201. {
  202.     register BUFHEAD *bp;        /* The buffer we're going to use */
  203.     register BUFHEAD *xbp;        /* Temp pointer */
  204.     register BUFHEAD *next_xbp;
  205.     SEGMENT segp;
  206.     int segment_ndx;
  207.     uint16 oaddr, *shortp;
  208.  
  209.     oaddr = 0;
  210.     bp = LRU;
  211.     /*
  212.      * If LRU buffer is pinned, the buffer pool is too small. We need to
  213.      * allocate more buffers.
  214.      */
  215.     if (hashp->nbufs || (bp->flags & BUF_PIN)) {
  216.         /* Allocate a new one */
  217.         if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL)
  218.             return (NULL);
  219.  
  220.         /* this memset is supposedly unnecessary but lets add
  221.          * it anyways.
  222.          */
  223.         memset(bp, 0xff, sizeof(BUFHEAD));
  224.  
  225.         if ((bp->page = (char *)malloc(hashp->BSIZE)) == NULL) {
  226.             free(bp);
  227.             return (NULL);
  228.         }
  229.  
  230.         /* this memset is supposedly unnecessary but lets add
  231.          * it anyways.
  232.          */
  233.         memset(bp->page, 0xff, hashp->BSIZE);
  234.  
  235.         if (hashp->nbufs)
  236.             hashp->nbufs--;
  237.     } else {
  238.         /* Kick someone out */
  239.         BUF_REMOVE(bp);
  240.         /*
  241.          * If this is an overflow page with addr 0, it's already been
  242.          * flushed back in an overflow chain and initialized.
  243.          */
  244.         if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) {
  245.             /*
  246.              * Set oaddr before __put_page so that you get it
  247.              * before bytes are swapped.
  248.              */
  249.             shortp = (uint16 *)bp->page;
  250.             if (shortp[0])
  251.               {
  252.                 if(shortp[0] > (hashp->BSIZE / sizeof(uint16)))
  253.                   {
  254.                     return(NULL);
  255.                   }
  256.                 oaddr = shortp[shortp[0] - 1];
  257.               }
  258.             if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page,
  259.                 bp->addr, (int)IS_BUCKET(bp->flags), 0))
  260.                 return (NULL);
  261.             /*
  262.              * Update the pointer to this page (i.e. invalidate it).
  263.              *
  264.              * If this is a new file (i.e. we created it at open
  265.              * time), make sure that we mark pages which have been
  266.              * written to disk so we retrieve them from disk later,
  267.              * rather than allocating new pages.
  268.              */
  269.             if (IS_BUCKET(bp->flags)) {
  270.                 segment_ndx = bp->addr & (hashp->SGSIZE - 1);
  271.                 segp = hashp->dir[bp->addr >> hashp->SSHIFT];
  272. #ifdef DEBUG
  273.                 assert(segp != NULL);
  274. #endif
  275.  
  276.                 if (hashp->new_file &&
  277.                     ((bp->flags & BUF_MOD) ||
  278.                     ISDISK(segp[segment_ndx])))
  279.                     segp[segment_ndx] = (BUFHEAD *)BUF_DISK;
  280.                 else
  281.                     segp[segment_ndx] = NULL;
  282.             }
  283.             /*
  284.              * Since overflow pages can only be access by means of
  285.              * their bucket, free overflow pages associated with
  286.              * this bucket.
  287.              */
  288.             for (xbp = bp; xbp->ovfl;) {
  289.                 next_xbp = xbp->ovfl;
  290.                 xbp->ovfl = 0;
  291.                 xbp = next_xbp;
  292.  
  293.                 /* Check that ovfl pointer is up date. */
  294.                 if (IS_BUCKET(xbp->flags) ||
  295.                     (oaddr != xbp->addr))
  296.                     break;
  297.  
  298.                 shortp = (uint16 *)xbp->page;
  299.                 if (shortp[0])
  300.                   {
  301.                     /* LJM is the number of reported
  302.                      * pages way too much?
  303.                      */
  304.                     if(shortp[0] > hashp->BSIZE/sizeof(uint16))
  305.                         return NULL;
  306.                     /* set before __put_page */
  307.                     oaddr = shortp[shortp[0] - 1];
  308.                   }
  309.                 if ((xbp->flags & BUF_MOD) && __put_page(hashp,
  310.                     xbp->page, xbp->addr, 0, 0))
  311.                     return (NULL);
  312.                 xbp->addr = 0;
  313.                 xbp->flags = 0;
  314.                 BUF_REMOVE(xbp);
  315.                 LRU_INSERT(xbp);
  316.             }
  317.         }
  318.     }
  319.  
  320.     /* Now assign this buffer */
  321.     bp->addr = addr;
  322. #ifdef DEBUG1
  323.     (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n",
  324.         bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0);
  325. #endif
  326.     bp->ovfl = NULL;
  327.     if (prev_bp) {
  328.         /*
  329.          * If prev_bp is set, this is an overflow page, hook it in to
  330.          * the buffer overflow links.
  331.          */
  332. #ifdef DEBUG1
  333.         (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n",
  334.             prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0),
  335.             (bp ? bp->addr : 0));
  336. #endif
  337.         prev_bp->ovfl = bp;
  338.         bp->flags = 0;
  339.     } else
  340.         bp->flags = BUF_BUCKET;
  341.     MRU_INSERT(bp);
  342.     return (bp);
  343. }
  344.  
  345. extern void __buf_init(HTAB *hashp, int32 nbytes)
  346. {
  347.     BUFHEAD *bfp;
  348.     int npages;
  349.  
  350.     bfp = &(hashp->bufhead);
  351.     npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT;
  352.     npages = MAX(npages, MIN_BUFFERS);
  353.  
  354.     hashp->nbufs = npages;
  355.     bfp->next = bfp;
  356.     bfp->prev = bfp;
  357.     /*
  358.      * This space is calloc'd so these are already null.
  359.      *
  360.      * bfp->ovfl = NULL;
  361.      * bfp->flags = 0;
  362.      * bfp->page = NULL;
  363.      * bfp->addr = 0;
  364.      */
  365. }
  366.  
  367. extern int
  368. __buf_free(HTAB *hashp, int do_free, int to_disk)
  369. {
  370.     BUFHEAD *bp;
  371.     int status = -1;
  372.  
  373.     /* Need to make sure that buffer manager has been initialized */
  374.     if (!LRU)
  375.         return (0);
  376.     for (bp = LRU; bp != &hashp->bufhead;) {
  377.         /* Check that the buffer is valid */
  378.         if (bp->addr || IS_BUCKET(bp->flags)) {
  379.             if (to_disk && (bp->flags & BUF_MOD) &&
  380.                 (status = __put_page(hashp, bp->page,
  381.                 bp->addr, IS_BUCKET(bp->flags), 0))) {
  382.               
  383.                 if (do_free) {
  384.                     if (bp->page)
  385.                         free(bp->page);
  386.                     BUF_REMOVE(bp);
  387.                     free(bp);
  388.                 }
  389.                 
  390.                 return (status);
  391.             }
  392.         }
  393.         /* Check if we are freeing stuff */
  394.         if (do_free) {
  395.             if (bp->page)
  396.                 free(bp->page);
  397.             BUF_REMOVE(bp);
  398.             free(bp);
  399.             bp = LRU;
  400.         } else
  401.             bp = bp->prev;
  402.     }
  403.     return (0);
  404. }
  405.  
  406. extern void
  407. __reclaim_buf(HTAB *hashp, BUFHEAD *bp)
  408. {
  409.     bp->ovfl = 0;
  410.     bp->addr = 0;
  411.     bp->flags = 0;
  412.     BUF_REMOVE(bp);
  413.     LRU_INSERT(bp);
  414. }
  415.