ebitset.c

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

	  bitset_windex woffset;
	  bitset_word *srcp = EBITSET_WORDS (elt);

	  windex = bitno / BITSET_WORD_BITS;
	  woffset = eindex * EBITSET_ELT_WORDS;

	  for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
	    {
	      word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);

	      for (; word; bitno++)
		{
		  if (word & 1)
		    {
		      list[count++] = bitno;
		      if (count >= num)
			{
			  *next = bitno + 1;
			  return count;
			}
		    }
		  word >>= 1;
		}
	      bitno = (windex + 1) * BITSET_WORD_BITS;
	    }
	}

      /* Skip to next element.  */
      eindex++;
    }

  /* If num is 1, we could speed things up with a binary search
     of the word of interest.  */

  for (; eindex < size; eindex++)
    {
      int i;
      bitset_word *srcp;

      elt = elts[eindex];
      if (!elt)
	continue;

      srcp = EBITSET_WORDS (elt);
      windex = eindex * EBITSET_ELT_WORDS;

      if ((count + EBITSET_ELT_BITS) < num)
	{
	  /* The coast is clear, plant boot!  */

#if EBITSET_ELT_WORDS == 2
	  word = srcp[0];
	  if (word)
	    {
	      if (!(word & 0xffff))
		{
		  word >>= 16;
		  bitno += 16;
		}
	      if (!(word & 0xff))
		{
		  word >>= 8;
		  bitno += 8;
		}
	      for (; word; bitno++)
		{
		  if (word & 1)
		    list[count++] = bitno;
		  word >>= 1;
		}
	    }
	  windex++;
	  bitno = windex * BITSET_WORD_BITS;

	  word = srcp[1];
	  if (word)
	    {
	      if (!(word & 0xffff))
		{
		  word >>= 16;
		  bitno += 16;
		}
	      for (; word; bitno++)
		{
		  if (word & 1)
		    list[count++] = bitno;
		  word >>= 1;
		}
	    }
	  windex++;
	  bitno = windex * BITSET_WORD_BITS;
#else
	  for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
	    {
	      bitno = windex * BITSET_WORD_BITS;

	      word = srcp[i];
	      if (word)
		{
		  if (!(word & 0xffff))
		    {
		      word >>= 16;
		      bitno += 16;
		    }
		  if (!(word & 0xff))
		    {
		      word >>= 8;
		      bitno += 8;
		    }
		  for (; word; bitno++)
		    {
		      if (word & 1)
			list[count++] = bitno;
		      word >>= 1;
		    }
		}
	    }
#endif
	}
      else
	{
	  /* Tread more carefully since we need to check
	     if array overflows.  */

	  for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
	    {
	      bitno = windex * BITSET_WORD_BITS;

	      for (word = srcp[i]; word; bitno++)
		{
		  if (word & 1)
		    {
		      list[count++] = bitno;
		      if (count >= num)
			{
			  *next = bitno + 1;
			  return count;
			}
		    }
		  word >>= 1;
		}
	    }
	}
    }

  *next = bitno;
  return count;
}


/* Ensure that any unused bits within the last element are clear.  */
static inline void
ebitset_unused_clear (bitset dst)
{
  unsigned int last_bit;
  bitset_bindex n_bits;
  
  n_bits = BITSET_NBITS_ (dst);
  last_bit = n_bits % EBITSET_ELT_BITS;
  
  if (last_bit)
    {
      bitset_windex eindex;
      ebitset_elts *elts;
      ebitset_elt *elt;

      elts = EBITSET_ELTS (dst);
      
      eindex = n_bits / EBITSET_ELT_BITS;
      
      elt = elts[eindex];
      if (elt)
	{
	  bitset_windex windex;
	  bitset_windex woffset;
	  bitset_word *srcp = EBITSET_WORDS (elt);
	  
	  windex = n_bits / BITSET_WORD_BITS;
	  woffset = eindex * EBITSET_ELT_WORDS;
	  
	  srcp[windex - woffset] &= ((bitset_word) 1 << last_bit) - 1;	  
	  windex++;
	  for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
	    srcp[windex - woffset] = 0;
	}
    }
}


static void
ebitset_ones (bitset dst)
{
  bitset_windex j;
  ebitset_elt *elt;

  for (j = 0; j < EBITSET_SIZE (dst); j++)
    {
      /* Create new elements if they cannot be found.  Perhaps
	 we should just add pointers to a ones element?  */
      elt =
	ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);
      memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
    }
  EBITSET_NONZERO_SET (dst);
  ebitset_unused_clear (dst);
}


static bool
ebitset_empty_p (bitset dst)
{
  ebitset_elts *elts;
  bitset_windex j;

  if (EBITSET_ZERO_P (dst))
    return 1;

  elts = EBITSET_ELTS (dst);
  for (j = 0; j < EBITSET_SIZE (dst); j++)
    {
      ebitset_elt *elt = elts[j];

      if (elt)
	{
	  if (!ebitset_elt_zero_p (elt))
	    return 0;
	  /* Do some weeding as we go.  */
	  ebitset_elt_remove (dst, j);
	}
    }

  /* All the bits are zero.  We could shrink the elts.
     For now just mark DST as known to be zero.  */
  EBITSET_ZERO_SET (dst);
  return 1;
}


