2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid
[] = "@(#)bt_put.c 8.8 (Berkeley) 7/26/94";
39 #endif /* LIBC_SCCS and not lint */
41 #include <sys/types.h>
51 static EPG
*bt_fast
__P((BTREE
*, const DBT
*, const DBT
*, int *));
54 * __BT_PUT -- Add a btree item to the tree.
57 * dbp: pointer to access method
63 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the
64 * tree and R_NOOVERWRITE specified.
67 __bt_put(dbp
, key
, data
, flags
)
77 indx_t index
, nxtindex
;
80 int dflags
, exact
, status
;
81 char *dest
, db
[NOVFLSIZE
], kb
[NOVFLSIZE
];
85 /* Toss any page pinned across calls. */
86 if (t
->bt_pinned
!= NULL
) {
87 mpool_put(t
->bt_mp
, t
->bt_pinned
, 0);
91 /* Check for change to a read-only tree. */
92 if (F_ISSET(t
, B_RDONLY
)) {
103 * If flags is R_CURSOR, put the cursor. Must already
104 * have started a scan and not have already deleted it.
106 if (F_ISSET(&t
->bt_cursor
, CURS_INIT
) &&
107 !F_ISSET(&t
->bt_cursor
,
108 CURS_ACQUIRE
| CURS_AFTER
| CURS_BEFORE
))
117 * If the key/data pair won't fit on a page, store it on overflow
118 * pages. Only put the key on the overflow page if the pair are
119 * still too big after moving the data to an overflow page.
122 * If the insert fails later on, the overflow pages aren't recovered.
125 if (key
->size
+ data
->size
> t
->bt_ovflsize
) {
126 if (key
->size
> t
->bt_ovflsize
) {
127 storekey
: if (__ovfl_put(t
, key
, &pg
) == RET_ERROR
)
130 tkey
.size
= NOVFLSIZE
;
131 memmove(kb
, &pg
, sizeof(pgno_t
));
132 memmove(kb
+ sizeof(pgno_t
),
133 &key
->size
, sizeof(u_int32_t
));
137 if (key
->size
+ data
->size
> t
->bt_ovflsize
) {
138 if (__ovfl_put(t
, data
, &pg
) == RET_ERROR
)
141 tdata
.size
= NOVFLSIZE
;
142 memmove(db
, &pg
, sizeof(pgno_t
));
143 memmove(db
+ sizeof(pgno_t
),
144 &data
->size
, sizeof(u_int32_t
));
148 if (key
->size
+ data
->size
> t
->bt_ovflsize
)
152 /* Replace the cursor. */
153 if (flags
== R_CURSOR
) {
154 if ((h
= mpool_get(t
->bt_mp
, t
->bt_cursor
.pg
.pgno
, 0)) == NULL
)
156 index
= t
->bt_cursor
.pg
.index
;
161 * Find the key to delete, or, the location at which to insert.
162 * Bt_fast and __bt_search both pin the returned page.
164 if (t
->bt_order
== NOT
|| (e
= bt_fast(t
, key
, data
, &exact
)) == NULL
)
165 if ((e
= __bt_search(t
, key
, &exact
)) == NULL
)
171 * Add the key/data pair to the tree. If an identical key is already
172 * in the tree, and R_NOOVERWRITE is set, an error is returned. If
173 * R_NOOVERWRITE is not set, the key is either added (if duplicates are
174 * permitted) or an error is returned.
180 mpool_put(t
->bt_mp
, h
, 0);
181 return (RET_SPECIAL
);
183 if (!exact
|| !F_ISSET(t
, B_NODUPS
))
187 * Note, the delete may empty the page, so we need to put a
188 * new entry into the page immediately.
190 delete: if (__bt_dleaf(t
, key
, h
, index
) == RET_ERROR
) {
191 mpool_put(t
->bt_mp
, h
, 0);
198 * If not enough room, or the user has put a ceiling on the number of
199 * keys permitted in the page, split the page. The split code will
200 * insert the key and data and unpin the current page. If inserting
201 * into the offset array, shift the pointers up.
203 nbytes
= NBLEAFDBT(key
->size
, data
->size
);
204 if ((u_int32_t
) (h
->upper
- h
->lower
) < nbytes
+ sizeof(indx_t
)) {
205 if ((status
= __bt_split(t
, h
, key
,
206 data
, dflags
, nbytes
, index
)) != RET_SUCCESS
)
211 if (index
< (nxtindex
= NEXTINDEX(h
)))
212 memmove(h
->linp
+ index
+ 1, h
->linp
+ index
,
213 (nxtindex
- index
) * sizeof(indx_t
));
214 h
->lower
+= sizeof(indx_t
);
216 h
->linp
[index
] = h
->upper
-= nbytes
;
217 dest
= (char *)h
+ h
->upper
;
218 WR_BLEAF(dest
, key
, data
, dflags
);
220 /* If the cursor is on this page, adjust it as necessary. */
221 if (F_ISSET(&t
->bt_cursor
, CURS_INIT
) &&
222 !F_ISSET(&t
->bt_cursor
, CURS_ACQUIRE
) &&
223 t
->bt_cursor
.pg
.pgno
== h
->pgno
&& t
->bt_cursor
.pg
.index
>= index
)
224 ++t
->bt_cursor
.pg
.index
;
226 if (t
->bt_order
== NOT
) {
227 if (h
->nextpg
== P_INVALID
) {
228 if (index
== NEXTINDEX(h
) - 1) {
229 t
->bt_order
= FORWARD
;
230 t
->bt_last
.index
= index
;
231 t
->bt_last
.pgno
= h
->pgno
;
233 } else if (h
->prevpg
== P_INVALID
) {
236 t
->bt_last
.index
= 0;
237 t
->bt_last
.pgno
= h
->pgno
;
242 mpool_put(t
->bt_mp
, h
, MPOOL_DIRTY
);
245 if (flags
== R_SETCURSOR
)
246 __bt_setcur(t
, e
->page
->pgno
, e
->index
);
248 F_SET(t
, B_MODIFIED
);
249 return (RET_SUCCESS
);
253 u_long bt_cache_hit
, bt_cache_miss
;
257 * BT_FAST -- Do a quick check for sorted data.
264 * EPG for new record or NULL if not found.
267 bt_fast(t
, key
, data
, exactp
)
269 const DBT
*key
, *data
;
276 if ((h
= mpool_get(t
->bt_mp
, t
->bt_last
.pgno
, 0)) == NULL
) {
281 t
->bt_cur
.index
= t
->bt_last
.index
;
284 * If won't fit in this page or have too many keys in this page,
285 * have to search to get split stack.
287 nbytes
= NBLEAFDBT(key
->size
, data
->size
);
288 if ((u_int32_t
) (h
->upper
- h
->lower
) < nbytes
+ sizeof(indx_t
))
291 if (t
->bt_order
== FORWARD
) {
292 if (t
->bt_cur
.page
->nextpg
!= P_INVALID
)
294 if (t
->bt_cur
.index
!= NEXTINDEX(h
) - 1)
296 if ((cmp
= __bt_cmp(t
, key
, &t
->bt_cur
)) < 0)
298 t
->bt_last
.index
= cmp
? ++t
->bt_cur
.index
: t
->bt_cur
.index
;
300 if (t
->bt_cur
.page
->prevpg
!= P_INVALID
)
302 if (t
->bt_cur
.index
!= 0)
304 if ((cmp
= __bt_cmp(t
, key
, &t
->bt_cur
)) > 0)
306 t
->bt_last
.index
= 0;
319 mpool_put(t
->bt_mp
, h
, 0);