diff options
Diffstat (limited to 'db')
42 files changed, 11409 insertions, 0 deletions
diff --git a/db/Makefile b/db/Makefile new file mode 100644 index 0000000000..c7a385a486 --- /dev/null +++ b/db/Makefile @@ -0,0 +1,28 @@ +# Makefile for 4.4BSD db code in GNU C library. +# This code is taken verbatim from the BSD db 1.85 package. Only this +# Makefile and compat.h were written for GNU libc, and the header files +# moved up to this directory. + +subdir = db + +dbdirs = btree db hash mpool recno +vpath %.c $(dbdirs) + +routines := bt_close bt_conv bt_debug bt_delete bt_get bt_open bt_overflow \ + bt_page bt_put bt_search bt_seq bt_split bt_utils \ + db \ + hash hash_bigkey hash_buf hash_func hash_log2 hash_page \ + ndbm \ + mpool \ + rec_close rec_delete rec_get rec_open rec_put rec_search \ + rec_seq rec_utils + +headers := db.h mpool.h ndbm.h +distribute := compat.h \ + btree/btree.h btree/extern.h \ + hash/extern.h hash/hash.h hash/page.h \ + recno/extern.h recno/recno.h + +include ../Rules + +CPPFLAGS += -D__DBINTERFACE_PRIVATE diff --git a/db/btree/bt_close.c b/db/btree/bt_close.c new file mode 100644 index 0000000000..27f9ab660f --- /dev/null +++ b/db/btree/bt_close.c @@ -0,0 +1,182 @@ +/*- + * 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) +static char sccsid[] = "@(#)bt_close.c 8.7 (Berkeley) 8/17/94"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/param.h> + +#include <errno.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#include <db.h> +#include "btree.h" + +static int bt_meta __P((BTREE *)); + +/* + * BT_CLOSE -- Close a btree. + * + * Parameters: + * dbp: pointer to access method + * + * Returns: + * RET_ERROR, RET_SUCCESS + */ +int +__bt_close(dbp) + DB *dbp; +{ + BTREE *t; + int fd; + + t = dbp->internal; + + /* Toss any page pinned across calls. */ + if (t->bt_pinned != NULL) { + mpool_put(t->bt_mp, t->bt_pinned, 0); + t->bt_pinned = NULL; + } + + /* 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); + + /* 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); + free(dbp); + return (close(fd) ? RET_ERROR : RET_SUCCESS); +} + +/* + * BT_SYNC -- sync the btree to disk. + * + * Parameters: + * dbp: pointer to access method + * + * Returns: + * RET_SUCCESS, RET_ERROR. + */ +int +__bt_sync(dbp, flags) + const DB *dbp; + u_int flags; +{ + BTREE *t; + int status; + + t = dbp->internal; + + /* Toss any page pinned across calls. */ + if (t->bt_pinned != NULL) { + mpool_put(t->bt_mp, t->bt_pinned, 0); + t->bt_pinned = NULL; + } + + /* Sync doesn't currently take any flags. */ + if (flags != 0) { + errno = EINVAL; + return (RET_ERROR); + } + + if (F_ISSET(t, B_INMEM | B_RDONLY) || !F_ISSET(t, B_MODIFIED)) + return (RET_SUCCESS); + + if (F_ISSET(t, B_METADIRTY) && bt_meta(t) == RET_ERROR) + return (RET_ERROR); + + if ((status = mpool_sync(t->bt_mp)) == RET_SUCCESS) + F_CLR(t, B_MODIFIED); + + return (status); +} + +/* + * BT_META -- write the tree meta data to disk. + * + * Parameters: + * t: tree + * + * Returns: + * RET_ERROR, RET_SUCCESS + */ +static int +bt_meta(t) + BTREE *t; +{ + BTMETA m; + void *p; + + if ((p = mpool_get(t->bt_mp, P_META, 0)) == NULL) + return (RET_ERROR); + + /* Fill in metadata. */ + 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); + return (RET_SUCCESS); +} diff --git a/db/btree/bt_conv.c b/db/btree/bt_conv.c new file mode 100644 index 0000000000..1cb208b14d --- /dev/null +++ b/db/btree/bt_conv.c @@ -0,0 +1,221 @@ +/*- + * 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) +static char sccsid[] = "@(#)bt_conv.c 8.5 (Berkeley) 8/17/94"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/param.h> + +#include <stdio.h> + +#include <db.h> +#include "btree.h" + +static void mswap __P((PAGE *)); + +/* + * __BT_BPGIN, __BT_BPGOUT -- + * Convert host-specific number layout to/from the host-independent + * format stored on disk. + * + * Parameters: + * t: tree + * pg: page number + * h: page to convert + */ +void +__bt_pgin(t, pg, pp) + void *t; + pgno_t pg; + void *pp; +{ + PAGE *h; + indx_t i, top; + u_char flags; + char *p; + + if (!F_ISSET(((BTREE *)t), B_NEEDSWAP)) + return; + if (pg == P_META) { + mswap(pp); + return; + } + + h = pp; + M_32_SWAP(h->pgno); + M_32_SWAP(h->prevpg); + M_32_SWAP(h->nextpg); + M_32_SWAP(h->flags); + M_16_SWAP(h->lower); + M_16_SWAP(h->upper); + + top = NEXTINDEX(h); + if ((h->flags & P_TYPE) == P_BINTERNAL) + for (i = 0; i < top; i++) { + M_16_SWAP(h->linp[i]); + p = (char *)GETBINTERNAL(h, i); + P_32_SWAP(p); + p += sizeof(u_int32_t); + P_32_SWAP(p); + p += sizeof(pgno_t); + if (*(u_char *)p & P_BIGKEY) { + p += sizeof(u_char); + P_32_SWAP(p); + p += sizeof(pgno_t); + P_32_SWAP(p); + } + } + else if ((h->flags & P_TYPE) == P_BLEAF) + for (i = 0; i < top; i++) { + M_16_SWAP(h->linp[i]); + p = (char *)GETBLEAF(h, i); + P_32_SWAP(p); + p += sizeof(u_int32_t); + P_32_SWAP(p); + p += sizeof(u_int32_t); + flags = *(u_char *)p; + if (flags & (P_BIGKEY | P_BIGDATA)) { + p += sizeof(u_char); + if (flags & P_BIGKEY) { + P_32_SWAP(p); + p += sizeof(pgno_t); + P_32_SWAP(p); + } + if (flags & P_BIGDATA) { + p += sizeof(u_int32_t); + P_32_SWAP(p); + p += sizeof(pgno_t); + P_32_SWAP(p); + } + } + } +} + +void +__bt_pgout(t, pg, pp) + void *t; + pgno_t pg; + void *pp; +{ + PAGE *h; + indx_t i, top; + u_char flags; + char *p; + + if (!F_ISSET(((BTREE *)t), B_NEEDSWAP)) + return; + if (pg == P_META) { + mswap(pp); + return; + } + + h = pp; + top = NEXTINDEX(h); + if ((h->flags & P_TYPE) == P_BINTERNAL) + for (i = 0; i < top; i++) { + p = (char *)GETBINTERNAL(h, i); + P_32_SWAP(p); + p += sizeof(u_int32_t); + P_32_SWAP(p); + p += sizeof(pgno_t); + if (*(u_char *)p & P_BIGKEY) { + p += sizeof(u_char); + P_32_SWAP(p); + p += sizeof(pgno_t); + P_32_SWAP(p); + } + M_16_SWAP(h->linp[i]); + } + else if ((h->flags & P_TYPE) == P_BLEAF) + for (i = 0; i < top; i++) { + p = (char *)GETBLEAF(h, i); + P_32_SWAP(p); + p += sizeof(u_int32_t); + P_32_SWAP(p); + p += sizeof(u_int32_t); + flags = *(u_char *)p; + if (flags & (P_BIGKEY | P_BIGDATA)) { + p += sizeof(u_char); + if (flags & P_BIGKEY) { + P_32_SWAP(p); + p += sizeof(pgno_t); + P_32_SWAP(p); + } + if (flags & P_BIGDATA) { + p += sizeof(u_int32_t); + P_32_SWAP(p); + p += sizeof(pgno_t); + P_32_SWAP(p); + } + } + M_16_SWAP(h->linp[i]); + } + + M_32_SWAP(h->pgno); + M_32_SWAP(h->prevpg); + M_32_SWAP(h->nextpg); + M_32_SWAP(h->flags); + M_16_SWAP(h->lower); + M_16_SWAP(h->upper); +} + +/* + * MSWAP -- Actually swap the bytes on the meta page. + * + * Parameters: + * p: page to convert + */ +static void +mswap(pg) + PAGE *pg; +{ + char *p; + + p = (char *)pg; + P_32_SWAP(p); /* magic */ + p += sizeof(u_int32_t); + P_32_SWAP(p); /* version */ + p += sizeof(u_int32_t); + P_32_SWAP(p); /* psize */ + p += sizeof(u_int32_t); + P_32_SWAP(p); /* free */ + p += sizeof(u_int32_t); + P_32_SWAP(p); /* nrecs */ + p += sizeof(u_int32_t); + P_32_SWAP(p); /* flags */ + p += sizeof(u_int32_t); +} diff --git a/db/btree/bt_debug.c b/db/btree/bt_debug.c new file mode 100644 index 0000000000..3aefbe7622 --- /dev/null +++ b/db/btree/bt_debug.c @@ -0,0 +1,329 @@ +/*- + * 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) +static char sccsid[] = "@(#)bt_debug.c 8.5 (Berkeley) 8/17/94"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/param.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <db.h> +#include "btree.h" + +#ifdef DEBUG +/* + * BT_DUMP -- Dump the tree + * + * Parameters: + * dbp: pointer to the DB + */ |