bt_stat.c

Go to the documentation of this file.
00001 /*-
00002  * See the file LICENSE for redistribution information.
00003  *
00004  * Copyright (c) 1996, 1997, 1998, 1999, 2000
00005  *      Sleepycat Software.  All rights reserved.
00006  */
00007 
00008 #include "config.h"
00009 
00010 #ifndef lint
00011 static const char revid[] = "$Id: bt__stat_8c-source.html,v 1.1 2008/06/08 10:13:46 sebdiaz Exp $";
00012 #endif /* not lint */
00013 
00014 #ifndef NO_SYSTEM_INCLUDES
00015 #include <sys/types.h>
00016 
00017 #include <string.h>
00018 #endif
00019 
00020 #include "db_int.h"
00021 #include "db_page.h"
00022 #include "db_shash.h"
00023 #include "lock.h"
00024 #include "btree.h"
00025 
00026 /*
00027  * CDB___bam_stat --
00028  *      Gather/print the btree statistics
00029  *
00030  * PUBLIC: int CDB___bam_stat __P((DB *, void *, void *(*)(size_t), u_int32_t));
00031  */
00032 int
00033 CDB___bam_stat(dbp, spp, db_malloc, flags)
00034         DB *dbp;
00035         void *spp;
00036         void *(*db_malloc) __P((size_t));
00037         u_int32_t flags;
00038 {
00039         BTMETA *meta;
00040         BTREE *t;
00041         BTREE_CURSOR *cp;
00042         DBC *dbc;
00043         DB_BTREE_STAT *sp;
00044         DB_LOCK lock;
00045         PAGE *h;
00046         db_pgno_t pgno;
00047         int ret, t_ret;
00048 
00049         PANIC_CHECK(dbp->dbenv);
00050         DB_ILLEGAL_BEFORE_OPEN(dbp, "DB->stat");
00051 
00052         meta = NULL;
00053         t = dbp->bt_internal;
00054         sp = NULL;
00055         lock.off = LOCK_INVALID;
00056         h = NULL;
00057         ret = 0;
00058 
00059         /* Check for invalid flags. */
00060         if ((ret = CDB___db_statchk(dbp, flags)) != 0)
00061                 return (ret);
00062 
00063         /* Acquire a cursor. */
00064         if ((ret = dbp->cursor(dbp, NULL, &dbc, 0)) != 0)
00065                 return (ret);
00066         cp = (BTREE_CURSOR *)dbc->internal;
00067 
00068         DEBUG_LWRITE(dbc, NULL, "bam_stat", NULL, NULL, flags);
00069 
00070         /* Allocate and clear the structure. */
00071         if ((ret = CDB___os_malloc(dbp->dbenv, sizeof(*sp), db_malloc, &sp)) != 0)
00072                 goto err;
00073         memset(sp, 0, sizeof(*sp));
00074 
00075         /* If the app just wants the record count, make it fast. */
00076         if (flags == DB_RECORDCOUNT) {
00077                 if ((ret = CDB___db_lget(dbc, 0,
00078                     cp->root, DB_LOCK_READ, 0, &lock)) != 0)
00079                         goto err;
00080                 if ((ret = CDB_memp_fget(dbp->mpf,
00081                     &cp->root, 0, (PAGE **)&h)) != 0)
00082                         goto err;
00083 
00084                 sp->bt_nkeys = RE_NREC(h);
00085 
00086                 goto done;
00087         }
00088         if (flags == DB_CACHED_COUNTS) {
00089                 if ((ret = CDB___db_lget(dbc,
00090                     0, t->bt_meta, DB_LOCK_READ, 0, &lock)) != 0)
00091                         goto err;
00092                 if ((ret =
00093                     CDB_memp_fget(dbp->mpf, &t->bt_meta, 0, (PAGE **)&meta)) != 0)
00094                         goto err;
00095                 sp->bt_nkeys = meta->dbmeta.key_count;
00096                 sp->bt_ndata = meta->dbmeta.record_count;
00097 
00098                 goto done;
00099         }
00100 
00101         /* Get the metadata page for the entire database. */
00102         pgno = PGNO_BASE_MD;
00103         if ((ret = CDB___db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &lock)) != 0)
00104                 goto err;
00105         if ((ret = CDB_memp_fget(dbp->mpf, &pgno, 0, (PAGE **)&meta)) != 0)
00106                 goto err;
00107 
00108         /* Walk the metadata free list, counting pages. */
00109         for (sp->bt_free = 0, pgno = meta->dbmeta.free; pgno != PGNO_INVALID;) {
00110                 ++sp->bt_free;
00111 
00112                 if ((ret = CDB_memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
00113                         goto err;
00114 
00115                 pgno = h->next_pgno;
00116                 if ((ret = CDB_memp_fput(dbp->mpf, h, 0)) != 0)
00117                         goto err;
00118                 h = NULL;
00119         }
00120 
00121         /* Get the root page. */
00122         pgno = cp->root;
00123         if ((ret = CDB___db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &lock)) != 0)
00124                 goto err;
00125         if ((ret = CDB_memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
00126                 goto err;
00127 
00128         /* Get the levels from the root page. */
00129         sp->bt_levels = h->level;
00130 
00131         /* Discard the root page. */
00132         if ((ret = CDB_memp_fput(dbp->mpf, h, 0)) != 0)
00133                 goto err;
00134         h = NULL;
00135         __LPUT(dbc, lock);
00136 
00137         /* Walk the tree. */
00138         if ((ret = CDB___bam_traverse(dbc,
00139             DB_LOCK_READ, cp->root, CDB___bam_stat_callback, sp)) != 0)
00140                 goto err;
00141 
00142         /*
00143          * Get the subdatabase metadata page if it's not the same as the
00144          * one we already have.
00145          */
00146         if (t->bt_meta != PGNO_BASE_MD || !F_ISSET(dbp, DB_AM_RDONLY)) {
00147                 if ((ret = CDB_memp_fput(dbp->mpf, meta, 0)) != 0)
00148                         goto err;
00149                 meta = NULL;
00150                 __LPUT(dbc, lock);
00151 
00152                 if ((ret = CDB___db_lget(dbc,
00153                     0, t->bt_meta, F_ISSET(dbp, DB_AM_RDONLY) ?
00154                     DB_LOCK_READ : DB_LOCK_WRITE, 0, &lock)) != 0)
00155                         goto err;
00156                 if ((ret =
00157                     CDB_memp_fget(dbp->mpf, &t->bt_meta, 0, (PAGE **)&meta)) != 0)
00158                         goto err;
00159         }
00160 
00161         /* Get metadata page statistics. */
00162         sp->bt_metaflags = meta->dbmeta.flags;
00163         sp->bt_maxkey = meta->maxkey;
00164         sp->bt_minkey = meta->minkey;
00165         sp->bt_re_len = meta->re_len;
00166         sp->bt_re_pad = meta->re_pad;
00167         sp->bt_pagesize = meta->dbmeta.pagesize;
00168         sp->bt_magic = meta->dbmeta.magic;
00169         sp->bt_version = meta->dbmeta.version;
00170         if (!F_ISSET(dbp, DB_AM_RDONLY)) {
00171                 meta->dbmeta.key_count = sp->bt_nkeys;
00172                 meta->dbmeta.record_count = sp->bt_ndata;
00173         }
00174 
00175         /* Discard the metadata page. */
00176         if ((ret = CDB_memp_fput(dbp->mpf,
00177             meta, F_ISSET(dbp, DB_AM_RDONLY) ? 0 : DB_MPOOL_DIRTY)) != 0)
00178                 goto err;
00179         meta = NULL;
00180         __LPUT(dbc, lock);
00181 
00182 done:   *(DB_BTREE_STAT **)spp = sp;
00183 
00184         if (0) {
00185 err:            if (sp != NULL)
00186                         CDB___os_free(sp, sizeof(*sp));
00187         }
00188 
00189         if (h != NULL &&
00190             (t_ret = CDB_memp_fput(dbp->mpf, h, 0)) != 0 && ret == 0)
00191                 ret = t_ret;
00192 
00193         if (meta != NULL &&
00194             (t_ret = CDB_memp_fput(dbp->mpf, meta, 0)) != 0 && ret == 0)
00195                 ret = t_ret;
00196 
00197         if (lock.off != LOCK_INVALID)
00198                 __LPUT(dbc, lock);
00199 
00200         if ((t_ret = dbc->c_close(dbc)) != 0 && ret == 0)
00201                 ret = t_ret;
00202 
00203         return (ret);
00204 }
00205 
00206 /*
00207  * CDB___bam_traverse --
00208  *      Walk a Btree database.
00209  *
00210  * PUBLIC: int CDB___bam_traverse __P((DBC *, db_lockmode_t,
00211  * PUBLIC:     db_pgno_t, int (*)(DB *, PAGE *, void *, int *), void *));
00212  */
00213 int
00214 CDB___bam_traverse(dbc, mode, root_pgno, callback, cookie)
00215         DBC *dbc;
00216         db_lockmode_t mode;
00217         db_pgno_t root_pgno;
00218         int (*callback)__P((DB *, PAGE *, void *, int *));
00219         void *cookie;
00220 {
00221         BINTERNAL *bi;
00222         BKEYDATA *bk;
00223         DB *dbp;
00224         DB_LOCK lock;
00225         PAGE *h;
00226         RINTERNAL *ri;
00227         db_indx_t indx;
00228         int already_put, ret, t_ret;
00229 
00230         dbp = dbc->dbp;
00231 
00232         if ((ret = CDB___db_lget(dbc, 0, root_pgno, mode, 0, &lock)) != 0)
00233                 return (ret);
00234         if ((ret = CDB_memp_fget(dbp->mpf, &root_pgno, 0, &h)) != 0)
00235                 goto err;
00236 
00237         switch (TYPE(h)) {
00238         case P_IBTREE:
00239                 for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
00240                         bi = GET_BINTERNAL(h, indx);
00241                         if (B_TYPE(bi->type) == B_OVERFLOW &&
00242                             (ret = CDB___db_traverse_big(dbp,
00243                             ((BOVERFLOW *)bi->data)->pgno,
00244                             callback, cookie)) != 0)
00245                                 goto err;
00246                         if ((ret = CDB___bam_traverse(
00247                             dbc, mode, bi->pgno, callback, cookie)) != 0)
00248                                 break;
00249                 }
00250                 break;
00251         case P_IRECNO:
00252                 for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
00253                         ri = GET_RINTERNAL(h, indx);
00254                         if ((ret = CDB___bam_traverse(
00255                             dbc, mode, ri->pgno, callback, cookie)) != 0)
00256                                 break;
00257                 }
00258                 break;
00259         case P_LBTREE:
00260                 for (indx = 0; indx < NUM_ENT(h); indx += P_INDX) {
00261                         bk = GET_BKEYDATA(h, indx);
00262                         if (B_TYPE(bk->type) == B_OVERFLOW &&
00263                             (ret = CDB___db_traverse_big(dbp,
00264                             GET_BOVERFLOW(h, indx)->pgno,
00265                             callback, cookie)) != 0)
00266                                 goto err;
00267                         bk = GET_BKEYDATA(h, indx + O_INDX);
00268                         if (B_TYPE(bk->type) == B_DUPLICATE &&
00269                             (ret = CDB___bam_traverse(dbc, mode,
00270                             GET_BOVERFLOW(h, indx + O_INDX)->pgno,
00271                             callback, cookie)) != 0)
00272                                 goto err;
00273                         if (B_TYPE(bk->type) == B_OVERFLOW &&
00274                             (ret = CDB___db_traverse_big(dbp,
00275                             GET_BOVERFLOW(h, indx + O_INDX)->pgno,
00276                             callback, cookie)) != 0)
00277                                 goto err;
00278                 }
00279                 break;
00280         }
00281 
00282         already_put = 0;
00283         if ((ret = callback(dbp, h, cookie, &already_put)) != 0)
00284                 goto err;
00285 
00286 err:    if (!already_put &&
00287             (t_ret = CDB_memp_fput(dbp->mpf, h, 0)) != 0 && ret != 0)
00288                 ret = t_ret;
00289         __LPUT(dbc, lock);
00290 
00291         return (ret);
00292 }
00293 
00294 /*
00295  * CDB___bam_stat_callback --
00296  *      Statistics callback.
00297  *
00298  * PUBLIC: int CDB___bam_stat_callback __P((DB *, PAGE *, void *, int *));
00299  */
00300 int
00301 CDB___bam_stat_callback(dbp, h, cookie, putp)
00302         DB *dbp;
00303         PAGE *h;
00304         void *cookie;
00305         int *putp;
00306 {
00307         DB_BTREE_STAT *sp;
00308         db_indx_t indx, top;
00309         u_int8_t type;
00310 
00311         sp = cookie;
00312         *putp = 0;
00313         top = NUM_ENT(h);
00314 
00315         switch (TYPE(h)) {
00316         case P_IBTREE:
00317         case P_IRECNO:
00318                 ++sp->bt_int_pg;
00319                 sp->bt_int_pgfree += P_FREESPACE(h);
00320                 break;
00321         case P_LBTREE:
00322                 /* Correct for on-page duplicates and deleted items. */
00323                 for (indx = 0; indx < top; indx += P_INDX) {
00324                         if (indx + P_INDX >= top ||
00325                             h->inp[indx] != h->inp[indx + P_INDX])
00326                                 ++sp->bt_nkeys;
00327 
00328                         type = GET_BKEYDATA(h, indx + O_INDX)->type;
00329                         if (!B_DISSET(type) && B_TYPE(type) != B_DUPLICATE)
00330                                 ++sp->bt_ndata;
00331                 }
00332 
00333                 ++sp->bt_leaf_pg;
00334                 sp->bt_leaf_pgfree += P_FREESPACE(h);
00335                 break;
00336         case P_LRECNO:
00337                 /*
00338                  * If walking a recno tree, then each of these items is a key.
00339                  * Otherwise, we're walking an off-page duplicate set.
00340                  */
00341                 if (dbp->type == DB_RECNO) {
00342                         sp->bt_nkeys += top;
00343                         sp->bt_ndata += top;
00344                         ++sp->bt_leaf_pg;
00345                         sp->bt_leaf_pgfree += P_FREESPACE(h);
00346                 } else {
00347                         sp->bt_ndata += top;
00348                         ++sp->bt_dup_pg;
00349                         sp->bt_dup_pgfree += P_FREESPACE(h);
00350                 }
00351                 break;
00352         case P_LDUP:
00353                 /* Correct for deleted items. */
00354                 for (indx = 0; indx < top; indx += O_INDX)
00355                         if (!B_DISSET(GET_BKEYDATA(h, indx)->type))
00356                                 ++sp->bt_ndata;
00357 
00358                 ++sp->bt_dup_pg;
00359                 sp->bt_dup_pgfree += P_FREESPACE(h);
00360                 break;
00361         case P_OVERFLOW:
00362                 ++sp->bt_over_pg;
00363                 sp->bt_over_pgfree += P_OVFLSPACE(dbp->pgsize, h);
00364                 break;
00365         case P_CMPR_FREE:
00366         case P_CMPR_INTERNAL:
00367                 break;
00368         default:
00369                 return (CDB___db_pgfmt(dbp, h->pgno));
00370         }
00371         return (0);
00372 }
00373 
00374 /*
00375  * CDB___bam_key_range --
00376  *      Return proportion of keys relative to given key.  The numbers are
00377  *      slightly skewed due to on page duplicates.
00378  *
00379  * PUBLIC: int CDB___bam_key_range __P((DB *,
00380  * PUBLIC:     DB_TXN *, DBT *, DB_KEY_RANGE *, u_int32_t));
00381  */
00382 int
00383 CDB___bam_key_range(dbp, txn, dbt, kp, flags)
00384         DB *dbp;
00385         DB_TXN *txn;
00386         DBT *dbt;
00387         DB_KEY_RANGE *kp;
00388         u_int32_t flags;
00389 {
00390         BTREE_CURSOR *cp;
00391         DBC *dbc;
00392         EPG *sp;
00393         double factor;
00394         int exact, ret, t_ret;
00395 
00396         PANIC_CHECK(dbp->dbenv);
00397         DB_ILLEGAL_BEFORE_OPEN(dbp, "DB->key_range");
00398 
00399         if (flags != 0)
00400                 return (CDB___db_ferr(dbp->dbenv, "DB->key_range", 0));
00401 
00402         /* Acquire a cursor. */
00403         if ((ret = dbp->cursor(dbp, txn, &dbc, 0)) != 0)
00404                 return (ret);
00405 
00406         DEBUG_LWRITE(dbc, NULL, "bam_key_range", NULL, NULL, 0);
00407 
00408         if ((ret = CDB___bam_search(dbc, dbt, S_STK_ONLY, 1, NULL, &exact)) != 0)
00409                 goto err;
00410 
00411         cp = (BTREE_CURSOR *)dbc->internal;
00412         kp->less = kp->greater = 0.0;
00413 
00414         factor = 1.0;
00415         /* Correct the leaf page. */
00416         cp->csp->entries /= 2;
00417         cp->csp->indx /= 2;
00418         for (sp = cp->sp; sp <= cp->csp; ++sp) {
00419                 /*
00420                  * At each level we know that pages greater than indx contain
00421                  * keys greater than what we are looking for and those less
00422                  * than indx are less than.  The one pointed to by indx may
00423                  * have some less, some greater or even equal.  If indx is
00424                  * equal to the number of entries, then the key is out of range
00425                  * and everything is less.
00426                  */
00427                 if (sp->indx == 0)
00428                         kp->greater += factor * (sp->entries - 1)/sp->entries;
00429                 else if (sp->indx == sp->entries)
00430                         kp->less += factor;
00431                 else {
00432                         kp->less += factor * sp->indx / sp->entries;
00433                         kp->greater += factor *
00434                             (sp->entries - sp->indx - 1) / sp->entries;
00435                 }
00436                 factor *= 1.0/sp->entries;
00437         }
00438 
00439         /*
00440          * If there was an exact match then assign 1 n'th to the key itself.
00441          * Otherwise that factor belongs to those greater than the key, unless
00442          * the key was out of range.
00443          */
00444         if (exact)
00445                 kp->equal = factor;
00446         else {
00447                 if (kp->less != 1)
00448                         kp->greater += factor;
00449                 kp->equal = 0;
00450         }
00451 
00452         BT_STK_CLR(cp);
00453 
00454 err:    if ((t_ret = dbc->c_close(dbc)) != 0 && ret == 0)
00455                 ret = t_ret;
00456 
00457         return (ret);
00458 }

Generated on Sun Jun 8 10:56:35 2008 for GNUmifluz by  doxygen 1.5.5