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.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@99605 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 10 insertions, 3 deletions

diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 2915623fa41..3c3b3c13f7a 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 *);