[unix-history] / lib / libc / db / btree / insert.c

/*-
 * 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[] = "@(#)insert.c	5.3 (Berkeley) 2/22/91";
#endif /* LIBC_SCCS and not lint */

#include <sys/types.h>
#include <db.h>
#include <stdlib.h>
#include <string.h>
#include "btree.h"

/*
 *  _BT_INSERT -- Insert a new user datum in the btree.
 *
 *	This routine is called by bt_put, the public interface, once the
 *	location for the new item is known.  We do the work here, and
 *	handle splits if necessary.
 *
 *	Parameters:
 *		t -- btree in which to do the insertion.
 *		item -- BTITEM describing location of new datum
 *		key -- key to insert
 *		data -- data associated with key
 *		flag -- magic cookie passed recursively to bt_put if we
 *			have to do a split
 *
 *	Returns:
 *		RET_SUCCESS, RET_ERROR.
 */

int
_bt_insert(t, item, key, data, flag)
	BTREE_P t;
	BTITEM *item;
	DBT *key;
	DBT *data;
	int flag;
{
	index_t index;
	BTHEADER *h;
	DATUM *d;
	int nbytes;
	int status;
	pgno_t pgno;
	int keysize, datasize;
	int bigkey, bigdata;

	if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
		return (RET_ERROR);
	h = t->bt_curpage;

	if (TOOBIG(t, data->size)) {
		bigdata = TRUE;
		datasize = sizeof(pgno_t);
	} else {
		bigdata = FALSE;
		datasize = data->size;
	}

	if (TOOBIG(t, key->size)) {
		bigkey = TRUE;
		keysize = sizeof(pgno_t);
	} else {
		bigkey = FALSE;
		keysize = key->size;
	}

	nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
	nbytes = LONGALIGN(nbytes) + sizeof(index_t);

	/* if there's not enough room here, split the page */
	if ((h->h_upper - h->h_lower) < nbytes) {
		if (_bt_split(t) == RET_ERROR)
			return (RET_ERROR);

		/* okay, try again (empty the stack first, though) */
		while (_bt_pop((BTREE) t) != P_NONE)
			continue;

		return (bt_put((BTREE) t, key, data, flag));
	}

	/* put together a leaf page datum from the key/data pair */
	index = item->bti_index;
	nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));

	if ((d = (DATUM *) malloc((unsigned) nbytes)) == (DATUM *) NULL)
		return (RET_ERROR);

	d->d_ksize = keysize;
	d->d_dsize = datasize;
	d->d_flags = 0;

	if (bigkey) {
		if (_bt_indirect(t, key, &pgno) == RET_ERROR)
			return (RET_ERROR);
		(void) bcopy((char *) &pgno, &(d->d_bytes[0]), sizeof(pgno));
		d->d_flags |= D_BIGKEY;
		if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
			return (RET_ERROR);
	} else {
		if (d->d_ksize > 0) {
			(void) bcopy((char *) key->data,
				      (char *) &(d->d_bytes[0]),
				      (int) d->d_ksize);
		}
	}

	if (bigdata) {
		if (_bt_indirect(t, data, &pgno) == RET_ERROR)
			return (RET_ERROR);
		(void) bcopy((char *) &pgno,
			     &(d->d_bytes[keysize]),
			     sizeof(pgno));
		d->d_flags |= D_BIGDATA;
		if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
			return (RET_ERROR);
	} else {
		if (d->d_dsize > 0) {
			(void) bcopy((char *) data->data,
				      (char *) &(d->d_bytes[keysize]),
				      (int) d->d_dsize);
		}
	}

	/* do the insertion */
	status = _bt_insertat(t, (char *) d, index);

	(void) free((char *) d);

	return (status);
}

/*
 *  _BT_INSERTI -- Insert IDATUM on current page in the btree.
 *
 *	This routine handles insertions to internal pages after splits
 *	lower in the tree.  On entry, t->bt_curpage is the page to get
 *	the new IDATUM.  We are also given pgno, the page number of the
 *	IDATUM that is immediately left of the new IDATUM's position.
 *	This guarantees that the IDATUM for the right half of the page
 *	after a split goes next to the IDATUM for its left half.
 *
 *	Parameters:
 *		t -- tree in which to do insertion.
 *		id -- new IDATUM to insert
 *		pgno -- page number of IDATUM left of id's position
 *
 *	Returns:
 *		RET_SUCCESS, RET_ERROR.
 */

