Context Navigation

source: rtems-libbsd/freebsd/lib/libc/db/btree/bt_delete.c @ 2404264

4.1155-freebsd-126-freebsd-12freebsd-9.3

Last change on this file since 2404264 was 2404264, checked in by Sebastian Huber <sebastian.huber@…>, on 10/30/13 at 12:23:59
Revert superfluous changes
Property mode set to `100644`
File size: 15.8 KB

Line
1	/*-
2	* Copyright (c) 1990, 1993, 1994
3	* The Regents of the University of California. All rights reserved.
4	*
5	* This code is derived from software contributed to Berkeley by
6	* Mike Olson.
7	*
8	* Redistribution and use in source and binary forms, with or without
9	* modification, are permitted provided that the following conditions
10	* are met:
11	* 1. Redistributions of source code must retain the above copyright
12	* notice, this list of conditions and the following disclaimer.
13	* 2. Redistributions in binary form must reproduce the above copyright
14	* notice, this list of conditions and the following disclaimer in the
15	* documentation and/or other materials provided with the distribution.
16	* 4. Neither the name of the University nor the names of its contributors
17	* may be used to endorse or promote products derived from this software
18	* without specific prior written permission.
19	*
20	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30	* SUCH DAMAGE.
31	*/
32
33	#if defined(LIBC_SCCS) && !defined(lint)
34	static char sccsid[] = "@(#)bt_delete.c 8.13 (Berkeley) 7/28/94";
35	#endif /* LIBC_SCCS and not lint */
36	#include <sys/cdefs.h>
37	__FBSDID("$FreeBSD$");
38
39	#include <rtems/bsd/sys/types.h>
40
41	#include <errno.h>
42	#include <stdio.h>
43	#include <string.h>
44
45	#include <db.h>
46	#include "btree.h"
47
48	static int __bt_bdelete(BTREE , const DBT );
49	static int __bt_curdel(BTREE , const DBT , PAGE *, u_int);
50	static int __bt_pdelete(BTREE , PAGE );
51	static int __bt_relink(BTREE , PAGE );
52	static int __bt_stkacq(BTREE , PAGE , CURSOR );
53
54	/*
55	* __bt_delete
56	* Delete the item(s) referenced by a key.
57	*
58	* Return RET_SPECIAL if the key is not found.
59	*/
60	int
61	__bt_delete(const DB dbp, const DBT key, u_int flags)
62	{
63	BTREE *t;
64	CURSOR *c;
65	PAGE *h;
66	int status;
67
68	t = dbp->internal;
69
70	/* Toss any page pinned across calls. */
71	if (t->bt_pinned != NULL) {
72	mpool_put(t->bt_mp, t->bt_pinned, 0);
73	t->bt_pinned = NULL;
74	}
75
76	/* Check for change to a read-only tree. */
77	if (F_ISSET(t, B_RDONLY)) {
78	errno = EPERM;
79	return (RET_ERROR);
80	}
81
82	switch (flags) {
83	case 0:
84	status = __bt_bdelete(t, key);
85	break;
86	case R_CURSOR:
87	/*
88	* If flags is R_CURSOR, delete the cursor. Must already
89	* have started a scan and not have already deleted it.
90	*/
91	c = &t->bt_cursor;
92	if (F_ISSET(c, CURS_INIT)) {
93	if (F_ISSET(c, CURS_ACQUIRE \| CURS_AFTER \| CURS_BEFORE))
94	return (RET_SPECIAL);
95	if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
96	return (RET_ERROR);
97
98	/*
99	* If the page is about to be emptied, we'll need to
100	* delete it, which means we have to acquire a stack.
101	*/
102	if (NEXTINDEX(h) == 1)
103	if (__bt_stkacq(t, &h, &t->bt_cursor))
104	return (RET_ERROR);
105
106	status = __bt_dleaf(t, NULL, h, c->pg.index);
107
108	if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) {
109	if (__bt_pdelete(t, h))
110	return (RET_ERROR);
111	} else
112	mpool_put(t->bt_mp,
113	h, status == RET_SUCCESS ? MPOOL_DIRTY : 0);
114	break;
115	}
116	/* FALLTHROUGH */
117	default:
118	errno = EINVAL;
119	return (RET_ERROR);
120	}
121	if (status == RET_SUCCESS)
122	F_SET(t, B_MODIFIED);
123	return (status);
124	}
125
126	/*
127	* __bt_stkacq --
128	* Acquire a stack so we can delete a cursor entry.
129	*
130	* Parameters:
131	* t: tree
132	* hp: pointer to current, pinned PAGE pointer
133	* c: pointer to the cursor
134	*
135	* Returns:
136	* 0 on success, 1 on failure
137	*/
138	static int
139	__bt_stkacq(BTREE t, PAGE hp, CURSOR c)
140	{
141	BINTERNAL *bi;
142	EPG *e;
143	EPGNO *parent;
144	PAGE *h;
145	indx_t idx;
146	pgno_t pgno;
147	recno_t nextpg, prevpg;
148	int exact, level;
149
150	/*
151	* Find the first occurrence of the key in the tree. Toss the
152	* currently locked page so we don't hit an already-locked page.
153	*/
154	h = *hp;
155	mpool_put(t->bt_mp, h, 0);
156	if ((e = __bt_search(t, &c->key, &exact)) == NULL)
157	return (1);
158	h = e->page;
159
160	/* See if we got it in one shot. */
161	if (h->pgno == c->pg.pgno)
162	goto ret;
163
164	/*
165	* Move right, looking for the page. At each move we have to move
166	* up the stack until we don't have to move to the next page. If
167	* we have to change pages at an internal level, we have to fix the
168	* stack back up.
169	*/
170	while (h->pgno != c->pg.pgno) {
171	if ((nextpg = h->nextpg) == P_INVALID)
172	break;
173	mpool_put(t->bt_mp, h, 0);
174
175	/* Move up the stack. */
176	for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
177	/* Get the parent page. */
178	if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
179	return (1);
180
181	/* Move to the next index. */
182	if (parent->index != NEXTINDEX(h) - 1) {
183	idx = parent->index + 1;
184	BT_PUSH(t, h->pgno, idx);
185	break;
186	}
187	mpool_put(t->bt_mp, h, 0);
188	}
189
190	/* Restore the stack. */
191	while (level--) {
192	/* Push the next level down onto the stack. */
193	bi = GETBINTERNAL(h, idx);
194	pgno = bi->pgno;
195	BT_PUSH(t, pgno, 0);
196
197	/* Lose the currently pinned page. */
198	mpool_put(t->bt_mp, h, 0);
199
200	/* Get the next level down. */
201	if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
202	return (1);
203	idx = 0;
204	}
205	mpool_put(t->bt_mp, h, 0);
206	if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL)
207	return (1);
208	}
209
210	if (h->pgno == c->pg.pgno)
211	goto ret;
212
213	/* Reacquire the original stack. */
214	mpool_put(t->bt_mp, h, 0);
215	if ((e = __bt_search(t, &c->key, &exact)) == NULL)
216	return (1);
217	h = e->page;
218
219	/*
220	* Move left, looking for the page. At each move we have to move
221	* up the stack until we don't have to change pages to move to the
222	* next page. If we have to change pages at an internal level, we
223	* have to fix the stack back up.
224	*/
225	while (h->pgno != c->pg.pgno) {
226	if ((prevpg = h->prevpg) == P_INVALID)
227	break;
228	mpool_put(t->bt_mp, h, 0);
229
230	/* Move up the stack. */
231	for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
232	/* Get the parent page. */
233	if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
234	return (1);
235
236	/* Move to the next index. */
237	if (parent->index != 0) {
238	idx = parent->index - 1;
239	BT_PUSH(t, h->pgno, idx);
240	break;
241	}
242	mpool_put(t->bt_mp, h, 0);
243	}
244
245	/* Restore the stack. */
246	while (level--) {
247	/* Push the next level down onto the stack. */
248	bi = GETBINTERNAL(h, idx);
249	pgno = bi->pgno;
250
251	/* Lose the currently pinned page. */
252	mpool_put(t->bt_mp, h, 0);
253
254	/* Get the next level down. */
255	if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
256	return (1);
257
258	idx = NEXTINDEX(h) - 1;
259	BT_PUSH(t, pgno, idx);
260	}
261	mpool_put(t->bt_mp, h, 0);
262	if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL)
263	return (1);
264	}
265
266
267	ret: mpool_put(t->bt_mp, h, 0);
268	return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL);
269	}
270
271	/*
272	* __bt_bdelete --
273	* Delete all key/data pairs matching the specified key.
274	*
275	* Parameters:
276	* t: tree
277	* key: key to delete
278	*
279	* Returns:
280	* RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
281	*/
282	static int
283	__bt_bdelete(BTREE t, const DBT key)
284	{
285	EPG *e;
286	PAGE *h;
287	int deleted, exact, redo;
288
289	deleted = 0;
290
291	/* Find any matching record; __bt_search pins the page. */
292	loop: if ((e = __bt_search(t, key, &exact)) == NULL)
293	return (deleted ? RET_SUCCESS : RET_ERROR);
294	if (!exact) {
295	mpool_put(t->bt_mp, e->page, 0);
296	return (deleted ? RET_SUCCESS : RET_SPECIAL);
297	}
298
299	/*
300	* Delete forward, then delete backward, from the found key. If
301	* there are duplicates and we reach either side of the page, do
302	* the key search again, so that we get them all.
303	*/
304	redo = 0;
305	h = e->page;
306	do {
307	if (__bt_dleaf(t, key, h, e->index)) {
308	mpool_put(t->bt_mp, h, 0);
309	return (RET_ERROR);
310	}
311	if (F_ISSET(t, B_NODUPS)) {
312	if (NEXTINDEX(h) == 0) {
313	if (__bt_pdelete(t, h))
314	return (RET_ERROR);
315	} else
316	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
317	return (RET_SUCCESS);
318	}
319	deleted = 1;
320	} while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
321
322	/* Check for right-hand edge of the page. */
323	if (e->index == NEXTINDEX(h))
324	redo = 1;
325
326	/* Delete from the key to the beginning of the page. */
327	while (e->index-- > 0) {
328	if (__bt_cmp(t, key, e) != 0)
329	break;
330	if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) {
331	mpool_put(t->bt_mp, h, 0);
332	return (RET_ERROR);
333	}
334	if (e->index == 0)
335	redo = 1;
336	}
337
338	/* Check for an empty page. */
339	if (NEXTINDEX(h) == 0) {
340	if (__bt_pdelete(t, h))
341	return (RET_ERROR);
342	goto loop;
343	}
344
345	/* Put the page. */
346	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
347
348	if (redo)
349	goto loop;
350	return (RET_SUCCESS);
351	}
352
353	/*
354	* __bt_pdelete --
355	* Delete a single page from the tree.
356	*
357	* Parameters:
358	* t: tree
359	* h: leaf page
360	*
361	* Returns:
362	* RET_SUCCESS, RET_ERROR.
363	*
364	* Side-effects:
365	* mpool_put's the page
366	*/
367	static int
368	__bt_pdelete(BTREE t, PAGE h)
369	{
370	BINTERNAL *bi;
371	PAGE *pg;
372	EPGNO *parent;
373	indx_t cnt, idx, *ip, offset;
374	u_int32_t nksize;
375	char *from;
376
377	/*
378	* Walk the parent page stack -- a LIFO stack of the pages that were
379	* traversed when we searched for the page where the delete occurred.
380	* Each stack entry is a page number and a page index offset. The
381	* offset is for the page traversed on the search. We've just deleted
382	* a page, so we have to delete the key from the parent page.
383	*
384	* If the delete from the parent page makes it empty, this process may
385	* continue all the way up the tree. We stop if we reach the root page
386	* (which is never deleted, it's just not worth the effort) or if the
387	* delete does not empty the page.
388	*/
389	while ((parent = BT_POP(t)) != NULL) {
390	/* Get the parent page. */
391	if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
392	return (RET_ERROR);
393
394	idx = parent->index;
395	bi = GETBINTERNAL(pg, idx);
396
397	/* Free any overflow pages. */
398	if (bi->flags & P_BIGKEY &&
399	__ovfl_delete(t, bi->bytes) == RET_ERROR) {
400	mpool_put(t->bt_mp, pg, 0);
401	return (RET_ERROR);
402	}
403
404	/*
405	* Free the parent if it has only the one key and it's not the
406	* root page. If it's the rootpage, turn it back into an empty
407	* leaf page.
408	*/
409	if (NEXTINDEX(pg) == 1) {
410	if (pg->pgno == P_ROOT) {
411	pg->lower = BTDATAOFF;
412	pg->upper = t->bt_psize;
413	pg->flags = P_BLEAF;
414	} else {
415	if (__bt_relink(t, pg) \|\| __bt_free(t, pg))
416	return (RET_ERROR);
417	continue;
418	}
419	} else {
420	/* Pack remaining key items at the end of the page. */
421	nksize = NBINTERNAL(bi->ksize);
422	from = (char *)pg + pg->upper;
423	memmove(from + nksize, from, (char *)bi - from);
424	pg->upper += nksize;
425
426	/* Adjust indices' offsets, shift the indices down. */
427	offset = pg->linp[idx];
428	for (cnt = idx, ip = &pg->linp[0]; cnt--; ++ip)
429	if (ip[0] < offset)
430	ip[0] += nksize;
431	for (cnt = NEXTINDEX(pg) - idx; --cnt; ++ip)
432	ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1];
433	pg->lower -= sizeof(indx_t);
434	}
435
436	mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
437	break;
438	}
439
440	/* Free the leaf page, as long as it wasn't the root. */
441	if (h->pgno == P_ROOT) {
442	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
443	return (RET_SUCCESS);
444	}
445	return (__bt_relink(t, h) \|\| __bt_free(t, h));
446	}
447
448	/*
449	* __bt_dleaf --
450	* Delete a single record from a leaf page.
451	*
452	* Parameters:
453	* t: tree
454	* key: referenced key
455	* h: page
456	* idx: index on page to delete
457	*
458	* Returns:
459	* RET_SUCCESS, RET_ERROR.
460	*/
461	int
462	__bt_dleaf(BTREE t, const DBT key, PAGE *h, u_int idx)
463	{
464	BLEAF *bl;
465	indx_t cnt, *ip, offset;
466	u_int32_t nbytes;
467	void *to;
468	char *from;
469
470	/* If this record is referenced by the cursor, delete the cursor. */
471	if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
472	!F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
473	t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == idx &&
474	__bt_curdel(t, key, h, idx))
475	return (RET_ERROR);
476
477	/* If the entry uses overflow pages, make them available for reuse. */
478	to = bl = GETBLEAF(h, idx);
479	if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
480	return (RET_ERROR);
481	if (bl->flags & P_BIGDATA &&
482	__ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
483	return (RET_ERROR);
484
485	/* Pack the remaining key/data items at the end of the page. */
486	nbytes = NBLEAF(bl);
487	from = (char *)h + h->upper;
488	memmove(from + nbytes, from, (char *)to - from);
489	h->upper += nbytes;
490
491	/* Adjust the indices' offsets, shift the indices down. */
492	offset = h->linp[idx];
493	for (cnt = idx, ip = &h->linp[0]; cnt--; ++ip)
494	if (ip[0] < offset)
495	ip[0] += nbytes;
496	for (cnt = NEXTINDEX(h) - idx; --cnt; ++ip)
497	ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
498	h->lower -= sizeof(indx_t);
499
500	/* If the cursor is on this page, adjust it as necessary. */
501	if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
502	!F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
503	t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > idx)
504	--t->bt_cursor.pg.index;
505
506	return (RET_SUCCESS);
507	}
508
509	/*
510	* __bt_curdel --
511	* Delete the cursor.
512	*
513	* Parameters:
514	* t: tree
515	* key: referenced key (or NULL)
516	* h: page
517	* idx: index on page to delete
518	*
519	* Returns:
520	* RET_SUCCESS, RET_ERROR.
521	*/
522	static int
523	__bt_curdel(BTREE t, const DBT key, PAGE *h, u_int idx)
524	{
525	CURSOR *c;
526	EPG e;
527	PAGE *pg;
528	int curcopy, status;
529
530	/*
531	* If there are duplicates, move forward or backward to one.
532	* Otherwise, copy the key into the cursor area.
533	*/
534	c = &t->bt_cursor;
535	F_CLR(c, CURS_AFTER \| CURS_BEFORE \| CURS_ACQUIRE);
536
537	curcopy = 0;
538	if (!F_ISSET(t, B_NODUPS)) {
539	/*
540	* We're going to have to do comparisons. If we weren't
541	* provided a copy of the key, i.e. the user is deleting
542	* the current cursor position, get one.
543	*/
544	if (key == NULL) {
545	e.page = h;
546	e.index = idx;
547	if ((status = __bt_ret(t, &e,
548	&c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS)
549	return (status);
550	curcopy = 1;
551	key = &c->key;
552	}
553	/* Check previous key, if not at the beginning of the page. */
554	if (idx > 0) {
555	e.page = h;
556	e.index = idx - 1;
557	if (__bt_cmp(t, key, &e) == 0) {
558	F_SET(c, CURS_BEFORE);
559	goto dup2;
560	}
561	}
562	/* Check next key, if not at the end of the page. */
563	if (idx < NEXTINDEX(h) - 1) {
564	e.page = h;
565	e.index = idx + 1;
566	if (__bt_cmp(t, key, &e) == 0) {
567	F_SET(c, CURS_AFTER);
568	goto dup2;
569	}
570	}
571	/* Check previous key if at the beginning of the page. */
572	if (idx == 0 && h->prevpg != P_INVALID) {
573	if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
574	return (RET_ERROR);
575	e.page = pg;
576	e.index = NEXTINDEX(pg) - 1;
577	if (__bt_cmp(t, key, &e) == 0) {
578	F_SET(c, CURS_BEFORE);
579	goto dup1;
580	}
581	mpool_put(t->bt_mp, pg, 0);
582	}
583	/* Check next key if at the end of the page. */
584	if (idx == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) {
585	if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
586	return (RET_ERROR);
587	e.page = pg;
588	e.index = 0;
589	if (__bt_cmp(t, key, &e) == 0) {
590	F_SET(c, CURS_AFTER);
591	dup1: mpool_put(t->bt_mp, pg, 0);
592	dup2: c->pg.pgno = e.page->pgno;
593	c->pg.index = e.index;
594	return (RET_SUCCESS);
595	}
596	mpool_put(t->bt_mp, pg, 0);
597	}
598	}
599	e.page = h;
600	e.index = idx;
601	if (curcopy \|\| (status =
602	__bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) {
603	F_SET(c, CURS_ACQUIRE);
604	return (RET_SUCCESS);
605	}
606	return (status);
607	}
608
609	/*
610	* __bt_relink --
611	* Link around a deleted page.
612	*
613	* Parameters:
614	* t: tree
615	* h: page to be deleted
616	*/
617	static int
618	__bt_relink(BTREE t, PAGE h)
619	{
620	PAGE *pg;
621
622	if (h->nextpg != P_INVALID) {
623	if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
624	return (RET_ERROR);
625	pg->prevpg = h->prevpg;
626	mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
627	}
628	if (h->prevpg != P_INVALID) {
629	if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
630	return (RET_ERROR);
631	pg->nextpg = h->nextpg;
632	mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
633	}
634	return (0);
635	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats: