rec_delete.c revision 1573
11573Srgrimes/*- 21573Srgrimes * Copyright (c) 1990, 1993 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) 381573Srgrimesstatic char sccsid[] = "@(#)rec_delete.c 8.4 (Berkeley) 2/21/94"; 391573Srgrimes#endif /* LIBC_SCCS and not lint */ 401573Srgrimes 411573Srgrimes#include <sys/types.h> 421573Srgrimes 431573Srgrimes#include <errno.h> 441573Srgrimes#include <stdio.h> 451573Srgrimes#include <string.h> 461573Srgrimes 471573Srgrimes#include <db.h> 481573Srgrimes#include "recno.h" 491573Srgrimes 501573Srgrimesstatic int rec_rdelete __P((BTREE *, recno_t)); 511573Srgrimes 521573Srgrimes/* 531573Srgrimes * __REC_DELETE -- Delete the item(s) referenced by a key. 541573Srgrimes * 551573Srgrimes * Parameters: 561573Srgrimes * dbp: pointer to access method 571573Srgrimes * key: key to delete 581573Srgrimes * flags: R_CURSOR if deleting what the cursor references 591573Srgrimes * 601573Srgrimes * Returns: 611573Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 621573Srgrimes */ 631573Srgrimesint 641573Srgrimes__rec_delete(dbp, key, flags) 651573Srgrimes const DB *dbp; 661573Srgrimes const DBT *key; 671573Srgrimes u_int flags; 681573Srgrimes{ 691573Srgrimes BTREE *t; 701573Srgrimes recno_t nrec; 711573Srgrimes int status; 721573Srgrimes 731573Srgrimes t = dbp->internal; 741573Srgrimes 751573Srgrimes /* Toss any page pinned across calls. */ 761573Srgrimes if (t->bt_pinned != NULL) { 771573Srgrimes mpool_put(t->bt_mp, t->bt_pinned, 0); 781573Srgrimes t->bt_pinned = NULL; 791573Srgrimes } 801573Srgrimes 811573Srgrimes switch(flags) { 821573Srgrimes case 0: 831573Srgrimes if ((nrec = *(recno_t *)key->data) == 0) 841573Srgrimes goto einval; 851573Srgrimes if (nrec > t->bt_nrecs) 861573Srgrimes return (RET_SPECIAL); 871573Srgrimes --nrec; 881573Srgrimes status = rec_rdelete(t, nrec); 891573Srgrimes break; 901573Srgrimes case R_CURSOR: 911573Srgrimes if (!ISSET(t, B_SEQINIT)) 921573Srgrimes goto einval; 931573Srgrimes if (t->bt_nrecs == 0) 941573Srgrimes return (RET_SPECIAL); 951573Srgrimes status = rec_rdelete(t, t->bt_rcursor - 1); 961573Srgrimes if (status == RET_SUCCESS) 971573Srgrimes --t->bt_rcursor; 981573Srgrimes break; 991573Srgrimes default: 1001573Srgrimeseinval: errno = EINVAL; 1011573Srgrimes return (RET_ERROR); 1021573Srgrimes } 1031573Srgrimes 1041573Srgrimes if (status == RET_SUCCESS) 1051573Srgrimes SET(t, B_MODIFIED | R_MODIFIED); 1061573Srgrimes return (status); 1071573Srgrimes} 1081573Srgrimes 1091573Srgrimes/* 1101573Srgrimes * REC_RDELETE -- Delete the data matching the specified key. 1111573Srgrimes * 1121573Srgrimes * Parameters: 1131573Srgrimes * tree: tree 1141573Srgrimes * nrec: record to delete 1151573Srgrimes * 1161573Srgrimes * Returns: 1171573Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 1181573Srgrimes */ 1191573Srgrimesstatic int 1201573Srgrimesrec_rdelete(t, nrec) 1211573Srgrimes BTREE *t; 1221573Srgrimes recno_t nrec; 1231573Srgrimes{ 1241573Srgrimes EPG *e; 1251573Srgrimes PAGE *h; 1261573Srgrimes int status; 1271573Srgrimes 1281573Srgrimes /* Find the record; __rec_search pins the page. */ 1291573Srgrimes if ((e = __rec_search(t, nrec, SDELETE)) == NULL) 1301573Srgrimes return (RET_ERROR); 1311573Srgrimes 1321573Srgrimes /* Delete the record. */ 1331573Srgrimes h = e->page; 1341573Srgrimes status = __rec_dleaf(t, h, e->index); 1351573Srgrimes if (status != RET_SUCCESS) { 1361573Srgrimes mpool_put(t->bt_mp, h, 0); 1371573Srgrimes return (status); 1381573Srgrimes } 1391573Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 1401573Srgrimes return (RET_SUCCESS); 1411573Srgrimes} 1421573Srgrimes 1431573Srgrimes/* 1441573Srgrimes * __REC_DLEAF -- Delete a single record from a recno leaf page. 1451573Srgrimes * 1461573Srgrimes * Parameters: 1471573Srgrimes * t: tree 1481573Srgrimes * index: index on current page to delete 1491573Srgrimes * 1501573Srgrimes * Returns: 1511573Srgrimes * RET_SUCCESS, RET_ERROR. 1521573Srgrimes */ 1531573Srgrimesint 1541573Srgrimes__rec_dleaf(t, h, index) 1551573Srgrimes BTREE *t; 1561573Srgrimes PAGE *h; 1571573Srgrimes indx_t index; 1581573Srgrimes{ 1591573Srgrimes register RLEAF *rl; 1601573Srgrimes register indx_t *ip, cnt, offset; 1611573Srgrimes register size_t nbytes; 1621573Srgrimes char *from; 1631573Srgrimes void *to; 1641573Srgrimes 1651573Srgrimes /* 1661573Srgrimes * Delete a record from a recno leaf page. Internal records are never 1671573Srgrimes * deleted from internal pages, regardless of the records that caused 1681573Srgrimes * them to be added being deleted. Pages made empty by deletion are 1691573Srgrimes * not reclaimed. They are, however, made available for reuse. 1701573Srgrimes * 1711573Srgrimes * Pack the remaining entries at the end of the page, shift the indices 1721573Srgrimes * down, overwriting the deleted record and its index. If the record 1731573Srgrimes * uses overflow pages, make them available for reuse. 1741573Srgrimes */ 1751573Srgrimes to = rl = GETRLEAF(h, index); 1761573Srgrimes if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR) 1771573Srgrimes return (RET_ERROR); 1781573Srgrimes nbytes = NRLEAF(rl); 1791573Srgrimes 1801573Srgrimes /* 1811573Srgrimes * Compress the key/data pairs. Compress and adjust the [BR]LEAF 1821573Srgrimes * offsets. Reset the headers. 1831573Srgrimes */ 1841573Srgrimes from = (char *)h + h->upper; 1851573Srgrimes memmove(from + nbytes, from, (char *)to - from); 1861573Srgrimes h->upper += nbytes; 1871573Srgrimes 1881573Srgrimes offset = h->linp[index]; 1891573Srgrimes for (cnt = &h->linp[index] - (ip = &h->linp[0]); cnt--; ++ip) 1901573Srgrimes if (ip[0] < offset) 1911573Srgrimes ip[0] += nbytes; 1921573Srgrimes for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip) 1931573Srgrimes ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; 1941573Srgrimes h->lower -= sizeof(indx_t); 1951573Srgrimes --t->bt_nrecs; 1961573Srgrimes return (RET_SUCCESS); 1971573Srgrimes} 198