11590Srgrimes/*- 21590Srgrimes * Copyright (c) 1990, 1993, 1994 31590Srgrimes * The Regents of the University of California. All rights reserved. 41590Srgrimes * 51590Srgrimes * This code is derived from software contributed to Berkeley by 61590Srgrimes * Mike Olson. 71590Srgrimes * 81590Srgrimes * Redistribution and use in source and binary forms, with or without 91590Srgrimes * modification, are permitted provided that the following conditions 101590Srgrimes * are met: 111590Srgrimes * 1. Redistributions of source code must retain the above copyright 121590Srgrimes * notice, this list of conditions and the following disclaimer. 131590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141590Srgrimes * notice, this list of conditions and the following disclaimer in the 151590Srgrimes * documentation and/or other materials provided with the distribution. 161590Srgrimes * 4. Neither the name of the University nor the names of its contributors 171590Srgrimes * may be used to endorse or promote products derived from this software 181590Srgrimes * without specific prior written permission. 191590Srgrimes * 201590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301590Srgrimes * SUCH DAMAGE. 311590Srgrimes */ 321590Srgrimes 331590Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 341590Srgrimesstatic char sccsid[] = "@(#)rec_delete.c 8.7 (Berkeley) 7/14/94"; 3527314Scharnier#endif /* LIBC_SCCS and not lint */ 361590Srgrimes#include <sys/cdefs.h> 371590Srgrimes__FBSDID("$FreeBSD$"); 381590Srgrimes 391590Srgrimes#include <sys/types.h> 401590Srgrimes 4127314Scharnier#include <errno.h> 4223693Speter#include <stdio.h> 4327314Scharnier#include <string.h> 4427314Scharnier 4550477Speter#include <db.h> 461590Srgrimes#include "recno.h" 471590Srgrimes 481590Srgrimesstatic int rec_rdelete(BTREE *, recno_t); 4923693Speter 5023693Speter/* 5127314Scharnier * __REC_DELETE -- Delete the item(s) referenced by a key. 5223693Speter * 531590Srgrimes * Parameters: 541590Srgrimes * dbp: pointer to access method 5523693Speter * key: key to delete 561590Srgrimes * flags: R_CURSOR if deleting what the cursor references 571590Srgrimes * 581590Srgrimes * Returns: 591590Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 601590Srgrimes */ 611590Srgrimesint 621590Srgrimes__rec_delete(const DB *dbp, const DBT *key, u_int flags) 631590Srgrimes{ 6424665Salex BTREE *t; 651590Srgrimes recno_t nrec; 661590Srgrimes int status; 671590Srgrimes 681590Srgrimes t = dbp->internal; 691590Srgrimes 701590Srgrimes /* Toss any page pinned across calls. */ 711590Srgrimes if (t->bt_pinned != NULL) { 721590Srgrimes mpool_put(t->bt_mp, t->bt_pinned, 0); 731590Srgrimes t->bt_pinned = NULL; 741590Srgrimes } 7585859Salfred 761590Srgrimes switch(flags) { 771590Srgrimes case 0: 781590Srgrimes if ((nrec = *(recno_t *)key->data) == 0) 7924665Salex goto einval; 801590Srgrimes if (nrec > t->bt_nrecs) 8124665Salex return (RET_SPECIAL); 8224665Salex --nrec; 8324665Salex status = rec_rdelete(t, nrec); 8427314Scharnier break; 8524665Salex case R_CURSOR: 861590Srgrimes if (!F_ISSET(&t->bt_cursor, CURS_INIT)) 871590Srgrimes goto einval; 881590Srgrimes if (t->bt_nrecs == 0) 8927314Scharnier return (RET_SPECIAL); 901590Srgrimes status = rec_rdelete(t, t->bt_cursor.rcursor - 1); 911590Srgrimes if (status == RET_SUCCESS) 921590Srgrimes --t->bt_cursor.rcursor; 931590Srgrimes break; 941590Srgrimes default: 951590Srgrimeseinval: errno = EINVAL; 961590Srgrimes return (RET_ERROR); 971590Srgrimes } 9824665Salex 9927314Scharnier if (status == RET_SUCCESS) 10024665Salex F_SET(t, B_MODIFIED | R_MODIFIED); 10124665Salex return (status); 10224665Salex} 1031590Srgrimes 1041590Srgrimes/* 10527314Scharnier * REC_RDELETE -- Delete the data matching the specified key. 10627328Scharnier * 1071590Srgrimes * Parameters: 1081590Srgrimes * tree: tree 1091590Srgrimes * nrec: record to delete 1101590Srgrimes * 1111590Srgrimes * Returns: 1121590Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 1131590Srgrimes */ 11424665Salexstatic int 11524665Salexrec_rdelete(BTREE *t, recno_t nrec) 11624665Salex{ 11724665Salex EPG *e; 1181590Srgrimes PAGE *h; 1191590Srgrimes int status; 12085859Salfred 12124665Salex /* Find the record; __rec_search pins the page. */ 1221590Srgrimes if ((e = __rec_search(t, nrec, SDELETE)) == NULL) 12324665Salex return (RET_ERROR); 12424665Salex 1251590Srgrimes /* Delete the record. */ 1261590Srgrimes h = e->page; 1271590Srgrimes status = __rec_dleaf(t, h, e->index); 1281590Srgrimes if (status != RET_SUCCESS) { 1291590Srgrimes mpool_put(t->bt_mp, h, 0); 1301590Srgrimes return (status); 1311590Srgrimes } 1321590Srgrimes mpool_put(t->bt_mp, h, MPOOL_DIRTY); 13385861Salfred return (RET_SUCCESS); 13485861Salfred} 1351590Srgrimes 13685861Salfred/* 13785861Salfred * __REC_DLEAF -- Delete a single record from a recno leaf page. 13885861Salfred * 13985861Salfred * Parameters: 14085861Salfred * t: tree 14185861Salfred * idx: index on current page to delete 1421590Srgrimes * 1431590Srgrimes * Returns: 1441590Srgrimes * RET_SUCCESS, RET_ERROR. 14524665Salex */ 14685859Salfredint 14785859Salfred__rec_dleaf(BTREE *t, PAGE *h, u_int32_t idx) 14824665Salex{ 14924665Salex RLEAF *rl; 15024665Salex indx_t *ip, cnt, offset; 15124665Salex u_int32_t nbytes; 15224665Salex char *from; 15324665Salex void *to; 15424665Salex 15524665Salex /* 15624665Salex * Delete a record from a recno leaf page. Internal records are never 15724665Salex * deleted from internal pages, regardless of the records that caused 15840114Sdes * them to be added being deleted. Pages made empty by deletion are 15924665Salex * not reclaimed. They are, however, made available for reuse. 16024665Salex * 16127314Scharnier * Pack the remaining entries at the end of the page, shift the indices 16224665Salex * down, overwriting the deleted record and its index. If the record 16324665Salex * uses overflow pages, make them available for reuse. 16424665Salex */ 16524665Salex to = rl = GETRLEAF(h, idx); 16624665Salex if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR) 1671590Srgrimes return (RET_ERROR); 1681590Srgrimes nbytes = NRLEAF(rl); 1691590Srgrimes 1701590Srgrimes /* 1711590Srgrimes * Compress the key/data pairs. Compress and adjust the [BR]LEAF 17224665Salex * offsets. Reset the headers. 1731590Srgrimes */ 1741590Srgrimes from = (char *)h + h->upper; 1751590Srgrimes memmove(from + nbytes, from, (char *)to - from); 1761590Srgrimes h->upper += nbytes; 17727314Scharnier 1781590Srgrimes offset = h->linp[idx]; 1791590Srgrimes for (cnt = &h->linp[idx] - (ip = &h->linp[0]); cnt--; ++ip) 1801590Srgrimes if (ip[0] < offset) 1811590Srgrimes ip[0] += nbytes; 1821590Srgrimes for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip) 1831590Srgrimes ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; 1841590Srgrimes h->lower -= sizeof(indx_t); 1851590Srgrimes --t->bt_nrecs; 1861590Srgrimes return (RET_SUCCESS); 1871590Srgrimes} 18885859Salfred