+/* Return the bit number of the first set bit in the bitmap, or -1
+ if the bitmap is empty. */
+
+int
+bitmap_first_set_bit (bitmap a)
+{
+ bitmap_element *ptr = a->first;
+ BITMAP_WORD word;
+ unsigned word_num, bit_num;
+
+ if (ptr == NULL)
+ return -1;
+
+#if BITMAP_ELEMENT_WORDS == 2
+ word_num = 0, word = ptr->bits[0];
+ if (word == 0)
+ word_num = 1, word = ptr->bits[1];
+#else
+ for (word_num = 0; word_num < BITMAP_ELEMENT_WORDS; ++word_num)
+ if ((word = ptr->bits[word_num]) != 0)
+ break;
+#endif
+
+ /* Binary search for the first set bit. */
+ /* ??? It'd be nice to know if ffs or ffsl was available. */
+
+ bit_num = 0;
+ word = word & -word;
+
+#if nBITMAP_WORD_BITS > 64
+ #error "Fill out the table."
+#endif
+#if nBITMAP_WORD_BITS > 32
+ if ((word & 0xffffffff) == 0)
+ word >>= 32, bit_num += 32;
+#endif
+ if ((word & 0xffff) == 0)
+ word >>= 16, bit_num += 16;
+ if ((word & 0xff) == 0)
+ word >>= 8, bit_num += 8;
+ if (word & 0xf0)
+ bit_num += 4;
+ if (word & 0xcc)
+ bit_num += 2;
+ if (word & 0xaa)
+ bit_num += 1;
+
+ return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
+ + word_num * BITMAP_WORD_BITS
+ + bit_num);
+}
+
+/* Return the bit number of the last set bit in the bitmap, or -1
+ if the bitmap is empty. */
+
+int
+bitmap_last_set_bit (bitmap a)
+{
+ bitmap_element *ptr = a->first;
+ BITMAP_WORD word;
+ unsigned word_num, bit_num;
+
+ if (ptr == NULL)
+ return -1;
+
+ while (ptr->next != NULL)
+ ptr = ptr->next;
+
+#if BITMAP_ELEMENT_WORDS == 2
+ word_num = 1, word = ptr->bits[1];
+ if (word == 0)
+ word_num = 0, word = ptr->bits[0];
+#else
+ for (word_num = BITMAP_ELEMENT_WORDS; word_num-- > 0; )
+ if ((word = ptr->bits[word_num]) != 0)
+ break;
+#endif
+
+ /* Binary search for the last set bit. */
+
+ bit_num = 0;
+#if nBITMAP_WORD_BITS > 64
+ #error "Fill out the table."
+#endif
+#if nBITMAP_WORD_BITS > 32
+ if (word & ~(BITMAP_WORD)0xffffffff)
+ word >>= 32, bit_num += 32;
+#endif
+ if (word & 0xffff0000)
+ word >>= 16, bit_num += 16;
+ if (word & 0xff00)
+ word >>= 8, bit_num += 8;
+ if (word & 0xf0)
+ word >>= 4, bit_num += 4;
+ if (word & 0xc)
+ word >>= 2, bit_num += 2;
+ if (word & 0x2)
+ bit_num += 1;
+
+ return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
+ + word_num * BITMAP_WORD_BITS
+ + bit_num);
+}
+\f