lib/libc/db/btree/lrutils.c

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