bt_stat.c 14.9 KB
Newer Older
1 2 3
/*-
 * See the file LICENSE for redistribution information.
 *
jimw@mysql.com's avatar
jimw@mysql.com committed
4
 * Copyright (c) 1996-2005
5
 *	Sleepycat Software.  All rights reserved.
jimw@mysql.com's avatar
jimw@mysql.com committed
6
 *
jimw@mysql.com's avatar
jimw@mysql.com committed
7
 * $Id: bt_stat.c,v 12.3 2005/06/16 20:20:23 bostic Exp $
8 9 10 11 12 13 14
 */

#include "db_config.h"

#ifndef NO_SYSTEM_INCLUDES
#include <sys/types.h>

jimw@mysql.com's avatar
jimw@mysql.com committed
15
#include <ctype.h>
16 17 18 19
#include <string.h>
#endif

#include "db_int.h"
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
20 21 22 23
#include "dbinc/db_page.h"
#include "dbinc/db_shash.h"
#include "dbinc/btree.h"
#include "dbinc/lock.h"
jimw@mysql.com's avatar
jimw@mysql.com committed
24
#include "dbinc/mp.h"
25

jimw@mysql.com's avatar
jimw@mysql.com committed
26
#ifdef HAVE_STATISTICS
27 28 29 30
/*
 * __bam_stat --
 *	Gather/print the btree statistics
 *
jimw@mysql.com's avatar
jimw@mysql.com committed
31
 * PUBLIC: int __bam_stat __P((DBC *, void *, u_int32_t));
32 33
 */
int
jimw@mysql.com's avatar
jimw@mysql.com committed
34 35
__bam_stat(dbc, spp, flags)
	DBC *dbc;
36 37 38 39 40 41
	void *spp;
	u_int32_t flags;
{
	BTMETA *meta;
	BTREE *t;
	BTREE_CURSOR *cp;
jimw@mysql.com's avatar
jimw@mysql.com committed
42
	DB *dbp;
43
	DB_BTREE_STAT *sp;
jimw@mysql.com's avatar
jimw@mysql.com committed
44
	DB_ENV *dbenv;
45
	DB_LOCK lock, metalock;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
46
	DB_MPOOLFILE *mpf;
47 48
	PAGE *h;
	db_pgno_t pgno;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
49
	int ret, t_ret, write_meta;
50

jimw@mysql.com's avatar
jimw@mysql.com committed
51 52
	dbp = dbc->dbp;
	dbenv = dbp->dbenv;
53 54 55 56

	meta = NULL;
	t = dbp->bt_internal;
	sp = NULL;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
57 58 59
	LOCK_INIT(metalock);
	LOCK_INIT(lock);
	mpf = dbp->mpf;
60
	h = NULL;
jimw@mysql.com's avatar
jimw@mysql.com committed
61
	ret = write_meta = 0;
62 63 64 65

	cp = (BTREE_CURSOR *)dbc->internal;

	/* Allocate and clear the structure. */
jimw@mysql.com's avatar
jimw@mysql.com committed
66
	if ((ret = __os_umalloc(dbenv, sizeof(*sp), &sp)) != 0)
67 68 69 70 71 72 73
		goto err;
	memset(sp, 0, sizeof(*sp));

	/* Get the metadata page for the entire database. */
	pgno = PGNO_BASE_MD;
	if ((ret = __db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &metalock)) != 0)
		goto err;
jimw@mysql.com's avatar
jimw@mysql.com committed
74
	if ((ret = __memp_fget(mpf, &pgno, 0, &meta)) != 0)
75 76
		goto err;

ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
77 78 79 80 81
	if (flags == DB_RECORDCOUNT || flags == DB_CACHED_COUNTS)
		flags = DB_FAST_STAT;
	if (flags == DB_FAST_STAT)
		goto meta_only;

