]> git.saurik.com Git - apple/libc.git/blame - db.subproj/btree.subproj/bt_put.c
Libc-166.tar.gz
[apple/libc.git] / db.subproj / btree.subproj / bt_put.c
CommitLineData
e9ce8d39
A
1/*
2 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * The contents of this file constitute Original Code as defined in and
7 * are subject to the Apple Public Source License Version 1.1 (the
8 * "License"). You may not use this file except in compliance with the
9 * License. Please obtain a copy of the License at
10 * http://www.apple.com/publicsource and read it before using this file.
11 *
12 * This Original Code and all software distributed under the License are
13 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17 * License for the specific language governing rights and limitations
18 * under the License.
19 *
20 * @APPLE_LICENSE_HEADER_END@
21 */
22/*
23 * Copyright (c) 1990, 1993
24 * The Regents of the University of California. All rights reserved.
25 *
26 * This code is derived from software contributed to Berkeley by
27 * Mike Olson.
28 *
29 * Redistribution and use in source and binary forms, with or without
30 * modification, are permitted provided that the following conditions
31 * are met:
32 * 1. Redistributions of source code must retain the above copyright
33 * notice, this list of conditions and the following disclaimer.
34 * 2. Redistributions in binary form must reproduce the above copyright
35 * notice, this list of conditions and the following disclaimer in the
36 * documentation and/or other materials provided with the distribution.
37 * 3. All advertising materials mentioning features or use of this software
38 * must display the following acknowledgement:
39 * This product includes software developed by the University of
40 * California, Berkeley and its contributors.
41 * 4. Neither the name of the University nor the names of its contributors
42 * may be used to endorse or promote products derived from this software
43 * without specific prior written permission.
44 *
45 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
46 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
47 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
48 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
49 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
50 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
51 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
52 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
53 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
54 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
55 * SUCH DAMAGE.
56 */
57
58
59#include <sys/types.h>
60
61#include <errno.h>
62#include <stdio.h>
63#include <stdlib.h>
64#include <string.h>
65
66#include <db.h>
67#include "btree.h"
68
69static EPG *bt_fast __P((BTREE *, const DBT *, const DBT *, int *));
70
71/*
72 * __BT_PUT -- Add a btree item to the tree.
73 *
74 * Parameters:
75 * dbp: pointer to access method
76 * key: key
77 * data: data
78 * flag: R_NOOVERWRITE
79 *
80 * Returns:
81 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the
82 * tree and R_NOOVERWRITE specified.
83 */
84int
85__bt_put(dbp, key, data, flags)
86 const DB *dbp;
87 DBT *key;
88 const DBT *data;
89 u_int flags;
90{
91 BTREE *t;
92 DBT tkey, tdata;
93 EPG *e;
94 PAGE *h;
95 indx_t index, nxtindex;
96 pgno_t pg;
97 size_t nbytes;
98 int dflags, exact, status;
99 char *dest, db[NOVFLSIZE], kb[NOVFLSIZE];
100
101 t = dbp->internal;
102
103 /* Toss any page pinned across calls. */
104 if (t->bt_pinned != NULL) {
105 mpool_put(t->bt_mp, t->bt_pinned, 0);
106 t->bt_pinned = NULL;
107 }
108
109 switch (flags) {
110 case R_CURSOR:
111 if (!ISSET(t, B_SEQINIT))
112 goto einval;
113 if (ISSET(t, B_DELCRSR))
114 goto einval;
115 break;
116 case 0:
117 case R_NOOVERWRITE:
118 break;
119 default:
120einval: errno = EINVAL;
121 return (RET_ERROR);
122 }
123
124 if (ISSET(t, B_RDONLY)) {
125 errno = EPERM;
126 return (RET_ERROR);
127 }
128
129 /*
130 * If the key/data won't fit on a page, store it on indirect pages.
131 * Only store the key on the overflow page if it's too big after the
132 * data is on an overflow page.
133 *
134 * XXX
135 * If the insert fails later on, these pages aren't recovered.
136 */
137 dflags = 0;
138 if (key->size + data->size > t->bt_ovflsize) {
139 if (key->size > t->bt_ovflsize) {
140storekey: if (__ovfl_put(t, key, &pg) == RET_ERROR)
141 return (RET_ERROR);
142 tkey.data = kb;
143 tkey.size = NOVFLSIZE;
144 memmove(kb, &pg, sizeof(pgno_t));
145 memmove(kb + sizeof(pgno_t),
146 &key->size, sizeof(size_t));
147 dflags |= P_BIGKEY;
148 key = &tkey;
149 }
150 if (key->size + data->size > t->bt_ovflsize) {
151 if (__ovfl_put(t, data, &pg) == RET_ERROR)
152 return (RET_ERROR);
153 tdata.data = db;
154 tdata.size = NOVFLSIZE;
155 memmove(db, &pg, sizeof(pgno_t));
156 memmove(db + sizeof(pgno_t),
157 &data->size, sizeof(size_t));
158 dflags |= P_BIGDATA;
159 data = &tdata;
160 }
161 if (key->size + data->size > t->bt_ovflsize)
162 goto storekey;
163 }
164
165 /* Replace the cursor. */
166 if (flags == R_CURSOR) {
167 if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL)
168 return (RET_ERROR);
169 index = t->bt_bcursor.index;
170 goto delete;
171 }
172
173 /*
174 * Find the key to delete, or, the location at which to insert. Bt_fast
175 * and __bt_search pin the returned page.
176 */
177 if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL)
178 if ((e = __bt_search(t, key, &exact)) == NULL)
179 return (RET_ERROR);
180 h = e->page;
181 index = e->index;
182
183 /*
184 * Add the specified key/data pair to the tree. If an identical key
185 * is already in the tree, and R_NOOVERWRITE is set, an error is
186 * returned. If R_NOOVERWRITE is not set, the key is either added (if
187 * duplicates are permitted) or an error is returned.
188 *
189 * Pages are split as required.
190 */
191 switch (flags) {
192 case R_NOOVERWRITE:
193 if (!exact)
194 break;
195 /*
196 * One special case is if the cursor references the record and
197 * it's been flagged for deletion. Then, we delete the record,
198 * leaving the cursor there -- this means that the inserted
199 * record will not be seen in a cursor scan.
200 */
201 if (ISSET(t, B_DELCRSR) && t->bt_bcursor.pgno == h->pgno &&
202 t->bt_bcursor.index == index) {
203 CLR(t, B_DELCRSR);
204 goto delete;
205 }
206 mpool_put(t->bt_mp, h, 0);
207 return (RET_SPECIAL);
208 default:
209 if (!exact || !ISSET(t, B_NODUPS))
210 break;
211delete: if (__bt_dleaf(t, h, index) == RET_ERROR) {
212 mpool_put(t->bt_mp, h, 0);
213 return (RET_ERROR);
214 }
215 break;
216 }
217
218 /*
219 * If not enough room, or the user has put a ceiling on the number of
220 * keys permitted in the page, split the page. The split code will
221 * insert the key and data and unpin the current page. If inserting
222 * into the offset array, shift the pointers up.
223 */
224 nbytes = NBLEAFDBT(key->size, data->size);
225 if (h->upper - h->lower < nbytes + sizeof(indx_t)) {
226 if ((status = __bt_split(t, h, key,
227 data, dflags, nbytes, index)) != RET_SUCCESS)
228 return (status);
229 goto success;
230 }
231
232 if (index < (nxtindex = NEXTINDEX(h)))
233 memmove(h->linp + index + 1, h->linp + index,
234 (nxtindex - index) * sizeof(indx_t));
235 h->lower += sizeof(indx_t);
236
237 h->linp[index] = h->upper -= nbytes;
238 dest = (char *)h + h->upper;
239 WR_BLEAF(dest, key, data, dflags);
240
241 if (t->bt_order == NOT)
242 if (h->nextpg == P_INVALID) {
243 if (index == NEXTINDEX(h) - 1) {
244 t->bt_order = FORWARD;
245 t->bt_last.index = index;
246 t->bt_last.pgno = h->pgno;
247 }
248 } else if (h->prevpg == P_INVALID) {
249 if (index == 0) {
250 t->bt_order = BACK;
251 t->bt_last.index = 0;
252 t->bt_last.pgno = h->pgno;
253 }
254 }
255
256 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
257
258success:
259 if (flags == R_SETCURSOR) {
260 t->bt_bcursor.pgno = e->page->pgno;
261 t->bt_bcursor.index = e->index;
262 }
263 SET(t, B_MODIFIED);
264 return (RET_SUCCESS);
265}
266
267#ifdef STATISTICS
268u_long bt_cache_hit, bt_cache_miss;
269#endif
270
271/*
272 * BT_FAST -- Do a quick check for sorted data.
273 *
274 * Parameters:
275 * t: tree
276 * key: key to insert
277 *
278 * Returns:
279 * EPG for new record or NULL if not found.
280 */
281static EPG *
282bt_fast(t, key, data, exactp)
283 BTREE *t;
284 const DBT *key, *data;
285 int *exactp;
286{
287 PAGE *h;
288 size_t nbytes;
289 int cmp;
290
291 if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) {
292 t->bt_order = NOT;
293 return (NULL);
294 }
295 t->bt_cur.page = h;
296 t->bt_cur.index = t->bt_last.index;
297
298 /*
299 * If won't fit in this page or have too many keys in this page, have
300 * to search to get split stack.
301 */
302 nbytes = NBLEAFDBT(key->size, data->size);
303 if (h->upper - h->lower < nbytes + sizeof(indx_t))
304 goto miss;
305
306 if (t->bt_order == FORWARD) {
307 if (t->bt_cur.page->nextpg != P_INVALID)
308 goto miss;
309 if (t->bt_cur.index != NEXTINDEX(h) - 1)
310 goto miss;
311 if ((cmp = __bt_cmp(t, key, &t->bt_cur)) < 0)
312 goto miss;
313 t->bt_last.index = cmp ? ++t->bt_cur.index : t->bt_cur.index;
314 } else {
315 if (t->bt_cur.page->prevpg != P_INVALID)
316 goto miss;
317 if (t->bt_cur.index != 0)
318 goto miss;
319 if ((cmp = __bt_cmp(t, key, &t->bt_cur)) > 0)
320 goto miss;
321 t->bt_last.index = 0;
322 }
323 *exactp = cmp == 0;
324#ifdef STATISTICS
325 ++bt_cache_hit;
326#endif
327 return (&t->bt_cur);
328
329miss:
330#ifdef STATISTICS
331 ++bt_cache_miss;
332#endif
333 t->bt_order = NOT;
334 mpool_put(t->bt_mp, h, 0);
335 return (NULL);
336}