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 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