82 83 84 85
	/* Walk the metadata free list, counting pages. */
	for (sp->bt_free = 0, pgno = meta->dbmeta.free; pgno != PGNO_INVALID;) {
		++sp->bt_free;

jimw@mysql.com's avatar
jimw@mysql.com committed
86
		if ((ret = __memp_fget(mpf, &pgno, 0, &h)) != 0)
87 88 89
			goto err;

		pgno = h->next_pgno;
jimw@mysql.com's avatar
jimw@mysql.com committed
90
		if ((ret = __memp_fput(mpf, h, 0)) != 0)
91 92 93 94 95 96 97 98
			goto err;
		h = NULL;
	}

	/* Get the root page. */
	pgno = cp->root;
	if ((ret = __db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &lock)) != 0)
		goto err;
jimw@mysql.com's avatar
jimw@mysql.com committed
99
	if ((ret = __memp_fget(mpf, &pgno, 0, &h)) != 0)
100 101 102 103 104 105
		goto err;

	/* Get the levels from the root page. */
	sp->bt_levels = h->level;

	/* Discard the root page. */
jimw@mysql.com's avatar
jimw@mysql.com committed
106
	ret = __memp_fput(mpf, h, 0);
107
	h = NULL;
jimw@mysql.com's avatar
jimw@mysql.com committed
108 109 110 111
	if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
		ret = t_ret;
	if (ret != 0)
		goto err;
112 113 114 115 116 117 118 119 120 121

	/* Walk the tree. */
	if ((ret = __bam_traverse(dbc,
	    DB_LOCK_READ, cp->root, __bam_stat_callback, sp)) != 0)
		goto err;

	/*
	 * Get the subdatabase metadata page if it's not the same as the
	 * one we already have.
	 */
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
122 123 124
	write_meta = !F_ISSET(dbp, DB_AM_RDONLY);
meta_only:
	if (t->bt_meta != PGNO_BASE_MD || write_meta != 0) {
jimw@mysql.com's avatar
jimw@mysql.com committed
125
		ret = __memp_fput(mpf, meta, 0);
126
		meta = NULL;
jimw@mysql.com's avatar
jimw@mysql.com committed
127 128 129 130
		if ((t_ret = __LPUT(dbc, metalock)) != 0 && ret == 0)
			ret = t_ret;
		if (ret != 0)
			goto err;
131 132

		if ((ret = __db_lget(dbc,
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
133
		    0, t->bt_meta, write_meta == 0 ?
134 135
		    DB_LOCK_READ : DB_LOCK_WRITE, 0, &metalock)) != 0)
			goto err;
jimw@mysql.com's avatar
jimw@mysql.com committed
136
		if ((ret = __memp_fget(mpf, &t->bt_meta, 0, &meta)) != 0)
137 138
			goto err;
	}
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
139 140 141 142 143 144
	if (flags == DB_FAST_STAT) {
		if (dbp->type == DB_RECNO ||
		    (dbp->type == DB_BTREE && F_ISSET(dbp, DB_AM_RECNUM))) {
			if ((ret = __db_lget(dbc, 0,
			    cp->root, DB_LOCK_READ, 0, &lock)) != 0)
				goto err;
jimw@mysql.com's avatar
jimw@mysql.com committed
145
			if ((ret = __memp_fget(mpf, &cp->root, 0, &h)) != 0)
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
146 147 148 149 150
				goto err;

			sp->bt_nkeys = RE_NREC(h);
		} else
			sp->bt_nkeys = meta->dbmeta.key_count;
jimw@mysql.com's avatar
jimw@mysql.com committed
151 152 153

		sp->bt_ndata = dbp->type == DB_RECNO ?
		   sp->bt_nkeys : meta->dbmeta.record_count;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
154
	}
155 156 157 158 159 160 161 162 163

	/* Get metadata page statistics. */
	sp->bt_metaflags = meta->dbmeta.flags;
	sp->bt_minkey = meta->minkey;
	sp->bt_re_len = meta->re_len;
	sp->bt_re_pad = meta->re_pad;
	sp->bt_pagesize = meta->dbmeta.pagesize;
	sp->bt_magic = meta->dbmeta.magic;
	sp->bt_version = meta->dbmeta.version;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
164 165

	if (write_meta != 0) {
166 167 168 169
		meta->dbmeta.key_count = sp->bt_nkeys;
		meta->dbmeta.record_count = sp->bt_ndata;
	}

ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
170
	*(DB_BTREE_STAT **)spp = sp;
