lbitset.c

GNU的词法/语法分析器bison源码

	  windex = elt->index;
	  bitno = windex * BITSET_WORD_BITS;
	}
      else
	{
	  bitset_word *srcp = elt->words;

	  /* We are starting within an element.  */

	  for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
	    {
	      word = srcp[windex - elt->index] >> (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;
	    }

	  elt = elt->next;
	  if (elt)
	    {
	      windex = elt->index;
	      bitno = windex * BITSET_WORD_BITS;
	    }
	}
    }


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

  while (elt)
    {
      int i;
      bitset_word *srcp = elt->words;

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

#if LBITSET_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 < LBITSET_ELT_WORDS; i++)
	    {
	      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;
		    }
		}
	      windex++;
	      bitno = windex * BITSET_WORD_BITS;
	    }
#endif
	}
      else
	{
	  /* Tread more carefully since we need to check
	     if array overflows.  */

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

      elt = elt->next;
      if (elt)
	{
	  windex = elt->index;
	  bitno = windex * BITSET_WORD_BITS;
	}
    }

  *next = bitno;
  return count;
}


static bool
lbitset_empty_p (bitset dst)
{
  lbitset_elt *elt;
  lbitset_elt *next;

  for (elt = LBITSET_HEAD (dst); elt; elt = next)
    {
      next = elt->next;
      if (!lbitset_elt_zero_p (elt))
	return 0;
      /* Weed as we go.  */
      lbitset_elt_unlink (dst, elt);
    }

  return 1;
}


/* Ensure that any unused bits within the last element are clear.  */
static inline void
lbitset_unused_clear (bitset dst)
{
  unsigned int last_bit;
  bitset_bindex n_bits;

  n_bits = BITSET_SIZE_ (dst);
  last_bit = n_bits % LBITSET_ELT_BITS;

  if (last_bit)
    {
      lbitset_elt *elt;
      bitset_windex windex;
      bitset_word *srcp;

      elt = LBITSET_TAIL (dst);
      srcp = elt->words;
      windex = n_bits / BITSET_WORD_BITS;

      srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1;
      windex++;

      for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
	srcp[windex - elt->index] = 0;
    }
}


static void
lbitset_ones (bitset dst)
{
  bitset_windex i;
  bitset_windex windex;
  lbitset_elt *elt;

  /* This is a decidedly unfriendly operation for a linked list
      bitset!  It makes a sparse bitset become dense.  An alternative
      is to have a flag that indicates that the bitset stores the
      complement of what it indicates.  */

  windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;

  for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
    {
      /* Create new elements if they cannot be found.  */
      elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
      memset (elt->words, -1, sizeof (elt->words));
    }

  lbitset_unused_clear (dst);
}


static void
lbitset_not (bitset dst, bitset src)
{
  lbitset_elt *elt;
  lbitset_elt *selt;
  lbitset_elt *delt;
  bitset_windex i;
  unsigned int j;
  bitset_windex windex;

  /* This is another unfriendly operation for a linked list
     bitset!  */
  elt = LBITSET_TAIL (dst);

  windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;

  for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
    {
      /* Create new elements for dst if they cannot be found
	 or substitute zero elements if src elements not found.  */
      selt = lbitset_elt_find (src, i, LBITSET_SUBST);
      delt = lbitset_elt_find (dst, i, LBITSET_CREATE);

      for (j = 0; j < LBITSET_ELT_WORDS; j++)
	delt->words[j] = ~selt->words[j];
    }
  lbitset_unused_clear (dst);
  lbitset_weed (dst);
  return;
}


/* Is DST == DST | SRC?  */
static bool
lbitset_subset_p (bitset dst, bitset src)
{
  lbitset_elt *selt;
  lbitset_elt *delt;
  unsigned int j;

  for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
       selt || delt; selt = selt->next, delt = delt->next)
    {
      if (!selt)
	selt = &lbitset_zero_elts[0];
      else if (!delt)
	delt = &lbitset_zero_elts[0];
      else if (selt->index != delt->index)
	{
	  if (selt->index < delt->index)
	    {
	      lbitset_zero_elts[2].next = delt;
	      delt = &lbitset_zero_elts[2];
	    }
	  else
	    {
	      lbitset_zero_elts[1].next = selt;
	      selt = &lbitset_zero_elts[1];
	    }
	}

      for (j = 0; j < LBITSET_ELT_WORDS; j++)
	if (delt->words[j] != (selt->words[j] | delt->words[j]))
	  return false;
    }
  return true;
}


