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 *
lruhashget(l,pgno)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 *
lruhashput(l,pgno,lruent)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
lruhashdel(l,pgno)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