* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- * must display the following acknowledgement:
- * This product includes software developed by the University of
- * California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
static char sccsid[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94";
#endif /* LIBC_SCCS and not lint */
#include <sys/cdefs.h>
-__FBSDID("$FreeBSD: src/lib/libc/db/hash/hash_page.c,v 1.8 2002/03/21 22:46:26 obrien Exp $");
+__FBSDID("$FreeBSD: src/lib/libc/db/hash/hash_page.c,v 1.16 2009/03/28 06:30:43 delphij Exp $");
/*
* PACKAGE: hashing
*/
#include "namespace.h"
-#include <sys/types.h>
+#include <sys/param.h>
#include <errno.h>
#include <fcntl.h>
#include <db.h>
#include "hash.h"
#include "page.h"
-#include "extern.h"
+#include "hash_extern.h"
-static u_int32_t *fetch_bitmap(HTAB *, int);
-static u_int32_t first_free(u_int32_t);
-static int open_temp(HTAB *);
-static u_int16_t overflow_page(HTAB *);
-static void putpair(char *, const DBT *, const DBT *);
-static void squeeze_key(u_int16_t *, const DBT *, const DBT *);
-static int ugly_split
-(HTAB *, u_int32_t, BUFHEAD *, BUFHEAD *, int, int);
+static u_int32_t *fetch_bitmap(HTAB *, int);
+static u_int32_t first_free(u_int32_t);
+static int open_temp(HTAB *);
+static u_int16_t overflow_page(HTAB *);
+static void putpair(char *, const DBT *, const DBT *);
+static void squeeze_key(u_int16_t *, const DBT *, const DBT *);
+static int ugly_split(HTAB *, u_int32_t, BUFHEAD *, BUFHEAD *, int, int);
#define PAGE_INIT(P) { \
((u_int16_t *)(P))[0] = 0; \
* stuff on.
*/
static void
-putpair(p, key, val)
- char *p;
- const DBT *key, *val;
+putpair(char *p, const DBT *key, const DBT *val)
{
u_int16_t *bp, n, off;
* 0 OK
* -1 error
*/
-extern int
-__delpair(hashp, bufp, ndx)
- HTAB *hashp;
- BUFHEAD *bufp;
- int ndx;
+int
+__delpair(HTAB *hashp, BUFHEAD *bufp, int ndx)
{
- u_int16_t *bp, newoff;
+ u_int16_t *bp, newoff, pairlen;
int n;
- u_int16_t pairlen;
bp = (u_int16_t *)bufp->page;
n = bp[0];
bp[i - 1] = bp[i + 1] + pairlen;
}
}
+ if (ndx == hashp->cndx) {
+ /*
+ * We just removed pair we were "pointing" to.
+ * By moving back the cndx we ensure subsequent
+ * hash_seq() calls won't skip over any entries.
+ */
+ hashp->cndx -= 2;
+ }
}
/* Finally adjust the page data */
bp[n] = OFFSET(bp) + pairlen;
* 0 ==> OK
* -1 ==> Error
*/
-extern int
-__split_page(hashp, obucket, nbucket)
- HTAB *hashp;
- u_int32_t obucket, nbucket;
+int
+__split_page(HTAB *hashp, u_int32_t obucket, u_int32_t nbucket)
{
BUFHEAD *new_bufp, *old_bufp;
u_int16_t *ino;
* -1 ==> failure
*/
static int
-ugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved)
- HTAB *hashp;
- u_int32_t obucket; /* Same as __split_page. */
- BUFHEAD *old_bufp, *new_bufp;
- int copyto; /* First byte on page which contains key/data values. */
- int moved; /* Number of pairs moved to new page. */
+ugly_split(HTAB *hashp,
+ u_int32_t obucket, /* Same as __split_page. */
+ BUFHEAD *old_bufp,
+ BUFHEAD *new_bufp,
+ int copyto, /* First byte on page which contains key/data values. */
+ int moved) /* Number of pairs moved to new page. */
{
- BUFHEAD *bufp; /* Buffer header for ino */
- u_int16_t *ino; /* Page keys come off of */
- u_int16_t *np; /* New page */
- u_int16_t *op; /* Page keys go on to if they aren't moving */
+ BUFHEAD *bufp; /* Buffer header for ino */
+ u_int16_t *ino; /* Page keys come off of */
+ u_int16_t *np; /* New page */
+ u_int16_t *op; /* Page keys go on to if they aren't moving */
BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */
DBT key, val;
* 0 ==> OK
* 1 ==> failure
*/
-extern int
-__addel(hashp, bufp, key, val)
- HTAB *hashp;
- BUFHEAD *bufp;
- const DBT *key, *val;
+int
+__addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val)
{
u_int16_t *bp, *sop;
int do_expand;
if (!bufp)
return (-1);
bp = (u_int16_t *)bufp->page;
- } else
+ } else if (bp[bp[0]] != OVFLPAGE) {
+ /* Short key/data pairs, no more pages */
+ break;
+ } else {
/* Try to squeeze key on this page */
- if (FREESPACE(bp) > PAIRSIZE(key, val)) {
+ if (bp[2] >= REAL_KEY &&
+ FREESPACE(bp) >= PAIRSIZE(key, val)) {
squeeze_key(bp, key, val);
- return (0);
+ goto stats;
} else {
bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
if (!bufp)
return (-1);
bp = (u_int16_t *)bufp->page;
}
+ }
if (PAIRFITS(bp, key, val))
putpair(bufp->page, key, val);
if (__big_insert(hashp, bufp, key, val))
return (-1);
}
+stats:
bufp->flags |= BUF_MOD;
/*
* If the average number of keys per bucket exceeds the fill factor,
* pointer on success
* NULL on error
*/
-extern BUFHEAD *
-__add_ovflpage(hashp, bufp)
- HTAB *hashp;
- BUFHEAD *bufp;
+BUFHEAD *
+__add_ovflpage(HTAB *hashp, BUFHEAD *bufp)
{
- u_int16_t *sp;
- u_int16_t ndx, ovfl_num;
+ u_int16_t *sp, ndx, ovfl_num;
#ifdef DEBUG1
int tmp1, tmp2;
#endif
* 0 indicates SUCCESS
* -1 indicates FAILURE
*/
-extern int
-__get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap)
- HTAB *hashp;
- char *p;
- u_int32_t bucket;
- int is_bucket, is_disk, is_bitmap;
+int
+__get_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_disk,
+ int is_bitmap)
{
- int fd, page, size;
- int rsize;
+ int fd, page, size, rsize;
u_int16_t *bp;
fd = hashp->fp;
page = BUCKET_TO_PAGE(bucket);
else
page = OADDR_TO_PAGE(bucket);
- if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
- ((rsize = _read(fd, p, size)) == -1))
+ if ((rsize = pread(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1)
return (-1);
bp = (u_int16_t *)p;
if (!rsize)
* 0 ==> OK
* -1 ==>failure
*/
-extern int
-__put_page(hashp, p, bucket, is_bucket, is_bitmap)
- HTAB *hashp;
- char *p;
- u_int32_t bucket;
- int is_bucket, is_bitmap;
+int
+__put_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_bitmap)
{
- int fd, page, size;
- int wsize;
+ int fd, page, size, wsize, max;
size = hashp->BSIZE;
if ((hashp->fp == -1) && open_temp(hashp))
if (hashp->LORDER != BYTE_ORDER) {
int i;
- int max;
if (is_bitmap) {
max = hashp->BSIZE >> 2; /* divide by 4 */
page = BUCKET_TO_PAGE(bucket);
else
page = OADDR_TO_PAGE(bucket);
- if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
- ((wsize = _write(fd, p, size)) == -1))
+ if ((wsize = pwrite(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1)
/* Errno is set */
return (-1);
if (wsize != size) {
errno = EFTYPE;
return (-1);
}
+ /* 4485533 - reswap the in-memory copy */
+ if (hashp->LORDER != BYTE_ORDER) {
+ int i;
+
+ if (is_bitmap) {
+ for (i = 0; i < max; i++)
+ M_32_SWAP(((int *)p)[i]);
+ } else {
+ for (i = 0; i <= max; i++)
+ M_16_SWAP(((u_int16_t *)p)[i]);
+ }
+ }
return (0);
}
* Initialize a new bitmap page. Bitmap pages are left in memory
* once they are read in.
*/
-extern int
-__ibitmap(hashp, pnum, nbits, ndx)
- HTAB *hashp;
- int pnum, nbits, ndx;
+int
+__ibitmap(HTAB *hashp, int pnum, int nbits, int ndx)
{
u_int32_t *ip;
int clearbytes, clearints;
}
static u_int32_t
-first_free(map)
- u_int32_t map;
+first_free(u_int32_t map)
{
u_int32_t i, mask;
}
static u_int16_t
-overflow_page(hashp)
- HTAB *hashp;
+overflow_page(HTAB *hashp)
{
u_int32_t *freep;
int max_free, offset, splitnum;
if (offset > SPLITMASK) {
if (++splitnum >= NCACHED) {
(void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
+ errno = EFBIG;
return (0);
}
hashp->OVFL_POINT = splitnum;
free_page++;
if (free_page >= NCACHED) {
(void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
+ errno = EFBIG;
return (0);
}
/*
if (++splitnum >= NCACHED) {
(void)_write(STDERR_FILENO, OVMSG,
sizeof(OVMSG) - 1);
+ errno = EFBIG;
return (0);
}
hashp->OVFL_POINT = splitnum;
/* Calculate the split number for this page */
for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++);
offset = (i ? bit - hashp->SPARES[i - 1] : bit);
- if (offset >= SPLITMASK)
+ if (offset >= SPLITMASK) {
+ (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
+ errno = EFBIG;
return (0); /* Out of overflow pages */
+ }
addr = OADDR_OF(i, offset);
#ifdef DEBUG2
(void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
/*
* Mark this overflow page as free.
*/
-extern void
-__free_ovflpage(hashp, obufp)
- HTAB *hashp;
- BUFHEAD *obufp;
+void
+__free_ovflpage(HTAB *hashp, BUFHEAD *obufp)
{
u_int16_t addr;
u_int32_t *freep;
* -1 failure
*/
static int
-open_temp(hashp)
- HTAB *hashp;
+open_temp(HTAB *hashp)
{
sigset_t set, oset;
- static char namestr[] = "_hashXXXXXX";
+ int len;
+ char *envtmp = NULL;
+ char path[MAXPATHLEN];
+
+ if (issetugid() == 0)
+ envtmp = getenv("TMPDIR");
+ len = snprintf(path,
+ sizeof(path), "%s/_hash.XXXXXX", envtmp ? envtmp : "/tmp");
+ if (len < 0 || len >= sizeof(path)) {
+ errno = ENAMETOOLONG;
+ return (-1);
+ }
/* Block signals; make sure file goes away at process exit. */
(void)sigfillset(&set);
(void)_sigprocmask(SIG_BLOCK, &set, &oset);
- if ((hashp->fp = mkstemp(namestr)) != -1) {
- (void)unlink(namestr);
+ if ((hashp->fp = mkstemp(path)) != -1) {
+ (void)unlink(path);
(void)_fcntl(hashp->fp, F_SETFD, 1);
}
(void)_sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
* an overflow pair, so we need to shift things.
*/
static void
-squeeze_key(sp, key, val)
- u_int16_t *sp;
- const DBT *key, *val;
+squeeze_key(u_int16_t *sp, const DBT *key, const DBT *val)
{
char *p;
u_int16_t free_space, n, off, pageno;
}
static u_int32_t *
-fetch_bitmap(hashp, ndx)
- HTAB *hashp;
- int ndx;
+fetch_bitmap(HTAB *hashp, int ndx)
{
if (ndx >= hashp->nmaps)
return (NULL);
#ifdef DEBUG4
int
-print_chain(addr)
- int addr;
+print_chain(int addr)
{
BUFHEAD *bufp;
short *bp, oaddr;
projects / apple / libc.git / blobdiff