171

ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
172
err:	/* Discard the second page. */
jimw@mysql.com's avatar
jimw@mysql.com committed
173 174 175
	if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
		ret = t_ret;
	if (h != NULL && (t_ret = __memp_fput(mpf, h, 0)) != 0 && ret == 0)
176 177
		ret = t_ret;

ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
178
	/* Discard the metadata page. */
jimw@mysql.com's avatar
jimw@mysql.com committed
179
	if ((t_ret = __LPUT(dbc, metalock)) != 0 && ret == 0)
180
		ret = t_ret;
jimw@mysql.com's avatar
jimw@mysql.com committed
181 182
	if (meta != NULL && (t_ret = __memp_fput(
	    mpf, meta, write_meta == 0 ? 0 : DB_MPOOL_DIRTY)) != 0 && ret == 0)
183 184
		ret = t_ret;

ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
185
	if (ret != 0 && sp != NULL) {
jimw@mysql.com's avatar
jimw@mysql.com committed
186
		__os_ufree(dbenv, sp);
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
187 188 189
		*(DB_BTREE_STAT **)spp = NULL;
	}

190 191 192 193
	return (ret);
}

/*
jimw@mysql.com's avatar
jimw@mysql.com committed
194 195
 * __bam_stat_print --
 *	Display btree/recno statistics.
196
 *
jimw@mysql.com's avatar
jimw@mysql.com committed
197
 * PUBLIC: int __bam_stat_print __P((DBC *, u_int32_t));
198 199
 */
int
jimw@mysql.com's avatar
jimw@mysql.com committed
200
__bam_stat_print(dbc, flags)
201
	DBC *dbc;
jimw@mysql.com's avatar
jimw@mysql.com committed
202
	u_int32_t flags;
