File: | s/lib/dbm/src/h_page.c |
Warning: | line 1040, column 9 Array access (from variable 'freep') results in a null pointer dereference |
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; | |||
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 |