#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
#include "mybdd.h"

typedef struct {
  char v;
  int f, t;
} bdd_t;

typedef struct {
  bdd_t *tbl;
  int   rootidx;
} bddtbl_t;

void *bdd_mk (char *trutbl, int numvars)
{
  int bdd_mk_ (char *trutbl, int numvars, int varidx,
               bdd_t **pbddtbl, int *pendidx, void **pbddtree)
  {
    if (varidx == numvars)
      return *trutbl;

    int numstat = 1 << (numvars - varidx);
    bdd_t ret;
    ret.f = bdd_mk_ (trutbl, numvars, varidx+1,
                     pbddtbl, pendidx, pbddtree);
    if (!memcmp (trutbl, trutbl + numstat/2, numstat/2))
      return ret.f;
    ret.t = bdd_mk_ (trutbl + numstat/2, numvars, varidx+1,
                     pbddtbl, pendidx, pbddtree);
    ret.v = varidx;
    (*pbddtbl)[*pendidx] = ret;

    int bdd_cmp (const void *bdd1, const void *bdd2)
    {
      static bdd_t *base;
      if (bdd1 == NULL) {
        base = bdd2;
        return 0;
      }
      return memcmp (base + (int )bdd1,
                     base + (int )bdd2,
                     sizeof (bdd_t));
    }
    bdd_cmp (NULL, *pbddtbl);
    int oldidx = (int )*(void **)tsearch ((void *)*pendidx, pbddtree, bdd_cmp);

    if (oldidx == *pendidx) {
      if (*pendidx % 0x80 == 0)
        *pbddtbl = realloc (*pbddtbl, (*pendidx + 0x81) * sizeof (bdd_t));
      return (*pendidx)++;
    } else
      return oldidx;
  }
  static const bdd_t termf = {0, 0, 0},
                     termt = {1, 0, 0};
  bddtbl_t *bddtbl = malloc (sizeof (bddtbl_t));
  bddtbl->tbl = malloc (0x81 * sizeof (bdd_t));
  bddtbl->tbl[0] = termf;
  bddtbl->tbl[1] = termt;

  void* bddtree = NULL;
  int endidx = 2;
  bddtbl->rootidx = bdd_mk_ (trutbl, numvars, 0,
                             &bddtbl->tbl, &endidx, &bddtree);
  bddtbl->tbl[endidx].v = -1;
  void empfunc (void* v) { return; }
  tdestroy (bddtree, empfunc); // вот в этом месте я рассчитываю получить свои мегабайты обратно

  return bddtbl;
}

void bdd_rm (void *this)
{
  free (((bddtbl_t *)this)->tbl);
  free (this);
}

int bdd_val (void *this, char *varval)
{
  bddtbl_t *this_ = this;
  int idx = this_->rootidx;
  while (this_->tbl[idx].f || this_->tbl[idx].t)
    idx = varval[this_->tbl[idx].v]
        ? this_->tbl[idx].t
        : this_->tbl[idx].f;

  return this_->tbl[idx].v;
}

void bdd_print (void *this, FILE *file)
{
  bddtbl_t *this_ = this;
  for (int i = 0; this_->tbl[i].v != -1; ++i)
    fprintf (file, "%d: %d, %d, %d\n",
             i, this_->tbl[i].v, this_->tbl[i].f, this_->tbl[i].t);
}