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 / lrutils.c < prev    next >
C/C++ Source or Header  |  1993-05-22  |  5KB  |  206 lines
  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include "cdefs.h"
  4. #include "lrucache.h"
  5.  
  6. /*
  7.  *  LRUGETPG -- Get a free page from the LRU cache.
  8.  *
  9.  *    This routine grows the cache if necessary, finds an unused page if
  10.  *    it can, and handles flushing dirty buffers to disk.
  11.  *
  12.  *    One of the parameters to this routine (f) is the routine that called
  13.  *    us.  If we have to grow the cache, we call this routine recursively
  14.  *    in order to fill the buffer.  The reason for this is that we have
  15.  *    two interfaces that call lrugetpg().  Lruget() fills a page from disk,
  16.  *    and lrugetnew() just allocates a new (empty) page.
  17.  *
  18.  *    Parameters:
  19.  *        l -- LRU cache to use.
  20.  *        pgno -- page number for which we want a buffer
  21.  *        nread -- pointer to an int to get number of bytes read
  22.  *        f -- who called us
  23.  *
  24.  *    Returns:
  25.  *        (char *) pointer to buffer to use, or NULL on failure.
  26.  *
  27.  *    Warnings:
  28.  *        The buffer returned is locked down until the user does an
  29.  *        explicit lrurelease() on it.
  30.  */
  31.  
  32. char *
  33. lrugetpg(l, pgno, nread, f)
  34.     LRUCACHE *l;
  35.     int pgno;
  36.     int *nread;
  37.     char *(*f)();
  38. {
  39.     CACHE_ENT *ce;
  40.     LRU_ENT *lruent;
  41.     char *buffer;
  42.  
  43.     /* if we're allowed to grow the cache, do so */
  44.     if (l->lru_cursz < l->lru_csize) {
  45.  
  46.         /* get a buffer */
  47.         if ((buffer = (char *) cbMALLOC((unsigned) l->lru_psize))
  48.             == (char *) NULL)
  49.             return ((char *) NULL);
  50.  
  51.         /* get and LRU list entry */
  52.         if ((lruent = (LRU_ENT *) cbMALLOC((unsigned) sizeof(LRU_ENT)))
  53.             == (LRU_ENT *) NULL)
  54.             return ((char *) NULL);
  55.         lruent->l_buffer = buffer;
  56.         lruent->l_pgno = pgno;
  57.         lruent->l_flags = 0;
  58.  
  59.         /* manage spaghetti */
  60.         lruent->l_prev = (LRU_ENT *) NULL;
  61.         lruent->l_next = l->lru_head;
  62.         if (l->lru_head != (LRU_ENT *) NULL)
  63.             l->lru_head->l_prev = lruent;
  64.         l->lru_head = lruent;
  65.         if (l->lru_tail == (LRU_ENT *) NULL)
  66.             l->lru_tail = lruent;
  67.  
  68.         /* add it to the hash table */
  69.         ce = lruhashput(l, pgno, lruent);
  70.         l->lru_cursz++;
  71.     } else {
  72.         lruent = l->lru_tail;
  73.  
  74.         /* find the oldest unused buffer */
  75.         while (lruent != (LRU_ENT *) NULL
  76.                && !(lruent->l_flags & F_FREE))
  77.             lruent = lruent->l_prev;
  78.  
  79.         /* if no free buffer was found, we have to grow the cache */
  80.         if (lruent == (LRU_ENT *) NULL) {
  81.             if (lrugrow(l) < 0)
  82.                 return ((char *) NULL);
  83.             return ((*f)((LRU) l, pgno, nread));
  84.         }
  85.  
  86.         /* okay, found a free buffer -- update hash table and list */
  87.         ce = lruhashget(l, lruent->l_pgno);
  88.         if (lruhashdel(l, lruent->l_pgno) < 0)
  89.             return ((char *) NULL);
  90.  
  91.         /* flush the old page to disk, if necessary */
  92.         if (lruent->l_flags & F_DIRTY)
  93.             if (lruflush(l, lruent) < 0)
  94.                 return ((char *) NULL);
  95.  
  96.         /* update stats, hash table, and list */
  97.         lruent->l_pgno = pgno;
  98.         lruhead(l, lruent);
  99.         ce = lruhashput(l, pgno, lruent);
  100.         buffer = lruent->l_buffer;
  101.     }
  102. #ifdef lint
  103.     ce = ce;
  104. #endif /* lint */
  105.  
  106.     /* lock this page down */
  107.     lruent->l_flags &= ~F_FREE;
  108.  
  109.     return (buffer);
  110. }
  111.  
  112. /*
  113.  *  LRUHEAD -- Move an LRU list entry to the head of the list.
  114.  *
  115.  *    The head of the list is where the most recently used item goes.
  116.  *
  117.  *    Parameters:
  118.  *        l -- LRU cache
  119.  *        lruent -- entry to move to the head of the list
  120.  *
  121.  *    Returns:
  122.  *        None
  123.  *
  124.  *    Side Effects:
  125.  *        Updates the cache's head and tail pointers as required.
  126.  */
  127.  
  128. void
  129. lruhead(l, lruent)
  130.     LRUCACHE *l;
  131.     LRU_ENT *lruent;
  132. {
  133.     LRU_ENT *next;
  134.     LRU_ENT *prev;
  135.  
  136.     if (l->lru_head == lruent)
  137.         return;
  138.  
  139.     next = lruent->l_next;
  140.     prev = lruent->l_prev;
  141.     lruent->l_prev = (LRU_ENT *) NULL;
  142.     lruent->l_next = l->lru_head;
  143.     l->lru_head->l_prev = lruent;
  144.     l->lru_head = lruent;
  145.  
  146.     prev->l_next = next;
  147.     if (next != (LRU_ENT *) NULL)
  148.         next->l_prev = prev;
  149.  
  150.     if (l->lru_tail == lruent)
  151.         l->lru_tail = prev;
  152. }
  153.  
  154. /*
  155.  *  LRUGROW -- Grow the LRU cache
  156.  *
  157.  *    This routine is called only if we can't satisfy a user's get() request
  158.  *    using an existing buffer.  We need to rebuild the hash table so that
  159.  *    subsequent lookups work correctly, since the cache size is used to
  160.  *    compute hash keys.
  161.  *
  162.  *    Parameters:
  163.  *        l -- LRU cache to grow
  164.  *
  165.  *    Returns:
  166.  *        Zero on success, -1 on failure
  167.  */
  168.  
  169. int
  170. lrugrow(l)
  171.     LRUCACHE *l;
  172. {
  173.     int oldsz, newsz;
  174.     CACHE_ENT **new;
  175.     CACHE_ENT *ce, *nce;
  176.     int h;
  177.     int i;
  178.  
  179.     oldsz = l->lru_csize;
  180.     newsz = l->lru_csize + 1;
  181.  
  182.     /* get a new hash table */
  183.     if ((new = (CACHE_ENT **) cbMALLOC((unsigned)newsz * sizeof(CACHE_ENT *)))
  184.         == (CACHE_ENT **) NULL)
  185.         return (-1);
  186.  
  187.     /* build the new hash table */
  188.     bzero((char *) new, (size_t) (newsz * sizeof(CACHE_ENT *)));
  189.     for (i = oldsz; --i >= 0; ) {
  190.         for (ce = l->lru_cache[i]; ce != (CACHE_ENT *) NULL; ) {
  191.             nce = ce->c_chain;
  192.             h = ce->c_pgno % newsz;
  193.             ce->c_chain = new[h];
  194.             new[h] = ce;
  195.             ce = nce;
  196.         }
  197.     }
  198.  
  199.     /* get rid of the old hash table, and update the cache */
  200.     free ((char *) (l->lru_cache));
  201.     l->lru_cache = new;
  202.     l->lru_csize = newsz;
  203.  
  204.     return (0);
  205. }
  206.