Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Browse files

Clean up deleted files.

  • Loading branch information...
commit fd2ebaac1322030a5c7ca0baaa5d4c14c4d84aa5 1 parent b7d601c
mycroft authored
View
224 lib/libc/DB/btree/bt_overflow.c
@@ -1,224 +0,0 @@
-/*-
- * Copyright (c) 1990 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_overflow.c 5.8 (Berkeley) 2/16/93";
-#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"
-
-/*
- * Big key/data code.
- *
- * Big key and data entries are stored on linked lists of pages. The initial
- * reference is byte string stored with the key or data and is the page number
- * and size. The actual record is stored in a chain of pages linked by the
- * nextpg field of the PAGE header.
- *
- * The first page of the chain has a special property. If the record is used
- * by an internal page, it cannot be deleted and the P_PRESERVE bit will be set
- * in the header.
- *
- * XXX
- * A single DBT is written to each chain, so a lot of space on the last page
- * is wasted. This is a fairly major bug for some data sets.
- */
-
-/*
- * __OVFL_GET -- Get an overflow key/data item.
- *
- * Parameters:
- * t: tree
- * p: pointer to { pgno_t, size_t }
- * buf: storage address
- * bufsz: storage size
- *
- * Returns:
- * RET_ERROR, RET_SUCCESS
- */
-int
-__ovfl_get(t, p, ssz, buf, bufsz)
- BTREE *t;
- void *p;
- size_t *ssz;
- char **buf;
- size_t *bufsz;
-{
- PAGE *h;
- pgno_t pg;
- size_t nb, plen, sz;
-
- memmove(&pg, p, sizeof(pgno_t));
- memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(size_t));
- *ssz = sz;
-
-#ifdef DEBUG
- if (pg == P_INVALID || sz == 0)
- abort();
-#endif
- /* Make the buffer bigger as necessary. */
- if (*bufsz < sz) {
- if ((*buf = realloc(*buf, sz)) == NULL)
- return (RET_ERROR);
- *bufsz = sz;
- }
-
- /*
- * Step through the linked list of pages, copying the data on each one
- * into the buffer. Never copy more than the data's length.
- */
- plen = t->bt_psize - BTDATAOFF;
- for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) {
- if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
- return (RET_ERROR);
-
- nb = MIN(sz, plen);
- memmove(p, (char *)h + BTDATAOFF, nb);
- mpool_put(t->bt_mp, h, 0);
-
- if ((sz -= nb) == 0)
- break;
- }
- return (RET_SUCCESS);
-}
-
-/*
- * __OVFL_PUT -- Store an overflow key/data item.
- *
- * Parameters:
- * t: tree
- * data: DBT to store
- * pgno: storage page number
- *
- * Returns:
- * RET_ERROR, RET_SUCCESS
- */
-int
-__ovfl_put(t, dbt, pg)
- BTREE *t;
- const DBT *dbt;
- pgno_t *pg;
-{
- PAGE *h, *last;
- void *p;
- pgno_t npg;
- size_t nb, plen, sz;
-
- /*
- * Allocate pages and copy the key/data record into them. Store the
- * number of the first page in the chain.
- */
- plen = t->bt_psize - BTDATAOFF;
- for (last = NULL, p = dbt->data, sz = dbt->size;;
- p = (char *)p + plen, last = h) {
- if ((h = __bt_new(t, &npg)) == NULL)
- return (RET_ERROR);
-
- h->pgno = npg;
- h->nextpg = h->prevpg = P_INVALID;
- h->flags = P_OVERFLOW;
- h->lower = h->upper = 0;
-
- nb = MIN(sz, plen);
- memmove((char *)h + BTDATAOFF, p, nb);
-
- if (last) {
- last->nextpg = h->pgno;
- mpool_put(t->bt_mp, last, MPOOL_DIRTY);
- } else
- *pg = h->pgno;
-
- if ((sz -= nb) == 0) {
- mpool_put(t->bt_mp, h, MPOOL_DIRTY);
- break;
- }
- }
- return (RET_SUCCESS);
-}
-
-/*
- * __OVFL_DELETE -- Delete an overflow chain.
- *
- * Parameters:
- * t: tree
- * p: pointer to { pgno_t, size_t }
- *
- * Returns:
- * RET_ERROR, RET_SUCCESS
- */
-int
-__ovfl_delete(t, p)
- BTREE *t;
- void *p;
-{
- PAGE *h;
- pgno_t pg;
- size_t plen, sz;
-
- memmove(&pg, p, sizeof(pgno_t));
- memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(size_t));
-
-#ifdef DEBUG
- if (pg == P_INVALID || sz == 0)
- abort();
-#endif
- if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
- return (RET_ERROR);
-
- /* Don't delete chains used by internal pages. */
- if (h->flags & P_PRESERVE) {
- mpool_put(t->bt_mp, h, 0);
- return (RET_SUCCESS);
- }
-
- /* Step through the chain, calling the free routine for each page. */
- for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) {
- pg = h->nextpg;
- __bt_free(t, h);
- if (sz <= plen)
- break;
- if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
- return (RET_ERROR);
- }
- return (RET_SUCCESS);
-}
View
94 lib/libc/DB/btree/bt_page.c
@@ -1,94 +0,0 @@
-/*-
- * Copyright (c) 1990 The Regents of the University of California.
- * All rights reserved.
- *
- * 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_page.c 5.3 (Berkeley) 2/11/93";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#define __DBINTERFACE_PRIVATE
-#include <stdio.h>
-
-#include <db.h>
-#include "btree.h"
-
-/*
- * __BT_FREE -- Put a page on the freelist.
- *
- * Parameters:
- * t: tree
- * h: page to free
- *
- * Returns:
- * RET_ERROR, RET_SUCCESS
- */
-int
-__bt_free(t, h)
- BTREE *t;
- PAGE *h;
-{
- /* Insert the page at the start of the free list. */
- h->prevpg = P_INVALID;
- h->nextpg = t->bt_free;
- t->bt_free = h->pgno;
-
- /* Make sure the page gets written back. */
- return (mpool_put(t->bt_mp, h, MPOOL_DIRTY));
-}
-
-/*
- * __BT_NEW -- Get a new page, preferably from the freelist.
- *
- * Parameters:
- * t: tree
- * npg: storage for page number.
- *
- * Returns:
- * Pointer to a page, NULL on error.
- */
-PAGE *
-__bt_new(t, npg)
- BTREE *t;
- pgno_t *npg;
-{
- PAGE *h;
-
- 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);
- }
- return (mpool_new(t->bt_mp, npg));
-}
View
119 lib/libc/DB/btree/bt_search.c
@@ -1,119 +0,0 @@
-/*-
- * Copyright (c) 1990 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_search.c 5.9 (Berkeley) 2/14/93";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <stdio.h>
-
-#include <db.h>
-#include "btree.h"
-
-/*
- * __BT_SEARCH -- Search a btree for a key.
- *
- * Parameters:
- * t: tree to search
- * key: key to find
- * exactp: pointer to exact match flag
- *
- * Returns:
- * EPG for matching record, if any, or the EPG for the location of the
- * key, if it were inserted into the tree.
- *
- * Warnings:
- * The EPG returned is in static memory, and will be overwritten by the
- * next search of any kind in any tree.
- */
-EPG *
-__bt_search(t, key, exactp)
- BTREE *t;
- const DBT *key;
- int *exactp;
-{
- register indx_t index;
- register int base, cmp, lim;
- register PAGE *h;
- pgno_t pg;
- static EPG e;
-
- BT_CLR(t);
- for (pg = P_ROOT;;) {
- if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
- return (NULL);
-
- /* Do a binary search on the current page. */
- e.page = h;
- for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
- e.index = index = base + (lim >> 1);
- if ((cmp = __bt_cmp(t, key, &e)) == 0) {
- if (h->flags & P_BLEAF) {
- *exactp = 1;
- return (&e);
- }
- goto next;
- }
- if (cmp > 0) {
- base = index + 1;
- --lim;
- }
- }
-
- /* If it's a leaf page, we're done. */
- if (h->flags & P_BLEAF) {
- e.index = base;
- *exactp = 0;
- return (&e);
- }
-
- /*
- * No match found. Base is the smallest index greater than
- * key and may be zero or a last + 1 index. If it's non-zero,
- * decrement by one, and record the internal page which should
- * be a parent page for the key. If a split later occurs, the
- * inserted page will be to the right of the saved page.
- */
- index = base ? base - 1 : base;
-
-next: if (__bt_push(t, h->pgno, index) == RET_ERROR)
- return (NULL);
- pg = GETBINTERNAL(h, index)->pgno;
- mpool_put(t->bt_mp, h, 0);
- }
-}
View
92 lib/libc/DB/btree/bt_stack.c
@@ -1,92 +0,0 @@
-/*-
- * Copyright (c) 1990 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_stack.c 5.4 (Berkeley) 2/11/93";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <errno.h>
-#include <stdio.h>
-#include <stdlib.h>
-
-#include <db.h>
-#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;
- int index;
-{
- if (t->bt_sp == t->bt_maxstack) {
- t->bt_maxstack += 50;
- if ((t->bt_stack = realloc(t->bt_stack,
- t->bt_maxstack * sizeof(EPGNO))) == 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);
-}
View
344 lib/libc/DB/hash/hash_buf.c
@@ -1,344 +0,0 @@
-/*-
- * Copyright (c) 1990 The Regents of the University of California.
- * All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Margo Seltzer.
- *
- * 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[] = "@(#)hash_buf.c 5.12 (Berkeley) 2/11/93";
-#endif /* LIBC_SCCS and not lint */
-
-/*
- * PACKAGE: hash
- *
- * DESCRIPTION:
- * Contains buffer management
- *
- * ROUTINES:
- * External
- * __buf_init
- * __get_buf
- * __buf_free
- * __reclaim_buf
- * Internal
- * newbuf
- */
-
-#include <sys/param.h>
-
-#include <errno.h>
-#include <stdio.h>
-#include <stdlib.h>
-#ifdef DEBUG
-#include <assert.h>
-#endif
-
-#include <db.h>
-#include "hash.h"
-#include "page.h"
-#include "extern.h"
-
-static BUFHEAD *newbuf __P((HTAB *, u_int, BUFHEAD *));
-
-/* Unlink B from its place in the lru */
-#define BUF_REMOVE(B) { \
- (B)->prev->next = (B)->next; \
- (B)->next->prev = (B)->prev; \
-}
-
-/* Insert B after P */
-#define BUF_INSERT(B, P) { \
- (B)->next = (P)->next; \
- (B)->prev = (P); \
- (P)->next = (B); \
- (B)->next->prev = (B); \
-}
-
-#define MRU hashp->bufhead.next
-#define LRU hashp->bufhead.prev
-
-#define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead)
-#define LRU_INSERT(B) BUF_INSERT((B), LRU)
-
-/*
- * We are looking for a buffer with address "addr". If prev_bp is NULL, then
- * address is a bucket index. If prev_bp is not NULL, then it points to the
- * page previous to an overflow page that we are trying to find.
- *
- * CAVEAT: The buffer header accessed via prev_bp's ovfl field may no longer
- * be valid. Therefore, you must always verify that its address matches the
- * address you are seeking.
- */
-extern BUFHEAD *
-__get_buf(hashp, addr, prev_bp, newpage)
- HTAB *hashp;
- u_int addr;
- BUFHEAD *prev_bp;
- int newpage; /* If prev_bp set, indicates a new overflow page. */
-{
- register BUFHEAD *bp;
- register u_int is_disk_mask;
- register int is_disk, segment_ndx;
- SEGMENT segp;
-
- is_disk = 0;
- is_disk_mask = 0;
- if (prev_bp) {
- bp = prev_bp->ovfl;
- if (!bp || (bp->addr != addr))
- bp = NULL;
- if (!newpage)
- is_disk = BUF_DISK;
- } else {
- /* Grab buffer out of directory */
- segment_ndx = addr & (hashp->SGSIZE - 1);
-
- /* valid segment ensured by __call_hash() */
- segp = hashp->dir[addr >> hashp->SSHIFT];
-#ifdef DEBUG
- assert(segp != NULL);
-#endif
- bp = PTROF(segp[segment_ndx]);
- is_disk_mask = ISDISK(segp[segment_ndx]);
- is_disk = is_disk_mask || !hashp->new_file;
- }
-
- if (!bp) {
- bp = newbuf(hashp, addr, prev_bp);
- if (!bp ||
- __get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0))
- return (NULL);
- if (!prev_bp)
- segp[segment_ndx] =
- (BUFHEAD *)((u_int)bp | is_disk_mask);
- } else {
- BUF_REMOVE(bp);
- MRU_INSERT(bp);
- }
- return (bp);
-}
-
-/*
- * We need a buffer for this page. Either allocate one, or evict a resident
- * one (if we have as many buffers as we're allowed) and put this one in.
- *
- * If newbuf finds an error (returning NULL), it also sets errno.
- */
-static BUFHEAD *
-newbuf(hashp, addr, prev_bp)
- HTAB *hashp;
- u_int addr;
- BUFHEAD *prev_bp;
-{
- register BUFHEAD *bp; /* The buffer we're going to use */
- register BUFHEAD *xbp; /* Temp pointer */
- register BUFHEAD *next_xbp;
- SEGMENT segp;
- int segment_ndx;
- u_short oaddr, *shortp;
-
- oaddr = 0;
- bp = LRU;
- /*
- * If LRU buffer is pinned, the buffer pool is too small. We need to
- * allocate more buffers.
- */
- if (hashp->nbufs || (bp->flags & BUF_PIN)) {
- /* Allocate a new one */
- bp = malloc(sizeof(struct _bufhead));
- if (!bp || !(bp->page = malloc(hashp->BSIZE)))
- return (NULL);
- if (hashp->nbufs)
- hashp->nbufs--;
- } else {
- /* Kick someone out */
- BUF_REMOVE(bp);
- /*
- * If this is an overflow page with addr 0, it's already been
- * flushed back in an overflow chain and initialized.
- */
- if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) {
- /*
- * Set oaddr before __put_page so that you get it
- * before bytes are swapped.
- */
- shortp = (u_short *)bp->page;
- if (shortp[0])
- oaddr = shortp[shortp[0] - 1];
- if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page,
- bp->addr, (int)IS_BUCKET(bp->flags), 0))
- return (NULL);
- /*
- * Update the pointer to this page (i.e. invalidate it).
- *
- * If this is a new file (i.e. we created it at open
- * time), make sure that we mark pages which have been
- * written to disk so we retrieve them from disk later,
- * rather than allocating new pages.
- */
- if (IS_BUCKET(bp->flags)) {
- segment_ndx = bp->addr & (hashp->SGSIZE - 1);
- segp = hashp->dir[bp->addr >> hashp->SSHIFT];
-#ifdef DEBUG
- assert(segp != NULL);
-#endif
-
- if (hashp->new_file &&
- ((bp->flags & BUF_MOD) ||
- ISDISK(segp[segment_ndx])))
- segp[segment_ndx] = (BUFHEAD *)BUF_DISK;
- else
- segp[segment_ndx] = NULL;
- }
- /*
- * Since overflow pages can only be access by means of
- * their bucket, free overflow pages associated with
- * this bucket.
- */
- for (xbp = bp; xbp->ovfl;) {
- next_xbp = xbp->ovfl;
- xbp->ovfl = 0;
- xbp = next_xbp;
-
- /* Check that ovfl pointer is up date. */
- if (IS_BUCKET(xbp->flags) ||
- (oaddr != xbp->addr))
- break;
-
- shortp = (u_short *)xbp->page;
- if (shortp[0])
- /* set before __put_page */
- oaddr = shortp[shortp[0] - 1];
- if ((xbp->flags & BUF_MOD) && __put_page(hashp,
- xbp->page, xbp->addr, 0, 0))
- return (NULL);
- xbp->addr = 0;
- xbp->flags = 0;
- BUF_REMOVE(xbp);
- LRU_INSERT(xbp);
- }
- }
- }
-
- /* Now assign this buffer */
- bp->addr = addr;
-#ifdef DEBUG1
- (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n",
- bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0);
-#endif
- bp->ovfl = NULL;
- if (prev_bp) {
- /*
- * If prev_bp is set, this is an overflow page, hook it in to
- * the buffer overflow links.
- */
-#ifdef DEBUG1
- (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n",
- prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0),
- (bp ? bp->addr : 0));
-#endif
- prev_bp->ovfl = bp;
- bp->flags = 0;
- } else
- bp->flags = BUF_BUCKET;
- MRU_INSERT(bp);
- return (bp);
-}
-
-extern void
-__buf_init(hashp, nbytes)
- HTAB *hashp;
- int nbytes;
-{
- BUFHEAD *bfp;
- int npages;
-
- bfp = &(hashp->bufhead);
- npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT;
- npages = MAX(npages, MIN_BUFFERS);
-
- hashp->nbufs = npages;
- bfp->next = bfp;
- bfp->prev = bfp;
- /*
- * This space is calloc'd so these are already null.
- *
- * bfp->ovfl = NULL;
- * bfp->flags = 0;
- * bfp->page = NULL;
- * bfp->addr = 0;
- */
-}
-
-extern int
-__buf_free(hashp, do_free, to_disk)
- HTAB *hashp;
- int do_free, to_disk;
-{
- BUFHEAD *bp;
-
- /* Need to make sure that buffer manager has been initialized */
- if (!LRU)
- return (0);
- for (bp = LRU; bp != &hashp->bufhead;) {
- /* Check that the buffer is valid */
- if (bp->addr || IS_BUCKET(bp->flags)) {
- if (to_disk && (bp->flags & BUF_MOD) &&
- __put_page(hashp, bp->page,
- bp->addr, IS_BUCKET(bp->flags), 0))
- return (-1);
- }
- /* Check if we are freeing stuff */
- if (do_free) {
- if (bp->page)
- free(bp->page);
- BUF_REMOVE(bp);
- free(bp);
- bp = LRU;
- } else
- bp = bp->prev;
- }
- return (0);
-}
-
-extern void
-__reclaim_buf(hashp, bp)
- HTAB *hashp;
- BUFHEAD *bp;
-{
- bp->ovfl = 0;
- bp->addr = 0;
- bp->flags = 0;
- BUF_REMOVE(bp);
- LRU_INSERT(bp);
-}
View
191 lib/libc/DB/hash/hash_func.c
@@ -1,191 +0,0 @@
-/*-
- * Copyright (c) 1990 The Regents of the University of California.
- * All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Margo Seltzer.
- *
- * 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[] = "@(#)hash_func.c 5.4 (Berkeley) 2/11/93";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <db.h>
-#include "hash.h"
-#include "page.h"
-#include "extern.h"
-
-static int hash1 __P((u_char *, int));
-static int hash2 __P((u_char *, int));
-static int hash3 __P((u_char *, int));
-static int hash4 __P((u_char *, int));
-
-/* Global default hash function */
-int (*__default_hash) __P((u_char *, int)) = hash4;
-
-/******************************* HASH FUNCTIONS **************************/
-/*
- * Assume that we've already split the bucket to which this key hashes,
- * calculate that bucket, and check that in fact we did already split it.
- *
- * This came from ejb's hsearch.
- */
-
-#define PRIME1 37
-#define PRIME2 1048583
-
-static int
-hash1(key, len)
- register u_char *key;
- register int len;
-{
- register int h;
-
- h = 0;
- /* Convert string to integer */
- while (len--)
- h = h * PRIME1 ^ (*key++ - ' ');
- h %= PRIME2;
- return (h);
-}
-
-/*
- * Phong's linear congruential hash
- */
-#define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
-
-static int
-hash2(key, len)
- register u_char *key;
- int len;
-{
- register u_char *e, c;
- register int h;
-
- e = key + len;
- for (h = 0; key != e;) {
- c = *key++;
- if (!c && key > e)
- break;
- dcharhash(h, c);
- }
- return (h);
-}
-
-/*
- * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte
- * units. On the first time through the loop we get the "leftover bytes"
- * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle
- * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If
- * this routine is heavily used enough, it's worth the ugly coding.
- *
- * OZ's original sdbm hash
- */
-static int
-hash3(key, len)
- register u_char *key;
- register int len;
-{
- register int n, loop;
-
-#define HASHC n = *key++ + 65599 * n
-
- n = 0;
- if (len > 0) {
- loop = (len + 8 - 1) >> 3;
-
- switch (len & (8 - 1)) {
- case 0:
- do { /* All fall throughs */
- HASHC;
- case 7:
- HASHC;
- case 6:
- HASHC;
- case 5:
- HASHC;
- case 4:
- HASHC;
- case 3:
- HASHC;
- case 2:
- HASHC;
- case 1:
- HASHC;
- } while (--loop);
- }
-
- }
- return (n);
-}
-
-/* Hash function from Chris Torek. */
-static int
-hash4(key, len)
- register u_char *key;
- register int len;
-{
- register int h, loop;
-
-#define HASH4a h = (h << 5) - h + *key++;
-#define HASH4b h = (h << 5) + h + *key++;
-#define HASH4 HASH4b
-
- h = 0;
- if (len > 0) {
- loop = (len + 8 - 1) >> 3;
-
- switch (len & (8 - 1)) {
- case 0:
- do { /* All fall throughs */
- HASH4;
- case 7:
- HASH4;
- case 6:
- HASH4;
- case 5:
- HASH4;
- case 4:
- HASH4;
- case 3:
- HASH4;
- case 2:
- HASH4;
- case 1:
- HASH4;
- } while (--loop);
- }
-
- }
- return (h);
-}
View
52 lib/libc/DB/hash/hash_log2.c
@@ -1,52 +0,0 @@
-/*-
- * Copyright (c) 1990 The Regents of the University of California.
- * All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Margo Seltzer.
- *
- * 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[] = "@(#)hash_log2.c 5.4 (Berkeley) 9/26/91";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-u_int
-__log2(num)
- u_int num;
-{
- register u_int i, limit;
-
- limit = 1;
- for (i = 0; limit < num; limit = limit << 1, i++);
- return (i);
-}
View
108 lib/libc/DB/hash/hsearch.c
@@ -1,108 +0,0 @@
-/*-
- * Copyright (c) 1990 The Regents of the University of California.
- * All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Margo Seltzer.
- *
- * 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[] = "@(#)hsearch.c 5.8 (Berkeley) 2/11/93";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <fcntl.h>
-#include <string.h>
-
-#define __DBINTERFACE_PRIVATE
-#include <db.h>
-#include "search.h"
-
-static DB *dbp = NULL;
-static ENTRY retval;
-
-extern int
-hcreate(nel)
- u_int nel;
-{
- HASHINFO info;
-
- info.nelem = nel;
- info.bsize = 256;
- info.ffactor = 8;
- info.cachesize = NULL;
- info.hash = NULL;
- info.lorder = 0;
- dbp = (DB *)__hash_open(NULL, O_CREAT | O_RDWR, 0600, &info);
- return ((int)dbp);
-}
-
-extern ENTRY *
-hsearch(item, action)
- ENTRY item;
- ACTION action;
-{
- DBT key, val;
- int status;
-
- if (!dbp)
- return (NULL);
- key.data = (u_char *)item.key;
- key.size = strlen(item.key) + 1;
-
- if (action == ENTER) {
- val.data = (u_char *)item.data;
- val.size = strlen(item.data) + 1;
- status = (dbp->put)(dbp, &key, &val, R_NOOVERWRITE);
- if (status)
- return (NULL);
- } else {
- /* FIND */
- status = (dbp->get)(dbp, &key, &val, 0);
- if (status)
- return (NULL);
- else
- item.data = (char *)val.data;
- }
- retval.key = item.key;
- retval.data = item.data;
- return (&retval);
-}
-
-extern void
-hdestroy()
-{
- if (dbp) {
- (void)(dbp->close)(dbp);
- dbp = NULL;
- }
-}
View
51 lib/libc/DB/hash/search.h
@@ -1,51 +0,0 @@
-/*-
- * Copyright (c) 1990 The Regents of the University of California.
- * All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Margo Seltzer.
- *
- * 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.
- *
- * @(#)search.h 5.2 (Berkeley) 9/4/91
- */
-
-/* Backward compatibility to hsearch interface. */
-typedef struct entry {
- char *key;
- char *data;
-} ENTRY;
-
-typedef enum {
- FIND, ENTER
-} ACTION;
-
-int hcreate __P((unsigned int));
-void hdestroy __P((void));
-ENTRY *hsearch __P((ENTRY, ACTION));
View
88 lib/libc/DB/hash/tests/tseq.c
@@ -1,88 +0,0 @@
-/*-
- * Copyright (c) 1991 The Regents of the University of California.
- * All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Margo Seltzer.
- *
- * 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.
- */
-
-#ifndef lint
-char copyright[] =
-"@(#) Copyright (c) 1991 The Regents of the University of California.\n\
- All rights reserved.\n";
-#endif /* not lint */
-
-#ifndef lint
-static char sccsid[] = "@(#)tseq.c 5.4 (Berkeley) 9/11/91";
-#endif /* not lint */
-
-#include <sys/types.h>
-#include <sys/file.h>
-#include <stdio.h>
-#include <db.h>
-
-#define INITIAL 25000
-#define MAXWORDS 25000 /* # of elements in search table */
-
-
-char wp[8192];
-char cp[8192];
-main(argc, argv)
-char **argv;
-{
- DBT item, key, res;
- DB *dbp;
- FILE *fp;
- int stat;
-
- if (!(dbp = dbopen( "hashtest", O_RDONLY, 0400, DB_HASH, NULL))) {
- /* create table */
- fprintf(stderr, "cannot open: hash table\n" );
- exit(1);
- }
-
-/*
-* put info in structure, and structure in the item
-*/
- for ( stat = (dbp->seq) (dbp, &res, &item, 1 );
- stat == 0;
- stat = (dbp->seq) (dbp, &res, &item, 0 ) ) {
-
- bcopy ( res.data, wp, res.size );
- wp[res.size] = 0;
- bcopy ( item.data, cp, item.size );
- cp[item.size] = 0;
-
- printf ( "%s %s\n", wp, cp );
- }
- (dbp->close)(dbp);
- exit(0);
-}
View
107 lib/libc/DB/hash/tests/tverify.c
@@ -1,107 +0,0 @@
-/*-
- * Copyright (c) 1991 The Regents of the University of California.
- * All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Margo Seltzer.
- *
- * 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.
- */
-
-#ifndef lint
-char copyright[] =
-"@(#) Copyright (c) 1991 The Regents of the University of California.\n\
- All rights reserved.\n";
-#endif /* not lint */
-
-#ifndef lint
-static char sccsid[] = "@(#)tverify.c 5.5 (Berkeley) 9/11/91";
-#endif /* not lint */
-
-#include <sys/types.h>
-#include <sys/file.h>
-#include <stdio.h>
-#include <db.h>
-
-#define INITIAL 25000
-#define MAXWORDS 25000 /* # of elements in search table */
-
-typedef struct { /* info to be stored */
- int num, siz;
-} info;
-
-char wp1[8192];
-char wp2[8192];
-main(argc, argv)
-char **argv;
-{
- DBT key, res;
- DB *dbp;
- HASHINFO ctl;
- int trash;
- int stat;
-
- int i = 0;
-
- ctl.nelem = INITIAL;
- ctl.hash = NULL;
- ctl.bsize = 64;
- ctl.ffactor = 1;
- ctl.cachesize = 1024 * 1024; /* 1 MEG */
- ctl.lorder = 0;
- if (!(dbp = dbopen( "hashtest", O_RDONLY, 0400, DB_HASH, &ctl))) {
- /* create table */
- fprintf(stderr, "cannot open: hash table\n" );
- exit(1);
- }
-
- key.data = wp1;
- while ( fgets(wp1, 8192, stdin) &&
- fgets(wp2, 8192, stdin) &&
- i++ < MAXWORDS) {
-/*
-* put info in structure, and structure in the item
-*/
- key.size = strlen(wp1);
-
- stat = (dbp->get)(dbp, &key, &res,0);
- if (stat < 0) {
- fprintf ( stderr, "Error retrieving %s\n", key.data );
- exit(1);
- } else if ( stat > 0 ) {
- fprintf ( stderr, "%s not found\n", key.data );
- exit(1);
- }
- if ( memcmp ( res.data, wp2, res.size ) ) {
- fprintf ( stderr, "data for %s is incorrect. Data was %s. Should have been %s\n", key.data, res.data, wp2 );
- }
- }
- (dbp->close)(dbp);
- exit(0);
-}
View
127 lib/libc/DB/recno/rec_search.c
@@ -1,127 +0,0 @@
-/*-
- * Copyright (c) 1990 The Regents of the University of California.
- * All rights reserved.
- *
- * 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[] = "@(#)rec_search.c 5.8 (Berkeley) 2/14/93";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <errno.h>
-#include <stdio.h>
-
-#include <db.h>
-#include "recno.h"
-
-/*
- * __REC_SEARCH -- Search a btree for a key.
- *
- * Parameters:
- * t: tree to search
- * recno: key to find
- * op: search operation
- *
- * Returns:
- * EPG for matching record, if any, or the EPG for the location of the
- * key, if it were inserted into the tree.
- *
- * Warnings:
- * The EPG returned is in static memory, and will be overwritten by the
- * next search of any kind in any tree.
- */
-EPG *
-__rec_search(t, recno, op)
- BTREE *t;
- recno_t recno;
- enum SRCHOP op;
-{
- static EPG e;
- register indx_t index;
- register PAGE *h;
- EPGNO *parent;
- RINTERNAL *r;
- pgno_t pg;
- indx_t top;
- recno_t total;
- int serrno;
-
- BT_CLR(t);
- for (pg = P_ROOT, total = 0;;) {
- if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
- goto err;
- if (h->flags & P_RLEAF) {
- e.page = h;
- e.index = recno - total;
- return (&e);
- }
- for (index = 0, top = NEXTINDEX(h);;) {
- r = GETRINTERNAL(h, index);
- if (++index == top || total + r->nrecs > recno)
- break;
- total += r->nrecs;
- }
-
- if (__bt_push(t, pg, index - 1) == RET_ERROR)
- return (NULL);
-
- pg = r->pgno;
- switch (op) {
- case SDELETE:
- --GETRINTERNAL(h, (index - 1))->nrecs;
- mpool_put(t->bt_mp, h, MPOOL_DIRTY);
- break;
- case SINSERT:
- ++GETRINTERNAL(h, (index - 1))->nrecs;
- mpool_put(t->bt_mp, h, MPOOL_DIRTY);
- break;
- case SEARCH:
- mpool_put(t->bt_mp, h, 0);
- break;
- }
-
- }
- /* Try and recover the tree. */
-err: serrno = errno;
- if (op != SEARCH)
- while ((parent = BT_POP(t)) != NULL) {
- if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
- break;
- if (op == SINSERT)
- --GETRINTERNAL(h, parent->index)->nrecs;
- else
- ++GETRINTERNAL(h, parent->index)->nrecs;
- mpool_put(t->bt_mp, h, MPOOL_DIRTY);
- }
- errno = serrno;
- return (NULL);
-}
View
103 lib/libc/DB/recno/rec_utils.c
@@ -1,103 +0,0 @@
-/*-
- * Copyright (c) 1990 The Regents of the University of California.
- * All rights reserved.
- *
- * 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[] = "@(#)rec_utils.c 5.7 (Berkeley) 2/16/93";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/param.h>
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include <db.h>
-#include "recno.h"
-
-/*
- * __REC_RET -- Build return data as a result of search or scan.
- *
- * Parameters:
- * t: tree
- * d: LEAF to be returned to the user.
- * data: user's data structure
- *
- * Returns:
- * RET_SUCCESS, RET_ERROR.
- */
-int
-__rec_ret(t, e, nrec, key, data)
- BTREE *t;
- EPG *e;
- recno_t nrec;
- DBT *key, *data;
-{
- register RLEAF *rl;
- register void *p;
-
- if (data == NULL)
- goto retkey;
-
- 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))
- return (RET_ERROR);
- } else {
- /* Use +1 in case the first record retrieved is 0 length. */
- if (rl->dsize + 1 > t->bt_dbufsz) {
- if ((p = realloc(t->bt_dbuf, rl->dsize + 1)) == NULL)
- return (RET_ERROR);
- t->bt_dbuf = p;
- t->bt_dbufsz = rl->dsize + 1;
- }
- memmove(t->bt_dbuf, rl->bytes, rl->dsize);
- data->size = rl->dsize;
- }
- data->data = t->bt_dbuf;
-
-retkey: if (key == NULL)
- return (RET_SUCCESS);
-
- if (sizeof(recno_t) > t->bt_kbufsz) {
- if ((p = realloc(t->bt_kbuf, sizeof(recno_t))) == 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);
-}
View
39 lib/libc/DB/recno/recno.h
@@ -1,39 +0,0 @@
-/*-
- * Copyright (c) 1991 The Regents of the University of California.
- * All rights reserved.
- *
- * 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.
- *
- * @(#)recno.h 5.1 (Berkeley) 9/11/91
- */
-
-enum SRCHOP { SDELETE, SINSERT, SEARCH}; /* Rec_search operation. */
-
-#include "../btree/btree.h"
-#include "extern.h"
Please sign in to comment.
Something went wrong with that request. Please try again.