203
{
jimw@mysql.com's avatar
jimw@mysql.com committed
204 205 206 207 208 209 210 211 212 213
	static const FN fn[] = {
		{ BTM_DUP,	"duplicates" },
		{ BTM_RECNO,	"recno" },
		{ BTM_RECNUM,	"record-numbers" },
		{ BTM_FIXEDLEN,	"fixed-length" },
		{ BTM_RENUMBER,	"renumber" },
		{ BTM_SUBDB,	"multiple-databases" },
		{ BTM_DUPSORT,	"sorted duplicates" },
		{ 0,		NULL }
	};
214
	DB *dbp;
jimw@mysql.com's avatar
jimw@mysql.com committed
215 216 217 218
	DB_BTREE_STAT *sp;
	DB_ENV *dbenv;
	int lorder, ret;
	const char *s;
219 220

	dbp = dbc->dbp;
jimw@mysql.com's avatar
jimw@mysql.com committed
221
	dbenv = dbp->dbenv;
222

jimw@mysql.com's avatar
jimw@mysql.com committed
223
	if ((ret = __bam_stat(dbc, &sp, 0)) != 0)
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
224
		return (ret);
jimw@mysql.com's avatar
jimw@mysql.com committed
225 226 227 228

	if (LF_ISSET(DB_STAT_ALL)) {
		__db_msg(dbenv, "%s", DB_GLOBAL(db_line));
		__db_msg(dbenv, "Default Btree/Recno database information:");
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
229
	}
230

jimw@mysql.com's avatar
jimw@mysql.com committed
231 232 233 234 235 236 237
	__db_msg(dbenv, "%lx\tBtree magic number", (u_long)sp->bt_magic);
	__db_msg(dbenv, "%lu\tBtree version number", (u_long)sp->bt_version);

	(void)__db_get_lorder(dbp, &lorder);
	switch (lorder) {
	case 1234:
		s = "Little-endian";
238
		break;
jimw@mysql.com's avatar
jimw@mysql.com committed
239 240
	case 4321:
		s = "Big-endian";
241
		break;
jimw@mysql.com's avatar
jimw@mysql.com committed
242 243
	default:
		s = "Unrecognized byte order";
244 245
		break;
	}
jimw@mysql.com's avatar
jimw@mysql.com committed
246 247
	__db_msg(dbenv, "%s\tByte order", s);
	__db_prflags(dbenv, NULL, sp->bt_metaflags, fn, NULL, "\tFlags");
jimw@mysql.com's avatar
jimw@mysql.com committed
248
	if (dbp->type == DB_BTREE)
jimw@mysql.com's avatar
jimw@mysql.com committed
249 250 251 252
		__db_dl(dbenv, "Minimum keys per-page", (u_long)sp->bt_minkey);
	if (dbp->type == DB_RECNO) {
		__db_dl(dbenv,
		    "Fixed-length record size", (u_long)sp->bt_re_len);
jimw@mysql.com's avatar
jimw@mysql.com committed
253
		__db_msg(dbenv,
jimw@mysql.com's avatar
jimw@mysql.com committed
254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294
		    "%#x\tFixed-length record pad", (u_int)sp->bt_re_pad);
	}
	__db_dl(dbenv,
	    "Underlying database page size", (u_long)sp->bt_pagesize);
	__db_dl(dbenv, "Number of levels in the tree", (u_long)sp->bt_levels);
	__db_dl(dbenv, dbp->type == DB_BTREE ?
	    "Number of unique keys in the tree" :
	    "Number of records in the tree", (u_long)sp->bt_nkeys);
	__db_dl(dbenv,
	    "Number of data items in the tree", (u_long)sp->bt_ndata);

	__db_dl(dbenv,
	    "Number of tree internal pages", (u_long)sp->bt_int_pg);
	__db_dl_pct(dbenv,
	    "Number of bytes free in tree internal pages",
	    (u_long)sp->bt_int_pgfree,
	    DB_PCT_PG(sp->bt_int_pgfree, sp->bt_int_pg, sp->bt_pagesize), "ff");

	__db_dl(dbenv,
	    "Number of tree leaf pages", (u_long)sp->bt_leaf_pg);
	__db_dl_pct(dbenv, "Number of bytes free in tree leaf pages",
	    (u_long)sp->bt_leaf_pgfree, DB_PCT_PG(
	    sp->bt_leaf_pgfree, sp->bt_leaf_pg, sp->bt_pagesize), "ff");

	__db_dl(dbenv,
	    "Number of tree duplicate pages", (u_long)sp->bt_dup_pg);
	__db_dl_pct(dbenv,
	    "Number of bytes free in tree duplicate pages",
	    (u_long)sp->bt_dup_pgfree,
	    DB_PCT_PG(sp->bt_dup_pgfree, sp->bt_dup_pg, sp->bt_pagesize), "ff");

	__db_dl(dbenv,
	    "Number of tree overflow pages", (u_long)sp->bt_over_pg);
	__db_dl_pct(dbenv, "Number of bytes free in tree overflow pages",
	    (u_long)sp->bt_over_pgfree, DB_PCT_PG(
	    sp->bt_over_pgfree, sp->bt_over_pg, sp->bt_pagesize), "ff");
	__db_dl(dbenv, "Number of empty pages", (u_long)sp->bt_empty_pg);

	__db_dl(dbenv, "Number of pages on the free list", (u_long)sp->bt_free);

	__os_ufree(dbenv, sp);
295

jimw@mysql.com's avatar
jimw@mysql.com committed
296
	return (0);
297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
}

/*
 * __bam_stat_callback --
 *	Statistics callback.
 *
 * PUBLIC: int __bam_stat_callback __P((DB *, PAGE *, void *, int *));
 */
