summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2024-05-23 11:28:14 -0400
committerTavian Barnes <tavianator@tavianator.com>2024-05-23 14:34:33 -0400
commit43d4fb7b1996cb453120143581e92b5b6e07c265 (patch)
tree278dfeda0fed5dcc97ffb698eb8c107d34acdb08 /src
parent25b4e40cd32175f39b94ffaa034bd46b428d8545 (diff)
downloadbfs-43d4fb7b1996cb453120143581e92b5b6e07c265.tar.xz
opt: Implement a general estimate_odds() function
Diffstat (limited to 'src')
-rw-r--r--src/opt.c26
1 files changed, 17 insertions, 9 deletions
diff --git a/src/opt.c b/src/opt.c
index 88aba5a..aef98ff 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -2176,17 +2176,20 @@ static struct bfs_expr *optimize(struct bfs_opt *opt, struct bfs_expr *expr) {
return expr;
}
-/** Estimate the odds of an expression calling stat(). */
-static float expr_stat_odds(struct bfs_expr *expr) {
- if (expr->calls_stat) {
+/** An expression predicate. */
+typedef bool expr_pred(const struct bfs_expr *expr);
+
+/** Estimate the odds that a matching expression will be evaluated. */
+static float estimate_odds(const struct bfs_expr *expr, expr_pred *pred) {
+ if (pred(expr)) {
return 1.0;
}
- float nostat_odds = 1.0;
+ float nonmatch_odds = 1.0;
float reached_odds = 1.0;
for_expr (child, expr) {
- float child_odds = expr_stat_odds(child);
- nostat_odds *= 1.0 - reached_odds * child_odds;
+ float child_odds = estimate_odds(child, pred);
+ nonmatch_odds *= 1.0 - reached_odds * child_odds;
if (expr->eval_fn == eval_and) {
reached_odds *= child->probability;
@@ -2195,7 +2198,12 @@ static float expr_stat_odds(struct bfs_expr *expr) {
}
}
- return 1.0 - nostat_odds;
+ return 1.0 - nonmatch_odds;
+}
+
+/** Whether an expression calls stat(). */
+static bool calls_stat(const struct bfs_expr *expr) {
+ return expr->calls_stat;
}
/** Estimate the odds of calling stat(). */
@@ -2204,10 +2212,10 @@ static float estimate_stat_odds(struct bfs_ctx *ctx) {
return 1.0;
}
- float nostat_odds = 1.0 - expr_stat_odds(ctx->exclude);
+ float nostat_odds = 1.0 - estimate_odds(ctx->exclude, calls_stat);
float reached_odds = 1.0 - ctx->exclude->probability;
- float expr_odds = expr_stat_odds(ctx->expr);
+ float expr_odds = estimate_odds(ctx->expr, calls_stat);
nostat_odds *= 1.0 - reached_odds * expr_odds;
return 1.0 - nostat_odds;