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