int
__bam_stat_callback(dbp, h, cookie, putp)
	DB *dbp;
	PAGE *h;
	void *cookie;
	int *putp;
{
	DB_BTREE_STAT *sp;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
313
	db_indx_t indx, *inp, top;
314 315 316 317 318
	u_int8_t type;

	sp = cookie;
	*putp = 0;
	top = NUM_ENT(h);
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
319
	inp = P_INP(dbp, h);
320 321 322 323 324

	switch (TYPE(h)) {
	case P_IBTREE:
	case P_IRECNO:
		++sp->bt_int_pg;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
325
		sp->bt_int_pgfree += P_FREESPACE(dbp, h);
326 327
		break;
	case P_LBTREE:
jimw@mysql.com's avatar
jimw@mysql.com committed
328 329 330
		if (top == 0)
			++sp->bt_empty_pg;

331 332
		/* Correct for on-page duplicates and deleted items. */
		for (indx = 0; indx < top; indx += P_INDX) {
jimw@mysql.com's avatar
jimw@mysql.com committed
333 334 335 336 337 338
			type = GET_BKEYDATA(dbp, h, indx + O_INDX)->type;
			/* Ignore deleted items. */
			if (B_DISSET(type))
				continue;

			/* Ignore duplicate keys. */
339
			if (indx + P_INDX >= top ||
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
340
			    inp[indx] != inp[indx + P_INDX])
341 342
				++sp->bt_nkeys;

jimw@mysql.com's avatar
jimw@mysql.com committed
343 344
			/* Ignore off-page duplicates. */
			if (B_TYPE(type) != B_DUPLICATE)
345 346 347 348
				++sp->bt_ndata;
		}

		++sp->bt_leaf_pg;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
349
		sp->bt_leaf_pgfree += P_FREESPACE(dbp, h);
350 351
		break;
	case P_LRECNO:
jimw@mysql.com's avatar
jimw@mysql.com committed
352 353 354
		if (top == 0)
			++sp->bt_empty_pg;

355 356 357 358 359 360
		/*
		 * If walking a recno tree, then each of these items is a key.
		 * Otherwise, we're walking an off-page duplicate set.
		 */
		if (dbp->type == DB_RECNO) {
			/*
jimw@mysql.com's avatar
jimw@mysql.com committed
361 362
			 * Correct for deleted items in non-renumbering Recno
			 * databases.
363
			 */
jimw@mysql.com's avatar
jimw@mysql.com committed
364 365
			if (F_ISSET(dbp, DB_AM_RENUMBER)) {
				sp->bt_nkeys += top;
366
				sp->bt_ndata += top;
jimw@mysql.com's avatar
jimw@mysql.com committed
367
			} else
368
				for (indx = 0; indx < top; indx += O_INDX) {
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
369
					type = GET_BKEYDATA(dbp, h, indx)->type;
jimw@mysql.com's avatar
jimw@mysql.com committed
370
					if (!B_DISSET(type)) {
371
						++sp->bt_ndata;
jimw@mysql.com's avatar
jimw@mysql.com committed
372 373
						++sp->bt_nkeys;
					}
374 375 376
				}

			++sp->bt_leaf_pg;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
377
			sp->bt_leaf_pgfree += P_FREESPACE(dbp, h);
378 379 380 381
		} else {
			sp->bt_ndata += top;

			++sp->bt_dup_pg;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
382
			sp->bt_dup_pgfree += P_FREESPACE(dbp, h);
383 384 385
		}
		break;
	case P_LDUP:
jimw@mysql.com's avatar
jimw@mysql.com committed
386 387 388
		if (top == 0)
			++sp->bt_empty_pg;

389 390
		/* Correct for deleted items. */
		for (indx = 0; indx < top; indx += O_INDX)
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
391
			if (!B_DISSET(GET_BKEYDATA(dbp, h, indx)->type))
392 393 394
				++sp->bt_ndata;

		++sp->bt_dup_pg;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
395
		sp->bt_dup_pgfree += P_FREESPACE(dbp, h);
396 397 398
		break;
	case P_OVERFLOW:
		++sp->bt_over_pg;
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
399
		sp->bt_over_pgfree += P_OVFLSPACE(dbp, dbp->pgsize, h);
400 401
		break;
	default:
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
402
		return (__db_pgfmt(dbp->dbenv, h->pgno));
403 404 405 406
	}
	return (0);
}

jimw@mysql.com's avatar
jimw@mysql.com committed
407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460
/*
 * __bam_print_cursor --
 *	Display the current internal cursor.
 *
 * PUBLIC: void __bam_print_cursor __P((DBC *));
 */
