[FFmpeg-devel] [PATCH v5 1/3] lavc/hashtable: create generic robin hood hash table

[Michael Niedermayer]

On Sat, Apr 26, 2025 at 01:05:07AM +0900, Emma Worley wrote:
> Adds a generic hash table with the DXV encoder as an initial use case.
> 
> Signed-off-by: Emma Worley <emma at emma.gg>
> ---
>  libavcodec/Makefile          |   2 +
>  libavcodec/hashtable.c       | 214 +++++++++++++++++++++++++++++++++++
>  libavcodec/hashtable.h       |  91 +++++++++++++++
>  libavcodec/tests/hashtable.c | 110 ++++++++++++++++++
>  4 files changed, 417 insertions(+)
>  create mode 100644 libavcodec/hashtable.c
>  create mode 100644 libavcodec/hashtable.h
>  create mode 100644 libavcodec/tests/hashtable.c
[...]

> diff --git a/libavcodec/hashtable.h b/libavcodec/hashtable.h
> new file mode 100644
> index 0000000000..a26eb30cec
> --- /dev/null
> +++ b/libavcodec/hashtable.h
> @@ -0,0 +1,91 @@
> +/*
> + * Generic hashtable
> + * Copyright (C) 2024 Connor Worley <connorbworley at gmail.com>
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#ifndef AVCODEC_HASHTABLE_H
> +#define AVCODEC_HASHTABLE_H
> +
> +#include <stddef.h>
> +
> +/* Implements a hash table using Robin Hood open addressing.
> + * See: https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
> + */
> +
> +typedef struct FFHashtableContext FFHashtableContext;
> +
> +/**
> + * Create a fixed-sized Robin Hood hash table.
> + *
> + * @param ctx         context to allocate and initialize
> + * @param key_size    size of key type in bytes
> + * @param val_size    size of value type in bytes
> + * @param max_entries maximum number of key-value pairs to store
> + *
> + * @return zero on success, nonzero on error
> + */
> +int ff_hashtable_alloc(struct FFHashtableContext **ctx, size_t key_size, size_t val_size, size_t max_entries);

I think this API should clarify how the hash of a object and object
equality is defined.
One can guess that from just a size and pointer that would be defined
on a bytewise compare and hash() of the bytes. But this should be spelled
out explicitly

thx

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

The misfortune of the wise is better than the prosperity of the fool.
-- Epicurus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20250530/5a7d9985/attachment.sig>