| @@ -1,959 +1,959 @@ | | | @@ -1,959 +1,959 @@ |
1 | /* $NetBSD: hash_page.c,v 1.1 2008/10/10 00:21:43 joerg Exp $ */ | | 1 | /* $NetBSD: hash_page.c,v 1.2 2008/10/28 17:57:36 joerg Exp $ */ |
2 | /* NetBSD: hash_page.c,v 1.23 2008/09/11 12:58:00 joerg Exp */ | | 2 | /* NetBSD: hash_page.c,v 1.23 2008/09/11 12:58:00 joerg Exp */ |
3 | | | 3 | |
4 | /*- | | 4 | /*- |
5 | * Copyright (c) 1990, 1993, 1994 | | 5 | * Copyright (c) 1990, 1993, 1994 |
6 | * The Regents of the University of California. All rights reserved. | | 6 | * The Regents of the University of California. All rights reserved. |
7 | * | | 7 | * |
8 | * This code is derived from software contributed to Berkeley by | | 8 | * This code is derived from software contributed to Berkeley by |
9 | * Margo Seltzer. | | 9 | * Margo Seltzer. |
10 | * | | 10 | * |
11 | * Redistribution and use in source and binary forms, with or without | | 11 | * Redistribution and use in source and binary forms, with or without |
12 | * modification, are permitted provided that the following conditions | | 12 | * modification, are permitted provided that the following conditions |
13 | * are met: | | 13 | * are met: |
14 | * 1. Redistributions of source code must retain the above copyright | | 14 | * 1. Redistributions of source code must retain the above copyright |
15 | * notice, this list of conditions and the following disclaimer. | | 15 | * notice, this list of conditions and the following disclaimer. |
16 | * 2. Redistributions in binary form must reproduce the above copyright | | 16 | * 2. Redistributions in binary form must reproduce the above copyright |
17 | * notice, this list of conditions and the following disclaimer in the | | 17 | * notice, this list of conditions and the following disclaimer in the |
18 | * documentation and/or other materials provided with the distribution. | | 18 | * documentation and/or other materials provided with the distribution. |
19 | * 3. Neither the name of the University nor the names of its contributors | | 19 | * 3. Neither the name of the University nor the names of its contributors |
20 | * may be used to endorse or promote products derived from this software | | 20 | * may be used to endorse or promote products derived from this software |
21 | * without specific prior written permission. | | 21 | * without specific prior written permission. |
22 | * | | 22 | * |
23 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | | 23 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
24 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | | 24 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
25 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | | 25 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
26 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | | 26 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
27 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | | 27 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
28 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | | 28 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
29 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | | 29 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
30 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | | 30 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
31 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | | 31 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
32 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | | 32 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
33 | * SUCH DAMAGE. | | 33 | * SUCH DAMAGE. |
34 | */ | | 34 | */ |
35 | | | 35 | |
36 | #include <nbcompat.h> | | 36 | #include <nbcompat.h> |
37 | #include <nbcompat/cdefs.h> | | 37 | #include <nbcompat/cdefs.h> |
38 | | | 38 | |
39 | __RCSID("$NetBSD: hash_page.c,v 1.1 2008/10/10 00:21:43 joerg Exp $"); | | 39 | __RCSID("$NetBSD: hash_page.c,v 1.2 2008/10/28 17:57:36 joerg Exp $"); |
40 | | | 40 | |
41 | /* | | 41 | /* |
42 | * PACKAGE: hashing | | 42 | * PACKAGE: hashing |
43 | * | | 43 | * |
44 | * DESCRIPTION: | | 44 | * DESCRIPTION: |
45 | * Page manipulation for hashing package. | | 45 | * Page manipulation for hashing package. |
46 | * | | 46 | * |
47 | * ROUTINES: | | 47 | * ROUTINES: |
48 | * | | 48 | * |
49 | * External | | 49 | * External |
50 | * __get_page | | 50 | * __get_page |
51 | * __add_ovflpage | | 51 | * __add_ovflpage |
52 | * Internal | | 52 | * Internal |
53 | * overflow_page | | 53 | * overflow_page |
54 | * open_temp | | 54 | * open_temp |
55 | */ | | 55 | */ |
56 | | | 56 | |
57 | #include <sys/types.h> | | 57 | #include <sys/types.h> |
58 | | | 58 | |
59 | #include <errno.h> | | 59 | #include <errno.h> |
60 | #include <fcntl.h> | | 60 | #include <fcntl.h> |
61 | #include <signal.h> | | 61 | #include <signal.h> |
62 | #include <stdio.h> | | 62 | #include <stdio.h> |
63 | #include <stdlib.h> | | 63 | #include <stdlib.h> |
64 | #include <string.h> | | 64 | #include <string.h> |
65 | #include <unistd.h> | | 65 | #include <unistd.h> |
66 | #include <paths.h> | | 66 | #include <nbcompat/paths.h> |
67 | #include <assert.h> | | 67 | #include <assert.h> |
68 | | | 68 | |
69 | #include <nbcompat/db.h> | | 69 | #include <nbcompat/db.h> |
70 | #include "hash.h" | | 70 | #include "hash.h" |
71 | #include "page.h" | | 71 | #include "page.h" |
72 | #include "extern.h" | | 72 | #include "extern.h" |
73 | | | 73 | |
74 | static uint32_t *fetch_bitmap(HTAB *, int); | | 74 | static uint32_t *fetch_bitmap(HTAB *, int); |
75 | static uint32_t first_free(uint32_t); | | 75 | static uint32_t first_free(uint32_t); |
76 | static int open_temp(HTAB *); | | 76 | static int open_temp(HTAB *); |
77 | static uint16_t overflow_page(HTAB *); | | 77 | static uint16_t overflow_page(HTAB *); |
78 | static void putpair(char *, const DBT *, const DBT *); | | 78 | static void putpair(char *, const DBT *, const DBT *); |
79 | static void squeeze_key(uint16_t *, const DBT *, const DBT *); | | 79 | static void squeeze_key(uint16_t *, const DBT *, const DBT *); |
80 | static int ugly_split(HTAB *, uint32_t, BUFHEAD *, BUFHEAD *, int, int); | | 80 | static int ugly_split(HTAB *, uint32_t, BUFHEAD *, BUFHEAD *, int, int); |
81 | | | 81 | |
82 | #define PAGE_INIT(P) { \ | | 82 | #define PAGE_INIT(P) { \ |
83 | ((uint16_t *)(void *)(P))[0] = 0; \ | | 83 | ((uint16_t *)(void *)(P))[0] = 0; \ |
84 | temp = 3 * sizeof(uint16_t); \ | | 84 | temp = 3 * sizeof(uint16_t); \ |
85 | _DIAGASSERT(hashp->BSIZE >= temp); \ | | 85 | _DIAGASSERT(hashp->BSIZE >= temp); \ |
86 | ((uint16_t *)(void *)(P))[1] = (uint16_t)(hashp->BSIZE - temp); \ | | 86 | ((uint16_t *)(void *)(P))[1] = (uint16_t)(hashp->BSIZE - temp); \ |
87 | ((uint16_t *)(void *)(P))[2] = hashp->BSIZE; \ | | 87 | ((uint16_t *)(void *)(P))[2] = hashp->BSIZE; \ |
88 | } | | 88 | } |
89 | | | 89 | |
90 | /* | | 90 | /* |
91 | * This is called AFTER we have verified that there is room on the page for | | 91 | * This is called AFTER we have verified that there is room on the page for |
92 | * the pair (PAIRFITS has returned true) so we go right ahead and start moving | | 92 | * the pair (PAIRFITS has returned true) so we go right ahead and start moving |
93 | * stuff on. | | 93 | * stuff on. |
94 | */ | | 94 | */ |
95 | static void | | 95 | static void |
96 | putpair(char *p, const DBT *key, const DBT *val) | | 96 | putpair(char *p, const DBT *key, const DBT *val) |
97 | { | | 97 | { |
98 | uint16_t *bp, n, off; | | 98 | uint16_t *bp, n, off; |
99 | size_t temp; | | 99 | size_t temp; |
100 | | | 100 | |
101 | bp = (uint16_t *)(void *)p; | | 101 | bp = (uint16_t *)(void *)p; |
102 | | | 102 | |
103 | /* Enter the key first. */ | | 103 | /* Enter the key first. */ |
104 | n = bp[0]; | | 104 | n = bp[0]; |
105 | | | 105 | |
106 | temp = OFFSET(bp); | | 106 | temp = OFFSET(bp); |
107 | _DIAGASSERT(temp >= key->size); | | 107 | _DIAGASSERT(temp >= key->size); |
108 | off = (uint16_t)(temp - key->size); | | 108 | off = (uint16_t)(temp - key->size); |
109 | memmove(p + off, key->data, key->size); | | 109 | memmove(p + off, key->data, key->size); |
110 | bp[++n] = off; | | 110 | bp[++n] = off; |
111 | | | 111 | |
112 | /* Now the data. */ | | 112 | /* Now the data. */ |
113 | _DIAGASSERT(off >= val->size); | | 113 | _DIAGASSERT(off >= val->size); |
114 | off -= (uint16_t)val->size; | | 114 | off -= (uint16_t)val->size; |
115 | memmove(p + off, val->data, val->size); | | 115 | memmove(p + off, val->data, val->size); |
116 | bp[++n] = off; | | 116 | bp[++n] = off; |
117 | | | 117 | |
118 | /* Adjust page info. */ | | 118 | /* Adjust page info. */ |
119 | bp[0] = n; | | 119 | bp[0] = n; |
120 | temp = (n + 3) * sizeof(uint16_t); | | 120 | temp = (n + 3) * sizeof(uint16_t); |
121 | _DIAGASSERT(off >= temp); | | 121 | _DIAGASSERT(off >= temp); |
122 | bp[n + 1] = (uint16_t)(off - temp); | | 122 | bp[n + 1] = (uint16_t)(off - temp); |
123 | bp[n + 2] = off; | | 123 | bp[n + 2] = off; |
124 | } | | 124 | } |
125 | | | 125 | |
126 | /* | | 126 | /* |
127 | * Returns: | | 127 | * Returns: |
128 | * 0 OK | | 128 | * 0 OK |
129 | * -1 error | | 129 | * -1 error |
130 | */ | | 130 | */ |
131 | int | | 131 | int |
132 | __delpair(HTAB *hashp, BUFHEAD *bufp, int ndx) | | 132 | __delpair(HTAB *hashp, BUFHEAD *bufp, int ndx) |
133 | { | | 133 | { |
134 | uint16_t *bp, newoff; | | 134 | uint16_t *bp, newoff; |
135 | int n; | | 135 | int n; |
136 | uint16_t pairlen; | | 136 | uint16_t pairlen; |
137 | size_t temp; | | 137 | size_t temp; |
138 | | | 138 | |
139 | bp = (uint16_t *)(void *)bufp->page; | | 139 | bp = (uint16_t *)(void *)bufp->page; |
140 | n = bp[0]; | | 140 | n = bp[0]; |
141 | | | 141 | |
142 | if (bp[ndx + 1] < REAL_KEY) | | 142 | if (bp[ndx + 1] < REAL_KEY) |
143 | return (__big_delete(hashp, bufp)); | | 143 | return (__big_delete(hashp, bufp)); |
144 | if (ndx != 1) | | 144 | if (ndx != 1) |
145 | newoff = bp[ndx - 1]; | | 145 | newoff = bp[ndx - 1]; |
146 | else | | 146 | else |
147 | newoff = hashp->BSIZE; | | 147 | newoff = hashp->BSIZE; |
148 | pairlen = newoff - bp[ndx + 1]; | | 148 | pairlen = newoff - bp[ndx + 1]; |
149 | | | 149 | |
150 | if (ndx != (n - 1)) { | | 150 | if (ndx != (n - 1)) { |
151 | /* Hard Case -- need to shuffle keys */ | | 151 | /* Hard Case -- need to shuffle keys */ |
152 | int i; | | 152 | int i; |
153 | char *src = bufp->page + (int)OFFSET(bp); | | 153 | char *src = bufp->page + (int)OFFSET(bp); |
154 | char *dst = src + (int)pairlen; | | 154 | char *dst = src + (int)pairlen; |
155 | memmove(dst, src, (size_t)(bp[ndx + 1] - OFFSET(bp))); | | 155 | memmove(dst, src, (size_t)(bp[ndx + 1] - OFFSET(bp))); |
156 | | | 156 | |
157 | /* Now adjust the pointers */ | | 157 | /* Now adjust the pointers */ |
158 | for (i = ndx + 2; i <= n; i += 2) { | | 158 | for (i = ndx + 2; i <= n; i += 2) { |
159 | if (bp[i + 1] == OVFLPAGE) { | | 159 | if (bp[i + 1] == OVFLPAGE) { |
160 | bp[i - 2] = bp[i]; | | 160 | bp[i - 2] = bp[i]; |
161 | bp[i - 1] = bp[i + 1]; | | 161 | bp[i - 1] = bp[i + 1]; |
162 | } else { | | 162 | } else { |
163 | bp[i - 2] = bp[i] + pairlen; | | 163 | bp[i - 2] = bp[i] + pairlen; |
164 | bp[i - 1] = bp[i + 1] + pairlen; | | 164 | bp[i - 1] = bp[i + 1] + pairlen; |
165 | } | | 165 | } |
166 | } | | 166 | } |
167 | } | | 167 | } |
168 | /* Finally adjust the page data */ | | 168 | /* Finally adjust the page data */ |
169 | bp[n] = OFFSET(bp) + pairlen; | | 169 | bp[n] = OFFSET(bp) + pairlen; |
170 | temp = bp[n + 1] + pairlen + 2 * sizeof(uint16_t); | | 170 | temp = bp[n + 1] + pairlen + 2 * sizeof(uint16_t); |
171 | _DIAGASSERT(temp <= 0xffff); | | 171 | _DIAGASSERT(temp <= 0xffff); |
172 | bp[n - 1] = (uint16_t)temp; | | 172 | bp[n - 1] = (uint16_t)temp; |
173 | bp[0] = n - 2; | | 173 | bp[0] = n - 2; |
174 | hashp->NKEYS--; | | 174 | hashp->NKEYS--; |
175 | | | 175 | |
176 | bufp->flags |= BUF_MOD; | | 176 | bufp->flags |= BUF_MOD; |
177 | return (0); | | 177 | return (0); |
178 | } | | 178 | } |
179 | /* | | 179 | /* |
180 | * Returns: | | 180 | * Returns: |
181 | * 0 ==> OK | | 181 | * 0 ==> OK |
182 | * -1 ==> Error | | 182 | * -1 ==> Error |
183 | */ | | 183 | */ |
184 | int | | 184 | int |
185 | __split_page(HTAB *hashp, uint32_t obucket, uint32_t nbucket) | | 185 | __split_page(HTAB *hashp, uint32_t obucket, uint32_t nbucket) |
186 | { | | 186 | { |
187 | BUFHEAD *new_bufp, *old_bufp; | | 187 | BUFHEAD *new_bufp, *old_bufp; |
188 | uint16_t *ino; | | 188 | uint16_t *ino; |
189 | char *np; | | 189 | char *np; |
190 | DBT key, val; | | 190 | DBT key, val; |
191 | int n, ndx, retval; | | 191 | int n, ndx, retval; |
192 | uint16_t copyto, diff, off, moved; | | 192 | uint16_t copyto, diff, off, moved; |
193 | char *op; | | 193 | char *op; |
194 | size_t temp; | | 194 | size_t temp; |
195 | | | 195 | |
196 | copyto = (uint16_t)hashp->BSIZE; | | 196 | copyto = (uint16_t)hashp->BSIZE; |
197 | off = (uint16_t)hashp->BSIZE; | | 197 | off = (uint16_t)hashp->BSIZE; |
198 | old_bufp = __get_buf(hashp, obucket, NULL, 0); | | 198 | old_bufp = __get_buf(hashp, obucket, NULL, 0); |
199 | if (old_bufp == NULL) | | 199 | if (old_bufp == NULL) |
200 | return (-1); | | 200 | return (-1); |
201 | new_bufp = __get_buf(hashp, nbucket, NULL, 0); | | 201 | new_bufp = __get_buf(hashp, nbucket, NULL, 0); |
202 | if (new_bufp == NULL) | | 202 | if (new_bufp == NULL) |
203 | return (-1); | | 203 | return (-1); |
204 | | | 204 | |
205 | old_bufp->flags |= (BUF_MOD | BUF_PIN); | | 205 | old_bufp->flags |= (BUF_MOD | BUF_PIN); |
206 | new_bufp->flags |= (BUF_MOD | BUF_PIN); | | 206 | new_bufp->flags |= (BUF_MOD | BUF_PIN); |
207 | | | 207 | |
208 | ino = (uint16_t *)(void *)(op = old_bufp->page); | | 208 | ino = (uint16_t *)(void *)(op = old_bufp->page); |
209 | np = new_bufp->page; | | 209 | np = new_bufp->page; |
210 | | | 210 | |
211 | moved = 0; | | 211 | moved = 0; |
212 | | | 212 | |
213 | for (n = 1, ndx = 1; n < ino[0]; n += 2) { | | 213 | for (n = 1, ndx = 1; n < ino[0]; n += 2) { |
214 | if (ino[n + 1] < REAL_KEY) { | | 214 | if (ino[n + 1] < REAL_KEY) { |
215 | retval = ugly_split(hashp, obucket, old_bufp, new_bufp, | | 215 | retval = ugly_split(hashp, obucket, old_bufp, new_bufp, |
216 | (int)copyto, (int)moved); | | 216 | (int)copyto, (int)moved); |
217 | old_bufp->flags &= ~BUF_PIN; | | 217 | old_bufp->flags &= ~BUF_PIN; |
218 | new_bufp->flags &= ~BUF_PIN; | | 218 | new_bufp->flags &= ~BUF_PIN; |
219 | return (retval); | | 219 | return (retval); |
220 | | | 220 | |
221 | } | | 221 | } |
222 | key.data = (uint8_t *)op + ino[n]; | | 222 | key.data = (uint8_t *)op + ino[n]; |
223 | key.size = off - ino[n]; | | 223 | key.size = off - ino[n]; |
224 | | | 224 | |
225 | if (__call_hash(hashp, key.data, (int)key.size) == obucket) { | | 225 | if (__call_hash(hashp, key.data, (int)key.size) == obucket) { |
226 | /* Don't switch page */ | | 226 | /* Don't switch page */ |
227 | diff = copyto - off; | | 227 | diff = copyto - off; |
228 | if (diff) { | | 228 | if (diff) { |
229 | copyto = ino[n + 1] + diff; | | 229 | copyto = ino[n + 1] + diff; |
230 | memmove(op + copyto, op + ino[n + 1], | | 230 | memmove(op + copyto, op + ino[n + 1], |
231 | (size_t)(off - ino[n + 1])); | | 231 | (size_t)(off - ino[n + 1])); |
232 | ino[ndx] = copyto + ino[n] - ino[n + 1]; | | 232 | ino[ndx] = copyto + ino[n] - ino[n + 1]; |
233 | ino[ndx + 1] = copyto; | | 233 | ino[ndx + 1] = copyto; |
234 | } else | | 234 | } else |
235 | copyto = ino[n + 1]; | | 235 | copyto = ino[n + 1]; |
236 | ndx += 2; | | 236 | ndx += 2; |
237 | } else { | | 237 | } else { |
238 | /* Switch page */ | | 238 | /* Switch page */ |
239 | val.data = (uint8_t *)op + ino[n + 1]; | | 239 | val.data = (uint8_t *)op + ino[n + 1]; |
240 | val.size = ino[n] - ino[n + 1]; | | 240 | val.size = ino[n] - ino[n + 1]; |
241 | putpair(np, &key, &val); | | 241 | putpair(np, &key, &val); |
242 | moved += 2; | | 242 | moved += 2; |
243 | } | | 243 | } |
244 | | | 244 | |
245 | off = ino[n + 1]; | | 245 | off = ino[n + 1]; |
246 | } | | 246 | } |
247 | | | 247 | |
248 | /* Now clean up the page */ | | 248 | /* Now clean up the page */ |
249 | ino[0] -= moved; | | 249 | ino[0] -= moved; |
250 | temp = sizeof(uint16_t) * (ino[0] + 3); | | 250 | temp = sizeof(uint16_t) * (ino[0] + 3); |
251 | _DIAGASSERT(copyto >= temp); | | 251 | _DIAGASSERT(copyto >= temp); |
252 | FREESPACE(ino) = (uint16_t)(copyto - temp); | | 252 | FREESPACE(ino) = (uint16_t)(copyto - temp); |
253 | OFFSET(ino) = copyto; | | 253 | OFFSET(ino) = copyto; |
254 | | | 254 | |
255 | #ifdef DEBUG3 | | 255 | #ifdef DEBUG3 |
256 | (void)fprintf(stderr, "split %d/%d\n", | | 256 | (void)fprintf(stderr, "split %d/%d\n", |
257 | ((uint16_t *)np)[0] / 2, | | 257 | ((uint16_t *)np)[0] / 2, |
258 | ((uint16_t *)op)[0] / 2); | | 258 | ((uint16_t *)op)[0] / 2); |
259 | #endif | | 259 | #endif |
260 | /* unpin both pages */ | | 260 | /* unpin both pages */ |
261 | old_bufp->flags &= ~BUF_PIN; | | 261 | old_bufp->flags &= ~BUF_PIN; |
262 | new_bufp->flags &= ~BUF_PIN; | | 262 | new_bufp->flags &= ~BUF_PIN; |
263 | return (0); | | 263 | return (0); |
264 | } | | 264 | } |
265 | | | 265 | |
266 | /* | | 266 | /* |
267 | * Called when we encounter an overflow or big key/data page during split | | 267 | * Called when we encounter an overflow or big key/data page during split |
268 | * handling. This is special cased since we have to begin checking whether | | 268 | * handling. This is special cased since we have to begin checking whether |
269 | * the key/data pairs fit on their respective pages and because we may need | | 269 | * the key/data pairs fit on their respective pages and because we may need |
270 | * overflow pages for both the old and new pages. | | 270 | * overflow pages for both the old and new pages. |
271 | * | | 271 | * |
272 | * The first page might be a page with regular key/data pairs in which case | | 272 | * The first page might be a page with regular key/data pairs in which case |
273 | * we have a regular overflow condition and just need to go on to the next | | 273 | * we have a regular overflow condition and just need to go on to the next |
274 | * page or it might be a big key/data pair in which case we need to fix the | | 274 | * page or it might be a big key/data pair in which case we need to fix the |
275 | * big key/data pair. | | 275 | * big key/data pair. |
276 | * | | 276 | * |
277 | * Returns: | | 277 | * Returns: |
278 | * 0 ==> success | | 278 | * 0 ==> success |
279 | * -1 ==> failure | | 279 | * -1 ==> failure |
280 | */ | | 280 | */ |
281 | static int | | 281 | static int |
282 | ugly_split( | | 282 | ugly_split( |
283 | HTAB *hashp, | | 283 | HTAB *hashp, |
284 | uint32_t obucket, /* Same as __split_page. */ | | 284 | uint32_t obucket, /* Same as __split_page. */ |
285 | BUFHEAD *old_bufp, | | 285 | BUFHEAD *old_bufp, |
286 | BUFHEAD *new_bufp, | | 286 | BUFHEAD *new_bufp, |
287 | int copyto, /* First byte on page which contains key/data values. */ | | 287 | int copyto, /* First byte on page which contains key/data values. */ |
288 | int moved /* Number of pairs moved to new page. */ | | 288 | int moved /* Number of pairs moved to new page. */ |
289 | ) | | 289 | ) |
290 | { | | 290 | { |
291 | BUFHEAD *bufp; /* Buffer header for ino */ | | 291 | BUFHEAD *bufp; /* Buffer header for ino */ |
292 | uint16_t *ino; /* Page keys come off of */ | | 292 | uint16_t *ino; /* Page keys come off of */ |
293 | uint16_t *np; /* New page */ | | 293 | uint16_t *np; /* New page */ |
294 | uint16_t *op; /* Page keys go on to if they aren't moving */ | | 294 | uint16_t *op; /* Page keys go on to if they aren't moving */ |
295 | size_t temp; | | 295 | size_t temp; |
296 | | | 296 | |
297 | BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ | | 297 | BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ |
298 | DBT key, val; | | 298 | DBT key, val; |
299 | SPLIT_RETURN ret; | | 299 | SPLIT_RETURN ret; |
300 | uint16_t n, off, ov_addr, scopyto; | | 300 | uint16_t n, off, ov_addr, scopyto; |
301 | char *cino; /* Character value of ino */ | | 301 | char *cino; /* Character value of ino */ |
302 | | | 302 | |
303 | bufp = old_bufp; | | 303 | bufp = old_bufp; |
304 | ino = (uint16_t *)(void *)old_bufp->page; | | 304 | ino = (uint16_t *)(void *)old_bufp->page; |
305 | np = (uint16_t *)(void *)new_bufp->page; | | 305 | np = (uint16_t *)(void *)new_bufp->page; |
306 | op = (uint16_t *)(void *)old_bufp->page; | | 306 | op = (uint16_t *)(void *)old_bufp->page; |
307 | last_bfp = NULL; | | 307 | last_bfp = NULL; |
308 | scopyto = (uint16_t)copyto; /* ANSI */ | | 308 | scopyto = (uint16_t)copyto; /* ANSI */ |
309 | | | 309 | |
310 | n = ino[0] - 1; | | 310 | n = ino[0] - 1; |
311 | while (n < ino[0]) { | | 311 | while (n < ino[0]) { |
312 | if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) { | | 312 | if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) { |
313 | if (__big_split(hashp, old_bufp, | | 313 | if (__big_split(hashp, old_bufp, |
314 | new_bufp, bufp, (int)bufp->addr, obucket, &ret)) | | 314 | new_bufp, bufp, (int)bufp->addr, obucket, &ret)) |
315 | return (-1); | | 315 | return (-1); |
316 | old_bufp = ret.oldp; | | 316 | old_bufp = ret.oldp; |
317 | if (!old_bufp) | | 317 | if (!old_bufp) |
318 | return (-1); | | 318 | return (-1); |
319 | op = (uint16_t *)(void *)old_bufp->page; | | 319 | op = (uint16_t *)(void *)old_bufp->page; |
320 | new_bufp = ret.newp; | | 320 | new_bufp = ret.newp; |
321 | if (!new_bufp) | | 321 | if (!new_bufp) |
322 | return (-1); | | 322 | return (-1); |
323 | np = (uint16_t *)(void *)new_bufp->page; | | 323 | np = (uint16_t *)(void *)new_bufp->page; |
324 | bufp = ret.nextp; | | 324 | bufp = ret.nextp; |
325 | if (!bufp) | | 325 | if (!bufp) |
326 | return (0); | | 326 | return (0); |
327 | cino = (char *)bufp->page; | | 327 | cino = (char *)bufp->page; |
328 | ino = (uint16_t *)(void *)cino; | | 328 | ino = (uint16_t *)(void *)cino; |
329 | last_bfp = ret.nextp; | | 329 | last_bfp = ret.nextp; |
330 | } else if (ino[n + 1] == OVFLPAGE) { | | 330 | } else if (ino[n + 1] == OVFLPAGE) { |
331 | ov_addr = ino[n]; | | 331 | ov_addr = ino[n]; |
332 | /* | | 332 | /* |
333 | * Fix up the old page -- the extra 2 are the fields | | 333 | * Fix up the old page -- the extra 2 are the fields |
334 | * which contained the overflow information. | | 334 | * which contained the overflow information. |
335 | */ | | 335 | */ |
336 | ino[0] -= (moved + 2); | | 336 | ino[0] -= (moved + 2); |
337 | temp = sizeof(uint16_t) * (ino[0] + 3); | | 337 | temp = sizeof(uint16_t) * (ino[0] + 3); |
338 | _DIAGASSERT(scopyto >= temp); | | 338 | _DIAGASSERT(scopyto >= temp); |
339 | FREESPACE(ino) = (uint16_t)(scopyto - temp); | | 339 | FREESPACE(ino) = (uint16_t)(scopyto - temp); |
340 | OFFSET(ino) = scopyto; | | 340 | OFFSET(ino) = scopyto; |
341 | | | 341 | |
342 | bufp = __get_buf(hashp, (uint32_t)ov_addr, bufp, 0); | | 342 | bufp = __get_buf(hashp, (uint32_t)ov_addr, bufp, 0); |
343 | if (!bufp) | | 343 | if (!bufp) |
344 | return (-1); | | 344 | return (-1); |
345 | | | 345 | |
346 | ino = (uint16_t *)(void *)bufp->page; | | 346 | ino = (uint16_t *)(void *)bufp->page; |
347 | n = 1; | | 347 | n = 1; |
348 | scopyto = hashp->BSIZE; | | 348 | scopyto = hashp->BSIZE; |
349 | moved = 0; | | 349 | moved = 0; |
350 | | | 350 | |
351 | if (last_bfp) | | 351 | if (last_bfp) |
352 | __free_ovflpage(hashp, last_bfp); | | 352 | __free_ovflpage(hashp, last_bfp); |
353 | last_bfp = bufp; | | 353 | last_bfp = bufp; |
354 | } | | 354 | } |
355 | /* Move regular sized pairs of there are any */ | | 355 | /* Move regular sized pairs of there are any */ |
356 | off = hashp->BSIZE; | | 356 | off = hashp->BSIZE; |
357 | for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) { | | 357 | for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) { |
358 | cino = (char *)(void *)ino; | | 358 | cino = (char *)(void *)ino; |
359 | key.data = (uint8_t *)cino + ino[n]; | | 359 | key.data = (uint8_t *)cino + ino[n]; |
360 | key.size = off - ino[n]; | | 360 | key.size = off - ino[n]; |
361 | val.data = (uint8_t *)cino + ino[n + 1]; | | 361 | val.data = (uint8_t *)cino + ino[n + 1]; |
362 | val.size = ino[n] - ino[n + 1]; | | 362 | val.size = ino[n] - ino[n + 1]; |
363 | off = ino[n + 1]; | | 363 | off = ino[n + 1]; |
364 | | | 364 | |
365 | if (__call_hash(hashp, key.data, (int)key.size) == obucket) { | | 365 | if (__call_hash(hashp, key.data, (int)key.size) == obucket) { |
366 | /* Keep on old page */ | | 366 | /* Keep on old page */ |
367 | if (PAIRFITS(op, (&key), (&val))) | | 367 | if (PAIRFITS(op, (&key), (&val))) |
368 | putpair((char *)(void *)op, &key, &val); | | 368 | putpair((char *)(void *)op, &key, &val); |
369 | else { | | 369 | else { |
370 | old_bufp = | | 370 | old_bufp = |
371 | __add_ovflpage(hashp, old_bufp); | | 371 | __add_ovflpage(hashp, old_bufp); |
372 | if (!old_bufp) | | 372 | if (!old_bufp) |
373 | return (-1); | | 373 | return (-1); |
374 | op = (uint16_t *)(void *)old_bufp->page; | | 374 | op = (uint16_t *)(void *)old_bufp->page; |
375 | putpair((char *)(void *)op, &key, &val); | | 375 | putpair((char *)(void *)op, &key, &val); |
376 | } | | 376 | } |
377 | old_bufp->flags |= BUF_MOD; | | 377 | old_bufp->flags |= BUF_MOD; |
378 | } else { | | 378 | } else { |
379 | /* Move to new page */ | | 379 | /* Move to new page */ |
380 | if (PAIRFITS(np, (&key), (&val))) | | 380 | if (PAIRFITS(np, (&key), (&val))) |
381 | putpair((char *)(void *)np, &key, &val); | | 381 | putpair((char *)(void *)np, &key, &val); |
382 | else { | | 382 | else { |
383 | new_bufp = | | 383 | new_bufp = |
384 | __add_ovflpage(hashp, new_bufp); | | 384 | __add_ovflpage(hashp, new_bufp); |
385 | if (!new_bufp) | | 385 | if (!new_bufp) |
386 | return (-1); | | 386 | return (-1); |
387 | np = (uint16_t *)(void *)new_bufp->page; | | 387 | np = (uint16_t *)(void *)new_bufp->page; |
388 | putpair((char *)(void *)np, &key, &val); | | 388 | putpair((char *)(void *)np, &key, &val); |
389 | } | | 389 | } |
390 | new_bufp->flags |= BUF_MOD; | | 390 | new_bufp->flags |= BUF_MOD; |
391 | } | | 391 | } |
392 | } | | 392 | } |
393 | } | | 393 | } |
394 | if (last_bfp) | | 394 | if (last_bfp) |
395 | __free_ovflpage(hashp, last_bfp); | | 395 | __free_ovflpage(hashp, last_bfp); |
396 | return (0); | | 396 | return (0); |
397 | } | | 397 | } |
398 | | | 398 | |
399 | /* | | 399 | /* |
400 | * Add the given pair to the page | | 400 | * Add the given pair to the page |
401 | * | | 401 | * |
402 | * Returns: | | 402 | * Returns: |
403 | * 0 ==> OK | | 403 | * 0 ==> OK |
404 | * 1 ==> failure | | 404 | * 1 ==> failure |
405 | */ | | 405 | */ |
406 | int | | 406 | int |
407 | __addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) | | 407 | __addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) |
408 | { | | 408 | { |
409 | uint16_t *bp, *sop; | | 409 | uint16_t *bp, *sop; |
410 | int do_expand; | | 410 | int do_expand; |
411 | | | 411 | |
412 | bp = (uint16_t *)(void *)bufp->page; | | 412 | bp = (uint16_t *)(void *)bufp->page; |
413 | do_expand = 0; | | 413 | do_expand = 0; |
414 | while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY)) | | 414 | while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY)) |
415 | /* Exception case */ | | 415 | /* Exception case */ |
416 | if (bp[2] == FULL_KEY_DATA && bp[0] == 2) | | 416 | if (bp[2] == FULL_KEY_DATA && bp[0] == 2) |
417 | /* This is the last page of a big key/data pair | | 417 | /* This is the last page of a big key/data pair |
418 | and we need to add another page */ | | 418 | and we need to add another page */ |
419 | break; | | 419 | break; |
420 | else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { | | 420 | else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { |
421 | bufp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, | | 421 | bufp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, |
422 | 0); | | 422 | 0); |
423 | if (!bufp) | | 423 | if (!bufp) |
424 | return (-1); | | 424 | return (-1); |
425 | bp = (uint16_t *)(void *)bufp->page; | | 425 | bp = (uint16_t *)(void *)bufp->page; |
426 | } else if (bp[bp[0]] != OVFLPAGE) { | | 426 | } else if (bp[bp[0]] != OVFLPAGE) { |
427 | /* Short key/data pairs, no more pages */ | | 427 | /* Short key/data pairs, no more pages */ |
428 | break; | | 428 | break; |
429 | } else { | | 429 | } else { |
430 | /* Try to squeeze key on this page */ | | 430 | /* Try to squeeze key on this page */ |
431 | if (bp[2] >= REAL_KEY && | | 431 | if (bp[2] >= REAL_KEY && |
432 | FREESPACE(bp) >= PAIRSIZE(key, val)) { | | 432 | FREESPACE(bp) >= PAIRSIZE(key, val)) { |
433 | squeeze_key(bp, key, val); | | 433 | squeeze_key(bp, key, val); |
434 | goto stats; | | 434 | goto stats; |
435 | } else { | | 435 | } else { |
436 | bufp = __get_buf(hashp, | | 436 | bufp = __get_buf(hashp, |
437 | (uint32_t)bp[bp[0] - 1], bufp, 0); | | 437 | (uint32_t)bp[bp[0] - 1], bufp, 0); |
438 | if (!bufp) | | 438 | if (!bufp) |
439 | return (-1); | | 439 | return (-1); |
440 | bp = (uint16_t *)(void *)bufp->page; | | 440 | bp = (uint16_t *)(void *)bufp->page; |
441 | } | | 441 | } |
442 | } | | 442 | } |
443 | | | 443 | |
444 | if (PAIRFITS(bp, key, val)) | | 444 | if (PAIRFITS(bp, key, val)) |
445 | putpair(bufp->page, key, val); | | 445 | putpair(bufp->page, key, val); |
446 | else { | | 446 | else { |
447 | do_expand = 1; | | 447 | do_expand = 1; |
448 | bufp = __add_ovflpage(hashp, bufp); | | 448 | bufp = __add_ovflpage(hashp, bufp); |
449 | if (!bufp) | | 449 | if (!bufp) |
450 | return (-1); | | 450 | return (-1); |
451 | sop = (uint16_t *)(void *)bufp->page; | | 451 | sop = (uint16_t *)(void *)bufp->page; |
452 | | | 452 | |
453 | if (PAIRFITS(sop, key, val)) | | 453 | if (PAIRFITS(sop, key, val)) |
454 | putpair((char *)(void *)sop, key, val); | | 454 | putpair((char *)(void *)sop, key, val); |
455 | else | | 455 | else |
456 | if (__big_insert(hashp, bufp, key, val)) | | 456 | if (__big_insert(hashp, bufp, key, val)) |
457 | return (-1); | | 457 | return (-1); |
458 | } | | 458 | } |
459 | stats: | | 459 | stats: |
460 | bufp->flags |= BUF_MOD; | | 460 | bufp->flags |= BUF_MOD; |
461 | /* | | 461 | /* |
462 | * If the average number of keys per bucket exceeds the fill factor, | | 462 | * If the average number of keys per bucket exceeds the fill factor, |
463 | * expand the table. | | 463 | * expand the table. |
464 | */ | | 464 | */ |
465 | hashp->NKEYS++; | | 465 | hashp->NKEYS++; |
466 | if (do_expand || | | 466 | if (do_expand || |
467 | (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) | | 467 | (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) |
468 | return (__expand_table(hashp)); | | 468 | return (__expand_table(hashp)); |
469 | return (0); | | 469 | return (0); |
470 | } | | 470 | } |
471 | | | 471 | |
472 | /* | | 472 | /* |
473 | * | | 473 | * |
474 | * Returns: | | 474 | * Returns: |
475 | * pointer on success | | 475 | * pointer on success |
476 | * NULL on error | | 476 | * NULL on error |
477 | */ | | 477 | */ |
478 | BUFHEAD * | | 478 | BUFHEAD * |
479 | __add_ovflpage(HTAB *hashp, BUFHEAD *bufp) | | 479 | __add_ovflpage(HTAB *hashp, BUFHEAD *bufp) |
480 | { | | 480 | { |
481 | uint16_t *sp; | | 481 | uint16_t *sp; |
482 | uint16_t ndx, ovfl_num; | | 482 | uint16_t ndx, ovfl_num; |
483 | size_t temp; | | 483 | size_t temp; |
484 | #ifdef DEBUG1 | | 484 | #ifdef DEBUG1 |
485 | int tmp1, tmp2; | | 485 | int tmp1, tmp2; |
486 | #endif | | 486 | #endif |
487 | sp = (uint16_t *)(void *)bufp->page; | | 487 | sp = (uint16_t *)(void *)bufp->page; |
488 | | | 488 | |
489 | /* Check if we are dynamically determining the fill factor */ | | 489 | /* Check if we are dynamically determining the fill factor */ |
490 | if (hashp->FFACTOR == DEF_FFACTOR) { | | 490 | if (hashp->FFACTOR == DEF_FFACTOR) { |
491 | hashp->FFACTOR = (uint32_t)sp[0] >> 1; | | 491 | hashp->FFACTOR = (uint32_t)sp[0] >> 1; |
492 | if (hashp->FFACTOR < MIN_FFACTOR) | | 492 | if (hashp->FFACTOR < MIN_FFACTOR) |
493 | hashp->FFACTOR = MIN_FFACTOR; | | 493 | hashp->FFACTOR = MIN_FFACTOR; |
494 | } | | 494 | } |
495 | bufp->flags |= BUF_MOD; | | 495 | bufp->flags |= BUF_MOD; |
496 | ovfl_num = overflow_page(hashp); | | 496 | ovfl_num = overflow_page(hashp); |
497 | #ifdef DEBUG1 | | 497 | #ifdef DEBUG1 |
498 | tmp1 = bufp->addr; | | 498 | tmp1 = bufp->addr; |
499 | tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; | | 499 | tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; |
500 | #endif | | 500 | #endif |
501 | if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, (uint32_t)ovfl_num, | | 501 | if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, (uint32_t)ovfl_num, |
502 | bufp, 1))) | | 502 | bufp, 1))) |
503 | return (NULL); | | 503 | return (NULL); |
504 | bufp->ovfl->flags |= BUF_MOD; | | 504 | bufp->ovfl->flags |= BUF_MOD; |
505 | #ifdef DEBUG1 | | 505 | #ifdef DEBUG1 |
506 | (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", | | 506 | (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", |
507 | tmp1, tmp2, bufp->ovfl->addr); | | 507 | tmp1, tmp2, bufp->ovfl->addr); |
508 | #endif | | 508 | #endif |
509 | ndx = sp[0]; | | 509 | ndx = sp[0]; |
510 | /* | | 510 | /* |
511 | * Since a pair is allocated on a page only if there's room to add | | 511 | * Since a pair is allocated on a page only if there's room to add |
512 | * an overflow page, we know that the OVFL information will fit on | | 512 | * an overflow page, we know that the OVFL information will fit on |
513 | * the page. | | 513 | * the page. |
514 | */ | | 514 | */ |
515 | sp[ndx + 4] = OFFSET(sp); | | 515 | sp[ndx + 4] = OFFSET(sp); |
516 | temp = FREESPACE(sp); | | 516 | temp = FREESPACE(sp); |
517 | _DIAGASSERT(temp >= OVFLSIZE); | | 517 | _DIAGASSERT(temp >= OVFLSIZE); |
518 | sp[ndx + 3] = (uint16_t)(temp - OVFLSIZE); | | 518 | sp[ndx + 3] = (uint16_t)(temp - OVFLSIZE); |
519 | sp[ndx + 1] = ovfl_num; | | 519 | sp[ndx + 1] = ovfl_num; |
520 | sp[ndx + 2] = OVFLPAGE; | | 520 | sp[ndx + 2] = OVFLPAGE; |
521 | sp[0] = ndx + 2; | | 521 | sp[0] = ndx + 2; |
522 | #ifdef HASH_STATISTICS | | 522 | #ifdef HASH_STATISTICS |
523 | hash_overflows++; | | 523 | hash_overflows++; |
524 | #endif | | 524 | #endif |
525 | return (bufp->ovfl); | | 525 | return (bufp->ovfl); |
526 | } | | 526 | } |
527 | | | 527 | |
528 | /* | | 528 | /* |
529 | * Returns: | | 529 | * Returns: |
530 | * 0 indicates SUCCESS | | 530 | * 0 indicates SUCCESS |
531 | * -1 indicates FAILURE | | 531 | * -1 indicates FAILURE |
532 | */ | | 532 | */ |
533 | int | | 533 | int |
534 | __get_page(HTAB *hashp, char *p, uint32_t bucket, int is_bucket, int is_disk, | | 534 | __get_page(HTAB *hashp, char *p, uint32_t bucket, int is_bucket, int is_disk, |
535 | int is_bitmap) | | 535 | int is_bitmap) |
536 | { | | 536 | { |
537 | int fd, page, size; | | 537 | int fd, page, size; |
538 | ssize_t rsize; | | 538 | ssize_t rsize; |
539 | uint16_t *bp; | | 539 | uint16_t *bp; |
540 | size_t temp; | | 540 | size_t temp; |
541 | | | 541 | |
542 | fd = hashp->fp; | | 542 | fd = hashp->fp; |
543 | size = hashp->BSIZE; | | 543 | size = hashp->BSIZE; |
544 | | | 544 | |
545 | if ((fd == -1) || !is_disk) { | | 545 | if ((fd == -1) || !is_disk) { |
546 | PAGE_INIT(p); | | 546 | PAGE_INIT(p); |
547 | return (0); | | 547 | return (0); |
548 | } | | 548 | } |
549 | if (is_bucket) | | 549 | if (is_bucket) |
550 | page = BUCKET_TO_PAGE(bucket); | | 550 | page = BUCKET_TO_PAGE(bucket); |
551 | else | | 551 | else |
552 | page = OADDR_TO_PAGE(bucket); | | 552 | page = OADDR_TO_PAGE(bucket); |
553 | if ((rsize = pread(fd, p, (size_t)size, (off_t)page << hashp->BSHIFT)) == -1) | | 553 | if ((rsize = pread(fd, p, (size_t)size, (off_t)page << hashp->BSHIFT)) == -1) |
554 | return (-1); | | 554 | return (-1); |
555 | bp = (uint16_t *)(void *)p; | | 555 | bp = (uint16_t *)(void *)p; |
556 | if (!rsize) | | 556 | if (!rsize) |
557 | bp[0] = 0; /* We hit the EOF, so initialize a new page */ | | 557 | bp[0] = 0; /* We hit the EOF, so initialize a new page */ |
558 | else | | 558 | else |
559 | if (rsize != size) { | | 559 | if (rsize != size) { |
560 | errno = EFTYPE; | | 560 | errno = EFTYPE; |
561 | return (-1); | | 561 | return (-1); |
562 | } | | 562 | } |
563 | if (!is_bitmap && !bp[0]) { | | 563 | if (!is_bitmap && !bp[0]) { |
564 | PAGE_INIT(p); | | 564 | PAGE_INIT(p); |
565 | } else | | 565 | } else |
566 | if (hashp->LORDER != BYTE_ORDER) { | | 566 | if (hashp->LORDER != BYTE_ORDER) { |
567 | int i, max; | | 567 | int i, max; |
568 | | | 568 | |
569 | if (is_bitmap) { | | 569 | if (is_bitmap) { |
570 | max = (uint32_t)hashp->BSIZE >> 2; /* divide by 4 */ | | 570 | max = (uint32_t)hashp->BSIZE >> 2; /* divide by 4 */ |
571 | for (i = 0; i < max; i++) | | 571 | for (i = 0; i < max; i++) |
572 | M_32_SWAP(((int *)(void *)p)[i]); | | 572 | M_32_SWAP(((int *)(void *)p)[i]); |
573 | } else { | | 573 | } else { |
574 | M_16_SWAP(bp[0]); | | 574 | M_16_SWAP(bp[0]); |
575 | max = bp[0] + 2; | | 575 | max = bp[0] + 2; |
576 | for (i = 1; i <= max; i++) | | 576 | for (i = 1; i <= max; i++) |
577 | M_16_SWAP(bp[i]); | | 577 | M_16_SWAP(bp[i]); |
578 | } | | 578 | } |
579 | } | | 579 | } |
580 | return (0); | | 580 | return (0); |
581 | } | | 581 | } |
582 | | | 582 | |
583 | /* | | 583 | /* |
584 | * Write page p to disk | | 584 | * Write page p to disk |
585 | * | | 585 | * |
586 | * Returns: | | 586 | * Returns: |
587 | * 0 ==> OK | | 587 | * 0 ==> OK |
588 | * -1 ==>failure | | 588 | * -1 ==>failure |
589 | */ | | 589 | */ |
590 | int | | 590 | int |
591 | __put_page(HTAB *hashp, char *p, uint32_t bucket, int is_bucket, int is_bitmap) | | 591 | __put_page(HTAB *hashp, char *p, uint32_t bucket, int is_bucket, int is_bitmap) |
592 | { | | 592 | { |
593 | int fd, page, size; | | 593 | int fd, page, size; |
594 | ssize_t wsize; | | 594 | ssize_t wsize; |
595 | | | 595 | |
596 | size = hashp->BSIZE; | | 596 | size = hashp->BSIZE; |
597 | if ((hashp->fp == -1) && open_temp(hashp)) | | 597 | if ((hashp->fp == -1) && open_temp(hashp)) |
598 | return (-1); | | 598 | return (-1); |
599 | fd = hashp->fp; | | 599 | fd = hashp->fp; |
600 | | | 600 | |
601 | if (hashp->LORDER != BYTE_ORDER) { | | 601 | if (hashp->LORDER != BYTE_ORDER) { |
602 | int i; | | 602 | int i; |
603 | int max; | | 603 | int max; |
604 | | | 604 | |
605 | if (is_bitmap) { | | 605 | if (is_bitmap) { |
606 | max = (uint32_t)hashp->BSIZE >> 2; /* divide by 4 */ | | 606 | max = (uint32_t)hashp->BSIZE >> 2; /* divide by 4 */ |
607 | for (i = 0; i < max; i++) | | 607 | for (i = 0; i < max; i++) |
608 | M_32_SWAP(((int *)(void *)p)[i]); | | 608 | M_32_SWAP(((int *)(void *)p)[i]); |
609 | } else { | | 609 | } else { |
610 | max = ((uint16_t *)(void *)p)[0] + 2; | | 610 | max = ((uint16_t *)(void *)p)[0] + 2; |
611 | for (i = 0; i <= max; i++) | | 611 | for (i = 0; i <= max; i++) |
612 | M_16_SWAP(((uint16_t *)(void *)p)[i]); | | 612 | M_16_SWAP(((uint16_t *)(void *)p)[i]); |
613 | } | | 613 | } |
614 | } | | 614 | } |
615 | if (is_bucket) | | 615 | if (is_bucket) |
616 | page = BUCKET_TO_PAGE(bucket); | | 616 | page = BUCKET_TO_PAGE(bucket); |
617 | else | | 617 | else |
618 | page = OADDR_TO_PAGE(bucket); | | 618 | page = OADDR_TO_PAGE(bucket); |
619 | if ((wsize = pwrite(fd, p, (size_t)size, (off_t)page << hashp->BSHIFT)) == -1) | | 619 | if ((wsize = pwrite(fd, p, (size_t)size, (off_t)page << hashp->BSHIFT)) == -1) |
620 | /* Errno is set */ | | 620 | /* Errno is set */ |
621 | return (-1); | | 621 | return (-1); |
622 | if (wsize != size) { | | 622 | if (wsize != size) { |
623 | errno = EFTYPE; | | 623 | errno = EFTYPE; |
624 | return (-1); | | 624 | return (-1); |
625 | } | | 625 | } |
626 | return (0); | | 626 | return (0); |
627 | } | | 627 | } |
628 | | | 628 | |
629 | #define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) | | 629 | #define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) |
630 | /* | | 630 | /* |
631 | * Initialize a new bitmap page. Bitmap pages are left in memory | | 631 | * Initialize a new bitmap page. Bitmap pages are left in memory |
632 | * once they are read in. | | 632 | * once they are read in. |
633 | */ | | 633 | */ |
634 | int | | 634 | int |
635 | __ibitmap(HTAB *hashp, int pnum, int nbits, int ndx) | | 635 | __ibitmap(HTAB *hashp, int pnum, int nbits, int ndx) |
636 | { | | 636 | { |
637 | uint32_t *ip; | | 637 | uint32_t *ip; |
638 | int clearbytes, clearints; | | 638 | int clearbytes, clearints; |
639 | | | 639 | |
640 | if ((ip = malloc((size_t)hashp->BSIZE)) == NULL) | | 640 | if ((ip = malloc((size_t)hashp->BSIZE)) == NULL) |
641 | return (1); | | 641 | return (1); |
642 | hashp->nmaps++; | | 642 | hashp->nmaps++; |
643 | clearints = ((uint32_t)(nbits - 1) >> INT_BYTE_SHIFT) + 1; | | 643 | clearints = ((uint32_t)(nbits - 1) >> INT_BYTE_SHIFT) + 1; |
644 | clearbytes = clearints << INT_TO_BYTE; | | 644 | clearbytes = clearints << INT_TO_BYTE; |
645 | (void)memset(ip, 0, (size_t)clearbytes); | | 645 | (void)memset(ip, 0, (size_t)clearbytes); |
646 | (void)memset(((char *)(void *)ip) + clearbytes, 0xFF, | | 646 | (void)memset(((char *)(void *)ip) + clearbytes, 0xFF, |
647 | (size_t)(hashp->BSIZE - clearbytes)); | | 647 | (size_t)(hashp->BSIZE - clearbytes)); |
648 | ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); | | 648 | ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); |
649 | SETBIT(ip, 0); | | 649 | SETBIT(ip, 0); |
650 | hashp->BITMAPS[ndx] = (uint16_t)pnum; | | 650 | hashp->BITMAPS[ndx] = (uint16_t)pnum; |
651 | hashp->mapp[ndx] = ip; | | 651 | hashp->mapp[ndx] = ip; |
652 | return (0); | | 652 | return (0); |
653 | } | | 653 | } |
654 | | | 654 | |
655 | static uint32_t | | 655 | static uint32_t |
656 | first_free(uint32_t map) | | 656 | first_free(uint32_t map) |
657 | { | | 657 | { |
658 | uint32_t i, mask; | | 658 | uint32_t i, mask; |
659 | | | 659 | |
660 | mask = 0x1; | | 660 | mask = 0x1; |
661 | for (i = 0; i < BITS_PER_MAP; i++) { | | 661 | for (i = 0; i < BITS_PER_MAP; i++) { |
662 | if (!(mask & map)) | | 662 | if (!(mask & map)) |
663 | return (i); | | 663 | return (i); |
664 | mask = mask << 1; | | 664 | mask = mask << 1; |
665 | } | | 665 | } |
666 | return (i); | | 666 | return (i); |
667 | } | | 667 | } |
668 | | | 668 | |
669 | static uint16_t | | 669 | static uint16_t |
670 | overflow_page(HTAB *hashp) | | 670 | overflow_page(HTAB *hashp) |
671 | { | | 671 | { |
672 | uint32_t *freep = NULL; | | 672 | uint32_t *freep = NULL; |
673 | int max_free, offset, splitnum; | | 673 | int max_free, offset, splitnum; |
674 | uint16_t addr; | | 674 | uint16_t addr; |
675 | int bit, first_page, free_bit, free_page, i, in_use_bits, j; | | 675 | int bit, first_page, free_bit, free_page, i, in_use_bits, j; |
676 | #ifdef DEBUG2 | | 676 | #ifdef DEBUG2 |
677 | int tmp1, tmp2; | | 677 | int tmp1, tmp2; |
678 | #endif | | 678 | #endif |
679 | splitnum = hashp->OVFL_POINT; | | 679 | splitnum = hashp->OVFL_POINT; |
680 | max_free = hashp->SPARES[splitnum]; | | 680 | max_free = hashp->SPARES[splitnum]; |
681 | | | 681 | |
682 | free_page = (uint32_t)(max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); | | 682 | free_page = (uint32_t)(max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); |
683 | free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); | | 683 | free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); |
684 | | | 684 | |
685 | /* Look through all the free maps to find the first free block */ | | 685 | /* Look through all the free maps to find the first free block */ |
686 | first_page = (uint32_t)hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); | | 686 | first_page = (uint32_t)hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); |
687 | for ( i = first_page; i <= free_page; i++ ) { | | 687 | for ( i = first_page; i <= free_page; i++ ) { |
688 | if (!(freep = (uint32_t *)hashp->mapp[i]) && | | 688 | if (!(freep = (uint32_t *)hashp->mapp[i]) && |
689 | !(freep = fetch_bitmap(hashp, i))) | | 689 | !(freep = fetch_bitmap(hashp, i))) |
690 | return (0); | | 690 | return (0); |
691 | if (i == free_page) | | 691 | if (i == free_page) |
692 | in_use_bits = free_bit; | | 692 | in_use_bits = free_bit; |
693 | else | | 693 | else |
694 | in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; | | 694 | in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; |
695 | | | 695 | |
696 | if (i == first_page) { | | 696 | if (i == first_page) { |
697 | bit = hashp->LAST_FREED & | | 697 | bit = hashp->LAST_FREED & |
698 | ((hashp->BSIZE << BYTE_SHIFT) - 1); | | 698 | ((hashp->BSIZE << BYTE_SHIFT) - 1); |
699 | j = bit / BITS_PER_MAP; | | 699 | j = bit / BITS_PER_MAP; |
700 | bit = bit & ~(BITS_PER_MAP - 1); | | 700 | bit = bit & ~(BITS_PER_MAP - 1); |
701 | } else { | | 701 | } else { |
702 | bit = 0; | | 702 | bit = 0; |
703 | j = 0; | | 703 | j = 0; |
704 | } | | 704 | } |
705 | for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) | | 705 | for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) |
706 | if (freep[j] != ALL_SET) | | 706 | if (freep[j] != ALL_SET) |
707 | goto found; | | 707 | goto found; |
708 | } | | 708 | } |
709 | | | 709 | |
710 | /* No Free Page Found */ | | 710 | /* No Free Page Found */ |
711 | hashp->LAST_FREED = hashp->SPARES[splitnum]; | | 711 | hashp->LAST_FREED = hashp->SPARES[splitnum]; |
712 | hashp->SPARES[splitnum]++; | | 712 | hashp->SPARES[splitnum]++; |
713 | offset = hashp->SPARES[splitnum] - | | 713 | offset = hashp->SPARES[splitnum] - |
714 | (splitnum ? hashp->SPARES[splitnum - 1] : 0); | | 714 | (splitnum ? hashp->SPARES[splitnum - 1] : 0); |
715 | | | 715 | |
716 | #define OVMSG "HASH: Out of overflow pages. Increase page size\n" | | 716 | #define OVMSG "HASH: Out of overflow pages. Increase page size\n" |
717 | if (offset > SPLITMASK) { | | 717 | if (offset > SPLITMASK) { |
718 | if (++splitnum >= NCACHED) { | | 718 | if (++splitnum >= NCACHED) { |
719 | (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); | | 719 | (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); |
720 | errno = EFBIG; | | 720 | errno = EFBIG; |
721 | return (0); | | 721 | return (0); |
722 | } | | 722 | } |
723 | hashp->OVFL_POINT = splitnum; | | 723 | hashp->OVFL_POINT = splitnum; |
724 | hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; | | 724 | hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; |
725 | hashp->SPARES[splitnum-1]--; | | 725 | hashp->SPARES[splitnum-1]--; |
726 | offset = 1; | | 726 | offset = 1; |
727 | } | | 727 | } |
728 | | | 728 | |
729 | /* Check if we need to allocate a new bitmap page */ | | 729 | /* Check if we need to allocate a new bitmap page */ |
730 | if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { | | 730 | if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { |
731 | free_page++; | | 731 | free_page++; |
732 | if (free_page >= NCACHED) { | | 732 | if (free_page >= NCACHED) { |
733 | (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); | | 733 | (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); |
734 | errno = EFBIG; | | 734 | errno = EFBIG; |
735 | return (0); | | 735 | return (0); |
736 | } | | 736 | } |
737 | /* | | 737 | /* |
738 | * This is tricky. The 1 indicates that you want the new page | | 738 | * This is tricky. The 1 indicates that you want the new page |
739 | * allocated with 1 clear bit. Actually, you are going to | | 739 | * allocated with 1 clear bit. Actually, you are going to |
740 | * allocate 2 pages from this map. The first is going to be | | 740 | * allocate 2 pages from this map. The first is going to be |
741 | * the map page, the second is the overflow page we were | | 741 | * the map page, the second is the overflow page we were |
742 | * looking for. The init_bitmap routine automatically, sets | | 742 | * looking for. The init_bitmap routine automatically, sets |
743 | * the first bit of itself to indicate that the bitmap itself | | 743 | * the first bit of itself to indicate that the bitmap itself |
744 | * is in use. We would explicitly set the second bit, but | | 744 | * is in use. We would explicitly set the second bit, but |
745 | * don't have to if we tell init_bitmap not to leave it clear | | 745 | * don't have to if we tell init_bitmap not to leave it clear |
746 | * in the first place. | | 746 | * in the first place. |
747 | */ | | 747 | */ |
748 | if (__ibitmap(hashp, | | 748 | if (__ibitmap(hashp, |
749 | (int)OADDR_OF(splitnum, offset), 1, free_page)) | | 749 | (int)OADDR_OF(splitnum, offset), 1, free_page)) |
750 | return (0); | | 750 | return (0); |
751 | hashp->SPARES[splitnum]++; | | 751 | hashp->SPARES[splitnum]++; |
752 | #ifdef DEBUG2 | | 752 | #ifdef DEBUG2 |
753 | free_bit = 2; | | 753 | free_bit = 2; |
754 | #endif | | 754 | #endif |
755 | offset++; | | 755 | offset++; |
756 | if (offset > SPLITMASK) { | | 756 | if (offset > SPLITMASK) { |
757 | if (++splitnum >= NCACHED) { | | 757 | if (++splitnum >= NCACHED) { |
758 | (void)write(STDERR_FILENO, OVMSG, | | 758 | (void)write(STDERR_FILENO, OVMSG, |
759 | sizeof(OVMSG) - 1); | | 759 | sizeof(OVMSG) - 1); |
760 | errno = EFBIG; | | 760 | errno = EFBIG; |
761 | return (0); | | 761 | return (0); |
762 | } | | 762 | } |
763 | hashp->OVFL_POINT = splitnum; | | 763 | hashp->OVFL_POINT = splitnum; |
764 | hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; | | 764 | hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; |
765 | hashp->SPARES[splitnum-1]--; | | 765 | hashp->SPARES[splitnum-1]--; |
766 | offset = 0; | | 766 | offset = 0; |
767 | } | | 767 | } |
768 | } else { | | 768 | } else { |
769 | /* | | 769 | /* |
770 | * Free_bit addresses the last used bit. Bump it to address | | 770 | * Free_bit addresses the last used bit. Bump it to address |
771 | * the first available bit. | | 771 | * the first available bit. |
772 | */ | | 772 | */ |
773 | free_bit++; | | 773 | free_bit++; |
774 | SETBIT(freep, free_bit); | | 774 | SETBIT(freep, free_bit); |
775 | } | | 775 | } |
776 | | | 776 | |
777 | /* Calculate address of the new overflow page */ | | 777 | /* Calculate address of the new overflow page */ |
778 | addr = OADDR_OF(splitnum, offset); | | 778 | addr = OADDR_OF(splitnum, offset); |
779 | #ifdef DEBUG2 | | 779 | #ifdef DEBUG2 |
780 | (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", | | 780 | (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", |
781 | addr, free_bit, free_page); | | 781 | addr, free_bit, free_page); |
782 | #endif | | 782 | #endif |
783 | return (addr); | | 783 | return (addr); |
784 | | | 784 | |
785 | found: | | 785 | found: |
786 | bit = bit + first_free(freep[j]); | | 786 | bit = bit + first_free(freep[j]); |
787 | SETBIT(freep, bit); | | 787 | SETBIT(freep, bit); |
788 | #ifdef DEBUG2 | | 788 | #ifdef DEBUG2 |
789 | tmp1 = bit; | | 789 | tmp1 = bit; |
790 | tmp2 = i; | | 790 | tmp2 = i; |
791 | #endif | | 791 | #endif |
792 | /* | | 792 | /* |
793 | * Bits are addressed starting with 0, but overflow pages are addressed | | 793 | * Bits are addressed starting with 0, but overflow pages are addressed |
794 | * beginning at 1. Bit is a bit addressnumber, so we need to increment | | 794 | * beginning at 1. Bit is a bit addressnumber, so we need to increment |
795 | * it to convert it to a page number. | | 795 | * it to convert it to a page number. |
796 | */ | | 796 | */ |
797 | bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); | | 797 | bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); |
798 | if (bit >= hashp->LAST_FREED) | | 798 | if (bit >= hashp->LAST_FREED) |
799 | hashp->LAST_FREED = bit - 1; | | 799 | hashp->LAST_FREED = bit - 1; |
800 | | | 800 | |
801 | /* Calculate the split number for this page */ | | 801 | /* Calculate the split number for this page */ |
802 | for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); | | 802 | for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); |
803 | offset = (i ? bit - hashp->SPARES[i - 1] : bit); | | 803 | offset = (i ? bit - hashp->SPARES[i - 1] : bit); |
804 | if (offset >= SPLITMASK) { | | 804 | if (offset >= SPLITMASK) { |
805 | (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); | | 805 | (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); |
806 | errno = EFBIG; | | 806 | errno = EFBIG; |
807 | return (0); /* Out of overflow pages */ | | 807 | return (0); /* Out of overflow pages */ |
808 | } | | 808 | } |
809 | addr = OADDR_OF(i, offset); | | 809 | addr = OADDR_OF(i, offset); |
810 | #ifdef DEBUG2 | | 810 | #ifdef DEBUG2 |
811 | (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", | | 811 | (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", |
812 | addr, tmp1, tmp2); | | 812 | addr, tmp1, tmp2); |
813 | #endif | | 813 | #endif |
814 | | | 814 | |
815 | /* Allocate and return the overflow page */ | | 815 | /* Allocate and return the overflow page */ |
816 | return (addr); | | 816 | return (addr); |
817 | } | | 817 | } |
818 | | | 818 | |
819 | /* | | 819 | /* |
820 | * Mark this overflow page as free. | | 820 | * Mark this overflow page as free. |
821 | */ | | 821 | */ |
822 | void | | 822 | void |
823 | __free_ovflpage(HTAB *hashp, BUFHEAD *obufp) | | 823 | __free_ovflpage(HTAB *hashp, BUFHEAD *obufp) |
824 | { | | 824 | { |
825 | uint16_t addr; | | 825 | uint16_t addr; |
826 | uint32_t *freep; | | 826 | uint32_t *freep; |
827 | int bit_address, free_page, free_bit; | | 827 | int bit_address, free_page, free_bit; |
828 | uint16_t ndx; | | 828 | uint16_t ndx; |
829 | | | 829 | |
830 | addr = obufp->addr; | | 830 | addr = obufp->addr; |
831 | #ifdef DEBUG1 | | 831 | #ifdef DEBUG1 |
832 | (void)fprintf(stderr, "Freeing %d\n", addr); | | 832 | (void)fprintf(stderr, "Freeing %d\n", addr); |
833 | #endif | | 833 | #endif |
834 | ndx = (((uint32_t)addr) >> SPLITSHIFT); | | 834 | ndx = (((uint32_t)addr) >> SPLITSHIFT); |
835 | bit_address = | | 835 | bit_address = |
836 | (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; | | 836 | (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; |
837 | if (bit_address < hashp->LAST_FREED) | | 837 | if (bit_address < hashp->LAST_FREED) |
838 | hashp->LAST_FREED = bit_address; | | 838 | hashp->LAST_FREED = bit_address; |
839 | free_page = ((uint32_t)bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); | | 839 | free_page = ((uint32_t)bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); |
840 | free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); | | 840 | free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); |
841 | | | 841 | |
842 | if (!(freep = hashp->mapp[free_page])) | | 842 | if (!(freep = hashp->mapp[free_page])) |
843 | freep = fetch_bitmap(hashp, free_page); | | 843 | freep = fetch_bitmap(hashp, free_page); |
844 | /* | | 844 | /* |
845 | * This had better never happen. It means we tried to read a bitmap | | 845 | * This had better never happen. It means we tried to read a bitmap |
846 | * that has already had overflow pages allocated off it, and we | | 846 | * that has already had overflow pages allocated off it, and we |
847 | * failed to read it from the file. | | 847 | * failed to read it from the file. |
848 | */ | | 848 | */ |
849 | _DIAGASSERT(freep != NULL); | | 849 | _DIAGASSERT(freep != NULL); |
850 | CLRBIT(freep, free_bit); | | 850 | CLRBIT(freep, free_bit); |
851 | #ifdef DEBUG2 | | 851 | #ifdef DEBUG2 |
852 | (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", | | 852 | (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", |
853 | obufp->addr, free_bit, free_page); | | 853 | obufp->addr, free_bit, free_page); |
854 | #endif | | 854 | #endif |
855 | __reclaim_buf(hashp, obufp); | | 855 | __reclaim_buf(hashp, obufp); |
856 | } | | 856 | } |
857 | | | 857 | |
858 | /* | | 858 | /* |
859 | * Returns: | | 859 | * Returns: |
860 | * 0 success | | 860 | * 0 success |
861 | * -1 failure | | 861 | * -1 failure |
862 | */ | | 862 | */ |
863 | static int | | 863 | static int |
864 | open_temp(HTAB *hashp) | | 864 | open_temp(HTAB *hashp) |
865 | { | | 865 | { |
866 | sigset_t set, oset; | | 866 | sigset_t set, oset; |
867 | char *envtmp; | | 867 | char *envtmp; |
868 | char namestr[PATH_MAX]; | | 868 | char namestr[PATH_MAX]; |
869 | | | 869 | |
870 | if (issetugid()) | | 870 | if (issetugid()) |
871 | envtmp = NULL; | | 871 | envtmp = NULL; |
872 | else | | 872 | else |
873 | envtmp = getenv("TMPDIR"); | | 873 | envtmp = getenv("TMPDIR"); |
874 | | | 874 | |
875 | if (-1 == snprintf(namestr, sizeof(namestr), "%s/_hashXXXXXX", | | 875 | if (-1 == snprintf(namestr, sizeof(namestr), "%s/_hashXXXXXX", |
876 | envtmp ? envtmp : _PATH_TMP)) | | 876 | envtmp ? envtmp : _PATH_TMP)) |
877 | return -1; | | 877 | return -1; |
878 | | | 878 | |
879 | /* Block signals; make sure file goes away at process exit. */ | | 879 | /* Block signals; make sure file goes away at process exit. */ |
880 | (void)sigfillset(&set); | | 880 | (void)sigfillset(&set); |
881 | (void)sigprocmask(SIG_BLOCK, &set, &oset); | | 881 | (void)sigprocmask(SIG_BLOCK, &set, &oset); |
882 | if ((hashp->fp = mkstemp(namestr)) != -1) { | | 882 | if ((hashp->fp = mkstemp(namestr)) != -1) { |
883 | (void)unlink(namestr); | | 883 | (void)unlink(namestr); |
884 | (void)fcntl(hashp->fp, F_SETFD, FD_CLOEXEC); | | 884 | (void)fcntl(hashp->fp, F_SETFD, FD_CLOEXEC); |
885 | } | | 885 | } |
886 | (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); | | 886 | (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); |
887 | return (hashp->fp != -1 ? 0 : -1); | | 887 | return (hashp->fp != -1 ? 0 : -1); |
888 | } | | 888 | } |
889 | | | 889 | |
890 | /* | | 890 | /* |
891 | * We have to know that the key will fit, but the last entry on the page is | | 891 | * We have to know that the key will fit, but the last entry on the page is |
892 | * an overflow pair, so we need to shift things. | | 892 | * an overflow pair, so we need to shift things. |
893 | */ | | 893 | */ |
894 | static void | | 894 | static void |
895 | squeeze_key(uint16_t *sp, const DBT *key, const DBT *val) | | 895 | squeeze_key(uint16_t *sp, const DBT *key, const DBT *val) |
896 | { | | 896 | { |
897 | char *p; | | 897 | char *p; |
898 | uint16_t free_space, n, off, pageno; | | 898 | uint16_t free_space, n, off, pageno; |
899 | size_t temp; | | 899 | size_t temp; |
900 | | | 900 | |
901 | p = (char *)(void *)sp; | | 901 | p = (char *)(void *)sp; |
902 | n = sp[0]; | | 902 | n = sp[0]; |
903 | free_space = FREESPACE(sp); | | 903 | free_space = FREESPACE(sp); |
904 | off = OFFSET(sp); | | 904 | off = OFFSET(sp); |
905 | | | 905 | |
906 | pageno = sp[n - 1]; | | 906 | pageno = sp[n - 1]; |
907 | _DIAGASSERT(off >= key->size); | | 907 | _DIAGASSERT(off >= key->size); |
908 | off -= (uint16_t)key->size; | | 908 | off -= (uint16_t)key->size; |
909 | sp[n - 1] = off; | | 909 | sp[n - 1] = off; |
910 | memmove(p + off, key->data, key->size); | | 910 | memmove(p + off, key->data, key->size); |
911 | _DIAGASSERT(off >= val->size); | | 911 | _DIAGASSERT(off >= val->size); |
912 | off -= (uint16_t)val->size; | | 912 | off -= (uint16_t)val->size; |
913 | sp[n] = off; | | 913 | sp[n] = off; |
914 | memmove(p + off, val->data, val->size); | | 914 | memmove(p + off, val->data, val->size); |
915 | sp[0] = n + 2; | | 915 | sp[0] = n + 2; |
916 | sp[n + 1] = pageno; | | 916 | sp[n + 1] = pageno; |
917 | sp[n + 2] = OVFLPAGE; | | 917 | sp[n + 2] = OVFLPAGE; |
918 | temp = PAIRSIZE(key, val); | | 918 | temp = PAIRSIZE(key, val); |
919 | _DIAGASSERT(free_space >= temp); | | 919 | _DIAGASSERT(free_space >= temp); |
920 | FREESPACE(sp) = (uint16_t)(free_space - temp); | | 920 | FREESPACE(sp) = (uint16_t)(free_space - temp); |
921 | OFFSET(sp) = off; | | 921 | OFFSET(sp) = off; |
922 | } | | 922 | } |
923 | | | 923 | |
924 | static uint32_t * | | 924 | static uint32_t * |
925 | fetch_bitmap(HTAB *hashp, int ndx) | | 925 | fetch_bitmap(HTAB *hashp, int ndx) |
926 | { | | 926 | { |
927 | if (ndx >= hashp->nmaps) | | 927 | if (ndx >= hashp->nmaps) |
928 | return (NULL); | | 928 | return (NULL); |
929 | if ((hashp->mapp[ndx] = malloc((size_t)hashp->BSIZE)) == NULL) | | 929 | if ((hashp->mapp[ndx] = malloc((size_t)hashp->BSIZE)) == NULL) |
930 | return (NULL); | | 930 | return (NULL); |
931 | if (__get_page(hashp, | | 931 | if (__get_page(hashp, |
932 | (char *)(void *)hashp->mapp[ndx], (uint32_t)hashp->BITMAPS[ndx], 0, 1, 1)) { | | 932 | (char *)(void *)hashp->mapp[ndx], (uint32_t)hashp->BITMAPS[ndx], 0, 1, 1)) { |
933 | free(hashp->mapp[ndx]); | | 933 | free(hashp->mapp[ndx]); |
934 | return (NULL); | | 934 | return (NULL); |
935 | } | | 935 | } |
936 | return (hashp->mapp[ndx]); | | 936 | return (hashp->mapp[ndx]); |
937 | } | | 937 | } |
938 | | | 938 | |
939 | #ifdef DEBUG4 | | 939 | #ifdef DEBUG4 |
940 | void print_chain(HTAB *, uint32_t); | | 940 | void print_chain(HTAB *, uint32_t); |
941 | void | | 941 | void |
942 | print_chain(HTAB *hashp, uint32_t addr) | | 942 | print_chain(HTAB *hashp, uint32_t addr) |
943 | { | | 943 | { |
944 | BUFHEAD *bufp; | | 944 | BUFHEAD *bufp; |
945 | uint16_t *bp, oaddr; | | 945 | uint16_t *bp, oaddr; |
946 | | | 946 | |
947 | (void)fprintf(stderr, "%d ", addr); | | 947 | (void)fprintf(stderr, "%d ", addr); |
948 | bufp = __get_buf(hashp, addr, NULL, 0); | | 948 | bufp = __get_buf(hashp, addr, NULL, 0); |
949 | bp = (uint16_t *)bufp->page; | | 949 | bp = (uint16_t *)bufp->page; |
950 | while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || | | 950 | while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || |
951 | ((bp[0] > 2) && bp[2] < REAL_KEY))) { | | 951 | ((bp[0] > 2) && bp[2] < REAL_KEY))) { |
952 | oaddr = bp[bp[0] - 1]; | | 952 | oaddr = bp[bp[0] - 1]; |
953 | (void)fprintf(stderr, "%d ", (int)oaddr); | | 953 | (void)fprintf(stderr, "%d ", (int)oaddr); |
954 | bufp = __get_buf(hashp, (uint32_t)oaddr, bufp, 0); | | 954 | bufp = __get_buf(hashp, (uint32_t)oaddr, bufp, 0); |
955 | bp = (uint16_t *)bufp->page; | | 955 | bp = (uint16_t *)bufp->page; |
956 | } | | 956 | } |
957 | (void)fprintf(stderr, "\n"); | | 957 | (void)fprintf(stderr, "\n"); |
958 | } | | 958 | } |
959 | #endif | | 959 | #endif |