int
_bt_inserti(t, id, pgno)
	BTREE_P t;
	IDATUM *id;
	pgno_t pgno;
{
	BTHEADER *h = t->bt_curpage;
	index_t next, i;
	IDATUM *idx;
	char *key;
	pgno_t chain;
	int free_key;
	int ignore;

	if (id->i_flags & D_BIGKEY) {
		free_key = TRUE;
		bcopy(&(id->i_bytes[0]), (char *) &chain, sizeof(chain));
		if (_bt_getbig(t, chain, &key, &ignore) == RET_ERROR)
			return (RET_ERROR);
	} else {
		free_key = FALSE;
		key = &(id->i_bytes[0]);
	}
	i = _bt_binsrch(t, key);

	next = NEXTINDEX(h);
	while (i < next && _bt_cmp(t, key, i) >= 0)
		i++;

	if (free_key)
		(void) free(key);

	/* okay, now we're close; find adjacent IDATUM */
	for (;;) {
		idx = (IDATUM *) GETDATUM(h,i);
		if (idx->i_pgno == pgno) {
			i++;
			break;
		}
		--i;
	}

	/* correctly positioned, do the insertion */
	return (_bt_insertat(t, (char *) id, i));
}

/*
 *  _BT_INSERTAT -- Insert a datum at a given location on the current page.
 *
 *	This routine does insertions on both leaf and internal pages.
 *
 *	Parameters:
 *		t -- tree in which to do insertion.
 *		p -- DATUM or IDATUM to insert.
 *		index -- index in line pointer array to put this item.
 *
 *	Returns:
 *		RET_SUCCESS, RET_ERROR.
 *
 *	Side Effects:
 *		Will rearrange line pointers to make space for the new
 *		entry.  This means that any scans currently active are
 *		invalid after this.
 *
 *	Warnings:
 *		There must be sufficient room for the new item on the page.
 */

int
_bt_insertat(t, p, index)
	BTREE_P t;
	char *p;
	index_t index;
{
	IDATUM *id = (IDATUM *) p;
	DATUM *d = (DATUM *) p;
	BTHEADER *h;
	CURSOR *c;
	index_t nxtindex;
	char *src, *dest;
	int nbytes;

	/* insertion may confuse an active scan.  fix it. */
	c = &(t->bt_cursor);
	if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno)
		if (_bt_fixscan(t, index, d, INSERT) == RET_ERROR)
			return (RET_ERROR);

	h = t->bt_curpage;
	nxtindex = (index_t) NEXTINDEX(h);

	/*
	 *  If we're inserting at the middle of the line pointer array,
	 *  copy pointers that will follow the new one up on the page.
	 */

	if (index < nxtindex) {
		src = (char *) &(h->h_linp[index]);
		dest = (char *) &(h->h_linp[index + 1]);
		nbytes = (h->h_lower - (src - ((char *) h)))
			 + sizeof(h->h_linp[0]);
		(void) bcopy(src, dest, nbytes);
	}

	/* compute size and copy data to page */
	if (h->h_flags & F_LEAF) {
		nbytes = d->d_ksize + d->d_dsize
			 + (sizeof(DATUM) - sizeof(char));
	} else {
		nbytes = id->i_size + (sizeof(IDATUM) - sizeof(char));
	}
	dest = (((char *) h) + h->h_upper) - LONGALIGN(nbytes);
	(void) bcopy((char *) p, dest, nbytes);

	/* update statistics */
	dest -= (int) h;
	h->h_linp[index] = (index_t) dest;
	h->h_upper = (index_t) dest;
	h->h_lower += sizeof(index_t);

	/* we're done */
	h->h_flags |= F_DIRTY;

	return (RET_SUCCESS);
}
Commit	Line	Data
15637ed4 RG	1	/*-
	2	* Copyright (c) 1990 The Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* This code is derived from software contributed to Berkeley by
	6	* Mike Olson.
	7	*
	8	* Redistribution and use in source and binary forms, with or without
	9	* modification, are permitted provided that the following conditions
	10	* are met:
	11	* 1. Redistributions of source code must retain the above copyright
	12	* notice, this list of conditions and the following disclaimer.
	13	* 2. Redistributions in binary form must reproduce the above copyright
	14	* notice, this list of conditions and the following disclaimer in the
	15	* documentation and/or other materials provided with the distribution.
	16	* 3. All advertising materials mentioning features or use of this software
	17	* must display the following acknowledgement:
	18	* This product includes software developed by the University of
	19	* California, Berkeley and its contributors.
	20	* 4. Neither the name of the University nor the names of its contributors
	21	* may be used to endorse or promote products derived from this software
	22	* without specific prior written permission.
	23	*
	24	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	25	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	26	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	27	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	28	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	29	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	30	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	31	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	32	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	33	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	34	* SUCH DAMAGE.
	35	*/
	36
	37	#if defined(LIBC_SCCS) && !defined(lint)
	38	static char sccsid[] = "@(#)insert.c 5.3 (Berkeley) 2/22/91";
	39	#endif /* LIBC_SCCS and not lint */
	40
	41	#include <sys/types.h>
	42	#include <db.h>
	43	#include <stdlib.h>
	44	#include <string.h>
	45	#include "btree.h"
	46
	47	/*
	48	* _BT_INSERT -- Insert a new user datum in the btree.
	49	*
	50	* This routine is called by bt_put, the public interface, once the
	51	* location for the new item is known. We do the work here, and
	52	* handle splits if necessary.
	53	*
	54	* Parameters:
	55	* t -- btree in which to do the insertion.
	56	* item -- BTITEM describing location of new datum
	57	* key -- key to insert
	58	* data -- data associated with key
	59	* flag -- magic cookie passed recursively to bt_put if we
	60	* have to do a split
	61	*
	62	* Returns:
	63	* RET_SUCCESS, RET_ERROR.
	64	*/
