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