lib/libc/db/btree/lruhash.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[] = "@(#)lruhash.c   5.2 (Berkeley) 2/22/91";
  39 #endif /* LIBC_SCCS and not lint */
  40
  41 #include <stdlib.h>
  42 #include "lrucache.h"
  43
  44 #define HASH(l, pgno)   (pgno % l->lru_csize)
  45
  46 /*
  47  *  LRUHASHGET -- Look up a block in the LRU cache by page number.
  48  *
  49  *      Parameters:
  50  *              l -- LRU cache
  51  *              pgno -- number of the logical page to get
  52  *
  53  *      Returns:
  54  *              (CACHE_ENT *) pointer to the associated hash table entry
  55  *              (if any), or NULL (if none).
  56  */
  57
  58 CACHE_ENT *
  59 lruhashget(l, pgno)
  60         LRUCACHE *l;
  61         int pgno;
  62 {
  63         int hashind;
  64         CACHE_ENT *ce;
  65
  66         hashind = HASH(l, pgno);
  67
  68         /* walk the chain */
  69         for (ce = l->lru_cache[hashind];
  70              ce != (CACHE_ENT *) NULL;
  71              ce = ce->c_chain) {
  72                 if (ce->c_pgno == pgno)
  73                         return (ce);
  74         }
  75
  76         return ((CACHE_ENT *) NULL);
  77 }
  78
  79 /*
  80  *  LRUHASHPUT -- Add an entry for a given page to the cache hash table.
  81  *
  82  *      This routine assumes that the given page does not yet have an entry
  83  *      in the table.
  84  *
  85  *      Parameters:
  86  *              l -- LRU cache
  87  *              pgno -- logical page number for this entry
  88  *              lruent -- LRU list entry at which hash table entry should
  89  *                        point
  90  *
  91  *      Returns:
  92  *              (CACHE_ENT *) pointer to the new hash table entry on success,
  93  *              or NULL on failure.
  94  *
  95  *      Side Effects:
  96  *              Allocates memory which should be freed when the hash table
  97  *              entry is removed.
  98  */
  99
 100 CACHE_ENT *
 101 lruhashput(l, pgno, lruent)
 102         LRUCACHE *l;
 103         int pgno;
 104         LRU_ENT *lruent;
 105 {
 106         int hashind;
 107         CACHE_ENT *ce;
 108
 109         if ((ce = (CACHE_ENT *) malloc((unsigned) sizeof(CACHE_ENT)))
 110             == (CACHE_ENT *) NULL)
 111                 return ((CACHE_ENT *) NULL);
 112
 113         hashind = HASH(l, pgno);
 114
 115         ce->c_pgno = pgno;
 116         ce->c_lruent = lruent;
 117         ce->c_chain = l->lru_cache[hashind];
 118         l->lru_cache[hashind] = ce;
 119
 120         return (ce);
 121 }
 122
 123 /*
 124  *  LRUHASHDEL -- Delete the entry for a given page from the LRU cache
 125  *                hash table.
 126  *
 127  *      Parameters:
 128  *              l -- LRU cache
 129  *              pgno -- page number for which we should delete htable entry
 130  *
 131  *      Returns:
 132  *              Zero on success, -1 on failure.
 133  *
 134  *      Side Effects:
 135  *              Releases the memory occupied by the hash table entry.
 136  */
 137
 138 int
 139 lruhashdel(l, pgno)
 140         LRUCACHE *l;
 141         int pgno;
 142 {
 143         CACHE_ENT *ce;
 144         CACHE_ENT *sce;
 145         int hashind;
 146
 147         sce = (CACHE_ENT *) NULL;
 148         hashind = HASH(l, pgno);
 149
 150         /* find the entry we want to delete */
 151         for (ce = l->lru_cache[hashind];
 152              ce != (CACHE_ENT *) NULL;
 153              ce = ce->c_chain) {
 154                 if (ce->c_pgno == pgno)
 155                         break;
 156                 sce = ce;
 157         }
 158
 159         if (ce == (CACHE_ENT *) NULL)
 160                 return (-1);
 161
 162         /* remove it from the chain */
 163         if (sce == (CACHE_ENT *) NULL)
 164                 l->lru_cache[hashind] = ce->c_chain;
 165         else
 166                 sce->c_chain = ce->c_chain;
 167
 168         /* release it */
 169         free ((char *) ce);
 170
 171         /* success */
 172         return (0);
 173 }