IT戦記

プログラミング、起業などについて書いているプログラマーのブログです😚

駄文 - C 言語難しいなあ

これを理解するのに数時間を要したよ orz
推移閉包を求める。
下半分は、無限ループ回避。←違った。もっかい読む
下半分は、グラフがループしている場合にそのループ内のノードは同じ bitset を持つことになるので、ループ内の全ノードに bitset をコピーしている。

static relation R;
static relation_nodes INDEX;
static relation_nodes VERTICES;
static relation_node top;
static relation_node infinity;
static bitsetv F;

static void
traverse (relation_node i)
{
  relation_node j;
  relation_node height;

  VERTICES[++top] = i;
  INDEX[i] = height = top;

  if (R[i])
    for (j = 0; R[i][j] != END_NODE; ++j)
      {
        if (INDEX[R[i][j]] == 0)
          traverse (R[i][j]);

        if (INDEX[i] > INDEX[R[i][j]])
          INDEX[i] = INDEX[R[i][j]];

        bitset_or (F[i], F[i], F[R[i][j]]);
      }

  if (INDEX[i] == height)
    for (;;)
      {
        j = VERTICES[top--];
        INDEX[j] = infinity;

        if (i == j)
          break;

        bitset_copy (F[j], F[i]);
      }
}
http://google.com/codesearch?hl=en&q=+bison-2.3/src/relation.c+show:fFa-8tgHjbU:SxNuVTmdWBo:gXWMzbhBK00&sa=N&cd=1&ct=rc&cs_p=ftp://ftp.gnu.org/gnu/bison/bison-2.3.tar.bz2&cs_f=bison-2.3/src/relation.c