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