bt_delete.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340
  1. /*
  2. * CDE - Common Desktop Environment
  3. *
  4. * Copyright (c) 1993-2012, The Open Group. All rights reserved.
  5. *
  6. * These libraries and programs are free software; you can
  7. * redistribute them and/or modify them under the terms of the GNU
  8. * Lesser General Public License as published by the Free Software
  9. * Foundation; either version 2 of the License, or (at your option)
  10. * any later version.
  11. *
  12. * These libraries and programs are distributed in the hope that
  13. * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14. * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15. * PURPOSE. See the GNU Lesser General Public License for more
  16. * details.
  17. *
  18. * You should have received a copy of the GNU Lesser General Public
  19. * License along with these libraries and programs; if not, write
  20. * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21. * Floor, Boston, MA 02110-1301 USA
  22. */
  23. /* $XConsortium: bt_delete.c /main/3 1996/06/11 17:12:29 cde-hal $ */
  24. /*-
  25. * Copyright (c) 1990, 1993
  26. * The Regents of the University of California. All rights reserved.
  27. *
  28. * This code is derived from software contributed to Berkeley by
  29. * Mike Olson.
  30. *
  31. * Redistribution and use in source and binary forms, with or without
  32. * modification, are permitted provided that the following conditions
  33. * are met:
  34. * 1. Redistributions of source code must retain the above copyright
  35. * notice, this list of conditions and the following disclaimer.
  36. * 2. Redistributions in binary form must reproduce the above copyright
  37. * notice, this list of conditions and the following disclaimer in the
  38. * documentation and/or other materials provided with the distribution.
  39. * 3. All advertising materials mentioning features or use of this software
  40. * must display the following acknowledgement:
  41. * This product includes software developed by the University of
  42. * California, Berkeley and its contributors.
  43. * 4. Neither the name of the University nor the names of its contributors
  44. * may be used to endorse or promote products derived from this software
  45. * without specific prior written permission.
  46. *
  47. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  48. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  49. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  50. * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  51. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  52. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  53. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  54. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  55. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  56. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  57. * SUCH DAMAGE.
  58. */
  59. #if defined(LIBC_SCCS) && !defined(lint)
  60. static char sccsid[] = "@(#)bt_delete.c 8.2 (Berkeley) 9/7/93";
  61. #endif /* LIBC_SCCS and not lint */
  62. #include <sys/types.h>
  63. #include <errno.h>
  64. #include <stdio.h>
  65. #include <string.h>
  66. #include <db.h>
  67. #include "btree.h"
  68. static int bt_bdelete __P((BTREE *, const DBT *));
  69. /*
  70. * __BT_DELETE -- Delete the item(s) referenced by a key.
  71. *
  72. * Parameters:
  73. * dbp: pointer to access method
  74. * key: key to delete
  75. * flags: R_CURSOR if deleting what the cursor references
  76. *
  77. * Returns:
  78. * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
  79. */
  80. int
  81. __bt_delete(const DB *dbp, const DBT *key, u_int flags)
  82. {
  83. BTREE *t;
  84. int status;
  85. t = dbp->internal;
  86. /* Toss any page pinned across calls. */
  87. if (t->bt_pinned != NULL) {
  88. mpool_put(t->bt_mp, t->bt_pinned, 0);
  89. t->bt_pinned = NULL;
  90. }
  91. if (ISSET(t, B_RDONLY)) {
  92. errno = EPERM;
  93. return (RET_ERROR);
  94. }
  95. switch(flags) {
  96. case 0:
  97. status = bt_bdelete(t, key);
  98. break;
  99. case R_CURSOR:
  100. /*
  101. * If flags is R_CURSOR, delete the cursor; must already have
  102. * started a scan and not have already deleted the record. For
  103. * the delete cursor bit to have been set requires that the
  104. * scan be initialized, so no reason to check.
  105. */
  106. if (!ISSET(t, B_SEQINIT))
  107. goto einval;
  108. status = ISSET(t, B_DELCRSR) ?
  109. RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor);
  110. break;
  111. default:
  112. einval: errno = EINVAL;
  113. return (RET_ERROR);
  114. }
  115. if (status == RET_SUCCESS)
  116. SET(t, B_MODIFIED);
  117. return (status);
  118. }
  119. /*
  120. * BT_BDELETE -- Delete all key/data pairs matching the specified key.
  121. *
  122. * Parameters:
  123. * tree: tree
  124. * key: key to delete
  125. *
  126. * Returns:
  127. * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
  128. */
  129. static int
  130. bt_bdelete(BTREE *t, const DBT *key)
  131. {
  132. EPG *e, save;
  133. PAGE *h;
  134. pgno_t cpgno, pg;
  135. indx_t cindex;
  136. int deleted, dirty1, dirty2, exact;
  137. /* Find any matching record; __bt_search pins the page. */
  138. if ((e = __bt_search(t, key, &exact)) == NULL)
  139. return (RET_ERROR);
  140. if (!exact) {
  141. mpool_put(t->bt_mp, e->page, 0);
  142. return (RET_SPECIAL);
  143. }
  144. /*
  145. * Delete forward, then delete backward, from the found key. The
  146. * ordering is so that the deletions don't mess up the page refs.
  147. * The first loop deletes the key from the original page, the second
  148. * unpins the original page. In the first loop, dirty1 is set if
  149. * the original page is modified, and dirty2 is set if any subsequent
  150. * pages are modified. In the second loop, dirty1 starts off set if
  151. * the original page has been modified, and is set if any subsequent
  152. * pages are modified.
  153. *
  154. * If find the key referenced by the cursor, don't delete it, just
  155. * flag it for future deletion. The cursor page number is P_INVALID
  156. * unless the sequential scan is initialized, so no reason to check.
  157. * A special case is when the already deleted cursor record was the
  158. * only record found. If so, then the delete opertion fails as no
  159. * records were deleted.
  160. *
  161. * Cycle in place in the current page until the current record doesn't
  162. * match the key or the page is empty. If the latter, walk forward,
  163. * skipping empty pages and repeating until a record doesn't match
  164. * the key or the end of the tree is reached.
  165. */
  166. cpgno = t->bt_bcursor.pgno;
  167. cindex = t->bt_bcursor.index;
  168. save = *e;
  169. dirty1 = 0;
  170. for (h = e->page, deleted = 0;;) {
  171. dirty2 = 0;
  172. do {
  173. if (h->pgno == cpgno && e->index == cindex) {
  174. if (!ISSET(t, B_DELCRSR)) {
  175. SET(t, B_DELCRSR);
  176. deleted = 1;
  177. }
  178. ++e->index;
  179. } else {
  180. if (__bt_dleaf(t, h, e->index)) {
  181. if (h->pgno != save.page->pgno)
  182. mpool_put(t->bt_mp, h, dirty2);
  183. mpool_put(t->bt_mp, save.page, dirty1);
  184. return (RET_ERROR);
  185. }
  186. if (h->pgno == save.page->pgno)
  187. dirty1 = MPOOL_DIRTY;
  188. else
  189. dirty2 = MPOOL_DIRTY;
  190. deleted = 1;
  191. }
  192. } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
  193. /*
  194. * Quit if didn't find a match, no next page, or first key on
  195. * the next page doesn't match. Don't unpin the original page
  196. * unless an error occurs.
  197. */
  198. if (e->index < NEXTINDEX(h))
  199. break;
  200. for (;;) {
  201. if ((pg = h->nextpg) == P_INVALID)
  202. goto done1;
  203. if (h->pgno != save.page->pgno)
  204. mpool_put(t->bt_mp, h, dirty2);
  205. if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) {
  206. mpool_put(t->bt_mp, save.page, dirty1);
  207. return (RET_ERROR);
  208. }
  209. if (NEXTINDEX(h) != 0) {
  210. e->page = h;
  211. e->index = 0;
  212. break;
  213. }
  214. }
  215. if (__bt_cmp(t, key, e) != 0)
  216. break;
  217. }
  218. /*
  219. * Reach here with the original page and the last page referenced
  220. * pinned (they may be the same). Release it if not the original.
  221. */
  222. done1: if (h->pgno != save.page->pgno)
  223. mpool_put(t->bt_mp, h, dirty2);
  224. /*
  225. * Walk backwards from the record previous to the record returned by
  226. * __bt_search, skipping empty pages, until a record doesn't match
  227. * the key or reach the beginning of the tree.
  228. */
  229. *e = save;
  230. for (;;) {
  231. if (e->index)
  232. --e->index;
  233. for (h = e->page; e->index; --e->index) {
  234. if (__bt_cmp(t, key, e) != 0)
  235. goto done2;
  236. if (h->pgno == cpgno && e->index == cindex) {
  237. if (!ISSET(t, B_DELCRSR)) {
  238. SET(t, B_DELCRSR);
  239. deleted = 1;
  240. }
  241. } else {
  242. if (__bt_dleaf(t, h, e->index) == RET_ERROR) {
  243. mpool_put(t->bt_mp, h, dirty1);
  244. return (RET_ERROR);
  245. }
  246. if (h->pgno == save.page->pgno)
  247. dirty1 = MPOOL_DIRTY;
  248. deleted = 1;
  249. }
  250. }
  251. if ((pg = h->prevpg) == P_INVALID)
  252. goto done2;
  253. mpool_put(t->bt_mp, h, dirty1);
  254. dirty1 = 0;
  255. if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL)
  256. return (RET_ERROR);
  257. e->index = NEXTINDEX(e->page);
  258. }
  259. /*
  260. * Reach here with the last page that was looked at pinned. Release
  261. * it.
  262. */
  263. done2: mpool_put(t->bt_mp, h, dirty1);
  264. return (deleted ? RET_SUCCESS : RET_SPECIAL);
  265. }
  266. /*
  267. * __BT_DLEAF -- Delete a single record from a leaf page.
  268. *
  269. * Parameters:
  270. * t: tree
  271. * index: index on current page to delete
  272. *
  273. * Returns:
  274. * RET_SUCCESS, RET_ERROR.
  275. */
  276. int
  277. __bt_dleaf(BTREE *t, PAGE *h, int index)
  278. {
  279. BLEAF *bl;
  280. indx_t *ip, offset;
  281. size_t nbytes;
  282. int cnt;
  283. char *from;
  284. void *to;
  285. /*
  286. * Delete a record from a btree leaf page. Internal records are never
  287. * deleted from internal pages, regardless of the records that caused
  288. * them to be added being deleted. Pages made empty by deletion are
  289. * not reclaimed. They are, however, made available for reuse.
  290. *
  291. * Pack the remaining entries at the end of the page, shift the indices
  292. * down, overwriting the deleted record and its index. If the record
  293. * uses overflow pages, make them available for reuse.
  294. */
  295. to = bl = GETBLEAF(h, index);
  296. if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
  297. return (RET_ERROR);
  298. if (bl->flags & P_BIGDATA &&
  299. __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
  300. return (RET_ERROR);
  301. nbytes = NBLEAF(bl);
  302. /*
  303. * Compress the key/data pairs. Compress and adjust the [BR]LEAF
  304. * offsets. Reset the headers.
  305. */
  306. from = (char *)h + h->upper;
  307. memmove(from + nbytes, from, (char *)to - from);
  308. h->upper += nbytes;
  309. offset = h->linp[index];
  310. for (cnt = index, ip = &h->linp[0]; cnt--; ++ip)
  311. if (ip[0] < offset)
  312. ip[0] += nbytes;
  313. for (cnt = NEXTINDEX(h) - index; --cnt; ++ip)
  314. ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
  315. h->lower -= sizeof(indx_t);
  316. return (RET_SUCCESS);
  317. }