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 / lrucache.c < prev    next >
Text File  |  1993-05-22  |  8KB  |  355 lines
  1.  
  2. /*
  3.  *  lrucache.c -- LRU cache for disk-based btree pages.
  4.  *
  5.  *    This file implements an LRU cache in user space for disk-based
  6.  *    btrees.
  7.  */
  8. #include <fcntl.h>
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12. #include "cdefs.h"
  13. #include "lrucache.h"
  14.  
  15. /*
  16.  *  LRUINIT -- Initialize a new LRU cache.
  17.  *
  18.  *    There's a separate LRU cache for every open file descriptor on which
  19.  *    the user wants caching.  The desired cache size and logical page
  20.  *    size are passed in.  We try to avoid growing the cache beyond the
  21.  *    limit specified by the user, but if we cannot satisfy a block request
  22.  *    without growing the cache, we do so.
  23.  *
  24.  *    Note that the page size passed in is the logical page size for
  25.  *    use with this file descriptor, and doesn't necessarily have anything
  26.  *    to do with the underlying hardware page size.
  27.  *
  28.  *    Parameters:
  29.  *        fd -- file descriptor for this cache
  30.  *        cachesz -- number of buffers in cache (suggested)
  31.  *        pagesz -- logical page size inside this file
  32.  *        inproc -- routine to call when a buffer is read
  33.  *        outproc -- routine to call when a buffer is written
  34.  *
  35.  *    Returns:
  36.  *        Opaque pointer to the LRU cache on success, NULL on failure.
  37.  *
  38.  *    Side Effects:
  39.  *        Allocates memory for the hash table and LRU cache.  Buffers
  40.  *        are allocated on demand, later.
  41.  */
  42. LRU
  43. lruinit(fd, cachesz, pagesz, opaque, inproc, outproc)
  44.     int fd;
  45.     int cachesz;
  46.     int pagesz;
  47.     char *opaque;
  48.     int (*inproc)();
  49.     int (*outproc)();
  50. {
  51.     register LRUCACHE *l;
  52.     int nbytes;
  53.  
  54.     /* allocate the LRU cache struct */
  55.     if ((l = (LRUCACHE *) cbMALLOC((unsigned) sizeof(LRUCACHE)))
  56.         == (LRUCACHE *) NULL)
  57.         return ((LRU) NULL);
  58.  
  59.     /* allocate the hash table */
  60.     nbytes = cachesz * sizeof(CACHE_ENT *);
  61.     if ((l->lru_cache = (CACHE_ENT **) cbMALLOC((unsigned) nbytes))
  62.         == (CACHE_ENT **) NULL) {
  63.         FREE((char *) l);
  64.         return ((LRU) NULL);
  65.     }
  66.  
  67.     /* init memory */
  68.     bzero((char *) (l->lru_cache), (size_t) nbytes);
  69.     l->lru_fd = fd;
  70.     l->lru_psize = pagesz;
  71.     l->lru_csize = cachesz;
  72.     l->lru_cursz = 0;
  73.     l->lru_opaque = opaque;
  74.     l->lru_head = l->lru_tail = (LRU_ENT *) NULL;
  75.     l->lru_inproc = inproc;
  76.     l->lru_outproc = outproc;
  77.  
  78.     return ((LRU) l);
  79. }
  80.  
  81. /*
  82.  *  LRUGET -- Get a buffer from an LRU cache.
  83.  *
  84.  *    If the buffer is not in the cache at present, this routine will
  85.  *    instantiate it from the file.  This REQUIRES that the desired
  86.  *    block actually be on disk; we don't do non-blocking reads, so
  87.  *    if it's not actually out there, this routine won't return for
  88.  *    a very long time.  In order to instantiate a new buffer, use
  89.  *    lrugetnew().
  90.  *
  91.  *    Parameters:
  92.  *        lru -- the LRU cache to use.
  93.  *        pgno -- the logical block number to get.
  94.  *        nread -- pointer to an int, in which the number of bytes
  95.  *             read is returned.
  96.  *
  97.  *    Returns:
  98.  *        (char *) pointer to the buffer for the desired block.  The
  99.  *        number of bytes actually read is returned in *nread.
  100.  *
  101.  *    Warnings:
  102.  *        The requested buffer is locked down until the user does
  103.  *        an explicit lrurelease() on it.
  104.  */
  105.  
  106. char *
  107. lruget(lru, pgno, nread)
  108.     LRU lru;
  109.     int pgno;
  110.     int *nread;
  111. {
  112.     LRUCACHE *l = (LRUCACHE *) lru;
  113.     CACHE_ENT *ce;
  114.     LRU_ENT *lruent;
  115.     char *buffer;
  116.     long pos;
  117.  
  118.     /* is it already in the cache? */
  119.     if ((ce = lruhashget(l, pgno)) != (CACHE_ENT *) NULL) {
  120.  
  121.         /* yes, move it to the head and return it */
  122.         lruent = ce->c_lruent;
  123.         lruent->l_flags &= ~F_FREE;
  124.         lruhead(l, ce->c_lruent);
  125.         *nread = l->lru_psize;
  126.         return (ce->c_lruent->l_buffer);
  127.     }
  128.  
  129.     /* not there, get a free page */
  130.     if ((buffer = lrugetpg(l, pgno, nread, lruget)) == (char *) NULL)
  131.         return ((char *) NULL);
  132.  
  133.     /* okay, got a buffer -- fill it */
  134.     pos = (long) (l->lru_psize * pgno);
  135.     if (ck_lseek(l->lru_fd, pos, SEEK_SET) != pos)
  136.         return ((char *) NULL);
  137.  
  138.     *nread = read(l->lru_fd, buffer, l->lru_psize);
  139.  
  140.     if (l->lru_inproc)
  141.         (*(l->lru_inproc))(buffer, l->lru_opaque);
  142.  
  143.     return (buffer);
  144. }
  145.  
  146. /*
  147.  *  LRUGETNEW -- Get a page for a new block in an LRU cache.
  148.  *
  149.  *    This routine allows users to instantiate pages for a file if they
  150.  *    don't exist on disk yet.  It's used to make a file bigger.
  151.  *
  152.  *    Parameters:
  153.  *        lru -- the LRU cache to use
  154.  *        pgno -- the (new) logical page number to instantiate
  155.  *        nread -- ptr to int to get number of bytes read (this is
  156.  *             guaranteed to be zero, since the page isn't on disk)
  157.  *
  158.  *    Returns:
  159.  *        Pointer to a buffer for the associated page, or NULL on
  160.  *        failure.
  161.  *
  162.  *    Warnings:
  163.  *        The associated buffer is locked down until the user
  164.  *        explicitly does an lrurelease() on it.
  165.  */
  166.  
  167. char *
  168. lrugetnew(lru, pgno, nread)
  169.     LRU lru;
  170.     int pgno;
  171.     int *nread;
  172. {
  173.     LRUCACHE *l = (LRUCACHE *) lru;
  174.  
  175.     *nread = 0;
  176.     return (lrugetpg(l, pgno, nread, lrugetnew));
  177. }
  178.  
  179. /*
  180.  *  LRUFLUSH -- flush an LRU page to disk.
  181.  *
  182.  *    This routine forces a page to disk.  Users should use lruwrite(),
  183.  *    which simply marks a page dirty and does late writing.
  184.  *
  185.  *    Parameters:
  186.  *        l -- LRU cache
  187.  *        lruent -- the LRU cache entry whose page we should flush
  188.  *
  189.  *    Returns:
  190.  *        Zero on success, -1 on failure.
  191.  */
  192.  
  193. lruflush(l, lruent)
  194.     LRUCACHE *l;
  195.     LRU_ENT *lruent;
  196. {
  197.     long pos;
  198.  
  199.     if (l->lru_outproc)
  200.         (*(l->lru_outproc))(lruent->l_buffer, l->lru_opaque);
  201.  
  202.     pos = (long) (l->lru_psize * lruent->l_pgno);
  203.     if (ck_lseek(l->lru_fd, pos, SEEK_SET) != pos)
  204.         return (-1);
  205.     if (write(l->lru_fd, lruent->l_buffer, l->lru_psize) != l->lru_psize)
  206.         return (-1);
  207.  
  208.     if (l->lru_inproc)
  209.         (*(l->lru_inproc))(lruent->l_buffer, l->lru_opaque);
  210.  
  211.     lruent->l_flags &= ~F_DIRTY;
  212.     return (0);
  213. }
  214.  
  215. /*
  216.  *  LRUWRITE -- Mark an LRU cache buffer dirty
  217.  *
  218.  *    This routine is how users should move their changes to disk.  The
  219.  *    cache code marks the associated buffer dirty, and flushes it to
  220.  *    disk if we need to reuse the buffer for some other page.
  221.  *
  222.  *    Parameters:
  223.  *        lru -- LRU cache
  224.  *        pgno -- page number to flush
  225.  *
  226.  *    Returns:
  227.  *        Zero on success, -1 on failure.
  228.  */
  229.  
  230. int
  231. lruwrite(lru, pgno)
  232.     LRU lru;
  233.     int pgno;
  234. {
  235.     LRUCACHE *l = (LRUCACHE *) lru;
  236.     CACHE_ENT *ce;
  237.  
  238.     if ((ce = lruhashget(l, pgno)) == (CACHE_ENT *) NULL)
  239.         return (-1);
  240.  
  241.     /* mark the entry dirty */
  242.     ce->c_lruent->l_flags |= F_DIRTY;
  243.  
  244.     return (0);
  245. }
  246.  
  247. /*
  248.  *  LRUSYNC -- Flush all changes to disk
  249.  *
  250.  *    This routine allows users to force all changes to buffers currently
  251.  *    in memory to disk.  This is expensive.
  252.  *
  253.  *    Parameters:
  254.  *        lru -- LRU cache to flush
  255.  *
  256.  *    Returns:
  257.  *        Zero on success, -1 on failure
  258.  *
  259.  *    Side Effects:
  260.  *        After this call, all buffers are clean.
  261.  */
  262.  
  263. int
  264. lrusync(lru)
  265.     LRU lru;
  266. {
  267.     LRUCACHE *l = (LRUCACHE *) lru;
  268.     LRU_ENT *le;
  269.  
  270.     for (le = l->lru_head; le != (LRU_ENT *) NULL; le = le->l_next)
  271.         if (le->l_flags & F_DIRTY)
  272.             if (lruflush(l, le) < 0)
  273.                 return (-1);
  274.     return (0);
  275. }
  276.  
  277. /*
  278.  *  LRURELEASE -- Release a buffer in the LRU cache for reuse
  279.  *
  280.  *    When the user does an lruget() or lrugetnew(), the buffer we return
  281.  *    is locked down, to guarantee that it's not reused while the user
  282.  *    still needs it.  Once a buffer is no longer needed, it should be
  283.  *    released (via this routine) so that we can use it for other pages
  284.  *    if necessary.
  285.  *
  286.  *    Parameters:
  287.  *        lru -- LRU cache
  288.  *        pgno -- page number of buffer to release
  289.  *
  290.  *    Returns:
  291.  *        Zero on success, -1 on failure
  292.  */
  293.  
  294. int
  295. lrurelease(lru, pgno)
  296.     LRU lru;
  297.     int pgno;
  298. {
  299.     LRUCACHE *l = (LRUCACHE *) lru;
  300.     CACHE_ENT *ce;
  301.  
  302.     if ((ce = lruhashget(l, pgno)) == (CACHE_ENT *) NULL)
  303.         return (-1);
  304.     ce->c_lruent->l_flags |= F_FREE;
  305.     return (0);
  306. }
  307.  
  308. /*
  309.  *  LRUFREE -- Free an entire LRU cache
  310.  *
  311.  *    This routine releases an LRU cache.  The cache should not be
  312.  *    used again.
  313.  *
  314.  *    Parameters:
  315.  *        lru -- LRU cache to free
  316.  *
  317.  *    Returns:
  318.  *        None.
  319.  *
  320.  *    Side Effects:
  321.  *        Frees a lot of memory.
  322.  */
  323.  
  324. void
  325. lrufree(lru)
  326.     LRU lru;
  327. {
  328.     LRUCACHE *l = (LRUCACHE *) lru;
  329.     LRU_ENT *le;
  330.     LRU_ENT *sle;
  331.  
  332.     for (le = l->lru_head; le != (LRU_ENT *) NULL; ) {
  333.         FREE((char *) (le->l_buffer));
  334.         sle = le;
  335.         le = le->l_next;
  336.         FREE((char *) sle);
  337.     }
  338.     FREE ((char *) l);
  339. }
  340.  
  341. int
  342. lrucheckbuf(lru, buffer)
  343.     LRU lru;
  344.     char *buffer;
  345. {
  346.     LRUCACHE *l = (LRUCACHE *) lru;
  347.     LRU_ENT *le;
  348.  
  349.     for (le = l->lru_head; le != (LRU_ENT *) NULL; le = le->l_next) {
  350.         if (le->l_buffer == buffer)
  351.             return 1;
  352.     }
  353.     return 0;
  354. }
  355.