65
66	int
67	_bt_insert(t, item, key, data, flag)
68	BTREE_P t;
69	BTITEM *item;
70	DBT *key;
71	DBT *data;
72	int flag;
73	{
74	index_t index;
75	BTHEADER *h;
76	DATUM *d;
77	int nbytes;
78	int status;
79	pgno_t pgno;
80	int keysize, datasize;
81	int bigkey, bigdata;
82
83	if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
84	return (RET_ERROR);
85	h = t->bt_curpage;
86
87	if (TOOBIG(t, data->size)) {
88	bigdata = TRUE;
89	datasize = sizeof(pgno_t);
90	} else {
91	bigdata = FALSE;
92	datasize = data->size;
93	}
94
95	if (TOOBIG(t, key->size)) {
96	bigkey = TRUE;
97	keysize = sizeof(pgno_t);
98	} else {
99	bigkey = FALSE;
100	keysize = key->size;
101	}
102
103	nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
104	nbytes = LONGALIGN(nbytes) + sizeof(index_t);
105
106	/* if there's not enough room here, split the page */
107	if ((h->h_upper - h->h_lower) < nbytes) {
108	if (_bt_split(t) == RET_ERROR)
109	return (RET_ERROR);
110
111	/* okay, try again (empty the stack first, though) */
112	while (_bt_pop((BTREE) t) != P_NONE)
113	continue;
114
115	return (bt_put((BTREE) t, key, data, flag));
116	}
117
118	/* put together a leaf page datum from the key/data pair */
119	index = item->bti_index;
120	nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
121
122	if ((d = (DATUM ) malloc((unsigned) nbytes)) == (DATUM ) NULL)
123	return (RET_ERROR);
124
125	d->d_ksize = keysize;
126	d->d_dsize = datasize;
127	d->d_flags = 0;
128
129	if (bigkey) {
130	if (_bt_indirect(t, key, &pgno) == RET_ERROR)
131	return (RET_ERROR);
132	(void) bcopy((char *) &pgno, &(d->d_bytes[0]), sizeof(pgno));
133	d->d_flags \|= D_BIGKEY;
134	if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
135	return (RET_ERROR);
136	} else {
137	if (d->d_ksize > 0) {
138	(void) bcopy((char *) key->data,
139	(char *) &(d->d_bytes[0]),
140	(int) d->d_ksize);
141	}
142	}
143
144	if (bigdata) {
145	if (_bt_indirect(t, data, &pgno) == RET_ERROR)
146	return (RET_ERROR);
147	(void) bcopy((char *) &pgno,
148	&(d->d_bytes[keysize]),
149	sizeof(pgno));
150	d->d_flags \|= D_BIGDATA;
151	if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
152	return (RET_ERROR);
153	} else {
154	if (d->d_dsize > 0) {
155	(void) bcopy((char *) data->data,
156	(char *) &(d->d_bytes[keysize]),
157	(int) d->d_dsize);
158	}
159	}
160
161	/* do the insertion */
162	status = _bt_insertat(t, (char *) d, index);
163
164	(void) free((char *) d);
165
166	return (status);
167	}
168
169	/*
170	* _BT_INSERTI -- Insert IDATUM on current page in the btree.
171	*
172	* This routine handles insertions to internal pages after splits
173	* lower in the tree. On entry, t->bt_curpage is the page to get
174	* the new IDATUM. We are also given pgno, the page number of the
175	* IDATUM that is immediately left of the new IDATUM's position.
176	* This guarantees that the IDATUM for the right half of the page
177	* after a split goes next to the IDATUM for its left half.
178	*
179	* Parameters:
180	* t -- tree in which to do insertion.
181	* id -- new IDATUM to insert
182	* pgno -- page number of IDATUM left of id's position
183	*
184	* Returns:
185	* RET_SUCCESS, RET_ERROR.
186	*/
187
188	int
189	_bt_inserti(t, id, pgno)
190	BTREE_P t;
191	IDATUM *id;
192	pgno_t pgno;
193	{
194	BTHEADER *h = t->bt_curpage;
195	index_t next, i;
196	IDATUM *idx;
197	char *key;
198	pgno_t chain;
199	int free_key;
200	int ignore;
201
202	if (id->i_flags & D_BIGKEY) {
203	free_key = TRUE;
204	bcopy(&(id->i_bytes[0]), (char *) &chain, sizeof(chain));
205	if (_bt_getbig(t, chain, &key, &ignore) == RET_ERROR)
206	return (RET_ERROR);
207	} else {
208	free_key = FALSE;
209	key = &(id->i_bytes[0]);
210	}
211	i = _bt_binsrch(t, key);
212
213	next = NEXTINDEX(h);
214	while (i < next && _bt_cmp(t, key, i) >= 0)
215	i++;
216
217	if (free_key)
218	(void) free(key);
219
220	/* okay, now we're close; find adjacent IDATUM */
221	for (;;) {
222	idx = (IDATUM *) GETDATUM(h,i);
223	if (idx->i_pgno == pgno) {
224	i++;
225	break;
226	}
227	--i;
228	}
229
230	/* correctly positioned, do the insertion */
231	return (_bt_insertat(t, (char *) id, i));
232	}
233
234	/*
235	* _BT_INSERTAT -- Insert a datum at a given location on the current page.
236	*
237	* This routine does insertions on both leaf and internal pages.
238	*
239	* Parameters:
240	* t -- tree in which to do insertion.
241	* p -- DATUM or IDATUM to insert.
242	* index -- index in line pointer array to put this item.
243	*
244	* Returns:
245	* RET_SUCCESS, RET_ERROR.
246	*
247	* Side Effects:
248	* Will rearrange line pointers to make space for the new
249	* entry. This means that any scans currently active are
250	* invalid after this.
251	*
252	* Warnings:
253	* There must be sufficient room for the new item on the page.
254	*/
255
256	int
257	_bt_insertat(t, p, index)
258	BTREE_P t;
259	char *p;
260	index_t index;
261	{
262	IDATUM id = (IDATUM ) p;
263	DATUM d = (DATUM ) p;
264	BTHEADER *h;
265	CURSOR *c;
266	index_t nxtindex;
267	char src, dest;
268	int nbytes;
269
270	/* insertion may confuse an active scan. fix it. */
271	c = &(t->bt_cursor);
272	if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno)
273	if (_bt_fixscan(t, index, d, INSERT) == RET_ERROR)
274	return (RET_ERROR);
275
276	h = t->bt_curpage;
277	nxtindex = (index_t) NEXTINDEX(h);
278
279	/*
280	* If we're inserting at the middle of the line pointer array,
281	* copy pointers that will follow the new one up on the page.
282	*/
283
284	if (index < nxtindex) {
285	src = (char *) &(h->h_linp[index]);
286	dest = (char *) &(h->h_linp[index + 1]);
287	nbytes = (h->h_lower - (src - ((char *) h)))
288	+ sizeof(h->h_linp[0]);
289	(void) bcopy(src, dest, nbytes);
290	}
291
292	/* compute size and copy data to page */
293	if (h->h_flags & F_LEAF) {
294	nbytes = d->d_ksize + d->d_dsize
295	+ (sizeof(DATUM) - sizeof(char));
296	} else {
297	nbytes = id->i_size + (sizeof(IDATUM) - sizeof(char));
298	}
299	dest = (((char *) h) + h->h_upper) - LONGALIGN(nbytes);
300	(void) bcopy((char *) p, dest, nbytes);
301
302	/* update statistics */
303	dest -= (int) h;
304	h->h_linp[index] = (index_t) dest;
305	h->h_upper = (index_t) dest;
306	h->h_lower += sizeof(index_t);
307
308	/* we're done */
309	h->h_flags \|= F_DIRTY;
310
311	return (RET_SUCCESS);
312	}