* Copyright (c) 1990, 1993
* The Regents of the University of California. All rights reserved.
* This code is derived from software contributed to Berkeley by
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* 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
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)bt_overflow.c 8.1 (Berkeley) 6/4/93";
#endif /* LIBC_SCCS and not lint */
* 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
* 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.
* p: pointer to { pgno_t, size_t }
__ovfl_get(t
, p
, ssz
, buf
, bufsz
)
memmove(&pg
, p
, sizeof(pgno_t
));
memmove(&sz
, (char *)p
+ sizeof(pgno_t
), sizeof(size_t));
if (pg
== P_INVALID
|| sz
== 0)
/* Make the buffer bigger as necessary. */
if ((*buf
= realloc(*buf
, sz
)) == NULL
)
* 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
)
memmove(p
, (char *)h
+ BTDATAOFF
, nb
);
mpool_put(t
->bt_mp
, h
, 0);
* __OVFL_PUT -- Store an overflow key/data item.
* pgno: storage page number
* 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
)
h
->nextpg
= h
->prevpg
= P_INVALID
;
memmove((char *)h
+ BTDATAOFF
, p
, nb
);
mpool_put(t
->bt_mp
, last
, MPOOL_DIRTY
);
mpool_put(t
->bt_mp
, h
, MPOOL_DIRTY
);
* __OVFL_DELETE -- Delete an overflow chain.
* p: pointer to { pgno_t, size_t }
memmove(&pg
, p
, sizeof(pgno_t
));
memmove(&sz
, (char *)p
+ sizeof(pgno_t
), sizeof(size_t));
if (pg
== P_INVALID
|| sz
== 0)
if ((h
= mpool_get(t
->bt_mp
, pg
, 0)) == NULL
)
/* Don't delete chains used by internal pages. */
if (h
->flags
& P_PRESERVE
) {
mpool_put(t
->bt_mp
, h
, 0);
/* Step through the chain, calling the free routine for each page. */
for (plen
= t
->bt_psize
- BTDATAOFF
;; sz
-= plen
) {
if ((h
= mpool_get(t
->bt_mp
, pg
, 0)) == NULL
)