1*50990Sbostic /*- 2*50990Sbostic * Copyright (c) 1990 The Regents of the University of California. 3*50990Sbostic * All rights reserved. 4*50990Sbostic * 5*50990Sbostic * This code is derived from software contributed to Berkeley by 6*50990Sbostic * Mike Olson. 7*50990Sbostic * 8*50990Sbostic * %sccs.include.redist.c% 9*50990Sbostic */ 10*50990Sbostic 11*50990Sbostic #if defined(LIBC_SCCS) && !defined(lint) 12*50990Sbostic static char sccsid[] = "@(#)bt_stack.c 5.1 (Berkeley) 09/04/91"; 13*50990Sbostic #endif /* LIBC_SCCS and not lint */ 14*50990Sbostic 15*50990Sbostic #include <sys/types.h> 16*50990Sbostic #include <errno.h> 17*50990Sbostic #include <db.h> 18*50990Sbostic #include <stdio.h> 19*50990Sbostic #include <stdlib.h> 20*50990Sbostic #include "btree.h" 21*50990Sbostic 22*50990Sbostic /* 23*50990Sbostic * When a page splits, a new record has to be inserted into its parent page. 24*50990Sbostic * This page may have to split as well, all the way up to the root. Since 25*50990Sbostic * parent pointers in each page would be expensive, we maintain a stack of 26*50990Sbostic * parent pages as we descend the tree. 27*50990Sbostic * 28*50990Sbostic * XXX 29*50990Sbostic * This is a problem for multiple users -- if user a creates a stack, then user 30*50990Sbostic * b splits the tree, then user a tries to split the tree, there's a new level 31*50990Sbostic * in the tree that user b doesn't know about. 32*50990Sbostic */ 33*50990Sbostic 34*50990Sbostic /* 35*50990Sbostic * BT_PUSH -- Push parent page info onto the stack (LIFO). 36*50990Sbostic * 37*50990Sbostic * Parameters: 38*50990Sbostic * t: tree 39*50990Sbostic * pgno: page 40*50990Sbostic * index: page index 41*50990Sbostic * 42*50990Sbostic * Returns: 43*50990Sbostic * RET_ERROR, RET_SUCCESS 44*50990Sbostic */ 45*50990Sbostic int 46*50990Sbostic bt_push(t, pgno, index) 47*50990Sbostic BTREE *t; 48*50990Sbostic pgno_t pgno; 49*50990Sbostic int index; 50*50990Sbostic { 51*50990Sbostic if (t->bt_sp == t->bt_maxstack) { 52*50990Sbostic t->bt_maxstack += 50; 53*50990Sbostic if ((t->bt_stack = realloc(t->bt_stack, 54*50990Sbostic t->bt_maxstack * sizeof(EPGNO))) == NULL) { 55*50990Sbostic t->bt_maxstack -= 50; 56*50990Sbostic return (RET_ERROR); 57*50990Sbostic } 58*50990Sbostic } 59*50990Sbostic 60*50990Sbostic t->bt_stack[t->bt_sp].pgno = pgno; 61*50990Sbostic t->bt_stack[t->bt_sp].index = index; 62*50990Sbostic ++t->bt_sp; 63*50990Sbostic return (RET_SUCCESS); 64*50990Sbostic } 65