← Back to branch summary

~ubuntu-branches/ubuntu/saucy/db/saucy-proposed

« back to all changes in this revision

Viewing changes to btree/bt_stat.c

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson
  • Date: 2010-11-05 15:02:09 UTC
  • mfrom: (13.1.12 sid)
  • Revision ID: james.westby@ubuntu.com-20101105150209-ppvyn0619pu014xo
Tags: 5.1.19-1ubuntu1
* Resynchronise with Debian.  Remaining changes:
  - Pass --build/--host to configure to support cross-building, and don't
    override CC.
  - Disable the Java build when cross-building, for now.

Show diffs side-by-side

added added

removed removed

Lines of Context:
btree/bt_stat.c
1
 
/*-
2
 
 * See the file LICENSE for redistribution information.
3
 
 *
4
 
 * Copyright (c) 1996, 2010 Oracle and/or its affiliates.  All rights reserved.
5
 
 *
6
 
 * $Id$
7
 
 */
8
 
 
9
 
#include "db_config.h"
10
 
 
11
 
#include "db_int.h"
12
 
#include "dbinc/db_page.h"
13
 
#include "dbinc/btree.h"
14
 
#include "dbinc/lock.h"
15
 
#include "dbinc/mp.h"
16
 
#include "dbinc/partition.h"
17
 
 
18
 
#ifdef HAVE_STATISTICS
19
 
/*
20
 
 * __bam_stat --
21
 
 *      Gather/print the btree statistics
22
 
 *
23
 
 * PUBLIC: int __bam_stat __P((DBC *, void *, u_int32_t));
24
 
 */
25
 
int
26
 
__bam_stat(dbc, spp, flags)
27
 
        DBC *dbc;
28
 
        void *spp;
29
 
        u_int32_t flags;
30
 
{
31
 
        BTMETA *meta;
32
 
        BTREE *t;
33
 
        DB *dbp;
34
 
        DB_BTREE_STAT *sp;
35
 
        DB_LOCK lock, metalock;
36
 
        DB_MPOOLFILE *mpf;
37
 
        ENV *env;
38
 
        PAGE *h;
39
 
        db_pgno_t pgno;
40
 
        int ret, t_ret, write_meta;
41
 
 
42
 
        dbp = dbc->dbp;
43
 
        env = dbp->env;
44
 
 
45
 
        meta = NULL;
46
 
        t = dbp->bt_internal;
47
 
        sp = NULL;
48
 
        LOCK_INIT(metalock);
49
 
        LOCK_INIT(lock);
50
 
        mpf = dbp->mpf;
51
 
        h = NULL;
52
 
        ret = write_meta = 0;
53
 
 
54
 
        /* Allocate and clear the structure. */
55
 
        if ((ret = __os_umalloc(env, sizeof(*sp), &sp)) != 0)
56
 
                goto err;
57
 
        memset(sp, 0, sizeof(*sp));
58
 
 
59
 
        /* Get the metadata page for the entire database. */
60
 
        pgno = PGNO_BASE_MD;
61
 
        if ((ret = __db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &metalock)) != 0)
62
 
                goto err;
63
 
        if ((ret = __memp_fget(mpf, &pgno,
64
 
             dbc->thread_info, dbc->txn, 0, &meta)) != 0)
65
 
                goto err;
66
 
 
67
 
        if (flags == DB_FAST_STAT)
68
 
                goto meta_only;
69
 
 
70
 
        /* Walk the metadata free list, counting pages. */
71
 
        for (sp->bt_free = 0, pgno = meta->dbmeta.free; pgno != PGNO_INVALID;) {
72
 
                ++sp->bt_free;
73
 
 
74
 
                if ((ret = __memp_fget(mpf, &pgno,
75
 
                     dbc->thread_info, dbc->txn, 0, &h)) != 0)
76
 
                        goto err;
77
 
 
78
 
                pgno = h->next_pgno;
79
 
                if ((ret = __memp_fput(mpf,
80
 
                    dbc->thread_info, h, dbc->priority)) != 0)
81
 
                        goto err;
82
 
                h = NULL;
83
 
        }
