[FFmpeg-devel] [RFC] av_tree enumeration

[Michael Niedermayer]

On Sun, Nov 15, 2009 at 01:07:07AM +0100, Stefano Sabatini wrote:
> 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.

so fix the api


> > > 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?

You pick a number like 10+ count we have and increase it if someone
has a reasonable complaint that it was too small for him.
Also people should in general submit filters, codecs and (de)muxers
to us not keep them private


> E.g. in the case of lavfi filters she could even create its own
> filters and register them.


[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Concerning the gods, I have no means of knowing whether they exist or not
or of what sort they may be, because of the obscurity of the subject, and
the brevity of human life -- Protagoras
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20091115/94a4aa1e/attachment.pgp>