[apple/libc.git] / db / btree / bt_overflow.c

/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
 * Copyright (c) 1990, 1993
 *	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.
 */


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