static void
ebitset_not (bitset dst, bitset src)
{
  unsigned int i;
  ebitset_elt *selt;
  ebitset_elt *delt;
  bitset_windex j;

  ebitset_resize (dst, BITSET_NBITS_ (src));

  for (j = 0; j < EBITSET_SIZE (src); j++)
    {
      /* Create new elements for dst if they cannot be found
	 or substitute zero elements if src elements not found.  */
      selt =
	ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_SUBST);
      delt =
	ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);

      for (i = 0; i < EBITSET_ELT_WORDS; i++)
	EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
    }
  EBITSET_NONZERO_SET (dst);
  ebitset_unused_clear (dst);
}


/* Is DST == DST | SRC?  */
static bool
ebitset_subset_p (bitset dst, bitset src)
{
  bitset_windex j;
  ebitset_elts *selts;
  ebitset_elts *delts;
  bitset_windex ssize;
  bitset_windex dsize;

  selts = EBITSET_ELTS (src);
  delts = EBITSET_ELTS (dst);

  ssize = EBITSET_SIZE (src);
  dsize = EBITSET_SIZE (dst);

  for (j = 0; j < ssize; j++)
    {
      unsigned int i;
      ebitset_elt *selt;
      ebitset_elt *delt;

      selt = j < ssize ? selts[j] : 0;
      delt = j < dsize ? delts[j] : 0;

      if (!selt && !delt)
	continue;

      if (!selt)
	selt = &ebitset_zero_elts[0];
      if (!delt)
	delt = &ebitset_zero_elts[0];

      for (i = 0; i < EBITSET_ELT_WORDS; i++)
	if (EBITSET_WORDS (delt)[i]
	    != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
	  return false;
    }
  return true;
}


/* Is DST & SRC == 0?  */
static bool
ebitset_disjoint_p (bitset dst, bitset src)
{
  bitset_windex j;
  ebitset_elts *selts;
  ebitset_elts *delts;
  bitset_windex ssize;
  bitset_windex dsize;

  selts = EBITSET_ELTS (src);
  delts = EBITSET_ELTS (dst);

  ssize = EBITSET_SIZE (src);
  dsize = EBITSET_SIZE (dst);

  for (j = 0; j < ssize; j++)
    {
      unsigned int i;
      ebitset_elt *selt;
      ebitset_elt *delt;

      selt = j < ssize ? selts[j] : 0;
      delt = j < dsize ? delts[j] : 0;

      if (!selt || !delt)
	continue;

      for (i = 0; i < EBITSET_ELT_WORDS; i++)
	if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
	  return false;
    }
  return true;
}



static bool
ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
{
  bitset_windex ssize1;
  bitset_windex ssize2;
  bitset_windex dsize;
  bitset_windex size;
  ebitset_elts *selts1;
  ebitset_elts *selts2;
  ebitset_elts *delts;
  bitset_word *srcp1;
  bitset_word *srcp2;
  bitset_word *dstp;
  bool changed = false;
  unsigned int i;
  bitset_windex j;

  ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2)));

  ssize1 = EBITSET_SIZE (src1);
  ssize2 = EBITSET_SIZE (src2);
  dsize = EBITSET_SIZE (dst);
  size = ssize1;
  if (size < ssize2)
    size = ssize2;

  selts1 = EBITSET_ELTS (src1);
  selts2 = EBITSET_ELTS (src2);
  delts = EBITSET_ELTS (dst);

  for (j = 0; j < size; j++)
    {
      ebitset_elt *selt1;
      ebitset_elt *selt2;
      ebitset_elt *delt;

      selt1 = j < ssize1 ? selts1[j] : 0;
      selt2 = j < ssize2 ? selts2[j] : 0;
      delt = j < dsize ? delts[j] : 0;

      if (!selt1 && !selt2)
	{
	  if (delt)
	    {
	      changed = true;
	      ebitset_elt_remove (dst, j);
	    }
	  continue;
	}

      if (!selt1)
	selt1 = &ebitset_zero_elts[0];
      if (!selt2)
	selt2 = &ebitset_zero_elts[0];
      if (!delt)
	delt = ebitset_elt_calloc ();
      else
	delts[j] = 0;

      srcp1 = EBITSET_WORDS (selt1);
      srcp2 = EBITSET_WORDS (selt2);
      dstp = EBITSET_WORDS (delt);
      switch (op)
	{
	case BITSET_OP_OR:
	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
	    {
	      bitset_word tmp = *srcp1++ | *srcp2++;

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

	case BITSET_OP_AND:
	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
	    {
	      bitset_word tmp = *srcp1++ & *srcp2++;

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

	case BITSET_OP_XOR:
	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
	    {
	      bitset_word tmp = *srcp1++ ^ *srcp2++;

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

	case BITSET_OP_ANDN:
	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
	    {
	      bitset_word tmp = *srcp1++ & ~(*srcp2++);

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

	default:
	  abort ();
	}

      if (!ebitset_elt_zero_p (delt))
	{
	  ebitset_elt_add (dst, delt, j);
	}
      else
	{
	  ebitset_elt_free (delt);
	}
    }

  /* If we have elements of DST left over, free them all.  */
  for (; j < dsize; j++)
    {
      ebitset_elt *delt;

      changed = true;

      delt = delts[j];

      if (delt)
	ebitset_elt_remove (dst, j);
    }

  EBITSET_NONZERO_SET (dst);
  return changed;
}


static bool
ebitset_and_cmp (bitset dst, bitset src1, bitset src2)
{
  bool changed;

  if (EBITSET_ZERO_P (src2))
    {
      ebitset_weed (dst);
      changed = EBITSET_ZERO_P (dst);
      ebitset_zero (dst);
      return changed;
    }
  else if (EBITSET_ZERO_P (src1))
    {
      ebitset_weed (dst);
      changed = EBITSET_ZERO_P (dst);
      ebitset_zero (dst);
      return changed;
    }
  return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
}


static void
ebitset_and (bitset dst, bitset src1, bitset src2)
{
  ebitset_and_cmp (dst, src1, src2);
}


static bool
ebitset_andn_cmp (bitset dst, bitset src1, bitset src2)
{
  bool changed;

  if (EBITSET_ZERO_P (src2))
    {
      return ebitset_copy_cmp (dst, src1);
    }
  else if (EBITSET_ZERO_P (src1))
    {
      ebitset_weed (dst);
      changed = EBITSET_ZERO_P (dst);
      ebitset_zero (dst);
      return changed;
    }
  return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
}


static void
ebitset_andn (bitset dst, bitset src1, bitset src2)
{
  ebitset_andn_cmp (dst, src1, src2);
}


static bool
ebitset_or_cmp (bitset dst, bitset src1, bitset src2)
{
  if (EBITSET_ZERO_P (src2))
    {
      return ebitset_copy_cmp (dst, src1);
    }
  else if (EBITSET_ZERO_P (src1))
    {
      return ebitset_copy_cmp (dst, src2);
    }
  return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
}


static void
ebitset_or (bitset dst, bitset src1, bitset src2)
{
  ebitset_or_cmp (dst, src1, src2);
}


static bool
ebitset_xor_cmp (bitset dst, bitset src1, bitset src2)
{
  if (EBITSET_ZERO_P (src2))
    {
      return ebitset_copy_cmp (dst, src1);
    }
  else if (EBITSET_ZERO_P (src1))
    {
      return ebitset_copy_cmp (dst, src2);
    }
  return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
}


static void
ebitset_xor (bitset dst, bitset src1, bitset src2)
{
  ebitset_xor_cmp (dst, src1, src2);
}


static void
ebitset_copy (bitset dst, bitset src)
{
  if (BITSET_COMPATIBLE_ (dst, src))
      ebitset_copy_ (dst, src);
  else
      bitset_copy_ (dst, src);
}


/* Vector of operations for linked-list bitsets.  */
struct bitset_vtable ebitset_vtable = {
  ebitset_set,
  ebitset_reset,
  bitset_toggle_,
  ebitset_test,
  ebitset_resize,
  bitset_size_,
  bitset_count_,
  ebitset_empty_p,
  ebitset_ones,
  ebitset_zero,
  ebitset_copy,
  ebitset_disjoint_p,
  ebitset_equal_p,
  ebitset_not,
  ebitset_subset_p,
  ebitset_and,
  ebitset_and_cmp,
  ebitset_andn,
  ebitset_andn_cmp,
  ebitset_or,
  ebitset_or_cmp,
  ebitset_xor,
  ebitset_xor_cmp,
  bitset_and_or_,
  bitset_and_or_cmp_,
  bitset_andn_or_,
  bitset_andn_or_cmp_,
  bitset_or_and_,
  bitset_or_and_cmp_,
  ebitset_list,
  ebitset_list_reverse,
  ebitset_free,
  BITSET_TABLE
};


/* Return size of initial structure.  */
size_t
ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
{
  return sizeof (struct ebitset_struct);
}


/* Initialize a bitset.  */

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

  bset->b.vtable = &ebitset_vtable;

  bset->b.csize = EBITSET_ELT_WORDS;

  EBITSET_ZERO_SET (bset);

  size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS
    : EBITSET_INITIAL_SIZE;

  EBITSET_ASIZE (bset) = 0;
  EBITSET_ELTS (bset) = 0;
  ebitset_resize (bset, n_bits);

  return bset;
}


void
ebitset_release_memory (void)
{
  ebitset_free_list = 0;
  if (ebitset_obstack_init)
    {
      ebitset_obstack_init = false;
      obstack_free (&ebitset_obstack, NULL);
    }
}