source: trunk/third/db/btree/bt_stat.c @ 17055

Revision 17055, 10.4 KB checked in by ghudson, 23 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r17054, which included commits to RCS files with non-trunk default branches.
Line 
1/*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 1996, 1997, 1998, 1999, 2000
5 *      Sleepycat Software.  All rights reserved.
6 */
7
8#include "db_config.h"
9
10#ifndef lint
11static const char revid[] = "$Id: bt_stat.c,v 1.1.1.2 2002-02-11 16:29:47 ghudson Exp $";
12#endif /* not lint */
13
14#ifndef NO_SYSTEM_INCLUDES
15#include <sys/types.h>
16
17#include <string.h>
18#endif
19
20#include "db_int.h"
21#include "db_page.h"
22#include "db_shash.h"
23#include "lock.h"
24#include "btree.h"
25
26/*
27 * __bam_stat --
28 *      Gather/print the btree statistics
29 *
30 * PUBLIC: int __bam_stat __P((DB *, void *, void *(*)(size_t), u_int32_t));
31 */
32int
33__bam_stat(dbp, spp, db_malloc, flags)
34        DB *dbp;
35        void *spp;
36        void *(*db_malloc) __P((size_t));
37        u_int32_t flags;
38{
39        BTMETA *meta;
40        BTREE *t;
41        BTREE_CURSOR *cp;
42        DBC *dbc;
43        DB_BTREE_STAT *sp;
44        DB_LOCK lock, metalock;
45        PAGE *h;
46        db_pgno_t pgno;
47        int ret, t_ret;
48
49        PANIC_CHECK(dbp->dbenv);
50        DB_ILLEGAL_BEFORE_OPEN(dbp, "DB->stat");
51
52        meta = NULL;
53        t = dbp->bt_internal;
54        sp = NULL;
55        metalock.off = lock.off = LOCK_INVALID;
56        h = NULL;
57        ret = 0;
58
59        /* Check for invalid flags. */
60        if ((ret = __db_statchk(dbp, flags)) != 0)
61                return (ret);
62
63        /* Acquire a cursor. */
64        if ((ret = dbp->cursor(dbp, NULL, &dbc, 0)) != 0)
65                return (ret);
66        cp = (BTREE_CURSOR *)dbc->internal;
67
68        DEBUG_LWRITE(dbc, NULL, "bam_stat", NULL, NULL, flags);
69
70        /* Allocate and clear the structure. */
71        if ((ret = __os_malloc(dbp->dbenv, sizeof(*sp), db_malloc, &sp)) != 0)
72                goto err;
73        memset(sp, 0, sizeof(*sp));
74
75        /* If the app just wants the record count, make it fast. */
76        if (flags == DB_RECORDCOUNT) {
77                if ((ret = __db_lget(dbc, 0,
78                    cp->root, DB_LOCK_READ, 0, &lock)) != 0)
79                        goto err;
80                if ((ret = memp_fget(dbp->mpf,
81                    &cp->root, 0, (PAGE **)&h)) != 0)
82                        goto err;
83
84                sp->bt_nkeys = RE_NREC(h);
85
86                goto done;
87        }
88        if (flags == DB_CACHED_COUNTS) {
89                if ((ret = __db_lget(dbc,
90                    0, t->bt_meta, DB_LOCK_READ, 0, &lock)) != 0)
91                        goto err;
92                if ((ret =
93                    memp_fget(dbp->mpf, &t->bt_meta, 0, (PAGE **)&meta)) != 0)
94                        goto err;
95                sp->bt_nkeys = meta->dbmeta.key_count;
96                sp->bt_ndata = meta->dbmeta.record_count;
97
98                goto done;
99        }
100
101        /* Get the metadata page for the entire database. */
102        pgno = PGNO_BASE_MD;
103        if ((ret = __db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &metalock)) != 0)
104                goto err;
105        if ((ret = memp_fget(dbp->mpf, &pgno, 0, (PAGE **)&meta)) != 0)
106                goto err;
107
108        /* Walk the metadata free list, counting pages. */
109        for (sp->bt_free = 0, pgno = meta->dbmeta.free; pgno != PGNO_INVALID;) {
110                ++sp->bt_free;
111
112                if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
113                        goto err;
114
115                pgno = h->next_pgno;
116                if ((ret = memp_fput(dbp->mpf, h, 0)) != 0)
117                        goto err;
118                h = NULL;
119        }
120
121        /* Get the root page. */
122        pgno = cp->root;
123        if ((ret = __db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &lock)) != 0)
124                goto err;
125        if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
126                goto err;
127
128        /* Get the levels from the root page. */
129        sp->bt_levels = h->level;
130
131        /* Discard the root page. */
132        if ((ret = memp_fput(dbp->mpf, h, 0)) != 0)
133                goto err;
134        h = NULL;
135        __LPUT(dbc, lock);
136
137        /* Walk the tree. */
138        if ((ret = __bam_traverse(dbc,
139            DB_LOCK_READ, cp->root, __bam_stat_callback, sp)) != 0)
140                goto err;
141
142        /*
143         * Get the subdatabase metadata page if it's not the same as the
144         * one we already have.
145         */
146        if (t->bt_meta != PGNO_BASE_MD || !F_ISSET(dbp, DB_AM_RDONLY)) {
147                if ((ret = memp_fput(dbp->mpf, meta, 0)) != 0)
148                        goto err;
149                meta = NULL;
150                __LPUT(dbc, metalock);
151
152                if ((ret = __db_lget(dbc,
153                    0, t->bt_meta, F_ISSET(dbp, DB_AM_RDONLY) ?
154                    DB_LOCK_READ : DB_LOCK_WRITE, 0, &metalock)) != 0)
155                        goto err;
156                if ((ret =
157                    memp_fget(dbp->mpf, &t->bt_meta, 0, (PAGE **)&meta)) != 0)
158                        goto err;
159        }
160
161        /* Get metadata page statistics. */
162        sp->bt_metaflags = meta->dbmeta.flags;
163        sp->bt_maxkey = meta->maxkey;
164        sp->bt_minkey = meta->minkey;
165        sp->bt_re_len = meta->re_len;
166        sp->bt_re_pad = meta->re_pad;
167        sp->bt_pagesize = meta->dbmeta.pagesize;
168        sp->bt_magic = meta->dbmeta.magic;
169        sp->bt_version = meta->dbmeta.version;
170        if (!F_ISSET(dbp, DB_AM_RDONLY)) {
171                meta->dbmeta.key_count = sp->bt_nkeys;
172                meta->dbmeta.record_count = sp->bt_ndata;
173        }
174
175        /* Discard the metadata page. */
176        if ((ret = memp_fput(dbp->mpf,
177            meta, F_ISSET(dbp, DB_AM_RDONLY) ? 0 : DB_MPOOL_DIRTY)) != 0)
178                goto err;
179        meta = NULL;
180        __LPUT(dbc, metalock);
181
182done:   *(DB_BTREE_STAT **)spp = sp;
183
184        if (0) {
185err:            if (sp != NULL)
186                        __os_free(sp, sizeof(*sp));
187        }
188
189        if (h != NULL &&
190            (t_ret = memp_fput(dbp->mpf, h, 0)) != 0 && ret == 0)
191                ret = t_ret;
192
193        if (meta != NULL &&
194            (t_ret = memp_fput(dbp->mpf, meta, 0)) != 0 && ret == 0)
195                ret = t_ret;
196
197        if (lock.off != LOCK_INVALID)
198                __LPUT(dbc, lock);
199
200        if ((t_ret = dbc->c_close(dbc)) != 0 && ret == 0)
201                ret = t_ret;
202
203        return (ret);
204}
205
206/*
207 * __bam_traverse --
208 *      Walk a Btree database.
209 *
210 * PUBLIC: int __bam_traverse __P((DBC *, db_lockmode_t,
211 * PUBLIC:     db_pgno_t, int (*)(DB *, PAGE *, void *, int *), void *));
212 */
213int
214__bam_traverse(dbc, mode, root_pgno, callback, cookie)
215        DBC *dbc;
216        db_lockmode_t mode;
217        db_pgno_t root_pgno;
218        int (*callback)__P((DB *, PAGE *, void *, int *));
219        void *cookie;
220{
221        BINTERNAL *bi;
222        BKEYDATA *bk;
223        DB *dbp;
224        DB_LOCK lock;
225        PAGE *h;
226        RINTERNAL *ri;
227        db_indx_t indx;
228        int already_put, ret, t_ret;
229
230        dbp = dbc->dbp;
231
232        if ((ret = __db_lget(dbc, 0, root_pgno, mode, 0, &lock)) != 0)
233                return (ret);
234        if ((ret = memp_fget(dbp->mpf, &root_pgno, 0, &h)) != 0)
235                goto err;
236
237        switch (TYPE(h)) {
238        case P_IBTREE:
239                for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
240                        bi = GET_BINTERNAL(h, indx);
241                        if (B_TYPE(bi->type) == B_OVERFLOW &&
242                            (ret = __db_traverse_big(dbp,
243                            ((BOVERFLOW *)bi->data)->pgno,
244                            callback, cookie)) != 0)
245                                goto err;
246                        if ((ret = __bam_traverse(
247                            dbc, mode, bi->pgno, callback, cookie)) != 0)
248                                break;
249                }
250                break;
251        case P_IRECNO:
252                for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
253                        ri = GET_RINTERNAL(h, indx);
254                        if ((ret = __bam_traverse(
255                            dbc, mode, ri->pgno, callback, cookie)) != 0)
256                                break;
257                }
258                break;
259        case P_LBTREE:
260                for (indx = 0; indx < NUM_ENT(h); indx += P_INDX) {
261                        bk = GET_BKEYDATA(h, indx);
262                        if (B_TYPE(bk->type) == B_OVERFLOW &&
263                            (ret = __db_traverse_big(dbp,
264                            GET_BOVERFLOW(h, indx)->pgno,
265                            callback, cookie)) != 0)
266                                goto err;
267                        bk = GET_BKEYDATA(h, indx + O_INDX);
268                        if (B_TYPE(bk->type) == B_DUPLICATE &&
269                            (ret = __bam_traverse(dbc, mode,
270                            GET_BOVERFLOW(h, indx + O_INDX)->pgno,
271                            callback, cookie)) != 0)
272                                goto err;
273                        if (B_TYPE(bk->type) == B_OVERFLOW &&
274                            (ret = __db_traverse_big(dbp,
275                            GET_BOVERFLOW(h, indx + O_INDX)->pgno,
276                            callback, cookie)) != 0)
277                                goto err;
278                }
279                break;
280        }
281
282        already_put = 0;
283        if ((ret = callback(dbp, h, cookie, &already_put)) != 0)
284                goto err;
285
286err:    if (!already_put &&
287            (t_ret = memp_fput(dbp->mpf, h, 0)) != 0 && ret != 0)
288                ret = t_ret;
289        __LPUT(dbc, lock);
290
291        return (ret);
292}
293
294/*
295 * __bam_stat_callback --
296 *      Statistics callback.
297 *
298 * PUBLIC: int __bam_stat_callback __P((DB *, PAGE *, void *, int *));
299 */
300int
301__bam_stat_callback(dbp, h, cookie, putp)
302        DB *dbp;
303        PAGE *h;
304        void *cookie;
305        int *putp;
306{
307        DB_BTREE_STAT *sp;
308        db_indx_t indx, top;
309        u_int8_t type;
310
311        sp = cookie;
312        *putp = 0;
313        top = NUM_ENT(h);
314
315        switch (TYPE(h)) {
316        case P_IBTREE:
317        case P_IRECNO:
318                ++sp->bt_int_pg;
319                sp->bt_int_pgfree += P_FREESPACE(h);
320                break;
321        case P_LBTREE:
322                /* Correct for on-page duplicates and deleted items. */
323                for (indx = 0; indx < top; indx += P_INDX) {
324                        if (indx + P_INDX >= top ||
325                            h->inp[indx] != h->inp[indx + P_INDX])
326                                ++sp->bt_nkeys;
327
328                        type = GET_BKEYDATA(h, indx + O_INDX)->type;
329                        if (!B_DISSET(type) && B_TYPE(type) != B_DUPLICATE)
330                                ++sp->bt_ndata;
331                }
332
333                ++sp->bt_leaf_pg;
334                sp->bt_leaf_pgfree += P_FREESPACE(h);
335                break;
336        case P_LRECNO:
337                /*
338                 * If walking a recno tree, then each of these items is a key.
339                 * Otherwise, we're walking an off-page duplicate set.
340                 */
341                if (dbp->type == DB_RECNO) {
342                        sp->bt_nkeys += top;
343                        sp->bt_ndata += top;
344                        ++sp->bt_leaf_pg;
345                        sp->bt_leaf_pgfree += P_FREESPACE(h);
346                } else {
347                        sp->bt_ndata += top;
348                        ++sp->bt_dup_pg;
349                        sp->bt_dup_pgfree += P_FREESPACE(h);
350                }
351                break;
352        case P_LDUP:
353                /* Correct for deleted items. */
354                for (indx = 0; indx < top; indx += O_INDX)
355                        if (!B_DISSET(GET_BKEYDATA(h, indx)->type))
356                                ++sp->bt_ndata;
357
358                ++sp->bt_dup_pg;
359                sp->bt_dup_pgfree += P_FREESPACE(h);
360                break;
361        case P_OVERFLOW:
362                ++sp->bt_over_pg;
363                sp->bt_over_pgfree += P_OVFLSPACE(dbp->pgsize, h);
364                break;
365        default:
366                return (__db_pgfmt(dbp, h->pgno));
367        }
368        return (0);
369}
370
371/*
372 * __bam_key_range --
373 *      Return proportion of keys relative to given key.  The numbers are
374 *      slightly skewed due to on page duplicates.
375 *
376 * PUBLIC: int __bam_key_range __P((DB *,
377 * PUBLIC:     DB_TXN *, DBT *, DB_KEY_RANGE *, u_int32_t));
378 */
379int
380__bam_key_range(dbp, txn, dbt, kp, flags)
381        DB *dbp;
382        DB_TXN *txn;
383        DBT *dbt;
384        DB_KEY_RANGE *kp;
385        u_int32_t flags;
386{
387        BTREE_CURSOR *cp;
388        DBC *dbc;
389        EPG *sp;
390        double factor;
391        int exact, ret, t_ret;
392
393        PANIC_CHECK(dbp->dbenv);
394        DB_ILLEGAL_BEFORE_OPEN(dbp, "DB->key_range");
395
396        if (flags != 0)
397                return (__db_ferr(dbp->dbenv, "DB->key_range", 0));
398
399        /* Acquire a cursor. */
400        if ((ret = dbp->cursor(dbp, txn, &dbc, 0)) != 0)
401                return (ret);
402
403        DEBUG_LWRITE(dbc, NULL, "bam_key_range", NULL, NULL, 0);
404
405        if ((ret = __bam_search(dbc, dbt, S_STK_ONLY, 1, NULL, &exact)) != 0)
406                goto err;
407
408        cp = (BTREE_CURSOR *)dbc->internal;
409        kp->less = kp->greater = 0.0;
410
411        factor = 1.0;
412        /* Correct the leaf page. */
413        cp->csp->entries /= 2;
414        cp->csp->indx /= 2;
415        for (sp = cp->sp; sp <= cp->csp; ++sp) {
416                /*
417                 * At each level we know that pages greater than indx contain
418                 * keys greater than what we are looking for and those less
419                 * than indx are less than.  The one pointed to by indx may
420                 * have some less, some greater or even equal.  If indx is
421                 * equal to the number of entries, then the key is out of range
422                 * and everything is less.
423                 */
424                if (sp->indx == 0)
425                        kp->greater += factor * (sp->entries - 1)/sp->entries;
426                else if (sp->indx == sp->entries)
427                        kp->less += factor;
428                else {
429                        kp->less += factor * sp->indx / sp->entries;
430                        kp->greater += factor *
431                            (sp->entries - sp->indx - 1) / sp->entries;
432                }
433                factor *= 1.0/sp->entries;
434        }
435
436        /*
437         * If there was an exact match then assign 1 n'th to the key itself.
438         * Otherwise that factor belongs to those greater than the key, unless
439         * the key was out of range.
440         */
441        if (exact)
442                kp->equal = factor;
443        else {
444                if (kp->less != 1)
445                        kp->greater += factor;
446                kp->equal = 0;
447        }
448
449        BT_STK_CLR(cp);
450
451err:    if ((t_ret = dbc->c_close(dbc)) != 0 && ret == 0)
452                ret = t_ret;
453
454        return (ret);
455}
Note: See TracBrowser for help on using the repository browser.