150990Sbostic /*- 250990Sbostic * Copyright (c) 1990 The Regents of the University of California. 350990Sbostic * All rights reserved. 450990Sbostic * 550990Sbostic * This code is derived from software contributed to Berkeley by 650990Sbostic * Mike Olson. 750990Sbostic * 850990Sbostic * %sccs.include.redist.c% 950990Sbostic */ 1050990Sbostic 1150990Sbostic #if defined(LIBC_SCCS) && !defined(lint) 12*56739Sbostic static char sccsid[] = "@(#)bt_stack.c 5.3 (Berkeley) 11/13/92"; 1350990Sbostic #endif /* LIBC_SCCS and not lint */ 1450990Sbostic 1550990Sbostic #include <sys/types.h> 16*56739Sbostic 17*56739Sbostic #include <db.h> 1850990Sbostic #include <errno.h> 1950990Sbostic #include <stdio.h> 2050990Sbostic #include <stdlib.h> 21*56739Sbostic 2250990Sbostic #include "btree.h" 2350990Sbostic 2450990Sbostic /* 2550990Sbostic * When a page splits, a new record has to be inserted into its parent page. 2650990Sbostic * This page may have to split as well, all the way up to the root. Since 2750990Sbostic * parent pointers in each page would be expensive, we maintain a stack of 2850990Sbostic * parent pages as we descend the tree. 2950990Sbostic * 3050990Sbostic * XXX 3151108Sbostic * This is a concurrency problem -- if user a builds a stack, then user b 3251108Sbostic * splits the tree, then user a tries to split the tree, there's a new level 3351108Sbostic * in the tree that user a doesn't know about. 3450990Sbostic */ 3550990Sbostic 3650990Sbostic /* 3751108Sbostic * __BT_PUSH -- Push parent page info onto the stack (LIFO). 3850990Sbostic * 3950990Sbostic * Parameters: 4050990Sbostic * t: tree 4150990Sbostic * pgno: page 4250990Sbostic * index: page index 4350990Sbostic * 4450990Sbostic * Returns: 4550990Sbostic * RET_ERROR, RET_SUCCESS 4650990Sbostic */ 4750990Sbostic int 4851108Sbostic __bt_push(t, pgno, index) 4950990Sbostic BTREE *t; 5050990Sbostic pgno_t pgno; 5150990Sbostic int index; 5250990Sbostic { 5350990Sbostic if (t->bt_sp == t->bt_maxstack) { 5450990Sbostic t->bt_maxstack += 50; 5550990Sbostic if ((t->bt_stack = realloc(t->bt_stack, 5650990Sbostic t->bt_maxstack * sizeof(EPGNO))) == NULL) { 5750990Sbostic t->bt_maxstack -= 50; 5850990Sbostic return (RET_ERROR); 5950990Sbostic } 6050990Sbostic } 6150990Sbostic 6250990Sbostic t->bt_stack[t->bt_sp].pgno = pgno; 6350990Sbostic t->bt_stack[t->bt_sp].index = index; 6450990Sbostic ++t->bt_sp; 6550990Sbostic return (RET_SUCCESS); 6650990Sbostic } 67