/* Is DST & SRC == 0?  */
static bool
lbitset_disjoint_p (bitset dst, bitset src)
{
  lbitset_elt *selt;
  lbitset_elt *delt;
  unsigned int j;

  for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
       selt && delt; selt = selt->next, delt = delt->next)
    {
      if (selt->index != delt->index)
	{
	  if (selt->index < delt->index)
	    {
	      lbitset_zero_elts[2].next = delt;
	      delt = &lbitset_zero_elts[2];
	    }
	  else
	    {
	      lbitset_zero_elts[1].next = selt;
	      selt = &lbitset_zero_elts[1];
	    }
	  /* Since the elements are different, there is no
	     intersection of these elements.  */
	  continue;
	}

      for (j = 0; j < LBITSET_ELT_WORDS; j++)
	if (selt->words[j] & delt->words[j])
	  return false;
    }
  return true;
}


static bool
lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
{
  lbitset_elt *selt1 = LBITSET_HEAD (src1);
  lbitset_elt *selt2 = LBITSET_HEAD (src2);
  lbitset_elt *delt = LBITSET_HEAD (dst);
  bitset_windex windex1;
  bitset_windex windex2;
  bitset_windex windex;
  lbitset_elt *stmp1;
  lbitset_elt *stmp2;
  lbitset_elt *dtmp;
  bitset_word *srcp1;
  bitset_word *srcp2;
  bitset_word *dstp;
  bool changed = false;
  unsigned int i;

  LBITSET_HEAD (dst) = 0;
  dst->b.csize = 0;

  windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
  windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;

  while (selt1 || selt2)
    {
      /* Figure out whether we need to substitute zero elements for
	 missing links.  */
      if (windex1 == windex2)
	{
	  windex = windex1;
	  stmp1 = selt1;
	  stmp2 = selt2;
	  selt1 = selt1->next;
	  windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
	  selt2 = selt2->next;
	  windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
	}
      else if (windex1 < windex2)
	{
	  windex = windex1;
	  stmp1 = selt1;
	  stmp2 = &lbitset_zero_elts[0];
	  selt1 = selt1->next;
	  windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
	}
      else
	{
	  windex = windex2;
	  stmp1 = &lbitset_zero_elts[0];
	  stmp2 = selt2;
	  selt2 = selt2->next;
	  windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
	}

      /* Find the appropriate element from DST.  Begin by discarding
	 elements that we've skipped.  */
      while (delt && delt->index < windex)
	{
	  changed = true;
	  dtmp = delt;
	  delt = delt->next;
	  lbitset_elt_free (dtmp);
	}
      if (delt && delt->index == windex)
	{
	  dtmp = delt;
	  delt = delt->next;
	}
      else
	dtmp = lbitset_elt_calloc ();

      /* Do the operation, and if any bits are set, link it into the
	 linked list.  */
      srcp1 = stmp1->words;
      srcp2 = stmp2->words;
      dstp = dtmp->words;
      switch (op)
	{
	case BITSET_OP_OR:
	  for (i = 0; i < LBITSET_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 < LBITSET_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 < LBITSET_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 < LBITSET_ELT_WORDS; i++, dstp++)
	    {
	      bitset_word tmp = *srcp1++ & ~(*srcp2++);

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

	default:
	  abort ();
	}

      if (!lbitset_elt_zero_p (dtmp))
	{
	  dtmp->index = windex;
	  /* Perhaps this could be optimised...  */
	  lbitset_elt_link (dst, dtmp);
	}
      else
	{
	  lbitset_elt_free (dtmp);
	}
    }

  /* If we have elements of DST left over, free them all.  */
  if (delt)
    {
      changed = true;
      lbitset_prune (dst, delt);
    }

  return changed;
}


static bool
lbitset_and_cmp (bitset dst, bitset src1, bitset src2)
{
  lbitset_elt *selt1 = LBITSET_HEAD (src1);
  lbitset_elt *selt2 = LBITSET_HEAD (src2);
  bool changed;

  if (!selt2)
    {
      lbitset_weed (dst);
      changed = !LBITSET_HEAD (dst);
      lbitset_zero (dst);
      return changed;
    }
  else if (!selt1)
    {
      lbitset_weed (dst);
      changed = !LBITSET_HEAD (dst);
      lbitset_zero (dst);
      return changed;
    }
  return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
}


static void
lbitset_and (bitset dst, bitset src1, bitset src2)
{
  lbitset_and_cmp (dst, src1, src2);
}


static bool
lbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
{
  lbitset_elt *selt1 = LBITSET_HEAD (src1);
  lbitset_elt *selt2 = LBITSET_HEAD (src2);
  bool changed;

  if (!selt2)
    {
      return lbitset_copy_cmp (dst, src1);
    }
  else if (!selt1)
    {
      lbitset_weed (dst);
      changed = !LBITSET_HEAD (dst);
      lbitset_zero (dst);
      return changed;
    }
  return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
}


static void
lbitset_andn (bitset dst, bitset src1, bitset src2)
{
  lbitset_andn_cmp (dst, src1, src2);
}


static bool
lbitset_or_cmp (bitset dst, bitset src1, bitset src2)
{
  lbitset_elt *selt1 = LBITSET_HEAD (src1);
  lbitset_elt *selt2 = LBITSET_HEAD (src2);

  if (!selt2)
    {
      return lbitset_copy_cmp (dst, src1);
    }
  else if (!selt1)
    {
      return lbitset_copy_cmp (dst, src2);
    }
  return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
}


static void
lbitset_or (bitset dst, bitset src1, bitset src2)
{
  lbitset_or_cmp (dst, src1, src2);
}


static bool
lbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
{
  lbitset_elt *selt1 = LBITSET_HEAD (src1);
  lbitset_elt *selt2 = LBITSET_HEAD (src2);

  if (!selt2)
    {
      return lbitset_copy_cmp (dst, src1);
    }
  else if (!selt1)
    {
      return lbitset_copy_cmp (dst, src2);
    }
  return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
}


static void
lbitset_xor (bitset dst, bitset src1, bitset src2)
{
  lbitset_xor_cmp (dst, src1, src2);
}



/* Vector of operations for linked-list bitsets.  */
struct bitset_vtable lbitset_vtable = {
  lbitset_set,
  lbitset_reset,
  bitset_toggle_,
  lbitset_test,
  lbitset_resize,
  bitset_size_,
  bitset_count_,
  lbitset_empty_p,
  lbitset_ones,
  lbitset_zero,
  lbitset_copy,
  lbitset_disjoint_p,
  lbitset_equal_p,
  lbitset_not,
  lbitset_subset_p,
  lbitset_and,
  lbitset_and_cmp,
  lbitset_andn,
  lbitset_andn_cmp,
  lbitset_or,
  lbitset_or_cmp,
  lbitset_xor,
  lbitset_xor_cmp,
  bitset_and_or_,
  bitset_and_or_cmp_,
  bitset_andn_or_,
  bitset_andn_or_cmp_,
  bitset_or_and_,
  bitset_or_and_cmp_,
  lbitset_list,
  lbitset_list_reverse,
  lbitset_free,
  BITSET_LIST
};


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


/* Initialize a bitset.  */
bitset
lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)
{
  BITSET_NBITS_ (bset) = n_bits;
  bset->b.vtable = &lbitset_vtable;
  return bset;
}


void
lbitset_release_memory (void)
{
  lbitset_free_list = 0;
  if (lbitset_obstack_init)
    {
      lbitset_obstack_init = false;
      obstack_free (&lbitset_obstack, NULL);
    }
}


/* Function to be called from debugger to debug lbitset.  */
void
debug_lbitset (bitset bset)
{
  lbitset_elt *elt;
  unsigned int i;

  if (!bset)
    return;

  for (elt = LBITSET_HEAD (bset); elt; elt = elt->next)
    {
      fprintf (stderr, "Elt %lu\n", (unsigned long int) elt->index);
      for (i = 0; i < LBITSET_ELT_WORDS; i++)
	{
	  unsigned int j;
	  bitset_word word;

	  word = elt->words[i];

	  fprintf (stderr, "  Word %u:", i);
	  for (j = 0; j < LBITSET_WORD_BITS; j++)
	    if ((word & ((bitset_word) 1 << j)))
	      fprintf (stderr, " %u", j);
	  fprintf (stderr, "\n");
	}
    }
}