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