[FFmpeg-devel] [RFC] av_tree enumeration

[Bobby Bingham]

On Sat, 14 Nov 2009 22:08:27 +0100
Stefano Sabatini <stefano.sabatini-lala at poste.it> wrote:

> On date Saturday 2009-11-14 16:53:53 +0100, Stefano Sabatini encoded:
> 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)
> 

Before you changed it, insert was O(1).  Here's the patch you sent:

 void avfilter_register(AVFilter *filter)
 {
-    struct FilterList *newfilt = av_malloc(sizeof(struct FilterList));
+    AVFilter **p;
+    p = &first_avfilter;
+    while (*p)
+        p = &(*p)->next;
 
-    newfilt->filter = filter;
-    newfilt->next   = filters;
-    filters         = newfilt;
+    *p = filter;
+    filter->next = NULL;
 }

That said, I don't really have a strong opinion.  Insert is probably
the least important case of the three to optimize for.

-- 
Bobby Bingham
??????????????????????