]>
Commit | Line | Data |
---|---|---|
71733723 RM |
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 | * 3. All advertising materials mentioning features or use of this software | |
17 | * must display the following acknowledgement: | |
18 | * This product includes software developed by the University of | |
19 | * California, Berkeley and its contributors. | |
20 | * 4. Neither the name of the University nor the names of its contributors | |
21 | * may be used to endorse or promote products derived from this software | |
22 | * without specific prior written permission. | |
23 | * | |
24 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
25 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
26 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
27 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
28 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
29 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
30 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
31 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
32 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
33 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
34 | * SUCH DAMAGE. | |
35 | */ | |
36 | ||
37 | #if defined(LIBC_SCCS) && !defined(lint) | |
38 | static char sccsid[] = "@(#)bt_split.c 8.9 (Berkeley) 7/26/94"; | |
39 | #endif /* LIBC_SCCS and not lint */ | |
40 | ||
41 | #include <sys/types.h> | |
42 | ||
43 | #include <limits.h> | |
44 | #include <stdio.h> | |
45 | #include <stdlib.h> | |
46 | #include <string.h> | |
47 | ||
48 | #include <db.h> | |
49 | #include "btree.h" | |
50 | ||
51 | static int bt_broot __P((BTREE *, PAGE *, PAGE *, PAGE *)); | |
52 | static PAGE *bt_page | |
53 | __P((BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t)); | |
54 | static int bt_preserve __P((BTREE *, pgno_t)); | |
55 | static PAGE *bt_psplit | |
56 | __P((BTREE *, PAGE *, PAGE *, PAGE *, indx_t *, size_t)); | |
57 | static PAGE *bt_root | |
58 | __P((BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t)); | |
59 | static int bt_rroot __P((BTREE *, PAGE *, PAGE *, PAGE *)); | |
60 | static recno_t rec_total __P((PAGE *)); | |
61 | ||
62 | #ifdef STATISTICS | |
63 | u_long bt_rootsplit, bt_split, bt_sortsplit, bt_pfxsaved; | |
64 | #endif | |
65 | ||
66 | /* | |
67 | * __BT_SPLIT -- Split the tree. | |
68 | * | |
69 | * Parameters: | |
70 | * t: tree | |
71 | * sp: page to split | |
72 | * key: key to insert | |
73 | * data: data to insert | |
74 | * flags: BIGKEY/BIGDATA flags | |
75 | * ilen: insert length | |
76 | * skip: index to leave open | |
77 | * | |
78 | * Returns: | |
79 | * RET_ERROR, RET_SUCCESS | |
80 | */ | |
81 | int | |
82 | __bt_split(t, sp, key, data, flags, ilen, argskip) | |
83 | BTREE *t; | |
84 | PAGE *sp; | |
85 | const DBT *key, *data; | |
86 | int flags; | |
87 | size_t ilen; | |
88 | u_int32_t argskip; | |
89 | { | |
90 | BINTERNAL *bi; | |
91 | BLEAF *bl, *tbl; | |
92 | DBT a, b; | |
93 | EPGNO *parent; | |
94 | PAGE *h, *l, *r, *lchild, *rchild; | |
95 | indx_t nxtindex; | |
96 | u_int16_t skip; | |
97 | u_int32_t n, nbytes, nksize; | |
98 | int parentsplit; | |
99 | char *dest; | |
100 | ||
101 | /* | |
102 | * Split the page into two pages, l and r. The split routines return | |
103 | * a pointer to the page into which the key should be inserted and with | |
104 | * skip set to the offset which should be used. Additionally, l and r | |
105 | * are pinned. | |
106 | */ | |
107 | skip = argskip; | |
108 | h = sp->pgno == P_ROOT ? | |
109 | bt_root(t, sp, &l, &r, &skip, ilen) : | |
110 | bt_page(t, sp, &l, &r, &skip, ilen); | |
111 | if (h == NULL) | |
112 | return (RET_ERROR); | |
113 | ||
114 | /* | |
115 | * Insert the new key/data pair into the leaf page. (Key inserts | |
116 | * always cause a leaf page to split first.) | |
117 | */ | |
118 | h->linp[skip] = h->upper -= ilen; | |
119 | dest = (char *)h + h->upper; | |
120 | if (F_ISSET(t, R_RECNO)) | |
121 | WR_RLEAF(dest, data, flags) | |
122 | else | |
123 | WR_BLEAF(dest, key, data, flags) | |
124 | ||
125 | /* If the root page was split, make it look right. */ | |
126 | if (sp->pgno == P_ROOT && | |
127 | (F_ISSET(t, R_RECNO) ? | |
128 | bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR) | |
129 | goto err2; | |
130 | ||
131 | /* | |
132 | * Now we walk the parent page stack -- a LIFO stack of the pages that | |
133 | * were traversed when we searched for the page that split. Each stack | |
134 | * entry is a page number and a page index offset. The offset is for | |
135 | * the page traversed on the search. We've just split a page, so we | |
136 | * have to insert a new key into the parent page. | |
137 | * | |
138 | * If the insert into the parent page causes it to split, may have to | |
139 | * continue splitting all the way up the tree. We stop if the root | |
140 | * splits or the page inserted into didn't have to split to hold the | |
141 | * new key. Some algorithms replace the key for the old page as well | |
142 | * as the new page. We don't, as there's no reason to believe that the | |
143 | * first key on the old page is any better than the key we have, and, | |
144 | * in the case of a key being placed at index 0 causing the split, the | |
145 | * key is unavailable. | |
146 | * | |
147 | * There are a maximum of 5 pages pinned at any time. We keep the left | |
148 | * and right pages pinned while working on the parent. The 5 are the | |
149 | * two children, left parent and right parent (when the parent splits) | |
150 | * and the root page or the overflow key page when calling bt_preserve. | |
151 | * This code must make sure that all pins are released other than the | |
152 | * root page or overflow page which is unlocked elsewhere. | |
153 | */ | |
154 | while ((parent = BT_POP(t)) != NULL) { | |
155 | lchild = l; | |
156 | rchild = r; | |
157 | ||
158 | /* Get the parent page. */ | |
159 | if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) | |
160 | goto err2; | |
161 | ||
162 | /* | |
163 | * The new key goes ONE AFTER the index, because the split | |
164 | * was to the right. | |
165 | */ | |
166 | skip = parent->index + 1; | |
167 | ||
168 | /* | |
169 | * Calculate the space needed on the parent page. | |
170 | * | |
171 | * Prefix trees: space hack when inserting into BINTERNAL | |
172 | * pages. Retain only what's needed to distinguish between | |
173 | * the new entry and the LAST entry on the page to its left. | |
174 | * If the keys compare equal, retain the entire key. Note, | |
175 | * we don't touch overflow keys, and the entire key must be | |
176 | * retained for the next-to-left most key on the leftmost | |
177 | * page of each level, or the search will fail. Applicable | |
178 | * ONLY to internal pages that have leaf pages as children. | |
179 | * Further reduction of the key between pairs of internal | |
180 | * pages loses too much information. | |
181 | */ | |
182 | switch (rchild->flags & P_TYPE) { | |
183 | case P_BINTERNAL: | |
184 | bi = GETBINTERNAL(rchild, 0); | |
185 | nbytes = NBINTERNAL(bi->ksize); | |
186 | break; | |
187 | case P_BLEAF: | |
188 | bl = GETBLEAF(rchild, 0); | |
189 | nbytes = NBINTERNAL(bl->ksize); | |
190 | if (t->bt_pfx && !(bl->flags & P_BIGKEY) && | |
191 | (h->prevpg != P_INVALID || skip > 1)) { | |
192 | tbl = GETBLEAF(lchild, NEXTINDEX(lchild) - 1); | |
193 | a.size = tbl->ksize; | |
194 | a.data = tbl->bytes; | |
195 | b.size = bl->ksize; | |
196 | b.data = bl->bytes; | |
197 | nksize = t->bt_pfx(&a, &b); | |
198 | n = NBINTERNAL(nksize); | |
199 | if (n < nbytes) { | |
200 | #ifdef STATISTICS | |
201 | bt_pfxsaved += nbytes - n; | |
202 | #endif | |
203 | nbytes = n; | |
204 | } else | |
205 | nksize = 0; | |
206 | } else | |
207 | nksize = 0; | |
208 | break; | |
209 | case P_RINTERNAL: | |
210 | case P_RLEAF: | |
211 | nbytes = NRINTERNAL; | |
212 | break; | |
213 | default: | |
214 | abort(); | |
215 | } | |
216 | ||
217 | /* Split the parent page if necessary or shift the indices. */ | |
54d79e99 UD |
218 | if ((u_int32_t) (h->upper - h->lower) |
219 | < nbytes + sizeof(indx_t)) { | |
71733723 RM |
220 | sp = h; |
221 | h = h->pgno == P_ROOT ? | |
222 | bt_root(t, h, &l, &r, &skip, nbytes) : | |
223 | bt_page(t, h, &l, &r, &skip, nbytes); | |
224 | if (h == NULL) | |
225 | goto err1; | |
226 | parentsplit = 1; | |
227 | } else { | |
228 | if (skip < (nxtindex = NEXTINDEX(h))) | |
229 | memmove(h->linp + skip + 1, h->linp + skip, | |
230 | (nxtindex - skip) * sizeof(indx_t)); | |
231 | h->lower += sizeof(indx_t); | |
232 | parentsplit = 0; | |
233 | } | |
234 | ||
235 | /* Insert the key into the parent page. */ | |
236 | switch (rchild->flags & P_TYPE) { | |
237 | case P_BINTERNAL: | |
238 | h->linp[skip] = h->upper -= nbytes; | |
239 | dest = (char *)h + h->linp[skip]; | |
240 | memmove(dest, bi, nbytes); | |
241 | ((BINTERNAL *)dest)->pgno = rchild->pgno; | |
242 | break; | |
243 | case P_BLEAF: | |
244 | h->linp[skip] = h->upper -= nbytes; | |
245 | dest = (char *)h + h->linp[skip]; | |
246 | WR_BINTERNAL(dest, nksize ? nksize : bl->ksize, | |
247 | rchild->pgno, bl->flags & P_BIGKEY); | |
248 | memmove(dest, bl->bytes, nksize ? nksize : bl->ksize); | |
249 | if (bl->flags & P_BIGKEY && | |
250 | bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR) | |
251 | goto err1; | |
252 | break; | |
253 | case P_RINTERNAL: | |
254 | /* | |
255 | * Update the left page count. If split | |
256 | * added at index 0, fix the correct page. | |
257 | */ | |
258 | if (skip > 0) | |
259 | dest = (char *)h + h->linp[skip - 1]; | |
260 | else | |
261 | dest = (char *)l + l->linp[NEXTINDEX(l) - 1]; | |
262 | ((RINTERNAL *)dest)->nrecs = rec_total(lchild); | |
263 | ((RINTERNAL *)dest)->pgno = lchild->pgno; | |
264 | ||
265 | /* Update the right page count. */ | |
266 | h->linp[skip] = h->upper -= nbytes; | |
267 | dest = (char *)h + h->linp[skip]; | |
268 | ((RINTERNAL *)dest)->nrecs = rec_total(rchild); | |
269 | ((RINTERNAL *)dest)->pgno = rchild->pgno; | |
270 | break; | |
271 | case P_RLEAF: | |
272 | /* | |
273 | * Update the left page count. If split | |
274 | * added at index 0, fix the correct page. | |
275 | */ | |
276 | if (skip > 0) | |
277 | dest = (char *)h + h->linp[skip - 1]; | |
278 | else | |
279 | dest = (char *)l + l->linp[NEXTINDEX(l) - 1]; | |
280 | ((RINTERNAL *)dest)->nrecs = NEXTINDEX(lchild); | |
281 | ((RINTERNAL *)dest)->pgno = lchild->pgno; | |
282 | ||
283 | /* Update the right page count. */ | |
284 | h->linp[skip] = h->upper -= nbytes; | |
285 | dest = (char *)h + h->linp[skip]; | |
286 | ((RINTERNAL *)dest)->nrecs = NEXTINDEX(rchild); | |
287 | ((RINTERNAL *)dest)->pgno = rchild->pgno; | |
288 | break; | |
289 | default: | |
290 | abort(); | |
291 | } | |
292 | ||
293 | /* Unpin the held pages. */ | |
294 | if (!parentsplit) { | |
295 | mpool_put(t->bt_mp, h, MPOOL_DIRTY); | |
296 | break; | |
297 | } | |
298 | ||
299 | /* If the root page was split, make it look right. */ | |
300 | if (sp->pgno == P_ROOT && | |
301 | (F_ISSET(t, R_RECNO) ? | |
302 | bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR) | |
303 | goto err1; | |
304 | ||
305 | mpool_put(t->bt_mp, lchild, MPOOL_DIRTY); | |
306 | mpool_put(t->bt_mp, rchild, MPOOL_DIRTY); | |
307 | } | |
308 | ||
309 | /* Unpin the held pages. */ | |
310 | mpool_put(t->bt_mp, l, MPOOL_DIRTY); | |
311 | mpool_put(t->bt_mp, r, MPOOL_DIRTY); | |
312 | ||
313 | /* Clear any pages left on the stack. */ | |
314 | return (RET_SUCCESS); | |
315 | ||
316 | /* | |
317 | * If something fails in the above loop we were already walking back | |
318 | * up the tree and the tree is now inconsistent. Nothing much we can | |
319 | * do about it but release any memory we're holding. | |
320 | */ | |
321 | err1: mpool_put(t->bt_mp, lchild, MPOOL_DIRTY); | |
322 | mpool_put(t->bt_mp, rchild, MPOOL_DIRTY); | |
323 | ||
324 | err2: mpool_put(t->bt_mp, l, 0); | |
325 | mpool_put(t->bt_mp, r, 0); | |
326 | __dbpanic(t->bt_dbp); | |
327 | return (RET_ERROR); | |
328 | } | |
329 | ||
330 | /* | |
331 | * BT_PAGE -- Split a non-root page of a btree. | |
332 | * | |
333 | * Parameters: | |
334 | * t: tree | |
335 | * h: root page | |
336 | * lp: pointer to left page pointer | |
337 | * rp: pointer to right page pointer | |
338 | * skip: pointer to index to leave open | |
339 | * ilen: insert length | |
340 | * | |
341 | * Returns: | |
342 | * Pointer to page in which to insert or NULL on error. | |
343 | */ | |
344 | static PAGE * | |
345 | bt_page(t, h, lp, rp, skip, ilen) | |
346 | BTREE *t; | |
347 | PAGE *h, **lp, **rp; | |
348 | indx_t *skip; | |
349 | size_t ilen; | |
350 | { | |
351 | PAGE *l, *r, *tp; | |
352 | pgno_t npg; | |
353 | ||
354 | #ifdef STATISTICS | |
355 | ++bt_split; | |
356 | #endif | |
357 | /* Put the new right page for the split into place. */ | |
358 | if ((r = __bt_new(t, &npg)) == NULL) | |
359 | return (NULL); | |
360 | r->pgno = npg; | |
361 | r->lower = BTDATAOFF; | |
362 | r->upper = t->bt_psize; | |
363 | r->nextpg = h->nextpg; | |
364 | r->prevpg = h->pgno; | |
365 | r->flags = h->flags & P_TYPE; | |
366 | ||
367 | /* | |
368 | * If we're splitting the last page on a level because we're appending | |
369 | * a key to it (skip is NEXTINDEX()), it's likely that the data is | |
370 | * sorted. Adding an empty page on the side of the level is less work | |
371 | * and can push the fill factor much higher than normal. If we're | |
372 | * wrong it's no big deal, we'll just do the split the right way next | |
373 | * time. It may look like it's equally easy to do a similar hack for | |
374 | * reverse sorted data, that is, split the tree left, but it's not. | |
375 | * Don't even try. | |
376 | */ | |
377 | if (h->nextpg == P_INVALID && *skip == NEXTINDEX(h)) { | |
378 | #ifdef STATISTICS | |
379 | ++bt_sortsplit; | |
380 | #endif | |
381 | h->nextpg = r->pgno; | |
382 | r->lower = BTDATAOFF + sizeof(indx_t); | |
383 | *skip = 0; | |
384 | *lp = h; | |
385 | *rp = r; | |
386 | return (r); | |
387 | } | |
388 | ||
389 | /* Put the new left page for the split into place. */ | |
390 | if ((l = (PAGE *)malloc(t->bt_psize)) == NULL) { | |
391 | mpool_put(t->bt_mp, r, 0); | |
392 | return (NULL); | |
393 | } | |
394 | #ifdef PURIFY | |
395 | memset(l, 0xff, t->bt_psize); | |
396 | #endif | |
397 | l->pgno = h->pgno; | |
398 | l->nextpg = r->pgno; | |
399 | l->prevpg = h->prevpg; | |
400 | l->lower = BTDATAOFF; | |
401 | l->upper = t->bt_psize; | |
402 | l->flags = h->flags & P_TYPE; | |
403 | ||
404 | /* Fix up the previous pointer of the page after the split page. */ | |
405 | if (h->nextpg != P_INVALID) { | |
406 | if ((tp = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) { | |
407 | free(l); | |
408 | /* XXX mpool_free(t->bt_mp, r->pgno); */ | |
409 | return (NULL); | |
410 | } | |
411 | tp->prevpg = r->pgno; | |
412 | mpool_put(t->bt_mp, tp, MPOOL_DIRTY); | |
413 | } | |
414 | ||
415 | /* | |
416 | * Split right. The key/data pairs aren't sorted in the btree page so | |
417 | * it's simpler to copy the data from the split page onto two new pages | |
418 | * instead of copying half the data to the right page and compacting | |
419 | * the left page in place. Since the left page can't change, we have | |
420 | * to swap the original and the allocated left page after the split. | |
421 | */ | |
422 | tp = bt_psplit(t, h, l, r, skip, ilen); | |
423 | ||
424 | /* Move the new left page onto the old left page. */ | |
425 | memmove(h, l, t->bt_psize); | |
426 | if (tp == l) | |
427 | tp = h; | |
428 | free(l); | |
429 | ||
430 | *lp = h; | |
431 | *rp = r; | |
432 | return (tp); | |
433 | } | |
434 | ||
435 | /* | |
436 | * BT_ROOT -- Split the root page of a btree. | |
437 | * | |
438 | * Parameters: | |
439 | * t: tree | |
440 | * h: root page | |
441 | * lp: pointer to left page pointer | |
442 | * rp: pointer to right page pointer | |
443 | * skip: pointer to index to leave open | |
444 | * ilen: insert length | |
445 | * | |
446 | * Returns: | |
447 | * Pointer to page in which to insert or NULL on error. | |
448 | */ | |
449 | static PAGE * | |
450 | bt_root(t, h, lp, rp, skip, ilen) | |
451 | BTREE *t; | |
452 | PAGE *h, **lp, **rp; | |
453 | indx_t *skip; | |
454 | size_t ilen; | |
455 | { | |
456 | PAGE *l, *r, *tp; | |
457 | pgno_t lnpg, rnpg; | |
458 | ||
459 | #ifdef STATISTICS | |
460 | ++bt_split; | |
461 | ++bt_rootsplit; | |
462 | #endif | |
463 | /* Put the new left and right pages for the split into place. */ | |
464 | if ((l = __bt_new(t, &lnpg)) == NULL || | |
465 | (r = __bt_new(t, &rnpg)) == NULL) | |
466 | return (NULL); | |
467 | l->pgno = lnpg; | |
468 | r->pgno = rnpg; | |
469 | l->nextpg = r->pgno; | |
470 | r->prevpg = l->pgno; | |
471 | l->prevpg = r->nextpg = P_INVALID; | |
472 | l->lower = r->lower = BTDATAOFF; | |
473 | l->upper = r->upper = t->bt_psize; | |
474 | l->flags = r->flags = h->flags & P_TYPE; | |
475 | ||
476 | /* Split the root page. */ | |
477 | tp = bt_psplit(t, h, l, r, skip, ilen); | |
478 | ||
479 | *lp = l; | |
480 | *rp = r; | |
481 | return (tp); | |
482 | } | |
483 | ||
484 | /* | |
485 | * BT_RROOT -- Fix up the recno root page after it has been split. | |
486 | * | |
487 | * Parameters: | |
488 | * t: tree | |
489 | * h: root page | |
490 | * l: left page | |
491 | * r: right page | |
492 | * | |
493 | * Returns: | |
494 | * RET_ERROR, RET_SUCCESS | |
495 | */ | |
496 | static int | |
497 | bt_rroot(t, h, l, r) | |
498 | BTREE *t; | |
499 | PAGE *h, *l, *r; | |
500 | { | |
501 | char *dest; | |
502 | ||
503 | /* Insert the left and right keys, set the header information. */ | |
504 | h->linp[0] = h->upper = t->bt_psize - NRINTERNAL; | |
505 | dest = (char *)h + h->upper; | |
506 | WR_RINTERNAL(dest, | |
507 | l->flags & P_RLEAF ? NEXTINDEX(l) : rec_total(l), l->pgno); | |
508 | ||
509 | h->linp[1] = h->upper -= NRINTERNAL; | |
510 | dest = (char *)h + h->upper; | |
511 | WR_RINTERNAL(dest, | |
512 | r->flags & P_RLEAF ? NEXTINDEX(r) : rec_total(r), r->pgno); | |
513 | ||
514 | h->lower = BTDATAOFF + 2 * sizeof(indx_t); | |
515 | ||
516 | /* Unpin the root page, set to recno internal page. */ | |
517 | h->flags &= ~P_TYPE; | |
518 | h->flags |= P_RINTERNAL; | |
519 | mpool_put(t->bt_mp, h, MPOOL_DIRTY); | |
520 | ||
521 | return (RET_SUCCESS); | |
522 | } | |
523 | ||
524 | /* | |
525 | * BT_BROOT -- Fix up the btree root page after it has been split. | |
526 | * | |
527 | * Parameters: | |
528 | * t: tree | |
529 | * h: root page | |
530 | * l: left page | |
531 | * r: right page | |
532 | * | |
533 | * Returns: | |
534 | * RET_ERROR, RET_SUCCESS | |
535 | */ | |
536 | static int | |
537 | bt_broot(t, h, l, r) | |
538 | BTREE *t; | |
539 | PAGE *h, *l, *r; | |
540 | { | |
541 | BINTERNAL *bi; | |
542 | BLEAF *bl; | |
543 | u_int32_t nbytes; | |
544 | char *dest; | |
545 | ||
546 | /* | |
547 | * If the root page was a leaf page, change it into an internal page. | |
548 | * We copy the key we split on (but not the key's data, in the case of | |
549 | * a leaf page) to the new root page. | |
550 | * | |
551 | * The btree comparison code guarantees that the left-most key on any | |
552 | * level of the tree is never used, so it doesn't need to be filled in. | |
553 | */ | |
554 | nbytes = NBINTERNAL(0); | |
555 | h->linp[0] = h->upper = t->bt_psize - nbytes; | |
556 | dest = (char *)h + h->upper; | |
557 | WR_BINTERNAL(dest, 0, l->pgno, 0); | |
558 | ||
559 | switch (h->flags & P_TYPE) { | |
560 | case P_BLEAF: | |
561 | bl = GETBLEAF(r, 0); | |
562 | nbytes = NBINTERNAL(bl->ksize); | |
563 | h->linp[1] = h->upper -= nbytes; | |
564 | dest = (char *)h + h->upper; | |
565 | WR_BINTERNAL(dest, bl->ksize, r->pgno, 0); | |
566 | memmove(dest, bl->bytes, bl->ksize); | |
567 | ||
568 | /* | |
569 | * If the key is on an overflow page, mark the overflow chain | |
570 | * so it isn't deleted when the leaf copy of the key is deleted. | |
571 | */ | |
572 | if (bl->flags & P_BIGKEY && | |
573 | bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR) | |
574 | return (RET_ERROR); | |
575 | break; | |
576 | case P_BINTERNAL: | |
577 | bi = GETBINTERNAL(r, 0); | |
578 | nbytes = NBINTERNAL(bi->ksize); | |
579 | h->linp[1] = h->upper -= nbytes; | |
580 | dest = (char *)h + h->upper; | |
581 | memmove(dest, bi, nbytes); | |
582 | ((BINTERNAL *)dest)->pgno = r->pgno; | |
583 | break; | |
584 | default: | |
585 | abort(); | |
586 | } | |
587 | ||
588 | /* There are two keys on the page. */ | |
589 | h->lower = BTDATAOFF + 2 * sizeof(indx_t); | |
590 | ||
591 | /* Unpin the root page, set to btree internal page. */ | |
592 | h->flags &= ~P_TYPE; | |
593 | h->flags |= P_BINTERNAL; | |
594 | mpool_put(t->bt_mp, h, MPOOL_DIRTY); | |
595 | ||
596 | return (RET_SUCCESS); | |
597 | } | |
598 | ||
599 | /* | |
600 | * BT_PSPLIT -- Do the real work of splitting the page. | |
601 | * | |
602 | * Parameters: | |
603 | * t: tree | |
604 | * h: page to be split | |
605 | * l: page to put lower half of data | |
606 | * r: page to put upper half of data | |
607 | * pskip: pointer to index to leave open | |
608 | * ilen: insert length | |
609 | * | |
610 | * Returns: | |
611 | * Pointer to page in which to insert. | |
612 | */ | |
613 | static PAGE * | |
614 | bt_psplit(t, h, l, r, pskip, ilen) | |
615 | BTREE *t; | |
616 | PAGE *h, *l, *r; | |
617 | indx_t *pskip; | |
618 | size_t ilen; | |
619 | { | |
620 | BINTERNAL *bi; | |
621 | BLEAF *bl; | |
622 | CURSOR *c; | |
623 | RLEAF *rl; | |
624 | PAGE *rval; | |
625 | void *src; | |
626 | indx_t full, half, nxt, off, skip, top, used; | |
627 | u_int32_t nbytes; | |
628 | int bigkeycnt, isbigkey; | |
629 | ||
630 | /* | |
631 | * Split the data to the left and right pages. Leave the skip index | |
632 | * open. Additionally, make some effort not to split on an overflow | |
633 | * key. This makes internal page processing faster and can save | |
634 | * space as overflow keys used by internal pages are never deleted. | |
635 | */ | |
636 | bigkeycnt = 0; | |
637 | skip = *pskip; | |
638 | full = t->bt_psize - BTDATAOFF; | |
639 | half = full / 2; | |
640 | used = 0; | |
641 | for (nxt = off = 0, top = NEXTINDEX(h); nxt < top; ++off) { | |
642 | if (skip == off) { | |
643 | nbytes = ilen; | |
644 | isbigkey = 0; /* XXX: not really known. */ | |
645 | } else | |
646 | switch (h->flags & P_TYPE) { | |
647 | case P_BINTERNAL: | |
648 | src = bi = GETBINTERNAL(h, nxt); | |
649 | nbytes = NBINTERNAL(bi->ksize); | |
650 | isbigkey = bi->flags & P_BIGKEY; | |
651 | break; | |
652 | case P_BLEAF: | |
653 | src = bl = GETBLEAF(h, nxt); | |
654 | nbytes = NBLEAF(bl); | |
655 | isbigkey = bl->flags & P_BIGKEY; | |
656 | break; | |
657 | case P_RINTERNAL: | |
658 | src = GETRINTERNAL(h, nxt); | |
659 | nbytes = NRINTERNAL; | |
660 | isbigkey = 0; | |
661 | break; | |
662 | case P_RLEAF: | |
663 | src = rl = GETRLEAF(h, nxt); | |
664 | nbytes = NRLEAF(rl); | |
665 | isbigkey = 0; | |
666 | break; | |
667 | default: | |
668 | abort(); | |
669 | } | |
670 | ||
671 | /* | |
672 | * If the key/data pairs are substantial fractions of the max | |
673 | * possible size for the page, it's possible to get situations | |
674 | * where we decide to try and copy too much onto the left page. | |
675 | * Make sure that doesn't happen. | |
676 | */ | |
677 | if (skip <= off && used + nbytes >= full) { | |
678 | --off; | |
679 | break; | |
680 | } | |
681 | ||
682 | /* Copy the key/data pair, if not the skipped index. */ | |
683 | if (skip != off) { | |
684 | ++nxt; | |
685 | ||
686 | l->linp[off] = l->upper -= nbytes; | |
687 | memmove((char *)l + l->upper, src, nbytes); | |
688 | } | |
689 | ||
690 | used += nbytes; | |
691 | if (used >= half) { | |
692 | if (!isbigkey || bigkeycnt == 3) | |
693 | break; | |
694 | else | |
695 | ++bigkeycnt; | |
696 | } | |
697 | } | |
698 | ||
699 | /* | |
700 | * Off is the last offset that's valid for the left page. | |
701 | * Nxt is the first offset to be placed on the right page. | |
702 | */ | |
703 | l->lower += (off + 1) * sizeof(indx_t); | |
704 | ||
705 | /* | |
706 | * If splitting the page that the cursor was on, the cursor has to be | |
707 | * adjusted to point to the same record as before the split. If the | |
708 | * cursor is at or past the skipped slot, the cursor is incremented by | |
709 | * one. If the cursor is on the right page, it is decremented by the | |
710 | * number of records split to the left page. | |
711 | */ | |
712 | c = &t->bt_cursor; | |
713 | if (F_ISSET(c, CURS_INIT) && c->pg.pgno == h->pgno) { | |
714 | if (c->pg.index >= skip) | |
715 | ++c->pg.index; | |
716 | if (c->pg.index < nxt) /* Left page. */ | |
717 | c->pg.pgno = l->pgno; | |
718 | else { /* Right page. */ | |
719 | c->pg.pgno = r->pgno; | |
720 | c->pg.index -= nxt; | |
721 | } | |
722 | } | |
723 | ||
724 | /* | |
725 | * If the skipped index was on the left page, just return that page. | |
726 | * Otherwise, adjust the skip index to reflect the new position on | |
727 | * the right page. | |
728 | */ | |
729 | if (skip <= off) { | |
730 | skip = 0; | |
731 | rval = l; | |
732 | } else { | |
733 | rval = r; | |
734 | *pskip -= nxt; | |
735 | } | |
736 | ||
737 | for (off = 0; nxt < top; ++off) { | |
738 | if (skip == nxt) { | |
739 | ++off; | |
740 | skip = 0; | |
741 | } | |
742 | switch (h->flags & P_TYPE) { | |
743 | case P_BINTERNAL: | |
744 | src = bi = GETBINTERNAL(h, nxt); | |
745 | nbytes = NBINTERNAL(bi->ksize); | |
746 | break; | |
747 | case P_BLEAF: | |
748 | src = bl = GETBLEAF(h, nxt); | |
749 | nbytes = NBLEAF(bl); | |
750 | break; | |
751 | case P_RINTERNAL: | |
752 | src = GETRINTERNAL(h, nxt); | |
753 | nbytes = NRINTERNAL; | |
754 | break; | |
755 | case P_RLEAF: | |
756 | src = rl = GETRLEAF(h, nxt); | |
757 | nbytes = NRLEAF(rl); | |
758 | break; | |
759 | default: | |
760 | abort(); | |
761 | } | |
762 | ++nxt; | |
763 | r->linp[off] = r->upper -= nbytes; | |
764 | memmove((char *)r + r->upper, src, nbytes); | |
765 | } | |
766 | r->lower += off * sizeof(indx_t); | |
767 | ||
768 | /* If the key is being appended to the page, adjust the index. */ | |
769 | if (skip == top) | |
770 | r->lower += sizeof(indx_t); | |
771 | ||
772 | return (rval); | |
773 | } | |
774 | ||
775 | /* | |
776 | * BT_PRESERVE -- Mark a chain of pages as used by an internal node. | |
777 | * | |
778 | * Chains of indirect blocks pointed to by leaf nodes get reclaimed when the | |
779 | * record that references them gets deleted. Chains pointed to by internal | |
780 | * pages never get deleted. This routine marks a chain as pointed to by an | |
781 | * internal page. | |
782 | * | |
783 | * Parameters: | |
784 | * t: tree | |
785 | * pg: page number of first page in the chain. | |
786 | * | |
787 | * Returns: | |
788 | * RET_SUCCESS, RET_ERROR. | |
789 | */ | |
790 | static int | |
791 | bt_preserve(t, pg) | |
792 | BTREE *t; | |
793 | pgno_t pg; | |
794 | { | |
795 | PAGE *h; | |
796 | ||
797 | if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) | |
798 | return (RET_ERROR); | |
799 | h->flags |= P_PRESERVE; | |
800 | mpool_put(t->bt_mp, h, MPOOL_DIRTY); | |
801 | return (RET_SUCCESS); | |
802 | } | |
803 | ||
804 | /* | |
805 | * REC_TOTAL -- Return the number of recno entries below a page. | |
806 | * | |
807 | * Parameters: | |
808 | * h: page | |
809 | * | |
810 | * Returns: | |
811 | * The number of recno entries below a page. | |
812 | * | |
813 | * XXX | |
814 | * These values could be set by the bt_psplit routine. The problem is that the | |
815 | * entry has to be popped off of the stack etc. or the values have to be passed | |
816 | * all the way back to bt_split/bt_rroot and it's not very clean. | |
817 | */ | |
818 | static recno_t | |
819 | rec_total(h) | |
820 | PAGE *h; | |
821 | { | |
822 | recno_t recs; | |
823 | indx_t nxt, top; | |
824 | ||
825 | for (recs = 0, nxt = 0, top = NEXTINDEX(h); nxt < top; ++nxt) | |
826 | recs += GETRINTERNAL(h, nxt)->nrecs; | |
827 | return (recs); | |
828 | } |