84
 
 
85
 
        /* Get the root page. */
86
 
        BAM_GET_ROOT(dbc, pgno, h, 0, DB_LOCK_READ, lock, ret);
87
 
        if (ret != 0)
88
 
                goto err;
89
 
        DB_ASSERT(env, h != NULL);
90
 
 
91
 
        /* Get the levels from the root page. */
92
 
        sp->bt_levels = h->level;
93
 
 
94
 
        /* Discard the root page. */
95
 
        ret = __memp_fput(mpf, dbc->thread_info, h, dbc->priority);
96
 
        h = NULL;
97
 
        if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
98
 
                ret = t_ret;
99
 
        if (ret != 0)
100
 
                goto err;
101
 
 
102
 
        /* Walk the tree. */
103
 
        if ((ret = __bam_traverse(dbc,
104
 
            DB_LOCK_READ, PGNO_INVALID, __bam_stat_callback, sp)) != 0)
105
 
                goto err;
106
 
 
107
 
#ifdef HAVE_COMPRESSION
108
 
        if (DB_IS_COMPRESSED(dbp) && (ret = __bam_compress_count(dbc,
109
 
            &sp->bt_nkeys, &sp->bt_ndata)) != 0)
110
 
                goto err;
111
 
#endif
112
 
 
113
 
        /*
114
 
         * Get the subdatabase metadata page if it's not the same as the
115
 
         * one we already have.
116
 
         */
117
 
        write_meta = !F_ISSET(dbp, DB_AM_RDONLY) &&
118
 
            (!MULTIVERSION(dbp) || dbc->txn != NULL);
119
 
meta_only:
120
 
        if (t->bt_meta != PGNO_BASE_MD || write_meta) {
121
 
                ret = __memp_fput(mpf, dbc->thread_info, meta, dbc->priority);
122
 
                meta = NULL;
123
 
                if ((t_ret = __LPUT(dbc, metalock)) != 0 && ret == 0)
124
 
                        ret = t_ret;
125
 
                if (ret != 0)
126
 
                        goto err;
127
 
 
128
 
                if ((ret = __db_lget(dbc,
129
 
                    0, t->bt_meta, write_meta ? DB_LOCK_WRITE : DB_LOCK_READ,
130
 
                    0, &metalock)) != 0)
131
 
                        goto err;
132
 
                if ((ret = __memp_fget(mpf, &t->bt_meta,
133
 
                     dbc->thread_info, dbc->txn,
134
 
                    write_meta ? DB_MPOOL_DIRTY : 0, &meta)) != 0)
135
 
                        goto err;
136
 
        }
137
 
        if (flags == DB_FAST_STAT) {
138
 
                if (dbp->type == DB_RECNO ||
139
 
                    (dbp->type == DB_BTREE && F_ISSET(dbp, DB_AM_RECNUM))) {
140
 
                        BAM_GET_ROOT(dbc, pgno, h, 0, DB_LOCK_READ, lock, ret);
141
 
                        if (ret != 0)
142
 
                                goto err;
143
 
 
144
 
                        sp->bt_nkeys = RE_NREC(h);
145
 
                } else
146
 
                        sp->bt_nkeys = meta->dbmeta.key_count;
147
 
 
148
 
                sp->bt_ndata = dbp->type == DB_RECNO ?
149
 
                   sp->bt_nkeys : meta->dbmeta.record_count;
150
 
        }
151
 
 
152
 
        /* Get metadata page statistics. */
153
 
        sp->bt_metaflags = meta->dbmeta.flags;
154
 
        sp->bt_minkey = meta->minkey;
155
 
        sp->bt_re_len = meta->re_len;
