[FFmpeg-devel] [RFC] av_tree enumeration

[Stefano Sabatini]

On date Sunday 2009-11-15 00:35:42 +0100, Michael Niedermayer encoded:
> On Sat, Nov 14, 2009 at 10:08:27PM +0100, Stefano Sabatini wrote:
[...]
> > We have different options here:
> > 
> > 1) to keep the next field in the various element and use it, the main
> > problem is that this way we have non-const data in the element
> > definitions, so the corresponding code cannot be kept in shareable
> > memory.
> > Performance:
> > 
> > insertion = O(n)
> > find      = O(n)
> > next      = O(1)
> > 
> > No need for allocation / free.
> > 
> > 2) to use a list of elements, as it was implemented for libavfilter
> > filters before I removed it, the list can be sorted or non-sorted.
> > 
> > insertion = O(n)
> > find      = O(n)
> > next      = O(n)
> > 
> > Requires allocation / deallocation of the list elements, so in theory
> > a registration may fail for a memory allocation error.
> > 
> > Main problem is that the next operation is slow, this *may* be in
> > theory a problem e.g. when enumerating a long list of elements.
> > 
> > 3) to use an array with variable dimension. If the array is sorted we
> > can use bsearch for fast searches. We need to allocate such array and
> > since we don't know its size we may need to reallocate and/or memcpy
> > data.
> > 
> > Performance (sorted):
> > 
> > insertion = O(log(n)) + realloc/memcpy?
> 
> insert is O(1) without sort and O(n) when maintaining sort its also
> O(1) when doing n inserts and seperate sort after all
> 
> 
> > find      = O(log(n))
> 
> true if sorted
> 
> 
> > next      = O(log(n))
> 
> next is O(1), that is p+1

We have AVElement elt and we call av_element_next(elt), we use
elt->name for finding the element in the array of registered elements,
which requires O(log(n)), then we can get the next element.

> > Looks more complex than 1) and 2).
> > 
> > 4) to use other data structures, e.g. trees or dictionaries.
> 
> 5)
> Use array of compile time constant size

How can we know how many elements the user is going to register?
E.g. in the case of lavfi filters she could even create its own
filters and register them.

Regards.
-- 
FFmpeg = Foolish Fantastic Mystic Proud Everlasting Gadget