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