156
 
        sp->bt_re_pad = meta->re_pad;
157
 
        /*
158
 
         * Don't take the page number from the meta-data page -- that value is
159
 
         * only maintained in the primary database, we may have been called on
160
 
         * a subdatabase.  (Yes, I read the primary database meta-data page
161
 
         * earlier in this function, but I'm asking the underlying cache so the
162
 
         * code for the Hash and Btree methods is the same.)
163
 
         */
164
 
        if ((ret = __memp_get_last_pgno(dbp->mpf, &pgno)) != 0)
165
 
                goto err;
166
 
        sp->bt_pagecnt = pgno + 1;
167
 
        sp->bt_pagesize = meta->dbmeta.pagesize;
168
 
        sp->bt_magic = meta->dbmeta.magic;
169
 
        sp->bt_version = meta->dbmeta.version;
170
 
 
171
 
        if (write_meta != 0) {
172
 
                meta->dbmeta.key_count = sp->bt_nkeys;
173
 
                meta->dbmeta.record_count = sp->bt_ndata;
174
 
        }
175
 
 
176
 
        *(DB_BTREE_STAT **)spp = sp;
177
 
 
178
 
err:    /* Discard the second page. */
179
 
        if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
180
 
                ret = t_ret;
181
 
        if (h != NULL && (t_ret = __memp_fput(mpf,
182
 
            dbc->thread_info, h, dbc->priority)) != 0 && ret == 0)
183
 
                ret = t_ret;
184
 
 
185
 
        /* Discard the metadata page. */
186
 
        if ((t_ret = __LPUT(dbc, metalock)) != 0 && ret == 0)
187
 
                ret = t_ret;
188
 
        if (meta != NULL && (t_ret = __memp_fput(mpf,
189
 
            dbc->thread_info, meta, dbc->priority)) != 0 && ret == 0)
190
 
                ret = t_ret;
191
 
 
192
 
        if (ret != 0 && sp != NULL) {
193
 
                __os_ufree(env, sp);
194
 
                *(DB_BTREE_STAT **)spp = NULL;
195
 
        }
196
 
 
197
 
        return (ret);
198
 
}
199
 
 
200
 
/*
201
 
 * __bam_stat_print --
202
 
 *      Display btree/recno statistics.
203
 
 *
204
 
 * PUBLIC: int __bam_stat_print __P((DBC *, u_int32_t));
205
 
 */
206
 
int
207
 
__bam_stat_print(dbc, flags)
208
 
        DBC *dbc;
209
 
        u_int32_t flags;
210
 
