150995Sbostic /*- 250995Sbostic * Copyright (c) 1990 The Regents of the University of California. 350995Sbostic * All rights reserved. 450995Sbostic * 550995Sbostic * %sccs.include.redist.c% 650995Sbostic */ 750995Sbostic 850995Sbostic #if defined(LIBC_SCCS) && !defined(lint) 9*51092Sbostic static char sccsid[] = "@(#)rec_search.c 5.2 (Berkeley) 09/11/91"; 1050995Sbostic #endif /* LIBC_SCCS and not lint */ 1150995Sbostic 1250995Sbostic #include <sys/types.h> 1350995Sbostic #include <errno.h> 1450995Sbostic #include <db.h> 1550995Sbostic #include <stdio.h> 16*51092Sbostic #include "recno.h" 1750995Sbostic 1850995Sbostic /* 1950995Sbostic * __REC_SEARCH -- Search a btree for a key. 2050995Sbostic * 2150995Sbostic * Parameters: 2250995Sbostic * t: tree to search 2350995Sbostic * key: key to find 24*51092Sbostic * op: search operation 2550995Sbostic * exactp: pointer to exact match flag 2650995Sbostic * 2750995Sbostic * Returns: 2850995Sbostic * EPG for matching record, if any, or the EPG for the location of the 2950995Sbostic * key, if it were inserted into the tree. 3050995Sbostic * 3150995Sbostic * Warnings: 3250995Sbostic * The EPG returned is in static memory, and will be overwritten by the 3350995Sbostic * next search of any kind in any tree. 3450995Sbostic */ 3550995Sbostic EPG * 36*51092Sbostic __rec_search(t, recno, op) 3750995Sbostic BTREE *t; 3850995Sbostic recno_t recno; 39*51092Sbostic enum SRCHOP op; 4050995Sbostic { 4150995Sbostic static EPG e; 4250995Sbostic register index_t index; 4350995Sbostic register PAGE *h; 44*51092Sbostic EPGNO *parent; 4550995Sbostic RINTERNAL *r; 4650995Sbostic pgno_t pg; 4750995Sbostic index_t top; 4850995Sbostic recno_t total; 49*51092Sbostic int serrno; 5050995Sbostic 5150995Sbostic for (pg = P_ROOT, total = 0;;) { 5250995Sbostic if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 53*51092Sbostic goto err; 5450995Sbostic if (h->flags & P_RLEAF) { 5550995Sbostic e.page = h; 5650995Sbostic e.index = recno - total; 5750995Sbostic return (&e); 5850995Sbostic } 5950995Sbostic for (index = 0, top = NEXTINDEX(h);;) { 6050995Sbostic r = GETRINTERNAL(h, index); 6150995Sbostic if (++index == top || total + r->nrecs >= recno) 6250995Sbostic break; 6350995Sbostic total += r->nrecs; 6450995Sbostic } 6550995Sbostic 66*51092Sbostic if (__bt_push(t, pg, index) == RET_ERROR) 6750995Sbostic return (NULL); 68*51092Sbostic 69*51092Sbostic pg = r->pgno; 70*51092Sbostic switch (op) { 71*51092Sbostic case SDELETE: 72*51092Sbostic --GETRINTERNAL(h, index)->nrecs; 73*51092Sbostic mpool_put(t->bt_mp, h, MPOOL_DIRTY); 74*51092Sbostic break; 75*51092Sbostic case SINSERT: 76*51092Sbostic ++GETRINTERNAL(h, index)->nrecs; 77*51092Sbostic mpool_put(t->bt_mp, h, MPOOL_DIRTY); 78*51092Sbostic break; 79*51092Sbostic case SEARCH: 80*51092Sbostic mpool_put(t->bt_mp, h, 0); 81*51092Sbostic break; 82*51092Sbostic } 8350995Sbostic 8450995Sbostic } 85*51092Sbostic /* Try and recover the tree. */ 86*51092Sbostic err: serrno = errno; 87*51092Sbostic if (op != SEARCH) 88*51092Sbostic while ((parent = BT_POP(t)) != NULL) { 89*51092Sbostic if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 90*51092Sbostic break; 91*51092Sbostic if (op == SINSERT) 92*51092Sbostic --GETRINTERNAL(h, parent->index)->nrecs; 93*51092Sbostic else 94*51092Sbostic ++GETRINTERNAL(h, parent->index)->nrecs; 95*51092Sbostic mpool_put(t->bt_mp, h, MPOOL_DIRTY); 96*51092Sbostic } 97*51092Sbostic errno = serrno; 98*51092Sbostic return (NULL); 9950995Sbostic } 100