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 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)lruhash.c 5.2 (Berkeley) 02/22/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <stdlib.h> 16 #include "lrucache.h" 17 18 #define HASH(l, pgno) (pgno % l->lru_csize) 19 20 /* 21 * LRUHASHGET -- Look up a block in the LRU cache by page number. 22 * 23 * Parameters: 24 * l -- LRU cache 25 * pgno -- number of the logical page to get 26 * 27 * Returns: 28 * (CACHE_ENT *) pointer to the associated hash table entry 29 * (if any), or NULL (if none). 30 */ 31 32 CACHE_ENT * 33 lruhashget(l, pgno) 34 LRUCACHE *l; 35 int pgno; 36 { 37 int hashind; 38 CACHE_ENT *ce; 39 40 hashind = HASH(l, pgno); 41 42 /* walk the chain */ 43 for (ce = l->lru_cache[hashind]; 44 ce != (CACHE_ENT *) NULL; 45 ce = ce->c_chain) { 46 if (ce->c_pgno == pgno) 47 return (ce); 48 } 49 50 return ((CACHE_ENT *) NULL); 51 } 52 53 /* 54 * LRUHASHPUT -- Add an entry for a given page to the cache hash table. 55 * 56 * This routine assumes that the given page does not yet have an entry 57 * in the table. 58 * 59 * Parameters: 60 * l -- LRU cache 61 * pgno -- logical page number for this entry 62 * lruent -- LRU list entry at which hash table entry should 63 * point 64 * 65 * Returns: 66 * (CACHE_ENT *) pointer to the new hash table entry on success, 67 * or NULL on failure. 68 * 69 * Side Effects: 70 * Allocates memory which should be freed when the hash table 71 * entry is removed. 72 */ 73 74 CACHE_ENT * 75 lruhashput(l, pgno, lruent) 76 LRUCACHE *l; 77 int pgno; 78 LRU_ENT *lruent; 79 { 80 int hashind; 81 CACHE_ENT *ce; 82 83 if ((ce = (CACHE_ENT *) malloc((unsigned) sizeof(CACHE_ENT))) 84 == (CACHE_ENT *) NULL) 85 return ((CACHE_ENT *) NULL); 86 87 hashind = HASH(l, pgno); 88 89 ce->c_pgno = pgno; 90 ce->c_lruent = lruent; 91 ce->c_chain = l->lru_cache[hashind]; 92 l->lru_cache[hashind] = ce; 93 94 return (ce); 95 } 96 97 /* 98 * LRUHASHDEL -- Delete the entry for a given page from the LRU cache 99 * hash table. 100 * 101 * Parameters: 102 * l -- LRU cache 103 * pgno -- page number for which we should delete htable entry 104 * 105 * Returns: 106 * Zero on success, -1 on failure. 107 * 108 * Side Effects: 109 * Releases the memory occupied by the hash table entry. 110 */ 111 112 int 113 lruhashdel(l, pgno) 114 LRUCACHE *l; 115 int pgno; 116 { 117 CACHE_ENT *ce; 118 CACHE_ENT *sce; 119 int hashind; 120 121 sce = (CACHE_ENT *) NULL; 122 hashind = HASH(l, pgno); 123 124 /* find the entry we want to delete */ 125 for (ce = l->lru_cache[hashind]; 126 ce != (CACHE_ENT *) NULL; 127 ce = ce->c_chain) { 128 if (ce->c_pgno == pgno) 129 break; 130 sce = ce; 131 } 132 133 if (ce == (CACHE_ENT *) NULL) 134 return (-1); 135 136 /* remove it from the chain */ 137 if (sce == (CACHE_ENT *) NULL) 138 l->lru_cache[hashind] = ce->c_chain; 139 else 140 sce->c_chain = ce->c_chain; 141 142 /* release it */ 143 free ((char *) ce); 144 145 /* success */ 146 return (0); 147 } 148