{
211
 
        static const FN fn[] = {
212
 
                { BTM_DUP,      "duplicates" },
213
 
                { BTM_RECNO,    "recno" },
214
 
                { BTM_RECNUM,   "record-numbers" },
215
 
                { BTM_FIXEDLEN, "fixed-length" },
216
 
                { BTM_RENUMBER, "renumber" },
217
 
                { BTM_SUBDB,    "multiple-databases" },
218
 
                { BTM_DUPSORT,  "sorted duplicates" },
219
 
                { BTM_COMPRESS, "compressed" },
220
 
                { 0,            NULL }
221
 
        };
222
 
        DB *dbp;
223
 
        DB_BTREE_STAT *sp;
224
 
        ENV *env;
225
 
        int lorder, ret;
226
 
        const char *s;
227
 
 
228
 
        dbp = dbc->dbp;
229
 
        env = dbp->env;
230
 
#ifdef HAVE_PARTITION
231
 
        if (DB_IS_PARTITIONED(dbp)) {
232
 
                if ((ret = __partition_stat(dbc, &sp, flags)) != 0)
233
 
                        return (ret);
234
 
        } else
235
 
#endif
236
 
        if ((ret = __bam_stat(dbc, &sp, LF_ISSET(DB_FAST_STAT))) != 0)
237
 
                return (ret);
238
 
 
239
 
        if (LF_ISSET(DB_STAT_ALL)) {
240
 
                __db_msg(env, "%s", DB_GLOBAL(db_line));
241
 
                __db_msg(env, "Default Btree/Recno database information:");
242
 
        }
243
 
 
244
 
        __db_msg(env, "%lx\tBtree magic number", (u_long)sp->bt_magic);
245
 
        __db_msg(env, "%lu\tBtree version number", (u_long)sp->bt_version);
246
 
 
247
 
        (void)__db_get_lorder(dbp, &lorder);
248
 
        switch (lorder) {
249
 
        case 1234:
250
 
                s = "Little-endian";
251
 
                break;
252
 
        case 4321:
253
 
                s = "Big-endian";
254
 
                break;
255
 
        default:
256
 
                s = "Unrecognized byte order";
257
 
                break;
258
 
        }
259
 
        __db_msg(env, "%s\tByte order", s);
260
 
        __db_prflags(env, NULL, sp->bt_metaflags, fn, NULL, "\tFlags");
261
 
        if (dbp->type == DB_BTREE)
262
 
                __db_dl(env, "Minimum keys per-page", (u_long)sp->bt_minkey);
263
 
        if (dbp->type == DB_RECNO) {
264
 
                __db_dl(env,
265
 
                    "Fixed-length record size", (u_long)sp->bt_re_len);
266
 
                __db_msg(env,
267
 
                    "%#x\tFixed-length record pad", (u_int)sp->bt_re_pad);
268
 
        }
269
 
        __db_dl(env,
270
 
            "Underlying database page size", (u_long)sp->bt_pagesize);
271
 
        if (dbp->type == DB_BTREE)
272
 
                __db_dl(env, "Overflow key/data size",
273
 
                    ((BTREE_CURSOR *)dbc->internal)->ovflsize);
274
 
        __db_dl(env, "Number of levels in the tree", (u_long)sp->bt_levels);
275
 
        __db_dl(env, dbp->type == DB_BTREE ?
276
 
            "Number of unique keys in the tree" :
277
 
            "Number of records in the tree", (u_long)sp->bt_nkeys);
278
 
        __db_dl(env,
279
 
            "Number of data items in the tree", (u_long)sp->bt_ndata);
280
 
 
281
 
        __db_dl(env,
282
 
            "Number of tree internal pages", (u_long)sp->bt_int_pg);
283
 
        __db_dl_pct(env,
284
 
            "Number of bytes free in tree internal pages",
285
 
            (u_long)sp->bt_int_pgfree,
286
 
            DB_PCT_PG(sp->bt_int_pgfree, sp->bt_int_pg, sp->bt_pagesize), "ff");
287
 
 
288
 
        __db_dl(env,
289
 
            "Number of tree leaf pages", (u_long)sp->bt_leaf_pg);
290
 
        __db_dl_pct(env, "Number of bytes free in tree leaf pages",
291
 
            (u_long)sp->bt_leaf_pgfree, DB_PCT_PG(
292
 
            sp->bt_leaf_pgfree, sp->bt_leaf_pg, sp->bt_pagesize), "ff");
293
 
 
294
 
        __db_dl(env,
295
 
            "Number of tree duplicate pages", (u_long)sp->bt_dup_pg);
296
 
        __db_dl_pct(env,
297
 
            "Number of bytes free in tree duplicate pages",
298
 
            (u_long)sp->bt_dup_pgfree,
299
 
            DB_PCT_PG(sp->bt_dup_pgfree, sp->bt_dup_pg, sp->bt_pagesize), "ff");
300
 
 
301
 
        __db_dl(env,
302
 
            "Number of tree overflow pages", (u_long)sp->bt_over_pg);
303
 
        __db_dl_pct(env, "Number of bytes free in tree overflow pages",
304
 
            (u_long)sp->bt_over_pgfree, DB_PCT_PG(
305
 
            sp->bt_over_pgfree, sp->bt_over_pg, sp->bt_pagesize), "ff");
306
 
        __db_dl(env, "Number of empty pages", (u_long)sp->bt_empty_pg);
307
 
 
308
 
        __db_dl(env, "Number of pages on the free list", (u_long)sp->bt_free);
309
 
 
310
 
        __os_ufree(env, sp);
311
 
 
312
 
        return (0);
313
 
}
314
 
 
315
 
