abitset.c

bison 2.0 主要可以用来做语法分析用的

  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++)
      if (*srcp++ & *dstp++)
	  return false;

  return true;
}


static void
abitset_and (bitset dst, bitset src1, bitset src2)
{
  bitset_windex i;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++)
      *dstp++ = *src1p++ & *src2p++;
}


static bool
abitset_and_cmp (bitset dst, bitset src1, bitset src2)
{
  bitset_windex i;
  bool changed = false;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++, dstp++)
    {
      bitset_word tmp = *src1p++ & *src2p++;

      if (*dstp != tmp)
	{
	  changed = true;
	  *dstp = tmp;
	}
    }
  return changed;
}


static void
abitset_andn (bitset dst, bitset src1, bitset src2)
{
  bitset_windex i;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++)
      *dstp++ = *src1p++ & ~(*src2p++);
}


static bool
abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
{
  bitset_windex i;
  bool changed = false;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++, dstp++)
    {
      bitset_word tmp = *src1p++ & ~(*src2p++);

      if (*dstp != tmp)
	{
	  changed = true;
	  *dstp = tmp;
	}
    }
  return changed;
}


static void
abitset_or (bitset dst, bitset src1, bitset src2)
{
  bitset_windex i;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++)
      *dstp++ = *src1p++ | *src2p++;
}


static bool
abitset_or_cmp (bitset dst, bitset src1, bitset src2)
{
  bitset_windex i;
  bool changed = false;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++, dstp++)
    {
      bitset_word tmp = *src1p++ | *src2p++;

      if (*dstp != tmp)
	{
	  changed = true;
	  *dstp = tmp;
	}
    }
  return changed;
}


static void
abitset_xor (bitset dst, bitset src1, bitset src2)
{
  bitset_windex i;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++)
      *dstp++ = *src1p++ ^ *src2p++;
}


static bool
abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
{
  bitset_windex i;
  bool changed = false;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++, dstp++)
    {
      bitset_word tmp = *src1p++ ^ *src2p++;

      if (*dstp != tmp)
	{
	  changed = true;
	  *dstp = tmp;
	}
    }
  return changed;
}


static void
abitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
{
  bitset_windex i;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *src3p = ABITSET_WORDS (src3);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++)
      *dstp++ = (*src1p++ & *src2p++) | *src3p++;
}


static bool
abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
{
  bitset_windex i;
  bool changed = false;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *src3p = ABITSET_WORDS (src3);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++, dstp++)
    {
      bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;

      if (*dstp != tmp)
	{
	  changed = true;
	  *dstp = tmp;
	}
    }
  return changed;
}


static void
abitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
{
  bitset_windex i;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *src3p = ABITSET_WORDS (src3);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++)
      *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
}


static bool
abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
{
  bitset_windex i;
  bool changed = false;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *src3p = ABITSET_WORDS (src3);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++, dstp++)
    {
      bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;

      if (*dstp != tmp)
	{
	  changed = true;
	  *dstp = tmp;
	}
    }
  return changed;
}


static void
abitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
{
  bitset_windex i;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *src3p = ABITSET_WORDS (src3);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++)
      *dstp++ = (*src1p++ | *src2p++) & *src3p++;
}


static bool
abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
{
  bitset_windex i;
  bool changed = false;
  bitset_word *src1p = ABITSET_WORDS (src1);
  bitset_word *src2p = ABITSET_WORDS (src2);
  bitset_word *src3p = ABITSET_WORDS (src3);
  bitset_word *dstp = ABITSET_WORDS (dst);
  bitset_windex size = dst->b.csize;

  for (i = 0; i < size; i++, dstp++)
    {
      bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;

      if (*dstp != tmp)
	{
	  changed = true;
	  *dstp = tmp;
	}
    }
  return changed;
}


static void
abitset_copy (bitset dst, bitset src)
{
  if (BITSET_COMPATIBLE_ (dst, src))
      abitset_copy1 (dst, src);
  else
      bitset_copy_ (dst, src);
}


/* Vector of operations for single word bitsets.  */
struct bitset_vtable abitset_small_vtable = {
  abitset_set,
  abitset_reset,
  bitset_toggle_,
  abitset_test,
  abitset_resize,
  bitset_size_,
  bitset_count_,
  abitset_empty_p,
  abitset_ones,
  abitset_zero,
  abitset_copy,
  abitset_disjoint_p,
  abitset_equal_p,
  abitset_not,
  abitset_subset_p,
  abitset_and,
  abitset_and_cmp,
  abitset_andn,
  abitset_andn_cmp,
  abitset_or,
  abitset_or_cmp,
  abitset_xor,
  abitset_xor_cmp,
  abitset_and_or,
  abitset_and_or_cmp,
  abitset_andn_or,
  abitset_andn_or_cmp,
  abitset_or_and,
  abitset_or_and_cmp,
  abitset_small_list,
  abitset_list_reverse,
  NULL,
  BITSET_ARRAY
};


/* Vector of operations for multiple word bitsets.  */
struct bitset_vtable abitset_vtable = {
  abitset_set,
  abitset_reset,
  bitset_toggle_,
  abitset_test,
  abitset_resize,
  bitset_size_,
  bitset_count_,
  abitset_empty_p,
  abitset_ones,
  abitset_zero,
  abitset_copy,
  abitset_disjoint_p,
  abitset_equal_p,
  abitset_not,
  abitset_subset_p,
  abitset_and,
  abitset_and_cmp,
  abitset_andn,
  abitset_andn_cmp,
  abitset_or,
  abitset_or_cmp,
  abitset_xor,
  abitset_xor_cmp,
  abitset_and_or,
  abitset_and_or_cmp,
  abitset_andn_or,
  abitset_andn_or_cmp,
  abitset_or_and,
  abitset_or_and_cmp,
  abitset_list,
  abitset_list_reverse,
  NULL,
  BITSET_ARRAY
};


size_t
abitset_bytes (bitset_bindex n_bits)
{
  bitset_windex size;
  size_t bytes;
  size_t header_size = offsetof (union bitset_union, a.words);
  struct bitset_align_struct { char a; union bitset_union b; };
  size_t bitset_alignment = offsetof (struct bitset_align_struct, b);

  size = ABITSET_N_WORDS (n_bits);
  bytes = header_size + size * sizeof (bitset_word);

  /* Align the size properly for a vector of abitset objects.  */
  if (header_size % bitset_alignment != 0
      || sizeof (bitset_word) % bitset_alignment != 0)
    {
      bytes += bitset_alignment - 1;
      bytes -= bytes % bitset_alignment;
    }

  return bytes;
}


bitset
abitset_init (bitset bset, bitset_bindex n_bits)
{
  bitset_windex size;

  size = ABITSET_N_WORDS (n_bits);
  BITSET_NBITS_ (bset) = n_bits;

  /* Use optimized routines if bitset fits within a single word.
     There is probably little merit if using caching since
     the small bitset will always fit in the cache.  */
  if (size == 1)
    bset->b.vtable = &abitset_small_vtable;
  else
    bset->b.vtable = &abitset_vtable;

  bset->b.cindex = 0;
  bset->b.csize = size;
  bset->b.cdata = ABITSET_WORDS (bset);
  return bset;
}