void
__bam_print_cursor(dbc)
	DBC *dbc;
{
	static const FN fn[] = {
		{ C_DELETED,	"C_DELETED" },
		{ C_RECNUM,	"C_RECNUM" },
		{ C_RENUMBER,	"C_RENUMBER" },
		{ 0,		NULL }
	};
	DB_ENV *dbenv;
	BTREE_CURSOR *cp;

	dbenv = dbc->dbp->dbenv;
	cp = (BTREE_CURSOR *)dbc->internal;

	STAT_ULONG("Overflow size", cp->ovflsize);
	if (dbc->dbtype == DB_RECNO)
		STAT_ULONG("Recno", cp->recno);
	STAT_ULONG("Order", cp->order);
	__db_prflags(dbenv, NULL, cp->flags, fn, NULL, "\tInternal Flags");
}

#else /* !HAVE_STATISTICS */

int
__bam_stat(dbc, spp, flags)
	DBC *dbc;
	void *spp;
	u_int32_t flags;
{
	COMPQUIET(spp, NULL);
	COMPQUIET(flags, 0);

	return (__db_stat_not_built(dbc->dbp->dbenv));
}

int
__bam_stat_print(dbc, flags)
	DBC *dbc;
	u_int32_t flags;
{
	COMPQUIET(flags, 0);

	return (__db_stat_not_built(dbc->dbp->dbenv));
}
#endif

461 462 463 464 465
/*
 * __bam_key_range --
 *	Return proportion of keys relative to given key.  The numbers are
 *	slightly skewed due to on page duplicates.
 *
jimw@mysql.com's avatar
jimw@mysql.com committed
466
 * PUBLIC: int __bam_key_range __P((DBC *, DBT *, DB_KEY_RANGE *, u_int32_t));
467 468
 */
int
jimw@mysql.com's avatar
jimw@mysql.com committed
469 470
__bam_key_range(dbc, dbt, kp, flags)
	DBC *dbc;
471 472 473 474 475 476 477
	DBT *dbt;
	DB_KEY_RANGE *kp;
	u_int32_t flags;
{
	BTREE_CURSOR *cp;
	EPG *sp;
	double factor;
jimw@mysql.com's avatar
jimw@mysql.com committed
478
	int exact, ret;
479

jimw@mysql.com's avatar
jimw@mysql.com committed
480
	COMPQUIET(flags, 0);
481

ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
482 483
	if ((ret = __bam_search(dbc, PGNO_INVALID,
	    dbt, S_STK_ONLY, 1, NULL, &exact)) != 0)
jimw@mysql.com's avatar
jimw@mysql.com committed
484
		return (ret);
485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508

	cp = (BTREE_CURSOR *)dbc->internal;
	kp->less = kp->greater = 0.0;

	factor = 1.0;
	/* Correct the leaf page. */
	cp->csp->entries /= 2;
	cp->csp->indx /= 2;
	for (sp = cp->sp; sp <= cp->csp; ++sp) {
		/*
		 * At each level we know that pages greater than indx contain
		 * keys greater than what we are looking for and those less
		 * than indx are less than.  The one pointed to by indx may
		 * have some less, some greater or even equal.  If indx is
		 * equal to the number of entries, then the key is out of range
		 * and everything is less.
		 */
		if (sp->indx == 0)
			kp->greater += factor * (sp->entries - 1)/sp->entries;
		else if (sp->indx == sp->entries)
			kp->less += factor;
		else {
			kp->less += factor * sp->indx / sp->entries;
			kp->greater += factor *
jimw@mysql.com's avatar
jimw@mysql.com committed
509
			    ((sp->entries - sp->indx) - 1) / sp->entries;
510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528
		}
		factor *= 1.0/sp->entries;
	}

	/*
	 * If there was an exact match then assign 1 n'th to the key itself.
	 * Otherwise that factor belongs to those greater than the key, unless
	 * the key was out of range.
	 */
	if (exact)
		kp->equal = factor;
	else {
		if (kp->less != 1)
			kp->greater += factor;
		kp->equal = 0;
	}

	BT_STK_CLR(cp);

jimw@mysql.com's avatar
jimw@mysql.com committed
529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634
	return (0);
}

