1#pragma ident	"%Z%%M%	%I%	%E% SMI"
2
3/*-
4 * Copyright (c) 1990, 1993, 1994
5 *	The Regents of the University of California.  All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Mike Olson.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 3. All advertising materials mentioning features or use of this software
19 *    must display the following acknowledgement:
20 *	This product includes software developed by the University of
21 *	California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 *    may be used to endorse or promote products derived from this software
24 *    without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
37 */
38
39#if defined(LIBC_SCCS) && !defined(lint)
40static char sccsid[] = "@(#)bt_overflow.c	8.5 (Berkeley) 7/16/94";
41#endif /* LIBC_SCCS and not lint */
42
43#include <sys/param.h>
44
45#include <stdio.h>
46#include <stdlib.h>
47#include <string.h>
48
49#include "db-int.h"
50#include "btree.h"
51
52/*
53 * Big key/data code.
54 *
55 * Big key and data entries are stored on linked lists of pages.  The initial
56 * reference is byte string stored with the key or data and is the page number
57 * and size.  The actual record is stored in a chain of pages linked by the
58 * nextpg field of the PAGE header.
59 *
60 * The first page of the chain has a special property.  If the record is used
61 * by an internal page, it cannot be deleted and the P_PRESERVE bit will be set
62 * in the header.
63 *
64 * XXX
65 * A single DBT is written to each chain, so a lot of space on the last page
66 * is wasted.  This is a fairly major bug for some data sets.
67 */
68
69/*
70 * __OVFL_GET -- Get an overflow key/data item.
71 *
72 * Parameters:
73 *	t:	tree
74 *	p:	pointer to { db_pgno_t, u_int32_t }
75 *	buf:	storage address
76 *	bufsz:	storage size
77 *
78 * Returns:
79 *	RET_ERROR, RET_SUCCESS
80 */
81int
82__ovfl_get(t, p, ssz, buf, bufsz)
83	BTREE *t;
84	void *p;
85	size_t *ssz;
86	void **buf;
87	size_t *bufsz;
88{
89	PAGE *h;
90	db_pgno_t pg;
91	size_t nb, plen;
92	u_int32_t sz;
93
94	memmove(&pg, p, sizeof(db_pgno_t));
95	memmove(&sz, (char *)p + sizeof(db_pgno_t), sizeof(u_int32_t));
96	*ssz = sz;
97
98#ifdef DEBUG
99	if (pg == P_INVALID || sz == 0)
100		abort();
101#endif
102	/* Make the buffer bigger as necessary. */
103	if (*bufsz < sz) {
104		*buf = (char *)(*buf == NULL ? malloc(sz) : realloc(*buf, sz));
105		if (*buf == NULL)
106			return (RET_ERROR);
107		*bufsz = sz;
108	}
109
110	/*
111	 * Step through the linked list of pages, copying the data on each one
112	 * into the buffer.  Never copy more than the data's length.
113	 */
114	plen = t->bt_psize - BTDATAOFF;
115	for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) {
116		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
117			return (RET_ERROR);
118
119		nb = MIN(sz, plen);
120		memmove(p, (char *)h + BTDATAOFF, nb);
121		mpool_put(t->bt_mp, h, 0);
122
123		if ((sz -= nb) == 0)
124			break;
125	}
126	return (RET_SUCCESS);
127}
128
129/*
130 * __OVFL_PUT -- Store an overflow key/data item.
131 *
132 * Parameters:
133 *	t:	tree
134 *	data:	DBT to store
135 *	pgno:	storage page number
136 *
137 * Returns:
138 *	RET_ERROR, RET_SUCCESS
139 */
140int
141__ovfl_put(t, dbt, pg)
142	BTREE *t;
143	const DBT *dbt;
144	db_pgno_t *pg;
145{
146	PAGE *h, *last;
147	void *p;
148	db_pgno_t npg;
149	size_t nb, plen;
150	u_int32_t sz;
151
152	/*
153	 * Allocate pages and copy the key/data record into them.  Store the
154	 * number of the first page in the chain.
155	 */
156	plen = t->bt_psize - BTDATAOFF;
157	for (last = NULL, p = dbt->data, sz = dbt->size;;
158	    p = (char *)p + plen, last = h) {
159		if ((h = __bt_new(t, &npg)) == NULL)
160			return (RET_ERROR);
161
162		h->pgno = npg;
163		h->nextpg = h->prevpg = P_INVALID;
164		h->flags = P_OVERFLOW;
165		h->lower = h->upper = 0;
166
167		nb = MIN(sz, plen);
168		memmove((char *)h + BTDATAOFF, p, nb);
169
170		if (last) {
171			last->nextpg = h->pgno;
172			mpool_put(t->bt_mp, last, MPOOL_DIRTY);
173		} else
174			*pg = h->pgno;
175
176		if ((sz -= nb) == 0) {
177			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
178			break;
179		}
180	}
181	return (RET_SUCCESS);
182}
183
184/*
185 * __OVFL_DELETE -- Delete an overflow chain.
186 *
187 * Parameters:
188 *	t:	tree
189 *	p:	pointer to { db_pgno_t, u_int32_t }
190 *
191 * Returns:
192 *	RET_ERROR, RET_SUCCESS
193 */
194int
195__ovfl_delete(t, p)
196	BTREE *t;
197	void *p;
198{
199	PAGE *h;
200	db_pgno_t pg;
201	size_t plen;
202	u_int32_t sz;
203
204	memmove(&pg, p, sizeof(db_pgno_t));
205	memmove(&sz, (char *)p + sizeof(db_pgno_t), sizeof(u_int32_t));
206
207#ifdef DEBUG
208	if (pg == P_INVALID || sz == 0)
209		abort();
210#endif
211	if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
212		return (RET_ERROR);
213
214	/* Don't delete chains used by internal pages. */
215	if (h->flags & P_PRESERVE) {
216		mpool_put(t->bt_mp, h, 0);
217		return (RET_SUCCESS);
218	}
219
220	/* Step through the chain, calling the free routine for each page. */
221	for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) {
222		pg = h->nextpg;
223		__bt_free(t, h);
224		if (sz <= plen)
225			break;
226		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
227			return (RET_ERROR);
228	}
229	return (RET_SUCCESS);
230}
231