From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <ffmpeg-devel-bounces@ffmpeg.org>
Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100])
by master.gitmailbox.com (Postfix) with ESMTPS id 605D44DBC4
for <ffmpegdev@gitmailbox.com>; Wed, 23 Apr 2025 20:47:39 +0000 (UTC)
Received: from [127.0.1.1] (localhost [127.0.0.1])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id F3E7568B2C9;
Wed, 23 Apr 2025 23:46:44 +0300 (EEST)
Received: from relay8-d.mail.gandi.net (relay8-d.mail.gandi.net
[217.70.183.201])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 8505A68AE09
for <ffmpeg-devel@ffmpeg.org>; Wed, 23 Apr 2025 23:46:19 +0300 (EEST)
Received: by mail.gandi.net (Postfix) with ESMTPSA id 5C6A643B70
for <ffmpeg-devel@ffmpeg.org>; Wed, 23 Apr 2025 20:46:18 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc;
s=gm1; t=1745441178;
h=from:from:reply-to:subject:subject:date:date:message-id:message-id:
to:to:cc:mime-version:mime-version:content-type:content-type:
in-reply-to:in-reply-to:references:references;
bh=XdUrPp3yZM9oBFkNe3mdNhnC4HNw4F8iAzNM6Wz/KHQ=;
b=VCc/bY4GqdAKDXHzaWFq6p/hTvphSB36mz4lhUTXa7W/SMASKAIcYpU7dLaEFCkWcyJ1GE
Bk7u3mYMQe8wiRGhUinRTvYvXt88eyy5qnsPZ3DwzaMAraLlUoa7F3bDkTHYvIpb7MK5JT
tZ9Re0WFKZq1OCPGM2Y7rZ+T2+UgLAaKpdzny3sflio7+p1S2DRxvY2U6f7tta5L0yq4Nz
5WkWnxetGys83IM4ySA06oNGG12Q7d+7/JAgQxmak5rUhiEXopayDlHAr/Vuh+lOxxxaKr
GjSXp24DQogDlj6wMdbnI+CW19yeHl7f0Fwm2OJCn+3x+tbEsuoxEC5NzPOmFw==
Date: Wed, 23 Apr 2025 22:46:17 +0200
From: Michael Niedermayer <michael@niedermayer.cc>
To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Message-ID: <20250423204617.GS4991@pb2>
References: <20250420022929.724535-1-michael@niedermayer.cc>
<aAZdv3D5O57mysFP@phare.normalesup.org>
MIME-Version: 1.0
In-Reply-To: <aAZdv3D5O57mysFP@phare.normalesup.org>
X-GND-State: clean
X-GND-Score: -70
X-GND-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvgeejheelucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuifetpfffkfdpucggtfgfnhhsuhgsshgtrhhisggvnecuuegrihhlohhuthemuceftddunecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenfghrlhcuvffnffculdeftddmnecujfgurhepfffhvffukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefoihgthhgrvghlucfpihgvuggvrhhmrgihvghruceomhhitghhrggvlhesnhhivgguvghrmhgrhigvrhdrtggtqeenucggtffrrghtthgvrhhnpeelkeeggfffiedufeejueffjeduhedttdduledtheevveevtdeiueelhfdtuedtkeenucfkphepgedurdeiiedrieejrdduudefnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehinhgvthepgedurdeiiedrieejrdduudefpdhhvghloheplhhotggrlhhhohhsthdpmhgrihhlfhhrohhmpehmihgthhgrvghlsehnihgvuggvrhhmrgihvghrrdgttgdpnhgspghrtghpthhtohepuddprhgtphhtthhopehffhhmphgvghdquggvvhgvlhesfhhfmhhpvghgrdhorhhg
X-GND-Sasl: michael@niedermayer.cc
Subject: Re: [FFmpeg-devel] [PATCH] avutil/map: [WIP] Introduction
X-BeenThere: ffmpeg-devel@ffmpeg.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: FFmpeg development discussions and patches <ffmpeg-devel.ffmpeg.org>
List-Unsubscribe: <https://ffmpeg.org/mailman/options/ffmpeg-devel>,
<mailto:ffmpeg-devel-request@ffmpeg.org?subject=unsubscribe>
List-Archive: <https://ffmpeg.org/pipermail/ffmpeg-devel>
List-Post: <mailto:ffmpeg-devel@ffmpeg.org>
List-Help: <mailto:ffmpeg-devel-request@ffmpeg.org?subject=help>
List-Subscribe: <https://ffmpeg.org/mailman/listinfo/ffmpeg-devel>,
<mailto:ffmpeg-devel-request@ffmpeg.org?subject=subscribe>
Reply-To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Content-Type: multipart/mixed; boundary="===============4249628474694197128=="
Errors-To: ffmpeg-devel-bounces@ffmpeg.org
Sender: "ffmpeg-devel" <ffmpeg-devel-bounces@ffmpeg.org>
Archived-At: <https://master.gitmailbox.com/ffmpegdev/20250423204617.GS4991@pb2/>
List-Archive: <https://master.gitmailbox.com/ffmpegdev/>
List-Post: <mailto:ffmpegdev@gitmailbox.com>
--===============4249628474694197128==
Content-Type: multipart/signed; micalg=pgp-sha512;
protocol="application/pgp-signature"; boundary="hlrzeVtNL3wMLXdx"
Content-Disposition: inline
--hlrzeVtNL3wMLXdx
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
Hi Nicolas
On Mon, Apr 21, 2025 at 05:01:19PM +0200, Nicolas George wrote:
> Michael Niedermayer (HE12025-04-20):
> > theres no real reason
> > to hurry here
>=20
> (This is me applauding.)
>=20
> > except that i seem to keep workig on it when
> > people ask for some non trivial changes/improvments :)
>=20
> As long as you have fun.
>=20
> > so dont ask, send patch yourself if its not a trivial change :))
> >=20
> > Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> > ---
> > libavutil/map.h | 86 +++++++++++++++++++++++++++++++++++++++++++++++++
> > 1 file changed, 86 insertions(+)
> >=20
> > 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"
> > =20
> > /**
> > + * @file
> > + *
> > + * AVMap is a simple and fast key -> value map.
> > + *
> > + * ---------- Creating AVMaps ------------------
> > + *
> > + * AVMap *map =3D 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 wi=
ll not allow
> > + * multiple entries with the same key.
> > + * or
> > + *
> > + * AVMap *map =3D av_map_alloc(av_map_strcmp_keyvalue, AV_MAP_CMP_CASE=
_SENSITIVE + AV_MAP_CMP_KEYVALUE, NULL, NULL);
> > + *
>=20
> > + * 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
>=20
> Maybe insist: =E2=80=9CIf the same (key, value) pair is added multiple ti=
mes, it
> will be returned only once when iterating and removing it once will
> completely remove it.=E2=80=9D
>=20
> And that raises the question: should this API not also allow entries
> with multiplicity?
you can have some map where each element maps to an integer, where
that integer represents a "count"
>=20
> Also: what happens if:
>=20
> AVMap *map =3D av_map_alloc(av_map_strcmp_keyvalue, AV_MAP_CMP_CASE_SENSI=
TIVE + AV_MAP_CMP_KEY, NULL, NULL);
> AVMap *map =3D av_map_alloc(strcmp, AV_MAP_CMP_CASE_SENSITIVE + AV_MAP_CM=
P_KEYVALUE, NULL, NULL);
>=20
> (I swapped the compare functions)?
crash probably, but technically, undefined behavior
[...]
> > + *
> > + *
> > + * ----------- Adding entries -----------------
> > + *
> > + * av_map_add_strings(map, "cat", "neko", 0); // add new entry or do n=
othing
> > + *
> > + * 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, whil=
e access will always
> > + * be O(log n) when n becomes smaller, memory consumption will not dec=
rease until
> > + * AV_SET_ALLOW_REBUILD is used. Note if you use AV_SET_ALLOW_REBUILD,=
all previously
> > + * returned elements become invalid.
> > + *
>=20
> > + * av_map_del(map, "cat", 0); // remove one entry matching "the key"
> > + *
> > + * av_map_del(map, "cat", AV_SET_ALLOW_REBUILD); // remove one entry m=
atching "the key" and rebuild the map to re
>=20
> (It seems you sentence got interrup)
>=20
> If I did =E2=80=9Cav_map_add("animal\0cat", 11, "neko", 5, 0)=E2=80=9D, h=
ow can I del or
> get it?
depends on the compare function, the map was setup with.
If you created your own function that works with double or tripple zero
terminated strings. This will work perfectly fine.
Otherwise if you mix the passed object and the function so they are
not compatible then you get undefined behavior
same with qsort() or printf() or AVDictionary
>=20
> > + *
> > + *
> > + * ----------- Retrieving an entry --------------
> > + *
> > + * AVMapEntry *e =3D av_map_get(map, "cat", AV_MAP_CMP_KEY); //Find an=
entry with the key =3D "cat"
> > + *
> > + * AVMapEntry *e =3D av_map_get(map, "cat", AV_MAP_CMP_KEY+AV_MAP_CMP_=
CASE_INSENSITIVE); //Find an entry with the key =3D "cat", "Cat", "cAt", ...
>=20
> > + * // this will only work if one of the set compare functions is case =
insensitive
>=20
> This is crucial: how? (This is redundant with my next remark.)
>=20
> > + *
> > + *
> > + * ----------- Iterating over all elements ------
> > + *
> > + * const AVMapEntry *t =3D NULL;
> > + * while ((t =3D av_map_iterate(s, t)))
> > + * printf("%s=3D%s %zu,%zu ", t->key, t->value, t->keylen, t->va=
luelen);
> > + *
> > + *
> > + * ----------- 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 -----------
> > + *
>=20
> > + * 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 th=
is ordering
> > + * OTOH
> > + * if we have have strcmp() as primary function we would order like th=
is:
> > + * "Dog", "cat", "dog", "fox"
> > + * and here we could not treat "dog" and "Dog" as equal, and thus case=
insensitive
> > + * compare would not be possible
>=20
> Code examples needed. For example: a map where key =3D name, value =3D ph=
one
> 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?
The phone numbers i have seen are not affected by case sensitivity.
So case sensitivity only matters for the name (which is in key)
This should work:
AVMap *map =3D av_map_alloc(av_map_supercmp_keyvalue, AV_MAP_CMP_KEYVALUE +=
AV_MAP_CMP_CASE_SENSITIVE, NULL, NULL);
av_map_add_cmp_func(map, av_map_supercmp_key, AV_MAP_CMP_KEY + A=
V_MAP_CMP_CASE_SENSITIVE);
av_map_add_cmp_func(map, av_strcasecmp, AV_MAP_CMP_KEY + A=
V_MAP_CMP_CASE_INSENSITIVE);
But the point you seem to try to raise, is correct,
not every combination is possible
thx
[...]
--=20
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
The worst form of inequality is to try to make unequal things equal.
-- Aristotle
--hlrzeVtNL3wMLXdx
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iF0EABEKAB0WIQSf8hKLFH72cwut8TNhHseHBAsPqwUCaAlRlQAKCRBhHseHBAsP
q3z7AJ9wE9FUnhaoidgjfpl4ITw7tBcmdQCfR5yM5hziqObElb1Y1w2I8fACyBY=
=sikg
-----END PGP SIGNATURE-----
--hlrzeVtNL3wMLXdx--
--===============4249628474694197128==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
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".
--===============4249628474694197128==--