2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
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)
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
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
23 /*%% (c) Copyright 1993, 1994 Hewlett-Packard Company */
24 /*%% (c) Copyright 1993, 1994 International Business Machines Corp. */
25 /*%% (c) Copyright 1993, 1994 Sun Microsystems, Inc. */
26 /*%% (c) Copyright 1993, 1994 Novell, Inc. */
27 /*%% $XConsortium: isbtree3.c /main/3 1995/10/23 11:36:12 rswiston $ */
30 * Copyright (c) 1988 by Sun Microsystems, Inc.
37 * B-tree operations: REMOVE
41 #include "isam_impl.h"
43 extern int _iskeycmp();
45 static void remove_entry(Btree *, char *, int);
46 static void move_from_right(Btree *, char *, char *, int);
47 static void move_from_left(Btree *, char *, char *, int);
49 /* _isbtree_remove() - Remove entry from B-tree ----------------------------*/
52 _isbtree_remove(Btree *btree)
54 struct keydesc2 *pkeydesc2 = btree->keydesc2;
55 int nkeys; /* Number of keys in the page */
57 char *pkp, *pkp2, *pkp3;
58 struct bufhdr *kp2bhdr;
64 /* Set comparison function. */
65 _iskeycmp_set(pkeydesc2, pkeydesc2->k2_nparts+1); /* +1 for recno field */
69 * Remove he current entry from leaf.
70 * If it was leftmost entry, propagate new leftmost to upper levels.
71 * If block has less than capac/2 + 1 entries, either move some entries
72 * from next left or right block, or merge with next left or right
76 for (i = btree->depth - 1; i >= 0; i--) {
78 /* Re-fix the current page for update. */
79 btree->bufhdr[i] = _isdisk_refix(btree->bufhdr[i], ISFIXWRITE);
80 pkp = btree->bufhdr[i]->isb_buffer;
82 level = ldshort(pkp + BT_LEVEL_OFF);
83 capac = ldshort(pkp + BT_CAPAC_OFF); /* Block capacity */
84 nkeys = ldshort(pkp + BT_NKEYS_OFF); /* Number of keys in block */
86 halfcapac = (capac+1) >> 1; /* same as capac/2 + 1 */
88 assert(level + i + 1 == btree->depth);
89 assert(i == 0 || nkeys >= halfcapac);
91 /* Remove entry from this page. */
92 remove_entry(btree, pkp, btree->curpos[i]);
95 /* Must propagate new leftmost key up. */
96 if (btree->curpos[i] == 0 && i > 0)
99 if (nkeys >= halfcapac || i == 0) {
102 * Page is still balanced. No changes are necessary.
103 * Also, no chages are needed if this is root block.
110 if(btree->curpos[i-1] > 0) {
113 * Block pkp is not the leftmost descendent of its parent.
114 * Either merge with left brother, or move a few entries
118 pkp3 = btree->bufhdr[i-1]->isb_buffer;
120 blkno2 = ldblkno(pkp3 + ISPAGESIZE -
121 (btree->curpos[i-1]) * BLKNOSIZE);
123 /* Fix the left brother. */
124 kp2bhdr = _isdisk_fix(btree->fcb, btree->fcb->indfd,
126 pkp2 = kp2bhdr->isb_buffer;
128 if (ldshort(pkp2 + BT_NKEYS_OFF) + nkeys > capac) {
131 * Current page cannot be merged with the left brother.
132 * Move some entries from the left brother into current.
135 move_keys = (ldshort(pkp2 + BT_NKEYS_OFF) - halfcapac +1)/2;
136 assert(move_keys > 0);
138 move_from_left (btree, pkp2, pkp, move_keys);
140 leftkey_up(btree, i); /* Propagate new leftmost key */
142 break; /* From main loop */
147 * Current page and left brotehr will be merged.
148 * Move all entries from current into left, and free
152 /* Move all entries from current into left. */
153 move_from_right(btree, pkp2, pkp, nkeys);
155 /* Free current page. */
156 _isindfreel_free(btree->fcb, btree->bufhdr[i]->isb_blkno);
158 btree->bufhdr[i] = kp2bhdr; /* Update search path */
160 /* The loop must iterate to delete entry in parent block. */
166 * Block pkp is the leftmost descendent of its parent.
167 * Either merge with right brother, or move a few entries
171 pkp3 = btree->bufhdr[i-1]->isb_buffer;
173 blkno2 = ldblkno(pkp3 + ISPAGESIZE -
174 (btree->curpos[i-1] + 2) * BLKNOSIZE);
176 /* Fix the right brother. */
177 kp2bhdr = _isdisk_fix(btree->fcb, btree->fcb->indfd,
179 pkp2 = kp2bhdr->isb_buffer;
181 if (ldshort(pkp2 + BT_NKEYS_OFF) + nkeys > capac) {
184 * Current page cannot be merged with the right brother.
185 * Move some entries from the right brother into current.
188 move_keys = (ldshort(pkp2 + BT_NKEYS_OFF) - halfcapac +1)/2;
189 assert(move_keys > 0);
191 move_from_right(btree, pkp, pkp2, move_keys);
193 /* Update search path to go through right brother. */
194 btree->curpos[i-1]++;
195 btree->bufhdr[i] = kp2bhdr;
196 btree->curpos[i] = 0;
197 leftkey_up(btree, i); /* Propagate new leftmost key */
199 break; /* From main loop */
204 * Current page and right brother will be merged.
205 * Move all entries from right into current, and free
209 /* Move all entries from right brother into current. */
210 move_from_right(btree, pkp, pkp2, ldshort(pkp2 + BT_NKEYS_OFF));
212 /* Free right brother page. */
213 _isindfreel_free(btree->fcb, kp2bhdr->isb_blkno);
215 /* Update search path to point at right brother*/
216 btree->curpos[i-1]++;
217 /* The loop must iterate to delete entry in parent block. */
222 } /* end of main loop */
224 if (btree->depth > 1) {
225 pkp = btree->bufhdr[0]->isb_buffer;
227 if (ldshort(pkp + BT_NKEYS_OFF) < 2) {
230 * Root now has only 1 entry and it is not the sole block.
231 * Replace root with its only descendant, don't change
234 pkp2 = btree->bufhdr[1]->isb_buffer;
235 memcpy( pkp,pkp2, ISPAGESIZE);
238 _isindfreel_free(btree->fcb, btree->bufhdr[1]->isb_blkno);
244 /*--------- remove supporting local functions -------------------------------*/
247 remove_entry(Btree *btree, char *pkp, int pos)
249 int keylength = btree->keydesc2->k2_len;
250 int nkeys = ldshort(pkp + BT_NKEYS_OFF);
251 int level = ldshort(pkp + BT_LEVEL_OFF);
254 assert(pos >= 0 && pos < nkeys);
256 /* Shift nkeys - pos - 1 entries to the left. */
257 memcpy(pkp + BT_KEYS_OFF + pos * keylength,
258 pkp + BT_KEYS_OFF + (pos + 1) * keylength,
259 (nkeys - pos - 1) * keylength);
261 /* For non-leaf nodes, remove block number from table of down pointers. */
264 memmove(pkp + ISPAGESIZE - (nkeys - 1) * BLKNOSIZE,
265 pkp + ISPAGESIZE - nkeys * BLKNOSIZE,
266 (nkeys - pos - 1) * BLKNOSIZE);
269 stshort((short) (nkeys - 1), pkp + BT_NKEYS_OFF);
273 move_from_right(Btree *btree, char *l, char *r, int move_keys)
275 int keylength = btree->keydesc2->k2_len;
276 int lnkeys = ldshort(l + BT_NKEYS_OFF);
277 int rnkeys = ldshort(r + BT_NKEYS_OFF);
278 int level = ldshort(r + BT_LEVEL_OFF);
280 /* Move move_keys from l into r block. */
281 memcpy( l + BT_KEYS_OFF + lnkeys * keylength,r + BT_KEYS_OFF,
282 move_keys * keylength);
284 /* Move remaining entries in r to the left side. */
285 memcpy( r + BT_KEYS_OFF,r + BT_KEYS_OFF + move_keys * keylength,
286 (rnkeys - move_keys) * keylength);
288 /* If non-leaf, move the pointers stored at the end of block. */
290 memcpy(l + ISPAGESIZE - (lnkeys + move_keys) * BLKNOSIZE,
291 r + ISPAGESIZE - move_keys * BLKNOSIZE,
292 move_keys * BLKNOSIZE);
294 memmove(r + ISPAGESIZE - (rnkeys - move_keys) * BLKNOSIZE,
295 r + ISPAGESIZE - rnkeys * BLKNOSIZE,
296 (rnkeys - move_keys) * BLKNOSIZE);
302 stshort((short) lnkeys, l + BT_NKEYS_OFF);
303 stshort((short) rnkeys, r + BT_NKEYS_OFF);
307 move_from_left(Btree *btree, char *l, char *r, int move_keys)
309 int keylength = btree->keydesc2->k2_len;
310 int lnkeys = ldshort(l + BT_NKEYS_OFF);
311 int rnkeys = ldshort(r + BT_NKEYS_OFF);
312 int level = ldshort(r + BT_LEVEL_OFF);
314 /* Move entries in r to the right side to create space for move_keys. */
315 memmove( r + BT_KEYS_OFF + move_keys * keylength,r + BT_KEYS_OFF,
318 /* Move move_keys from l into r block. */
319 memcpy( r + BT_KEYS_OFF,l + BT_KEYS_OFF + (lnkeys - move_keys) * keylength,
320 move_keys * keylength);
322 /* If non-leaf, move the pointers stored at the end of block. */
325 memcpy(r + ISPAGESIZE - (rnkeys + move_keys) * BLKNOSIZE,
326 r + ISPAGESIZE - rnkeys * BLKNOSIZE,
329 memcpy(r + ISPAGESIZE - move_keys * BLKNOSIZE,
330 l + ISPAGESIZE - lnkeys * BLKNOSIZE,
331 move_keys * BLKNOSIZE);
337 stshort((short) lnkeys, l + BT_NKEYS_OFF);
338 stshort((short) rnkeys, r + BT_NKEYS_OFF);