<commit_before>#include "bdd_impl.h"
#include "bdd_pair.h"
#include "bdd_pair_cache.h"
#include "bdd_double_ht.h"
#include "bdd_ht.h"
#include <stdio.h>

unsigned
bdd_var (bdd_mgr_t *mgr, bdd_t b)
{
    return bdd_get_node(mgr, b).var;
}

bdd_t
bdd_low (bdd_mgr_t *mgr, bdd_t b)
{
    return bdd_get_node(mgr, b).low;
}

bdd_t
bdd_high (bdd_mgr_t *mgr, bdd_t b)
{
    return bdd_get_node(mgr, b).high;
}


bdd_t
bdd_ith_var (bdd_mgr_t *mgr, unsigned i)
{
    bdd_t ith_var;
    bdd_mgr_check_invariants (mgr);
    assert (i < mgr->num_vars);

    ith_var = make_node_from_parts (mgr, i, bdd_false, bdd_true);
    bdd_mgr_check_invariants (mgr);
    return ith_var;
}


/* The type of an optional BDD. */
typedef struct maybe_bdd
{
    bdd_t value;
    bool has_value;
} maybe_bdd_t;

/* Create an optional BDD with no value. */
static inline maybe_bdd_t
maybe_bdd_nothing ()
{
    maybe_bdd_t m;
    m.value = 0;
    m.has_value = false;
    return m;
}

/* Create an optional BDD with the given value. */
static inline maybe_bdd_t
maybe_bdd_just (bdd_t v)
{
    maybe_bdd_t m;
    m.value = v;
    m.has_value = true;
    return m;
}

/* The type of operator-specific functions passed to bdd_apply.  A
 * bdd_apply_op_fun looks at its two BDD arguments and possibly
 * returns a BDD result.  Given two terminal BDDs, such a function
 * must return a result; in the other case, the function maybe return
 * a result if identies apply.  This allows the same recursive BDD
 * apply code to be reused, as only the operator-specific code
 * changes. */
typedef maybe_bdd_t (* bdd_apply_op_fun) (bdd_t b1, bdd_t b2);

typedef enum {make, apply} apply_command_type;

typedef struct
{
    apply_command_type ctype;
    union {
        struct {
            unsigned var;
            bdd_pair_t input;
        } make_input;
        bdd_pair_t apply_input;
    };
} apply_command_t;

static inline apply_command_t
make_node_cmd (unsigned var, bdd_pair_t input)
{
    apply_command_t cmd;
    cmd.ctype = make;
    cmd.make_input.var = var;
    cmd.make_input.input = input;
    return cmd;
}

static inline apply_command_t
apply_cmd (bdd_pair_t input)
{
    apply_command_t cmd;
    cmd.ctype = apply;
    cmd.apply_input = input;
    return cmd;
}

static void
fprint_command (FILE *f, apply_command_t cmd)
{
    if (cmd.ctype == make)
        fprintf (
            f, "MAKE %u %d %d\n",
            cmd.make_input.var,
            cmd.make_input.input.first,
            cmd.make_input.input.second
            );
    else
        fprintf (
            f, "APPLY %d %d\n",
            cmd.apply_input.first,
            cmd.apply_input.second
            );
}

#define STACK_PUSH(stk, val) (stk)[++(stk ## _idx)] = (val)
#define STACK_POP(stk) (stk)[(stk ## _idx)--]
#define STACK_EMPTY(stk) ((stk ## _idx) == -1)

static void
do_make_cmd (
    bdd_mgr_t *mgr,
    bdd_pair_cache_t cache,
    bdd_t *res_stk,
    int *res_stk_idx_ptr,
    apply_command_t cmd
    )
{
    bdd_t low, high, res;
    cache_entry_t *cache_val;
    int res_stk_idx = *res_stk_idx_ptr;
    /* fprintf (stderr, "!!! do_make_cmd\n"); */
    low = STACK_POP (res_stk);
    high = STACK_POP (res_stk);
    res = make_node_from_parts (mgr, cmd.make_input.var, low, high);
    STACK_PUSH (res_stk, res);
    cache_val = bdd_pair_cache_lookup (cache, cmd.make_input.input);
    cache_val->key = cmd.make_input.input;
    cache_val->value = res;
    *res_stk_idx_ptr = res_stk_idx;
}

