Re: [FFmpeg-devel] [PATCH] avutil/map: [WIP] Introduction

[Nicolas George <george@nsup.org>]

Michael Niedermayer (HE12025-04-20):
>					  theres no real reason
> to hurry here

(This is me applauding.)

>		except that i seem to keep workig on it when
> people ask for some non trivial changes/improvments :)

As long as you have fun.

> so dont ask, send patch yourself if its not a trivial change :))
> 
> Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> ---
>  libavutil/map.h | 86 +++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 86 insertions(+)
> 
> diff --git a/libavutil/map.h b/libavutil/map.h
> index 8211a05ec8d..0d3f7eab9ac 100644
> --- a/libavutil/map.h
> +++ b/libavutil/map.h
> @@ -31,6 +31,92 @@
>  #include "tree.h"
>  
>  /**
> + * @file
> + *
> + * AVMap is a simple and fast key -> value map.
> + *
> + * ---------- Creating AVMaps ------------------
> + *
> + * AVMap *map = av_map_alloc(strcmp, AV_MAP_CMP_CASE_SENSITIVE + AV_MAP_CMP_KEY, NULL, NULL);
> + *
> + * This creates a case sensitve string based map using strcmp(). It will not allow
> + * multiple entries with the same key.
> + * or
> + *
> + * AVMap *map = av_map_alloc(av_map_strcmp_keyvalue, AV_MAP_CMP_CASE_SENSITIVE + AV_MAP_CMP_KEYVALUE, NULL, NULL);
> + *

> + * This is like the previous, but it will allow multiple entries with the same key
> + * the difference here is that the compare function compares the value too when
> + * the key is equal.
> + * All entries in a map must always be different. So by comparing the value
> + * too we can have multiple entries with the same key

Maybe insist: “If the same (key, value) pair is added multiple times, it
will be returned only once when iterating and removing it once will
completely remove it.”

And that raises the question: should this API not also allow entries
with multiplicity?

Also: what happens if:

AVMap *map = av_map_alloc(av_map_strcmp_keyvalue, AV_MAP_CMP_CASE_SENSITIVE + AV_MAP_CMP_KEY, NULL, NULL);
AVMap *map = av_map_alloc(strcmp, AV_MAP_CMP_CASE_SENSITIVE + AV_MAP_CMP_KEYVALUE, NULL, NULL);

(I swapped the compare functions)?


> + * The remaining 2 pointers in av_map_alloc() are for a function copying an element
> + * and one for freeing it. That is only needed for complex objects, not for strings.

Ok for now I guess, but eventually a complete introduction should
include sample code, for example if key is
struct { const char *family_name, *given_name; }
and the value is
struct { int type; const char *text; }.

> + *
> + *
> + * ----------- Adding entries -----------------
> + *
> + * av_map_add_strings(map, "cat", "neko", 0); // add new entry or do nothing
> + *
> + * av_map_add_strings(map, "cat", "neko", AV_MAP_REPLACE); // add new entry or replace existing
> + *
> + *
> + * ----------- Removing entries -----------------
> + *
> + * Removing entries does by default not rebuild the map. That is, while access will always
> + * be O(log n) when n becomes smaller, memory consumption will not decrease until
> + * AV_SET_ALLOW_REBUILD is used. Note if you use AV_SET_ALLOW_REBUILD, all previously
> + * returned elements become invalid.
> + *

> + * av_map_del(map, "cat", 0); // remove one entry matching "the key"
> + *
> + * av_map_del(map, "cat", AV_SET_ALLOW_REBUILD); // remove one entry matching "the key" and rebuild the map to re

(It seems you sentence got interrup)

If I did “av_map_add("animal\0cat", 11, "neko", 5, 0)”, how can I del or
get it?

> + *
> + *
> + * ----------- Retrieving an entry --------------
> + *
> + * AVMapEntry *e = av_map_get(map, "cat", AV_MAP_CMP_KEY); //Find an entry with the key = "cat"
> + *
> + * AVMapEntry *e = av_map_get(map, "cat", AV_MAP_CMP_KEY+AV_MAP_CMP_CASE_INSENSITIVE); //Find an entry with the key = "cat", "Cat", "cAt", ...

> + * // this will only work if one of the set compare functions is case insensitive

This is crucial: how? (This is redundant with my next remark.)

> + *
> + *
> + * ----------- Iterating over all elements ------
> + *
> + * const AVMapEntry *t = NULL;
> + * while ((t = av_map_iterate(s, t)))
> + *     printf("%s=%s %zu,%zu   ", t->key, t->value, t->keylen, t->valuelen);
> + *
> + *
> + * ----------- copying all elements of a mep into another map
> + *
> + * av_map_copy(dst, src);
> + *
> + *
> + * ----------- freeing a map ---------------------
> + *
> + * av_map_free(&map);
> + *
> + *
> + * ----------- multiple compare function in a single map -----------
> + *

> + * Each map has a primary compare function, which is used for ordering elements.
> + * Additional (compatible) compare functions can be added with av_map_add_cmp_func()
> + *
> + * What "compaibility" means here is that every added function returns the same value
> + * as the primary function or 0.
> + *
> + * An example, Imagine we have "cat", "dog", "Dog", "fox"
> + * a function that treats "dog" and "Dog" as equal is compatible to this ordering
> + * OTOH
> + * if we have have strcmp() as primary function we would order like this:
> + * "Dog", "cat", "dog", "fox"
> + * and here we could not treat "dog" and "Dog" as equal, and thus case insensitive
> + * compare would not be possible

Code examples needed. For example: a map where key = name, value = phone
number, with AV_MAP_CMP_KEYVALUE. How do we set it up to allow
case-insensitive lookups and name only lookups, and name only
case-insensitive lookups?

I would help, but I still cannot wrap my head around the way your flags
system work.

> + *
> + * ----------- compared to AVDictionary -----------
> + *
>   * compared to AVDictionary this has
>   * clone is O(n) instead of O(n²)
>   * copy is O(n*log n) instead of O(n²)

Thanks.

Regards,

-- 
  Nicolas George
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".