/*
316
 
 * __bam_stat_callback --
317
 
 *      Statistics callback.
318
 
 *
319
 
 * PUBLIC: int __bam_stat_callback __P((DBC *, PAGE *, void *, int *));
320
 
 */
321
 
int
322
 
__bam_stat_callback(dbc, h, cookie, putp)
323
 
        DBC *dbc;
324
 
        PAGE *h;
325
 
        void *cookie;
326
 
        int *putp;
327
 
{
328
 
        DB *dbp;
329
 
        DB_BTREE_STAT *sp;
330
 
        db_indx_t indx, *inp, top;
331
 
        u_int8_t type;
332
 
 
333
 
        dbp = dbc->dbp;
334
 
        sp = cookie;
335
 
        *putp = 0;
336
 
        top = NUM_ENT(h);
337
 
        inp = P_INP(dbp, h);
338
 
 
339
 
        switch (TYPE(h)) {
340
 
        case P_IBTREE:
341
 
        case P_IRECNO:
342
 
                ++sp->bt_int_pg;
343
 
                sp->bt_int_pgfree += P_FREESPACE(dbp, h);
344
 
                break;
345
 
        case P_LBTREE:
346
 
                if (top == 0)
347
 
                        ++sp->bt_empty_pg;
348
 
 
349
 
                /* Correct for on-page duplicates and deleted items. */
350
 
                for (indx = 0; indx < top; indx += P_INDX) {
351
 
                        type = GET_BKEYDATA(dbp, h, indx + O_INDX)->type;
352
 
                        /* Ignore deleted items. */
353
 
                        if (B_DISSET(type))
354
 
                                continue;
355
 
 
356
 
                        /* Ignore duplicate keys. */
357
 
                        if (indx + P_INDX >= top ||
358
 
                            inp[indx] != inp[indx + P_INDX])
359
 
                                ++sp->bt_nkeys;
360
 
 
361
 
                        /* Ignore off-page duplicates. */
362
 
                        if (B_TYPE(type) != B_DUPLICATE)
363
 
                                ++sp->bt_ndata;
364
 
                }
365
 
 
366
 
                ++sp->bt_leaf_pg;
367
 
                sp->bt_leaf_pgfree += P_FREESPACE(dbp, h);
368
 
                break;
369
 
        case P_LRECNO:
370
 
                if (top == 0)
371
 
                        ++sp->bt_empty_pg;
372
 
 
373
 
                /*
374
 
                 * If walking a recno tree, then each of these items is a key.
375
 
                 * Otherwise, we're walking an off-page duplicate set.
376
 
                 */
377
 
                if (dbp->type == DB_RECNO) {
378
 
                        /*
379
 
                         * Correct for deleted items in non-renumbering Recno
380
 
                         * databases.
381
 
                         */
382
 
                        if (F_ISSET(dbp, DB_AM_RENUMBER)) {
383
 
                                sp->bt_nkeys += top;
384
 
                                sp->bt_ndata += top;
385
 
                        } else
386
 
                                for (indx = 0; indx < top; indx += O_INDX) {
387
 
                                        type = GET_BKEYDATA(dbp, h, indx)->type;
388
 
                                        if (!B_DISSET(type)) {
389
 
                                                ++sp->bt_ndata;
390
 
                                                ++sp->bt_nkeys;
391
 
                                        }
392
 
                                }
393
 
 
394
 
                        ++sp->bt_leaf_pg;
395
 
                        sp->bt_leaf_pgfree += P_FREESPACE(dbp, h);
396
 
                } else {
397
 
                        sp->bt_ndata += top;
398
 
 
399
 
                        ++sp->bt_dup_pg;
400
 
                        sp->bt_dup_pgfree += P_FREESPACE(dbp, h);
401
 
                }
402
 
                break;
403
 
        case P_LDUP:
404
 
                if (top == 0)
405
 
                        ++sp->bt_empty_pg;
406
 
 
407
 
                /* Correct for deleted items. */
408
 
                for (indx = 0; indx < top; indx += O_INDX)
409
 
                        if (!B_DISSET(GET_BKEYDATA(dbp, h, indx)->type))
410
 
                                ++sp->bt_ndata;
411
 
 
412
 
                ++sp->bt_dup_pg;
413
 
                sp->bt_dup_pgfree += P_FREESPACE(dbp, h);
414
 
                break;
415
 
        case P_OVERFLOW:
416
 
                ++sp->bt_over_pg;
417
 
                sp->bt_over_pgfree += P_OVFLSPACE(dbp, dbp->pgsize, h);
418
 
                break;
419
 
        default:
420
 
                return (__db_pgfmt(dbp->env, h->pgno));
421
 
        }
422
 
        return (0);
423
 
}
424
 
 
425
 