static void
do_apply_cmd (
    bdd_mgr_t *mgr,
    bdd_pair_cache_t cache,
    bdd_apply_op_fun op,
    apply_command_t *cmd_stk,
    int *cmd_stk_idx_ptr,
    bdd_t *res_stk,
    int *res_stk_idx_ptr,
    apply_command_t cmd
    )
{
    cache_entry_t *cache_val;
    int cmd_stk_idx;
    int res_stk_idx;

    /* fprintf (stderr, "!!! do_apply_cmd\n"); */
    cmd_stk_idx = *cmd_stk_idx_ptr;
    res_stk_idx = *res_stk_idx_ptr;

    cache_val = bdd_pair_cache_lookup (cache, cmd.apply_input);
    if (bdd_pair_equal (cache_val->key, cmd.apply_input))
        STACK_PUSH (res_stk, cache_val->value);
    else {
        const bdd_t b1 = cmd.apply_input.first;
        const node_t n1 = bdd_get_node (mgr, b1);
        const bdd_t b2 = cmd.apply_input.second;
        const node_t n2 = bdd_get_node (mgr, b2);
        const maybe_bdd_t mresult = op (b1, b2);
        if (mresult.has_value)
            STACK_PUSH (res_stk, mresult.value);
        else {
            bdd_pair_t p1, p2;
            unsigned var;
            if (n1.var == n2.var) {
                var = n1.var;
                p1.first = n1.low;
                p1.second = n2.low;
                p2.first = n1.high;
                p2.second = n2.high;
            }
            else if (n1.var < n2.var) {
                var = n1.var;
                p1.first = n1.low;
                p1.second = b2;
                p2.first = n1.high;
                p2.second = b2;
            }
            else {
                assert (n1.var > n2.var);
                var = n2.var;
                p1.first = b1;
                p1.second = n2.low;
                p2.first = b1;
                p2.second = n2.high;
            }
            STACK_PUSH (cmd_stk, make_node_cmd (var, cmd.apply_input));
            /* fprintf (stderr, "!!! push "); */
            /* fprint_command (stderr, make_node_cmd (var, cmd.apply_input)); */
            STACK_PUSH (cmd_stk, apply_cmd (p1));
            /* fprintf (stderr, "!!! push "); */
            /* fprint_command (stderr, apply_cmd (p1)); */
            STACK_PUSH (cmd_stk, apply_cmd (p2));
            /* fprintf (stderr, "!!! push "); */
            /* fprint_command (stderr, apply_cmd (p2)); */
        }
    }

    /* fprintf (stderr, "!!! *res_stk_idx_ptr is %d\n", *res_stk_idx_ptr); */
    /* fprintf (stderr, "!!! res_stk_idx is %d\n", res_stk_idx); */
    /* fprintf (stderr, "!!! *cmd_stk_idx_ptr is %d\n", *cmd_stk_idx_ptr); */
    /* fprintf (stderr, "!!! cmd_stk_idx is %d\n", cmd_stk_idx); */
    assert ((*res_stk_idx_ptr + 1 == res_stk_idx) !=
            (*cmd_stk_idx_ptr + 3 == cmd_stk_idx));

    *res_stk_idx_ptr = res_stk_idx;
    *cmd_stk_idx_ptr = cmd_stk_idx;
}

static bdd_t
bdd_apply_nonrec (bdd_mgr_t *mgr,
                  bdd_pair_cache_t cache,
                  bdd_apply_op_fun op,
                  bdd_pair_t start_pair)
{
    apply_command_t *cmd_stk;    /* stack for commands */
    int cmd_stk_idx;
    bdd_t *res_stk;              /* stack for results */
    int res_stk_idx;
    bdd_t result;                /* final result */

    cmd_stk = (apply_command_t *) malloc (1000000 * sizeof(apply_command_t));
    cmd_stk_idx = -1;
    STACK_PUSH (cmd_stk, apply_cmd (start_pair));
    /* fprintf (stderr, "!!! push "); */
    /* fprint_command (stderr, apply_cmd (start_pair)); */
    assert (cmd_stk_idx == 0);
    res_stk = (bdd_t *) malloc (1000000 * sizeof(bdd_t));
    res_stk_idx = -1;

    while (!STACK_EMPTY(cmd_stk)) {
        apply_command_t cmd = STACK_POP (cmd_stk);
        /* fprint_command (stderr, cmd); */
        if (cmd.ctype == make) {
            do_make_cmd (mgr, cache, res_stk, &res_stk_idx, cmd);
        }
        else {
            do_apply_cmd (mgr, cache, op,
                          cmd_stk, &cmd_stk_idx,
                          res_stk, &res_stk_idx,
                          cmd);
        }
    }

    /* fprintf (stderr, "!!! cmd_stk_idx is %d\n", cmd_stk_idx); */
    /* fprintf (stderr, "!!! res_stk_idx is %d\n", res_stk_idx); */
    assert (cmd_stk_idx == -1);
    assert (res_stk_idx == 0);
    result = STACK_POP (res_stk);

    free (res_stk);
    free (cmd_stk);

    return result;
}

