From bec2d00aee11811f26f3f148c6197e34c35176ed Mon Sep 17 00:00:00 2001 From: deraadt Date: Tue, 7 May 1996 09:00:07 +0000 Subject: [PATCH] db release 1.85 --- include/mpool.h | 112 ++--- lib/libc/db/README | 43 +- lib/libc/db/VERSION | 113 ----- lib/libc/db/btree/Makefile.inc | 6 +- lib/libc/db/btree/bt_close.c | 86 ++-- lib/libc/db/btree/bt_conv.c | 22 +- lib/libc/db/btree/bt_debug.c | 40 +- lib/libc/db/btree/bt_delete.c | 667 +++++++++++++++++++++------- lib/libc/db/btree/bt_get.c | 145 +------ lib/libc/db/btree/bt_open.c | 70 +-- lib/libc/db/btree/bt_overflow.c | 8 +- lib/libc/db/btree/bt_page.c | 25 +- lib/libc/db/btree/bt_put.c | 100 ++--- lib/libc/db/btree/bt_search.c | 134 +++--- lib/libc/db/btree/bt_seq.c | 384 +++++++++------- lib/libc/db/btree/bt_split.c | 42 +- lib/libc/db/btree/bt_stack.c | 102 ----- lib/libc/db/btree/bt_utils.c | 104 +++-- lib/libc/db/btree/btree.h | 202 +++++---- lib/libc/db/btree/extern.h | 14 +- lib/libc/db/changelog | 105 +++++ lib/libc/db/db2netbsd | 31 ++ lib/libc/db/hash/Makefile.inc | 2 +- lib/libc/db/hash/README | 2 +- lib/libc/db/hash/extern.h | 2 +- lib/libc/db/hash/hash.c | 4 +- lib/libc/db/hash/hash.h | 2 +- lib/libc/db/hash/hash_bigkey.c | 4 +- lib/libc/db/hash/hash_buf.c | 12 +- lib/libc/db/hash/hash_func.c | 4 +- lib/libc/db/hash/hash_log2.c | 4 +- lib/libc/db/hash/hash_page.c | 22 +- lib/libc/db/hash/hsearch.c | 8 +- lib/libc/db/hash/ndbm.c | 59 ++- lib/libc/db/hash/page.h | 2 +- lib/libc/db/hash/search.h | 2 +- lib/libc/db/man/btree.3 | 13 +- lib/libc/db/man/hash.3 | 13 +- lib/libc/db/man/recno.3 | 26 +- lib/libc/db/mpool/mpool.c | 431 ++++++++---------- lib/libc/db/mpool/mpool.libtp | 746 ++++++++++++++++++++++++++++++++ lib/libc/db/recno/Makefile.inc | 2 +- lib/libc/db/recno/extern.h | 2 +- lib/libc/db/recno/rec_close.c | 63 ++- lib/libc/db/recno/rec_delete.c | 14 +- lib/libc/db/recno/rec_get.c | 109 ++--- lib/libc/db/recno/rec_open.c | 47 +- lib/libc/db/recno/rec_put.c | 53 ++- lib/libc/db/recno/rec_search.c | 9 +- lib/libc/db/recno/rec_seq.c | 26 +- lib/libc/db/recno/rec_utils.c | 79 ++-- lib/libc/db/recno/recno.h | 2 +- regress/lib/libc/db/README | 36 +- regress/lib/libc/db/dbtest.c | 213 ++++++--- regress/lib/libc/db/run.test | 35 +- 55 files changed, 2862 insertions(+), 1741 deletions(-) create mode 100644 lib/libc/db/changelog create mode 100644 lib/libc/db/db2netbsd create mode 100644 lib/libc/db/mpool/mpool.libtp diff --git a/include/mpool.h b/include/mpool.h index 849729759b3..622d2c9a377 100644 --- a/include/mpool.h +++ b/include/mpool.h @@ -1,7 +1,7 @@ -/* $NetBSD: mpool.h,v 1.6 1994/10/26 00:56:07 cgd Exp $ */ +/* $NetBSD: mpool.h,v 1.7 1996/05/03 21:13:41 cgd Exp $ */ /*- - * Copyright (c) 1991, 1993 + * Copyright (c) 1991, 1993, 1994 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -32,98 +32,62 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * @(#)mpool.h 8.1 (Berkeley) 6/2/93 + * @(#)mpool.h 8.2 (Berkeley) 7/14/94 */ +#include + /* - * The memory pool scheme is a simple one. Each in memory page is referenced - * by a bucket which is threaded in three ways. All active pages are threaded - * on a hash chain (hashed by the page number) and an lru chain. Inactive - * pages are threaded on a free chain. Each reference to a memory pool is - * handed an MPOOL which is the opaque cookie passed to all of the memory - * routines. + * The memory pool scheme is a simple one. Each in-memory page is referenced + * by a bucket which is threaded in up to two of three ways. All active pages + * are threaded on a hash chain (hashed by page number) and an lru chain. + * Inactive pages are threaded on a free chain. Each reference to a memory + * pool is handed an opaque MPOOL cookie which stores all of this information. */ #define HASHSIZE 128 #define HASHKEY(pgno) ((pgno - 1) % HASHSIZE) -/* The BKT structures are the elements of the lists. */ -typedef struct BKT { - struct BKT *hnext; /* next hash bucket */ - struct BKT *hprev; /* previous hash bucket */ - struct BKT *cnext; /* next free/lru bucket */ - struct BKT *cprev; /* previous free/lru bucket */ - void *page; /* page */ - pgno_t pgno; /* page number */ +/* The BKT structures are the elements of the queues. */ +typedef struct _bkt { + CIRCLEQ_ENTRY(_bkt) hq; /* hash queue */ + CIRCLEQ_ENTRY(_bkt) q; /* lru queue */ + void *page; /* page */ + pgno_t pgno; /* page number */ #define MPOOL_DIRTY 0x01 /* page needs to be written */ #define MPOOL_PINNED 0x02 /* page is pinned into memory */ - unsigned long flags; /* flags */ + u_int8_t flags; /* flags */ } BKT; -/* The BKTHDR structures are the heads of the lists. */ -typedef struct BKTHDR { - struct BKT *hnext; /* next hash bucket */ - struct BKT *hprev; /* previous hash bucket */ - struct BKT *cnext; /* next free/lru bucket */ - struct BKT *cprev; /* previous free/lru bucket */ -} BKTHDR; - typedef struct MPOOL { - BKTHDR free; /* The free list. */ - BKTHDR lru; /* The LRU list. */ - BKTHDR hashtable[HASHSIZE]; /* Hashed list by page number. */ - pgno_t curcache; /* Current number of cached pages. */ - pgno_t maxcache; /* Max number of cached pages. */ - pgno_t npages; /* Number of pages in the file. */ - u_long pagesize; /* File page size. */ - int fd; /* File descriptor. */ - /* Page in conversion routine. */ + CIRCLEQ_HEAD(_lqh, _bkt) lqh; /* lru queue head */ + /* hash queue array */ + CIRCLEQ_HEAD(_hqh, _bkt) hqh[HASHSIZE]; + pgno_t curcache; /* current number of cached pages */ + pgno_t maxcache; /* max number of cached pages */ + pgno_t npages; /* number of pages in the file */ + u_long pagesize; /* file page size */ + int fd; /* file descriptor */ + /* page in conversion routine */ void (*pgin) __P((void *, pgno_t, void *)); - /* Page out conversion routine. */ + /* page out conversion routine */ void (*pgout) __P((void *, pgno_t, void *)); - void *pgcookie; /* Cookie for page in/out routines. */ + void *pgcookie; /* cookie for page in/out routines */ #ifdef STATISTICS - unsigned long cachehit; - unsigned long cachemiss; - unsigned long pagealloc; - unsigned long pageflush; - unsigned long pageget; - unsigned long pagenew; - unsigned long pageput; - unsigned long pageread; - unsigned long pagewrite; + u_long cachehit; + u_long cachemiss; + u_long pagealloc; + u_long pageflush; + u_long pageget; + u_long pagenew; + u_long pageput; + u_long pageread; + u_long pagewrite; #endif } MPOOL; -#ifdef __MPOOLINTERFACE_PRIVATE -/* Macros to insert/delete into/from hash chain. */ -#define rmhash(bp) { \ - (bp)->hprev->hnext = (bp)->hnext; \ - (bp)->hnext->hprev = (bp)->hprev; \ -} -#define inshash(bp, pg) { \ - hp = &mp->hashtable[HASHKEY(pg)]; \ - (bp)->hnext = hp->hnext; \ - (bp)->hprev = (struct BKT *)hp; \ - hp->hnext->hprev = (bp); \ - hp->hnext = (bp); \ -} - -/* Macros to insert/delete into/from lru and free chains. */ -#define rmchain(bp) { \ - (bp)->cprev->cnext = (bp)->cnext; \ - (bp)->cnext->cprev = (bp)->cprev; \ -} -#define inschain(bp, dp) { \ - (bp)->cnext = (dp)->cnext; \ - (bp)->cprev = (struct BKT *)(dp); \ - (dp)->cnext->cprev = (bp); \ - (dp)->cnext = (bp); \ -} -#endif - __BEGIN_DECLS -MPOOL *mpool_open __P((DBT *, int, pgno_t, pgno_t)); +MPOOL *mpool_open __P((void *, int, pgno_t, pgno_t)); void mpool_filter __P((MPOOL *, void (*)(void *, pgno_t, void *), void (*)(void *, pgno_t, void *), void *)); void *mpool_new __P((MPOOL *, pgno_t *)); diff --git a/lib/libc/db/README b/lib/libc/db/README index df1be282063..d06cdf14fc7 100644 --- a/lib/libc/db/README +++ b/lib/libc/db/README @@ -1,2 +1,41 @@ -$NetBSD: README,v 1.2 1995/02/27 13:19:30 cgd Exp $ -(was symlink to VERSION. -- cgd) +# $NetBSD: README,v 1.3 1996/05/03 21:17:07 cgd Exp $ +# @(#)README 8.27 (Berkeley) 9/1/94 + +This is version 1.85 of the Berkeley DB code. + +For information on compiling and installing this software, see the file +PORT/README. + +Newer versions of this software will periodically be made available by +anonymous ftp from ftp.cs.berkeley.edu. An archive in compressed format +is in ucb/4bsd/db.tar.Z, or in gzip format in ucb/4bsd/db.tar.gz. If +you'd like to receive announcements of future releases of this software, +send email to the contact address below. + +Email questions may be addressed to Keith Bostic at bostic@cs.berkeley.edu. + +============================================ +Distribution contents: + +Makefile.inc Ignore this, it's the 4.4BSD subsystem Makefile. +PORT The per OS/architecture directories to use to build + libdb.a, if you're not running 4.4BSD. See the file + PORT/README for more information. +README This file. +btree The B+tree routines. +changelog List of changes, per version. +db The dbopen(3) interface routine. +docs Various USENIX papers, and the formatted manual pages. +hash The extended linear hashing routines. +man The unformatted manual pages. +mpool The memory pool routines. +recno The fixed/variable length record routines. +test Test package. + +============================================ +Debugging: + +If you're running a memory checker (e.g. Purify) on DB, make sure that +you recompile it with "-DPURIFY" in the CFLAGS, first. By default, +allocated pages are not initialized by the DB code, and they will show +up as reads of uninitialized memory in the buffer write routines. diff --git a/lib/libc/db/VERSION b/lib/libc/db/VERSION index 440b71bad09..e69de29bb2d 100644 --- a/lib/libc/db/VERSION +++ b/lib/libc/db/VERSION @@ -1,113 +0,0 @@ -# $NetBSD: VERSION,v 1.7 1995/02/27 13:19:33 cgd Exp $ -# @(#)VERSION 8.17 (Berkeley) 6/20/94 - -This is version 1.79 of the Berkeley DB code. - -For information on compiling and installing this software, see the file -PORT/README. - -If your version of the DB code doesn't have a copy of this version file, -it's really old, please update it! - -Newer versions of this software will periodically be made available by -anonymous ftp from ftp.cs.berkeley.edu. An archive in compressed format -is in ucb/4bsd/db.tar.Z, or in gzip format in ucb/4bsd/db.tar.gz. If -you'd like to receive announcements of future releases of this software, -send email to the contact address below. - -Email questions may be addressed to Keith Bostic at bostic@cs.berkeley.edu. - -============================================ -Distribution contents: - -Makefile.inc Ignore this, it's the 4.4BSD subsystem Makefile. -PORT The per OS/architecture directories to use to build - libdb.a, if you're not running 4.4BSD. See the file - PORT/README for more information. -README This file. -VERSION This file. -btree B+tree routines. -db Dbopen(3) interface routine. -doc USENIX papers, formatted manual pages. -hash Extended linear hashing routines. -man Unformatted manual pages. -mpool Memory pool routines. -recno Fixed/variable length record routines. -test Test package. - -============================================ -1.78 -> 1.79 Mon Jun 20 17:36:47 EDT 1994 - all: Minor cleanups of 1.78 for porting reasons; only - major change was inlining check of NULL pointer - so that __fix_realloc goes away. - -1.77 -> 1.78 Thu Jun 16 19:06:43 EDT 1994 - all: Move "standard" size typedef's into db.h. - -1.76 -> 1.77 Thu Jun 16 16:48:38 EDT 1994 - hash: Delete __init_ routine, has special meaning to OSF 2.0. - -1.74 -> 1.76 - all: Finish up the port to the Alpha. - -1.73 -> 1.74 - recno: Don't put the record if rec_search fails, in rec_rdelete. - Create fixed-length intermediate records past "end" of DB - correctly. - Realloc bug when reading in fixed records. - all: First cut at port to Alpha (64-bit architecture) using - 4.4BSD basic integral types typedef's. - Cast allocation pointers to shut up old compilers. - Rework PORT directory into OS/machine directories. - -1.72 -> 1.73 - btree: If enough duplicate records were inserted and then deleted - that internal pages had references to empty pages of the - duplicate keys, the search function ended up on the wrong - page. - -1.7 -> 1.72 12 Oct 1993 - hash: Support NET/2 hash formats. - -1.7 -> 1.71 16 Sep 1993 - btree/recno: - Fix bug in internal search routines that caused - return of invalid pointers. - -1.6 -> 1.7 07 Sep 1993 - hash: Fixed big key overflow bugs. - test: Portability hacks, rewrite test script, Makefile. - btree/recno: - Stop copying non-overflow key/data pairs. - PORT: Break PORT directory up into per architecture/OS - subdirectories. - -1.5 -> 1.6 06 Jun 1993 - hash: In PAIRFITS, the first comparison should look at (P)[2]. - The hash_realloc function was walking off the end of memory. - The overflow page number was wrong when bumping splitpoint. - -1.4 -> 1.5 23 May 1993 - hash: Set hash default fill factor dynamically. - recno: Fixed bug in sorted page splits. - Add page size parameter support. - Allow recno to specify the name of the underlying btree; - used for vi recovery. - btree/recno: - Support 64K pages. - btree/hash/recno: - Provide access to an underlying file descriptor. - Change sync routines to take a flag argument, recno - uses this to sync out the underlying btree. - -1.3 -> 1.4 10 May 1993 - recno: Delete the R_CURSORLOG flag from the recno interface. - Zero-length record fix for non-mmap reads. - Try and make SIZE_T_MAX test in open portable. - -1.2 -> 1.3 01 May 1993 - btree: Ignore user byte-order setting when reading already - existing database. Fixes to byte-order conversions. - -1.1 -> 1.2 15 Apr 1993 - No bug fixes, only compatibility hacks. diff --git a/lib/libc/db/btree/Makefile.inc b/lib/libc/db/btree/Makefile.inc index d187103e2d3..46fbb029e39 100644 --- a/lib/libc/db/btree/Makefile.inc +++ b/lib/libc/db/btree/Makefile.inc @@ -1,8 +1,8 @@ -# $NetBSD: Makefile.inc,v 1.5 1995/02/27 13:19:53 cgd Exp $ -# @(#)Makefile.inc 8.1 (Berkeley) 6/4/93 +# $NetBSD: Makefile.inc,v 1.6 1996/05/03 21:50:36 cgd Exp $ +# @(#)Makefile.inc 8.2 (Berkeley) 7/14/94 .PATH: ${.CURDIR}/db/btree SRCS+= bt_close.c bt_conv.c bt_debug.c bt_delete.c bt_get.c bt_open.c \ bt_overflow.c bt_page.c bt_put.c bt_search.c bt_seq.c bt_split.c \ - bt_stack.c bt_utils.c + bt_utils.c diff --git a/lib/libc/db/btree/bt_close.c b/lib/libc/db/btree/bt_close.c index 2b27327f7ed..b18c278602e 100644 --- a/lib/libc/db/btree/bt_close.c +++ b/lib/libc/db/btree/bt_close.c @@ -1,7 +1,7 @@ -/* $NetBSD: bt_close.c,v 1.6 1995/02/27 13:19:59 cgd Exp $ */ +/* $NetBSD: bt_close.c,v 1.7 1996/05/03 21:50:38 cgd Exp $ */ /*- - * Copyright (c) 1990, 1993 + * Copyright (c) 1990, 1993, 1994 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_close.c 8.3 (Berkeley) 2/21/94"; +static char sccsid[] = "@(#)bt_close.c 8.7 (Berkeley) 8/17/94"; #else -static char rcsid[] = "$NetBSD: bt_close.c,v 1.6 1995/02/27 13:19:59 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_close.c,v 1.7 1996/05/03 21:50:38 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -81,25 +81,30 @@ __bt_close(dbp) t->bt_pinned = NULL; } - /* - * Delete any already deleted record that we've been saving - * because the cursor pointed to it. - */ - if (ISSET(t, B_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor)) - return (RET_ERROR); - + /* Sync the tree. */ if (__bt_sync(dbp, 0) == RET_ERROR) return (RET_ERROR); + /* Close the memory pool. */ if (mpool_close(t->bt_mp) == RET_ERROR) return (RET_ERROR); - if (t->bt_stack) - free(t->bt_stack); - if (t->bt_kbuf) - free(t->bt_kbuf); - if (t->bt_dbuf) - free(t->bt_dbuf); + /* Free random memory. */ + if (t->bt_cursor.key.data != NULL) { + free(t->bt_cursor.key.data); + t->bt_cursor.key.size = 0; + t->bt_cursor.key.data = NULL; + } + if (t->bt_rkey.data) { + free(t->bt_rkey.data); + t->bt_rkey.size = 0; + t->bt_rkey.data = NULL; + } + if (t->bt_rdata.data) { + free(t->bt_rdata.data); + t->bt_rdata.size = 0; + t->bt_rdata.data = NULL; + } fd = t->bt_fd; free(t); @@ -123,8 +128,6 @@ __bt_sync(dbp, flags) { BTREE *t; int status; - PAGE *h; - void *p; t = dbp->internal; @@ -140,40 +143,15 @@ __bt_sync(dbp, flags) return (RET_ERROR); } - if (ISSET(t, B_INMEM | B_RDONLY) || !ISSET(t, B_MODIFIED)) + if (F_ISSET(t, B_INMEM | B_RDONLY) || !F_ISSET(t, B_MODIFIED)) return (RET_SUCCESS); - if (ISSET(t, B_METADIRTY) && bt_meta(t) == RET_ERROR) + if (F_ISSET(t, B_METADIRTY) && bt_meta(t) == RET_ERROR) return (RET_ERROR); - /* - * Nastiness. If the cursor has been marked for deletion, but not - * actually deleted, we have to make a copy of the page, delete the - * key/data item, sync the file, and then restore the original page - * contents. - */ - if (ISSET(t, B_DELCRSR)) { - if ((p = (void *)malloc(t->bt_psize)) == NULL) - return (RET_ERROR); - if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL) - return (RET_ERROR); - memmove(p, h, t->bt_psize); - if ((status = - __bt_dleaf(t, h, t->bt_bcursor.index)) == RET_ERROR) - goto ecrsr; - mpool_put(t->bt_mp, h, MPOOL_DIRTY); - } - if ((status = mpool_sync(t->bt_mp)) == RET_SUCCESS) - CLR(t, B_MODIFIED); - -ecrsr: if (ISSET(t, B_DELCRSR)) { - if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL) - return (RET_ERROR); - memmove(h, p, t->bt_psize); - free(p); - mpool_put(t->bt_mp, h, MPOOL_DIRTY); - } + F_CLR(t, B_MODIFIED); + return (status); } @@ -197,12 +175,12 @@ bt_meta(t) return (RET_ERROR); /* Fill in metadata. */ - m.m_magic = BTREEMAGIC; - m.m_version = BTREEVERSION; - m.m_psize = t->bt_psize; - m.m_free = t->bt_free; - m.m_nrecs = t->bt_nrecs; - m.m_flags = t->bt_flags & SAVEMETA; + m.magic = BTREEMAGIC; + m.version = BTREEVERSION; + m.psize = t->bt_psize; + m.free = t->bt_free; + m.nrecs = t->bt_nrecs; + m.flags = F_ISSET(t, SAVEMETA); memmove(p, &m, sizeof(BTMETA)); mpool_put(t->bt_mp, p, MPOOL_DIRTY); diff --git a/lib/libc/db/btree/bt_conv.c b/lib/libc/db/btree/bt_conv.c index 1d513865455..27ab66c0752 100644 --- a/lib/libc/db/btree/bt_conv.c +++ b/lib/libc/db/btree/bt_conv.c @@ -1,4 +1,4 @@ -/* $NetBSD: bt_conv.c,v 1.5 1995/02/27 13:20:04 cgd Exp $ */ +/* $NetBSD: bt_conv.c,v 1.6 1996/05/03 21:50:39 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_conv.c 8.3 (Berkeley) 5/31/94"; +static char sccsid[] = "@(#)bt_conv.c 8.5 (Berkeley) 8/17/94"; #else -static char rcsid[] = "$NetBSD: bt_conv.c,v 1.5 1995/02/27 13:20:04 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_conv.c,v 1.6 1996/05/03 21:50:39 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -74,7 +74,7 @@ __bt_pgin(t, pg, pp) u_char flags; char *p; - if (!ISSET(((BTREE *)t), B_NEEDSWAP)) + if (!F_ISSET(((BTREE *)t), B_NEEDSWAP)) return; if (pg == P_META) { mswap(pp); @@ -142,7 +142,7 @@ __bt_pgout(t, pg, pp) u_char flags; char *p; - if (!ISSET(((BTREE *)t), B_NEEDSWAP)) + if (!F_ISSET(((BTREE *)t), B_NEEDSWAP)) return; if (pg == P_META) { mswap(pp); @@ -212,16 +212,16 @@ mswap(pg) char *p; p = (char *)pg; - P_32_SWAP(p); /* m_magic */ + P_32_SWAP(p); /* magic */ p += sizeof(u_int32_t); - P_32_SWAP(p); /* m_version */ + P_32_SWAP(p); /* version */ p += sizeof(u_int32_t); - P_32_SWAP(p); /* m_psize */ + P_32_SWAP(p); /* psize */ p += sizeof(u_int32_t); - P_32_SWAP(p); /* m_free */ + P_32_SWAP(p); /* free */ p += sizeof(u_int32_t); - P_32_SWAP(p); /* m_nrecs */ + P_32_SWAP(p); /* nrecs */ p += sizeof(u_int32_t); - P_32_SWAP(p); /* m_flags */ + P_32_SWAP(p); /* flags */ p += sizeof(u_int32_t); } diff --git a/lib/libc/db/btree/bt_debug.c b/lib/libc/db/btree/bt_debug.c index fb967122aaa..7b80328b952 100644 --- a/lib/libc/db/btree/bt_debug.c +++ b/lib/libc/db/btree/bt_debug.c @@ -1,4 +1,4 @@ -/* $NetBSD: bt_debug.c,v 1.5 1995/02/27 13:20:12 cgd Exp $ */ +/* $NetBSD: bt_debug.c,v 1.6 1996/05/03 21:50:41 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_debug.c 8.3 (Berkeley) 5/31/94"; +static char sccsid[] = "@(#)bt_debug.c 8.5 (Berkeley) 8/17/94"; #else -static char rcsid[] = "$NetBSD: bt_debug.c,v 1.5 1995/02/27 13:20:12 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_debug.c,v 1.6 1996/05/03 21:50:41 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -71,24 +71,22 @@ __bt_dump(dbp) t = dbp->internal; (void)fprintf(stderr, "%s: pgsz %d", - ISSET(t, B_INMEM) ? "memory" : "disk", t->bt_psize); - if (ISSET(t, R_RECNO)) + F_ISSET(t, B_INMEM) ? "memory" : "disk", t->bt_psize); + if (F_ISSET(t, R_RECNO)) (void)fprintf(stderr, " keys %lu", t->bt_nrecs); #undef X #define X(flag, name) \ - if (ISSET(t, flag)) { \ + if (F_ISSET(t, flag)) { \ (void)fprintf(stderr, "%s%s", sep, name); \ sep = ", "; \ } - if (t->bt_flags) { + if (t->flags != 0) { sep = " flags ("; - X(B_DELCRSR, "DELCRSR"); X(R_FIXLEN, "FIXLEN"); X(B_INMEM, "INMEM"); X(B_NODUPS, "NODUPS"); X(B_RDONLY, "RDONLY"); X(R_RECNO, "RECNO"); - X(B_SEQINIT, "SEQINIT"); X(B_METADIRTY,"METADIRTY"); (void)fprintf(stderr, ")\n"); } @@ -114,19 +112,19 @@ __bt_dmpage(h) char *sep; m = (BTMETA *)h; - (void)fprintf(stderr, "magic %lx\n", m->m_magic); - (void)fprintf(stderr, "version %lu\n", m->m_version); - (void)fprintf(stderr, "psize %lu\n", m->m_psize); - (void)fprintf(stderr, "free %lu\n", m->m_free); - (void)fprintf(stderr, "nrecs %lu\n", m->m_nrecs); - (void)fprintf(stderr, "flags %lu", m->m_flags); + (void)fprintf(stderr, "magic %lx\n", m->magic); + (void)fprintf(stderr, "version %lu\n", m->version); + (void)fprintf(stderr, "psize %lu\n", m->psize); + (void)fprintf(stderr, "free %lu\n", m->free); + (void)fprintf(stderr, "nrecs %lu\n", m->nrecs); + (void)fprintf(stderr, "flags %lu", m->flags); #undef X #define X(flag, name) \ - if (m->m_flags & flag) { \ + if (m->flags & flag) { \ (void)fprintf(stderr, "%s%s", sep, name); \ sep = ", "; \ } - if (m->m_flags) { + if (m->flags) { sep = " ("; X(B_NODUPS, "NODUPS"); X(R_RECNO, "RECNO"); @@ -198,7 +196,7 @@ __bt_dpage(h) h->lower, h->upper, top); for (cur = 0; cur < top; cur++) { (void)fprintf(stderr, "\t[%03d] %4d ", cur, h->linp[cur]); - switch(h->flags & P_TYPE) { + switch (h->flags & P_TYPE) { case P_BINTERNAL: bi = GETBINTERNAL(h, cur); (void)fprintf(stderr, @@ -273,7 +271,7 @@ __bt_stat(dbp) pcont = pinternal = pleaf = 0; nkeys = ifree = lfree = 0; for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) { - switch(h->flags & P_TYPE) { + switch (h->flags & P_TYPE) { case P_BINTERNAL: case P_RINTERNAL: ++pinternal; @@ -301,7 +299,7 @@ __bt_stat(dbp) (void)mpool_put(t->bt_mp, h, 0); break; } - i = ISSET(t, R_RECNO) ? + i = F_ISSET(t, R_RECNO) ? GETRINTERNAL(h, 0)->pgno : GETBINTERNAL(h, 0)->pgno; (void)mpool_put(t->bt_mp, h, 0); @@ -309,7 +307,7 @@ __bt_stat(dbp) (void)fprintf(stderr, "%d level%s with %ld keys", levels, levels == 1 ? "" : "s", nkeys); - if (ISSET(t, R_RECNO)) + if (F_ISSET(t, R_RECNO)) (void)fprintf(stderr, " (%ld header count)", t->bt_nrecs); (void)fprintf(stderr, "\n%lu pages (leaf %ld, internal %ld, overflow %ld)\n", diff --git a/lib/libc/db/btree/bt_delete.c b/lib/libc/db/btree/bt_delete.c index e5ced2bc5c9..32efd2529fb 100644 --- a/lib/libc/db/btree/bt_delete.c +++ b/lib/libc/db/btree/bt_delete.c @@ -1,4 +1,4 @@ -/* $NetBSD: bt_delete.c,v 1.6 1995/02/27 13:20:16 cgd Exp $ */ +/* $NetBSD: bt_delete.c,v 1.7 1996/05/03 21:50:44 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_delete.c 8.4 (Berkeley) 5/31/94"; +static char sccsid[] = "@(#)bt_delete.c 8.13 (Berkeley) 7/28/94"; #else -static char rcsid[] = "$NetBSD: bt_delete.c,v 1.6 1995/02/27 13:20:16 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_delete.c,v 1.7 1996/05/03 21:50:44 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -53,18 +53,17 @@ static char rcsid[] = "$NetBSD: bt_delete.c,v 1.6 1995/02/27 13:20:16 cgd Exp $" #include #include "btree.h" -static int bt_bdelete __P((BTREE *, const DBT *)); +static int __bt_bdelete __P((BTREE *, const DBT *)); +static int __bt_curdel __P((BTREE *, const DBT *, PAGE *, u_int)); +static int __bt_pdelete __P((BTREE *, PAGE *)); +static int __bt_relink __P((BTREE *, PAGE *)); +static int __bt_stkacq __P((BTREE *, PAGE **, CURSOR *)); /* - * __BT_DELETE -- Delete the item(s) referenced by a key. + * __bt_delete + * Delete the item(s) referenced by a key. * - * Parameters: - * dbp: pointer to access method - * key: key to delete - * flags: R_CURSOR if deleting what the cursor references - * - * Returns: - * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. + * Return RET_SPECIAL if the key is not found. */ int __bt_delete(dbp, key, flags) @@ -73,6 +72,8 @@ __bt_delete(dbp, key, flags) u_int flags; { BTREE *t; + CURSOR *c; + PAGE *h; int status; t = dbp->internal; @@ -83,242 +84,433 @@ __bt_delete(dbp, key, flags) t->bt_pinned = NULL; } - if (ISSET(t, B_RDONLY)) { + /* Check for change to a read-only tree. */ + if (F_ISSET(t, B_RDONLY)) { errno = EPERM; return (RET_ERROR); } - switch(flags) { + switch (flags) { case 0: - status = bt_bdelete(t, key); + status = __bt_bdelete(t, key); break; case R_CURSOR: /* - * If flags is R_CURSOR, delete the cursor; must already have - * started a scan and not have already deleted the record. For - * the delete cursor bit to have been set requires that the - * scan be initialized, so no reason to check. + * If flags is R_CURSOR, delete the cursor. Must already + * have started a scan and not have already deleted it. */ - if (!ISSET(t, B_SEQINIT)) - goto einval; - status = ISSET(t, B_DELCRSR) ? - RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor); - break; + c = &t->bt_cursor; + if (F_ISSET(c, CURS_INIT)) { + if (F_ISSET(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE)) + return (RET_SPECIAL); + if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) + return (RET_ERROR); + + /* + * If the page is about to be emptied, we'll need to + * delete it, which means we have to acquire a stack. + */ + if (NEXTINDEX(h) == 1) + if (__bt_stkacq(t, &h, &t->bt_cursor)) + return (RET_ERROR); + + status = __bt_dleaf(t, NULL, h, c->pg.index); + + if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) { + if (__bt_pdelete(t, h)) + return (RET_ERROR); + } else + mpool_put(t->bt_mp, + h, status == RET_SUCCESS ? MPOOL_DIRTY : 0); + break; + } + /* FALLTHROUGH */ default: -einval: errno = EINVAL; + errno = EINVAL; return (RET_ERROR); } if (status == RET_SUCCESS) - SET(t, B_MODIFIED); + F_SET(t, B_MODIFIED); return (status); } /* - * BT_BDELETE -- Delete all key/data pairs matching the specified key. + * __bt_stkacq -- + * Acquire a stack so we can delete a cursor entry. * * Parameters: - * tree: tree + * t: tree + * hp: pointer to current, pinned PAGE pointer + * c: pointer to the cursor + * + * Returns: + * 0 on success, 1 on failure + */ +static int +__bt_stkacq(t, hp, c) + BTREE *t; + PAGE **hp; + CURSOR *c; +{ + BINTERNAL *bi; + EPG *e; + EPGNO *parent; + PAGE *h; + indx_t index; + pgno_t pgno; + recno_t nextpg, prevpg; + int exact, level; + + /* + * Find the first occurrence of the key in the tree. Toss the + * currently locked page so we don't hit an already-locked page. + */ + h = *hp; + mpool_put(t->bt_mp, h, 0); + if ((e = __bt_search(t, &c->key, &exact)) == NULL) + return (1); + h = e->page; + + /* See if we got it in one shot. */ + if (h->pgno == c->pg.pgno) + goto ret; + + /* + * Move right, looking for the page. At each move we have to move + * up the stack until we don't have to move to the next page. If + * we have to change pages at an internal level, we have to fix the + * stack back up. + */ + while (h->pgno != c->pg.pgno) { + if ((nextpg = h->nextpg) == P_INVALID) + break; + mpool_put(t->bt_mp, h, 0); + + /* Move up the stack. */ + for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { + /* Get the parent page. */ + if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) + return (1); + + /* Move to the next index. */ + if (parent->index != NEXTINDEX(h) - 1) { + index = parent->index + 1; + BT_PUSH(t, h->pgno, index); + break; + } + mpool_put(t->bt_mp, h, 0); + } + + /* Restore the stack. */ + while (level--) { + /* Push the next level down onto the stack. */ + bi = GETBINTERNAL(h, index); + pgno = bi->pgno; + BT_PUSH(t, pgno, 0); + + /* Lose the currently pinned page. */ + mpool_put(t->bt_mp, h, 0); + + /* Get the next level down. */ + if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) + return (1); + index = 0; + } + mpool_put(t->bt_mp, h, 0); + if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL) + return (1); + } + + if (h->pgno == c->pg.pgno) + goto ret; + + /* Reacquire the original stack. */ + mpool_put(t->bt_mp, h, 0); + if ((e = __bt_search(t, &c->key, &exact)) == NULL) + return (1); + h = e->page; + + /* + * Move left, looking for the page. At each move we have to move + * up the stack until we don't have to change pages to move to the + * next page. If we have to change pages at an internal level, we + * have to fix the stack back up. + */ + while (h->pgno != c->pg.pgno) { + if ((prevpg = h->prevpg) == P_INVALID) + break; + mpool_put(t->bt_mp, h, 0); + + /* Move up the stack. */ + for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { + /* Get the parent page. */ + if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) + return (1); + + /* Move to the next index. */ + if (parent->index != 0) { + index = parent->index - 1; + BT_PUSH(t, h->pgno, index); + break; + } + mpool_put(t->bt_mp, h, 0); + } + + /* Restore the stack. */ + while (level--) { + /* Push the next level down onto the stack. */ + bi = GETBINTERNAL(h, index); + pgno = bi->pgno; + + /* Lose the currently pinned page. */ + mpool_put(t->bt_mp, h, 0); + + /* Get the next level down. */ + if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) + return (1); + + index = NEXTINDEX(h) - 1; + BT_PUSH(t, pgno, index); + } + mpool_put(t->bt_mp, h, 0); + if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL) + return (1); + } + + +ret: mpool_put(t->bt_mp, h, 0); + return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL); +} + +/* + * __bt_bdelete -- + * Delete all key/data pairs matching the specified key. + * + * Parameters: + * t: tree * key: key to delete * * Returns: * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. */ static int -bt_bdelete(t, key) +__bt_bdelete(t, key) BTREE *t; const DBT *key; { - EPG *e, save; + EPG *e; PAGE *h; - pgno_t cpgno, pg; - indx_t cindex; - int deleted, dirty1, dirty2, exact; + int deleted, exact, redo; + + deleted = 0; /* Find any matching record; __bt_search pins the page. */ - if ((e = __bt_search(t, key, &exact)) == NULL) - return (RET_ERROR); +loop: if ((e = __bt_search(t, key, &exact)) == NULL) + return (deleted ? RET_SUCCESS : RET_ERROR); if (!exact) { mpool_put(t->bt_mp, e->page, 0); - return (RET_SPECIAL); + return (deleted ? RET_SUCCESS : RET_SPECIAL); } /* - * Delete forward, then delete backward, from the found key. The - * ordering is so that the deletions don't mess up the page refs. - * The first loop deletes the key from the original page, the second - * unpins the original page. In the first loop, dirty1 is set if - * the original page is modified, and dirty2 is set if any subsequent - * pages are modified. In the second loop, dirty1 starts off set if - * the original page has been modified, and is set if any subsequent - * pages are modified. - * - * If find the key referenced by the cursor, don't delete it, just - * flag it for future deletion. The cursor page number is P_INVALID - * unless the sequential scan is initialized, so no reason to check. - * A special case is when the already deleted cursor record was the - * only record found. If so, then the delete opertion fails as no - * records were deleted. - * - * Cycle in place in the current page until the current record doesn't - * match the key or the page is empty. If the latter, walk forward, - * skipping empty pages and repeating until a record doesn't match - * the key or the end of the tree is reached. + * Delete forward, then delete backward, from the found key. If + * there are duplicates and we reach either side of the page, do + * the key search again, so that we get them all. */ - cpgno = t->bt_bcursor.pgno; - cindex = t->bt_bcursor.index; - save = *e; - dirty1 = 0; - for (h = e->page, deleted = 0;;) { - dirty2 = 0; - do { - if (h->pgno == cpgno && e->index == cindex) { - if (!ISSET(t, B_DELCRSR)) { - SET(t, B_DELCRSR); - deleted = 1; - } - ++e->index; - } else { - if (__bt_dleaf(t, h, e->index)) { - if (h->pgno != save.page->pgno) - mpool_put(t->bt_mp, h, dirty2); - mpool_put(t->bt_mp, save.page, dirty1); + redo = 0; + h = e->page; + do { + if (__bt_dleaf(t, key, h, e->index)) { + mpool_put(t->bt_mp, h, 0); + return (RET_ERROR); + } + if (F_ISSET(t, B_NODUPS)) { + if (NEXTINDEX(h) == 0) { + if (__bt_pdelete(t, h)) return (RET_ERROR); - } - if (h->pgno == save.page->pgno) - dirty1 = MPOOL_DIRTY; - else - dirty2 = MPOOL_DIRTY; - deleted = 1; - } - } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); - - /* - * Quit if didn't find a match, no next page, or first key on - * the next page doesn't match. Don't unpin the original page - * unless an error occurs. - */ - if (e->index < NEXTINDEX(h)) - break; - for (;;) { - if ((pg = h->nextpg) == P_INVALID) - goto done1; - if (h->pgno != save.page->pgno) - mpool_put(t->bt_mp, h, dirty2); - if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) { - mpool_put(t->bt_mp, save.page, dirty1); - return (RET_ERROR); - } - if (NEXTINDEX(h) != 0) { - e->page = h; - e->index = 0; - break; - } + } else + mpool_put(t->bt_mp, h, MPOOL_DIRTY); + return (RET_SUCCESS); } + deleted = 1; + } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); + /* Check for right-hand edge of the page. */ + if (e->index == NEXTINDEX(h)) + redo = 1; + + /* Delete from the key to the beginning of the page. */ + while (e->index-- > 0) { if (__bt_cmp(t, key, e) != 0) break; + if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) { + mpool_put(t->bt_mp, h, 0); + return (RET_ERROR); + } + if (e->index == 0) + redo = 1; } - /* - * Reach here with the original page and the last page referenced - * pinned (they may be the same). Release it if not the original. - */ -done1: if (h->pgno != save.page->pgno) - mpool_put(t->bt_mp, h, dirty2); + /* Check for an empty page. */ + if (NEXTINDEX(h) == 0) { + if (__bt_pdelete(t, h)) + return (RET_ERROR); + goto loop; + } + + /* Put the page. */ + mpool_put(t->bt_mp, h, MPOOL_DIRTY); + + if (redo) + goto loop; + return (RET_SUCCESS); +} + +/* + * __bt_pdelete -- + * Delete a single page from the tree. + * + * Parameters: + * t: tree + * h: leaf page + * + * Returns: + * RET_SUCCESS, RET_ERROR. + * + * Side-effects: + * mpool_put's the page + */ +static int +__bt_pdelete(t, h) + BTREE *t; + PAGE *h; +{ + BINTERNAL *bi; + PAGE *pg; + EPGNO *parent; + indx_t cnt, index, *ip, offset; + u_int32_t nksize; + char *from; /* - * Walk backwards from the record previous to the record returned by - * __bt_search, skipping empty pages, until a record doesn't match - * the key or reach the beginning of the tree. + * Walk the parent page stack -- a LIFO stack of the pages that were + * traversed when we searched for the page where the delete occurred. + * Each stack entry is a page number and a page index offset. The + * offset is for the page traversed on the search. We've just deleted + * a page, so we have to delete the key from the parent page. + * + * If the delete from the parent page makes it empty, this process may + * continue all the way up the tree. We stop if we reach the root page + * (which is never deleted, it's just not worth the effort) or if the + * delete does not empty the page. */ - *e = save; - for (;;) { - if (e->index) - --e->index; - for (h = e->page; e->index; --e->index) { - if (__bt_cmp(t, key, e) != 0) - goto done2; - if (h->pgno == cpgno && e->index == cindex) { - if (!ISSET(t, B_DELCRSR)) { - SET(t, B_DELCRSR); - deleted = 1; - } + while ((parent = BT_POP(t)) != NULL) { + /* Get the parent page. */ + if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) + return (RET_ERROR); + + index = parent->index; + bi = GETBINTERNAL(pg, index); + + /* Free any overflow pages. */ + if (bi->flags & P_BIGKEY && + __ovfl_delete(t, bi->bytes) == RET_ERROR) { + mpool_put(t->bt_mp, pg, 0); + return (RET_ERROR); + } + + /* + * Free the parent if it has only the one key and it's not the + * root page. If it's the rootpage, turn it back into an empty + * leaf page. + */ + if (NEXTINDEX(pg) == 1) + if (pg->pgno == P_ROOT) { + pg->lower = BTDATAOFF; + pg->upper = t->bt_psize; + pg->flags = P_BLEAF; } else { - if (__bt_dleaf(t, h, e->index) == RET_ERROR) { - mpool_put(t->bt_mp, h, dirty1); + if (__bt_relink(t, pg) || __bt_free(t, pg)) return (RET_ERROR); - } - if (h->pgno == save.page->pgno) - dirty1 = MPOOL_DIRTY; - deleted = 1; + continue; } + else { + /* Pack remaining key items at the end of the page. */ + nksize = NBINTERNAL(bi->ksize); + from = (char *)pg + pg->upper; + memmove(from + nksize, from, (char *)bi - from); + pg->upper += nksize; + + /* Adjust indices' offsets, shift the indices down. */ + offset = pg->linp[index]; + for (cnt = index, ip = &pg->linp[0]; cnt--; ++ip) + if (ip[0] < offset) + ip[0] += nksize; + for (cnt = NEXTINDEX(pg) - index; --cnt; ++ip) + ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1]; + pg->lower -= sizeof(indx_t); } - if ((pg = h->prevpg) == P_INVALID) - goto done2; - mpool_put(t->bt_mp, h, dirty1); - dirty1 = 0; - if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL) - return (RET_ERROR); - e->index = NEXTINDEX(e->page); + mpool_put(t->bt_mp, pg, MPOOL_DIRTY); + break; } - /* - * Reach here with the last page that was looked at pinned. Release - * it. - */ -done2: mpool_put(t->bt_mp, h, dirty1); - return (deleted ? RET_SUCCESS : RET_SPECIAL); + /* Free the leaf page, as long as it wasn't the root. */ + if (h->pgno == P_ROOT) { + mpool_put(t->bt_mp, h, MPOOL_DIRTY); + return (RET_SUCCESS); + } + return (__bt_relink(t, h) || __bt_free(t, h)); } /* - * __BT_DLEAF -- Delete a single record from a leaf page. + * __bt_dleaf -- + * Delete a single record from a leaf page. * * Parameters: * t: tree - * index: index on current page to delete + * key: referenced key + * h: page + * index: index on page to delete * * Returns: * RET_SUCCESS, RET_ERROR. */ int -__bt_dleaf(t, h, index) +__bt_dleaf(t, key, h, index) BTREE *t; + const DBT *key; PAGE *h; - indx_t index; + u_int index; { - register BLEAF *bl; - register indx_t cnt, *ip, offset; - register u_int32_t nbytes; - char *from; + BLEAF *bl; + indx_t cnt, *ip, offset; + u_int32_t nbytes; void *to; + char *from; - /* - * Delete a record from a btree leaf page. Internal records are never - * deleted from internal pages, regardless of the records that caused - * them to be added being deleted. Pages made empty by deletion are - * not reclaimed. They are, however, made available for reuse. - * - * Pack the remaining entries at the end of the page, shift the indices - * down, overwriting the deleted record and its index. If the record - * uses overflow pages, make them available for reuse. - */ + /* If this record is referenced by the cursor, delete the cursor. */ + if (F_ISSET(&t->bt_cursor, CURS_INIT) && + !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && + t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == index && + __bt_curdel(t, key, h, index)) + return (RET_ERROR); + + /* If the entry uses overflow pages, make them available for reuse. */ to = bl = GETBLEAF(h, index); if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR) return (RET_ERROR); if (bl->flags & P_BIGDATA && __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR) return (RET_ERROR); - nbytes = NBLEAF(bl); - /* - * Compress the key/data pairs. Compress and adjust the [BR]LEAF - * offsets. Reset the headers. - */ + /* Pack the remaining key/data items at the end of the page. */ + nbytes = NBLEAF(bl); from = (char *)h + h->upper; memmove(from + nbytes, from, (char *)to - from); h->upper += nbytes; + /* Adjust the indices' offsets, shift the indices down. */ offset = h->linp[index]; for (cnt = index, ip = &h->linp[0]; cnt--; ++ip) if (ip[0] < offset) @@ -326,5 +518,146 @@ __bt_dleaf(t, h, index) for (cnt = NEXTINDEX(h) - index; --cnt; ++ip) ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; h->lower -= sizeof(indx_t); + + /* If the cursor is on this page, adjust it as necessary. */ + if (F_ISSET(&t->bt_cursor, CURS_INIT) && + !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && + t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > index) + --t->bt_cursor.pg.index; + return (RET_SUCCESS); } + +/* + * __bt_curdel -- + * Delete the cursor. + * + * Parameters: + * t: tree + * key: referenced key (or NULL) + * h: page + * index: index on page to delete + * + * Returns: + * RET_SUCCESS, RET_ERROR. + */ +static int +__bt_curdel(t, key, h, index) + BTREE *t; + const DBT *key; + PAGE *h; + u_int index; +{ + CURSOR *c; + EPG e; + PAGE *pg; + int curcopy, status; + + /* + * If there are duplicates, move forward or backward to one. + * Otherwise, copy the key into the cursor area. + */ + c = &t->bt_cursor; + F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE); + + curcopy = 0; + if (!F_ISSET(t, B_NODUPS)) { + /* + * We're going to have to do comparisons. If we weren't + * provided a copy of the key, i.e. the user is deleting + * the current cursor position, get one. + */ + if (key == NULL) { + e.page = h; + e.index = index; + if ((status = __bt_ret(t, &e, + &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS) + return (status); + curcopy = 1; + key = &c->key; + } + /* Check previous key, if not at the beginning of the page. */ + if (index > 0) { + e.page = h; + e.index = index - 1; + if (__bt_cmp(t, key, &e) == 0) { + F_SET(c, CURS_BEFORE); + goto dup2; + } + } + /* Check next key, if not at the end of the page. */ + if (index < NEXTINDEX(h) - 1) { + e.page = h; + e.index = index + 1; + if (__bt_cmp(t, key, &e) == 0) { + F_SET(c, CURS_AFTER); + goto dup2; + } + } + /* Check previous key if at the beginning of the page. */ + if (index == 0 && h->prevpg != P_INVALID) { + if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) + return (RET_ERROR); + e.page = pg; + e.index = NEXTINDEX(pg) - 1; + if (__bt_cmp(t, key, &e) == 0) { + F_SET(c, CURS_BEFORE); + goto dup1; + } + mpool_put(t->bt_mp, pg, 0); + } + /* Check next key if at the end of the page. */ + if (index == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) { + if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) + return (RET_ERROR); + e.page = pg; + e.index = 0; + if (__bt_cmp(t, key, &e) == 0) { + F_SET(c, CURS_AFTER); +dup1: mpool_put(t->bt_mp, pg, 0); +dup2: c->pg.pgno = e.page->pgno; + c->pg.index = e.index; + return (RET_SUCCESS); + } + mpool_put(t->bt_mp, pg, 0); + } + } + e.page = h; + e.index = index; + if (curcopy || (status = + __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) { + F_SET(c, CURS_ACQUIRE); + return (RET_SUCCESS); + } + return (status); +} + +/* + * __bt_relink -- + * Link around a deleted page. + * + * Parameters: + * t: tree + * h: page to be deleted + */ +static int +__bt_relink(t, h) + BTREE *t; + PAGE *h; +{ + PAGE *pg; + + if (h->nextpg != P_INVALID) { + if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) + return (RET_ERROR); + pg->prevpg = h->prevpg; + mpool_put(t->bt_mp, pg, MPOOL_DIRTY); + } + if (h->prevpg != P_INVALID) { + if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) + return (RET_ERROR); + pg->nextpg = h->nextpg; + mpool_put(t->bt_mp, pg, MPOOL_DIRTY); + } + return (0); +} diff --git a/lib/libc/db/btree/bt_get.c b/lib/libc/db/btree/bt_get.c index 2adc73feb7a..18e3a37b6c0 100644 --- a/lib/libc/db/btree/bt_get.c +++ b/lib/libc/db/btree/bt_get.c @@ -1,7 +1,7 @@ -/* $NetBSD: bt_get.c,v 1.6 1995/02/27 13:20:22 cgd Exp $ */ +/* $NetBSD: bt_get.c,v 1.7 1996/05/03 21:50:45 cgd Exp $ */ /*- - * Copyright (c) 1990, 1993 + * Copyright (c) 1990, 1993, 1994 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_get.c 8.2 (Berkeley) 9/7/93"; +static char sccsid[] = "@(#)bt_get.c 8.6 (Berkeley) 7/20/94"; #else -static char rcsid[] = "$NetBSD: bt_get.c,v 1.6 1995/02/27 13:20:22 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_get.c,v 1.7 1996/05/03 21:50:45 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -97,148 +97,15 @@ __bt_get(dbp, key, data, flags) return (RET_SPECIAL); } - /* - * A special case is if we found the record but it's flagged for - * deletion. In this case, we want to find another record with the - * same key, if it exists. Rather than look around the tree we call - * __bt_first and have it redo the search, as __bt_first will not - * return keys marked for deletion. Slow, but should never happen. - */ - if (ISSET(t, B_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno && - e->index == t->bt_bcursor.index) { - mpool_put(t->bt_mp, e->page, 0); - if ((e = __bt_first(t, key, &exact)) == NULL) - return (RET_ERROR); - if (!exact) - return (RET_SPECIAL); - } + status = __bt_ret(t, e, NULL, NULL, data, &t->bt_rdata, 0); - status = __bt_ret(t, e, NULL, data); /* * If the user is doing concurrent access, we copied the * key/data, toss the page. */ - if (ISSET(t, B_DB_LOCK)) + if (F_ISSET(t, B_DB_LOCK)) mpool_put(t->bt_mp, e->page, 0); else t->bt_pinned = e->page; return (status); } - -/* - * __BT_FIRST -- Find the first entry. - * - * Parameters: - * t: the tree - * key: the key - * - * Returns: - * The first entry in the tree greater than or equal to key. - */ -EPG * -__bt_first(t, key, exactp) - BTREE *t; - const DBT *key; - int *exactp; -{ - register PAGE *h; - register EPG *e; - EPG save; - pgno_t cpgno, pg; - indx_t cindex; - int found; - - /* - * Find any matching record; __bt_search pins the page. Only exact - * matches are tricky, otherwise just return the location of the key - * if it were to be inserted into the tree. - */ - if ((e = __bt_search(t, key, exactp)) == NULL) - return (NULL); - if (!*exactp) - return (e); - - if (ISSET(t, B_DELCRSR)) { - cpgno = t->bt_bcursor.pgno; - cindex = t->bt_bcursor.index; - } else { - cpgno = P_INVALID; - cindex = 0; /* GCC thinks it's uninitialized. */ - } - - /* - * Walk backwards, skipping empty pages, as long as the entry matches - * and there are keys left in the tree. Save a copy of each match in - * case we go too far. A special case is that we don't return a match - * on records that the cursor references that have already been flagged - * for deletion. - */ - save = *e; - h = e->page; - found = 0; - do { - if (cpgno != h->pgno || cindex != e->index) { - if (save.page->pgno != e->page->pgno) { - mpool_put(t->bt_mp, save.page, 0); - save = *e; - } else - save.index = e->index; - found = 1; - } - /* - * Make a special effort not to unpin the page the last (or - * original) match was on, but also make sure it's unpinned - * if an error occurs. - */ - while (e->index == 0) { - if (h->prevpg == P_INVALID) - goto done1; - if (h->pgno != save.page->pgno) - mpool_put(t->bt_mp, h, 0); - if ((h = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) { - if (h->pgno == save.page->pgno) - mpool_put(t->bt_mp, save.page, 0); - return (NULL); - } - e->page = h; - e->index = NEXTINDEX(h); - } - --e->index; - } while (__bt_cmp(t, key, e) == 0); - - /* - * Reach here with the last page that was looked at pinned, which may - * or may not be the same as the last (or original) match page. If - * it's not useful, release it. - */ -done1: if (h->pgno != save.page->pgno) - mpool_put(t->bt_mp, h, 0); - - /* - * If still haven't found a record, the only possibility left is the - * next one. Move forward one slot, skipping empty pages and check. - */ - if (!found) { - h = save.page; - if (++save.index == NEXTINDEX(h)) { - do { - pg = h->nextpg; - mpool_put(t->bt_mp, h, 0); - if (pg == P_INVALID) { - *exactp = 0; - return (e); - } - if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) - return (NULL); - } while ((save.index = NEXTINDEX(h)) == 0); - save.page = h; - } - if (__bt_cmp(t, key, &save) != 0) { - *exactp = 0; - return (e); - } - } - *e = save; - *exactp = 1; - return (e); -} diff --git a/lib/libc/db/btree/bt_open.c b/lib/libc/db/btree/bt_open.c index 63162702051..8339edea618 100644 --- a/lib/libc/db/btree/bt_open.c +++ b/lib/libc/db/btree/bt_open.c @@ -1,4 +1,4 @@ -/* $NetBSD: bt_open.c,v 1.7 1995/02/27 13:20:27 cgd Exp $ */ +/* $NetBSD: bt_open.c,v 1.8 1996/05/03 21:50:46 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_open.c 8.7 (Berkeley) 6/16/94"; +static char sccsid[] = "@(#)bt_open.c 8.10 (Berkeley) 8/17/94"; #else -static char rcsid[] = "$NetBSD: bt_open.c,v 1.7 1995/02/27 13:20:27 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_open.c,v 1.8 1996/05/03 21:50:46 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -67,6 +67,11 @@ static char rcsid[] = "$NetBSD: bt_open.c,v 1.7 1995/02/27 13:20:27 cgd Exp $"; #include #include "btree.h" +#ifdef DEBUG +#undef MINPSIZE +#define MINPSIZE 128 +#endif + static int byteorder __P((void)); static int nroot __P((BTREE *)); static int tmp __P((void)); @@ -163,7 +168,6 @@ __bt_open(fname, flags, mode, openinfo, dflags) if ((t = (BTREE *)malloc(sizeof(BTREE))) == NULL) goto err; memset(t, 0, sizeof(BTREE)); - t->bt_bcursor.pgno = P_INVALID; t->bt_fd = -1; /* Don't close unopened fd on error. */ t->bt_lorder = b.lorder; t->bt_order = NOT; @@ -173,9 +177,9 @@ __bt_open(fname, flags, mode, openinfo, dflags) if ((t->bt_dbp = dbp = (DB *)malloc(sizeof(DB))) == NULL) goto err; - t->bt_flags = 0; + memset(t->bt_dbp, 0, sizeof(DB)); if (t->bt_lorder != machine_lorder) - SET(t, B_NEEDSWAP); + F_SET(t, B_NEEDSWAP); dbp->type = DB_BTREE; dbp->internal = t; @@ -192,9 +196,9 @@ __bt_open(fname, flags, mode, openinfo, dflags) * open a backing temporary file. Otherwise, it's a disk-based tree. */ if (fname) { - switch(flags & O_ACCMODE) { + switch (flags & O_ACCMODE) { case O_RDONLY: - SET(t, B_RDONLY); + F_SET(t, B_RDONLY); break; case O_RDWR: break; @@ -211,7 +215,7 @@ __bt_open(fname, flags, mode, openinfo, dflags) goto einval; if ((t->bt_fd = tmp()) == -1) goto err; - SET(t, B_INMEM); + F_SET(t, B_INMEM); } if (fcntl(t->bt_fd, F_SETFD, 1) == -1) @@ -233,28 +237,28 @@ __bt_open(fname, flags, mode, openinfo, dflags) * don't bother to return an error, we just clear the NEEDSWAP * bit. */ - if (m.m_magic == BTREEMAGIC) - CLR(t, B_NEEDSWAP); + if (m.magic == BTREEMAGIC) + F_CLR(t, B_NEEDSWAP); else { - SET(t, B_NEEDSWAP); - M_32_SWAP(m.m_magic); - M_32_SWAP(m.m_version); - M_32_SWAP(m.m_psize); - M_32_SWAP(m.m_free); - M_32_SWAP(m.m_nrecs); - M_32_SWAP(m.m_flags); + F_SET(t, B_NEEDSWAP); + M_32_SWAP(m.magic); + M_32_SWAP(m.version); + M_32_SWAP(m.psize); + M_32_SWAP(m.free); + M_32_SWAP(m.nrecs); + M_32_SWAP(m.flags); } - if (m.m_magic != BTREEMAGIC || m.m_version != BTREEVERSION) + if (m.magic != BTREEMAGIC || m.version != BTREEVERSION) goto eftype; - if (m.m_psize < MINPSIZE || m.m_psize > MAX_PAGE_OFFSET + 1 || - m.m_psize & sizeof(indx_t) - 1) + if (m.psize < MINPSIZE || m.psize > MAX_PAGE_OFFSET + 1 || + m.psize & sizeof(indx_t) - 1) goto eftype; - if (m.m_flags & ~SAVEMETA) + if (m.flags & ~SAVEMETA) goto eftype; - b.psize = m.m_psize; - t->bt_flags |= m.m_flags; - t->bt_free = m.m_free; - t->bt_nrecs = m.m_nrecs; + b.psize = m.psize; + F_SET(t, m.flags); + t->bt_free = m.free; + t->bt_nrecs = m.nrecs; } else { /* * Set the page size to the best value for I/O to this file. @@ -270,11 +274,11 @@ __bt_open(fname, flags, mode, openinfo, dflags) /* Set flag if duplicates permitted. */ if (!(b.flags & R_DUP)) - SET(t, B_NODUPS); + F_SET(t, B_NODUPS); t->bt_free = P_INVALID; t->bt_nrecs = 0; - SET(t, B_METADIRTY); + F_SET(t, B_METADIRTY); } t->bt_psize = b.psize; @@ -309,7 +313,7 @@ __bt_open(fname, flags, mode, openinfo, dflags) if ((t->bt_mp = mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL) goto err; - if (!ISSET(t, B_INMEM)) + if (!F_ISSET(t, B_INMEM)) mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t); /* Create a root page if new tree. */ @@ -318,11 +322,11 @@ __bt_open(fname, flags, mode, openinfo, dflags) /* Global flags. */ if (dflags & DB_LOCK) - SET(t, B_DB_LOCK); + F_SET(t, B_DB_LOCK); if (dflags & DB_SHMEM) - SET(t, B_DB_SHMEM); + F_SET(t, B_DB_SHMEM); if (dflags & DB_TXN) - SET(t, B_DB_TXN); + F_SET(t, B_DB_TXN); return (dbp); @@ -438,7 +442,7 @@ __bt_fd(dbp) } /* In-memory database can't have a file descriptor. */ - if (ISSET(t, B_INMEM)) { + if (F_ISSET(t, B_INMEM)) { errno = ENOENT; return (-1); } diff --git a/lib/libc/db/btree/bt_overflow.c b/lib/libc/db/btree/bt_overflow.c index b5c43c60435..fcae9ef013b 100644 --- a/lib/libc/db/btree/bt_overflow.c +++ b/lib/libc/db/btree/bt_overflow.c @@ -1,4 +1,4 @@ -/* $NetBSD: bt_overflow.c,v 1.5 1995/02/27 13:20:33 cgd Exp $ */ +/* $NetBSD: bt_overflow.c,v 1.6 1996/05/03 21:50:48 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_overflow.c 8.4 (Berkeley) 6/20/94"; +static char sccsid[] = "@(#)bt_overflow.c 8.5 (Berkeley) 7/16/94"; #else -static char rcsid[] = "$NetBSD: bt_overflow.c,v 1.5 1995/02/27 13:20:33 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_overflow.c,v 1.6 1996/05/03 21:50:48 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -87,7 +87,7 @@ __ovfl_get(t, p, ssz, buf, bufsz) BTREE *t; void *p; size_t *ssz; - char **buf; + void **buf; size_t *bufsz; { PAGE *h; diff --git a/lib/libc/db/btree/bt_page.c b/lib/libc/db/btree/bt_page.c index d6a44941854..7b977bd0d36 100644 --- a/lib/libc/db/btree/bt_page.c +++ b/lib/libc/db/btree/bt_page.c @@ -1,7 +1,7 @@ -/* $NetBSD: bt_page.c,v 1.5 1995/02/27 13:20:36 cgd Exp $ */ +/* $NetBSD: bt_page.c,v 1.6 1996/05/03 21:50:49 cgd Exp $ */ /*- - * Copyright (c) 1990, 1993 + * Copyright (c) 1990, 1993, 1994 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -35,9 +35,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_page.c 8.2 (Berkeley) 2/21/94"; +static char sccsid[] = "@(#)bt_page.c 8.3 (Berkeley) 7/14/94"; #else -static char rcsid[] = "$NetBSD: bt_page.c,v 1.5 1995/02/27 13:20:36 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_page.c,v 1.6 1996/05/03 21:50:49 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -49,7 +49,8 @@ static char rcsid[] = "$NetBSD: bt_page.c,v 1.5 1995/02/27 13:20:36 cgd Exp $"; #include "btree.h" /* - * __BT_FREE -- Put a page on the freelist. + * __bt_free -- + * Put a page on the freelist. * * Parameters: * t: tree @@ -57,13 +58,16 @@ static char rcsid[] = "$NetBSD: bt_page.c,v 1.5 1995/02/27 13:20:36 cgd Exp $"; * * Returns: * RET_ERROR, RET_SUCCESS + * + * Side-effect: + * mpool_put's the page. */ int __bt_free(t, h) BTREE *t; PAGE *h; { - /* Insert the page at the start of the free list. */ + /* Insert the page at the head of the free list. */ h->prevpg = P_INVALID; h->nextpg = t->bt_free; t->bt_free = h->pgno; @@ -73,7 +77,8 @@ __bt_free(t, h) } /* - * __BT_NEW -- Get a new page, preferably from the freelist. + * __bt_new -- + * Get a new page, preferably from the freelist. * * Parameters: * t: tree @@ -91,9 +96,9 @@ __bt_new(t, npg) if (t->bt_free != P_INVALID && (h = mpool_get(t->bt_mp, t->bt_free, 0)) != NULL) { - *npg = t->bt_free; - t->bt_free = h->nextpg; - return (h); + *npg = t->bt_free; + t->bt_free = h->nextpg; + return (h); } return (mpool_new(t->bt_mp, npg)); } diff --git a/lib/libc/db/btree/bt_put.c b/lib/libc/db/btree/bt_put.c index 9ddc98d8ec1..5d13b062648 100644 --- a/lib/libc/db/btree/bt_put.c +++ b/lib/libc/db/btree/bt_put.c @@ -1,4 +1,4 @@ -/* $NetBSD: bt_put.c,v 1.7 1995/02/27 13:20:40 cgd Exp $ */ +/* $NetBSD: bt_put.c,v 1.8 1996/05/03 21:50:51 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_put.c 8.4 (Berkeley) 5/31/94"; +static char sccsid[] = "@(#)bt_put.c 8.8 (Berkeley) 7/26/94"; #else -static char rcsid[] = "$NetBSD: bt_put.c,v 1.7 1995/02/27 13:20:40 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_put.c,v 1.8 1996/05/03 21:50:51 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -94,33 +94,38 @@ __bt_put(dbp, key, data, flags) t->bt_pinned = NULL; } + /* Check for change to a read-only tree. */ + if (F_ISSET(t, B_RDONLY)) { + errno = EPERM; + return (RET_ERROR); + } + switch (flags) { - case R_CURSOR: - if (!ISSET(t, B_SEQINIT)) - goto einval; - if (ISSET(t, B_DELCRSR)) - goto einval; - break; case 0: case R_NOOVERWRITE: break; + case R_CURSOR: + /* + * If flags is R_CURSOR, put the cursor. Must already + * have started a scan and not have already deleted it. + */ + if (F_ISSET(&t->bt_cursor, CURS_INIT) && + !F_ISSET(&t->bt_cursor, + CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE)) + break; + /* FALLTHROUGH */ default: -einval: errno = EINVAL; - return (RET_ERROR); - } - - if (ISSET(t, B_RDONLY)) { - errno = EPERM; + errno = EINVAL; return (RET_ERROR); } /* - * If the key/data won't fit on a page, store it on indirect pages. - * Only store the key on the overflow page if it's too big after the - * data is on an overflow page. + * If the key/data pair won't fit on a page, store it on overflow + * pages. Only put the key on the overflow page if the pair are + * still too big after moving the data to an overflow page. * * XXX - * If the insert fails later on, these pages aren't recovered. + * If the insert fails later on, the overflow pages aren't recovered. */ dflags = 0; if (key->size + data->size > t->bt_ovflsize) { @@ -152,15 +157,15 @@ storekey: if (__ovfl_put(t, key, &pg) == RET_ERROR) /* Replace the cursor. */ if (flags == R_CURSOR) { - if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL) + if ((h = mpool_get(t->bt_mp, t->bt_cursor.pg.pgno, 0)) == NULL) return (RET_ERROR); - index = t->bt_bcursor.index; + index = t->bt_cursor.pg.index; goto delete; } /* - * Find the key to delete, or, the location at which to insert. Bt_fast - * and __bt_search pin the returned page. + * Find the key to delete, or, the location at which to insert. + * Bt_fast and __bt_search both pin the returned page. */ if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL) if ((e = __bt_search(t, key, &exact)) == NULL) @@ -169,34 +174,26 @@ storekey: if (__ovfl_put(t, key, &pg) == RET_ERROR) index = e->index; /* - * Add the specified key/data pair to the tree. If an identical key - * is already in the tree, and R_NOOVERWRITE is set, an error is - * returned. If R_NOOVERWRITE is not set, the key is either added (if - * duplicates are permitted) or an error is returned. - * - * Pages are split as required. + * Add the key/data pair to the tree. If an identical key is already + * in the tree, and R_NOOVERWRITE is set, an error is returned. If + * R_NOOVERWRITE is not set, the key is either added (if duplicates are + * permitted) or an error is returned. */ switch (flags) { case R_NOOVERWRITE: if (!exact) break; - /* - * One special case is if the cursor references the record and - * it's been flagged for deletion. Then, we delete the record, - * leaving the cursor there -- this means that the inserted - * record will not be seen in a cursor scan. - */ - if (ISSET(t, B_DELCRSR) && t->bt_bcursor.pgno == h->pgno && - t->bt_bcursor.index == index) { - CLR(t, B_DELCRSR); - goto delete; - } mpool_put(t->bt_mp, h, 0); return (RET_SPECIAL); default: - if (!exact || !ISSET(t, B_NODUPS)) + if (!exact || !F_ISSET(t, B_NODUPS)) break; -delete: if (__bt_dleaf(t, h, index) == RET_ERROR) { + /* + * !!! + * Note, the delete may empty the page, so we need to put a + * new entry into the page immediately. + */ +delete: if (__bt_dleaf(t, key, h, index) == RET_ERROR) { mpool_put(t->bt_mp, h, 0); return (RET_ERROR); } @@ -226,6 +223,12 @@ delete: if (__bt_dleaf(t, h, index) == RET_ERROR) { dest = (char *)h + h->upper; WR_BLEAF(dest, key, data, dflags); + /* If the cursor is on this page, adjust it as necessary. */ + if (F_ISSET(&t->bt_cursor, CURS_INIT) && + !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && + t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index >= index) + ++t->bt_cursor.pg.index; + if (t->bt_order == NOT) if (h->nextpg == P_INVALID) { if (index == NEXTINDEX(h) - 1) { @@ -244,11 +247,10 @@ delete: if (__bt_dleaf(t, h, index) == RET_ERROR) { mpool_put(t->bt_mp, h, MPOOL_DIRTY); success: - if (flags == R_SETCURSOR) { - t->bt_bcursor.pgno = e->page->pgno; - t->bt_bcursor.index = e->index; - } - SET(t, B_MODIFIED); + if (flags == R_SETCURSOR) + __bt_setcur(t, e->page->pgno, e->index); + + F_SET(t, B_MODIFIED); return (RET_SUCCESS); } @@ -284,8 +286,8 @@ bt_fast(t, key, data, exactp) t->bt_cur.index = t->bt_last.index; /* - * If won't fit in this page or have too many keys in this page, have - * to search to get split stack. + * If won't fit in this page or have too many keys in this page, + * have to search to get split stack. */ nbytes = NBLEAFDBT(key->size, data->size); if (h->upper - h->lower < nbytes + sizeof(indx_t)) diff --git a/lib/libc/db/btree/bt_search.c b/lib/libc/db/btree/bt_search.c index c98fe7346ea..d0832b9d383 100644 --- a/lib/libc/db/btree/bt_search.c +++ b/lib/libc/db/btree/bt_search.c @@ -1,7 +1,7 @@ -/* $NetBSD: bt_search.c,v 1.7 1995/02/27 13:20:44 cgd Exp $ */ +/* $NetBSD: bt_search.c,v 1.8 1996/05/03 21:50:52 cgd Exp $ */ /*- - * Copyright (c) 1990, 1993 + * Copyright (c) 1990, 1993, 1994 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_search.c 8.6 (Berkeley) 3/15/94"; +static char sccsid[] = "@(#)bt_search.c 8.8 (Berkeley) 7/31/94"; #else -static char rcsid[] = "$NetBSD: bt_search.c,v 1.7 1995/02/27 13:20:44 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_search.c,v 1.8 1996/05/03 21:50:52 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -51,11 +51,12 @@ static char rcsid[] = "$NetBSD: bt_search.c,v 1.7 1995/02/27 13:20:44 cgd Exp $" #include #include "btree.h" -static int bt_snext __P((BTREE *, PAGE *, const DBT *, int *)); -static int bt_sprev __P((BTREE *, PAGE *, const DBT *, int *)); +static int __bt_snext __P((BTREE *, PAGE *, const DBT *, int *)); +static int __bt_sprev __P((BTREE *, PAGE *, const DBT *, int *)); /* - * __BT_SEARCH -- Search a btree for a key. + * __bt_search -- + * Search a btree for a key. * * Parameters: * t: tree to search @@ -101,24 +102,26 @@ __bt_search(t, key, exactp) } /* - * If it's a leaf page, and duplicates aren't allowed, we're - * done. If duplicates are allowed, it's possible that there - * were duplicate keys on duplicate pages, and they were later - * deleted, so we could be on a page with no matches while - * there are matches on other pages. If we're at the start or - * end of a page, check on both sides. + * If it's a leaf page, we're almost done. If no duplicates + * are allowed, or we have an exact match, we're done. Else, + * it's possible that there were matching keys on this page, + * which later deleted, and we're on a page with no matches + * while there are matches on other pages. If at the start or + * end of a page, check the adjacent page. */ if (h->flags & P_BLEAF) { - t->bt_cur.index = base; - *exactp = 0; - if (!ISSET(t, B_NODUPS)) { + if (!F_ISSET(t, B_NODUPS)) { if (base == 0 && - bt_sprev(t, h, key, exactp)) + h->prevpg != P_INVALID && + __bt_sprev(t, h, key, exactp)) return (&t->bt_cur); if (base == NEXTINDEX(h) && - bt_snext(t, h, key, exactp)) + h->nextpg != P_INVALID && + __bt_snext(t, h, key, exactp)) return (&t->bt_cur); } + *exactp = 0; + t->bt_cur.index = base; return (&t->bt_cur); } @@ -131,111 +134,86 @@ __bt_search(t, key, exactp) */ index = base ? base - 1 : base; -next: if (__bt_push(t, h->pgno, index) == RET_ERROR) - return (NULL); +next: BT_PUSH(t, h->pgno, index); pg = GETBINTERNAL(h, index)->pgno; mpool_put(t->bt_mp, h, 0); } } /* - * BT_SNEXT -- Check for an exact match after the key. + * __bt_snext -- + * Check for an exact match after the key. * * Parameters: - * t: tree to search - * h: current page. - * key: key to find + * t: tree + * h: current page + * key: key * exactp: pointer to exact match flag * * Returns: * If an exact match found. */ static int -bt_snext(t, h, key, exactp) +__bt_snext(t, h, key, exactp) BTREE *t; PAGE *h; const DBT *key; int *exactp; { EPG e; - PAGE *tp; - pgno_t pg; - /* Skip until reach the end of the tree or a key. */ - for (pg = h->nextpg; pg != P_INVALID;) { - if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) { - mpool_put(t->bt_mp, h, 0); - return (NULL); - } - if (NEXTINDEX(tp) != 0) - break; - pg = tp->prevpg; - mpool_put(t->bt_mp, tp, 0); - } /* - * The key is either an exact match, or not as good as - * the one we already have. + * Get the next page. The key is either an exact + * match, or not as good as the one we already have. */ - if (pg != P_INVALID) { - e.page = tp; - e.index = NEXTINDEX(tp) - 1; - if (__bt_cmp(t, key, &e) == 0) { - mpool_put(t->bt_mp, h, 0); - t->bt_cur = e; - *exactp = 1; - return (1); - } + if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) + return (0); + e.index = 0; + if (__bt_cmp(t, key, &e) == 0) { + mpool_put(t->bt_mp, h, 0); + t->bt_cur = e; + *exactp = 1; + return (1); } + mpool_put(t->bt_mp, e.page, 0); return (0); } /* - * BT_SPREV -- Check for an exact match before the key. + * __bt_sprev -- + * Check for an exact match before the key. * * Parameters: - * t: tree to search - * h: current page. - * key: key to find + * t: tree + * h: current page + * key: key * exactp: pointer to exact match flag * * Returns: * If an exact match found. */ static int -bt_sprev(t, h, key, exactp) +__bt_sprev(t, h, key, exactp) BTREE *t; PAGE *h; const DBT *key; int *exactp; { EPG e; - PAGE *tp; - pgno_t pg; - /* Skip until reach the beginning of the tree or a key. */ - for (pg = h->prevpg; pg != P_INVALID;) { - if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) { - mpool_put(t->bt_mp, h, 0); - return (NULL); - } - if (NEXTINDEX(tp) != 0) - break; - pg = tp->prevpg; - mpool_put(t->bt_mp, tp, 0); - } /* - * The key is either an exact match, or not as good as - * the one we already have. + * Get the previous page. The key is either an exact + * match, or not as good as the one we already have. */ - if (pg != P_INVALID) { - e.page = tp; - e.index = NEXTINDEX(tp) - 1; - if (__bt_cmp(t, key, &e) == 0) { - mpool_put(t->bt_mp, h, 0); - t->bt_cur = e; - *exactp = 1; - return (1); - } + if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) + return (0); + e.index = NEXTINDEX(e.page) - 1; + if (__bt_cmp(t, key, &e) == 0) { + mpool_put(t->bt_mp, h, 0); + t->bt_cur = e; + *exactp = 1; + return (1); } + mpool_put(t->bt_mp, e.page, 0); return (0); } diff --git a/lib/libc/db/btree/bt_seq.c b/lib/libc/db/btree/bt_seq.c index f029cc3e174..7717593a589 100644 --- a/lib/libc/db/btree/bt_seq.c +++ b/lib/libc/db/btree/bt_seq.c @@ -1,7 +1,7 @@ -/* $NetBSD: bt_seq.c,v 1.6 1995/02/27 13:20:51 cgd Exp $ */ +/* $NetBSD: bt_seq.c,v 1.7 1996/05/03 21:50:54 cgd Exp $ */ /*- - * Copyright (c) 1990, 1993 + * Copyright (c) 1990, 1993, 1994 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_seq.c 8.2 (Berkeley) 9/7/93"; +static char sccsid[] = "@(#)bt_seq.c 8.7 (Berkeley) 7/20/94"; #else -static char rcsid[] = "$NetBSD: bt_seq.c,v 1.6 1995/02/27 13:20:51 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_seq.c,v 1.7 1996/05/03 21:50:54 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -54,24 +54,21 @@ static char rcsid[] = "$NetBSD: bt_seq.c,v 1.6 1995/02/27 13:20:51 cgd Exp $"; #include #include "btree.h" -static int bt_seqadv __P((BTREE *, EPG *, int)); -static int bt_seqset __P((BTREE *, EPG *, DBT *, int)); +static int __bt_first __P((BTREE *, const DBT *, EPG *, int *)); +static int __bt_seqadv __P((BTREE *, EPG *, int)); +static int __bt_seqset __P((BTREE *, EPG *, DBT *, int)); /* * Sequential scan support. * - * The tree can be scanned sequentially, starting from either end of the tree - * or from any specific key. A scan request before any scanning is done is - * initialized as starting from the least node. - * - * Each tree has an EPGNO which has the current position of the cursor. The - * cursor has to survive deletions/insertions in the tree without losing its - * position. This is done by noting deletions without doing them, and then - * doing them when the cursor moves (or the tree is closed). + * The tree can be scanned sequentially, starting from either end of the + * tree or from any specific key. A scan request before any scanning is + * done is initialized as starting from the least node. */ /* - * __BT_SEQ -- Btree sequential scan interface. + * __bt_seq -- + * Btree sequential scan interface. * * Parameters: * dbp: pointer to access method @@ -102,21 +99,21 @@ __bt_seq(dbp, key, data, flags) /* * If scan unitialized as yet, or starting at a specific record, set - * the scan to a specific key. Both bt_seqset and bt_seqadv pin the - * page the cursor references if they're successful. + * the scan to a specific key. Both __bt_seqset and __bt_seqadv pin + * the page the cursor references if they're successful. */ - switch(flags) { + switch (flags) { case R_NEXT: case R_PREV: - if (ISSET(t, B_SEQINIT)) { - status = bt_seqadv(t, &e, flags); + if (F_ISSET(&t->bt_cursor, CURS_INIT)) { + status = __bt_seqadv(t, &e, flags); break; } /* FALLTHROUGH */ - case R_CURSOR: case R_FIRST: case R_LAST: - status = bt_seqset(t, &e, key, flags); + case R_CURSOR: + status = __bt_seqset(t, &e, key, flags); break; default: errno = EINVAL; @@ -124,27 +121,26 @@ __bt_seq(dbp, key, data, flags) } if (status == RET_SUCCESS) { - status = __bt_ret(t, &e, key, data); + __bt_setcur(t, e.page->pgno, e.index); - /* Update the actual cursor. */ - t->bt_bcursor.pgno = e.page->pgno; - t->bt_bcursor.index = e.index; + status = + __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0); /* * If the user is doing concurrent access, we copied the * key/data, toss the page. */ - if (ISSET(t, B_DB_LOCK)) + if (F_ISSET(t, B_DB_LOCK)) mpool_put(t->bt_mp, e.page, 0); else t->bt_pinned = e.page; - SET(t, B_SEQINIT); } return (status); } /* - * BT_SEQSET -- Set the sequential scan to a specific key. + * __bt_seqset -- + * Set the sequential scan to a specific key. * * Parameters: * t: tree @@ -159,87 +155,50 @@ __bt_seq(dbp, key, data, flags) * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. */ static int -bt_seqset(t, ep, key, flags) +__bt_seqset(t, ep, key, flags) BTREE *t; EPG *ep; DBT *key; int flags; { - EPG *e; PAGE *h; pgno_t pg; int exact; /* - * Delete any already deleted record that we've been saving because - * the cursor pointed to it. Since going to a specific key, should - * delete any logically deleted records so they aren't found. - */ - if (ISSET(t, B_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor)) - return (RET_ERROR); - - /* - * Find the first, last or specific key in the tree and point the cursor - * at it. The cursor may not be moved until a new key has been found. + * Find the first, last or specific key in the tree and point the + * cursor at it. The cursor may not be moved until a new key has + * been found. */ - switch(flags) { + switch (flags) { case R_CURSOR: /* Keyed scan. */ /* - * Find the first instance of the key or the smallest key which - * is greater than or equal to the specified key. If run out - * of keys, return RET_SPECIAL. + * Find the first instance of the key or the smallest key + * which is greater than or equal to the specified key. */ if (key->data == NULL || key->size == 0) { errno = EINVAL; return (RET_ERROR); } - e = __bt_first(t, key, &exact); /* Returns pinned page. */ - if (e == NULL) - return (RET_ERROR); - /* - * If at the end of a page, skip any empty pages and find the - * next entry. - */ - if (e->index == NEXTINDEX(e->page)) { - h = e->page; - do { - pg = h->nextpg; - mpool_put(t->bt_mp, h, 0); - if (pg == P_INVALID) - return (RET_SPECIAL); - if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) - return (RET_ERROR); - } while (NEXTINDEX(h) == 0); - e->index = 0; - e->page = h; - } - *ep = *e; - break; + return (__bt_first(t, key, ep, &exact)); case R_FIRST: /* First record. */ case R_NEXT: /* Walk down the left-hand side of the tree. */ for (pg = P_ROOT;;) { if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) return (RET_ERROR); + + /* Check for an empty tree. */ + if (NEXTINDEX(h) == 0) { + mpool_put(t->bt_mp, h, 0); + return (RET_SPECIAL); + } + if (h->flags & (P_BLEAF | P_RLEAF)) break; pg = GETBINTERNAL(h, 0)->pgno; mpool_put(t->bt_mp, h, 0); } - - /* Skip any empty pages. */ - while (NEXTINDEX(h) == 0 && h->nextpg != P_INVALID) { - pg = h->nextpg; - mpool_put(t->bt_mp, h, 0); - if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) - return (RET_ERROR); - } - - if (NEXTINDEX(h) == 0) { - mpool_put(t->bt_mp, h, 0); - return (RET_SPECIAL); - } - ep->page = h; ep->index = 0; break; @@ -249,25 +208,19 @@ bt_seqset(t, ep, key, flags) for (pg = P_ROOT;;) { if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) return (RET_ERROR); + + /* Check for an empty tree. */ + if (NEXTINDEX(h) == 0) { + mpool_put(t->bt_mp, h, 0); + return (RET_SPECIAL); + } + if (h->flags & (P_BLEAF | P_RLEAF)) break; pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno; mpool_put(t->bt_mp, h, 0); } - /* Skip any empty pages. */ - while (NEXTINDEX(h) == 0 && h->prevpg != P_INVALID) { - pg = h->prevpg; - mpool_put(t->bt_mp, h, 0); - if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) - return (RET_ERROR); - } - - if (NEXTINDEX(h) == 0) { - mpool_put(t->bt_mp, h, 0); - return (RET_SPECIAL); - } - ep->page = h; ep->index = NEXTINDEX(h) - 1; break; @@ -276,7 +229,8 @@ bt_seqset(t, ep, key, flags) } /* - * BT_SEQADVANCE -- Advance the sequential scan. + * __bt_seqadvance -- + * Advance the sequential scan. * * Parameters: * t: tree @@ -289,98 +243,224 @@ bt_seqset(t, ep, key, flags) * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. */ static int -bt_seqadv(t, e, flags) +__bt_seqadv(t, ep, flags) BTREE *t; - EPG *e; + EPG *ep; int flags; { - EPGNO *c, delc; + CURSOR *c; PAGE *h; indx_t index; pgno_t pg; + int exact; - /* Save the current cursor if going to delete it. */ - c = &t->bt_bcursor; - if (ISSET(t, B_DELCRSR)) - delc = *c; + /* + * There are a couple of states that we can be in. The cursor has + * been initialized by the time we get here, but that's all we know. + */ + c = &t->bt_cursor; - if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL) + /* + * The cursor was deleted where there weren't any duplicate records, + * so the key was saved. Find out where that key would go in the + * current tree. It doesn't matter if the returned key is an exact + * match or not -- if it's an exact match, the record was added after + * the delete so we can just return it. If not, as long as there's + * a record there, return it. + */ + if (F_ISSET(c, CURS_ACQUIRE)) + return (__bt_first(t, &c->key, ep, &exact)); + + /* Get the page referenced by the cursor. */ + if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) return (RET_ERROR); /* - * Find the next/previous record in the tree and point the cursor at it. - * The cursor may not be moved until a new key has been found. + * Find the next/previous record in the tree and point the cursor at + * it. The cursor may not be moved until a new key has been found. */ - index = c->index; - switch(flags) { + switch (flags) { case R_NEXT: /* Next record. */ + /* + * The cursor was deleted in duplicate records, and moved + * forward to a record that has yet to be returned. Clear + * that flag, and return the record. + */ + if (F_ISSET(c, CURS_AFTER)) + goto usecurrent; + index = c->pg.index; if (++index == NEXTINDEX(h)) { - do { - pg = h->nextpg; - mpool_put(t->bt_mp, h, 0); - if (pg == P_INVALID) - return (RET_SPECIAL); - if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) - return (RET_ERROR); - } while (NEXTINDEX(h) == 0); + pg = h->nextpg; + mpool_put(t->bt_mp, h, 0); + if (pg == P_INVALID) + return (RET_SPECIAL); + if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) + return (RET_ERROR); index = 0; } break; case R_PREV: /* Previous record. */ - if (index-- == 0) { - do { - pg = h->prevpg; - mpool_put(t->bt_mp, h, 0); - if (pg == P_INVALID) - return (RET_SPECIAL); - if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) - return (RET_ERROR); - } while (NEXTINDEX(h) == 0); - index = NEXTINDEX(h) - 1; + /* + * The cursor was deleted in duplicate records, and moved + * backward to a record that has yet to be returned. Clear + * that flag, and return the record. + */ + if (F_ISSET(c, CURS_BEFORE)) { +usecurrent: F_CLR(c, CURS_AFTER | CURS_BEFORE); + ep->page = h; + ep->index = c->pg.index; + return (RET_SUCCESS); } + index = c->pg.index; + if (index == 0) { + pg = h->prevpg; + mpool_put(t->bt_mp, h, 0); + if (pg == P_INVALID) + return (RET_SPECIAL); + if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) + return (RET_ERROR); + index = NEXTINDEX(h) - 1; + } else + --index; break; } - e->page = h; - e->index = index; + ep->page = h; + ep->index = index; + return (RET_SUCCESS); +} + +/* + * __bt_first -- + * Find the first entry. + * + * Parameters: + * t: the tree + * key: the key + * erval: return EPG + * exactp: pointer to exact match flag + * + * Returns: + * The first entry in the tree greater than or equal to key, + * or RET_SPECIAL if no such key exists. + */ +static int +__bt_first(t, key, erval, exactp) + BTREE *t; + const DBT *key; + EPG *erval; + int *exactp; +{ + PAGE *h; + EPG *ep, save; + pgno_t pg; /* - * Delete any already deleted record that we've been saving because the - * cursor pointed to it. This could cause the new index to be shifted - * down by one if the record we're deleting is on the same page and has - * a larger index. + * Find any matching record; __bt_search pins the page. + * + * If it's an exact match and duplicates are possible, walk backwards + * in the tree until we find the first one. Otherwise, make sure it's + * a valid key (__bt_search may return an index just past the end of a + * page) and return it. */ - if (ISSET(t, B_DELCRSR)) { - CLR(t, B_DELCRSR); /* Don't try twice. */ - if (c->pgno == delc.pgno && c->index > delc.index) - --c->index; - if (__bt_crsrdel(t, &delc)) + if ((ep = __bt_search(t, key, exactp)) == NULL) + return (NULL); + if (*exactp) { + if (F_ISSET(t, B_NODUPS)) { + *erval = *ep; + return (RET_SUCCESS); + } + + /* + * Walk backwards, as long as the entry matches and there are + * keys left in the tree. Save a copy of each match in case + * we go too far. + */ + save = *ep; + h = ep->page; + do { + if (save.page->pgno != ep->page->pgno) { + mpool_put(t->bt_mp, save.page, 0); + save = *ep; + } else + save.index = ep->index; + + /* + * Don't unpin the page the last (or original) match + * was on, but make sure it's unpinned if an error + * occurs. + */ + if (ep->index == 0) { + if (h->prevpg == P_INVALID) + break; + if (h->pgno != save.page->pgno) + mpool_put(t->bt_mp, h, 0); + if ((h = mpool_get(t->bt_mp, + h->prevpg, 0)) == NULL) { + if (h->pgno == save.page->pgno) + mpool_put(t->bt_mp, + save.page, 0); + return (RET_ERROR); + } + ep->page = h; + ep->index = NEXTINDEX(h); + } + --ep->index; + } while (__bt_cmp(t, key, ep) == 0); + + /* + * Reach here with the last page that was looked at pinned, + * which may or may not be the same as the last (or original) + * match page. If it's not useful, release it. + */ + if (h->pgno != save.page->pgno) + mpool_put(t->bt_mp, h, 0); + + *erval = save; + return (RET_SUCCESS); + } + + /* If at the end of a page, find the next entry. */ + if (ep->index == NEXTINDEX(ep->page)) { + h = ep->page; + pg = h->nextpg; + mpool_put(t->bt_mp, h, 0); + if (pg == P_INVALID) + return (RET_SPECIAL); + if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) return (RET_ERROR); + ep->index = 0; + ep->page = h; } + *erval = *ep; return (RET_SUCCESS); } /* - * __BT_CRSRDEL -- Delete the record referenced by the cursor. + * __bt_setcur -- + * Set the cursor to an entry in the tree. * * Parameters: - * t: tree - * - * Returns: - * RET_ERROR, RET_SUCCESS + * t: the tree + * pgno: page number + * index: page index */ -int -__bt_crsrdel(t, c) +void +__bt_setcur(t, pgno, index) BTREE *t; - EPGNO *c; + pgno_t pgno; + u_int index; { - PAGE *h; - int status; + /* Lose any already deleted key. */ + if (t->bt_cursor.key.data != NULL) { + free(t->bt_cursor.key.data); + t->bt_cursor.key.size = 0; + t->bt_cursor.key.data = NULL; + } + F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE); - CLR(t, B_DELCRSR); /* Don't try twice. */ - if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL) - return (RET_ERROR); - status = __bt_dleaf(t, h, c->index); - mpool_put(t->bt_mp, h, MPOOL_DIRTY); - return (status); + /* Update the cursor. */ + t->bt_cursor.pg.pgno = pgno; + t->bt_cursor.pg.index = index; + F_SET(&t->bt_cursor, CURS_INIT); } diff --git a/lib/libc/db/btree/bt_split.c b/lib/libc/db/btree/bt_split.c index 22334c1e430..110e3f9dd1d 100644 --- a/lib/libc/db/btree/bt_split.c +++ b/lib/libc/db/btree/bt_split.c @@ -1,4 +1,4 @@ -/* $NetBSD: bt_split.c,v 1.5 1995/02/27 13:20:55 cgd Exp $ */ +/* $NetBSD: bt_split.c,v 1.6 1996/05/03 21:50:56 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_split.c 8.6 (Berkeley) 6/16/94"; +static char sccsid[] = "@(#)bt_split.c 8.9 (Berkeley) 7/26/94"; #else -static char rcsid[] = "$NetBSD: bt_split.c,v 1.5 1995/02/27 13:20:55 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_split.c,v 1.6 1996/05/03 21:50:56 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -123,14 +123,14 @@ __bt_split(t, sp, key, data, flags, ilen, argskip) */ h->linp[skip] = h->upper -= ilen; dest = (char *)h + h->upper; - if (ISSET(t, R_RECNO)) + if (F_ISSET(t, R_RECNO)) WR_RLEAF(dest, data, flags) else WR_BLEAF(dest, key, data, flags) /* If the root page was split, make it look right. */ if (sp->pgno == P_ROOT && - (ISSET(t, R_RECNO) ? + (F_ISSET(t, R_RECNO) ? bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR) goto err2; @@ -238,7 +238,7 @@ __bt_split(t, sp, key, data, flags, ilen, argskip) } /* Insert the key into the parent page. */ - switch(rchild->flags & P_TYPE) { + switch (rchild->flags & P_TYPE) { case P_BINTERNAL: h->linp[skip] = h->upper -= nbytes; dest = (char *)h + h->linp[skip]; @@ -303,7 +303,7 @@ __bt_split(t, sp, key, data, flags, ilen, argskip) /* If the root page was split, make it look right. */ if (sp->pgno == P_ROOT && - (ISSET(t, R_RECNO) ? + (F_ISSET(t, R_RECNO) ? bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR) goto err1; @@ -396,6 +396,9 @@ bt_page(t, h, lp, rp, skip, ilen) mpool_put(t->bt_mp, r, 0); return (NULL); } +#ifdef PURIFY + memset(l, 0xff, t->bt_psize); +#endif l->pgno = h->pgno; l->nextpg = r->pgno; l->prevpg = h->prevpg; @@ -411,7 +414,7 @@ bt_page(t, h, lp, rp, skip, ilen) return (NULL); } tp->prevpg = r->pgno; - mpool_put(t->bt_mp, tp, 0); + mpool_put(t->bt_mp, tp, MPOOL_DIRTY); } /* @@ -558,7 +561,7 @@ bt_broot(t, h, l, r) dest = (char *)h + h->upper; WR_BINTERNAL(dest, 0, l->pgno, 0); - switch(h->flags & P_TYPE) { + switch (h->flags & P_TYPE) { case P_BLEAF: bl = GETBLEAF(r, 0); nbytes = NBINTERNAL(bl->ksize); @@ -621,8 +624,8 @@ bt_psplit(t, h, l, r, pskip, ilen) { BINTERNAL *bi; BLEAF *bl; + CURSOR *c; RLEAF *rl; - EPGNO *c; PAGE *rval; void *src; indx_t full, half, nxt, off, skip, top, used; @@ -710,19 +713,16 @@ bt_psplit(t, h, l, r, pskip, ilen) * cursor is at or past the skipped slot, the cursor is incremented by * one. If the cursor is on the right page, it is decremented by the * number of records split to the left page. - * - * Don't bother checking for the B_SEQINIT flag, the page number will - * be P_INVALID. */ - c = &t->bt_bcursor; - if (c->pgno == h->pgno) { - if (c->index >= skip) - ++c->index; - if (c->index < nxt) /* Left page. */ - c->pgno = l->pgno; + c = &t->bt_cursor; + if (F_ISSET(c, CURS_INIT) && c->pg.pgno == h->pgno) { + if (c->pg.index >= skip) + ++c->pg.index; + if (c->pg.index < nxt) /* Left page. */ + c->pg.pgno = l->pgno; else { /* Right page. */ - c->pgno = r->pgno; - c->index -= nxt; + c->pg.pgno = r->pgno; + c->pg.index -= nxt; } } diff --git a/lib/libc/db/btree/bt_stack.c b/lib/libc/db/btree/bt_stack.c index 7199ae9b090..e69de29bb2d 100644 --- a/lib/libc/db/btree/bt_stack.c +++ b/lib/libc/db/btree/bt_stack.c @@ -1,102 +0,0 @@ -/* $NetBSD: bt_stack.c,v 1.5 1995/02/27 13:21:01 cgd Exp $ */ - -/*- - * Copyright (c) 1990, 1993, 1994 - * The Regents of the University of California. All rights reserved. - * - * This code is derived from software contributed to Berkeley by - * Mike Olson. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 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. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - */ - -#if defined(LIBC_SCCS) && !defined(lint) -#if 0 -static char sccsid[] = "@(#)bt_stack.c 8.4 (Berkeley) 6/20/94"; -#else -static char rcsid[] = "$NetBSD: bt_stack.c,v 1.5 1995/02/27 13:21:01 cgd Exp $"; -#endif -#endif /* LIBC_SCCS and not lint */ - -#include - -#include -#include -#include - -#include -#include "btree.h" - -/* - * When a page splits, a new record has to be inserted into its parent page. - * This page may have to split as well, all the way up to the root. Since - * parent pointers in each page would be expensive, we maintain a stack of - * parent pages as we descend the tree. - * - * XXX - * This is a concurrency problem -- if user a builds a stack, then user b - * splits the tree, then user a tries to split the tree, there's a new level - * in the tree that user a doesn't know about. - */ - -/* - * __BT_PUSH -- Push parent page info onto the stack (LIFO). - * - * Parameters: - * t: tree - * pgno: page - * index: page index - * - * Returns: - * RET_ERROR, RET_SUCCESS - */ -int -__bt_push(t, pgno, index) - BTREE *t; - pgno_t pgno; - indx_t index; -{ - size_t sz; - - if (t->bt_sp == t->bt_maxstack) { - t->bt_maxstack += 50; - sz = t->bt_maxstack * sizeof(EPGNO); - t->bt_stack = (EPGNO *)(t->bt_stack == NULL ? - malloc(sz) : realloc(t->bt_stack, sz)); - if (t->bt_stack == NULL) { - t->bt_maxstack -= 50; - return (RET_ERROR); - } - } - - t->bt_stack[t->bt_sp].pgno = pgno; - t->bt_stack[t->bt_sp].index = index; - ++t->bt_sp; - return (RET_SUCCESS); -} diff --git a/lib/libc/db/btree/bt_utils.c b/lib/libc/db/btree/bt_utils.c index f9acf0ab8a1..2637f719a18 100644 --- a/lib/libc/db/btree/bt_utils.c +++ b/lib/libc/db/btree/bt_utils.c @@ -1,4 +1,4 @@ -/* $NetBSD: bt_utils.c,v 1.6 1995/02/27 13:21:04 cgd Exp $ */ +/* $NetBSD: bt_utils.c,v 1.7 1996/05/03 21:50:58 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)bt_utils.c 8.5 (Berkeley) 6/20/94"; +static char sccsid[] = "@(#)bt_utils.c 8.8 (Berkeley) 7/20/94"; #else -static char rcsid[] = "$NetBSD: bt_utils.c,v 1.6 1995/02/27 13:21:04 cgd Exp $"; +static char rcsid[] = "$NetBSD: bt_utils.c,v 1.7 1996/05/03 21:50:58 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -54,81 +54,91 @@ static char rcsid[] = "$NetBSD: bt_utils.c,v 1.6 1995/02/27 13:21:04 cgd Exp $"; #include "btree.h" /* - * __BT_RET -- Build return key/data pair as a result of search or scan. + * __bt_ret -- + * Build return key/data pair. * * Parameters: * t: tree - * d: LEAF to be returned to the user. + * e: key/data pair to be returned * key: user's key structure (NULL if not to be filled in) - * data: user's data structure + * rkey: memory area to hold key + * data: user's data structure (NULL if not to be filled in) + * rdata: memory area to hold data + * copy: always copy the key/data item * * Returns: * RET_SUCCESS, RET_ERROR. */ int -__bt_ret(t, e, key, data) +__bt_ret(t, e, key, rkey, data, rdata, copy) BTREE *t; EPG *e; - DBT *key, *data; + DBT *key, *rkey, *data, *rdata; + int copy; { - register BLEAF *bl; - register void *p; + BLEAF *bl; + void *p; bl = GETBLEAF(e->page, e->index); /* - * We always copy big keys/data to make them contigous. Otherwise, - * we leave the page pinned and don't copy unless the user specified + * We must copy big keys/data to make them contigous. Otherwise, + * leave the page pinned and don't copy unless the user specified * concurrent access. */ - if (bl->flags & P_BIGDATA) { - if (__ovfl_get(t, bl->bytes + bl->ksize, - &data->size, &t->bt_dbuf, &t->bt_dbufsz)) + if (key == NULL) + goto dataonly; + + if (bl->flags & P_BIGKEY) { + if (__ovfl_get(t, bl->bytes, + &key->size, &rkey->data, &rkey->size)) return (RET_ERROR); - data->data = t->bt_dbuf; - } else if (ISSET(t, B_DB_LOCK)) { - /* Use +1 in case the first record retrieved is 0 length. */ - if (bl->dsize + 1 > t->bt_dbufsz) { - p = (void *)(t->bt_dbuf == NULL ? - malloc(bl->dsize + 1) : - realloc(t->bt_dbuf, bl->dsize + 1)); + key->data = rkey->data; + } else if (copy || F_ISSET(t, B_DB_LOCK)) { + if (bl->ksize > rkey->size) { + p = (void *)(rkey->data == NULL ? + malloc(bl->ksize) : realloc(rkey->data, bl->ksize)); if (p == NULL) return (RET_ERROR); - t->bt_dbuf = p; - t->bt_dbufsz = bl->dsize + 1; + rkey->data = p; + rkey->size = bl->ksize; } - memmove(t->bt_dbuf, bl->bytes + bl->ksize, bl->dsize); - data->size = bl->dsize; - data->data = t->bt_dbuf; + memmove(rkey->data, bl->bytes, bl->ksize); + key->size = bl->ksize; + key->data = rkey->data; } else { - data->size = bl->dsize; - data->data = bl->bytes + bl->ksize; + key->size = bl->ksize; + key->data = bl->bytes; } - if (key == NULL) +dataonly: + if (data == NULL) return (RET_SUCCESS); - if (bl->flags & P_BIGKEY) { - if (__ovfl_get(t, bl->bytes, - &key->size, &t->bt_kbuf, &t->bt_kbufsz)) + if (bl->flags & P_BIGDATA) { + if (__ovfl_get(t, bl->bytes + bl->ksize, + &data->size, &rdata->data, &rdata->size)) return (RET_ERROR); - key->data = t->bt_kbuf; - } else if (ISSET(t, B_DB_LOCK)) { - if (bl->ksize > t->bt_kbufsz) { - p = (void *)(t->bt_kbuf == NULL ? - malloc(bl->ksize) : realloc(t->bt_kbuf, bl->ksize)); + data->data = rdata->data; + } else if (copy || F_ISSET(t, B_DB_LOCK)) { + /* Use +1 in case the first record retrieved is 0 length. */ + if (bl->dsize + 1 > rdata->size) { + p = (void *)(rdata->data == NULL ? + malloc(bl->dsize + 1) : + realloc(rdata->data, bl->dsize + 1)); if (p == NULL) return (RET_ERROR); - t->bt_kbuf = p; - t->bt_kbufsz = bl->ksize; + rdata->data = p; + rdata->size = bl->dsize + 1; } - memmove(t->bt_kbuf, bl->bytes, bl->ksize); - key->size = bl->ksize; - key->data = t->bt_kbuf; + memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize); + data->size = bl->dsize; + data->data = rdata->data; } else { - key->size = bl->ksize; - key->data = bl->bytes; + data->size = bl->dsize; + data->data = bl->bytes + bl->ksize; } + return (RET_SUCCESS); } @@ -189,9 +199,9 @@ __bt_cmp(t, k1, e) if (bigkey) { if (__ovfl_get(t, bigkey, - &k2.size, &t->bt_dbuf, &t->bt_dbufsz)) + &k2.size, &t->bt_rdata.data, &t->bt_rdata.size)) return (RET_ERROR); - k2.data = t->bt_dbuf; + k2.data = t->bt_rdata.data; } return ((*t->bt_cmp)(k1, &k2)); } diff --git a/lib/libc/db/btree/btree.h b/lib/libc/db/btree/btree.h index 747ed93638e..d2bb945a1c3 100644 --- a/lib/libc/db/btree/btree.h +++ b/lib/libc/db/btree/btree.h @@ -1,4 +1,4 @@ -/* $NetBSD: btree.h,v 1.8 1995/02/27 13:21:08 cgd Exp $ */ +/* $NetBSD: btree.h,v 1.9 1996/05/03 21:51:00 cgd Exp $ */ /*- * Copyright (c) 1991, 1993, 1994 @@ -35,9 +35,14 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * @(#)btree.h 8.6 (Berkeley) 5/31/94 + * @(#)btree.h 8.11 (Berkeley) 8/17/94 */ +/* Macros to set/clear/test flags. */ +#define F_SET(p, f) (p)->flags |= (f) +#define F_CLR(p, f) (p)->flags &= ~(f) +#define F_ISSET(p, f) ((p)->flags & (f)) + #include #define DEFMINKEYPAGE (2) /* Minimum keys per page */ @@ -81,8 +86,9 @@ typedef struct _page { } PAGE; /* First and next index. */ -#define BTDATAOFF (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t) + \ - sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t)) +#define BTDATAOFF \ + (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t) + \ + sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t)) #define NEXTINDEX(p) (((p)->lower - BTDATAOFF) / sizeof(indx_t)) /* @@ -101,8 +107,7 @@ typedef struct _page { * be manipulated without copying. (This presumes that 32 bit items can be * manipulated on this system.) */ -#define LALIGN(n) \ - (((n) + sizeof(pgno_t) - 1) & ~(sizeof(pgno_t) - 1)) +#define LALIGN(n) (((n) + sizeof(pgno_t) - 1) & ~(sizeof(pgno_t) - 1)) #define NOVFLSIZE (sizeof(pgno_t) + sizeof(u_int32_t)) /* @@ -124,11 +129,11 @@ typedef struct _binternal { } BINTERNAL; /* Get the page's BINTERNAL structure at index indx. */ -#define GETBINTERNAL(pg, indx) \ +#define GETBINTERNAL(pg, indx) \ ((BINTERNAL *)((char *)(pg) + (pg)->linp[indx])) /* Get the number of bytes in the entry. */ -#define NBINTERNAL(len) \ +#define NBINTERNAL(len) \ LALIGN(sizeof(u_int32_t) + sizeof(pgno_t) + sizeof(u_char) + (len)) /* Copy a BINTERNAL entry to the page. */ @@ -151,18 +156,18 @@ typedef struct _rinternal { } RINTERNAL; /* Get the page's RINTERNAL structure at index indx. */ -#define GETRINTERNAL(pg, indx) \ +#define GETRINTERNAL(pg, indx) \ ((RINTERNAL *)((char *)(pg) + (pg)->linp[indx])) /* Get the number of bytes in the entry. */ -#define NRINTERNAL \ +#define NRINTERNAL \ LALIGN(sizeof(recno_t) + sizeof(pgno_t)) /* Copy a RINTERAL entry to the page. */ -#define WR_RINTERNAL(p, nrecs, pgno) { \ - *(recno_t *)p = nrecs; \ - p += sizeof(recno_t); \ - *(pgno_t *)p = pgno; \ +#define WR_RINTERNAL(p, nrecs, pgno) { \ + *(recno_t *)p = nrecs; \ + p += sizeof(recno_t); \ + *(pgno_t *)p = pgno; \ } /* For the btree leaf pages, the item is a key and data pair. */ @@ -174,15 +179,15 @@ typedef struct _bleaf { } BLEAF; /* Get the page's BLEAF structure at index indx. */ -#define GETBLEAF(pg, indx) \ +#define GETBLEAF(pg, indx) \ ((BLEAF *)((char *)(pg) + (pg)->linp[indx])) /* Get the number of bytes in the entry. */ #define NBLEAF(p) NBLEAFDBT((p)->ksize, (p)->dsize) /* Get the number of bytes in the user's key/data pair. */ -#define NBLEAFDBT(ksize, dsize) \ - LALIGN(sizeof(u_int32_t) + sizeof(u_int32_t) + sizeof(u_char) + \ +#define NBLEAFDBT(ksize, dsize) \ + LALIGN(sizeof(u_int32_t) + sizeof(u_int32_t) + sizeof(u_char) + \ (ksize) + (dsize)) /* Copy a BLEAF entry to the page. */ @@ -206,14 +211,14 @@ typedef struct _rleaf { } RLEAF; /* Get the page's RLEAF structure at index indx. */ -#define GETRLEAF(pg, indx) \ +#define GETRLEAF(pg, indx) \ ((RLEAF *)((char *)(pg) + (pg)->linp[indx])) /* Get the number of bytes in the entry. */ #define NRLEAF(p) NRLEAFDBT((p)->dsize) /* Get the number of bytes from the user's data. */ -#define NRLEAFDBT(dsize) \ +#define NRLEAFDBT(dsize) \ LALIGN(sizeof(u_int32_t) + sizeof(u_char) + (dsize)) /* Copy a RLEAF entry to the page. */ @@ -234,12 +239,6 @@ typedef struct _rleaf { * record less than key in the tree so that descents work. Leaf page searches * must find the smallest record greater than key so that the returned index * is the record's correct position for insertion. - * - * One comment about cursors. The cursor key is never removed from the tree, - * even if deleted. This is because it is quite difficult to decide where the - * cursor should be when other keys have been inserted/deleted in the tree; - * duplicate keys make it impossible. This scheme does require extra work - * though, to make sure that we don't perform an operation on a deleted key. */ typedef struct _epgno { pgno_t pgno; /* the page number */ @@ -252,53 +251,90 @@ typedef struct _epg { } EPG; /* - * The metadata of the tree. The m_nrecs field is used only by the RECNO code. + * About cursors. The cursor (and the page that contained the key/data pair + * that it referenced) can be deleted, which makes things a bit tricky. If + * there are no duplicates of the cursor key in the tree (i.e. B_NODUPS is set + * or there simply aren't any duplicates of the key) we copy the key that it + * referenced when it's deleted, and reacquire a new cursor key if the cursor + * is used again. If there are duplicates keys, we move to the next/previous + * key, and set a flag so that we know what happened. NOTE: if duplicate (to + * the cursor) keys are added to the tree during this process, it is undefined + * if they will be returned or not in a cursor scan. + * + * The flags determine the possible states of the cursor: + * + * CURS_INIT The cursor references *something*. + * CURS_ACQUIRE The cursor was deleted, and a key has been saved so that + * we can reacquire the right position in the tree. + * CURS_AFTER, CURS_BEFORE + * The cursor was deleted, and now references a key/data pair + * that has not yet been returned, either before or after the + * deleted key/data pair. + * XXX + * This structure is broken out so that we can eventually offer multiple + * cursors as part of the DB interface. + */ +typedef struct _cursor { + EPGNO pg; /* B: Saved tree reference. */ + DBT key; /* B: Saved key, or key.data == NULL. */ + recno_t rcursor; /* R: recno cursor (1-based) */ + +#define CURS_ACQUIRE 0x01 /* B: Cursor needs to be reacquired. */ +#define CURS_AFTER 0x02 /* B: Unreturned cursor after key. */ +#define CURS_BEFORE 0x04 /* B: Unreturned cursor before key. */ +#define CURS_INIT 0x08 /* RB: Cursor initialized. */ + u_int8_t flags; +} CURSOR; + +/* + * The metadata of the tree. The nrecs field is used only by the RECNO code. * This is because the btree doesn't really need it and it requires that every * put or delete call modify the metadata. */ typedef struct _btmeta { - u_int32_t m_magic; /* magic number */ - u_int32_t m_version; /* version */ - u_int32_t m_psize; /* page size */ - u_int32_t m_free; /* page number of first free page */ - u_int32_t m_nrecs; /* R: number of records */ + u_int32_t magic; /* magic number */ + u_int32_t version; /* version */ + u_int32_t psize; /* page size */ + u_int32_t free; /* page number of first free page */ + u_int32_t nrecs; /* R: number of records */ + #define SAVEMETA (B_NODUPS | R_RECNO) - u_int32_t m_flags; /* bt_flags & SAVEMETA */ - u_int32_t m_unused; /* unused */ + u_int32_t flags; /* bt_flags & SAVEMETA */ } BTMETA; /* The in-memory btree/recno data structure. */ typedef struct _btree { - MPOOL *bt_mp; /* memory pool cookie */ + MPOOL *bt_mp; /* memory pool cookie */ - DB *bt_dbp; /* pointer to enclosing DB */ + DB *bt_dbp; /* pointer to enclosing DB */ - EPG bt_cur; /* current (pinned) page */ - PAGE *bt_pinned; /* page pinned across calls */ + EPG bt_cur; /* current (pinned) page */ + PAGE *bt_pinned; /* page pinned across calls */ - EPGNO bt_bcursor; /* B: btree cursor */ - recno_t bt_rcursor; /* R: recno cursor (1-based) */ + CURSOR bt_cursor; /* cursor */ -#define BT_POP(t) (t->bt_sp ? t->bt_stack + --t->bt_sp : NULL) -#define BT_CLR(t) (t->bt_sp = 0) - EPGNO *bt_stack; /* stack of parent pages */ - u_int bt_sp; /* current stack pointer */ - u_int bt_maxstack; /* largest stack */ +#define BT_PUSH(t, p, i) { \ + t->bt_sp->pgno = p; \ + t->bt_sp->index = i; \ + ++t->bt_sp; \ +} +#define BT_POP(t) (t->bt_sp == t->bt_stack ? NULL : --t->bt_sp) +#define BT_CLR(t) (t->bt_sp = t->bt_stack) + EPGNO bt_stack[50]; /* stack of parent pages */ + EPGNO *bt_sp; /* current stack pointer */ - char *bt_kbuf; /* key buffer */ - size_t bt_kbufsz; /* key buffer size */ - char *bt_dbuf; /* data buffer */ - size_t bt_dbufsz; /* data buffer size */ + DBT bt_rkey; /* returned key */ + DBT bt_rdata; /* returned data */ - int bt_fd; /* tree file descriptor */ + int bt_fd; /* tree file descriptor */ - pgno_t bt_free; /* next free page */ + pgno_t bt_free; /* next free page */ u_int32_t bt_psize; /* page size */ - indx_t bt_ovflsize; /* cut-off for key/data overflow */ - int bt_lorder; /* byte order */ + indx_t bt_ovflsize; /* cut-off for key/data overflow */ + int bt_lorder; /* byte order */ /* sorted order */ enum { NOT, BACK, FORWARD } bt_order; - EPGNO bt_last; /* last insert */ + EPGNO bt_last; /* last insert */ /* B: key comparison function */ int (*bt_cmp) __P((const DBT *, const DBT *)); @@ -307,49 +343,43 @@ typedef struct _btree { /* R: recno input function */ int (*bt_irec) __P((struct _btree *, recno_t)); - FILE *bt_rfp; /* R: record FILE pointer */ - int bt_rfd; /* R: record file descriptor */ + FILE *bt_rfp; /* R: record FILE pointer */ + int bt_rfd; /* R: record file descriptor */ - caddr_t bt_cmap; /* R: current point in mapped space */ - caddr_t bt_smap; /* R: start of mapped space */ - caddr_t bt_emap; /* R: end of mapped space */ - size_t bt_msize; /* R: size of mapped region. */ + caddr_t bt_cmap; /* R: current point in mapped space */ + caddr_t bt_smap; /* R: start of mapped space */ + caddr_t bt_emap; /* R: end of mapped space */ + size_t bt_msize; /* R: size of mapped region. */ - recno_t bt_nrecs; /* R: number of records */ - size_t bt_reclen; /* R: fixed record length */ - u_char bt_bval; /* R: delimiting byte/pad character */ + recno_t bt_nrecs; /* R: number of records */ + size_t bt_reclen; /* R: fixed record length */ + u_char bt_bval; /* R: delimiting byte/pad character */ /* * NB: * B_NODUPS and R_RECNO are stored on disk, and may not be changed. */ -#define B_DELCRSR 0x00001 /* cursor has been deleted */ -#define B_INMEM 0x00002 /* in-memory tree */ -#define B_METADIRTY 0x00004 /* need to write metadata */ -#define B_MODIFIED 0x00008 /* tree modified */ -#define B_NEEDSWAP 0x00010 /* if byte order requires swapping */ +#define B_INMEM 0x00001 /* in-memory tree */ +#define B_METADIRTY 0x00002 /* need to write metadata */ +#define B_MODIFIED 0x00004 /* tree modified */ +#define B_NEEDSWAP 0x00008 /* if byte order requires swapping */ +#define B_RDONLY 0x00010 /* read-only tree */ + #define B_NODUPS 0x00020 /* no duplicate keys permitted */ -#define B_RDONLY 0x00040 /* read-only tree */ #define R_RECNO 0x00080 /* record oriented tree */ -#define B_SEQINIT 0x00100 /* sequential scan initialized */ - -#define R_CLOSEFP 0x00200 /* opened a file pointer */ -#define R_EOF 0x00400 /* end of input file reached. */ -#define R_FIXLEN 0x00800 /* fixed length records */ -#define R_MEMMAPPED 0x01000 /* memory mapped file. */ -#define R_INMEM 0x02000 /* in-memory file */ -#define R_MODIFIED 0x04000 /* modified file */ -#define R_RDONLY 0x08000 /* read-only file */ -#define B_DB_LOCK 0x10000 /* DB_LOCK specified. */ -#define B_DB_SHMEM 0x20000 /* DB_SHMEM specified. */ -#define B_DB_TXN 0x40000 /* DB_TXN specified. */ - - u_int32_t bt_flags; /* btree state */ +#define R_CLOSEFP 0x00040 /* opened a file pointer */ +#define R_EOF 0x00100 /* end of input file reached. */ +#define R_FIXLEN 0x00200 /* fixed length records */ +#define R_MEMMAPPED 0x00400 /* memory mapped file. */ +#define R_INMEM 0x00800 /* in-memory file */ +#define R_MODIFIED 0x01000 /* modified file */ +#define R_RDONLY 0x02000 /* read-only file */ + +#define B_DB_LOCK 0x04000 /* DB_LOCK specified. */ +#define B_DB_SHMEM 0x08000 /* DB_SHMEM specified. */ +#define B_DB_TXN 0x10000 /* DB_TXN specified. */ + u_int32_t flags; } BTREE; -#define SET(t, f) ((t)->bt_flags |= (f)) -#define CLR(t, f) ((t)->bt_flags &= ~(f)) -#define ISSET(t, f) ((t)->bt_flags & (f)) - #include "extern.h" diff --git a/lib/libc/db/btree/extern.h b/lib/libc/db/btree/extern.h index 6d09c2eb204..6a4fddf61c4 100644 --- a/lib/libc/db/btree/extern.h +++ b/lib/libc/db/btree/extern.h @@ -1,7 +1,7 @@ -/* $NetBSD: extern.h,v 1.5 1995/02/27 13:21:12 cgd Exp $ */ +/* $NetBSD: extern.h,v 1.6 1996/05/03 21:51:01 cgd Exp $ */ /*- - * Copyright (c) 1991, 1993 + * Copyright (c) 1991, 1993, 1994 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -32,7 +32,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * @(#)extern.h 8.4 (Berkeley) 6/4/94 + * @(#)extern.h 8.10 (Berkeley) 7/20/94 */ int __bt_close __P((DB *)); @@ -41,9 +41,8 @@ int __bt_crsrdel __P((BTREE *, EPGNO *)); int __bt_defcmp __P((const DBT *, const DBT *)); size_t __bt_defpfx __P((const DBT *, const DBT *)); int __bt_delete __P((const DB *, const DBT *, u_int)); -int __bt_dleaf __P((BTREE *, PAGE *, int)); +int __bt_dleaf __P((BTREE *, const DBT *, PAGE *, u_int)); int __bt_fd __P((const DB *)); -EPG *__bt_first __P((BTREE *, const DBT *, int *)); int __bt_free __P((BTREE *, PAGE *)); int __bt_get __P((const DB *, const DBT *, DBT *, u_int)); PAGE *__bt_new __P((BTREE *, pgno_t *)); @@ -51,15 +50,16 @@ void __bt_pgin __P((void *, pgno_t, void *)); void __bt_pgout __P((void *, pgno_t, void *)); int __bt_push __P((BTREE *, pgno_t, int)); int __bt_put __P((const DB *dbp, DBT *, const DBT *, u_int)); -int __bt_ret __P((BTREE *, EPG *, DBT *, DBT *)); +int __bt_ret __P((BTREE *, EPG *, DBT *, DBT *, DBT *, DBT *, int)); EPG *__bt_search __P((BTREE *, const DBT *, int *)); int __bt_seq __P((const DB *, DBT *, DBT *, u_int)); +void __bt_setcur __P((BTREE *, pgno_t, u_int)); int __bt_split __P((BTREE *, PAGE *, const DBT *, const DBT *, int, size_t, u_int32_t)); int __bt_sync __P((const DB *, u_int)); int __ovfl_delete __P((BTREE *, void *)); -int __ovfl_get __P((BTREE *, void *, size_t *, char **, size_t *)); +int __ovfl_get __P((BTREE *, void *, size_t *, void **, size_t *)); int __ovfl_put __P((BTREE *, const DBT *, pgno_t *)); #ifdef DEBUG diff --git a/lib/libc/db/changelog b/lib/libc/db/changelog new file mode 100644 index 00000000000..f820e56b588 --- /dev/null +++ b/lib/libc/db/changelog @@ -0,0 +1,105 @@ +# $NetBSD: changelog,v 1.2 1996/05/03 21:20:56 cgd Exp $ + +1.84 -> 1.85 + recno: #ifdef out use of mmap, it's not portable enough. + +1.83 -> 1.84 Thu Aug 18 15:46:07 EDT 1994 + recno: Rework fixed-length records so that closing and reopening + the file now works. Pad short records on input. Never do + signed comparison in recno input reading functions. + +1.82 -> 1.83 Tue Jul 26 15:33:44 EDT 1994 + btree: Rework cursor deletion code yet again; bugs with + deleting empty pages that only contained the cursor + record. + +1.81 -> 1.82 Sat Jul 16 11:01:50 EDT 1994 + btree: Fix bugs introduced by new cursor/deletion code. + Replace return kbuf/dbuf with real DBT's. + +1.80 -> 1.81 + btree: Fix bugs introduced by new cursor/deletion code. + all: Add #defines for Purify. + +1.79 -> 1.80 Wed Jul 13 22:41:54 EDT 1994 + btree Change deletion to coalesce empty pages. This is a major + change, cursors and duplicate pages all had to be reworked. + Return to a fixed stack. + recno: Affected by cursor changes. New cursor structures should + permit multiple cursors in the future. + +1.78 -> 1.79 Mon Jun 20 17:36:47 EDT 1994 + all: Minor cleanups of 1.78 for porting reasons; only + major change was inlining check of NULL pointer + so that __fix_realloc goes away. + +1.77 -> 1.78 Thu Jun 16 19:06:43 EDT 1994 + all: Move "standard" size typedef's into db.h. + +1.76 -> 1.77 Thu Jun 16 16:48:38 EDT 1994 + hash: Delete __init_ routine, has special meaning to OSF 2.0. + +1.74 -> 1.76 + all: Finish up the port to the Alpha. + +1.73 -> 1.74 + recno: Don't put the record if rec_search fails, in rec_rdelete. + Create fixed-length intermediate records past "end" of DB + correctly. + Realloc bug when reading in fixed records. + all: First cut at port to Alpha (64-bit architecture) using + 4.4BSD basic integral types typedef's. + Cast allocation pointers to shut up old compilers. + Rework PORT directory into OS/machine directories. + +1.72 -> 1.73 + btree: If enough duplicate records were inserted and then deleted + that internal pages had references to empty pages of the + duplicate keys, the search function ended up on the wrong + page. + +1.7 -> 1.72 12 Oct 1993 + hash: Support NET/2 hash formats. + +1.7 -> 1.71 16 Sep 1993 + btree/recno: + Fix bug in internal search routines that caused + return of invalid pointers. + +1.6 -> 1.7 07 Sep 1993 + hash: Fixed big key overflow bugs. + test: Portability hacks, rewrite test script, Makefile. + btree/recno: + Stop copying non-overflow key/data pairs. + PORT: Break PORT directory up into per architecture/OS + subdirectories. + +1.5 -> 1.6 06 Jun 1993 + hash: In PAIRFITS, the first comparison should look at (P)[2]. + The hash_realloc function was walking off the end of memory. + The overflow page number was wrong when bumping splitpoint. + +1.4 -> 1.5 23 May 1993 + hash: Set hash default fill factor dynamically. + recno: Fixed bug in sorted page splits. + Add page size parameter support. + Allow recno to specify the name of the underlying btree; + used for vi recovery. + btree/recno: + Support 64K pages. + btree/hash/recno: + Provide access to an underlying file descriptor. + Change sync routines to take a flag argument, recno + uses this to sync out the underlying btree. + +1.3 -> 1.4 10 May 1993 + recno: Delete the R_CURSORLOG flag from the recno interface. + Zero-length record fix for non-mmap reads. + Try and make SIZE_T_MAX test in open portable. + +1.2 -> 1.3 01 May 1993 + btree: Ignore user byte-order setting when reading already + existing database. Fixes to byte-order conversions. + +1.1 -> 1.2 15 Apr 1993 + No bug fixes, only compatibility hacks. diff --git a/lib/libc/db/db2netbsd b/lib/libc/db/db2netbsd new file mode 100644 index 00000000000..e29c97593bc --- /dev/null +++ b/lib/libc/db/db2netbsd @@ -0,0 +1,31 @@ +#!/bin/sh +# $NetBSD: db2netbsd,v 1.1 1996/05/03 22:43:02 cgd Exp $ + +# This version transforms a Berkeley DB distribution into something +# which can be 'cvs import'ed into the NetBSD source repository. +# It is to be run in the untarred Berkeley DB distribution directory +# (e.g. the "db.1.85" directory created by tar xvf), and sets up +# the destination tree in place. + +version=`basename $PWD | sed -e 's/db\.//'` +releasetag=`basename $PWD | sed -e 's/\./-/g'` + +CLEANFILES="PORT docs test/btree.tests test/hash.tests" + +# clean up pieces that we never import +/bin/rm -rf $CLEANFILES +find . -type l -o -name tags | xargs /bin/rm -f + +# The include files are already in place + +# Put the regression tests in the right place +mkdir -p regress/lib/libc +mv test regress/lib/libc/db + +# Put the libc pieces in the right place. +mkdir -p lib/libc/db +mv Makefile.inc README btree changelog db hash man mpool recno lib/libc/db + +echo "import with:" +echo "cvs import -m \"Import of Berkeley DB version $version\" \ +src CSRG $releasetag" diff --git a/lib/libc/db/hash/Makefile.inc b/lib/libc/db/hash/Makefile.inc index 00f339ac2ed..79fddf587d9 100644 --- a/lib/libc/db/hash/Makefile.inc +++ b/lib/libc/db/hash/Makefile.inc @@ -1,4 +1,4 @@ -# $NetBSD: Makefile.inc,v 1.5 1995/02/27 13:21:44 cgd Exp $ +# $NetBSD: Makefile.inc,v 1.6 1996/05/03 21:43:43 cgd Exp $ # @(#)Makefile.inc 8.1 (Berkeley) 6/4/93 .PATH: ${.CURDIR}/db/hash diff --git a/lib/libc/db/hash/README b/lib/libc/db/hash/README index fd1fc653a92..444bcb90414 100644 --- a/lib/libc/db/hash/README +++ b/lib/libc/db/hash/README @@ -1,4 +1,4 @@ -# $NetBSD: README,v 1.3 1995/02/27 13:21:52 cgd Exp $ +# $NetBSD: README,v 1.4 1996/05/03 21:43:44 cgd Exp $ # @(#)README 8.1 (Berkeley) 6/4/93 This package implements a superset of the hsearch and dbm/ndbm libraries. diff --git a/lib/libc/db/hash/extern.h b/lib/libc/db/hash/extern.h index af98921ef19..6b87ce4496d 100644 --- a/lib/libc/db/hash/extern.h +++ b/lib/libc/db/hash/extern.h @@ -1,4 +1,4 @@ -/* $NetBSD: extern.h,v 1.4 1995/02/27 13:21:55 cgd Exp $ */ +/* $NetBSD: extern.h,v 1.5 1996/05/03 21:43:45 cgd Exp $ */ /*- * Copyright (c) 1991, 1993, 1994 diff --git a/lib/libc/db/hash/hash.c b/lib/libc/db/hash/hash.c index 2fc3281cb9f..7ee731e500b 100644 --- a/lib/libc/db/hash/hash.c +++ b/lib/libc/db/hash/hash.c @@ -1,4 +1,4 @@ -/* $NetBSD: hash.c,v 1.8 1995/02/27 13:21:59 cgd Exp $ */ +/* $NetBSD: hash.c,v 1.9 1996/05/03 21:43:47 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -40,7 +40,7 @@ #if 0 static char sccsid[] = "@(#)hash.c 8.9 (Berkeley) 6/16/94"; #else -static char rcsid[] = "$NetBSD: hash.c,v 1.8 1995/02/27 13:21:59 cgd Exp $"; +static char rcsid[] = "$NetBSD: hash.c,v 1.9 1996/05/03 21:43:47 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ diff --git a/lib/libc/db/hash/hash.h b/lib/libc/db/hash/hash.h index 1ad93b74d9f..8ed5c6f6130 100644 --- a/lib/libc/db/hash/hash.h +++ b/lib/libc/db/hash/hash.h @@ -1,4 +1,4 @@ -/* $NetBSD: hash.h,v 1.5 1995/02/27 13:22:08 cgd Exp $ */ +/* $NetBSD: hash.h,v 1.6 1996/05/03 21:43:48 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 diff --git a/lib/libc/db/hash/hash_bigkey.c b/lib/libc/db/hash/hash_bigkey.c index 993839d9f79..0db652b8645 100644 --- a/lib/libc/db/hash/hash_bigkey.c +++ b/lib/libc/db/hash/hash_bigkey.c @@ -1,4 +1,4 @@ -/* $NetBSD: hash_bigkey.c,v 1.5 1995/02/27 13:22:16 cgd Exp $ */ +/* $NetBSD: hash_bigkey.c,v 1.6 1996/05/03 21:43:49 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -40,7 +40,7 @@ #if 0 static char sccsid[] = "@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94"; #else -static char rcsid[] = "$NetBSD: hash_bigkey.c,v 1.5 1995/02/27 13:22:16 cgd Exp $"; +static char rcsid[] = "$NetBSD: hash_bigkey.c,v 1.6 1996/05/03 21:43:49 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ diff --git a/lib/libc/db/hash/hash_buf.c b/lib/libc/db/hash/hash_buf.c index 7747331688a..81aca2a1dc3 100644 --- a/lib/libc/db/hash/hash_buf.c +++ b/lib/libc/db/hash/hash_buf.c @@ -1,4 +1,4 @@ -/* $NetBSD: hash_buf.c,v 1.5 1995/02/27 13:22:23 cgd Exp $ */ +/* $NetBSD: hash_buf.c,v 1.6 1996/05/03 21:43:51 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)hash_buf.c 8.4 (Berkeley) 6/4/94"; +static char sccsid[] = "@(#)hash_buf.c 8.5 (Berkeley) 7/15/94"; #else -static char rcsid[] = "$NetBSD: hash_buf.c,v 1.5 1995/02/27 13:22:23 cgd Exp $"; +static char rcsid[] = "$NetBSD: hash_buf.c,v 1.6 1996/05/03 21:43:51 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -185,10 +185,16 @@ newbuf(hashp, addr, prev_bp) /* Allocate a new one */ if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL) return (NULL); +#ifdef PURIFY + memset(bp, 0xff, sizeof(BUFHEAD)); +#endif if ((bp->page = (char *)malloc(hashp->BSIZE)) == NULL) { free(bp); return (NULL); } +#ifdef PURIFY + memset(bp->page, 0xff, hashp->BSIZE); +#endif if (hashp->nbufs) hashp->nbufs--; } else { diff --git a/lib/libc/db/hash/hash_func.c b/lib/libc/db/hash/hash_func.c index a978b99d2fa..09cf72e77f6 100644 --- a/lib/libc/db/hash/hash_func.c +++ b/lib/libc/db/hash/hash_func.c @@ -1,4 +1,4 @@ -/* $NetBSD: hash_func.c,v 1.5 1995/02/27 13:22:27 cgd Exp $ */ +/* $NetBSD: hash_func.c,v 1.6 1996/05/03 21:43:52 cgd Exp $ */ /*- * Copyright (c) 1990, 1993 @@ -40,7 +40,7 @@ #if 0 static char sccsid[] = "@(#)hash_func.c 8.2 (Berkeley) 2/21/94"; #else -static char rcsid[] = "$NetBSD: hash_func.c,v 1.5 1995/02/27 13:22:27 cgd Exp $"; +static char rcsid[] = "$NetBSD: hash_func.c,v 1.6 1996/05/03 21:43:52 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ diff --git a/lib/libc/db/hash/hash_log2.c b/lib/libc/db/hash/hash_log2.c index 9332cbac887..6ac2ab1ec2d 100644 --- a/lib/libc/db/hash/hash_log2.c +++ b/lib/libc/db/hash/hash_log2.c @@ -1,4 +1,4 @@ -/* $NetBSD: hash_log2.c,v 1.5 1995/02/27 13:22:30 cgd Exp $ */ +/* $NetBSD: hash_log2.c,v 1.6 1996/05/03 21:43:54 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -40,7 +40,7 @@ #if 0 static char sccsid[] = "@(#)hash_log2.c 8.2 (Berkeley) 5/31/94"; #else -static char rcsid[] = "$NetBSD: hash_log2.c,v 1.5 1995/02/27 13:22:30 cgd Exp $"; +static char rcsid[] = "$NetBSD: hash_log2.c,v 1.6 1996/05/03 21:43:54 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ diff --git a/lib/libc/db/hash/hash_page.c b/lib/libc/db/hash/hash_page.c index 49ee8904a14..c81d46ba60f 100644 --- a/lib/libc/db/hash/hash_page.c +++ b/lib/libc/db/hash/hash_page.c @@ -1,4 +1,4 @@ -/* $NetBSD: hash_page.c,v 1.7 1995/02/27 13:22:34 cgd Exp $ */ +/* $NetBSD: hash_page.c,v 1.8 1996/05/03 21:43:55 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)hash_page.c 8.6 (Berkeley) 6/16/94"; +static char sccsid[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94"; #else -static char rcsid[] = "$NetBSD: hash_page.c,v 1.7 1995/02/27 13:22:34 cgd Exp $"; +static char rcsid[] = "$NetBSD: hash_page.c,v 1.8 1996/05/03 21:43:55 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -689,7 +689,7 @@ overflow_page(hashp) for ( i = first_page; i <= free_page; i++ ) { if (!(freep = (u_int32_t *)hashp->mapp[i]) && !(freep = fetch_bitmap(hashp, i))) - return (NULL); + return (0); if (i == free_page) in_use_bits = free_bit; else @@ -719,7 +719,7 @@ overflow_page(hashp) if (offset > SPLITMASK) { if (++splitnum >= NCACHED) { (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); - return (NULL); + return (0); } hashp->OVFL_POINT = splitnum; hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; @@ -732,7 +732,7 @@ overflow_page(hashp) free_page++; if (free_page >= NCACHED) { (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); - return (NULL); + return (0); } /* * This is tricky. The 1 indicates that you want the new page @@ -745,9 +745,9 @@ overflow_page(hashp) * don't have to if we tell init_bitmap not to leave it clear * in the first place. */ - if (__ibitmap(hashp, (int)OADDR_OF(splitnum, offset), - 1, free_page)) - return (NULL); + if (__ibitmap(hashp, + (int)OADDR_OF(splitnum, offset), 1, free_page)) + return (0); hashp->SPARES[splitnum]++; #ifdef DEBUG2 free_bit = 2; @@ -757,7 +757,7 @@ overflow_page(hashp) if (++splitnum >= NCACHED) { (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); - return (NULL); + return (0); } hashp->OVFL_POINT = splitnum; hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; @@ -801,7 +801,7 @@ found: for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); offset = (i ? bit - hashp->SPARES[i - 1] : bit); if (offset >= SPLITMASK) - return (NULL); /* Out of overflow pages */ + 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", diff --git a/lib/libc/db/hash/hsearch.c b/lib/libc/db/hash/hsearch.c index ef825ab7182..409182c0c64 100644 --- a/lib/libc/db/hash/hsearch.c +++ b/lib/libc/db/hash/hsearch.c @@ -1,4 +1,4 @@ -/* $NetBSD: hsearch.c,v 1.8 1995/02/27 13:22:38 cgd Exp $ */ +/* $NetBSD: hsearch.c,v 1.10 1996/05/03 22:16:32 cgd Exp $ */ /*- * Copyright (c) 1990, 1993 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)hsearch.c 8.3 (Berkeley) 2/21/94"; +static char sccsid[] = "@(#)hsearch.c 8.4 (Berkeley) 7/21/94"; #else -static char rcsid[] = "$NetBSD: hsearch.c,v 1.8 1995/02/27 13:22:38 cgd Exp $"; +static char rcsid[] = "$NetBSD: hsearch.c,v 1.10 1996/05/03 22:16:32 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -64,7 +64,7 @@ hcreate(nel) info.nelem = nel; info.bsize = 256; info.ffactor = 8; - info.cachesize = NULL; + info.cachesize = 0; info.hash = NULL; info.lorder = 0; dbp = (DB *)__hash_open(NULL, O_CREAT | O_RDWR, 0600, &info, 0); diff --git a/lib/libc/db/hash/ndbm.c b/lib/libc/db/hash/ndbm.c index 875b0494e59..dd519a4a8ce 100644 --- a/lib/libc/db/hash/ndbm.c +++ b/lib/libc/db/hash/ndbm.c @@ -1,4 +1,4 @@ -/* $NetBSD: ndbm.c,v 1.7 1995/02/27 13:22:44 cgd Exp $ */ +/* $NetBSD: ndbm.c,v 1.9 1996/05/04 00:38:58 cgd Exp $ */ /*- * Copyright (c) 1990, 1993 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)ndbm.c 8.3 (Berkeley) 5/30/94"; +static char sccsid[] = "@(#)ndbm.c 8.4 (Berkeley) 7/21/94"; #else -static char rcsid[] = "$NetBSD: ndbm.c,v 1.7 1995/02/27 13:22:44 cgd Exp $"; +static char rcsid[] = "$NetBSD: ndbm.c,v 1.9 1996/05/04 00:38:58 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -73,7 +73,7 @@ dbm_open(file, flags, mode) info.bsize = 4096; info.ffactor = 40; info.nelem = 1; - info.cachesize = NULL; + info.cachesize = 0; info.hash = NULL; info.lorder = 0; (void)strcpy(path, file); @@ -98,15 +98,20 @@ dbm_fetch(db, key) DBM *db; datum key; { - datum retval; + datum retdata; int status; + DBT dbtkey, dbtretdata; - status = (db->get)(db, (DBT *)&key, (DBT *)&retval, 0); + dbtkey.data = key.dptr; + dbtkey.size = key.dsize; + status = (db->get)(db, &dbtkey, &dbtretdata, 0); if (status) { - retval.dptr = NULL; - retval.dsize = 0; + dbtretdata.data = NULL; + dbtretdata.size = 0; } - return (retval); + retdata.dptr = dbtretdata.data; + retdata.dsize = dbtretdata.size; + return (retdata); } /* @@ -119,11 +124,14 @@ dbm_firstkey(db) DBM *db; { int status; - datum retdata, retkey; + datum retkey; + DBT dbtretkey, dbtretdata; - status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_FIRST); + status = (db->seq)(db, &dbtretkey, &dbtretdata, R_FIRST); if (status) - retkey.dptr = NULL; + dbtretkey.data = NULL; + retkey.dptr = dbtretkey.data; + retkey.dsize = dbtretkey.size; return (retkey); } @@ -137,13 +145,17 @@ dbm_nextkey(db) DBM *db; { int status; - datum retdata, retkey; + datum retkey; + DBT dbtretkey, dbtretdata; - status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_NEXT); + status = (db->seq)(db, &dbtretkey, &dbtretdata, R_NEXT); if (status) - retkey.dptr = NULL; + dbtretkey.data = NULL; + retkey.dptr = dbtretkey.data; + retkey.dsize = dbtretkey.size; return (retkey); } + /* * Returns: * 0 on success @@ -155,8 +167,11 @@ dbm_delete(db, key) datum key; { int status; + DBT dbtkey; - status = (db->del)(db, (DBT *)&key, 0); + dbtkey.data = key.dptr; + dbtkey.size = key.dsize; + status = (db->del)(db, &dbtkey, 0); if (status) return (-1); else @@ -170,12 +185,18 @@ dbm_delete(db, key) * 1 if DBM_INSERT and entry exists */ extern int -dbm_store(db, key, content, flags) +dbm_store(db, key, data, flags) DBM *db; - datum key, content; + datum key, data; int flags; { - return ((db->put)(db, (DBT *)&key, (DBT *)&content, + DBT dbtkey, dbtdata; + + dbtkey.data = key.dptr; + dbtkey.size = key.dsize; + dbtdata.data = data.dptr; + dbtdata.size = data.dsize; + return ((db->put)(db, &dbtkey, &dbtdata, (flags == DBM_INSERT) ? R_NOOVERWRITE : 0)); } diff --git a/lib/libc/db/hash/page.h b/lib/libc/db/hash/page.h index ed62d595dc1..0ea00b7aea6 100644 --- a/lib/libc/db/hash/page.h +++ b/lib/libc/db/hash/page.h @@ -1,4 +1,4 @@ -/* $NetBSD: page.h,v 1.5 1995/02/27 13:22:52 cgd Exp $ */ +/* $NetBSD: page.h,v 1.6 1996/05/03 21:43:59 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 diff --git a/lib/libc/db/hash/search.h b/lib/libc/db/hash/search.h index d11ac14eefb..b9f73132d8d 100644 --- a/lib/libc/db/hash/search.h +++ b/lib/libc/db/hash/search.h @@ -1,4 +1,4 @@ -/* $NetBSD: search.h,v 1.5 1995/02/27 13:22:58 cgd Exp $ */ +/* $NetBSD: search.h,v 1.6 1996/05/03 21:44:01 cgd Exp $ */ /*- * Copyright (c) 1990, 1993 diff --git a/lib/libc/db/man/btree.3 b/lib/libc/db/man/btree.3 index f0cd4eba8d6..7c74828975a 100644 --- a/lib/libc/db/man/btree.3 +++ b/lib/libc/db/man/btree.3 @@ -1,4 +1,4 @@ -.\" $NetBSD: btree.3,v 1.5 1995/02/27 13:23:18 cgd Exp $ +.\" $NetBSD: btree.3,v 1.6 1996/05/03 21:26:48 cgd Exp $ .\" .\" Copyright (c) 1990, 1993 .\" The Regents of the University of California. All rights reserved. @@ -31,9 +31,9 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.\" @(#)btree.3 8.3 (Berkeley) 2/21/94 +.\" @(#)btree.3 8.4 (Berkeley) 8/18/94 .\" -.TH BTREE 3 "February 21, 1994" +.TH BTREE 3 "August 18, 1994" .\".UC 7 .SH NAME btree \- btree database access method @@ -209,6 +209,13 @@ O lg base N where base is the average fill factor. Often, inserting ordered data into btrees results in a low fill factor. This implementation has been modified to make ordered insertion the best case, resulting in a much better than normal page fill factor. +.SH ERRORS +The +.I btree +access method routines may fail and set +.I errno +for any of the errors specified for the library routine +.IR dbopen (3). .SH "SEE ALSO" .IR dbopen (3), .IR hash (3), diff --git a/lib/libc/db/man/hash.3 b/lib/libc/db/man/hash.3 index 6d296a8f6d1..fcdb1f3af12 100644 --- a/lib/libc/db/man/hash.3 +++ b/lib/libc/db/man/hash.3 @@ -1,4 +1,4 @@ -.\" $NetBSD: hash.3,v 1.5 1995/02/27 13:23:31 cgd Exp $ +.\" $NetBSD: hash.3,v 1.6 1996/05/03 21:26:50 cgd Exp $ .\" .\" Copyright (c) 1990, 1993 .\" The Regents of the University of California. All rights reserved. @@ -31,9 +31,9 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.\" @(#)hash.3 8.5 (Berkeley) 2/21/94 +.\" @(#)hash.3 8.6 (Berkeley) 8/18/94 .\" -.TH HASH 3 "February 21, 1994" +.TH HASH 3 "August 18, 1994" .UC 7 .SH NAME hash \- hash database access method @@ -139,6 +139,13 @@ and .IR ndbm (3) are provided, however these interfaces are not compatible with previous file formats. +.SH ERRORS +The +.I hash +access method routines may fail and set +.I errno +for any of the errors specified for the library routine +.IR dbopen (3). .SH "SEE ALSO" .IR btree (3), .IR dbopen (3), diff --git a/lib/libc/db/man/recno.3 b/lib/libc/db/man/recno.3 index 63a366b645f..1fd42078053 100644 --- a/lib/libc/db/man/recno.3 +++ b/lib/libc/db/man/recno.3 @@ -1,4 +1,4 @@ -.\" $NetBSD: recno.3,v 1.5 1995/06/13 00:53:40 jtc Exp $ +.\" $NetBSD: recno.3,v 1.6 1996/05/03 21:26:51 cgd Exp $ .\" .\" Copyright (c) 1990, 1993 .\" The Regents of the University of California. All rights reserved. @@ -31,9 +31,9 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.\" @(#)recno.3 8.3 (Berkeley) 2/21/94 +.\" @(#)recno.3 8.5 (Berkeley) 8/18/94 .\" -.TH RECNO 3 "February 21, 1994" +.TH RECNO 3 "August 18, 1994" .UC 7 .SH NAME recno \- record number database access method @@ -99,6 +99,9 @@ The structure element specifies the length of the record, and the structure element .I bval is used as the pad character. +Any records, inserted into the database, that are less than +.I reclen +bytes long are automatically padded. .TP R_NOKEY In the interface specified by @@ -178,6 +181,11 @@ The .I size field of the key should be the size of that type. .PP +Because there can be no meta-data associated with the underlying +recno access method files, any changes made to the default values +(e.g. fixed record length or byte separator value) must be explicitly +specified each time the file is opened. +.PP In the interface specified by .IR dbopen , using the @@ -185,6 +193,18 @@ using the interface to create a new record will cause the creation of multiple, empty records if the record number is more than one greater than the largest record currently in the database. +.SH ERRORS +The +.I recno +access method routines may fail and set +.I errno +for any of the errors specified for the library routine +.IR dbopen (3) +or the following: +.TP +[EINVAL] +An attempt was made to add a record to a fixed-length database that +was too large to fit. .SH "SEE ALSO" .IR btree (3), .IR dbopen (3), diff --git a/lib/libc/db/mpool/mpool.c b/lib/libc/db/mpool/mpool.c index 6417c29d453..be04f45e56c 100644 --- a/lib/libc/db/mpool/mpool.c +++ b/lib/libc/db/mpool/mpool.c @@ -1,7 +1,7 @@ -/* $NetBSD: mpool.c,v 1.5 1995/02/27 13:24:05 cgd Exp $ */ +/* $NetBSD: mpool.c,v 1.6 1996/05/03 21:29:48 cgd Exp $ */ /*- - * Copyright (c) 1990, 1993 + * Copyright (c) 1990, 1993, 1994 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -35,13 +35,14 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)mpool.c 8.2 (Berkeley) 2/21/94"; +static char sccsid[] = "@(#)mpool.c 8.5 (Berkeley) 7/26/94"; #else -static char rcsid[] = "$NetBSD: mpool.c,v 1.5 1995/02/27 13:24:05 cgd Exp $"; +static char rcsid[] = "$NetBSD: mpool.c,v 1.6 1996/05/03 21:29:48 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ #include +#include #include #include @@ -51,31 +52,21 @@ static char rcsid[] = "$NetBSD: mpool.c,v 1.5 1995/02/27 13:24:05 cgd Exp $"; #include #include + #define __MPOOLINTERFACE_PRIVATE -#include "mpool.h" +#include static BKT *mpool_bkt __P((MPOOL *)); static BKT *mpool_look __P((MPOOL *, pgno_t)); static int mpool_write __P((MPOOL *, BKT *)); -#ifdef DEBUG -static void __mpoolerr __P((const char *fmt, ...)); -#endif /* - * MPOOL_OPEN -- initialize a memory pool. - * - * Parameters: - * key: Shared buffer key. - * fd: File descriptor. - * pagesize: File page size. - * maxcache: Max number of cached pages. - * - * Returns: - * MPOOL pointer, NULL on error. + * mpool_open -- + * Initialize a memory pool. */ MPOOL * mpool_open(key, fd, pagesize, maxcache) - DBT *key; + void *key; int fd; pgno_t pagesize, maxcache; { @@ -83,49 +74,35 @@ mpool_open(key, fd, pagesize, maxcache) MPOOL *mp; int entry; + /* + * Get information about the file. + * + * XXX + * We don't currently handle pipes, although we should. + */ if (fstat(fd, &sb)) return (NULL); - /* XXX - * We should only set st_size to 0 for pipes -- 4.4BSD has the fix so - * that stat(2) returns true for ISSOCK on pipes. Until then, this is - * fairly close. - */ if (!S_ISREG(sb.st_mode)) { errno = ESPIPE; return (NULL); } - if ((mp = (MPOOL *)malloc(sizeof(MPOOL))) == NULL) + /* Allocate and initialize the MPOOL cookie. */ + if ((mp = (MPOOL *)calloc(1, sizeof(MPOOL))) == NULL) return (NULL); - mp->free.cnext = mp->free.cprev = (BKT *)&mp->free; - mp->lru.cnext = mp->lru.cprev = (BKT *)&mp->lru; + CIRCLEQ_INIT(&mp->lqh); for (entry = 0; entry < HASHSIZE; ++entry) - mp->hashtable[entry].hnext = mp->hashtable[entry].hprev = - mp->hashtable[entry].cnext = mp->hashtable[entry].cprev = - (BKT *)&mp->hashtable[entry]; - mp->curcache = 0; + CIRCLEQ_INIT(&mp->hqh[entry]); mp->maxcache = maxcache; - mp->pagesize = pagesize; mp->npages = sb.st_size / pagesize; + mp->pagesize = pagesize; mp->fd = fd; - mp->pgcookie = NULL; - mp->pgin = mp->pgout = NULL; - -#ifdef STATISTICS - mp->cachehit = mp->cachemiss = mp->pagealloc = mp->pageflush = - mp->pageget = mp->pagenew = mp->pageput = mp->pageread = - mp->pagewrite = 0; -#endif return (mp); } /* - * MPOOL_FILTER -- initialize input/output filters. - * - * Parameters: - * pgin: Page in conversion routine. - * pgout: Page out conversion routine. - * pgcookie: Cookie for page in/out routines. + * mpool_filter -- + * Initialize input/output filters. */ void mpool_filter(mp, pgin, pgout, pgcookie) @@ -140,124 +117,128 @@ mpool_filter(mp, pgin, pgout, pgcookie) } /* - * MPOOL_NEW -- get a new page - * - * Parameters: - * mp: mpool cookie - * pgnoadddr: place to store new page number - * Returns: - * RET_ERROR, RET_SUCCESS + * mpool_new -- + * Get a new page of memory. */ void * mpool_new(mp, pgnoaddr) MPOOL *mp; pgno_t *pgnoaddr; { - BKT *b; - BKTHDR *hp; + struct _hqh *head; + BKT *bp; + if (mp->npages == MAX_PAGE_NUMBER) { + (void)fprintf(stderr, "mpool_new: page allocation overflow.\n"); + abort(); + } #ifdef STATISTICS ++mp->pagenew; #endif /* - * Get a BKT from the cache. Assign a new page number, attach it to - * the hash and lru chains and return. + * Get a BKT from the cache. Assign a new page number, attach + * it to the head of the hash chain, the tail of the lru chain, + * and return. */ - if ((b = mpool_bkt(mp)) == NULL) + if ((bp = mpool_bkt(mp)) == NULL) return (NULL); - *pgnoaddr = b->pgno = mp->npages++; - b->flags = MPOOL_PINNED; - inshash(b, b->pgno); - inschain(b, &mp->lru); - return (b->page); + *pgnoaddr = bp->pgno = mp->npages++; + bp->flags = MPOOL_PINNED; + + head = &mp->hqh[HASHKEY(bp->pgno)]; + CIRCLEQ_INSERT_HEAD(head, bp, hq); + CIRCLEQ_INSERT_TAIL(&mp->lqh, bp, q); + return (bp->page); } /* - * MPOOL_GET -- get a page from the pool - * - * Parameters: - * mp: mpool cookie - * pgno: page number - * flags: not used - * - * Returns: - * RET_ERROR, RET_SUCCESS + * mpool_get + * Get a page. */ void * mpool_get(mp, pgno, flags) MPOOL *mp; pgno_t pgno; - u_int flags; /* XXX not used? */ + u_int flags; /* XXX not used? */ { - BKT *b; - BKTHDR *hp; + struct _hqh *head; + BKT *bp; off_t off; int nr; - /* - * If asking for a specific page that is already in the cache, find - * it and return it. - */ - if (b = mpool_look(mp, pgno)) { + /* Check for attempt to retrieve a non-existent page. */ + if (pgno >= mp->npages) { + errno = EINVAL; + return (NULL); + } + #ifdef STATISTICS - ++mp->pageget; + ++mp->pageget; #endif + + /* Check for a page that is cached. */ + if ((bp = mpool_look(mp, pgno)) != NULL) { #ifdef DEBUG - if (b->flags & MPOOL_PINNED) - __mpoolerr("mpool_get: page %d already pinned", - b->pgno); + if (bp->flags & MPOOL_PINNED) { + (void)fprintf(stderr, + "mpool_get: page %d already pinned\n", bp->pgno); + abort(); + } #endif - rmchain(b); - inschain(b, &mp->lru); - b->flags |= MPOOL_PINNED; - return (b->page); - } - - /* Not allowed to retrieve a non-existent page. */ - if (pgno >= mp->npages) { - errno = EINVAL; - return (NULL); + /* + * Move the page to the head of the hash chain and the tail + * of the lru chain. + */ + head = &mp->hqh[HASHKEY(bp->pgno)]; + CIRCLEQ_REMOVE(head, bp, hq); + CIRCLEQ_INSERT_HEAD(head, bp, hq); + CIRCLEQ_REMOVE(&mp->lqh, bp, q); + CIRCLEQ_INSERT_TAIL(&mp->lqh, bp, q); + + /* Return a pinned page. */ + bp->flags |= MPOOL_PINNED; + return (bp->page); } /* Get a page from the cache. */ - if ((b = mpool_bkt(mp)) == NULL) + if ((bp = mpool_bkt(mp)) == NULL) return (NULL); - b->pgno = pgno; - b->flags = MPOOL_PINNED; + /* Read in the contents. */ #ifdef STATISTICS ++mp->pageread; #endif - /* Read in the contents. */ off = mp->pagesize * pgno; if (lseek(mp->fd, off, SEEK_SET) != off) return (NULL); - if ((nr = read(mp->fd, b->page, mp->pagesize)) != mp->pagesize) { + if ((nr = read(mp->fd, bp->page, mp->pagesize)) != mp->pagesize) { if (nr >= 0) errno = EFTYPE; return (NULL); } - if (mp->pgin) - (mp->pgin)(mp->pgcookie, b->pgno, b->page); - inshash(b, b->pgno); - inschain(b, &mp->lru); -#ifdef STATISTICS - ++mp->pageget; -#endif - return (b->page); + /* Set the page number, pin the page. */ + bp->pgno = pgno; + bp->flags = MPOOL_PINNED; + + /* + * Add the page to the head of the hash chain and the tail + * of the lru chain. + */ + head = &mp->hqh[HASHKEY(bp->pgno)]; + CIRCLEQ_INSERT_HEAD(head, bp, hq); + CIRCLEQ_INSERT_TAIL(&mp->lqh, bp, q); + + /* Run through the user's filter. */ + if (mp->pgin != NULL) + (mp->pgin)(mp->pgcookie, bp->pgno, bp->page); + + return (bp->page); } /* - * MPOOL_PUT -- return a page to the pool - * - * Parameters: - * mp: mpool cookie - * page: page pointer - * pgno: page number - * - * Returns: - * RET_ERROR, RET_SUCCESS + * mpool_put + * Return a page. */ int mpool_put(mp, page, flags) @@ -265,193 +246,172 @@ mpool_put(mp, page, flags) void *page; u_int flags; { - BKT *baddr; -#ifdef DEBUG - BKT *b; -#endif + BKT *bp; #ifdef STATISTICS ++mp->pageput; #endif - baddr = (BKT *)((char *)page - sizeof(BKT)); + bp = (BKT *)((char *)page - sizeof(BKT)); #ifdef DEBUG - if (!(baddr->flags & MPOOL_PINNED)) - __mpoolerr("mpool_put: page %d not pinned", b->pgno); - for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) { - if (b == (BKT *)&mp->lru) - __mpoolerr("mpool_put: %0x: bad address", baddr); - if (b == baddr) - break; + if (!(bp->flags & MPOOL_PINNED)) { + (void)fprintf(stderr, + "mpool_put: page %d not pinned\n", bp->pgno); + abort(); } #endif - baddr->flags &= ~MPOOL_PINNED; - baddr->flags |= flags & MPOOL_DIRTY; + bp->flags &= ~MPOOL_PINNED; + bp->flags |= flags & MPOOL_DIRTY; return (RET_SUCCESS); } /* - * MPOOL_CLOSE -- close the buffer pool - * - * Parameters: - * mp: mpool cookie - * - * Returns: - * RET_ERROR, RET_SUCCESS + * mpool_close + * Close the buffer pool. */ int mpool_close(mp) MPOOL *mp; { - BKT *b, *next; + BKT *bp; /* Free up any space allocated to the lru pages. */ - for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = next) { - next = b->cprev; - free(b); + while ((bp = mp->lqh.cqh_first) != (void *)&mp->lqh) { + CIRCLEQ_REMOVE(&mp->lqh, mp->lqh.cqh_first, q); + free(bp); } + + /* Free the MPOOL cookie. */ free(mp); return (RET_SUCCESS); } /* - * MPOOL_SYNC -- sync the file to disk. - * - * Parameters: - * mp: mpool cookie - * - * Returns: - * RET_ERROR, RET_SUCCESS + * mpool_sync + * Sync the pool to disk. */ int mpool_sync(mp) MPOOL *mp; { - BKT *b; + BKT *bp; - for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev) - if (b->flags & MPOOL_DIRTY && mpool_write(mp, b) == RET_ERROR) + /* Walk the lru chain, flushing any dirty pages to disk. */ + for (bp = mp->lqh.cqh_first; + bp != (void *)&mp->lqh; bp = bp->q.cqe_next) + if (bp->flags & MPOOL_DIRTY && + mpool_write(mp, bp) == RET_ERROR) return (RET_ERROR); + + /* Sync the file descriptor. */ return (fsync(mp->fd) ? RET_ERROR : RET_SUCCESS); } /* - * MPOOL_BKT -- get/create a BKT from the cache - * - * Parameters: - * mp: mpool cookie - * - * Returns: - * NULL on failure and a pointer to the BKT on success + * mpool_bkt + * Get a page from the cache (or create one). */ static BKT * mpool_bkt(mp) MPOOL *mp; { - BKT *b; + struct _hqh *head; + BKT *bp; + /* If under the max cached, always create a new page. */ if (mp->curcache < mp->maxcache) goto new; /* - * If the cache is maxxed out, search the lru list for a buffer we - * can flush. If we find one, write it if necessary and take it off - * any lists. If we don't find anything we grow the cache anyway. + * If the cache is max'd out, walk the lru list for a buffer we + * can flush. If we find one, write it (if necessary) and take it + * off any lists. If we don't find anything we grow the cache anyway. * The cache never shrinks. */ - for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev) - if (!(b->flags & MPOOL_PINNED)) { - if (b->flags & MPOOL_DIRTY && - mpool_write(mp, b) == RET_ERROR) + for (bp = mp->lqh.cqh_first; + bp != (void *)&mp->lqh; bp = bp->q.cqe_next) + if (!(bp->flags & MPOOL_PINNED)) { + /* Flush if dirty. */ + if (bp->flags & MPOOL_DIRTY && + mpool_write(mp, bp) == RET_ERROR) return (NULL); - rmhash(b); - rmchain(b); #ifdef STATISTICS ++mp->pageflush; #endif + /* Remove from the hash and lru queues. */ + head = &mp->hqh[HASHKEY(bp->pgno)]; + CIRCLEQ_REMOVE(head, bp, hq); + CIRCLEQ_REMOVE(&mp->lqh, bp, q); #ifdef DEBUG - { - void *spage; - spage = b->page; - memset(b, 0xff, sizeof(BKT) + mp->pagesize); - b->page = spage; + { void *spage; + spage = bp->page; + memset(bp, 0xff, sizeof(BKT) + mp->pagesize); + bp->page = spage; } #endif - return (b); + return (bp); } -new: if ((b = (BKT *)malloc(sizeof(BKT) + mp->pagesize)) == NULL) +new: if ((bp = (BKT *)malloc(sizeof(BKT) + mp->pagesize)) == NULL) return (NULL); #ifdef STATISTICS ++mp->pagealloc; #endif -#ifdef DEBUG - memset(b, 0xff, sizeof(BKT) + mp->pagesize); +#if defined(DEBUG) || defined(PURIFY) + memset(bp, 0xff, sizeof(BKT) + mp->pagesize); #endif - b->page = (char *)b + sizeof(BKT); + bp->page = (char *)bp + sizeof(BKT); ++mp->curcache; - return (b); + return (bp); } /* - * MPOOL_WRITE -- sync a page to disk - * - * Parameters: - * mp: mpool cookie - * - * Returns: - * RET_ERROR, RET_SUCCESS + * mpool_write + * Write a page to disk. */ static int -mpool_write(mp, b) +mpool_write(mp, bp) MPOOL *mp; - BKT *b; + BKT *bp; { off_t off; - if (mp->pgout) - (mp->pgout)(mp->pgcookie, b->pgno, b->page); - #ifdef STATISTICS ++mp->pagewrite; #endif - off = mp->pagesize * b->pgno; + + /* Run through the user's filter. */ + if (mp->pgout) + (mp->pgout)(mp->pgcookie, bp->pgno, bp->page); + + off = mp->pagesize * bp->pgno; if (lseek(mp->fd, off, SEEK_SET) != off) return (RET_ERROR); - if (write(mp->fd, b->page, mp->pagesize) != mp->pagesize) + if (write(mp->fd, bp->page, mp->pagesize) != mp->pagesize) return (RET_ERROR); - b->flags &= ~MPOOL_DIRTY; + + bp->flags &= ~MPOOL_DIRTY; return (RET_SUCCESS); } /* - * MPOOL_LOOK -- lookup a page - * - * Parameters: - * mp: mpool cookie - * pgno: page number - * - * Returns: - * NULL on failure and a pointer to the BKT on success + * mpool_look + * Lookup a page in the cache. */ static BKT * mpool_look(mp, pgno) MPOOL *mp; pgno_t pgno; { - register BKT *b; - register BKTHDR *tb; + struct _hqh *head; + BKT *bp; - /* XXX - * If find the buffer, put it first on the hash chain so can - * find it again quickly. - */ - tb = &mp->hashtable[HASHKEY(pgno)]; - for (b = tb->hnext; b != (BKT *)tb; b = b->hnext) - if (b->pgno == pgno) { + head = &mp->hqh[HASHKEY(pgno)]; + for (bp = head->cqh_first; bp != (void *)head; bp = bp->hq.cqe_next) + if (bp->pgno == pgno) { #ifdef STATISTICS ++mp->cachehit; #endif - return (b); + return (bp); } #ifdef STATISTICS ++mp->cachemiss; @@ -461,16 +421,14 @@ mpool_look(mp, pgno) #ifdef STATISTICS /* - * MPOOL_STAT -- cache statistics - * - * Parameters: - * mp: mpool cookie + * mpool_stat + * Print out cache statistics. */ void mpool_stat(mp) MPOOL *mp; { - BKT *b; + BKT *bp; int cnt; char *sep; @@ -492,11 +450,12 @@ mpool_stat(mp) sep = ""; cnt = 0; - for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) { - (void)fprintf(stderr, "%s%d", sep, b->pgno); - if (b->flags & MPOOL_DIRTY) + for (bp = mp->lqh.cqh_first; + bp != (void *)&mp->lqh; bp = bp->q.cqe_next) { + (void)fprintf(stderr, "%s%d", sep, bp->pgno); + if (bp->flags & MPOOL_DIRTY) (void)fprintf(stderr, "d"); - if (b->flags & MPOOL_PINNED) + if (bp->flags & MPOOL_PINNED) (void)fprintf(stderr, "P"); if (++cnt == 10) { sep = "\n"; @@ -508,33 +467,3 @@ mpool_stat(mp) (void)fprintf(stderr, "\n"); } #endif - -#ifdef DEBUG -#if __STDC__ -#include -#else -#include -#endif - -static void -#if __STDC__ -__mpoolerr(const char *fmt, ...) -#else -__mpoolerr(fmt, va_alist) - char *fmt; - va_dcl -#endif -{ - va_list ap; -#if __STDC__ - va_start(ap, fmt); -#else - va_start(ap); -#endif - (void)vfprintf(stderr, fmt, ap); - va_end(ap); - (void)fprintf(stderr, "\n"); - abort(); - /* NOTREACHED */ -} -#endif diff --git a/lib/libc/db/mpool/mpool.libtp b/lib/libc/db/mpool/mpool.libtp new file mode 100644 index 00000000000..3ab0c8f835c --- /dev/null +++ b/lib/libc/db/mpool/mpool.libtp @@ -0,0 +1,746 @@ +/****************************************************************************** + +VERSION $Id: mpool.libtp,v 1.1 1996/05/07 09:02:01 deraadt Exp $ +PACKAGE: User Level Shared Memory Manager + +DESCRIPTION: + This package provides a buffer pool interface implemented as + a collection of file pages mapped into shared memory. + + Based on Mark's buffer manager + +ROUTINES: + External + buf_alloc + buf_flags + buf_get + buf_init + buf_last + buf_open + buf_pin + buf_sync + buf_unpin + Internal + bf_assign_buf + bf_fid_to_fd + bf_newbuf + bf_put_page + + +******************************************************************************/ +#include +#include +#include +#include +#include +#include +#include "list.h" +#include "user.h" +#include "txn_sys.h" +#include "buf.h" +#include "semkeys.h" +#include "error.h" + +/* + we need to translate between some type of file id that the user + process passes and a file descriptor. For now, it's a nop. +*/ +#define GET_MASTER get_sem ( buf_spinlock ) +#define RELEASE_MASTER release_sem ( buf_spinlock ) + +#define LRUID *buf_lru +#define LRUP (bufhdr_table+*buf_lru) +#define MRU bufhdr_table[*buf_lru].lru.prev + +/* Global indicator that you have started reusing buffers */ +int do_statistics = 0; +/* + Process Statics (pointers into shared memory) +*/ +static BUF_T *buf_table = 0; +static BUFHDR_T *bufhdr_table; +static int *buf_hash_table; +static int *buf_lru; /* LRU is the free list */ +static int buf_spinlock; +static FINFO_T *buf_fids; +static int *buf_sp; /* Pointer to string free space */ +static char *buf_strings; + +/* Process Local FID->FD table */ +static int fds[NUM_FILE_ENTRIES]; + +/* Static routines */ +static BUFHDR_T *bf_assign_buf(); +static int bf_fid_to_fd(); +static BUFHDR_T *bf_newbuf(); +static int bf_put_page(); + +/* + Return 0 on success + 1 on failure +*/ +extern int +buf_init ( ) +{ + ADDR_T buf_region; + BUFHDR_T *bhp; + int i; + int ref_count; + int *spinlockp; + + /* + Initialize Process local structures + */ + for ( i = 0; i < NUM_FILE_ENTRIES; i++ ) { + fds[i] = -1; + } + + buf_region = attach_region ( BUF_REGION_NAME, BUF_REGION_NUM, + BUF_REGION_SIZE, &ref_count ); + if ( !buf_region ) { + return (1); + } + error_log3 ( "Buf Region: ADDR: %d ID: %d SIZE: %d\n", buf_region, + BUF_REGION_NUM, BUF_REGION_SIZE ); + + buf_table = (BUF_T *)buf_region; + bufhdr_table = (BUFHDR_T *)(buf_table + NUM_BUFS); + buf_hash_table = (int *)(bufhdr_table + NUM_BUFS); + buf_lru = buf_hash_table + NUMTABLE_ENTRIES; + spinlockp = buf_lru + 1; + buf_fids = (FINFO_T *)(spinlockp+1); + buf_sp = (int *)(buf_fids + NUM_FILE_ENTRIES); + buf_strings = (char *)(buf_sp + 1); + + /* Create locking spinlock (gets creating holding the lock) */ + buf_spinlock = create_sem ( BUF_SPIN_NAME, BUF_SPIN_NUM, ref_count <= 1 ); + if ( buf_spinlock < 0 ) { + return(1); + } + if ( ref_count <= 1 ) { + *spinlockp = buf_spinlock; + + /* Now initialize the buffer manager */ + + /* 1. Free list */ + *buf_lru = 0; + + /* 2. Buffer headers */ + for ( i = 0, bhp = bufhdr_table; i < NUM_BUFS; bhp++, i++ ) { + bhp->lru.next = i+1; + bhp->lru.prev = i-1; + bhp->flags = 0; /* All Flags off */ + bhp->refcount = 0; + bhp->wait_proc = -1; /* No sleepers */ + LISTPE_INIT ( hash, bhp, i ); /* Hash chains */ + } + bufhdr_table[0].lru.prev = NUM_BUFS-1; + bufhdr_table[NUM_BUFS-1].lru.next = 0; + + /* 3. Hash Table */ + for ( i = 0; i < NUMTABLE_ENTRIES; i++ ) { + buf_hash_table[i] = NUM_BUFS; + } + + /* 4. File ID Table */ + for ( i = 0; i < NUM_FILE_ENTRIES; i++ ) { + buf_fids[i].offset = -1; + buf_fids[i].npages = -1; + buf_fids[i].refcount = 0; + } + + /* 5. Free String Pointer */ + *buf_sp = (FILE_NAME_LEN*NUM_FILE_ENTRIES); + if (RELEASE_MASTER) { + return(1); + } + error_log0 ( "Initialized buffer region\n" ); + } + return (0); +} + +extern void +buf_exit() +{ + int ref; + int i; + + /* Flush Buffer Pool on Exit */ + for ( i = 0; i < NUM_FILE_ENTRIES; i++ ) { + if ( fds[i] != -1 ) { + close ( fds[i] ); + } + } + if ( buf_table ) { + detach_region ( buf_table, BUF_REGION_NUM, BUF_REGION_SIZE, &ref ); + } + return; +} + +/* + We need an empty buffer. Find the LRU unpinned NON-Dirty page. +*/ +static BUFHDR_T * +bf_newbuf() +{ + int fd; + int lruid; + int nbytes; + int ndx; + BUFHDR_T *bhp; + + lruid = LRUID; + for ( bhp = LRUP; + bhp->flags & (BUF_PINNED|BUF_IO_IN_PROGRESS); + bhp = LISTP_NEXTP (bufhdr_table, lru, bhp ) ) { + + if ( bhp->lru.next == lruid ) { + /* OUT OF BUFFERS */ + error_log1 ( "All buffers are pinned. %s\n", + "Unable to grant buffer request" ); + return(NULL); + } + } + /* BHP can be used */ + if ( bhp->flags & BUF_DIRTY ) { + do_statistics = 1; + /* + MIS Check for log flushed appropriately + */ + fd = bf_fid_to_fd(bhp->id.file_id); + if ( fd == -1 ) { + error_log1 ("Invalid fid %d\n", bhp->id.file_id); + return(NULL); + } + if ( bf_put_page(fd, bhp) < 0 ) { + return(NULL); + } + } + /* Update Hash Pointers */ + ndx = BUF_HASH ( bhp->id.file_id, bhp->id.obj_id ); + LISTP_REMOVE(bufhdr_table, hash, bhp); + if ( buf_hash_table[ndx] == (bhp-bufhdr_table) ) { + if ( bhp->hash.next != (bhp-bufhdr_table) ) { + buf_hash_table[ndx] = bhp->hash.next; + } else { + buf_hash_table[ndx] = NUM_BUFS; + } + } + INIT_BUF(bhp); + + return(bhp); +} +/* + buf_alloc + + Add a page to a file and return a buffer for it. + +*/ +ADDR_T +buf_alloc ( fid, new_pageno ) +int fid; +int *new_pageno; +{ + BUFHDR_T *bhp; + int fd; + int len; + int ndx; + OBJ_T fobj; + + if (GET_MASTER) { + return(NULL); + } + if ( buf_fids[fid].npages == -1 ) { + /* initialize npages field */ + fd = bf_fid_to_fd ( fid ); + } + assert (fid < NUM_FILE_ENTRIES); + + *new_pageno = buf_fids[fid].npages; + if ( *new_pageno == -1 ) { + RELEASE_MASTER; + return ( NULL ); + } + buf_fids[fid].npages++; + ndx = BUF_HASH ( fid, *new_pageno ); + fobj.file_id = fid; + fobj.obj_id = *new_pageno; + bhp = bf_assign_buf ( ndx, &fobj, BF_PIN|BF_DIRTY|BF_EMPTY, &len ); + if ( RELEASE_MASTER ) { + /* Memory leak */ + return(NULL); + } + if ( bhp ) { + return ((ADDR_T)(buf_table+(bhp-bufhdr_table))); + } else { + return ( NULL ); + } +} + + +/* + Buffer Flags + BF_DIRTY Mark page as dirty + BF_EMPTY Don't initialize page, just get buffer + BF_PIN Retrieve with pin + +MIS +Might want to add a flag that sets an LSN for this buffer is the +DIRTY flag is set + +Eventually, you may want a flag that indicates the I/O and lock +request should be shipped off together, but not for now. +*/ +extern ADDR_T +buf_get ( file_id, page_id, flags, len ) +int file_id; +int page_id; +u_long flags; +int *len; /* Number of bytes read into buffer */ +{ + BUFHDR_T *bhp; + int bufid; + int fd; + int ndx; + int next_bufid; + int stat; + OBJ_T fobj; + + ndx = BUF_HASH ( file_id, page_id ); + fobj.file_id = (long) file_id; + fobj.obj_id = (long) page_id; + if ( GET_MASTER ) { + return(NULL); + } + /* + This could be a for loop, but we lose speed + by making all the cases general purpose so we + optimize for the no-collision case. + */ + bufid = buf_hash_table[ndx]; + if ( bufid < NUM_BUFS ) { + for ( bhp = bufhdr_table+bufid; + !OBJ_EQ (bhp->id, fobj) || !(bhp->flags & BUF_VALID); + bhp = LISTP_NEXTP ( bufhdr_table, hash, bhp ) ) { + + if ( bhp->hash.next == bufid ) { + goto not_found; + } + } +/* found */ + if ( flags & BF_PIN ) { + bhp->flags |= BUF_PINNED; + bhp->refcount++; +#ifdef PIN_DEBUG + fprintf(stderr, "buf_get: %X PINNED (%d)\n", + buf_table + (bhp-bufhdr_table), bhp->refcount); +#endif + } + if ( flags & BF_DIRTY ) { + bhp->flags |= BUF_DIRTY; + } + + while ( bhp->flags & BUF_IO_IN_PROGRESS ) { + /* MIS -- eventually err check here */ +#ifdef DEBUG + printf("About to sleep on %d (me: %d\n)\n", bhp->wait_proc, + my_txnp - txn_table); +#endif +#ifdef WAIT_STATS + buf_waits++; +#endif + stat = proc_sleep_on ( &(bhp->wait_proc), buf_spinlock ); + if ( stat ) { + /* Memory leak */ + return(NULL); + } + if (!( bhp->flags & BUF_IO_IN_PROGRESS) && + (!OBJ_EQ (bhp->id, fobj) || !(bhp->flags & BUF_VALID))) { + if (RELEASE_MASTER) + return(NULL); + return(buf_get ( file_id, page_id, flags, len )); + } + } + MAKE_MRU( bhp ); + *len = BUFSIZE; + } else { +not_found: + /* If you get here, the page isn't in the hash table */ + bhp = bf_assign_buf ( ndx, &fobj, flags, len ); + } + /* Common code between found and not found */ + + if ( bhp && bhp->flags & BUF_NEWPAGE ) { + *len = 0; + } + if (RELEASE_MASTER){ + /* Memory leak */ + return(NULL); + } + if ( bhp ) { + return ((ADDR_T)(buf_table+(bhp-bufhdr_table))); + } else { + return ( NULL ); + } +} + +/* + MIS - do I want to add file links to buffer pool? +*/ +extern int +buf_sync ( fid, close ) +int fid; +int close; /* should we dec refcount and possibly + invalidate all the buffers */ +{ + int i; + int fd; + int invalidate; + BUFHDR_T *bhp; + + if ( (fd = bf_fid_to_fd ( fid )) < 0 ) { + return(1); + } + if (GET_MASTER) { + return(1); + } + invalidate = (buf_fids[fid].refcount == 1 && close); + if ( invalidate ) + for ( bhp = bufhdr_table, i = 0; i < NUM_BUFS; bhp++, i++ ) { + if (bhp->id.file_id == fid) { + if ((bhp->flags & BF_DIRTY) && (bf_put_page( fd, bhp ) < 0)) { + return(1); + } + bhp->id.file_id = -1; + } + } + if (invalidate || close) + buf_fids[fid].refcount--; + + if (RELEASE_MASTER) { + return(1); + } + return(0); + + +} + +extern int +buf_flags ( addr, set_flags, unset_flags ) +ADDR_T addr; +u_long set_flags; +u_long unset_flags; +{ + int bufid; + BUFHDR_T *bhp; + +#ifdef PIN_DEBUG + fprintf(stderr, "buf_flags: %X setting %s%s%s%s%s releasing %s%s%s%s%s\n", + addr, + set_flags&BUF_DIRTY ? "DIRTY " : "", + set_flags&BUF_VALID ? "VALID " : "", + set_flags&BUF_PINNED ? "PINNED " : "", + set_flags&BUF_IO_ERROR ? "IO_ERROR " : "", + set_flags&BUF_IO_IN_PROGRESS ? "IO_IN_PROG " : "", + set_flags&BUF_NEWPAGE ? "NEWPAGE " : "", + unset_flags&BUF_DIRTY ? "DIRTY " : "", + unset_flags&BUF_VALID ? "VALID " : "", + unset_flags&BUF_PINNED ? "PINNED " : "", + unset_flags&BUF_IO_ERROR ? "IO_ERROR " : "", + unset_flags&BUF_IO_IN_PROGRESS ? "IO_IN_PROG " : "", + unset_flags&BUF_NEWPAGE ? "NEWPAGE " : "" ); +#endif + if (!ADDR_OK(addr)) { + error_log1 ( "buf_pin: Invalid Buffer Address %x\n", addr ); + return(1); + } + bufid = ((BUF_T *)addr) - buf_table; + assert ( bufid < NUM_BUFS); + bhp = &bufhdr_table[bufid]; + if (GET_MASTER) { + return(1); + } + bhp->flags |= set_flags; + if ( set_flags & BUF_PINNED ) { + bhp->refcount++; + } + if ( set_flags & BUF_DIRTY ) { + unset_flags |= BUF_NEWPAGE; + } + + if ( unset_flags & BUF_PINNED ) { + bhp->refcount--; + if ( bhp->refcount ) { + /* Turn off pin bit so it doesn't get unset */ + unset_flags &= ~BUF_PINNED; + } + } + bhp->flags &= ~unset_flags; + MAKE_MRU(bhp); + if (RELEASE_MASTER) { + return(1); + } + return(0); +} + +/* + Take a string name and produce an fid. + + returns -1 on error + + MIS -- this is a potential problem -- you keep actual names + here -- what if people run from different directories? +*/ +extern int +buf_name_lookup ( fname ) +char *fname; +{ + int i; + int fid; + int ndx; + + fid = -1; + if (GET_MASTER) { + return(-1); + } + for ( i = 0; i < NUM_FILE_ENTRIES; i++ ) { + if ( buf_fids[i].offset == -1 ) { + fid = i; + } else { + if (!strcmp (fname, buf_strings+buf_fids[i].offset)) { + if (RELEASE_MASTER) { + return(-1); + } + buf_fids[i].refcount++; + return(i); + } + } + } + if ( fid == -1 ) { + error_log0 ( "No more file ID's\n" ); + } else { + ndx = *buf_sp - strlen(fname) - 1; + if ( ndx < 0 ) { + error_log0 ( "Out of string space\n" ); + fid = -1; + } else { + *buf_sp = ndx; + strcpy ( buf_strings+ndx, fname ); + buf_fids[fid].offset = ndx; + } + buf_fids[fid].refcount = 1; + } + if (RELEASE_MASTER) { + return(-1); + } + return(fid); +} + +static int +bf_fid_to_fd ( fid ) +int fid; +{ + struct stat sbuf; + + assert ( (fid < NUM_FILE_ENTRIES) && (buf_fids[fid].offset != -1) ); + if ( fds[fid] != -1 ) { + return(fds[fid]); + + } + fds[fid] = open ( buf_strings+buf_fids[fid].offset, O_RDWR|O_CREAT, + 0666 ); + if ( fds[fid] < 0 ) { + error_log3 ( "Error Opening File %s FID: %d FD: %d. Errno = %d\n", + buf_strings+buf_fids[fid].offset, fid, fds[fid], + errno ); + return(-1); + } + error_log3 ( "Opening File %s FID: %d FD: %d\n", + buf_strings+buf_fids[fid].offset, fid, fds[fid] ); + if ( buf_fids[fid].npages == -1 ) { + /* Initialize the npages field */ + if ( fstat ( fds[fid], &sbuf ) ) { + error_log3 ( "Error Fstating %s FID: %d. Errno = %d\n", + buf_strings+buf_fids[fid].offset, fid, errno ); + } else { + buf_fids[fid].npages = ( sbuf.st_size / BUFSIZE ); + } + } + + return ( fds[fid] ); +} + +static int +bf_put_page ( fd, bhp ) +int fd; +BUFHDR_T *bhp; +{ + int nbytes; + + assert ( (bhp-bufhdr_table) < NUM_BUFS ); + if ( lseek ( fd, bhp->id.obj_id << BUFSHIFT, L_SET ) < 0 ) { + return(-1); + } + bhp->flags |= BUF_IO_IN_PROGRESS; + if (RELEASE_MASTER) { + return(-1); + } + nbytes = write(fd, buf_table[bhp-bufhdr_table], BUFSIZE); + if (GET_MASTER) { + return(-2); + } + if ( nbytes < 0 ) { + error_log1 ("Write failed with error code %d\n", errno); + return(-1); + } else if ( nbytes != BUFSIZE ) { + error_log1 ("Short write: %d bytes of %d\n", nbytes, BUFSIZE ); + } + bhp->flags &= ~(BUF_DIRTY|BUF_IO_IN_PROGRESS); + return (0); +} + +static BUFHDR_T * +bf_assign_buf ( ndx, obj, flags, len ) +int ndx; +OBJ_T *obj; +u_long flags; +int *len; /* Number of bytes read */ +{ + BUFHDR_T *bhp; + int fd; + + assert ( obj->file_id < NUM_FILE_ENTRIES ); + bhp = bf_newbuf(); + if ( !bhp ) { + return(NULL); + } + OBJ_ASSIGN ( (*obj), bhp->id ); + if ( buf_hash_table[ndx] >= NUM_BUFS ) { + buf_hash_table[ndx] = bhp-bufhdr_table; + } else { + LISTPE_INSERT ( bufhdr_table, hash, bhp, buf_hash_table[ndx] ); + } + + bhp->flags |= BUF_VALID; + if ( flags & BF_PIN ) { + bhp->flags |= BUF_PINNED; + bhp->refcount++; +#ifdef PIN_DEBUG + fprintf(stderr, "bf_assign_buf: %X PINNED (%d)\n", + buf_table + (bhp-bufhdr_table), bhp->refcount); +#endif + } + fd = bf_fid_to_fd(obj->file_id); + if ( fd == -1 ) { + error_log1 ("Invalid fid %d\n", obj->file_id); + bhp->flags |= ~BUF_IO_ERROR; + return(NULL); + } + if ( obj->obj_id >= buf_fids[obj->file_id].npages) { + buf_fids[obj->file_id].npages = obj->obj_id+1; + *len = 0; + } else if ( flags & BF_EMPTY ) { + *len = 0; + } else { + bhp->flags |= BUF_IO_IN_PROGRESS; + if (RELEASE_MASTER) { + return(NULL); + } + if ( lseek ( fd, obj->obj_id << BUFSHIFT, L_SET ) < -1 ) { + error_log2 ("Unable to perform seek on file: %d to page %d", + obj->file_id, obj->obj_id ); + bhp->flags &= ~BUF_IO_IN_PROGRESS; + bhp->flags |= ~BUF_IO_ERROR; + return(NULL); + } + *len = read(fd, buf_table[bhp-bufhdr_table], BUFSIZE); + if ( *len < 0 ) { + error_log2 ("Unable to perform read on file: %d to page %d", + obj->file_id, obj->obj_id ); + bhp->flags &= ~BUF_IO_IN_PROGRESS; + bhp->flags |= ~BUF_IO_ERROR; + return(NULL); + } + if (GET_MASTER) { + return(NULL); + } + bhp->flags &= ~BUF_IO_IN_PROGRESS; + if ( bhp->wait_proc != -1 ) { + /* wake up waiter and anyone waiting on it */ +#ifdef DEBUG + printf("Waking transaction %d due to completed I/O\n", + bhp->wait_proc); +#endif + proc_wake_id ( bhp->wait_proc ); + bhp->wait_proc = -1; + } + MAKE_MRU(bhp); + } + + if ( flags & BF_DIRTY ) { + bhp->flags |= BUF_DIRTY; + } else if ( *len < BUFSIZE ) { + bhp->flags |= BUF_NEWPAGE; + } + return ( bhp ); +} + +int +buf_last ( fid ) +int fid; +{ + int val; + + if (GET_MASTER) { + return(-1); + } + assert ( fid < NUM_FILE_ENTRIES ); + if ( buf_fids[fid].npages == -1 ) { + /* initialize npages field */ + (void) bf_fid_to_fd ( fid ); + } + val = buf_fids[fid].npages; + if ( val ) { + val--; /* Convert to page number */ + } + if (RELEASE_MASTER) { + return(-1); + } + return(val); +} + +#ifdef DEBUG +extern void +buf_dump ( id, all ) +int id; +int all; +{ + int i; + BUFHDR_T *bhp; + + printf ( "LRU + %d\n", *buf_lru ); + if ( all ) { + printf("ID\tFID\tPID\tLNEXT\tLPREV\tHNEXT\tHPREV\tSLEEP\tFLAG\tREFS\n"); + for ( bhp = bufhdr_table, i = 0; i < NUM_BUFS; bhp++, i++ ) { + printf ( "%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%x\t%d\n", i, + bhp->id.file_id, bhp->id.obj_id, + bhp->lru.next, bhp->lru.prev, + bhp->hash.next, bhp->hash.prev, + bhp->wait_proc, bhp->flags, bhp->refcount ); + } + } else { + if ( id >= NUM_BUFS ) { + printf ( "Buffer ID (%d) too high\n", id ); + return; + } + bhp = bufhdr_table+id; + printf ( "%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%x\t%d\n", i, + bhp->id.file_id, bhp->id.obj_id, + bhp->lru.next, bhp->lru.prev, + bhp->hash.next, bhp->hash.prev, + bhp->wait_proc, bhp->flags, bhp->refcount ); + } + return; +} +#endif + diff --git a/lib/libc/db/recno/Makefile.inc b/lib/libc/db/recno/Makefile.inc index c0fd31125a1..e7f78f4ce76 100644 --- a/lib/libc/db/recno/Makefile.inc +++ b/lib/libc/db/recno/Makefile.inc @@ -1,4 +1,4 @@ -# $NetBSD: Makefile.inc,v 1.4 1995/02/27 13:24:22 cgd Exp $ +# $NetBSD: Makefile.inc,v 1.5 1996/05/03 21:38:43 cgd Exp $ # @(#)Makefile.inc 8.1 (Berkeley) 6/4/93 .PATH: ${.CURDIR}/db/recno diff --git a/lib/libc/db/recno/extern.h b/lib/libc/db/recno/extern.h index 5ec5d2f220c..39d8d6379ab 100644 --- a/lib/libc/db/recno/extern.h +++ b/lib/libc/db/recno/extern.h @@ -1,4 +1,4 @@ -/* $NetBSD: extern.h,v 1.4 1995/02/27 13:24:30 cgd Exp $ */ +/* $NetBSD: extern.h,v 1.5 1996/05/03 21:38:44 cgd Exp $ */ /*- * Copyright (c) 1991, 1993 diff --git a/lib/libc/db/recno/rec_close.c b/lib/libc/db/recno/rec_close.c index 7c4dc283525..b8894afd732 100644 --- a/lib/libc/db/recno/rec_close.c +++ b/lib/libc/db/recno/rec_close.c @@ -1,7 +1,7 @@ -/* $NetBSD: rec_close.c,v 1.6 1995/02/27 13:24:37 cgd Exp $ */ +/* $NetBSD: rec_close.c,v 1.7 1996/05/03 21:38:45 cgd Exp $ */ /*- - * Copyright (c) 1990, 1993 + * Copyright (c) 1990, 1993, 1994 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -35,9 +35,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)rec_close.c 8.3 (Berkeley) 2/21/94"; +static char sccsid[] = "@(#)rec_close.c 8.6 (Berkeley) 8/18/94"; #else -static char rcsid[] = "$NetBSD: rec_close.c,v 1.6 1995/02/27 13:24:37 cgd Exp $"; +static char rcsid[] = "$NetBSD: rec_close.c,v 1.7 1996/05/03 21:38:45 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -82,11 +82,11 @@ __rec_close(dbp) /* Committed to closing. */ status = RET_SUCCESS; - if (ISSET(t, R_MEMMAPPED) && munmap(t->bt_smap, t->bt_msize)) + if (F_ISSET(t, R_MEMMAPPED) && munmap(t->bt_smap, t->bt_msize)) status = RET_ERROR; - if (!ISSET(t, R_INMEM)) - if (ISSET(t, R_CLOSEFP)) { + if (!F_ISSET(t, R_INMEM)) + if (F_ISSET(t, R_CLOSEFP)) { if (fclose(t->bt_rfp)) status = RET_ERROR; } else @@ -131,39 +131,58 @@ __rec_sync(dbp, flags) if (flags == R_RECNOSYNC) return (__bt_sync(dbp, 0)); - if (ISSET(t, R_RDONLY | R_INMEM) || !ISSET(t, R_MODIFIED)) + if (F_ISSET(t, R_RDONLY | R_INMEM) || !F_ISSET(t, R_MODIFIED)) return (RET_SUCCESS); /* Read any remaining records into the tree. */ - if (!ISSET(t, R_EOF) && t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR) + if (!F_ISSET(t, R_EOF) && t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR) return (RET_ERROR); /* Rewind the file descriptor. */ if (lseek(t->bt_rfd, (off_t)0, SEEK_SET) != 0) return (RET_ERROR); - iov[1].iov_base = "\n"; - iov[1].iov_len = 1; - scursor = t->bt_rcursor; + /* Save the cursor. */ + scursor = t->bt_cursor.rcursor; key.size = sizeof(recno_t); key.data = &trec; - status = (dbp->seq)(dbp, &key, &data, R_FIRST); - while (status == RET_SUCCESS) { - iov[0].iov_base = data.data; - iov[0].iov_len = data.size; - if (writev(t->bt_rfd, iov, 2) != data.size + 1) - return (RET_ERROR); - status = (dbp->seq)(dbp, &key, &data, R_NEXT); - } - t->bt_rcursor = scursor; + if (F_ISSET(t, R_FIXLEN)) { + /* + * We assume that fixed length records are all fixed length. + * Any that aren't are either EINVAL'd or corrected by the + * record put code. + */ + status = (dbp->seq)(dbp, &key, &data, R_FIRST); + while (status == RET_SUCCESS) { + if (write(t->bt_rfd, data.data, data.size) != data.size) + return (RET_ERROR); + status = (dbp->seq)(dbp, &key, &data, R_NEXT); + } + } else { + iov[1].iov_base = &t->bt_bval; + iov[1].iov_len = 1; + + status = (dbp->seq)(dbp, &key, &data, R_FIRST); + while (status == RET_SUCCESS) { + iov[0].iov_base = data.data; + iov[0].iov_len = data.size; + if (writev(t->bt_rfd, iov, 2) != data.size + 1) + return (RET_ERROR); + status = (dbp->seq)(dbp, &key, &data, R_NEXT); + } + } + + /* Restore the cursor. */ + t->bt_cursor.rcursor = scursor; + if (status == RET_ERROR) return (RET_ERROR); if ((off = lseek(t->bt_rfd, (off_t)0, SEEK_CUR)) == -1) return (RET_ERROR); if (ftruncate(t->bt_rfd, off)) return (RET_ERROR); - CLR(t, R_MODIFIED); + F_CLR(t, R_MODIFIED); return (RET_SUCCESS); } diff --git a/lib/libc/db/recno/rec_delete.c b/lib/libc/db/recno/rec_delete.c index 6f438a35cd9..3c6d48e698f 100644 --- a/lib/libc/db/recno/rec_delete.c +++ b/lib/libc/db/recno/rec_delete.c @@ -1,4 +1,4 @@ -/* $NetBSD: rec_delete.c,v 1.7 1995/02/27 13:24:48 cgd Exp $ */ +/* $NetBSD: rec_delete.c,v 1.8 1996/05/03 21:38:46 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)rec_delete.c 8.6 (Berkeley) 6/4/94"; +static char sccsid[] = "@(#)rec_delete.c 8.7 (Berkeley) 7/14/94"; #else -static char rcsid[] = "$NetBSD: rec_delete.c,v 1.7 1995/02/27 13:24:48 cgd Exp $"; +static char rcsid[] = "$NetBSD: rec_delete.c,v 1.8 1996/05/03 21:38:46 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -94,13 +94,13 @@ __rec_delete(dbp, key, flags) status = rec_rdelete(t, nrec); break; case R_CURSOR: - if (!ISSET(t, B_SEQINIT)) + if (!F_ISSET(&t->bt_cursor, CURS_INIT)) goto einval; if (t->bt_nrecs == 0) return (RET_SPECIAL); - status = rec_rdelete(t, t->bt_rcursor - 1); + status = rec_rdelete(t, t->bt_cursor.rcursor - 1); if (status == RET_SUCCESS) - --t->bt_rcursor; + --t->bt_cursor.rcursor; break; default: einval: errno = EINVAL; @@ -108,7 +108,7 @@ einval: errno = EINVAL; } if (status == RET_SUCCESS) - SET(t, B_MODIFIED | R_MODIFIED); + F_SET(t, B_MODIFIED | R_MODIFIED); return (status); } diff --git a/lib/libc/db/recno/rec_get.c b/lib/libc/db/recno/rec_get.c index bc25104e552..a08e16f8089 100644 --- a/lib/libc/db/recno/rec_get.c +++ b/lib/libc/db/recno/rec_get.c @@ -1,4 +1,4 @@ -/* $NetBSD: rec_get.c,v 1.7 1995/02/27 13:24:57 cgd Exp $ */ +/* $NetBSD: rec_get.c,v 1.8 1996/05/03 21:38:48 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -35,9 +35,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)rec_get.c 8.5 (Berkeley) 6/20/94"; +static char sccsid[] = "@(#)rec_get.c 8.9 (Berkeley) 8/18/94"; #else -static char rcsid[] = "$NetBSD: rec_get.c,v 1.7 1995/02/27 13:24:57 cgd Exp $"; +static char rcsid[] = "$NetBSD: rec_get.c,v 1.8 1996/05/03 21:38:48 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -96,7 +96,7 @@ __rec_get(dbp, key, data, flags) * original file. */ if (nrec > t->bt_nrecs) { - if (ISSET(t, R_EOF | R_INMEM)) + if (F_ISSET(t, R_EOF | R_INMEM)) return (RET_SPECIAL); if ((status = t->bt_irec(t, nrec)) != RET_SUCCESS) return (status); @@ -107,7 +107,7 @@ __rec_get(dbp, key, data, flags) return (RET_ERROR); status = __rec_ret(t, e, 0, NULL, data); - if (ISSET(t, B_DB_LOCK)) + if (F_ISSET(t, B_DB_LOCK)) mpool_put(t->bt_mp, e->page, 0); else t->bt_pinned = e->page; @@ -133,32 +133,38 @@ __rec_fpipe(t, top) recno_t nrec; size_t len; int ch; - char *p; + u_char *p; - if (t->bt_dbufsz < t->bt_reclen) { - t->bt_dbuf = (char *)(t->bt_dbuf == NULL ? - malloc(t->bt_reclen) : realloc(t->bt_dbuf, t->bt_reclen)); - if (t->bt_dbuf == NULL) + if (t->bt_rdata.size < t->bt_reclen) { + t->bt_rdata.data = t->bt_rdata.data == NULL ? + malloc(t->bt_reclen) : + realloc(t->bt_rdata.data, t->bt_reclen); + if (t->bt_rdata.data == NULL) return (RET_ERROR); - t->bt_dbufsz = t->bt_reclen; + t->bt_rdata.size = t->bt_reclen; } - data.data = t->bt_dbuf; + data.data = t->bt_rdata.data; data.size = t->bt_reclen; - for (nrec = t->bt_nrecs; nrec < top; ++nrec) { + for (nrec = t->bt_nrecs; nrec < top;) { len = t->bt_reclen; - for (p = t->bt_dbuf;; *p++ = ch) - if ((ch = getc(t->bt_rfp)) == EOF || !len--) { - if (__rec_iput(t, nrec, &data, 0) - != RET_SUCCESS) + for (p = t->bt_rdata.data;; *p++ = ch) + if ((ch = getc(t->bt_rfp)) == EOF || !--len) { + if (ch != EOF) + *p = ch; + if (len != 0) + memset(p, t->bt_bval, len); + if (__rec_iput(t, + nrec, &data, 0) != RET_SUCCESS) return (RET_ERROR); + ++nrec; break; } if (ch == EOF) break; } if (nrec < top) { - SET(t, R_EOF); + F_SET(t, R_EOF); return (RET_SPECIAL); } return (RET_SUCCESS); @@ -184,14 +190,15 @@ __rec_vpipe(t, top) indx_t len; size_t sz; int bval, ch; - char *p; + u_char *p; bval = t->bt_bval; for (nrec = t->bt_nrecs; nrec < top; ++nrec) { - for (p = t->bt_dbuf, sz = t->bt_dbufsz;; *p++ = ch, --sz) { + for (p = t->bt_rdata.data, + sz = t->bt_rdata.size;; *p++ = ch, --sz) { if ((ch = getc(t->bt_rfp)) == EOF || ch == bval) { - data.data = t->bt_dbuf; - data.size = p - t->bt_dbuf; + data.data = t->bt_rdata.data; + data.size = p - (u_char *)t->bt_rdata.data; if (ch == EOF && data.size == 0) break; if (__rec_iput(t, nrec, &data, 0) @@ -200,21 +207,21 @@ __rec_vpipe(t, top) break; } if (sz == 0) { - len = p - t->bt_dbuf; - t->bt_dbufsz += (sz = 256); - t->bt_dbuf = (char *)(t->bt_dbuf == NULL ? - malloc(t->bt_dbufsz) : - realloc(t->bt_dbuf, t->bt_dbufsz)); - if (t->bt_dbuf == NULL) + len = p - (u_char *)t->bt_rdata.data; + t->bt_rdata.size += (sz = 256); + t->bt_rdata.data = t->bt_rdata.data == NULL ? + malloc(t->bt_rdata.size) : + realloc(t->bt_rdata.data, t->bt_rdata.size); + if (t->bt_rdata.data == NULL) return (RET_ERROR); - p = t->bt_dbuf + len; + p = (u_char *)t->bt_rdata.data + len; } } if (ch == EOF) break; } if (nrec < top) { - SET(t, R_EOF); + F_SET(t, R_EOF); return (RET_SPECIAL); } return (RET_SUCCESS); @@ -237,34 +244,36 @@ __rec_fmap(t, top) { DBT data; recno_t nrec; - caddr_t sp, ep; + u_char *sp, *ep, *p; size_t len; - char *p; - if (t->bt_dbufsz < t->bt_reclen) { - t->bt_dbuf = (char *)(t->bt_dbuf == NULL ? - malloc(t->bt_reclen) : realloc(t->bt_dbuf, t->bt_reclen)); - if (t->bt_dbuf == NULL) + if (t->bt_rdata.size < t->bt_reclen) { + t->bt_rdata.data = t->bt_rdata.data == NULL ? + malloc(t->bt_reclen) : + realloc(t->bt_rdata.data, t->bt_reclen); + if (t->bt_rdata.data == NULL) return (RET_ERROR); - t->bt_dbufsz = t->bt_reclen; + t->bt_rdata.size = t->bt_reclen; } - data.data = t->bt_dbuf; + data.data = t->bt_rdata.data; data.size = t->bt_reclen; - sp = t->bt_cmap; - ep = t->bt_emap; + sp = (u_char *)t->bt_cmap; + ep = (u_char *)t->bt_emap; for (nrec = t->bt_nrecs; nrec < top; ++nrec) { if (sp >= ep) { - SET(t, R_EOF); + F_SET(t, R_EOF); return (RET_SPECIAL); } len = t->bt_reclen; - for (p = t->bt_dbuf; sp < ep && len--; *p++ = *sp++); - memset(p, t->bt_bval, len); + for (p = t->bt_rdata.data; + sp < ep && len > 0; *p++ = *sp++, --len); + if (len != 0) + memset(p, t->bt_bval, len); if (__rec_iput(t, nrec, &data, 0) != RET_SUCCESS) return (RET_ERROR); } - t->bt_cmap = sp; + t->bt_cmap = (caddr_t)sp; return (RET_SUCCESS); } @@ -284,25 +293,25 @@ __rec_vmap(t, top) recno_t top; { DBT data; - caddr_t sp, ep; + u_char *sp, *ep; recno_t nrec; int bval; - sp = t->bt_cmap; - ep = t->bt_emap; + sp = (u_char *)t->bt_cmap; + ep = (u_char *)t->bt_emap; bval = t->bt_bval; for (nrec = t->bt_nrecs; nrec < top; ++nrec) { if (sp >= ep) { - SET(t, R_EOF); + F_SET(t, R_EOF); return (RET_SPECIAL); } for (data.data = sp; sp < ep && *sp != bval; ++sp); - data.size = sp - (caddr_t)data.data; + data.size = sp - (u_char *)data.data; if (__rec_iput(t, nrec, &data, 0) != RET_SUCCESS) return (RET_ERROR); ++sp; } - t->bt_cmap = sp; + t->bt_cmap = (caddr_t)sp; return (RET_SUCCESS); } diff --git a/lib/libc/db/recno/rec_open.c b/lib/libc/db/recno/rec_open.c index e67a7b6f000..d2c9369b730 100644 --- a/lib/libc/db/recno/rec_open.c +++ b/lib/libc/db/recno/rec_open.c @@ -1,7 +1,7 @@ -/* $NetBSD: rec_open.c,v 1.6 1995/02/27 13:25:05 cgd Exp $ */ +/* $NetBSD: rec_open.c,v 1.7 1996/05/03 21:38:49 cgd Exp $ */ /*- - * Copyright (c) 1990, 1993 + * Copyright (c) 1990, 1993, 1994 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by @@ -38,9 +38,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)rec_open.c 8.6 (Berkeley) 2/22/94"; +static char sccsid[] = "@(#)rec_open.c 8.10 (Berkeley) 9/1/94"; #else -static char rcsid[] = "$NetBSD: rec_open.c,v 1.6 1995/02/27 13:25:05 cgd Exp $"; +static char rcsid[] = "$NetBSD: rec_open.c,v 1.7 1996/05/03 21:38:49 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -104,7 +104,7 @@ __rec_open(fname, flags, mode, openinfo, dflags) t = dbp->internal; if (openinfo) { if (openinfo->flags & R_FIXEDLEN) { - SET(t, R_FIXLEN); + F_SET(t, R_FIXLEN); t->bt_reclen = openinfo->reclen; if (t->bt_reclen == 0) goto einval; @@ -113,12 +113,11 @@ __rec_open(fname, flags, mode, openinfo, dflags) } else t->bt_bval = '\n'; - SET(t, R_RECNO); + F_SET(t, R_RECNO); if (fname == NULL) - SET(t, R_EOF | R_INMEM); + F_SET(t, R_EOF | R_INMEM); else t->bt_rfd = rfd; - t->bt_rcursor = 0; if (fname != NULL) { /* @@ -130,20 +129,20 @@ __rec_open(fname, flags, mode, openinfo, dflags) if (lseek(rfd, (off_t)0, SEEK_CUR) == -1 && errno == ESPIPE) { switch (flags & O_ACCMODE) { case O_RDONLY: - SET(t, R_RDONLY); + F_SET(t, R_RDONLY); break; default: goto einval; } slow: if ((t->bt_rfp = fdopen(rfd, "r")) == NULL) goto err; - SET(t, R_CLOSEFP); + F_SET(t, R_CLOSEFP); t->bt_irec = - ISSET(t, R_FIXLEN) ? __rec_fpipe : __rec_vpipe; + F_ISSET(t, R_FIXLEN) ? __rec_fpipe : __rec_vpipe; } else { switch (flags & O_ACCMODE) { case O_RDONLY: - SET(t, R_RDONLY); + F_SET(t, R_RDONLY); break; case O_RDWR: break; @@ -163,8 +162,16 @@ slow: if ((t->bt_rfp = fdopen(rfd, "r")) == NULL) * fails if the file is too large. */ if (sb.st_size == 0) - SET(t, R_EOF); + F_SET(t, R_EOF); else { +#ifdef MMAP_NOT_AVAILABLE + /* + * XXX + * Mmap doesn't work correctly on many current + * systems. In particular, it can fail subtly, + * with cache coherency problems. Don't use it + * for now. + */ t->bt_msize = sb.st_size; if ((t->bt_smap = mmap(NULL, t->bt_msize, PROT_READ, MAP_PRIVATE, rfd, @@ -172,9 +179,12 @@ slow: if ((t->bt_rfp = fdopen(rfd, "r")) == NULL) goto slow; t->bt_cmap = t->bt_smap; t->bt_emap = t->bt_smap + sb.st_size; - t->bt_irec = ISSET(t, R_FIXLEN) ? + t->bt_irec = F_ISSET(t, R_FIXLEN) ? __rec_fmap : __rec_vmap; - SET(t, R_MEMMAPPED); + F_SET(t, R_MEMMAPPED); +#else + goto slow; +#endif } } } @@ -192,13 +202,14 @@ slow: if ((t->bt_rfp = fdopen(rfd, "r")) == NULL) if ((h = mpool_get(t->bt_mp, P_ROOT, 0)) == NULL) goto err; if ((h->flags & P_TYPE) == P_BLEAF) { - h->flags = h->flags & ~P_TYPE | P_RLEAF; + F_CLR(h, P_TYPE); + F_SET(h, P_RLEAF); mpool_put(t->bt_mp, h, MPOOL_DIRTY); } else mpool_put(t->bt_mp, h, 0); if (openinfo && openinfo->flags & R_SNAPSHOT && - !ISSET(t, R_EOF | R_INMEM) && + !F_ISSET(t, R_EOF | R_INMEM) && t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR) goto err; return (dbp); @@ -228,7 +239,7 @@ __rec_fd(dbp) } /* In-memory database can't have a file descriptor. */ - if (ISSET(t, R_INMEM)) { + if (F_ISSET(t, R_INMEM)) { errno = ENOENT; return (-1); } diff --git a/lib/libc/db/recno/rec_put.c b/lib/libc/db/recno/rec_put.c index 77d7079fb73..107d645a649 100644 --- a/lib/libc/db/recno/rec_put.c +++ b/lib/libc/db/recno/rec_put.c @@ -1,4 +1,4 @@ -/* $NetBSD: rec_put.c,v 1.7 1995/02/27 13:25:13 cgd Exp $ */ +/* $NetBSD: rec_put.c,v 1.8 1996/05/03 21:38:50 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -35,9 +35,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)rec_put.c 8.4 (Berkeley) 5/31/94"; +static char sccsid[] = "@(#)rec_put.c 8.7 (Berkeley) 8/18/94"; #else -static char rcsid[] = "$NetBSD: rec_put.c,v 1.7 1995/02/27 13:25:13 cgd Exp $"; +static char rcsid[] = "$NetBSD: rec_put.c,v 1.8 1996/05/03 21:38:50 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -72,7 +72,7 @@ __rec_put(dbp, key, data, flags) u_int flags; { BTREE *t; - DBT tdata; + DBT fdata, tdata; recno_t nrec; int status; @@ -84,11 +84,38 @@ __rec_put(dbp, key, data, flags) t->bt_pinned = NULL; } + /* + * If using fixed-length records, and the record is long, return + * EINVAL. If it's short, pad it out. Use the record data return + * memory, it's only short-term. + */ + if (F_ISSET(t, R_FIXLEN) && data->size != t->bt_reclen) { + if (data->size > t->bt_reclen) + goto einval; + + if (t->bt_rdata.size < t->bt_reclen) { + t->bt_rdata.data = t->bt_rdata.data == NULL ? + malloc(t->bt_reclen) : + realloc(t->bt_rdata.data, t->bt_reclen); + if (t->bt_rdata.data == NULL) + return (RET_ERROR); + t->bt_rdata.size = t->bt_reclen; + } + memmove(t->bt_rdata.data, data->data, data->size); + memset((char *)t->bt_rdata.data + data->size, + t->bt_bval, t->bt_reclen - data->size); + fdata.data = t->bt_rdata.data; + fdata.size = t->bt_reclen; + } else { + fdata.data = data->data; + fdata.size = data->size; + } + switch (flags) { case R_CURSOR: - if (!ISSET(t, B_SEQINIT)) + if (!F_ISSET(&t->bt_cursor, CURS_INIT)) goto einval; - nrec = t->bt_rcursor; + nrec = t->bt_cursor.rcursor; break; case R_SETCURSOR: if ((nrec = *(recno_t *)key->data) == 0) @@ -121,11 +148,11 @@ einval: errno = EINVAL; * already in the database. If skipping records, create empty ones. */ if (nrec > t->bt_nrecs) { - if (!ISSET(t, R_EOF | R_INMEM) && + if (!F_ISSET(t, R_EOF | R_INMEM) && t->bt_irec(t, nrec) == RET_ERROR) return (RET_ERROR); if (nrec > t->bt_nrecs + 1) { - if (ISSET(t, R_FIXLEN)) { + if (F_ISSET(t, R_FIXLEN)) { if ((tdata.data = (void *)malloc(t->bt_reclen)) == NULL) return (RET_ERROR); @@ -139,18 +166,18 @@ einval: errno = EINVAL; if (__rec_iput(t, t->bt_nrecs, &tdata, 0) != RET_SUCCESS) return (RET_ERROR); - if (ISSET(t, R_FIXLEN)) + if (F_ISSET(t, R_FIXLEN)) free(tdata.data); } } - if ((status = __rec_iput(t, nrec - 1, data, flags)) != RET_SUCCESS) + if ((status = __rec_iput(t, nrec - 1, &fdata, flags)) != RET_SUCCESS) return (status); if (flags == R_SETCURSOR) - t->bt_rcursor = nrec; + t->bt_cursor.rcursor = nrec; - SET(t, R_MODIFIED); + F_SET(t, R_MODIFIED); return (__rec_ret(t, NULL, nrec, key, NULL)); } @@ -252,7 +279,7 @@ __rec_iput(t, nrec, data, flags) WR_RLEAF(dest, data, dflags); ++t->bt_nrecs; - SET(t, B_MODIFIED); + F_SET(t, B_MODIFIED); mpool_put(t->bt_mp, h, MPOOL_DIRTY); return (RET_SUCCESS); diff --git a/lib/libc/db/recno/rec_search.c b/lib/libc/db/recno/rec_search.c index 208328d9ddd..beb714b5146 100644 --- a/lib/libc/db/recno/rec_search.c +++ b/lib/libc/db/recno/rec_search.c @@ -1,4 +1,4 @@ -/* $NetBSD: rec_search.c,v 1.6 1995/02/27 13:25:17 cgd Exp $ */ +/* $NetBSD: rec_search.c,v 1.7 1996/05/03 21:38:52 cgd Exp $ */ /*- * Copyright (c) 1990, 1993 @@ -35,9 +35,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)rec_search.c 8.3 (Berkeley) 2/21/94"; +static char sccsid[] = "@(#)rec_search.c 8.4 (Berkeley) 7/14/94"; #else -static char rcsid[] = "$NetBSD: rec_search.c,v 1.6 1995/02/27 13:25:17 cgd Exp $"; +static char rcsid[] = "$NetBSD: rec_search.c,v 1.7 1996/05/03 21:38:52 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -97,8 +97,7 @@ __rec_search(t, recno, op) total += r->nrecs; } - if (__bt_push(t, pg, index - 1) == RET_ERROR) - return (NULL); + BT_PUSH(t, pg, index - 1); pg = r->pgno; switch (op) { diff --git a/lib/libc/db/recno/rec_seq.c b/lib/libc/db/recno/rec_seq.c index b91f3a27bf6..3b5c534dda6 100644 --- a/lib/libc/db/recno/rec_seq.c +++ b/lib/libc/db/recno/rec_seq.c @@ -1,7 +1,7 @@ -/* $NetBSD: rec_seq.c,v 1.6 1995/02/27 13:25:24 cgd Exp $ */ +/* $NetBSD: rec_seq.c,v 1.7 1996/05/03 21:38:53 cgd Exp $ */ /*- - * Copyright (c) 1991, 1993 + * Copyright (c) 1991, 1993, 1994 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -35,9 +35,9 @@ #ifndef lint #if 0 -static char sccsid[] = "@(#)rec_seq.c 8.2 (Berkeley) 9/7/93"; +static char sccsid[] = "@(#)rec_seq.c 8.3 (Berkeley) 7/14/94"; #else -static char rcsid[] = "$NetBSD: rec_seq.c,v 1.6 1995/02/27 13:25:24 cgd Exp $"; +static char rcsid[] = "$NetBSD: rec_seq.c,v 1.7 1996/05/03 21:38:53 cgd Exp $"; #endif #endif /* not lint */ @@ -88,8 +88,8 @@ __rec_seq(dbp, key, data, flags) goto einval; break; case R_NEXT: - if (ISSET(t, B_SEQINIT)) { - nrec = t->bt_rcursor + 1; + if (F_ISSET(&t->bt_cursor, CURS_INIT)) { + nrec = t->bt_cursor.rcursor + 1; break; } /* FALLTHROUGH */ @@ -97,14 +97,14 @@ __rec_seq(dbp, key, data, flags) nrec = 1; break; case R_PREV: - if (ISSET(t, B_SEQINIT)) { - if ((nrec = t->bt_rcursor - 1) == 0) + if (F_ISSET(&t->bt_cursor, CURS_INIT)) { + if ((nrec = t->bt_cursor.rcursor - 1) == 0) return (RET_SPECIAL); break; } /* FALLTHROUGH */ case R_LAST: - if (!ISSET(t, R_EOF | R_INMEM) && + if (!F_ISSET(t, R_EOF | R_INMEM) && t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR) return (RET_ERROR); nrec = t->bt_nrecs; @@ -115,7 +115,7 @@ einval: errno = EINVAL; } if (t->bt_nrecs == 0 || nrec > t->bt_nrecs) { - if (!ISSET(t, R_EOF | R_INMEM) && + if (!F_ISSET(t, R_EOF | R_INMEM) && (status = t->bt_irec(t, nrec)) != RET_SUCCESS) return (status); if (t->bt_nrecs == 0 || nrec > t->bt_nrecs) @@ -125,11 +125,11 @@ einval: errno = EINVAL; if ((e = __rec_search(t, nrec - 1, SEARCH)) == NULL) return (RET_ERROR); - SET(t, B_SEQINIT); - t->bt_rcursor = nrec; + F_SET(&t->bt_cursor, CURS_INIT); + t->bt_cursor.rcursor = nrec; status = __rec_ret(t, e, nrec, key, data); - if (ISSET(t, B_DB_LOCK)) + if (F_ISSET(t, B_DB_LOCK)) mpool_put(t->bt_mp, e->page, 0); else t->bt_pinned = e->page; diff --git a/lib/libc/db/recno/rec_utils.c b/lib/libc/db/recno/rec_utils.c index 7aab4ac3a91..e411dae7db4 100644 --- a/lib/libc/db/recno/rec_utils.c +++ b/lib/libc/db/recno/rec_utils.c @@ -1,4 +1,4 @@ -/* $NetBSD: rec_utils.c,v 1.6 1995/02/27 13:25:29 cgd Exp $ */ +/* $NetBSD: rec_utils.c,v 1.7 1996/05/03 21:38:54 cgd Exp $ */ /*- * Copyright (c) 1990, 1993, 1994 @@ -35,9 +35,9 @@ #if defined(LIBC_SCCS) && !defined(lint) #if 0 -static char sccsid[] = "@(#)rec_utils.c 8.4 (Berkeley) 6/20/94"; +static char sccsid[] = "@(#)rec_utils.c 8.6 (Berkeley) 7/16/94"; #else -static char rcsid[] = "$NetBSD: rec_utils.c,v 1.6 1995/02/27 13:25:29 cgd Exp $"; +static char rcsid[] = "$NetBSD: rec_utils.c,v 1.7 1996/05/03 21:38:54 cgd Exp $"; #endif #endif /* LIBC_SCCS and not lint */ @@ -51,11 +51,14 @@ static char rcsid[] = "$NetBSD: rec_utils.c,v 1.6 1995/02/27 13:25:29 cgd Exp $" #include "recno.h" /* - * __REC_RET -- Build return data as a result of search or scan. + * __rec_ret -- + * Build return data. * * Parameters: * t: tree - * d: LEAF to be returned to the user. + * e: key/data pair to be returned + * nrec: record number + * key: user's key structure * data: user's data structure * * Returns: @@ -68,58 +71,58 @@ __rec_ret(t, e, nrec, key, data) recno_t nrec; DBT *key, *data; { - register RLEAF *rl; - register void *p; + RLEAF *rl; + void *p; - if (data == NULL) - goto retkey; + if (key == NULL) + goto dataonly; - rl = GETRLEAF(e->page, e->index); + /* We have to copy the key, it's not on the page. */ + if (sizeof(recno_t) > t->bt_rkey.size) { + p = (void *)(t->bt_rkey.data == NULL ? + malloc(sizeof(recno_t)) : + realloc(t->bt_rkey.data, sizeof(recno_t))); + if (p == NULL) + return (RET_ERROR); + t->bt_rkey.data = p; + t->bt_rkey.size = sizeof(recno_t); + } + memmove(t->bt_rkey.data, &nrec, sizeof(recno_t)); + key->size = sizeof(recno_t); + key->data = t->bt_rkey.data; + +dataonly: + if (data == NULL) + return (RET_SUCCESS); /* - * We always copy big data to make it contigous. Otherwise, we + * We must copy big keys/data to make them contigous. Otherwise, * leave the page pinned and don't copy unless the user specified * concurrent access. */ + rl = GETRLEAF(e->page, e->index); if (rl->flags & P_BIGDATA) { if (__ovfl_get(t, rl->bytes, - &data->size, &t->bt_dbuf, &t->bt_dbufsz)) + &data->size, &t->bt_rdata.data, &t->bt_rdata.size)) return (RET_ERROR); - data->data = t->bt_dbuf; - } else if (ISSET(t, B_DB_LOCK)) { + data->data = t->bt_rdata.data; + } else if (F_ISSET(t, B_DB_LOCK)) { /* Use +1 in case the first record retrieved is 0 length. */ - if (rl->dsize + 1 > t->bt_dbufsz) { - p = (void *)(t->bt_dbuf == NULL ? + if (rl->dsize + 1 > t->bt_rdata.size) { + p = (void *)(t->bt_rdata.data == NULL ? malloc(rl->dsize + 1) : - realloc(t->bt_dbuf, rl->dsize + 1)); + realloc(t->bt_rdata.data, rl->dsize + 1)); if (p == NULL) return (RET_ERROR); - t->bt_dbuf = p; - t->bt_dbufsz = rl->dsize + 1; + t->bt_rdata.data = p; + t->bt_rdata.size = rl->dsize + 1; } - memmove(t->bt_dbuf, rl->bytes, rl->dsize); + memmove(t->bt_rdata.data, rl->bytes, rl->dsize); data->size = rl->dsize; - data->data = t->bt_dbuf; + data->data = t->bt_rdata.data; } else { data->size = rl->dsize; data->data = rl->bytes; } - -retkey: if (key == NULL) - return (RET_SUCCESS); - - /* We have to copy the key, it's not on the page. */ - if (sizeof(recno_t) > t->bt_kbufsz) { - p = (void *)(t->bt_kbuf == NULL ? - malloc(sizeof(recno_t)) : - realloc(t->bt_kbuf, sizeof(recno_t))); - if (p == NULL) - return (RET_ERROR); - t->bt_kbuf = p; - t->bt_kbufsz = sizeof(recno_t); - } - memmove(t->bt_kbuf, &nrec, sizeof(recno_t)); - key->size = sizeof(recno_t); - key->data = t->bt_kbuf; return (RET_SUCCESS); } diff --git a/lib/libc/db/recno/recno.h b/lib/libc/db/recno/recno.h index 5c1c716ace3..747c7bd9ee7 100644 --- a/lib/libc/db/recno/recno.h +++ b/lib/libc/db/recno/recno.h @@ -1,4 +1,4 @@ -/* $NetBSD: recno.h,v 1.4 1995/02/27 13:25:35 cgd Exp $ */ +/* $NetBSD: recno.h,v 1.5 1996/05/03 21:38:55 cgd Exp $ */ /*- * Copyright (c) 1991, 1993 diff --git a/regress/lib/libc/db/README b/regress/lib/libc/db/README index 3b290b09d81..fddf5c3d5a0 100644 --- a/regress/lib/libc/db/README +++ b/regress/lib/libc/db/README @@ -1,5 +1,5 @@ -# $NetBSD: README,v 1.4 1995/04/20 22:39:18 cgd Exp $ -# @(#)README 8.4 (Berkeley) 6/20/94 +# $NetBSD: README,v 1.5 1996/05/03 21:54:19 cgd Exp $ +# @(#)README 8.8 (Berkeley) 7/31/94 To run the tests, enter "make regress". @@ -9,8 +9,11 @@ the test runs, and even larger files (the database files) are created in variable TMPDIR to a directory where the files can be built. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= -The script file consists of lines with a initial character which is -the "command" for that line. Legal characters are as follows: +The script file consists of lines with an initial character which is +the command for that line, or an initial character indicating a key +or data entry for a previous command. + +Legal command characters are as follows: c: compare a record + must be followed by [kK][dD]; the data value in the database @@ -19,17 +22,24 @@ c: compare a record e: echo a string + writes out the rest of the line into the output file; if the last character is not a carriage-return, a newline is appended. +f: set the flags for the next command + + no value zero's the flags g: do a get command + must be followed by [kK] + writes out the retrieved data DBT. +o [r]: dump [reverse] + + dump the database out, if 'r' is set, in reverse order. p: do a put command + must be followed by [kK][dD] r: do a del command - + must be followed by [kK] + + must be followed by [kK] unless R_CURSOR flag set. +S: sync the database s: do a seq command + + must be followed by [kK] if R_CURSOR flag set. + writes out the retrieved data DBT. -f: set the flags for the next command - + no value zero's the flags + +Legal key/data characters are as follows: + D [file]: data file + set the current data value to the contents of the file d [data]: @@ -38,17 +48,21 @@ K [file]: key file + set the current key value to the contents of the file k [data]: + set the current key value to the contents of the line. -o [r]: dump [reverse] - + dump the database out, if 'r' is set, in reverse order. + +Blank lines, lines with leading white space, and lines with leading +hash marks (#) are ignored. Options to dbtest are as follows: + -d: Set the DB_LOCK flag. -f: Use the file argument as the database file. -i: Use the rest of the argument to set elements in the info structure. If the type is btree, then "-i cachesize=10240" will set BTREEINFO.cachesize to 10240. -o: The rest of the argument is the output file instead of using stdout. + -s: Don't delete the database file before opening it, i.e. + use the database file from a previous run. -Dbtest requires two arguments, the type of access "hash", "recno" or -"btree", and the script name. +Dbtest requires two arguments, the type of access "hash", "recno" +or "btree", and the script name or "-" to indicate stdin. diff --git a/regress/lib/libc/db/dbtest.c b/regress/lib/libc/db/dbtest.c index 1fcf09af97f..65587a6fcb2 100644 --- a/regress/lib/libc/db/dbtest.c +++ b/regress/lib/libc/db/dbtest.c @@ -1,7 +1,7 @@ -/* $NetBSD: dbtest.c,v 1.7 1995/04/20 22:39:22 cgd Exp $ */ +/* $NetBSD: dbtest.c,v 1.8 1996/05/03 21:57:48 cgd Exp $ */ /*- - * Copyright (c) 1992, 1993 + * Copyright (c) 1992, 1993, 1994 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -35,15 +35,15 @@ #ifndef lint static char copyright[] = -"@(#) Copyright (c) 1992, 1993\n\ +"@(#) Copyright (c) 1992, 1993, 1994\n\ The Regents of the University of California. All rights reserved.\n"; #endif /* not lint */ #ifndef lint #if 0 -static char sccsid[] = "@(#)dbtest.c 8.8 (Berkeley) 2/21/94"; +static char sccsid[] = "@(#)dbtest.c 8.17 (Berkeley) 9/1/94"; #else -static char rcsid[] = "$NetBSD: dbtest.c,v 1.7 1995/04/20 22:39:22 cgd Exp $"; +static char rcsid[] = "$NetBSD: dbtest.c,v 1.8 1996/05/03 21:57:48 cgd Exp $"; #endif #endif /* not lint */ @@ -71,6 +71,8 @@ void get __P((DB *, DBT *)); void getdata __P((DB *, DBT *, DBT *)); void put __P((DB *, DBT *, DBT *)); void rem __P((DB *, DBT *)); +char *sflags __P((int)); +void synk __P((DB *)); void *rfile __P((char *, size_t *)); void seq __P((DB *, DBT *)); u_int setflags __P((char *)); @@ -78,13 +80,14 @@ void *setinfo __P((DBTYPE, char *)); void usage __P((void)); void *xmalloc __P((char *, size_t)); -DBTYPE type; -void *infop; -u_long lineno; -u_int flags; -int ofd = STDOUT_FILENO; +DBTYPE type; /* Database type. */ +void *infop; /* Iflags. */ +u_long lineno; /* Current line in test script. */ +u_int flags; /* Current DB flags. */ +int ofd = STDOUT_FILENO; /* Standard output fd. */ DB *XXdbp; /* Global for gdb. */ +int XXlineno; /* Fast breakpoint for gdb. */ int main(argc, argv) @@ -97,14 +100,15 @@ main(argc, argv) DB *dbp; DBT data, key, keydata; size_t len; - int ch, oflags; - char *fname, *infoarg, *p, buf[8 * 1024]; + int ch, oflags, sflag; + char *fname, *infoarg, *p, *t, buf[8 * 1024]; infoarg = NULL; fname = NULL; oflags = O_CREAT | O_RDWR; - while ((ch = getopt(argc, argv, "f:i:lo:")) != EOF) - switch(ch) { + sflag = 0; + while ((ch = getopt(argc, argv, "f:i:lo:s")) != EOF) + switch (ch) { case 'f': fname = optarg; break; @@ -119,6 +123,9 @@ main(argc, argv) O_WRONLY|O_CREAT|O_TRUNC, 0666)) < 0) err("%s: %s", optarg, strerror(errno)); break; + case 's': + sflag = 1; + break; case '?': default: usage(); @@ -133,8 +140,8 @@ main(argc, argv) type = dbtype(*argv++); /* Open the descriptor file. */ - if (freopen(*argv, "r", stdin) == NULL) - err("%s: %s", *argv, strerror(errno)); + if (strcmp(*argv, "-") && freopen(*argv, "r", stdin) == NULL) + err("%s: %s", *argv, strerror(errno)); /* Set up the db structure as necessary. */ if (infoarg == NULL) @@ -145,7 +152,10 @@ main(argc, argv) if (*p != '\0') infop = setinfo(type, p); - /* Open the DB. */ + /* + * Open the DB. Delete any preexisting copy, you almost never + * want it around, and it often screws up tests. + */ if (fname == NULL) { p = getenv("TMPDIR"); if (p == NULL) @@ -153,7 +163,9 @@ main(argc, argv) (void)sprintf(buf, "%s/__dbtest", p); fname = buf; (void)unlink(buf); - } + } else if (!sflag) + (void)unlink(fname); + if ((dbp = dbopen(fname, oflags, S_IRUSR | S_IWUSR, type, infop)) == NULL) err("dbopen: %s", strerror(errno)); @@ -162,8 +174,16 @@ main(argc, argv) state = COMMAND; for (lineno = 1; (p = fgets(buf, sizeof(buf), stdin)) != NULL; ++lineno) { - len = strlen(buf); - switch(*p) { + /* Delete the newline, displaying the key/data is easier. */ + if (ofd == STDOUT_FILENO && (t = strchr(p, '\n')) != NULL) + *t = '\0'; + if ((len = strlen(buf)) == 0 || isspace(*p) || *p == '#') + continue; + + /* Convenient gdb break point. */ + if (XXlineno == lineno) + XXlineno = 1; + switch (*p) { case 'c': /* compare */ if (state != COMMAND) err("line %lu: not expecting command", lineno); @@ -176,7 +196,8 @@ main(argc, argv) /* Don't display the newline, if CR at EOL. */ if (p[len - 2] == '\r') --len; - if (write(ofd, p + 1, len - 1) != len - 1) + if (write(ofd, p + 1, len - 1) != len - 1 || + write(ofd, "\n", 1) != 1) err("write: %s", strerror(errno)); break; case 'g': /* get */ @@ -194,8 +215,19 @@ main(argc, argv) case 'r': /* remove */ if (state != COMMAND) err("line %lu: not expecting command", lineno); - state = KEY; - command = REMOVE; + if (flags == R_CURSOR) { + rem(dbp, &key); + state = COMMAND; + } else { + state = KEY; + command = REMOVE; + } + break; + case 'S': /* sync */ + if (state != COMMAND) + err("line %lu: not expecting command", lineno); + synk(dbp); + state = COMMAND; break; case 's': /* seq */ if (state != COMMAND) @@ -219,7 +251,7 @@ main(argc, argv) err("line %lu: not expecting data", lineno); data.data = xmalloc(p + 1, len - 1); data.size = len - 1; -ldata: switch(command) { +ldata: switch (command) { case COMPARE: compare(&keydata, &data); break; @@ -255,7 +287,7 @@ ldata: switch(command) { key.data = xmalloc(p + 1, len - 1); key.size = len - 1; } -lkey: switch(command) { +lkey: switch (command) { case COMPARE: getdata(dbp, &key, &keydata); state = DATA; @@ -271,13 +303,13 @@ lkey: switch(command) { break; case REMOVE: rem(dbp, &key); - if (type != DB_RECNO) + if ((type != DB_RECNO) && (flags != R_CURSOR)) free(key.data); state = COMMAND; break; case SEQ: seq(dbp, &key); - if (type != DB_RECNO) + if ((type != DB_RECNO) && (flags != R_CURSOR)) free(key.data); state = COMMAND; break; @@ -291,11 +323,15 @@ lkey: switch(command) { break; default: err("line %lu: %s: unknown command character", - p, lineno); + lineno, p); } } #ifdef STATISTICS - if (type == DB_BTREE) + /* + * -l must be used (DB_LOCK must be set) for this to be + * used, otherwise a page will be locked and it will fail. + */ + if (type == DB_BTREE && oflags & DB_LOCK) __bt_stat(dbp); #endif if (dbp->close(dbp)) @@ -305,7 +341,6 @@ lkey: switch(command) { } #define NOOVERWRITE "put failed, would overwrite key\n" -#define NOSUCHKEY "get failed, no such key\n" void compare(db1, db2) @@ -334,17 +369,23 @@ get(dbp, kp) { DBT data; - switch(dbp->get(dbp, kp, &data, flags)) { + switch (dbp->get(dbp, kp, &data, flags)) { case 0: (void)write(ofd, data.data, data.size); + if (ofd == STDOUT_FILENO) + (void)write(ofd, "\n", 1); break; case -1: err("line %lu: get: %s", lineno, strerror(errno)); /* NOTREACHED */ case 1: - (void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1); - (void)fprintf(stderr, "%d: %.*s: %s\n", - lineno, kp->size, kp->data, NOSUCHKEY); +#define NOSUCHKEY "get failed, no such key\n" + if (ofd != STDOUT_FILENO) + (void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1); + else + (void)fprintf(stderr, "%d: %.*s: %s", + lineno, MIN(kp->size, 20), kp->data, NOSUCHKEY); +#undef NOSUCHKEY break; } } @@ -354,14 +395,14 @@ getdata(dbp, kp, dp) DB *dbp; DBT *kp, *dp; { - switch(dbp->get(dbp, kp, dp, flags)) { + switch (dbp->get(dbp, kp, dp, flags)) { case 0: return; case -1: err("line %lu: getdata: %s", lineno, strerror(errno)); /* NOTREACHED */ case 1: - err("line %lu: get failed, no such key", lineno); + err("line %lu: getdata failed, no such key", lineno); /* NOTREACHED */ } } @@ -371,7 +412,7 @@ put(dbp, kp, dp) DB *dbp; DBT *kp, *dp; { - switch(dbp->put(dbp, kp, dp, flags)) { + switch (dbp->put(dbp, kp, dp, flags)) { case 0: break; case -1: @@ -388,18 +429,40 @@ rem(dbp, kp) DB *dbp; DBT *kp; { - switch(dbp->del(dbp, kp, flags)) { + switch (dbp->del(dbp, kp, flags)) { case 0: break; case -1: - err("line %lu: get: %s", lineno, strerror(errno)); + err("line %lu: rem: %s", lineno, strerror(errno)); /* NOTREACHED */ case 1: - (void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1); +#define NOSUCHKEY "rem failed, no such key\n" + if (ofd != STDOUT_FILENO) + (void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1); + else if (flags != R_CURSOR) + (void)fprintf(stderr, "%d: %.*s: %s", + lineno, MIN(kp->size, 20), kp->data, NOSUCHKEY); + else + (void)fprintf(stderr, + "%d: rem of cursor failed\n", lineno); +#undef NOSUCHKEY break; } } +void +synk(dbp) + DB *dbp; +{ + switch (dbp->sync(dbp, flags)) { + case 0: + break; + case -1: + err("line %lu: synk: %s", lineno, strerror(errno)); + /* NOTREACHED */ + } +} + void seq(dbp, kp) DB *dbp; @@ -407,15 +470,26 @@ seq(dbp, kp) { DBT data; - switch(dbp->seq(dbp, kp, &data, flags)) { + switch (dbp->seq(dbp, kp, &data, flags)) { case 0: (void)write(ofd, data.data, data.size); + if (ofd == STDOUT_FILENO) + (void)write(ofd, "\n", 1); break; case -1: err("line %lu: seq: %s", lineno, strerror(errno)); /* NOTREACHED */ case 1: - (void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1); +#define NOSUCHKEY "seq failed, no such key\n" + if (ofd != STDOUT_FILENO) + (void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1); + else if (flags == R_CURSOR) + (void)fprintf(stderr, "%d: %.*s: %s", + lineno, MIN(kp->size, 20), kp->data, NOSUCHKEY); + else + (void)fprintf(stderr, + "%d: seq (%s) failed\n", lineno, sflags(flags)); +#undef NOSUCHKEY break; } } @@ -436,9 +510,11 @@ dump(dbp, rev) nflags = R_NEXT; } for (;; flags = nflags) - switch(dbp->seq(dbp, &key, &data, flags)) { + switch (dbp->seq(dbp, &key, &data, flags)) { case 0: (void)write(ofd, data.data, data.size); + if (ofd == STDOUT_FILENO) + (void)write(ofd, "\n", 1); break; case 1: goto done; @@ -457,31 +533,42 @@ setflags(s) char *p, *index(); for (; isspace(*s); ++s); - if (*s == '\n') + if (*s == '\n' || *s == '\0') return (0); if ((p = index(s, '\n')) != NULL) *p = '\0'; - if (!strcmp(s, "R_CURSOR")) - return (R_CURSOR); - if (!strcmp(s, "R_FIRST")) - return (R_FIRST); - if (!strcmp(s, "R_IAFTER")) - return (R_IAFTER); - if (!strcmp(s, "R_IBEFORE")) - return (R_IBEFORE); - if (!strcmp(s, "R_LAST")) - return (R_LAST); - if (!strcmp(s, "R_NEXT")) - return (R_NEXT); - if (!strcmp(s, "R_NOOVERWRITE")) - return (R_NOOVERWRITE); - if (!strcmp(s, "R_PREV")) - return (R_PREV); - if (!strcmp(s, "R_SETCURSOR")) - return (R_SETCURSOR); + if (!strcmp(s, "R_CURSOR")) return (R_CURSOR); + if (!strcmp(s, "R_FIRST")) return (R_FIRST); + if (!strcmp(s, "R_IAFTER")) return (R_IAFTER); + if (!strcmp(s, "R_IBEFORE")) return (R_IBEFORE); + if (!strcmp(s, "R_LAST")) return (R_LAST); + if (!strcmp(s, "R_NEXT")) return (R_NEXT); + if (!strcmp(s, "R_NOOVERWRITE")) return (R_NOOVERWRITE); + if (!strcmp(s, "R_PREV")) return (R_PREV); + if (!strcmp(s, "R_SETCURSOR")) return (R_SETCURSOR); + err("line %lu: %s: unknown flag", lineno, s); /* NOTREACHED */ } + +char * +sflags(flags) + int flags; +{ + switch (flags) { + case R_CURSOR: return ("R_CURSOR"); + case R_FIRST: return ("R_FIRST"); + case R_IAFTER: return ("R_IAFTER"); + case R_IBEFORE: return ("R_IBEFORE"); + case R_LAST: return ("R_LAST"); + case R_NEXT: return ("R_NEXT"); + case R_NOOVERWRITE: return ("R_NOOVERWRITE"); + case R_PREV: return ("R_PREV"); + case R_SETCURSOR: return ("R_SETCURSOR"); + } + + return ("UNKNOWN!"); +} DBTYPE dbtype(s) @@ -513,7 +600,7 @@ setinfo(type, s) if (!isdigit(*eq)) err("%s: structure set statement must be a number", s); - switch(type) { + switch (type) { case DB_BTREE: if (!strcmp("flags", s)) { ib.flags = atoi(eq); diff --git a/regress/lib/libc/db/run.test b/regress/lib/libc/db/run.test index 4073310a311..acbd3f49e17 100644 --- a/regress/lib/libc/db/run.test +++ b/regress/lib/libc/db/run.test @@ -1,19 +1,27 @@ #!/bin/sh - -# $NetBSD: run.test,v 1.7 1995/04/20 22:39:27 cgd Exp $ # -# @(#)run.test 8.8 (Berkeley) 6/16/94 +# $NetBSD: run.test,v 1.8 1996/05/03 21:57:51 cgd Exp $ +# @(#)run.test 8.10 (Berkeley) 7/26/94 # # db regression tests main() { -DICT=/usr/share/dict/web2 -PROG=./dbtest -TMP1=t1 -TMP2=t2 -TMP3=t3 + PROG=./dbtest + TMP1=t1 + TMP2=t2 + TMP3=t3 + if [ -f /usr/share/dict/words ]; then + DICT=/usr/share/dict/words + elif [ -f /usr/dict/words ]; then + DICT=/usr/dict/words + else + echo 'run.test: no dictionary' + exit 1 + fi + if [ $# -eq 0 ]; then for t in 1 2 3 4 5 6 7 8 9 10 11 12 13 20; do test$t @@ -345,7 +353,7 @@ test7() for (i = 1; i <= 120; ++i) printf("%05d: input key %d: %s\n", i, i, $0); printf("%05d: input key %d: %s\n", 120, 120, $0); - printf("get failed, no such key\n"); + printf("seq failed, no such key\n"); printf("%05d: input key %d: %s\n", 1, 1, $0); printf("%05d: input key %d: %s\n", 2, 2, $0); exit; @@ -364,10 +372,10 @@ test7() for (i = 1; i <= 120; ++i) printf("s\n"); printf("fR_CURSOR\ns\nk120\n"); - printf("r\nk120\n"); + printf("r\n"); printf("fR_NEXT\ns\n"); printf("fR_CURSOR\ns\nk1\n"); - printf("r\nk1\n"); + printf("r\n"); printf("fR_FIRST\ns\n"); }' > $TMP2 $PROG -o $TMP3 recno $TMP2 @@ -397,8 +405,6 @@ test8() printf("e\t%d of 10 \n", i); printf("r\nkkey1\nr\nkkey2\n"); } - printf("e\n"); - printf("eend of test8 run\n"); }' > $TMP1 $PROG btree $TMP1 # $PROG hash $TMP1 @@ -459,7 +465,7 @@ test10() printf("p\nk%d\nd%s\n", ++i, $0); } END { - printf("fR_CURSOR\nr\nk1\n"); + printf("fR_CURSOR\nr\n"); printf("eR_CURSOR SHOULD HAVE FAILED\n"); }' > $TMP2 $PROG -o $TMP3 $type $TMP2 > /dev/null 2>&1 @@ -573,7 +579,8 @@ test13() echo g echo k$i done > $TMP2 - $PROG -ilorder=$order -f byte.file -o $TMP3 $type $TMP2 + $PROG -s \ + -ilorder=$order -f byte.file -o $TMP3 $type $TMP2 if (cmp -s $TMP1 $TMP3) ; then : else echo "test13: $type/$order get failed" -- 2.20.1