[dm-devel] Array-driven persistent-data structure

[Eric Wheeler]

On Wed, 9 Mar 2016, Nikolay Borisov wrote:
>>On Wed, 9 Mar 2016, Eric Wheeler wrote:
>> Hello all,
>> 
>> I'm considering writing an array-driven persistent-data structure for 
>> arbitrary metadata.  The implementation is intended to be trivial but 
>> reusable:
>> 
[...]
>
> Have you checked the existing:
> http://lxr.free-electrons.com/source/drivers/md/persistent-data/dm-array.h

Interesting, I hadn't, looking now.  dm-bitset looks useful too.

It is neat to see a transactional array; that provides some correctness 
guarantees.  Having the ability to hold multiple roots could be useful 
too.

While the transactional correctness guarantee outweighs the need for O(1) 
IMHO, it would be neat to see O(1) since btree is O(lg(n)).  O(1) should 
be attainable since the chunksize is known, so offset=chunksize*index 
---but then one would need to manage their own crash recovery.

I'll look at using dm-array and/or dm-bitset for our purpose.  I think it 
will do nicely.

Thank you for the hint!

-Eric

--
Eric Wheeler

> 
> --
> dm-devel mailing list
> dm-devel at redhat.com
> https://www.redhat.com/mailman/listinfo/dm-devel
>