#undef STACK_EMPTY<commit_msg>Use stack- instead of heap-allocated arrays.<commit_after>#include "bdd_impl.h"
#include "bdd_pair.h"
#include "bdd_pair_cache.h"
#include "bdd_double_ht.h"
#include "bdd_ht.h"
#include <stdio.h>

unsigned
bdd_var (bdd_mgr_t *mgr, bdd_t b)
{
    return bdd_get_node(mgr, b).var;
}

bdd_t
bdd_low (bdd_mgr_t *mgr, bdd_t b)
{
    return bdd_get_node(mgr, b).low;
}

bdd_t
bdd_high (bdd_mgr_t *mgr, bdd_t b)
{
    return bdd_get_node(mgr, b).high;
}


bdd_t
bdd_ith_var (bdd_mgr_t *mgr, unsigned i)
{
    bdd_t ith_var;
    bdd_mgr_check_invariants (mgr);
    assert (i < mgr->num_vars);

    ith_var = make_node_from_parts (mgr, i, bdd_false, bdd_true);
    bdd_mgr_check_invariants (mgr);
    return ith_var;
}


/* The type of an optional BDD. */
typedef struct maybe_bdd
{
    bdd_t value;
    bool has_value;
} maybe_bdd_t;

/* Create an optional BDD with no value. */
static inline maybe_bdd_t
maybe_bdd_nothing ()
{
    maybe_bdd_t m;
    m.value = 0;
    m.has_value = false;
    return m;
}

/* Create an optional BDD with the given value. */
static inline maybe_bdd_t
maybe_bdd_just (bdd_t v)
{
    maybe_bdd_t m;
    m.value = v;
    m.has_value = true;
    return m;
}

/* The type of operator-specific functions passed to bdd_apply.  A
 * bdd_apply_op_fun looks at its two BDD arguments and possibly
 * returns a BDD result.  Given two terminal BDDs, such a function
 * must return a result; in the other case, the function maybe return
 * a result if identies apply.  This allows the same recursive BDD
 * apply code to be reused, as only the operator-specific code
 * changes. */
typedef maybe_bdd_t (* bdd_apply_op_fun) (bdd_t b1, bdd_t b2);

typedef enum {make, apply} apply_command_type;

typedef struct
{
    apply_command_type ctype;
    union {
        struct {
            unsigned var;
            bdd_pair_t input;
        } make_input;
        bdd_pair_t apply_input;
    };
} apply_command_t;

static inline apply_command_t
make_node_cmd (unsigned var, bdd_pair_t input)
{
    apply_command_t cmd;
    cmd.ctype = make;
    cmd.make_input.var = var;
    cmd.make_input.input = input;
    return cmd;
}

static inline apply_command_t
apply_cmd (bdd_pair_t input)
{
    apply_command_t cmd;
    cmd.ctype = apply;
    cmd.apply_input = input;
    return cmd;
}

static void
fprint_command (FILE *f, apply_command_t cmd)
{
    if (cmd.ctype == make)
        fprintf (
            f, "MAKE %u %d %d\n",
            cmd.make_input.var,
            cmd.make_input.input.first,
            cmd.make_input.input.second
            );
    else
        fprintf (
            f, "APPLY %d %d\n",
            cmd.apply_input.first,
            cmd.apply_input.second
            );
}

#define STACK_PUSH(stk, val) (stk)[++(stk ## _idx)] = (val)
#define STACK_POP(stk) (stk)[(stk ## _idx)--]
#define STACK_EMPTY(stk) ((stk ## _idx) == -1)

static void
do_make_cmd (
    bdd_mgr_t *mgr,
    bdd_pair_cache_t cache,
    bdd_t *res_stk,
    int *res_stk_idx_ptr,
    apply_command_t cmd
    )
{
    bdd_t low, high, res;
    cache_entry_t *cache_val;
    int res_stk_idx = *res_stk_idx_ptr;
    /* fprintf (stderr, "!!! do_make_cmd\n"); */
    low = STACK_POP (res_stk);
    high = STACK_POP (res_stk);
    res = make_node_from_parts (mgr, cmd.make_input.var, low, high);
    STACK_PUSH (res_stk, res);
    cache_val = bdd_pair_cache_lookup (cache, cmd.make_input.input);
    cache_val->key = cmd.make_input.input;
    cache_val->value = res;
    *res_stk_idx_ptr = res_stk_idx;
}

