1 /*-
2 * Copyright (c) 1990, 1993
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 * %sccs.include.redist.c%
9 */
10
11 #if defined(LIBC_SCCS) && !defined(lint)
12 static char sccsid[] = "@(#)bt_stack.c 8.3 (Berkeley) 02/21/94";
13 #endif /* LIBC_SCCS and not lint */
14
15 #include <sys/types.h>
16
17 #include <errno.h>
18 #include <stdio.h>
19 #include <stdlib.h>
20
21 #include <db.h>
22 #include "btree.h"
23
24 /*
25 * When a page splits, a new record has to be inserted into its parent page.
26 * This page may have to split as well, all the way up to the root. Since
27 * parent pointers in each page would be expensive, we maintain a stack of
28 * parent pages as we descend the tree.
29 *
30 * XXX
31 * This is a concurrency problem -- if user a builds a stack, then user b
32 * splits the tree, then user a tries to split the tree, there's a new level
33 * in the tree that user a doesn't know about.
34 */
35
36 /*
37 * __BT_PUSH -- Push parent page info onto the stack (LIFO).
38 *
39 * Parameters:
40 * t: tree
41 * pgno: page
42 * index: page index
43 *
44 * Returns:
45 * RET_ERROR, RET_SUCCESS
46 */
47 int
__bt_push(t,pgno,index)48 __bt_push(t, pgno, index)
49 BTREE *t;
50 pgno_t pgno;
51 indx_t index;
52 {
53 if (t->bt_sp == t->bt_maxstack) {
54 t->bt_maxstack += 50;
55 if ((t->bt_stack = (EPGNO *)realloc(t->bt_stack,
56 t->bt_maxstack * sizeof(EPGNO))) == NULL) {
57 t->bt_maxstack -= 50;
58 return (RET_ERROR);
59 }
60 }
61
62 t->bt_stack[t->bt_sp].pgno = pgno;
63 t->bt_stack[t->bt_sp].index = index;
64 ++t->bt_sp;
65 return (RET_SUCCESS);
66 }
67