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

[Michael Niedermayer]

Note, help is welcome.
Time i spend on this, i cannot spend on other things

Note2: i intend to push AVMap after the release unless the release
ends up delayed alot for other reasons, theres no real reason
to hurry here except that i seem to keep workig on it when
people ask for some non trivial changes/improvments :)
so dont ask, send patch yourself if its not a trivial change :))

Signed-off-by: Michael Niedermayer <michael at 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
+ *
+ * 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.
+ *
+ *
+ * ----------- 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
+ *
+ *
+ * ----------- 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
+ *
+ *
+ * ----------- 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
+ *
+ * ----------- 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²)
-- 
2.49.0