bitmap.c (bitmap_elmt_to_freelist, [...]): Changed freelist structure.

2005-05-11 Kenneth Zadeck <zadeck@naturalbridge.com>

	* bitmap.c (bitmap_elmt_to_freelist, bitmap_element_allocate,
	bitmap_elt_clear_from, bitmap_clear): Changed freelist structure.
	* bitmap.h: Fixed comments.

From-SVN: r99605

3 files changed, 71 insertions, 21 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index f92014e..b3f576d 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2005-05-11 Kenneth Zadeck <zadeck@naturalbridge.com>
+
+	* bitmap.c (bitmap_elmt_to_freelist, bitmap_element_allocate,
+	bitmap_elt_clear_from, bitmap_clear): Changed freelist structure.
+	* bitmap.h: Fixed comments.
+
 2005-05-11  Richard Henderson  <rth@redhat.com>
 
 	PR target/21412
diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 2cf4c8c..dd56bba 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -51,14 +51,15 @@ bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
 {
   bitmap_obstack *bit_obstack = head->obstack;
   
+  elt->next = NULL;
   if (bit_obstack)
     {
-      elt->next = bit_obstack->elements;
+      elt->prev = bit_obstack->elements;
       bit_obstack->elements = elt;
     }
   else
     {
-      elt->next = bitmap_ggc_free;
+      elt->prev = bitmap_ggc_free;
       bitmap_ggc_free = elt;
     }
 }
@@ -105,7 +106,16 @@ bitmap_element_allocate (bitmap head)
       element = bit_obstack->elements;
       
       if (element)
-	bit_obstack->elements = element->next;
+	/* Use up the inner list first before looking at the next
+	   element of the outer list.  */
+	if (element->next)
+	  {
+	    bit_obstack->elements = element->next;
+	    bit_obstack->elements->prev = element->prev;
+	  }
+	else
+	  /*  Inner list was just a singleton.  */
+	  bit_obstack->elements = element->prev;
       else
 	element = XOBNEW (&bit_obstack->obstack, bitmap_element);
     }
@@ -113,7 +123,16 @@ bitmap_element_allocate (bitmap head)
     {
       element = bitmap_ggc_free;
       if (element)
-	bitmap_ggc_free = element->next;
+	/* Use up the inner list first before looking at the next
+	   element of the outer list.  */
+	if (element->next)
+	  {
+	    bitmap_ggc_free = element->next;
+	    bitmap_ggc_free->prev = element->prev;
+	  }
+	else
+	  /*  Inner list was just a singleton.  */
+	  bitmap_ggc_free = element->prev;
       else
 	element = GGC_NEW (bitmap_element);
     }
@@ -128,13 +147,38 @@ bitmap_element_allocate (bitmap head)
 void
 bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
 {
-  bitmap_element *next;
+  bitmap_element *prev;
+  bitmap_obstack *bit_obstack = head->obstack;
+
+  if (!elt) return;
 
-  while (elt)
+  prev = elt->prev;
+  if (prev)
     {
-      next = elt->next;
-      bitmap_element_free (head, elt);
-      elt = next;
+      prev->next = NULL;
+      if (head->current->indx > prev->indx)
+	{
+	  head->current = prev;
+	  head->indx = prev->indx;
+	}
+    } 
+  else
+    {
+      head->first = NULL;
+      head->current = NULL;
+      head->indx = 0;
+    }
+
+  /* Put the entire list onto the free list in one operation. */ 
+  if (bit_obstack)
+    {
+      elt->prev = bit_obstack->elements; 
+      bit_obstack->elements = elt;
+    }
+  else
+    {
+      elt->prev = bitmap_ggc_free;
+      bitmap_ggc_free = elt;
     }
 }
 
@@ -143,15 +187,8 @@ bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
 inline void
 bitmap_clear (bitmap head)
 {
-  bitmap_element *element, *next;
-
-  for (element = head->first; element != 0; element = next)
-    {
-      next = element->next;
-      bitmap_elem_to_freelist (head, element);
-    }
-
-  head->first = head->current = 0;
+  if (head->first)
+    bitmap_elt_clear_from (head, head->first);
 }
 
 /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 2915623..3c3b3c1 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -49,8 +49,15 @@ typedef struct bitmap_obstack GTY (())
 
 /* Bitmap set element.  We use a linked list to hold only the bits that
    are set.  This allows for use to grow the bitset dynamically without
-   having to realloc and copy a giant bit array.  The `prev' field is
-   undefined for an element on the free list.  */
+   having to realloc and copy a giant bit array.  
+
+   The free list is implemented as a list of lists.  There is one
+   outer list connected together by prev fields.  Each element of that
+   outer is an inner list (that may consist only of the outer list
+   element) that are connected by the next fields.  The prev pointer
+   is undefined for interior elements.  This allows
+   bitmap_elt_clear_from to be implemented in unit time rather than
+   linear in the number of elements to be freed.  */
 
 typedef struct bitmap_element_def GTY(())
 {
@@ -129,7 +136,7 @@ extern void debug_bitmap_file (FILE *, bitmap);
 /* Print a bitmap.  */
 extern void bitmap_print (FILE *, bitmap, const char *, const char *);
 
-/* Initialize and releas a bitmap obstack.  */
+/* Initialize and release a bitmap obstack.  */
 extern void bitmap_obstack_initialize (bitmap_obstack *);
 extern void bitmap_obstack_release (bitmap_obstack *);