/*
426
 
 * __bam_print_cursor --
427
 
 *      Display the current internal cursor.
428
 
 *
429
 
 * PUBLIC: void __bam_print_cursor __P((DBC *));
430
 
 */
431
 
void
432
 
__bam_print_cursor(dbc)
433
 
        DBC *dbc;
434
 
{
435
 
        static const FN fn[] = {
436
 
                { C_DELETED,    "C_DELETED" },
437
 
                { C_RECNUM,     "C_RECNUM" },
438
 
                { C_RENUMBER,   "C_RENUMBER" },
439
 
                { 0,            NULL }
440
 
        };
441
 
        ENV *env;
442
 
        BTREE_CURSOR *cp;
443
 
 
444
 
        env = dbc->env;
445
 
        cp = (BTREE_CURSOR *)dbc->internal;
446
 
 
447
 
        STAT_ULONG("Overflow size", cp->ovflsize);
448
 
        if (dbc->dbtype == DB_RECNO)
449
 
                STAT_ULONG("Recno", cp->recno);
450
 
        STAT_ULONG("Order", cp->order);
451
 
        __db_prflags(env, NULL, cp->flags, fn, NULL, "\tInternal Flags");
452
 
}
453
 
 
454
 
#else /* !HAVE_STATISTICS */
455
 
 
456
 
int
457
 
__bam_stat(dbc, spp, flags)
458
 
        DBC *dbc;
459
 
        void *spp;
460
 
        u_int32_t flags;
461
 
{
462
 
        COMPQUIET(spp, NULL);
463
 
        COMPQUIET(flags, 0);
464
 
 
465
 
        return (__db_stat_not_built(dbc->env));
466
 
}
467
 
 
468
 
int
469
 
__bam_stat_print(dbc, flags)
470
 
        DBC *dbc;
471
 
        u_int32_t flags;
472
 
{
473
 
        COMPQUIET(flags, 0);
474
 
 
475
 
        return (__db_stat_not_built(dbc->env));
476
 
}
477
 
#endif
478
 
 
479
 
#ifndef HAVE_BREW
480
 
/*
481
 
 * __bam_key_range --
482
 
 *      Return proportion of keys relative to given key.  The numbers are
483
 
 *      slightly skewed due to on page duplicates.
484
 
 *
485
 
 * PUBLIC: int __bam_key_range __P((DBC *, DBT *, DB_KEY_RANGE *, u_int32_t));
486
 
 */
487
 
int
488
 
__bam_key_range(dbc, dbt, kp, flags)
489
 
        DBC *dbc;
