Re: [PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

[Sami Liedes <sami.liedes@iki.fi>]

[-- Attachment #1: Type: text/plain, Size: 2065 bytes --]

On Sun, Mar 11, 2012 at 03:51:05AM -0600, Andreas Dilger wrote:
> Rather than making the bitmap searching loop more efficient, I've always thought
> it would be better to have an interface that iterates over the bitmap and returns
> the next set bit.  It is similar to what you implemented with ->find_first_zero(),
> but it would be better to have (IMHO) ->find_next_zero() and ->find_next_set().

I've been thinking about this. Such an interface might be a good idea,
and I could implement it and a corresponding backend implementation
for the bit array backend, but I don't think ext2fs_new_inode() could
properly exercise it and I'm hesitant to submit code that isn't tested
by being actually properly used somewhere. I will still do it if
there's a general consensus that it's a good idea.

It could be something along the lines of

* type ext2fs_bitmap_iterator, opaque to calling code, mainly a magic
  number and backend-specific private data. In the bitarray case it
  could just be the number of the bit pointed to and the end of the
  range to iterate.

* bool bitmap_ops->deref_iterator(ext2fs_generic_bitmap, ext2fs_bitmap_iterator)

* ext2fs_bitmap_iterator ops->create_iterator()
                            ->create_ranged_iterator(__u64 start, __u64 end)
                            ->free_iterator(ext2fs_bitmap_iterator) 

* __u64 bitmap_ops->iterator_position(...)

* errcode_t ops->find_next_zero(..., __u64 *pos),
               ->find_next_set(..., __u64 *pos)
  * These would both increment the iterator and, if pos != NULL, set
    *pos to the new bit position

* Modifying a bitmap invalidates all its iterators in such a way that
  the only legal operation for them afterwards is ->free_iterator()

In the case of ext2fs_new_inode(), the function does not actually
iterate through all zero bits; it really only wants to find the first
zero in a certain range, after which it returns. So for simplicity of
use (and efficiency) I think it still makes sense to have
->find_first_zero() too.

	Sami

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]