← Back to branch summary

~ubuntu-branches/ubuntu/maverick/evolution-data-server/maverick-proposed

« back to all changes in this revision

Viewing changes to libdb/btree/bt_stat.c

  • Committer: Bazaar Package Importer
  • Author(s): Didier Roche
  • Date: 2010-05-17 17:02:06 UTC
  • mfrom: (1.1.79 upstream) (1.6.12 experimental)
  • Revision ID: james.westby@ubuntu.com-20100517170206-4ufr52vwrhh26yh0
Tags: 2.30.1-1ubuntu1
https://launchpad.net/bugs/42199
https://launchpad.net/bugs/229669
https://launchpad.net/bugs/173703
https://launchpad.net/bugs/360344
https://launchpad.net/bugs/508494
* Merge from debian experimental. Remaining change:
  (LP: #42199, #229669, #173703, #360344, #508494)
  + debian/control:
    - add Vcs-Bzr tag
    - don't use libgnome
    - Use Breaks instead of Conflicts against evolution 2.25 and earlier.
  + debian/evolution-data-server.install,
    debian/patches/45_libcamel_providers_version.patch:
    - use the upstream versioning, not a Debian-specific one 
  + debian/libedata-book1.2-dev.install, debian/libebackend-1.2-dev.install,
    debian/libcamel1.2-dev.install, debian/libedataserverui1.2-dev.install:
    - install html documentation
  + debian/rules:
    - don't build documentation it's shipped with the tarball

Show diffs side-by-side

added added

removed removed

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