rec_delete.c revision 92905
11573Srgrimes/*- 214272Spst * Copyright (c) 1990, 1993, 1994 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * This code is derived from software contributed to Berkeley by 61573Srgrimes * Mike Olson. 71573Srgrimes * 81573Srgrimes * Redistribution and use in source and binary forms, with or without 91573Srgrimes * modification, are permitted provided that the following conditions 101573Srgrimes * are met: 111573Srgrimes * 1. Redistributions of source code must retain the above copyright 121573Srgrimes * notice, this list of conditions and the following disclaimer. 131573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141573Srgrimes * notice, this list of conditions and the following disclaimer in the 151573Srgrimes * documentation and/or other materials provided with the distribution. 161573Srgrimes * 3. All advertising materials mentioning features or use of this software 171573Srgrimes * must display the following acknowledgement: 181573Srgrimes * This product includes software developed by the University of 191573Srgrimes * California, Berkeley and its contributors. 201573Srgrimes * 4. Neither the name of the University nor the names of its contributors 211573Srgrimes * may be used to endorse or promote products derived from this software 221573Srgrimes * without specific prior written permission. 231573Srgrimes * 241573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341573Srgrimes * SUCH DAMAGE. 351573Srgrimes */ 361573Srgrimes 371573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3814272Spststatic char sccsid[] = "@(#)rec_delete.c 8.7 (Berkeley) 7/14/94"; 391573Srgrimes#endif /* LIBC_SCCS and not lint */ 4092905Sobrien#include <sys/cdefs.h> 4192905Sobrien__FBSDID("$FreeBSD: head/lib/libc/db/recno/rec_delete.c 92905 2002-03-21 22:49:10Z obrien $"); 421573Srgrimes 431573Srgrimes#include <sys/types.h> 441573Srgrimes 451573Srgrimes#include <errno.h> 461573Srgrimes#include <stdio.h> 471573Srgrimes#include <string.h> 481573Srgrimes 491573Srgrimes#include <db.h> 501573Srgrimes#include "recno.h" 511573Srgrimes 5292905Sobrienstatic int rec_rdelete(BTREE *, recno_t); 531573Srgrimes 541573Srgrimes/* 551573Srgrimes * __REC_DELETE -- Delete the item(s) referenced by a key. 561573Srgrimes * 571573Srgrimes * Parameters: 581573Srgrimes * dbp: pointer to access method 591573Srgrimes * key: key to delete 601573Srgrimes * flags: R_CURSOR if deleting what the cursor references 611573Srgrimes * 621573Srgrimes * Returns: 631573Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 641573Srgrimes */ 651573Srgrimesint 661573Srgrimes__rec_delete(dbp, key, flags) 671573Srgrimes const DB *dbp; 681573Srgrimes const DBT *key; 691573Srgrimes u_int flags; 701573Srgrimes{ 711573Srgrimes BTREE *t; 721573Srgrimes recno_t nrec; 731573Srgrimes int status; 741573Srgrimes 751573Srgrimes t = dbp->internal; 761573Srgrimes 771573Srgrimes /* Toss any page pinned across calls. */ 781573Srgrimes if (t->bt_pinned != NULL) { 791573Srgrimes mpool_put(t->bt_mp, t->bt_pinned, 0); 801573Srgrimes t->bt_pinned = NULL; 811573Srgrimes } 821573Srgrimes 831573Srgrimes switch(flags) { 841573Srgrimes case 0: 851573Srgrimes if ((nrec = *(recno_t *)key->data) == 0) 861573Srgrimes goto einval; 871573Srgrimes if (nrec > t->bt_nrecs) 881573Srgrimes return (RET_SPECIAL); 891573Srgrimes --nrec; 901573Srgrimes status = rec_rdelete(t, nrec); 911573Srgrimes break; 921573Srgrimes case R_CURSOR: 9314272Spst if (!F_ISSET(&t->bt_cursor, CURS_INIT)) 941573Srgrimes goto einval; 951573Srgrimes if (t->bt_nrecs == 0) 961573Srgrimes return (RET_SPECIAL); 9714272Spst status = rec_rdelete(t, t->bt_cursor.rcursor - 1); 981573Srgrimes if (status == RET_SUCCESS) 9914272Spst --t->bt_cursor.rcursor; 1001573Srgrimes break; 1011573Srgrimes default: 1021573Srgrimeseinval: errno = EINVAL; 1031573Srgrimes return (RET_ERROR); 1041573Srgrimes } 1051573Srgrimes 1061573Srgrimes if (status == RET_SUCCESS) 10714272Spst F_SET(t, B_MODIFIED | R_MODIFIED); 1081573Srgrimes return (status); 1091573Srgrimes} 1101573Srgrimes 1111573Srgrimes/* 1121573Srgrimes * REC_RDELETE -- Delete the data matching the specified key. 1131573Srgrimes * 1141573Srgrimes * Parameters: 1151573Srgrimes * tree: tree 1161573Srgrimes * nrec: record to delete 1171573Srgrimes * 1181573Srgrimes * Returns: 1191573Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 1201573Srgrimes */ 1211573Srgrimesstatic int 1221573Srgrimesrec_rdelete(t, nrec) 1231573Srgrimes BTREE *t; 1241573Srgrimes recno_t nrec; 1251573Srgrimes{ 1261573Srgrimes EPG *e; 1271573Srgrimes PAGE *h; 1281573Srgrimes int status; 1291573Srgrimes 1301573Srgrimes /* Find the record; __rec_search pins the page. */ 1311573Srgrimes if ((e = __rec_search(t, nrec, SDELETE)) == NULL) 1321573Srgrimes return (RET_ERROR); 1331573Srgrimes 1341573Srgrimes /* Delete the record. */ 1351573Srgrimes h = e->page; 1361573Srgrimes status = __rec_dleaf(t, h, e->index); 1371573Srgrimes if (status != RET_SUCCESS) { 1381573Srgrimes mpool_put(t->bt_mp, h, 0); 1391573Srgrimes return (status); 1401573Srgrimes } 1411573Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 1421573Srgrimes return (RET_SUCCESS); 1431573Srgrimes} 1441573Srgrimes 1451573Srgrimes/* 1461573Srgrimes * __REC_DLEAF -- Delete a single record from a recno leaf page. 1471573Srgrimes * 1481573Srgrimes * Parameters: 1491573Srgrimes * t: tree 1501573Srgrimes * index: index on current page to delete 1511573Srgrimes * 1521573Srgrimes * Returns: 1531573Srgrimes * RET_SUCCESS, RET_ERROR. 1541573Srgrimes */ 1551573Srgrimesint 1561573Srgrimes__rec_dleaf(t, h, index) 1571573Srgrimes BTREE *t; 1581573Srgrimes PAGE *h; 15914272Spst u_int32_t index; 1601573Srgrimes{ 16114272Spst RLEAF *rl; 16214272Spst indx_t *ip, cnt, offset; 16314272Spst u_int32_t nbytes; 1641573Srgrimes char *from; 1651573Srgrimes void *to; 1661573Srgrimes 1671573Srgrimes /* 1681573Srgrimes * Delete a record from a recno leaf page. Internal records are never 1691573Srgrimes * deleted from internal pages, regardless of the records that caused 1701573Srgrimes * them to be added being deleted. Pages made empty by deletion are 1711573Srgrimes * not reclaimed. They are, however, made available for reuse. 1721573Srgrimes * 1731573Srgrimes * Pack the remaining entries at the end of the page, shift the indices 1741573Srgrimes * down, overwriting the deleted record and its index. If the record 1751573Srgrimes * uses overflow pages, make them available for reuse. 1761573Srgrimes */ 1771573Srgrimes to = rl = GETRLEAF(h, index); 1781573Srgrimes if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR) 1791573Srgrimes return (RET_ERROR); 1801573Srgrimes nbytes = NRLEAF(rl); 1811573Srgrimes 1821573Srgrimes /* 1831573Srgrimes * Compress the key/data pairs. Compress and adjust the [BR]LEAF 1841573Srgrimes * offsets. Reset the headers. 1851573Srgrimes */ 1861573Srgrimes from = (char *)h + h->upper; 1871573Srgrimes memmove(from + nbytes, from, (char *)to - from); 1881573Srgrimes h->upper += nbytes; 1891573Srgrimes 1901573Srgrimes offset = h->linp[index]; 1911573Srgrimes for (cnt = &h->linp[index] - (ip = &h->linp[0]); cnt--; ++ip) 1921573Srgrimes if (ip[0] < offset) 1931573Srgrimes ip[0] += nbytes; 1941573Srgrimes for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip) 1951573Srgrimes ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; 1961573Srgrimes h->lower -= sizeof(indx_t); 1971573Srgrimes --t->bt_nrecs; 1981573Srgrimes return (RET_SUCCESS); 1991573Srgrimes} 200