static void
do_apply_cmd (
    bdd_mgr_t *mgr,
    bdd_pair_cache_t cache,
    bdd_apply_op_fun op,
    apply_command_t *cmd_stk,
    int *cmd_stk_idx_ptr,
    bdd_t *res_stk,
    int *res_stk_idx_ptr,
    apply_command_t cmd
    )
{
    cache_entry_t *cache_val;
    int cmd_stk_idx;
    int res_stk_idx;

    /* fprintf (stderr, "!!! do_apply_cmd\n"); */
    cmd_stk_idx = *cmd_stk_idx_ptr;
    res_stk_idx = *res_stk_idx_ptr;

    cache_val = bdd_pair_cache_lookup (cache, cmd.apply_input);
    if (bdd_pair_equal (cache_val->key, cmd.apply_input))
        STACK_PUSH (res_stk, cache_val->value);
    else {
        const bdd_t b1 = cmd.apply_input.first;
        const node_t n1 = bdd_get_node (mgr, b1);
        const bdd_t b2 = cmd.apply_input.second;
        const node_t n2 = bdd_get_node (mgr, b2);
        const maybe_bdd_t mresult = op (b1, b2);
        if (mresult.has_value)
            STACK_PUSH (res_stk, mresult.value);
        else {
            bdd_pair_t p1, p2;
            unsigned var;
            if (n1.var == n2.var) {
                var = n1.var;
                p1.first = n1.low;
                p1.second = n2.low;
                p2.first = n1.high;
                p2.second = n2.high;
            }
            else if (n1.var < n2.var) {
                var = n1.var;
                p1.first = n1.low;
                p1.second = b2;
                p2.first = n1.high;
                p2.second = b2;
            }
            else {
                assert (n1.var > n2.var);
                var = n2.var;
                p1.first = b1;
                p1.second = n2.low;
                p2.first = b1;
                p2.second = n2.high;
            }
            STACK_PUSH (cmd_stk, make_node_cmd (var, cmd.apply_input));
            /* fprintf (stderr, "!!! push "); */
            /* fprint_command (stderr, make_node_cmd (var, cmd.apply_input)); */
            STACK_PUSH (cmd_stk, apply_cmd (p1));
            /* fprintf (stderr, "!!! push "); */
            /* fprint_command (stderr, apply_cmd (p1)); */
            STACK_PUSH (cmd_stk, apply_cmd (p2));
            /* fprintf (stderr, "!!! push "); */
            /* fprint_command (stderr, apply_cmd (p2)); */
        }
    }

    /* fprintf (stderr, "!!! *res_stk_idx_ptr is %d\n", *res_stk_idx_ptr); */
    /* fprintf (stderr, "!!! res_stk_idx is %d\n", res_stk_idx); */
    /* fprintf (stderr, "!!! *cmd_stk_idx_ptr is %d\n", *cmd_stk_idx_ptr); */
    /* fprintf (stderr, "!!! cmd_stk_idx is %d\n", cmd_stk_idx); */
    assert ((*res_stk_idx_ptr + 1 == res_stk_idx) !=
            (*cmd_stk_idx_ptr + 3 == cmd_stk_idx));

    *res_stk_idx_ptr = res_stk_idx;
    *cmd_stk_idx_ptr = cmd_stk_idx;
}

static bdd_t
bdd_apply_nonrec (bdd_mgr_t *mgr,
                  bdd_pair_cache_t cache,
                  bdd_apply_op_fun op,
                  bdd_pair_t start_pair)
{
    apply_command_t cmd_stk[1000];    /* stack for commands */
    int cmd_stk_idx;
    bdd_t res_stk[1000];              /* stack for results */
    int res_stk_idx;
    bdd_t result;                /* final result */

    cmd_stk_idx = -1;
    STACK_PUSH (cmd_stk, apply_cmd (start_pair));
    /* fprintf (stderr, "!!! push "); */
    /* fprint_command (stderr, apply_cmd (start_pair)); */
    assert (cmd_stk_idx == 0);
    res_stk_idx = -1;

    while (!STACK_EMPTY(cmd_stk)) {
        apply_command_t cmd = STACK_POP (cmd_stk);
        /* fprint_command (stderr, cmd); */
        if (cmd.ctype == make) {
            do_make_cmd (mgr, cache, res_stk, &res_stk_idx, cmd);
        }
        else {
            do_apply_cmd (mgr, cache, op,
                          cmd_stk, &cmd_stk_idx,
                          res_stk, &res_stk_idx,
                          cmd);
        }
    }

    /* fprintf (stderr, "!!! cmd_stk_idx is %d\n", cmd_stk_idx); */
    /* fprintf (stderr, "!!! res_stk_idx is %d\n", res_stk_idx); */
    assert (cmd_stk_idx == -1);
    assert (res_stk_idx == 0);
    result = STACK_POP (res_stk);

    return result;
}

#undef STACK_EMPTY
{'fraction_non_alphanumeric': 0.1190068493150685, 'fraction_numerical': 0.009088514225500527, 'mean_word_length': 2.1901260504201683, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6051575', 'n_tokens_mistral': 5957, 'n_tokens_neox': 5897, 'n_words': 1262}