* Copyright (c) 1990 The Regents of the University of California.
* This code is derived from software contributed to Berkeley by
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* 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
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)insert.c 5.3 (Berkeley) 2/22/91";
#endif /* LIBC_SCCS and not lint */
* _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.
* t -- btree in which to do the insertion.
* item -- BTITEM describing location of new datum
* data -- data associated with key
* flag -- magic cookie passed recursively to bt_put if we
* RET_SUCCESS, RET_ERROR.
_bt_insert(t
, item
, key
, data
, flag
)
if (_bt_getpage(t
, item
->bti_pgno
) == RET_ERROR
)
if (TOOBIG(t
, data
->size
)) {
datasize
= sizeof(pgno_t
);
if (TOOBIG(t
, key
->size
)) {
keysize
= sizeof(pgno_t
);
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
)
/* okay, try again (empty the stack first, though) */
while (_bt_pop((BTREE
) t
) != P_NONE
)
return (bt_put((BTREE
) t
, key
, data
, flag
));
/* put together a leaf page datum from the key/data pair */
nbytes
= keysize
+ datasize
+ (sizeof(DATUM
) - sizeof(char));
if ((d
= (DATUM
*) malloc((unsigned) nbytes
)) == (DATUM
*) NULL
)
if (_bt_indirect(t
, key
, &pgno
) == RET_ERROR
)
(void) bcopy((char *) &pgno
, &(d
->d_bytes
[0]), sizeof(pgno
));
if (_bt_getpage(t
, item
->bti_pgno
) == RET_ERROR
)
(void) bcopy((char *) key
->data
,
(char *) &(d
->d_bytes
[0]),
if (_bt_indirect(t
, data
, &pgno
) == RET_ERROR
)
(void) bcopy((char *) &pgno
,
if (_bt_getpage(t
, item
->bti_pgno
) == RET_ERROR
)
(void) bcopy((char *) data
->data
,
(char *) &(d
->d_bytes
[keysize
]),
status
= _bt_insertat(t
, (char *) d
, index
);
* _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.
* t -- tree in which to do insertion.
* id -- new IDATUM to insert
* pgno -- page number of IDATUM left of id's position
* RET_SUCCESS, RET_ERROR.
BTHEADER
*h
= t
->bt_curpage
;
if (id
->i_flags
& D_BIGKEY
) {
bcopy(&(id
->i_bytes
[0]), (char *) &chain
, sizeof(chain
));
if (_bt_getbig(t
, chain
, &key
, &ignore
) == RET_ERROR
)
while (i
< next
&& _bt_cmp(t
, key
, i
) >= 0)
/* okay, now we're close; find adjacent IDATUM */
idx
= (IDATUM
*) GETDATUM(h
,i
);
if (idx
->i_pgno
== pgno
) {
/* 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.
* t -- tree in which to do insertion.
* p -- DATUM or IDATUM to insert.
* index -- index in line pointer array to put this item.
* RET_SUCCESS, RET_ERROR.
* Will rearrange line pointers to make space for the new
* entry. This means that any scans currently active are
* There must be sufficient room for the new item on the page.
_bt_insertat(t
, p
, index
)
IDATUM
*id
= (IDATUM
*) p
;
/* insertion may confuse an active scan. fix it. */
if (t
->bt_flags
& BTF_SEQINIT
&& t
->bt_curpage
->h_pgno
== c
->c_pgno
)
if (_bt_fixscan(t
, index
, d
, INSERT
) == RET_ERROR
)
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.
src
= (char *) &(h
->h_linp
[index
]);
dest
= (char *) &(h
->h_linp
[index
+ 1]);
nbytes
= (h
->h_lower
- (src
- ((char *) h
)))
(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));
nbytes
= id
->i_size
+ (sizeof(IDATUM
) - sizeof(char));
dest
= (((char *) h
) + h
->h_upper
) - LONGALIGN(nbytes
);
(void) bcopy((char *) p
, dest
, nbytes
);
h
->h_linp
[index
] = (index_t
) dest
;
h
->h_upper
= (index_t
) dest
;
h
->h_lower
+= sizeof(index_t
);