490
 
        DBT *dbt;
491
 
        DB_KEY_RANGE *kp;
492
 
        u_int32_t flags;
493
 
{
494
 
        BTREE_CURSOR *cp;
495
 
        EPG *sp;
496
 
        double factor;
497
 
        int exact, ret;
498
 
 
499
 
        COMPQUIET(flags, 0);
500
 
 
501
 
        if ((ret = __bam_search(dbc, PGNO_INVALID,
502
 
            dbt, SR_STK_ONLY, 1, NULL, &exact)) != 0)
503
 
                return (ret);
504
 
 
505
 
        cp = (BTREE_CURSOR *)dbc->internal;
506
 
        kp->less = kp->greater = 0.0;
507
 
 
508
 
        factor = 1.0;
509
 
 
510
 
        /* Correct the leaf page. */
511
 
        cp->csp->entries /= 2;
512
 
        cp->csp->indx /= 2;
513
 
        for (sp = cp->sp; sp <= cp->csp; ++sp) {
514
 
                /*
515
 
                 * At each level we know that pages greater than indx contain
516
 
                 * keys greater than what we are looking for and those less
517
 
                 * than indx are less than.  The one pointed to by indx may
518
 
                 * have some less, some greater or even equal.  If indx is
519
 
                 * equal to the number of entries, then the key is out of range
520
 
                 * and everything is less.
521
 
                 */
522
 
                if (sp->indx == 0)
523
 
                        kp->greater += factor * (sp->entries - 1)/sp->entries;
524
 
                else if (sp->indx == sp->entries)
525
 
                        kp->less += factor;
526
 
                else {
527
 
                        kp->less += factor * sp->indx / sp->entries;
528
 
                        kp->greater += factor *
529
 
                            ((sp->entries - sp->indx) - 1) / sp->entries;
530
 
                }
531
 
                factor *= 1.0/sp->entries;
532
 
        }
533
 
 
534
 
        /*
535
 
         * If there was an exact match then assign 1 n'th to the key itself.
536
 
         * Otherwise that factor belongs to those greater than the key, unless
537
 
         * the key was out of range.
538
 
         */
539
 
        if (exact)
540
 
                kp->equal = factor;
541
 
        else {
542
 
                if (kp->less != 1)
543
 
                        kp->greater += factor;
544
 
                kp->equal = 0;
545
 
        }
546
 
 
547
 
        if ((ret = __bam_stkrel(dbc, 0)) != 0)
548
 
                return (ret);
549
 
 
550
 
        return (0);
551
 
}
552
 
#endif
553
 
 
554
 
/*
555
 
 * __bam_traverse --
556
 
 *      Walk a Btree database.
557
 
 *
558
 
 * PUBLIC: int __bam_traverse __P((DBC *, db_lockmode_t,
559
 
 * PUBLIC:     db_pgno_t, int (*)(DBC *, PAGE *, void *, int *), void *));
560
 
 */
561
 
int
562
 
__bam_traverse(dbc, mode, root_pgno, callback, cookie)
563
 
        DBC *dbc;
564
 
        db_lockmode_t mode;
565
 
        db_pgno_t root_pgno;
566
 
        int (*callback)__P((DBC *, PAGE *, void *, int *));
567
 
        void *cookie;
568
 
