rec_delete.c revision 189291
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 * 4. Neither the name of the University nor the names of its contributors 171573Srgrimes * may be used to endorse or promote products derived from this software 181573Srgrimes * without specific prior written permission. 191573Srgrimes * 201573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301573Srgrimes * SUCH DAMAGE. 311573Srgrimes */ 321573Srgrimes 331573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3414272Spststatic char sccsid[] = "@(#)rec_delete.c 8.7 (Berkeley) 7/14/94"; 351573Srgrimes#endif /* LIBC_SCCS and not lint */ 3692905Sobrien#include <sys/cdefs.h> 3792905Sobrien__FBSDID("$FreeBSD: head/lib/libc/db/recno/rec_delete.c 189291 2009-03-02 23:47:18Z delphij $"); 381573Srgrimes 391573Srgrimes#include <sys/types.h> 401573Srgrimes 411573Srgrimes#include <errno.h> 421573Srgrimes#include <stdio.h> 431573Srgrimes#include <string.h> 441573Srgrimes 451573Srgrimes#include <db.h> 461573Srgrimes#include "recno.h" 471573Srgrimes 4892905Sobrienstatic int rec_rdelete(BTREE *, recno_t); 491573Srgrimes 501573Srgrimes/* 511573Srgrimes * __REC_DELETE -- Delete the item(s) referenced by a key. 521573Srgrimes * 531573Srgrimes * Parameters: 541573Srgrimes * dbp: pointer to access method 551573Srgrimes * key: key to delete 561573Srgrimes * flags: R_CURSOR if deleting what the cursor references 571573Srgrimes * 581573Srgrimes * Returns: 591573Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 601573Srgrimes */ 611573Srgrimesint 62189291Sdelphij__rec_delete(const DB *dbp, const DBT *key, u_int flags) 631573Srgrimes{ 641573Srgrimes BTREE *t; 651573Srgrimes recno_t nrec; 661573Srgrimes int status; 671573Srgrimes 681573Srgrimes t = dbp->internal; 691573Srgrimes 701573Srgrimes /* Toss any page pinned across calls. */ 711573Srgrimes if (t->bt_pinned != NULL) { 721573Srgrimes mpool_put(t->bt_mp, t->bt_pinned, 0); 731573Srgrimes t->bt_pinned = NULL; 741573Srgrimes } 751573Srgrimes 761573Srgrimes switch(flags) { 771573Srgrimes case 0: 781573Srgrimes if ((nrec = *(recno_t *)key->data) == 0) 791573Srgrimes goto einval; 801573Srgrimes if (nrec > t->bt_nrecs) 811573Srgrimes return (RET_SPECIAL); 821573Srgrimes --nrec; 831573Srgrimes status = rec_rdelete(t, nrec); 841573Srgrimes break; 851573Srgrimes case R_CURSOR: 8614272Spst if (!F_ISSET(&t->bt_cursor, CURS_INIT)) 871573Srgrimes goto einval; 881573Srgrimes if (t->bt_nrecs == 0) 891573Srgrimes return (RET_SPECIAL); 9014272Spst status = rec_rdelete(t, t->bt_cursor.rcursor - 1); 911573Srgrimes if (status == RET_SUCCESS) 9214272Spst --t->bt_cursor.rcursor; 931573Srgrimes break; 941573Srgrimes default: 951573Srgrimeseinval: errno = EINVAL; 961573Srgrimes return (RET_ERROR); 971573Srgrimes } 981573Srgrimes 991573Srgrimes if (status == RET_SUCCESS) 10014272Spst F_SET(t, B_MODIFIED | R_MODIFIED); 1011573Srgrimes return (status); 1021573Srgrimes} 1031573Srgrimes 1041573Srgrimes/* 1051573Srgrimes * REC_RDELETE -- Delete the data matching the specified key. 1061573Srgrimes * 1071573Srgrimes * Parameters: 1081573Srgrimes * tree: tree 1091573Srgrimes * nrec: record to delete 1101573Srgrimes * 1111573Srgrimes * Returns: 1121573Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 1131573Srgrimes */ 1141573Srgrimesstatic int 115189291Sdelphijrec_rdelete(BTREE *t, recno_t nrec) 1161573Srgrimes{ 1171573Srgrimes EPG *e; 1181573Srgrimes PAGE *h; 1191573Srgrimes int status; 1201573Srgrimes 1211573Srgrimes /* Find the record; __rec_search pins the page. */ 1221573Srgrimes if ((e = __rec_search(t, nrec, SDELETE)) == NULL) 1231573Srgrimes return (RET_ERROR); 1241573Srgrimes 1251573Srgrimes /* Delete the record. */ 1261573Srgrimes h = e->page; 1271573Srgrimes status = __rec_dleaf(t, h, e->index); 1281573Srgrimes if (status != RET_SUCCESS) { 1291573Srgrimes mpool_put(t->bt_mp, h, 0); 1301573Srgrimes return (status); 1311573Srgrimes } 1321573Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 1331573Srgrimes return (RET_SUCCESS); 1341573Srgrimes} 1351573Srgrimes 1361573Srgrimes/* 1371573Srgrimes * __REC_DLEAF -- Delete a single record from a recno leaf page. 1381573Srgrimes * 1391573Srgrimes * Parameters: 1401573Srgrimes * t: tree 1411573Srgrimes * index: index on current page to delete 1421573Srgrimes * 1431573Srgrimes * Returns: 1441573Srgrimes * RET_SUCCESS, RET_ERROR. 1451573Srgrimes */ 1461573Srgrimesint 1471573Srgrimes__rec_dleaf(t, h, index) 1481573Srgrimes BTREE *t; 1491573Srgrimes PAGE *h; 15014272Spst u_int32_t index; 1511573Srgrimes{ 15214272Spst RLEAF *rl; 15314272Spst indx_t *ip, cnt, offset; 15414272Spst u_int32_t nbytes; 1551573Srgrimes char *from; 1561573Srgrimes void *to; 1571573Srgrimes 1581573Srgrimes /* 1591573Srgrimes * Delete a record from a recno leaf page. Internal records are never 1601573Srgrimes * deleted from internal pages, regardless of the records that caused 1611573Srgrimes * them to be added being deleted. Pages made empty by deletion are 1621573Srgrimes * not reclaimed. They are, however, made available for reuse. 1631573Srgrimes * 1641573Srgrimes * Pack the remaining entries at the end of the page, shift the indices 1651573Srgrimes * down, overwriting the deleted record and its index. If the record 1661573Srgrimes * uses overflow pages, make them available for reuse. 1671573Srgrimes */ 1681573Srgrimes to = rl = GETRLEAF(h, index); 1691573Srgrimes if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR) 1701573Srgrimes return (RET_ERROR); 1711573Srgrimes nbytes = NRLEAF(rl); 1721573Srgrimes 1731573Srgrimes /* 1741573Srgrimes * Compress the key/data pairs. Compress and adjust the [BR]LEAF 1751573Srgrimes * offsets. Reset the headers. 1761573Srgrimes */ 1771573Srgrimes from = (char *)h + h->upper; 1781573Srgrimes memmove(from + nbytes, from, (char *)to - from); 1791573Srgrimes h->upper += nbytes; 1801573Srgrimes 1811573Srgrimes offset = h->linp[index]; 1821573Srgrimes for (cnt = &h->linp[index] - (ip = &h->linp[0]); cnt--; ++ip) 1831573Srgrimes if (ip[0] < offset) 1841573Srgrimes ip[0] += nbytes; 1851573Srgrimes for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip) 1861573Srgrimes ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; 1871573Srgrimes h->lower -= sizeof(indx_t); 1881573Srgrimes --t->bt_nrecs; 1891573Srgrimes return (RET_SUCCESS); 1901573Srgrimes} 191