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[] = "@(#)rec_delete.c 5.1 (Berkeley) 09/04/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 #include <errno.h> 17 #include <db.h> 18 #include <stdio.h> 19 #include <string.h> 20 #include "../btree/btree.h" 21 22 static int rec_rdelete __P((BTREE *, recno_t)); 23 24 /* 25 * __REC_DELETE -- Delete the item(s) referenced by a key. 26 * 27 * Parameters: 28 * dbp: pointer to access method 29 * key: key to delete 30 * flags: R_CURSOR if deleting what the cursor references 31 * 32 * Returns: 33 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 34 */ 35 int 36 __rec_delete(dbp, key, flags) 37 const DB *dbp; 38 const DBT *key; 39 u_int flags; 40 { 41 BTREE *t; 42 recno_t nrec; 43 int status; 44 45 if ((nrec = *(recno_t *)key->data) == 0) { 46 errno = EINVAL; 47 return (RET_ERROR); 48 } 49 --nrec; 50 51 t = dbp->internal; 52 switch(flags) { 53 case 0: 54 status = rec_rdelete(t, nrec); 55 break; 56 case R_CURSOR: 57 status = rec_rdelete(t, t->bt_rcursor); 58 break; 59 default: 60 errno = EINVAL; 61 return (RET_ERROR); 62 } 63 64 if (status == RET_SUCCESS) { 65 --t->bt_nrecs; 66 SET(t, BTF_MODIFIED); 67 } 68 return (status); 69 } 70 71 /* 72 * REC_RDELETE -- Delete the data matching the specified key. 73 * 74 * Parameters: 75 * tree: tree 76 * nrec: record to delete 77 * 78 * Returns: 79 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 80 */ 81 static int 82 rec_rdelete(t, nrec) 83 BTREE *t; 84 recno_t nrec; 85 { 86 EPG *e; 87 EPGNO *parent; 88 PAGE *h; 89 int exact, status; 90 91 /* Find any matching record; __rec_search pins the page. */ 92 e = __rec_search(t, nrec, &exact); 93 if (e == NULL || !exact) { 94 mpool_put(t->bt_mp, e->page, 0); 95 return (e == NULL ? RET_ERROR : RET_SPECIAL); 96 } 97 98 /* Delete the record. */ 99 h = e->page; 100 status = __rec_dleaf(t, h, e->index); 101 if (status == RET_SUCCESS) 102 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 103 else { 104 mpool_put(t->bt_mp, h, 0); 105 return (status); 106 } 107 108 /* Decrement the count on all parent pages. */ 109 while ((parent = BT_POP(t)) != NULL) { 110 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 111 return (RET_ERROR); 112 --GETRINTERNAL(h, parent->index)->nrecs; 113 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 114 } 115 return (RET_SUCCESS); 116 } 117 118 /* 119 * __REC_DLEAF -- Delete a single record from a recno leaf page. 120 * 121 * Parameters: 122 * t: tree 123 * index: index on current page to delete 124 * 125 * Returns: 126 * RET_SUCCESS, RET_ERROR. 127 */ 128 int 129 __rec_dleaf(t, h, index) 130 BTREE *t; 131 PAGE *h; 132 int index; 133 { 134 register RLEAF *rl; 135 register index_t *ip, offset; 136 register size_t nbytes; 137 register int cnt; 138 char *from; 139 void *to; 140 141 /* 142 * Delete a record from a recno leaf page. Internal records are never 143 * deleted from internal pages, regardless of the records that caused 144 * them to be added being deleted. Pages made empty by deletion are 145 * not reclaimed. They are, however, made available for reuse. 146 * 147 * Pack the remaining entries at the end of the page, shift the indices 148 * down, overwriting the deleted record and its index. If the record 149 * uses overflow pages, make them available for reuse. 150 */ 151 to = rl = GETRLEAF(h, index); 152 if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR) 153 return (RET_ERROR); 154 nbytes = NRLEAF(rl); 155 156 /* 157 * Compress the key/data pairs. Compress and adjust the [BR]LEAF 158 * offsets. Reset the headers. 159 */ 160 from = (char *)h + h->upper; 161 bcopy(from, from + nbytes, (char *)to - from); 162 h->upper += nbytes; 163 164 offset = h->linp[index]; 165 for (cnt = &h->linp[index] - (ip = &h->linp[0]); cnt--; ++ip) 166 if (ip[0] < offset) 167 ip[0] += nbytes; 168 for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip) 169 ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; 170 h->lower -= sizeof(index_t); 171 return (RET_SUCCESS); 172 } 173