[apple/libc.git] / db / btree / bt_get.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/types.h>

#include <errno.h>
#include <stddef.h>
#include <stdio.h>

#include <db.h>
#include "btree.h"

/*
 * __BT_GET -- Get a record from the btree.
 *
 * Parameters:
 *	dbp:	pointer to access method
 *	key:	key to find
 *	data:	data to return
 *	flag:	currently unused
 *
 * Returns:
 *	RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
 */
int
__bt_get(dbp, key, data, flags)
	const DB *dbp;
	const DBT *key;
	DBT *data;
	u_int flags;
{
	BTREE *t;
	EPG *e;
	int exact, status;

	t = dbp->internal;

	/* Toss any page pinned across calls. */
	if (t->bt_pinned != NULL) {
		mpool_put(t->bt_mp, t->bt_pinned, 0);
		t->bt_pinned = NULL;
	}

	/* Get currently doesn't take any flags. */
	if (flags) {
		errno = EINVAL;
		return (RET_ERROR);
	}

	if ((e = __bt_search(t, key, &exact)) == NULL)
		return (RET_ERROR);
	if (!exact) {
		mpool_put(t->bt_mp, e->page, 0);
		return (RET_SPECIAL);
	}

	/*
	 * A special case is if we found the record but it's flagged for
	 * deletion.  In this case, we want to find another record with the
	 * same key, if it exists.  Rather than look around the tree we call
	 * __bt_first and have it redo the search, as __bt_first will not
	 * return keys marked for deletion.  Slow, but should never happen.
	 */
	if (ISSET(t, B_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno &&
	    e->index == t->bt_bcursor.index) {
		mpool_put(t->bt_mp, e->page, 0);
		if ((e = __bt_first(t, key, &exact)) == NULL)
			return (RET_ERROR);
		if (!exact)
			return (RET_SPECIAL);
	}

	status = __bt_ret(t, e, NULL, data);
	/*
	 * If the user is doing concurrent access, we copied the
	 * key/data, toss the page.
	 */
	if (ISSET(t, B_DB_LOCK))
		mpool_put(t->bt_mp, e->page, 0);
	else
		t->bt_pinned = e->page;
	return (status);
}

/*
 * __BT_FIRST -- Find the first entry.
 *
 * Parameters:
 *	t:	the tree
 *	key:	the key
 *
 * Returns:
 *	The first entry in the tree greater than or equal to key.
 */
EPG *
__bt_first(t, key, exactp)
	BTREE *t;
	const DBT *key;
	int *exactp;
{
	register PAGE *h;
	register EPG *e;
	EPG save;
	pgno_t cpgno, pg;
	indx_t cindex;
	int found;

	/*
	 * Find any matching record; __bt_search pins the page.  Only exact
	 * matches are tricky, otherwise just return the location of the key
	 * if it were to be inserted into the tree.
	 */
	if ((e = __bt_search(t, key, exactp)) == NULL)
		return (NULL);
	if (!*exactp)
		return (e);

	if (ISSET(t, B_DELCRSR)) {
		cpgno = t->bt_bcursor.pgno;
		cindex = t->bt_bcursor.index;
	} else {
		cpgno = P_INVALID;
		cindex = 0;		/* GCC thinks it's uninitialized. */
	}

	/*
	 * Walk backwards, skipping empty pages, as long as the entry matches
	 * and there are keys left in the tree.  Save a copy of each match in
	 * case we go too far.  A special case is that we don't return a match
	 * on records that the cursor references that have already been flagged
	 * for deletion.
	 */
	save = *e;
	h = e->page;
	found = 0;
	do {
		if (cpgno != h->pgno || cindex != e->index) {
			if (save.page->pgno != e->page->pgno) {
				mpool_put(t->bt_mp, save.page, 0);
				save = *e;
			} else
				save.index = e->index;
			found = 1;
		}
		/*
		 * Make a special effort not to unpin the page the last (or
		 * original) match was on, but also make sure it's unpinned
		 * if an error occurs.
		 */
		while (e->index == 0) {
			if (h->prevpg == P_INVALID)
				goto done1;
			if (h->pgno != save.page->pgno)
				mpool_put(t->bt_mp, h, 0);
			if ((h = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) {
				if (h->pgno == save.page->pgno)
					mpool_put(t->bt_mp, save.page, 0);
				return (NULL);
			}
			e->page = h;
			e->index = NEXTINDEX(h);
		}
		--e->index;
	} while (__bt_cmp(t, key, e) == 0);

	/*
	 * Reach here with the last page that was looked at pinned, which may
	 * or may not be the same as the last (or original) match page.  If
	 * it's not useful, release it.
	 */
done1:	if (h->pgno != save.page->pgno)
		mpool_put(t->bt_mp, h, 0);

	/*
	 * If still haven't found a record, the only possibility left is the
	 * next one.  Move forward one slot, skipping empty pages and check.
	 */
	if (!found) {
		h = save.page;
		if (++save.index == NEXTINDEX(h)) {
			do {
				pg = h->nextpg;
				mpool_put(t->bt_mp, h, 0);
				if (pg == P_INVALID) {
					*exactp = 0;
					return (e);
				}
				if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
					return (NULL);
			} while ((save.index = NEXTINDEX(h)) == 0);
			save.page = h;
		}
		if (__bt_cmp(t, key, &save) != 0) {
			*exactp = 0;
			return (e);
		}
	}
	*e = save;
	*exactp = 1;
	return (e);
}
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/types.h>
	63
	64	#include <errno.h>
	65	#include <stddef.h>
	66	#include <stdio.h>
	67
	68	#include <db.h>
	69	#include "btree.h"
	70
	71	/*
	72	* __BT_GET -- Get a record from the btree.
	73	*
	74	* Parameters:
	75	* dbp: pointer to access method
	76	* key: key to find
	77	* data: data to return
	78	* flag: currently unused
	79	*
	80	* Returns:
	81	* RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
	82	*/
	83	int
	84	__bt_get(dbp, key, data, flags)
	85	const DB *dbp;
86	const DBT *key;
87	DBT *data;
88	u_int flags;
89	{
90	BTREE *t;
91	EPG *e;
92	int exact, status;
93
94	t = dbp->internal;
95
96	/* Toss any page pinned across calls. */
97	if (t->bt_pinned != NULL) {
98	mpool_put(t->bt_mp, t->bt_pinned, 0);
99	t->bt_pinned = NULL;
100	}
101
102	/* Get currently doesn't take any flags. */
103	if (flags) {
104	errno = EINVAL;
105	return (RET_ERROR);
106	}
107
108	if ((e = __bt_search(t, key, &exact)) == NULL)
109	return (RET_ERROR);
110	if (!exact) {
111	mpool_put(t->bt_mp, e->page, 0);
112	return (RET_SPECIAL);
113	}
114
115	/*
116	* A special case is if we found the record but it's flagged for
117	* deletion. In this case, we want to find another record with the
118	* same key, if it exists. Rather than look around the tree we call
119	* __bt_first and have it redo the search, as __bt_first will not
120	* return keys marked for deletion. Slow, but should never happen.
121	*/
122	if (ISSET(t, B_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno &&
123	e->index == t->bt_bcursor.index) {
124	mpool_put(t->bt_mp, e->page, 0);
125	if ((e = __bt_first(t, key, &exact)) == NULL)
126	return (RET_ERROR);
127	if (!exact)
128	return (RET_SPECIAL);
129	}
130
131	status = __bt_ret(t, e, NULL, data);
132	/*
133	* If the user is doing concurrent access, we copied the
134	* key/data, toss the page.
135	*/
136	if (ISSET(t, B_DB_LOCK))
137	mpool_put(t->bt_mp, e->page, 0);
138	else
139	t->bt_pinned = e->page;
140	return (status);
141	}
142
143	/*
144	* __BT_FIRST -- Find the first entry.
145	*
146	* Parameters:
147	* t: the tree
148	* key: the key
149	*
150	* Returns:
151	* The first entry in the tree greater than or equal to key.
152	*/
153	EPG *
154	__bt_first(t, key, exactp)
155	BTREE *t;
156	const DBT *key;
157	int *exactp;
158	{
159	register PAGE *h;
160	register EPG *e;
161	EPG save;
162	pgno_t cpgno, pg;
163	indx_t cindex;
164	int found;
165
166	/*
167	* Find any matching record; __bt_search pins the page. Only exact
168	* matches are tricky, otherwise just return the location of the key
169	* if it were to be inserted into the tree.
170	*/
171	if ((e = __bt_search(t, key, exactp)) == NULL)
172	return (NULL);
173	if (!*exactp)
174	return (e);
175
176	if (ISSET(t, B_DELCRSR)) {
177	cpgno = t->bt_bcursor.pgno;
178	cindex = t->bt_bcursor.index;
179	} else {
180	cpgno = P_INVALID;
181	cindex = 0; /* GCC thinks it's uninitialized. */
182	}
183
184	/*
185	* Walk backwards, skipping empty pages, as long as the entry matches
186	* and there are keys left in the tree. Save a copy of each match in
187	* case we go too far. A special case is that we don't return a match
188	* on records that the cursor references that have already been flagged
189	* for deletion.
190	*/
191	save = *e;
192	h = e->page;
193	found = 0;
194	do {
195	if (cpgno != h->pgno \|\| cindex != e->index) {
196	if (save.page->pgno != e->page->pgno) {
197	mpool_put(t->bt_mp, save.page, 0);
198	save = *e;
199	} else
200	save.index = e->index;
201	found = 1;
202	}
203	/*
204	* Make a special effort not to unpin the page the last (or
205	* original) match was on, but also make sure it's unpinned
206	* if an error occurs.
207	*/
208	while (e->index == 0) {
209	if (h->prevpg == P_INVALID)
210	goto done1;
211	if (h->pgno != save.page->pgno)
212	mpool_put(t->bt_mp, h, 0);
213	if ((h = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) {
214	if (h->pgno == save.page->pgno)
215	mpool_put(t->bt_mp, save.page, 0);
216	return (NULL);
217	}
218	e->page = h;
219	e->index = NEXTINDEX(h);
220	}
221	--e->index;
222	} while (__bt_cmp(t, key, e) == 0);
223
224	/*
225	* Reach here with the last page that was looked at pinned, which may
226	* or may not be the same as the last (or original) match page. If
227	* it's not useful, release it.
228	*/
229	done1: if (h->pgno != save.page->pgno)
230	mpool_put(t->bt_mp, h, 0);
231
232	/*
233	* If still haven't found a record, the only possibility left is the
234	* next one. Move forward one slot, skipping empty pages and check.
235	*/
236	if (!found) {
237	h = save.page;
238	if (++save.index == NEXTINDEX(h)) {
239	do {
240	pg = h->nextpg;
241	mpool_put(t->bt_mp, h, 0);
242	if (pg == P_INVALID) {
243	*exactp = 0;
244	return (e);
245	}
246	if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
247	return (NULL);
248	} while ((save.index = NEXTINDEX(h)) == 0);
249	save.page = h;
250	}
251	if (__bt_cmp(t, key, &save) != 0) {
252	*exactp = 0;
253	return (e);
254	}
255	}
256	*e = save;
257	*exactp = 1;
258	return (e);
259	}