1 /*- 2 * Copyright (c) 1990 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Mike Olson. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)bt_delete.c 5.2 (Berkeley) 02/22/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 #include <db.h> 17 #include <errno.h> 18 #include <string.h> 19 #include "btree.h" 20 21 /* 22 * _BT_CRSRDEL -- Delete the item pointed to by the cursor. 23 * 24 * This routine deletes the item most recently returned by a scan 25 * through the tree. Since it only makes sense to delete the current 26 * record once, we make sure that we don't try to delete twice without 27 * advancing the scan. 28 * 29 * Parameters: 30 * t -- tree in which to do deletion 31 * 32 * Returns: 33 * RET_SUCCESS, RET_ERROR. 34 * 35 * Side Effects: 36 * The call to _bt_delone marks the cursor, so we can tell that 37 * the current record has been deleted. 38 */ 39 40 int 41 _bt_crsrdel(t) 42 BTREE_P t; 43 { 44 CURSOR *c; 45 46 c = &(t->bt_cursor); 47 48 /* a cursor must exist, and can't have deleted the current key yet */ 49 if (!(t->bt_flags & BTF_SEQINIT) || (c->c_flags & CRSR_BEFORE)) { 50 errno = EINVAL; 51 return (RET_ERROR); 52 } 53 54 if (_bt_getpage(t, c->c_pgno) == RET_ERROR) 55 return (RET_ERROR); 56 57 if (c->c_index >= NEXTINDEX(t->bt_curpage)) { 58 errno = EINVAL; 59 return (RET_ERROR); 60 } 61 62 return (_bt_delone(t, c->c_index)); 63 } 64 65 /* 66 * _BT_DELONE -- Delete a single entry from a btree. 67 * 68 * This routine physically removes a btree entry from a leaf page. 69 * IDATUM items are *never* removed from internal nodes, regardless 70 * of whether the entries that originally caused them to be added 71 * are removed from the tree or not. In addition, pages made empty 72 * by element deletion are not actually reclaimed. They are, 73 * however, made available for reuse. 74 * 75 * To delete an item from a page, we pack the remaining items at 76 * the end of the page, overwriting the deleted item's entry. We 77 * move the line pointers backward on the page, overwriting the 78 * original item's line pointer. This guarantees that the space in 79 * the middle of the page is free -- a property that our insertion 80 * strategy relies on. 81 * 82 * This routine doesn't reclaim pages all of whose entries have 83 * been deleted. These pages are available for reuse, however. 84 * If an item is deleted that was too big to fit on a page, then 85 * the blocks that it occupies are put on a free list for reuse. 86 * 87 * Parameters: 88 * t -- btree from which to delete item 89 * index -- index of entry on current page to delete 90 * 91 * Returns: 92 * RET_SUCCESS, RET_ERROR. 93 * 94 * Side Effects: 95 * Physically changes page layout, adjusts internal page 96 * state to reflect the deletion of the item, and updates 97 * the list of free pages for this tree. 98 */ 99 100 int 101 _bt_delone(t, index) 102 BTREE_P t; 103 index_t index; 104 { 105 char *src, *dest; 106 int nbytes, nmoved; 107 index_t off; 108 index_t top; 109 index_t i; 110 pgno_t chain; 111 BTHEADER *h; 112 CURSOR *c; 113 DATUM *d; 114 115 /* deletion may confuse an active scan. fix it. */ 116 c = &(t->bt_cursor); 117 if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno) 118 if (_bt_fixscan(t, index, (DATUM *) NULL, DELETE) == RET_ERROR) 119 return (RET_ERROR); 120 121 h = t->bt_curpage; 122 off = h->h_linp[index]; 123 d = (DATUM *) GETDATUM(h, index); 124 125 /* if this is a big item, reclaim the space it occupies */ 126 if (d->d_flags & D_BIGKEY) { 127 bcopy(&(d->d_bytes[0]), 128 (char *) &chain, 129 sizeof(chain)); 130 if (_bt_delindir(t, chain) == RET_ERROR) 131 return (RET_ERROR); 132 h = t->bt_curpage; 133 d = (DATUM *) GETDATUM(h, index); 134 } 135 if (d->d_flags & D_BIGDATA) { 136 bcopy(&(d->d_bytes[d->d_ksize]), 137 (char *) &chain, 138 sizeof(chain)); 139 if (_bt_delindir(t, chain) == RET_ERROR) 140 return (RET_ERROR); 141 h = t->bt_curpage; 142 d = (DATUM *) GETDATUM(h, index); 143 } 144 145 /* move the data down on the page */ 146 nbytes = d->d_ksize + d->d_dsize 147 + (sizeof(DATUM) - sizeof(char)); 148 nbytes = LONGALIGN(nbytes); 149 src = ((char *) h) + h->h_upper; 150 dest = src + nbytes; 151 nmoved = (int) (((char *) d) - src); 152 (void) bcopy(src, dest, nmoved); 153 154 /* next move the line pointers up */ 155 src = (char *) &(h->h_linp[index + 1]); 156 dest = (char *) &(h->h_linp[index]); 157 nmoved = (int) (((char *) &(h->h_linp[NEXTINDEX(h)])) - src); 158 (void) bcopy(src, dest, nmoved); 159 160 /* remember that we freed up some space */ 161 h->h_upper += nbytes; 162 h->h_lower -= sizeof(index_t); 163 164 /* adjust offsets in line pointers affected by moving the data */ 165 top = NEXTINDEX(h); 166 for (i = 0; i < top; i++) { 167 if (h->h_linp[i] < off) 168 h->h_linp[i] += nbytes; 169 } 170 171 /* it's gone */ 172 h->h_flags |= F_DIRTY; 173 174 return (RET_SUCCESS); 175 } 176