bitmap.c

GCC编译器源代码


/* Clear a single bit in a bitmap.  */

void
bitmap_clear_bit (head, bit)
     bitmap head;
     int bit;
{
  bitmap_element *ptr = bitmap_find_bit (head, bit);

  if (ptr != 0)
    {
      unsigned bit_num  = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
      unsigned word_num = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT)
			   % BITMAP_ELEMENT_WORDS);
      ptr->bits[word_num] &= ~ (((unsigned HOST_WIDE_INT) 1) << bit_num);

      /* If we cleared the entire word, free up the element */
      if (bitmap_element_zerop (ptr))
	bitmap_element_free (head, ptr);
    }
}


/* Set a single bit in a bitmap.  */

void
bitmap_set_bit (head, bit)
     bitmap head;
     int bit;
{
  bitmap_element *ptr = bitmap_find_bit (head, bit);
  unsigned word_num
    = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
  unsigned bit_num  = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
  unsigned HOST_WIDE_INT bit_val = ((unsigned HOST_WIDE_INT) 1) << bit_num;

  if (ptr == 0)
    {
      ptr = bitmap_element_allocate (head);
      ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
      ptr->bits[word_num] = bit_val;
      bitmap_element_link (head, ptr);
    }
  else
    ptr->bits[word_num] |= bit_val;
}

/* Return whether a bit is set within a bitmap.  */

int
bitmap_bit_p (head, bit)
     bitmap head;
     int bit;
{
  bitmap_element *ptr;
  unsigned bit_num;
  unsigned word_num;

  ptr = bitmap_find_bit (head, bit);
  if (ptr == 0)
    return 0;

  bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
  word_num
    = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);

  return
    (ptr->bits[word_num] & (((unsigned HOST_WIDE_INT) 1) << bit_num)) != 0;
}

/* Store in bitmap TO the result of combining bitmap FROM1 and
   FROM2 using a specific bit manipulation.  */

void
bitmap_operation (to, from1, from2, operation)
     bitmap to;
     bitmap from1;
     bitmap from2;
     enum bitmap_bits operation;
{
  bitmap_element *delete_list = 0;
  bitmap_element *from1_ptr = from1->first;
  bitmap_element *from2_ptr = from2->first;
  unsigned int indx1
    = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
  unsigned int indx2
    = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
  bitmap_element *to_ptr = 0;
  bitmap_element *from1_tmp;
  bitmap_element *from2_tmp;
  unsigned int indx;
  int i;

  /* To simplify things, always create a new list.  If the old list was one
     of the inputs, free it later.  Otherwise, free it now.  */
  if (to == from1 || to == from2)
    {
      delete_list = to->first;
      to->first = to->current = 0;
    }
  else
    bitmap_clear (to);

  while (from1_ptr != 0 || from2_ptr != 0)
    {
      /* Figure out whether we need to substitute zero elements for
	 missing links.  */
      if (indx1 == indx2)
	{
	  indx = indx1;
	  from1_tmp = from1_ptr;
	  from2_tmp = from2_ptr;
	  from1_ptr = from1_ptr->next;
	  indx1 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
	  from2_ptr = from2_ptr->next;
	  indx2 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
	}
      else if (indx1 < indx2)
	{
	  indx = indx1;
	  from1_tmp = from1_ptr;
	  from2_tmp = &bitmap_zero;
	  from1_ptr = from1_ptr->next;
	  indx1 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
	}
      else
	{
	  indx = indx2;
	  from1_tmp = &bitmap_zero;
	  from2_tmp = from2_ptr;
	  from2_ptr = from2_ptr->next;
	  indx2 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
	}

      if (to_ptr == 0)
	to_ptr = bitmap_element_allocate (to);

      /* Do the operation, and if any bits are set, link it into the
	 linked list.  */
      switch (operation)
	{
	default:
	  abort ();

	case BITMAP_AND:
#if BITMAP_ELEMENT_WORDS == 2
	  to_ptr->bits[0] = from1_tmp->bits[0] & from2_tmp->bits[0];
	  to_ptr->bits[1] = from1_tmp->bits[1] & from2_tmp->bits[1];
#else
	  for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
	    to_ptr->bits[i] = from1_tmp->bits[i] & from2_tmp->bits[i];
#endif
	  break;

	case BITMAP_AND_COMPL:
#if BITMAP_ELEMENT_WORDS == 2
	  to_ptr->bits[0] = from1_tmp->bits[0] & ~ from2_tmp->bits[0];
	  to_ptr->bits[1] = from1_tmp->bits[1] & ~ from2_tmp->bits[1];
#else
	  for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
	    to_ptr->bits[i] = from1_tmp->bits[i] & ~ from2_tmp->bits[i];
#endif
	  break;

	case BITMAP_IOR:
#if BITMAP_ELEMENT_WORDS == 2
	  to_ptr->bits[0] = from1_tmp->bits[0] | from2_tmp->bits[0];
	  to_ptr->bits[1] = from1_tmp->bits[1] | from2_tmp->bits[1];
#else
	  for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
	    to_ptr->bits[i] = from1_tmp->bits[i] | from2_tmp->bits[i];
#endif
	  break;
	}

      if (! bitmap_element_zerop (to_ptr))
	{
	  to_ptr->indx = indx;
	  bitmap_element_link (to, to_ptr);
	  to_ptr = 0;
	}
    }