/*
 * __bam_traverse --
 *	Walk a Btree database.
 *
 * PUBLIC: int __bam_traverse __P((DBC *, db_lockmode_t,
 * PUBLIC:     db_pgno_t, int (*)(DB *, PAGE *, void *, int *), void *));
 */
int
__bam_traverse(dbc, mode, root_pgno, callback, cookie)
	DBC *dbc;
	db_lockmode_t mode;
	db_pgno_t root_pgno;
	int (*callback)__P((DB *, PAGE *, void *, int *));
	void *cookie;
{
	BINTERNAL *bi;
	BKEYDATA *bk;
	DB *dbp;
	DB_LOCK lock;
	DB_MPOOLFILE *mpf;
	PAGE *h;
	RINTERNAL *ri;
	db_indx_t indx, *inp;
	int already_put, ret, t_ret;

	dbp = dbc->dbp;
	mpf = dbp->mpf;
	already_put = 0;

	if ((ret = __db_lget(dbc, 0, root_pgno, mode, 0, &lock)) != 0)
		return (ret);
	if ((ret = __memp_fget(mpf, &root_pgno, 0, &h)) != 0) {
		(void)__TLPUT(dbc, lock);
		return (ret);
	}

	switch (TYPE(h)) {
	case P_IBTREE:
		for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
			bi = GET_BINTERNAL(dbp, h, indx);
			if (B_TYPE(bi->type) == B_OVERFLOW &&
			    (ret = __db_traverse_big(dbp,
			    ((BOVERFLOW *)bi->data)->pgno,
			    callback, cookie)) != 0)
				goto err;
			if ((ret = __bam_traverse(
			    dbc, mode, bi->pgno, callback, cookie)) != 0)
				goto err;
		}
		break;
	case P_IRECNO:
		for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
			ri = GET_RINTERNAL(dbp, h, indx);
			if ((ret = __bam_traverse(
			    dbc, mode, ri->pgno, callback, cookie)) != 0)
				goto err;
		}
		break;
	case P_LBTREE:
		inp = P_INP(dbp, h);
		for (indx = 0; indx < NUM_ENT(h); indx += P_INDX) {
			bk = GET_BKEYDATA(dbp, h, indx);
			if (B_TYPE(bk->type) == B_OVERFLOW &&
			    (indx + P_INDX >= NUM_ENT(h) ||
			    inp[indx] != inp[indx + P_INDX])) {
				if ((ret = __db_traverse_big(dbp,
				    GET_BOVERFLOW(dbp, h, indx)->pgno,
				    callback, cookie)) != 0)
					goto err;
			}
			bk = GET_BKEYDATA(dbp, h, indx + O_INDX);
			if (B_TYPE(bk->type) == B_DUPLICATE &&
			    (ret = __bam_traverse(dbc, mode,
			    GET_BOVERFLOW(dbp, h, indx + O_INDX)->pgno,
			    callback, cookie)) != 0)
				goto err;
			if (B_TYPE(bk->type) == B_OVERFLOW &&
			    (ret = __db_traverse_big(dbp,
			    GET_BOVERFLOW(dbp, h, indx + O_INDX)->pgno,
			    callback, cookie)) != 0)
				goto err;
		}
		break;
	case P_LDUP:
	case P_LRECNO:
		for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
			bk = GET_BKEYDATA(dbp, h, indx);
			if (B_TYPE(bk->type) == B_OVERFLOW &&
			    (ret = __db_traverse_big(dbp,
			    GET_BOVERFLOW(dbp, h, indx)->pgno,
			    callback, cookie)) != 0)
				goto err;
		}
		break;
	default:
		return (__db_pgfmt(dbp->dbenv, h->pgno));
	}

	ret = callback(dbp, h, cookie, &already_put);

err:	if (!already_put && (t_ret = __memp_fput(mpf, h, 0)) != 0 && ret == 0)
		ret = t_ret;
	if ((t_ret = __TLPUT(dbc, lock)) != 0 && ret == 0)
635 636 637 638
		ret = t_ret;

	return (ret);
}