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