File: | s/lib/dbm/src/h_page.c |
Warning: | line 485, column 13 Value stored to 'n' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /*- |
2 | * Copyright (c) 1990, 1993, 1994 |
3 | * The Regents of the University of California. All rights reserved. |
4 | * |
5 | * This code is derived from software contributed to Berkeley by |
6 | * Margo Seltzer. |
7 | * |
8 | * Redistribution and use in source and binary forms, with or without |
9 | * modification, are permitted provided that the following conditions |
10 | * are met: |
11 | * 1. Redistributions of source code must retain the above copyright |
12 | * notice, this list of conditions and the following disclaimer. |
13 | * 2. Redistributions in binary form must reproduce the above copyright |
14 | * notice, this list of conditions and the following disclaimer in the |
15 | * documentation and/or other materials provided with the distribution. |
16 | * 3. ***REMOVED*** - see |
17 | * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change |
18 | * 4. 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 | #if defined(unix) |
36 | #define MY_LSEEKnew_lseek lseek |
37 | #else |
38 | #define MY_LSEEKnew_lseek new_lseek |
39 | extern long new_lseek(int fd, long pos, int start); |
40 | #endif |
41 | |
42 | #if defined(LIBC_SCCS) && !defined(lint) |
43 | static char sccsid[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94"; |
44 | #endif /* LIBC_SCCS and not lint */ |
45 | |
46 | /* |
47 | * PACKAGE: hashing |
48 | * |
49 | * DESCRIPTION: |
50 | * Page manipulation for hashing package. |
51 | * |
52 | * ROUTINES: |
53 | * |
54 | * External |
55 | * __get_page |
56 | * __add_ovflpage |
57 | * Internal |
58 | * overflow_page |
59 | * open_temp |
60 | */ |
61 | #ifndef macintosh |
62 | #include <sys/types.h> |
63 | #endif |
64 | |
65 | #if defined(macintosh) |
66 | #include <unistd.h> |
67 | #endif |
68 | |
69 | #include <errno(*__errno_location ()).h> |
70 | #include <fcntl.h> |
71 | #if defined(_WIN32) || defined(_WINDOWS) |
72 | #include <io.h> |
73 | #endif |
74 | #include <signal.h> |
75 | #include <stdio.h> |
76 | #include <stdlib.h> |
77 | #include <string.h> |
78 | |
79 | #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) |
80 | #include <unistd.h> |
81 | #endif |
82 | |
83 | #include <assert.h> |
84 | |
85 | #include "mcom_db.h" |
86 | #include "hash.h" |
87 | #include "page.h" |
88 | /* #include "extern.h" */ |
89 | |
90 | extern int mkstempflags(char *path, int extraFlags); |
91 | |
92 | static uint32 *fetch_bitmap(HTAB *, uint32); |
93 | static uint32 first_free(uint32); |
94 | static int open_temp(HTAB *); |
95 | static uint16 overflow_page(HTAB *); |
96 | static void squeeze_key(uint16 *, const DBT *, const DBT *); |
97 | static int ugly_split(HTAB *, uint32, BUFHEAD *, BUFHEAD *, int, int); |
98 | |
99 | #define PAGE_INIT(P){ ((uint16 *)(P))[0] = 0; ((uint16 *)(P))[1] = hashp->hdr. bsize - 3 * sizeof(uint16); ((uint16 *)(P))[2] = hashp->hdr .bsize; } \ |
100 | { \ |
101 | ((uint16 *)(P))[0] = 0; \ |
102 | ((uint16 *)(P))[1] = hashp->BSIZEhdr.bsize - 3 * sizeof(uint16); \ |
103 | ((uint16 *)(P))[2] = hashp->BSIZEhdr.bsize; \ |
104 | } |
105 | |
106 | /* implement a new lseek using lseek that |
107 | * writes zero's when extending a file |
108 | * beyond the end. |
109 | */ |
110 | long |
111 | new_lseek(int fd, long offset, int origin) |
112 | { |
113 | long cur_pos = 0; |
114 | long end_pos = 0; |
115 | long seek_pos = 0; |
116 | |
117 | if (origin == SEEK_CUR1) { |
118 | if (offset < 1) |
119 | return (lseek(fd, offset, SEEK_CUR1)); |
120 | |
121 | cur_pos = lseek(fd, 0, SEEK_CUR1); |
122 | |
123 | if (cur_pos < 0) |
124 | return (cur_pos); |
125 | } |
126 | |
127 | end_pos = lseek(fd, 0, SEEK_END2); |
128 | if (end_pos < 0) |
129 | return (end_pos); |
130 | |
131 | if (origin == SEEK_SET0) |
132 | seek_pos = offset; |
133 | else if (origin == SEEK_CUR1) |
134 | seek_pos = cur_pos + offset; |
135 | else if (origin == SEEK_END2) |
136 | seek_pos = end_pos + offset; |
137 | else { |
138 | assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 138, __extension__ __PRETTY_FUNCTION__)); |
139 | return (-1); |
140 | } |
141 | |
142 | /* the seek position desired is before the |
143 | * end of the file. We don't need |
144 | * to do anything special except the seek. |
145 | */ |
146 | if (seek_pos <= end_pos) |
147 | return (lseek(fd, seek_pos, SEEK_SET0)); |
148 | |
149 | /* the seek position is beyond the end of the |
150 | * file. Write zero's to the end. |
151 | * |
152 | * we are already at the end of the file so |
153 | * we just need to "write()" zeros for the |
154 | * difference between seek_pos-end_pos and |
155 | * then seek to the position to finish |
156 | * the call |
157 | */ |
158 | { |
159 | char buffer[1024]; |
160 | long len = seek_pos - end_pos; |
161 | memset(buffer, 0, 1024); |
162 | while (len > 0) { |
163 | if (write(fd, buffer, (size_t)(1024 > len ? len : 1024)) < 0) |
164 | return (-1); |
165 | len -= 1024; |
166 | } |
167 | return (lseek(fd, seek_pos, SEEK_SET0)); |
168 | } |
169 | } |
170 | |
171 | /* |
172 | * This is called AFTER we have verified that there is room on the page for |
173 | * the pair (PAIRFITS has returned true) so we go right ahead and start moving |
174 | * stuff on. |
175 | */ |
176 | static void |
177 | putpair(char *p, const DBT *key, DBT *val) |
178 | { |
179 | register uint16 *bp, n, off; |
180 | |
181 | bp = (uint16 *)p; |
182 | |
183 | /* Enter the key first. */ |
184 | n = bp[0]; |
185 | |
186 | off = OFFSET(bp)((bp)[(bp)[0] + 2]) - key->size; |
187 | memmove(p + off, key->data, key->size); |
188 | bp[++n] = off; |
189 | |
190 | /* Now the data. */ |
191 | off -= val->size; |
192 | memmove(p + off, val->data, val->size); |
193 | bp[++n] = off; |
194 | |
195 | /* Adjust page info. */ |
196 | bp[0] = n; |
197 | bp[n + 1] = off - ((n + 3) * sizeof(uint16)); |
198 | bp[n + 2] = off; |
199 | } |
200 | |
201 | /* |
202 | * Returns: |
203 | * 0 OK |
204 | * -1 error |
205 | */ |
206 | extern int |
207 | dbm_delpair(HTAB *hashp, BUFHEAD *bufp, int ndx) |
208 | { |
209 | register uint16 *bp, newoff; |
210 | register int n; |
211 | uint16 pairlen; |
212 | |
213 | bp = (uint16 *)bufp->page; |
214 | n = bp[0]; |
215 | |
216 | if (bp[ndx + 1] < REAL_KEY4) |
217 | return (dbm_big_delete(hashp, bufp)); |
218 | if (ndx != 1) |
219 | newoff = bp[ndx - 1]; |
220 | else |
221 | newoff = hashp->BSIZEhdr.bsize; |
222 | pairlen = newoff - bp[ndx + 1]; |
223 | |
224 | if (ndx != (n - 1)) { |
225 | /* Hard Case -- need to shuffle keys */ |
226 | register int i; |
227 | register char *src = bufp->page + (int)OFFSET(bp)((bp)[(bp)[0] + 2]); |
228 | uint32 dst_offset = (uint32)OFFSET(bp)((bp)[(bp)[0] + 2]) + (uint32)pairlen; |
229 | register char *dst = bufp->page + dst_offset; |
230 | uint32 length = bp[ndx + 1] - OFFSET(bp)((bp)[(bp)[0] + 2]); |
231 | |
232 | /* |
233 | * +-----------+XXX+---------+XXX+---------+---------> +infinity |
234 | * | | | | |
235 | * 0 src_offset dst_offset BSIZE |
236 | * |
237 | * Dst_offset is > src_offset, so if src_offset were bad, dst_offset |
238 | * would be too, therefore we check only dst_offset. |
239 | * |
240 | * If dst_offset is >= BSIZE, either OFFSET(bp), or pairlen, or both |
241 | * is corrupted. |
242 | * |
243 | * Once we know dst_offset is < BSIZE, we can subtract it from BSIZE |
244 | * to get an upper bound on length. |
245 | */ |
246 | if (dst_offset > (uint32)hashp->BSIZEhdr.bsize) |
247 | return (DATABASE_CORRUPTED_ERROR-999); |
248 | |
249 | if (length > (uint32)(hashp->BSIZEhdr.bsize - dst_offset)) |
250 | return (DATABASE_CORRUPTED_ERROR-999); |
251 | |
252 | memmove(dst, src, length); |
253 | |
254 | /* Now adjust the pointers */ |
255 | for (i = ndx + 2; i <= n; i += 2) { |
256 | if (bp[i + 1] == OVFLPAGE0) { |
257 | bp[i - 2] = bp[i]; |
258 | bp[i - 1] = bp[i + 1]; |
259 | } else { |
260 | bp[i - 2] = bp[i] + pairlen; |
261 | bp[i - 1] = bp[i + 1] + pairlen; |
262 | } |
263 | } |
264 | } |
265 | /* Finally adjust the page data */ |
266 | bp[n] = OFFSET(bp)((bp)[(bp)[0] + 2]) + pairlen; |
267 | bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(uint16); |
268 | bp[0] = n - 2; |
269 | hashp->NKEYShdr.nkeys--; |
270 | |
271 | bufp->flags |= BUF_MOD0x0001; |
272 | return (0); |
273 | } |
274 | /* |
275 | * Returns: |
276 | * 0 ==> OK |
277 | * -1 ==> Error |
278 | */ |
279 | extern int |
280 | dbm_split_page(HTAB *hashp, uint32 obucket, uint32 nbucket) |
281 | { |
282 | register BUFHEAD *new_bufp, *old_bufp; |
283 | register uint16 *ino; |
284 | register uint16 *tmp_uint16_array; |
285 | register char *np; |
286 | DBT key, val; |
287 | uint16 n, ndx; |
288 | int retval; |
289 | uint16 copyto, diff, moved; |
290 | size_t off; |
291 | char *op; |
292 | |
293 | copyto = (uint16)hashp->BSIZEhdr.bsize; |
294 | off = (uint16)hashp->BSIZEhdr.bsize; |
295 | old_bufp = dbm_get_buf(hashp, obucket, NULL((void*)0), 0); |
296 | if (old_bufp == NULL((void*)0)) |
297 | return (-1); |
298 | new_bufp = dbm_get_buf(hashp, nbucket, NULL((void*)0), 0); |
299 | if (new_bufp == NULL((void*)0)) |
300 | return (-1); |
301 | |
302 | old_bufp->flags |= (BUF_MOD0x0001 | BUF_PIN0x0008); |
303 | new_bufp->flags |= (BUF_MOD0x0001 | BUF_PIN0x0008); |
304 | |
305 | ino = (uint16 *)(op = old_bufp->page); |
306 | np = new_bufp->page; |
307 | |
308 | moved = 0; |
309 | |
310 | for (n = 1, ndx = 1; n < ino[0]; n += 2) { |
311 | if (ino[n + 1] < REAL_KEY4) { |
312 | retval = ugly_split(hashp, obucket, old_bufp, new_bufp, |
313 | (int)copyto, (int)moved); |
314 | old_bufp->flags &= ~BUF_PIN0x0008; |
315 | new_bufp->flags &= ~BUF_PIN0x0008; |
316 | return (retval); |
317 | } |
318 | key.data = (uint8 *)op + ino[n]; |
319 | |
320 | /* check here for ino[n] being greater than |
321 | * off. If it is then the database has |
322 | * been corrupted. |
323 | */ |
324 | if (ino[n] > off) |
325 | return (DATABASE_CORRUPTED_ERROR-999); |
326 | |
327 | key.size = off - ino[n]; |
328 | |
329 | #ifdef DEBUG1 |
330 | /* make sure the size is positive */ |
331 | assert(((int)key.size) > -1)((((int)key.size) > -1) ? (void) (0) : __assert_fail ("((int)key.size) > -1" , "h_page.c", 331, __extension__ __PRETTY_FUNCTION__)); |
332 | #endif |
333 | |
334 | if (dbm_call_hash(hashp, (char *)key.data, key.size) == obucket) { |
335 | /* Don't switch page */ |
336 | diff = copyto - off; |
337 | if (diff) { |
338 | copyto = ino[n + 1] + diff; |
339 | memmove(op + copyto, op + ino[n + 1], |
340 | off - ino[n + 1]); |
341 | ino[ndx] = copyto + ino[n] - ino[n + 1]; |
342 | ino[ndx + 1] = copyto; |
343 | } else |
344 | copyto = ino[n + 1]; |
345 | ndx += 2; |
346 | } else { |
347 | /* Switch page */ |
348 | val.data = (uint8 *)op + ino[n + 1]; |
349 | val.size = ino[n] - ino[n + 1]; |
350 | |
351 | /* if the pair doesn't fit something is horribly |
352 | * wrong. LJM |
353 | */ |
354 | tmp_uint16_array = (uint16 *)np; |
355 | if (!PAIRFITS(tmp_uint16_array, &key, &val)(((tmp_uint16_array)[2] >= 4) && ((2 * sizeof(uint16 ) + ((&key))->size + ((&val))->size) + (2 * sizeof (uint16))) <= (((tmp_uint16_array))[((tmp_uint16_array))[0 ] + 1]))) |
356 | return (DATABASE_CORRUPTED_ERROR-999); |
357 | |
358 | putpair(np, &key, &val); |
359 | moved += 2; |
360 | } |
361 | |
362 | off = ino[n + 1]; |
363 | } |
364 | |
365 | /* Now clean up the page */ |
366 | ino[0] -= moved; |
367 | FREESPACE(ino)((ino)[(ino)[0] + 1]) = copyto - sizeof(uint16) * (ino[0] + 3); |
368 | OFFSET(ino)((ino)[(ino)[0] + 2]) = copyto; |
369 | |
370 | #ifdef DEBUG3 |
371 | (void)fprintf(stderrstderr, "split %d/%d\n", |
372 | ((uint16 *)np)[0] / 2, |
373 | ((uint16 *)op)[0] / 2); |
374 | #endif |
375 | /* unpin both pages */ |
376 | old_bufp->flags &= ~BUF_PIN0x0008; |
377 | new_bufp->flags &= ~BUF_PIN0x0008; |
378 | return (0); |
379 | } |
380 | |
381 | /* |
382 | * Called when we encounter an overflow or big key/data page during split |
383 | * handling. This is special cased since we have to begin checking whether |
384 | * the key/data pairs fit on their respective pages and because we may need |
385 | * overflow pages for both the old and new pages. |
386 | * |
387 | * The first page might be a page with regular key/data pairs in which case |
388 | * we have a regular overflow condition and just need to go on to the next |
389 | * page or it might be a big key/data pair in which case we need to fix the |
390 | * big key/data pair. |
391 | * |
392 | * Returns: |
393 | * 0 ==> success |
394 | * -1 ==> failure |
395 | */ |
396 | |
397 | /* the maximum number of loops we will allow UGLY split to chew |
398 | * on before we assume the database is corrupted and throw it |
399 | * away. |
400 | */ |
401 | #define MAX_UGLY_SPLIT_LOOPS10000 10000 |
402 | |
403 | static int |
404 | ugly_split(HTAB *hashp, uint32 obucket, BUFHEAD *old_bufp, |
405 | BUFHEAD *new_bufp, /* Same as __split_page. */ int copyto, int moved) |
406 | /* int copyto; First byte on page which contains key/data values. */ |
407 | /* int moved; Number of pairs moved to new page. */ |
408 | { |
409 | register BUFHEAD *bufp; /* Buffer header for ino */ |
410 | register uint16 *ino; /* Page keys come off of */ |
411 | register uint16 *np; /* New page */ |
412 | register uint16 *op; /* Page keys go on to if they aren't moving */ |
413 | uint32 loop_detection = 0; |
414 | |
415 | BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ |
416 | DBT key, val; |
417 | SPLIT_RETURN ret; |
418 | uint16 n, off, ov_addr, scopyto; |
419 | char *cino; /* Character value of ino */ |
420 | int status; |
421 | |
422 | bufp = old_bufp; |
423 | ino = (uint16 *)old_bufp->page; |
424 | np = (uint16 *)new_bufp->page; |
425 | op = (uint16 *)old_bufp->page; |
426 | last_bfp = NULL((void*)0); |
427 | scopyto = (uint16)copyto; /* ANSI */ |
428 | |
429 | if (ino[0] < 1) { |
430 | return DATABASE_CORRUPTED_ERROR-999; |
431 | } |
432 | n = ino[0] - 1; |
433 | while (n < ino[0]) { |
434 | |
435 | /* this function goes nuts sometimes and never returns. |
436 | * I havent found the problem yet but I need a solution |
437 | * so if we loop too often we assume a database curruption error |
438 | * :LJM |
439 | */ |
440 | loop_detection++; |
441 | |
442 | if (loop_detection > MAX_UGLY_SPLIT_LOOPS10000) |
443 | return DATABASE_CORRUPTED_ERROR-999; |
444 | |
445 | if (ino[2] < REAL_KEY4 && ino[2] != OVFLPAGE0) { |
446 | if ((status = dbm_big_split(hashp, old_bufp, |
447 | new_bufp, bufp, bufp->addr, obucket, &ret))) |
448 | return (status); |
449 | old_bufp = ret.oldp; |
450 | if (!old_bufp) |
451 | return (-1); |
452 | op = (uint16 *)old_bufp->page; |
453 | new_bufp = ret.newp; |
454 | if (!new_bufp) |
455 | return (-1); |
456 | np = (uint16 *)new_bufp->page; |
457 | bufp = ret.nextp; |
458 | if (!bufp) |
459 | return (0); |
460 | cino = (char *)bufp->page; |
461 | ino = (uint16 *)cino; |
462 | last_bfp = ret.nextp; |
463 | } else if (ino[n + 1] == OVFLPAGE0) { |
464 | ov_addr = ino[n]; |
465 | /* |
466 | * Fix up the old page -- the extra 2 are the fields |
467 | * which contained the overflow information. |
468 | */ |
469 | if (ino[0] < (moved + 2)) { |
470 | return DATABASE_CORRUPTED_ERROR-999; |
471 | } |
472 | ino[0] -= (moved + 2); |
473 | if (scopyto < sizeof(uint16) * (ino[0] + 3)) { |
474 | return DATABASE_CORRUPTED_ERROR-999; |
475 | } |
476 | FREESPACE(ino)((ino)[(ino)[0] + 1]) = |
477 | scopyto - sizeof(uint16) * (ino[0] + 3); |
478 | OFFSET(ino)((ino)[(ino)[0] + 2]) = scopyto; |
479 | |
480 | bufp = dbm_get_buf(hashp, ov_addr, bufp, 0); |
481 | if (!bufp) |
482 | return (-1); |
483 | |
484 | ino = (uint16 *)bufp->page; |
485 | n = 1; |
Value stored to 'n' is never read | |
486 | scopyto = hashp->BSIZEhdr.bsize; |
487 | moved = 0; |
488 | |
489 | if (last_bfp) |
490 | dbm_free_ovflpage(hashp, last_bfp); |
491 | last_bfp = bufp; |
492 | } |
493 | /* Move regular sized pairs of there are any */ |
494 | off = hashp->BSIZEhdr.bsize; |
495 | for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY4); n += 2) { |
496 | cino = (char *)ino; |
497 | key.data = (uint8 *)cino + ino[n]; |
498 | if (off < ino[n]) { |
499 | return DATABASE_CORRUPTED_ERROR-999; |
500 | } |
501 | key.size = off - ino[n]; |
502 | val.data = (uint8 *)cino + ino[n + 1]; |
503 | if (ino[n] < ino[n + 1]) { |
504 | return DATABASE_CORRUPTED_ERROR-999; |
505 | } |
506 | val.size = ino[n] - ino[n + 1]; |
507 | off = ino[n + 1]; |
508 | |
509 | if (dbm_call_hash(hashp, (char *)key.data, key.size) == obucket) { |
510 | /* Keep on old page */ |
511 | if (PAIRFITS(op, (&key), (&val))(((op)[2] >= 4) && ((2 * sizeof(uint16) + (((& key)))->size + (((&val)))->size) + (2 * sizeof(uint16 ))) <= (((op))[((op))[0] + 1]))) |
512 | putpair((char *)op, &key, &val); |
513 | else { |
514 | old_bufp = |
515 | dbm_add_ovflpage(hashp, old_bufp); |
516 | if (!old_bufp) |
517 | return (-1); |
518 | op = (uint16 *)old_bufp->page; |
519 | putpair((char *)op, &key, &val); |
520 | } |
521 | old_bufp->flags |= BUF_MOD0x0001; |
522 | } else { |
523 | /* Move to new page */ |
524 | if (PAIRFITS(np, (&key), (&val))(((np)[2] >= 4) && ((2 * sizeof(uint16) + (((& key)))->size + (((&val)))->size) + (2 * sizeof(uint16 ))) <= (((np))[((np))[0] + 1]))) |
525 | putpair((char *)np, &key, &val); |
526 | else { |
527 | new_bufp = |
528 | dbm_add_ovflpage(hashp, new_bufp); |
529 | if (!new_bufp) |
530 | return (-1); |
531 | np = (uint16 *)new_bufp->page; |
532 | putpair((char *)np, &key, &val); |
533 | } |
534 | new_bufp->flags |= BUF_MOD0x0001; |
535 | } |
536 | } |
537 | } |
538 | if (last_bfp) |
539 | dbm_free_ovflpage(hashp, last_bfp); |
540 | return (0); |
541 | } |
542 | |
543 | /* |
544 | * Add the given pair to the page |
545 | * |
546 | * Returns: |
547 | * 0 ==> OK |
548 | * 1 ==> failure |
549 | */ |
550 | extern int |
551 | dbm_addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) |
552 | { |
553 | register uint16 *bp, *sop; |
554 | int do_expand; |
555 | |
556 | bp = (uint16 *)bufp->page; |
557 | do_expand = 0; |
558 | while (bp[0] && (bp[2] < REAL_KEY4 || bp[bp[0]] < REAL_KEY4)) |
559 | /* Exception case */ |
560 | if (bp[2] == FULL_KEY_DATA3 && bp[0] == 2) |
561 | /* This is the last page of a big key/data pair |
562 | and we need to add another page */ |
563 | break; |
564 | else if (bp[2] < REAL_KEY4 && bp[bp[0]] != OVFLPAGE0) { |
565 | bufp = dbm_get_buf(hashp, bp[bp[0] - 1], bufp, 0); |
566 | if (!bufp) { |
567 | #ifdef DEBUG1 |
568 | assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 568, __extension__ __PRETTY_FUNCTION__)); |
569 | #endif |
570 | return (-1); |
571 | } |
572 | bp = (uint16 *)bufp->page; |
573 | } else |
574 | /* Try to squeeze key on this page */ |
575 | if (FREESPACE(bp)((bp)[(bp)[0] + 1]) > PAIRSIZE(key, val)(2 * sizeof(uint16) + (key)->size + (val)->size)) { |
576 | { |
577 | squeeze_key(bp, key, val); |
578 | |
579 | /* LJM: I added this because I think it was |
580 | * left out on accident. |
581 | * if this isn't incremented nkeys will not |
582 | * be the actual number of keys in the db. |
583 | */ |
584 | hashp->NKEYShdr.nkeys++; |
585 | return (0); |
586 | } |
587 | } else { |
588 | bufp = dbm_get_buf(hashp, bp[bp[0] - 1], bufp, 0); |
589 | if (!bufp) { |
590 | #ifdef DEBUG1 |
591 | assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 591, __extension__ __PRETTY_FUNCTION__)); |
592 | #endif |
593 | return (-1); |
594 | } |
595 | bp = (uint16 *)bufp->page; |
596 | } |
597 | |
598 | if (PAIRFITS(bp, key, val)(((bp)[2] >= 4) && ((2 * sizeof(uint16) + ((key))-> size + ((val))->size) + (2 * sizeof(uint16))) <= (((bp) )[((bp))[0] + 1]))) |
599 | putpair(bufp->page, key, (DBT *)val); |
600 | else { |
601 | do_expand = 1; |
602 | bufp = dbm_add_ovflpage(hashp, bufp); |
603 | if (!bufp) { |
604 | #ifdef DEBUG1 |
605 | assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 605, __extension__ __PRETTY_FUNCTION__)); |
606 | #endif |
607 | return (-1); |
608 | } |
609 | sop = (uint16 *)bufp->page; |
610 | |
611 | if (PAIRFITS(sop, key, val)(((sop)[2] >= 4) && ((2 * sizeof(uint16) + ((key)) ->size + ((val))->size) + (2 * sizeof(uint16))) <= ( ((sop))[((sop))[0] + 1]))) |
612 | putpair((char *)sop, key, (DBT *)val); |
613 | else if (dbm_big_insert(hashp, bufp, key, val)) { |
614 | #ifdef DEBUG1 |
615 | assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 615, __extension__ __PRETTY_FUNCTION__)); |
616 | #endif |
617 | return (-1); |
618 | } |
619 | } |
620 | bufp->flags |= BUF_MOD0x0001; |
621 | /* |
622 | * If the average number of keys per bucket exceeds the fill factor, |
623 | * expand the table. |
624 | */ |
625 | hashp->NKEYShdr.nkeys++; |
626 | if (do_expand || |
627 | (hashp->NKEYShdr.nkeys / (hashp->MAX_BUCKEThdr.max_bucket + 1) > hashp->FFACTORhdr.ffactor)) |
628 | return (dbm_expand_table(hashp)); |
629 | return (0); |
630 | } |
631 | |
632 | /* |
633 | * |
634 | * Returns: |
635 | * pointer on success |
636 | * NULL on error |
637 | */ |
638 | extern BUFHEAD * |
639 | dbm_add_ovflpage(HTAB *hashp, BUFHEAD *bufp) |
640 | { |
641 | register uint16 *sp; |
642 | uint16 ndx, ovfl_num; |
643 | #ifdef DEBUG1 |
644 | int tmp1, tmp2; |
645 | #endif |
646 | sp = (uint16 *)bufp->page; |
647 | |
648 | /* Check if we are dynamically determining the fill factor */ |
649 | if (hashp->FFACTORhdr.ffactor == DEF_FFACTOR65536l) { |
650 | hashp->FFACTORhdr.ffactor = sp[0] >> 1; |
651 | if (hashp->FFACTORhdr.ffactor < MIN_FFACTOR4) |
652 | hashp->FFACTORhdr.ffactor = MIN_FFACTOR4; |
653 | } |
654 | bufp->flags |= BUF_MOD0x0001; |
655 | ovfl_num = overflow_page(hashp); |
656 | #ifdef DEBUG1 |
657 | tmp1 = bufp->addr; |
658 | tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; |
659 | #endif |
660 | if (!ovfl_num || !(bufp->ovfl = dbm_get_buf(hashp, ovfl_num, bufp, 1))) |
661 | return (NULL((void*)0)); |
662 | bufp->ovfl->flags |= BUF_MOD0x0001; |
663 | #ifdef DEBUG1 |
664 | (void)fprintf(stderrstderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", |
665 | tmp1, tmp2, bufp->ovfl->addr); |
666 | #endif |
667 | ndx = sp[0]; |
668 | /* |
669 | * Since a pair is allocated on a page only if there's room to add |
670 | * an overflow page, we know that the OVFL information will fit on |
671 | * the page. |
672 | */ |
673 | sp[ndx + 4] = OFFSET(sp)((sp)[(sp)[0] + 2]); |
674 | sp[ndx + 3] = FREESPACE(sp)((sp)[(sp)[0] + 1]) - OVFLSIZE(2 * sizeof(uint16)); |
675 | sp[ndx + 1] = ovfl_num; |
676 | sp[ndx + 2] = OVFLPAGE0; |
677 | sp[0] = ndx + 2; |
678 | #ifdef HASH_STATISTICS |
679 | hash_overflows++; |
680 | #endif |
681 | return (bufp->ovfl); |
682 | } |
683 | |
684 | /* |
685 | * Returns: |
686 | * 0 indicates SUCCESS |
687 | * -1 indicates FAILURE |
688 | */ |
689 | extern int |
690 | dbm_get_page(HTAB *hashp, |
691 | char *p, |
692 | uint32 bucket, |
693 | int is_bucket, |
694 | int is_disk, |
695 | int is_bitmap) |
696 | { |
697 | register int fd, page; |
698 | size_t size; |
699 | int rsize; |
700 | uint16 *bp; |
701 | |
702 | fd = hashp->fp; |
703 | size = hashp->BSIZEhdr.bsize; |
704 | |
705 | if ((fd == -1) || !is_disk) { |
706 | PAGE_INIT(p){ ((uint16 *)(p))[0] = 0; ((uint16 *)(p))[1] = hashp->hdr. bsize - 3 * sizeof(uint16); ((uint16 *)(p))[2] = hashp->hdr .bsize; }; |
707 | return (0); |
708 | } |
709 | if (is_bucket) |
710 | page = BUCKET_TO_PAGE(bucket)(bucket) + hashp->hdr.hdrpages + ((bucket) ? hashp->hdr .spares[dbm_log2((uint32)((bucket) + 1)) - 1] : 0); |
711 | else |
712 | page = OADDR_TO_PAGE(bucket)((1 << (((uint32)((bucket))) >> 11)) - 1) + hashp ->hdr.hdrpages + (((1 << (((uint32)((bucket))) >> 11)) - 1) ? hashp->hdr.spares[dbm_log2((uint32)(((1 << (((uint32)((bucket))) >> 11)) - 1) + 1)) - 1] : 0) + ( ((bucket))&0x7FF);; |
713 | if ((MY_LSEEKnew_lseek(fd, (off_t)page << hashp->BSHIFThdr.bshift, SEEK_SET0) == -1) || |
714 | ((rsize = read(fd, p, size)) == -1)) |
715 | return (-1); |
716 | |
717 | bp = (uint16 *)p; |
718 | if (!rsize) |
719 | bp[0] = 0; /* We hit the EOF, so initialize a new page */ |
720 | else if ((unsigned)rsize != size) { |
721 | errno(*__errno_location ()) = EFTYPE22; |
722 | return (-1); |
723 | } |
724 | |
725 | if (!is_bitmap && !bp[0]) { |
726 | PAGE_INIT(p){ ((uint16 *)(p))[0] = 0; ((uint16 *)(p))[1] = hashp->hdr. bsize - 3 * sizeof(uint16); ((uint16 *)(p))[2] = hashp->hdr .bsize; }; |
727 | } else { |
728 | |
729 | if (hashp->LORDERhdr.lorder != BYTE_ORDER1234) { |
730 | register int i, max; |
731 | |
732 | if (is_bitmap) { |
733 | max = hashp->BSIZEhdr.bsize >> 2; /* divide by 4 */ |
734 | for (i = 0; i < max; i++) |
735 | M_32_SWAP(((int *)p)[i]){ uint32 _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]; }; |
736 | } else { |
737 | M_16_SWAP(bp[0]){ uint16 _tmp = bp[0]; ((char *)&bp[0])[0] = ((char *)& _tmp)[1]; ((char *)&bp[0])[1] = ((char *)&_tmp)[0]; }; |
738 | max = bp[0] + 2; |
739 | |
740 | /* bound the size of max by |
741 | * the maximum number of entries |
742 | * in the array |
743 | */ |
744 | if ((unsigned)max > (size / sizeof(uint16))) |
745 | return (DATABASE_CORRUPTED_ERROR-999); |
746 | |
747 | /* do the byte order swap |
748 | */ |
749 | for (i = 1; i <= max; i++) |
750 | M_16_SWAP(bp[i]){ uint16 _tmp = bp[i]; ((char *)&bp[i])[0] = ((char *)& _tmp)[1]; ((char *)&bp[i])[1] = ((char *)&_tmp)[0]; }; |
751 | } |
752 | } |
753 | |
754 | /* check the validity of the page here |
755 | * (after doing byte order swaping if necessary) |
756 | */ |
757 | if (!is_bitmap && bp[0] != 0) { |
758 | uint16 num_keys = bp[0]; |
759 | uint16 offset; |
760 | uint16 i; |
761 | |
762 | /* bp[0] is supposed to be the number of |
763 | * entries currently in the page. If |
764 | * bp[0] is too large (larger than the whole |
765 | * page) then the page is corrupted |
766 | */ |
767 | if (bp[0] > (size / sizeof(uint16))) |
768 | return (DATABASE_CORRUPTED_ERROR-999); |
769 | |
770 | /* bound free space */ |
771 | if (FREESPACE(bp)((bp)[(bp)[0] + 1]) > size) |
772 | return (DATABASE_CORRUPTED_ERROR-999); |
773 | |
774 | /* check each key and data offset to make |
775 | * sure they are all within bounds they |
776 | * should all be less than the previous |
777 | * offset as well. |
778 | */ |
779 | offset = size; |
780 | for (i = 1; i <= num_keys; i += 2) { |
781 | /* ignore overflow pages etc. */ |
782 | if (bp[i + 1] >= REAL_KEY4) { |
783 | |
784 | if (bp[i] > offset || bp[i + 1] > bp[i]) |
785 | return (DATABASE_CORRUPTED_ERROR-999); |
786 | |
787 | offset = bp[i + 1]; |
788 | } else { |
789 | /* there are no other valid keys after |
790 | * seeing a non REAL_KEY |
791 | */ |
792 | break; |
793 | } |
794 | } |
795 | } |
796 | } |
797 | return (0); |
798 | } |
799 | |
800 | /* |
801 | * Write page p to disk |
802 | * |
803 | * Returns: |
804 | * 0 ==> OK |
805 | * -1 ==>failure |
806 | */ |
807 | extern int |
808 | dbm_put_page(HTAB *hashp, char *p, uint32 bucket, int is_bucket, int is_bitmap) |
809 | { |
810 | register int fd, page; |
811 | size_t size; |
812 | int wsize; |
813 | off_t offset; |
814 | |
815 | size = hashp->BSIZEhdr.bsize; |
816 | if ((hashp->fp == -1) && open_temp(hashp)) |
817 | return (-1); |
818 | fd = hashp->fp; |
819 | |
820 | if (hashp->LORDERhdr.lorder != BYTE_ORDER1234) { |
821 | register int i; |
822 | register int max; |
823 | |
824 | if (is_bitmap) { |
825 | max = hashp->BSIZEhdr.bsize >> 2; /* divide by 4 */ |
826 | for (i = 0; i < max; i++) |
827 | M_32_SWAP(((int *)p)[i]){ uint32 _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]; }; |
828 | } else { |
829 | max = ((uint16 *)p)[0] + 2; |
830 | |
831 | /* bound the size of max by |
832 | * the maximum number of entries |
833 | * in the array |
834 | */ |
835 | if ((unsigned)max > (size / sizeof(uint16))) |
836 | return (DATABASE_CORRUPTED_ERROR-999); |
837 | |
838 | for (i = 0; i <= max; i++) |
839 | M_16_SWAP(((uint16 *)p)[i]){ uint16 _tmp = ((uint16 *)p)[i]; ((char *)&((uint16 *)p) [i])[0] = ((char *)&_tmp)[1]; ((char *)&((uint16 *)p) [i])[1] = ((char *)&_tmp)[0]; }; |
840 | } |
841 | } |
842 | |
843 | if (is_bucket) |
844 | page = BUCKET_TO_PAGE(bucket)(bucket) + hashp->hdr.hdrpages + ((bucket) ? hashp->hdr .spares[dbm_log2((uint32)((bucket) + 1)) - 1] : 0); |
845 | else |
846 | page = OADDR_TO_PAGE(bucket)((1 << (((uint32)((bucket))) >> 11)) - 1) + hashp ->hdr.hdrpages + (((1 << (((uint32)((bucket))) >> 11)) - 1) ? hashp->hdr.spares[dbm_log2((uint32)(((1 << (((uint32)((bucket))) >> 11)) - 1) + 1)) - 1] : 0) + ( ((bucket))&0x7FF);; |
847 | offset = (off_t)page << hashp->BSHIFThdr.bshift; |
848 | if ((MY_LSEEKnew_lseek(fd, offset, SEEK_SET0) == -1) || |
849 | ((wsize = write(fd, p, size)) == -1)) |
850 | /* Errno is set */ |
851 | return (-1); |
852 | if ((unsigned)wsize != size) { |
853 | errno(*__errno_location ()) = EFTYPE22; |
854 | return (-1); |
855 | } |
856 | #if defined(_WIN32) || defined(_WINDOWS) |
857 | if (offset + size > hashp->file_size) { |
858 | hashp->updateEOF = 1; |
859 | } |
860 | #endif |
861 | /* put the page back the way it was so that it isn't byteswapped |
862 | * if it remains in memory - LJM |
863 | */ |
864 | if (hashp->LORDERhdr.lorder != BYTE_ORDER1234) { |
865 | register int i; |
866 | register int max; |
867 | |
868 | if (is_bitmap) { |
869 | max = hashp->BSIZEhdr.bsize >> 2; /* divide by 4 */ |
870 | for (i = 0; i < max; i++) |
871 | M_32_SWAP(((int *)p)[i]){ uint32 _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]; }; |
872 | } else { |
873 | uint16 *bp = (uint16 *)p; |
874 | |
875 | M_16_SWAP(bp[0]){ uint16 _tmp = bp[0]; ((char *)&bp[0])[0] = ((char *)& _tmp)[1]; ((char *)&bp[0])[1] = ((char *)&_tmp)[0]; }; |
876 | max = bp[0] + 2; |
877 | |
878 | /* no need to bound the size if max again |
879 | * since it was done already above |
880 | */ |
881 | |
882 | /* do the byte order re-swap |
883 | */ |
884 | for (i = 1; i <= max; i++) |
885 | M_16_SWAP(bp[i]){ uint16 _tmp = bp[i]; ((char *)&bp[i])[0] = ((char *)& _tmp)[1]; ((char *)&bp[i])[1] = ((char *)&_tmp)[0]; }; |
886 | } |
887 | } |
888 | |
889 | return (0); |
890 | } |
891 | |
892 | #define BYTE_MASK((1 << 5) - 1) ((1 << INT_BYTE_SHIFT5) - 1) |
893 | /* |
894 | * Initialize a new bitmap page. Bitmap pages are left in memory |
895 | * once they are read in. |
896 | */ |
897 | extern int |
898 | dbm_ibitmap(HTAB *hashp, int pnum, int nbits, int ndx) |
899 | { |
900 | uint32 *ip; |
901 | size_t clearbytes, clearints; |
902 | |
903 | if ((ip = (uint32 *)malloc((size_t)hashp->BSIZEhdr.bsize)) == NULL((void*)0)) |
904 | return (1); |
905 | hashp->nmaps++; |
906 | clearints = ((nbits - 1) >> INT_BYTE_SHIFT5) + 1; |
907 | clearbytes = clearints << INT_TO_BYTE2; |
908 | (void)memset((char *)ip, 0, clearbytes); |
909 | (void)memset(((char *)ip) + clearbytes, 0xFF, |
910 | hashp->BSIZEhdr.bsize - clearbytes); |
911 | ip[clearints - 1] = ALL_SET((uint32)0xFFFFFFFF) << (nbits & BYTE_MASK((1 << 5) - 1)); |
912 | SETBIT(ip, 0)((ip)[(0) / 32] |= (1 << ((0) % 32))); |
913 | hashp->BITMAPShdr.bitmaps[ndx] = (uint16)pnum; |
914 | hashp->mapp[ndx] = ip; |
915 | return (0); |
916 | } |
917 | |
918 | static uint32 |
919 | first_free(uint32 map) |
920 | { |
921 | register uint32 i, mask; |
922 | |
923 | mask = 0x1; |
924 | for (i = 0; i < BITS_PER_MAP32; i++) { |
925 | if (!(mask & map)) |
926 | return (i); |
927 | mask = mask << 1; |
928 | } |
929 | return (i); |
930 | } |
931 | |
932 | static uint16 |
933 | overflow_page(HTAB *hashp) |
934 | { |
935 | register uint32 *freep = NULL((void*)0); |
936 | register int max_free, offset, splitnum; |
937 | uint16 addr; |
938 | uint32 i; |
939 | int bit, first_page, free_bit, free_page, in_use_bits, j; |
940 | #ifdef DEBUG2 |
941 | int tmp1, tmp2; |
942 | #endif |
943 | splitnum = hashp->OVFL_POINThdr.ovfl_point; |
944 | max_free = hashp->SPAREShdr.spares[splitnum]; |
945 | |
946 | free_page = (max_free - 1) >> (hashp->BSHIFThdr.bshift + BYTE_SHIFT3); |
947 | free_bit = (max_free - 1) & ((hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1); |
948 | |
949 | /* Look through all the free maps to find the first free block */ |
950 | first_page = hashp->LAST_FREEDhdr.last_freed >> (hashp->BSHIFThdr.bshift + BYTE_SHIFT3); |
951 | for (i = first_page; i <= (unsigned)free_page; i++) { |
952 | if (!(freep = (uint32 *)hashp->mapp[i]) && |
953 | !(freep = fetch_bitmap(hashp, i))) |
954 | return (0); |
955 | if (i == (unsigned)free_page) |
956 | in_use_bits = free_bit; |
957 | else |
958 | in_use_bits = (hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1; |
959 | |
960 | if (i == (unsigned)first_page) { |
961 | bit = hashp->LAST_FREEDhdr.last_freed & |
962 | ((hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1); |
963 | j = bit / BITS_PER_MAP32; |
964 | bit = bit & ~(BITS_PER_MAP32 - 1); |
965 | } else { |
966 | bit = 0; |
967 | j = 0; |
968 | } |
969 | for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP32) |
970 | if (freep[j] != ALL_SET((uint32)0xFFFFFFFF)) |
971 | goto found; |
972 | } |
973 | |
974 | /* No Free Page Found */ |
975 | hashp->LAST_FREEDhdr.last_freed = hashp->SPAREShdr.spares[splitnum]; |
976 | hashp->SPAREShdr.spares[splitnum]++; |
977 | offset = hashp->SPAREShdr.spares[splitnum] - |
978 | (splitnum ? hashp->SPAREShdr.spares[splitnum - 1] : 0); |
979 | |
980 | #define OVMSG"HASH: Out of overflow pages. Increase page size\n" "HASH: Out of overflow pages. Increase page size\n" |
981 | if (offset > SPLITMASK0x7FF) { |
982 | if (++splitnum >= NCACHED32) { |
983 | #ifndef macintosh |
984 | (void)fwrite(OVMSG"HASH: Out of overflow pages. Increase page size\n", 1, sizeof(OVMSG"HASH: Out of overflow pages. Increase page size\n") - 1, stderrstderr); |
985 | #endif |
986 | return (0); |
987 | } |
988 | hashp->OVFL_POINThdr.ovfl_point = splitnum; |
989 | hashp->SPAREShdr.spares[splitnum] = hashp->SPAREShdr.spares[splitnum - 1]; |
990 | hashp->SPAREShdr.spares[splitnum - 1]--; |
991 | offset = 1; |
992 | } |
993 | |
994 | /* Check if we need to allocate a new bitmap page */ |
995 | if (free_bit == (hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1) { |
996 | free_page++; |
997 | if (free_page >= NCACHED32) { |
998 | #ifndef macintosh |
999 | (void)fwrite(OVMSG"HASH: Out of overflow pages. Increase page size\n", 1, sizeof(OVMSG"HASH: Out of overflow pages. Increase page size\n") - 1, stderrstderr); |
1000 | #endif |
1001 | return (0); |
1002 | } |
1003 | /* |
1004 | * This is tricky. The 1 indicates that you want the new page |
1005 | * allocated with 1 clear bit. Actually, you are going to |
1006 | * allocate 2 pages from this map. The first is going to be |
1007 | * the map page, the second is the overflow page we were |
1008 | * looking for. The init_bitmap routine automatically, sets |
1009 | * the first bit of itself to indicate that the bitmap itself |
1010 | * is in use. We would explicitly set the second bit, but |
1011 | * don't have to if we tell init_bitmap not to leave it clear |
1012 | * in the first place. |
1013 | */ |
1014 | if (dbm_ibitmap(hashp, |
1015 | (int)OADDR_OF(splitnum, offset)((uint32)((uint32)(splitnum) << 11) + (offset)), 1, free_page)) |
1016 | return (0); |
1017 | hashp->SPAREShdr.spares[splitnum]++; |
1018 | #ifdef DEBUG2 |
1019 | free_bit = 2; |
1020 | #endif |
1021 | offset++; |
1022 | if (offset > SPLITMASK0x7FF) { |
1023 | if (++splitnum >= NCACHED32) { |
1024 | #ifndef macintosh |
1025 | (void)fwrite(OVMSG"HASH: Out of overflow pages. Increase page size\n", 1, sizeof(OVMSG"HASH: Out of overflow pages. Increase page size\n") - 1, stderrstderr); |
1026 | #endif |
1027 | return (0); |
1028 | } |
1029 | hashp->OVFL_POINThdr.ovfl_point = splitnum; |
1030 | hashp->SPAREShdr.spares[splitnum] = hashp->SPAREShdr.spares[splitnum - 1]; |
1031 | hashp->SPAREShdr.spares[splitnum - 1]--; |
1032 | offset = 0; |
1033 | } |
1034 | } else { |
1035 | /* |
1036 | * Free_bit addresses the last used bit. Bump it to address |
1037 | * the first available bit. |
1038 | */ |
1039 | free_bit++; |
1040 | SETBIT(freep, free_bit)((freep)[(free_bit) / 32] |= (1 << ((free_bit) % 32))); |
1041 | } |
1042 | |
1043 | /* Calculate address of the new overflow page */ |
1044 | addr = OADDR_OF(splitnum, offset)((uint32)((uint32)(splitnum) << 11) + (offset)); |
1045 | #ifdef DEBUG2 |
1046 | (void)fprintf(stderrstderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", |
1047 | addr, free_bit, free_page); |
1048 | #endif |
1049 | return (addr); |
1050 | |
1051 | found: |
1052 | bit = bit + first_free(freep[j]); |
1053 | SETBIT(freep, bit)((freep)[(bit) / 32] |= (1 << ((bit) % 32))); |
1054 | #ifdef DEBUG2 |
1055 | tmp1 = bit; |
1056 | tmp2 = i; |
1057 | #endif |
1058 | /* |
1059 | * Bits are addressed starting with 0, but overflow pages are addressed |
1060 | * beginning at 1. Bit is a bit addressnumber, so we need to increment |
1061 | * it to convert it to a page number. |
1062 | */ |
1063 | bit = 1 + bit + (i * (hashp->BSIZEhdr.bsize << BYTE_SHIFT3)); |
1064 | if (bit >= hashp->LAST_FREEDhdr.last_freed) |
1065 | hashp->LAST_FREEDhdr.last_freed = bit - 1; |
1066 | |
1067 | /* Calculate the split number for this page */ |
1068 | for (i = 0; (i < (unsigned)splitnum) && (bit > hashp->SPAREShdr.spares[i]); i++) { |
1069 | } |
1070 | offset = (i ? bit - hashp->SPAREShdr.spares[i - 1] : bit); |
1071 | if (offset >= SPLITMASK0x7FF) |
1072 | return (0); /* Out of overflow pages */ |
1073 | addr = OADDR_OF(i, offset)((uint32)((uint32)(i) << 11) + (offset)); |
1074 | #ifdef DEBUG2 |
1075 | (void)fprintf(stderrstderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", |
1076 | addr, tmp1, tmp2); |
1077 | #endif |
1078 | |
1079 | /* Allocate and return the overflow page */ |
1080 | return (addr); |
1081 | } |
1082 | |
1083 | /* |
1084 | * Mark this overflow page as free. |
1085 | */ |
1086 | extern void |
1087 | dbm_free_ovflpage(HTAB *hashp, BUFHEAD *obufp) |
1088 | { |
1089 | uint16 addr; |
1090 | uint32 *freep; |
1091 | uint32 bit_address, free_page, free_bit; |
1092 | uint16 ndx; |
1093 | |
1094 | if (!obufp || !obufp->addr) |
1095 | return; |
1096 | |
1097 | addr = obufp->addr; |
1098 | #ifdef DEBUG1 |
1099 | (void)fprintf(stderrstderr, "Freeing %d\n", addr); |
1100 | #endif |
1101 | ndx = (((uint16)addr) >> SPLITSHIFT11); |
1102 | bit_address = |
1103 | (ndx ? hashp->SPAREShdr.spares[ndx - 1] : 0) + (addr & SPLITMASK0x7FF) - 1; |
1104 | if (bit_address < (uint32)hashp->LAST_FREEDhdr.last_freed) |
1105 | hashp->LAST_FREEDhdr.last_freed = bit_address; |
1106 | free_page = (bit_address >> (hashp->BSHIFThdr.bshift + BYTE_SHIFT3)); |
1107 | free_bit = bit_address & ((hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1); |
1108 | |
1109 | if (!(freep = hashp->mapp[free_page])) |
1110 | freep = fetch_bitmap(hashp, free_page); |
1111 | |
1112 | #ifdef DEBUG1 |
1113 | /* |
1114 | * This had better never happen. It means we tried to read a bitmap |
1115 | * that has already had overflow pages allocated off it, and we |
1116 | * failed to read it from the file. |
1117 | */ |
1118 | if (!freep) { |
1119 | assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 1119, __extension__ __PRETTY_FUNCTION__)); |
1120 | return; |
1121 | } |
1122 | #endif |
1123 | CLRBIT(freep, free_bit)((freep)[(free_bit) / 32] &= ~(1 << ((free_bit) % 32 ))); |
1124 | #ifdef DEBUG2 |
1125 | (void)fprintf(stderrstderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", |
1126 | obufp->addr, free_bit, free_page); |
1127 | #endif |
1128 | dbm_reclaim_buf(hashp, obufp); |
1129 | } |
1130 | |
1131 | /* |
1132 | * Returns: |
1133 | * 0 success |
1134 | * -1 failure |
1135 | */ |
1136 | static int |
1137 | open_temp(HTAB *hashp) |
1138 | { |
1139 | #ifdef XP_OS2 |
1140 | hashp->fp = mkstemp(NULL((void*)0)); |
1141 | #else |
1142 | #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) |
1143 | sigset_t set, oset; |
1144 | #endif |
1145 | #if !defined(macintosh) |
1146 | char *tmpdir; |
1147 | size_t len; |
1148 | char last; |
1149 | #endif |
1150 | static const char namestr[] = "/_hashXXXXXX"; |
1151 | char filename[1024]; |
1152 | |
1153 | #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) |
1154 | /* Block signals; make sure file goes away at process exit. */ |
1155 | (void)sigfillset(&set); |
1156 | (void)sigprocmask(SIG_BLOCK0, &set, &oset); |
1157 | #endif |
1158 | |
1159 | filename[0] = 0; |
1160 | #if defined(macintosh) |
1161 | strcat(filename, namestr + 1); |
1162 | #else |
1163 | tmpdir = getenv("TMP"); |
1164 | if (!tmpdir) |
1165 | tmpdir = getenv("TMPDIR"); |
1166 | if (!tmpdir) |
1167 | tmpdir = getenv("TEMP"); |
1168 | if (!tmpdir) |
1169 | tmpdir = "."; |
1170 | len = strlen(tmpdir); |
1171 | if (len && len < (sizeof filename - sizeof namestr)) { |
1172 | strcpy(filename, tmpdir); |
1173 | } |
1174 | len = strlen(filename); |
1175 | last = tmpdir[len - 1]; |
1176 | strcat(filename, (last == '/' || last == '\\') ? namestr + 1 : namestr); |
1177 | #endif |
1178 | |
1179 | #if defined(_WIN32) || defined(_WINDOWS) |
1180 | if ((hashp->fp = mkstempflags(filename, _O_BINARY | _O_TEMPORARY)) != -1) { |
1181 | if (hashp->filename) { |
1182 | free(hashp->filename); |
1183 | } |
1184 | hashp->filename = strdup(filename); |
1185 | hashp->is_temp = 1; |
1186 | } |
1187 | #else |
1188 | if ((hashp->fp = mkstemp(filename)) != -1) { |
1189 | (void)unlink(filename); |
1190 | #if !defined(macintosh) |
1191 | (void)fcntl(hashp->fp, F_SETFD2, 1); |
1192 | #endif |
1193 | } |
1194 | #endif |
1195 | |
1196 | #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) |
1197 | (void)sigprocmask(SIG_SETMASK2, &oset, (sigset_t *)NULL((void*)0)); |
1198 | #endif |
1199 | #endif /* !OS2 */ |
1200 | return (hashp->fp != -1 ? 0 : -1); |
1201 | } |
1202 | |
1203 | /* |
1204 | * We have to know that the key will fit, but the last entry on the page is |
1205 | * an overflow pair, so we need to shift things. |
1206 | */ |
1207 | static void |
1208 | squeeze_key(uint16 *sp, const DBT *key, const DBT *val) |
1209 | { |
1210 | register char *p; |
1211 | uint16 free_space, n, off, pageno; |
1212 | |
1213 | p = (char *)sp; |
1214 | n = sp[0]; |
1215 | free_space = FREESPACE(sp)((sp)[(sp)[0] + 1]); |
1216 | off = OFFSET(sp)((sp)[(sp)[0] + 2]); |
1217 | |
1218 | pageno = sp[n - 1]; |
1219 | off -= key->size; |
1220 | sp[n - 1] = off; |
1221 | memmove(p + off, key->data, key->size); |
1222 | off -= val->size; |
1223 | sp[n] = off; |
1224 | memmove(p + off, val->data, val->size); |
1225 | sp[0] = n + 2; |
1226 | sp[n + 1] = pageno; |
1227 | sp[n + 2] = OVFLPAGE0; |
1228 | FREESPACE(sp)((sp)[(sp)[0] + 1]) = free_space - PAIRSIZE(key, val)(2 * sizeof(uint16) + (key)->size + (val)->size); |
1229 | OFFSET(sp)((sp)[(sp)[0] + 2]) = off; |
1230 | } |
1231 | |
1232 | static uint32 * |
1233 | fetch_bitmap(HTAB *hashp, uint32 ndx) |
1234 | { |
1235 | if (ndx >= (unsigned)hashp->nmaps) |
1236 | return (NULL((void*)0)); |
1237 | if ((hashp->mapp[ndx] = (uint32 *)malloc((size_t)hashp->BSIZEhdr.bsize)) == NULL((void*)0)) |
1238 | return (NULL((void*)0)); |
1239 | if (dbm_get_page(hashp, |
1240 | (char *)hashp->mapp[ndx], hashp->BITMAPShdr.bitmaps[ndx], 0, 1, 1)) { |
1241 | free(hashp->mapp[ndx]); |
1242 | hashp->mapp[ndx] = NULL((void*)0); /* NEW: 9-11-95 */ |
1243 | return (NULL((void*)0)); |
1244 | } |
1245 | return (hashp->mapp[ndx]); |
1246 | } |
1247 | |
1248 | #ifdef DEBUG4 |
1249 | int |
1250 | print_chain(int addr) |
1251 | { |
1252 | BUFHEAD *bufp; |
1253 | short *bp, oaddr; |
1254 | |
1255 | (void)fprintf(stderrstderr, "%d ", addr); |
1256 | bufp = dbm_get_buf(hashp, addr, NULL((void*)0), 0); |
1257 | bp = (short *)bufp->page; |
1258 | while (bp[0] && ((bp[bp[0]] == OVFLPAGE0) || |
1259 | ((bp[0] > 2) && bp[2] < REAL_KEY4))) { |
1260 | oaddr = bp[bp[0] - 1]; |
1261 | (void)fprintf(stderrstderr, "%d ", (int)oaddr); |
1262 | bufp = dbm_get_buf(hashp, (int)oaddr, bufp, 0); |
1263 | bp = (short *)bufp->page; |
1264 | } |
1265 | (void)fprintf(stderrstderr, "\n"); |
1266 | } |
1267 | #endif |