{
569
 
        BINTERNAL *bi;
570
 
        BKEYDATA *bk;
571
 
        DB *dbp;
572
 
        DB_LOCK lock;
573
 
        DB_MPOOLFILE *mpf;
574
 
        PAGE *h;
575
 
        RINTERNAL *ri;
576
 
        db_indx_t indx, *inp;
577
 
        int already_put, ret, t_ret;
578
 
 
579
 
        dbp = dbc->dbp;
580
 
        mpf = dbp->mpf;
581
 
        already_put = 0;
582
 
        LOCK_INIT(lock);
583
 
 
584
 
        COMPQUIET(h, NULL);
585
 
        BAM_GET_ROOT(dbc, root_pgno, h, 0, mode, lock, ret);
586
 
        if (ret != 0)
587
 
                goto err1;
588
 
 
589
 
        switch (TYPE(h)) {
590
 
        case P_IBTREE:
591
 
                for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
592
 
                        bi = GET_BINTERNAL(dbp, h, indx);
593
 
                        if (B_TYPE(bi->type) == B_OVERFLOW &&
594
 
                            (ret = __db_traverse_big(dbc,
595
 
                            ((BOVERFLOW *)bi->data)->pgno,
596
 
                            callback, cookie)) != 0)
597
 
                                goto err;
598
 
                        if ((ret = __bam_traverse(
599
 
                            dbc, mode, bi->pgno, callback, cookie)) != 0)
600
 
                                goto err;
601
 
                }
602
 
                break;
603
 
        case P_IRECNO:
604
 
                for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
605
 
                        ri = GET_RINTERNAL(dbp, h, indx);
606
 
                        if ((ret = __bam_traverse(
607
 
                            dbc, mode, ri->pgno, callback, cookie)) != 0)
608
 
                                goto err;
609
 
                }
610
 
                break;
611
 
        case P_LBTREE:
612
 
                inp = P_INP(dbp, h);
613
 
                for (indx = 0; indx < NUM_ENT(h); indx += P_INDX) {
614
 
                        bk = GET_BKEYDATA(dbp, h, indx);
615
 
                        if (B_TYPE(bk->type) == B_OVERFLOW &&
616
 
                            (indx + P_INDX >= NUM_ENT(h) ||
617
 
                            inp[indx] != inp[indx + P_INDX])) {
618
 
                                if ((ret = __db_traverse_big(dbc,
619
 
                                    GET_BOVERFLOW(dbp, h, indx)->pgno,
620
 
                                    callback, cookie)) != 0)
621
 
                                        goto err;
622
 
                        }
623
 
                        bk = GET_BKEYDATA(dbp, h, indx + O_INDX);
624
 
                        if (B_TYPE(bk->type) == B_DUPLICATE &&
625
 
                            (ret = __bam_traverse(dbc, mode,
626
 
                            GET_BOVERFLOW(dbp, h, indx + O_INDX)->pgno,
627
 
                            callback, cookie)) != 0)
628
 
                                goto err;
629
 
                        if (B_TYPE(bk->type) == B_OVERFLOW &&
630
 
                            (ret = __db_traverse_big(dbc,
631
 
                            GET_BOVERFLOW(dbp, h, indx + O_INDX)->pgno,
632
 
                            callback, cookie)) != 0)
633
 
                                goto err;
634
 
                }
635
 
                break;
636
 
        case P_LDUP:
637
 
        case P_LRECNO:
638
 
                for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
639
 
                        bk = GET_BKEYDATA(dbp, h, indx);
640
 
                        if (B_TYPE(bk->type) == B_OVERFLOW &&
641
 
                            (ret = __db_traverse_big(dbc,
642
 
                            GET_BOVERFLOW(dbp, h, indx)->pgno,
643
 
                            callback, cookie)) != 0)
644
 
                                goto err;
645
 
                }
646
 
                break;
647
 
        default:
648
 
                return (__db_pgfmt(dbp->env, h->pgno));
649
 
        }
650
 
 
651
 
        ret = callback(dbc, h, cookie, &already_put);
652
 
 
653
 
err:    if (!already_put && (t_ret = __memp_fput(mpf,
654
 
            dbc->thread_info, h, dbc->priority)) != 0 && ret == 0)
655
 
                ret = t_ret;
656
 
err1:   if ((t_ret = __TLPUT(dbc, lock)) != 0 && ret == 0)
657
 
                ret = t_ret;
658
 
 
659
 
        return (ret);
660
 
}