* Copyright (c) 1990 The Regents of the University of California.
* This code is derived from software contributed to Berkeley by
* %sccs.include.redist.c%
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)bt_put.c 5.11 (Berkeley) %G%";
#endif /* LIBC_SCCS and not lint */
static EPG
*bt_fast
__P((BTREE
*, const DBT
*, const DBT
*, int *));
* __BT_PUT -- Add a btree item to the tree.
* dbp: pointer to access method
* RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the
* tree and R_NOOVERWRITE specified.
__bt_put(dbp
, key
, data
, flags
)
int dflags
, exact
, status
;
char *dest
, db
[NOVFLSIZE
], kb
[NOVFLSIZE
];
if (!ISSET(t
, BTF_SEQINIT
))
if (ISSET(t
, BTF_DELCRSR
))
if (ISSET(t
, BTF_RDONLY
)) {
* If the key/data won't fit on a page, store it on indirect pages.
* Only store the key on the overflow page if it's too big after the
* data is on an overflow page.
* If the insert fails later on, these pages aren't recovered.
if (key
->size
+ data
->size
> t
->bt_ovflsize
) {
if (key
->size
> t
->bt_ovflsize
) {
storekey
: if (__ovfl_put(t
, key
, &pg
) == RET_ERROR
)
bcopy(&pg
, kb
, sizeof(pgno_t
));
bcopy(&key
->size
, kb
+ sizeof(pgno_t
), sizeof(size_t));
if (key
->size
+ data
->size
> t
->bt_ovflsize
) {
if (__ovfl_put(t
, data
, &pg
) == RET_ERROR
)
bcopy(&pg
, db
, sizeof(pgno_t
));
bcopy(&data
->size
, db
+ sizeof(pgno_t
), sizeof(size_t));
if (key
->size
+ data
->size
> t
->bt_ovflsize
)
/* Replace the cursor. */
if ((h
= mpool_get(t
->bt_mp
, t
->bt_bcursor
.pgno
, 0)) == NULL
)
index
= t
->bt_bcursor
.index
;
* Find the key to delete, or, the location at which to insert. Bt_fast
* and __bt_search pin the returned page.
if (t
->bt_order
== NOT
|| (e
= bt_fast(t
, key
, data
, &exact
)) == NULL
)
if ((e
= __bt_search(t
, key
, &exact
)) == NULL
)
* Add the specified key/data pair to the tree. If an identical key
* is already in the tree, and R_NOOVERWRITE is set, an error is
* returned. If R_NOOVERWRITE is not set, the key is either added (if
* duplicates are permitted) or an error is returned.
* Pages are split as required.
* One special case is if the cursor references the record and
* it's been flagged for deletion. Then, we delete the record,
* leaving the cursor there -- this means that the inserted
* record will not be seen in a cursor scan.
if (ISSET(t
, BTF_DELCRSR
) && t
->bt_bcursor
.pgno
== h
->pgno
&&
t
->bt_bcursor
.index
== index
) {
mpool_put(t
->bt_mp
, h
, 0);
if (!exact
|| !ISSET(t
, BTF_NODUPS
))
delete: if (__bt_dleaf(t
, h
, index
) == RET_ERROR
) {
mpool_put(t
->bt_mp
, h
, 0);
* If not enough room, or the user has put a ceiling on the number of
* keys permitted in the page, split the page. The split code will
* insert the key and data and unpin the current page. If inserting
* into the offset array, shift the pointers up.
nbytes
= NBLEAFDBT(key
->size
, data
->size
);
if (h
->upper
- h
->lower
< nbytes
+ sizeof(index_t
)) {
if ((status
= __bt_split(t
, h
, key
,
data
, dflags
, nbytes
, index
)) != RET_SUCCESS
)
if (index
< (nxtindex
= NEXTINDEX(h
)))
bcopy(h
->linp
+ index
, h
->linp
+ index
+ 1,
(nxtindex
- index
) * sizeof(index_t
));
h
->lower
+= sizeof(index_t
);
h
->linp
[index
] = h
->upper
-= nbytes
;
dest
= (char *)h
+ h
->upper
;
WR_BLEAF(dest
, key
, data
, dflags
);
if (h
->nextpg
== P_INVALID
) {
if (index
== NEXTINDEX(h
) - 1) {
t
->bt_last
.index
= index
;
t
->bt_last
.pgno
= h
->pgno
;
} else if (h
->prevpg
== P_INVALID
) {
t
->bt_last
.pgno
= h
->pgno
;
mpool_put(t
->bt_mp
, h
, MPOOL_DIRTY
);
if (flags
== R_SETCURSOR
) {
t
->bt_bcursor
.pgno
= e
->page
->pgno
;
t
->bt_bcursor
.index
= e
->index
;
u_long bt_cache_hit
, bt_cache_miss
;
* BT_FAST -- Do a quick check for sorted data.
* EPG for new record or NULL if not found.
bt_fast(t
, key
, data
, exactp
)
if ((h
= mpool_get(t
->bt_mp
, t
->bt_last
.pgno
, 0)) == NULL
) {
e
.index
= t
->bt_last
.index
;
* If won't fit in this page or have too many keys in this page, have
* to search to get split stack.
nbytes
= NBLEAFDBT(key
->size
, data
->size
);
if (h
->upper
- h
->lower
< nbytes
+ sizeof(index_t
))
if (t
->bt_order
== FORWARD
) {
if (e
.page
->nextpg
!= P_INVALID
)
if (e
.index
!= NEXTINDEX(h
) - 1)
if ((cmp
= __bt_cmp(t
, key
, &e
)) < 0)
t
->bt_last
.index
= cmp
? ++e
.index
: e
.index
;
if (e
.page
->prevpg
!= P_INVALID
)
if ((cmp
= __bt_cmp(t
, key
, &e
)) > 0)
mpool_put(t
->bt_mp
, h
, 0);