bt_stat.c

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 }