  /* If we have an unallocated element due to the last element being 0,
     release it back to the free pool.  Don't bother calling
     bitmap_element_free since it was never linked into a bitmap.  */
  if (to_ptr != 0)
    {
      to_ptr->next = bitmap_free;
      bitmap_free = to_ptr;
    }

  /* If the output bitmap was one of the inputs, free up its
     elements now that we're done.  */
  for (; delete_list != 0; delete_list = to_ptr)
    {
      to_ptr = delete_list->next;
      delete_list->next = bitmap_free;
      bitmap_free = delete_list;
    }
}

/* Or into bitmap TO bitmap FROM1 and'ed with the complement of
   bitmap FROM2. */

void
bitmap_ior_and_compl (to, from1, from2)
     bitmap to;
     bitmap from1;
     bitmap from2;
{
  bitmap_head tmp;

  tmp.first = tmp.current = 0;

  bitmap_operation (&tmp, from1, from2, BITMAP_AND_COMPL);
  bitmap_operation (to, to, &tmp, BITMAP_IOR);
  bitmap_clear (&tmp);
}

/* Initialize a bitmap header.  */

bitmap
bitmap_initialize (head)
     bitmap head;
{
  head->first = head->current = 0;

  return head;
}

/* Debugging function to print out the contents of a bitmap.  */

void
bitmap_debug_file (file, head)
     FILE *file;
     bitmap head;
{
  bitmap_element *ptr;

  fprintf (file, "\nfirst = ");
  fprintf (file, HOST_PTR_PRINTF, (HOST_WIDE_INT) head->first);
  fprintf (file, " current = ");
  fprintf (file, HOST_PTR_PRINTF, (HOST_WIDE_INT) head->current);
  fprintf (file, " indx = %u\n", head->indx);

  for (ptr = head->first; ptr; ptr = ptr->next)
    {
      int i, j, col = 26;

      fprintf (file, "\t");
      fprintf (file, HOST_PTR_PRINTF, (HOST_WIDE_INT) ptr);
      fprintf (file, " next = ");
      fprintf (file, HOST_PTR_PRINTF, (HOST_WIDE_INT) ptr->next);
      fprintf (file, " prev = ");
      fprintf (file, HOST_PTR_PRINTF, (HOST_WIDE_INT) ptr->prev);
      fprintf (file, " indx = %u\n\t\tbits = {", ptr->indx);

      for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
	for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++)
	  if ((ptr->bits[i] & (((unsigned HOST_WIDE_INT) 1) << j)) != 0)
	    {
	      if (col > 70)
		{
		  fprintf (file, "\n\t\t\t");
		  col = 24;
		}

	      fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
				     + i * HOST_BITS_PER_WIDE_INT + j));
	      col += 4;
	    }

      fprintf (file, " }\n");
    }
}

/* Function to be called from the debugger to print the contents
   of a bitmap.  */

void
debug_bitmap (head)
     bitmap head;
{
  bitmap_debug_file (stdout, head);
}

/* Function to print out the contents of a bitmap.  Unlike bitmap_debug_file,
   it does not print anything but the bits.  */

void
bitmap_print (file, head, prefix, suffix)
     FILE *file;
     bitmap head;
     char *prefix;
     char *suffix;
{
  char *comma = "";
  int i;

  fputs (prefix, file);
  EXECUTE_IF_SET_IN_BITMAP (head, 0, i,
			    {
			      fprintf (file, "%s%d", comma, i);
			      comma = ", ";
			    });
  fputs (suffix, file);
}

/* Release any memory allocated by bitmaps.  */

void
bitmap_release_memory ()
{
  bitmap_free = 0;
  if (bitmap_obstack_init)
    {
      bitmap_obstack_init = FALSE;
      obstack_free (&bitmap_obstack, NULL_PTR);
    }
}