[FFmpeg-devel] [PATCH 1/3] avutil/dict2: Add AVDictionary2 with hash-based lookup
softworkz
ffmpegagent at gmail.com
Sat Apr 12 18:11:56 EEST 2025
From: softworkz <softworkz at hotmail.com>
see doc/dict2.md
Signed-off-by: softworkz <softworkz at hotmail.com>
---
libavutil/Makefile | 3 +
libavutil/dict2.c | 335 ++++++++++++++++++++++++++++++++++++++++++++
libavutil/dict2.h | 167 ++++++++++++++++++++++
libavutil/version.h | 2 +-
4 files changed, 506 insertions(+), 1 deletion(-)
create mode 100644 libavutil/dict2.c
create mode 100644 libavutil/dict2.h
diff --git a/libavutil/Makefile b/libavutil/Makefile
index 9ef118016b..5542684462 100644
--- a/libavutil/Makefile
+++ b/libavutil/Makefile
@@ -26,6 +26,7 @@ HEADERS = adler32.h \
des.h \
detection_bbox.h \
dict.h \
+ dict2.h \
display.h \
dovi_meta.h \
downmix_info.h \
@@ -128,6 +129,7 @@ OBJS = adler32.o \
des.o \
detection_bbox.o \
dict.o \
+ dict2.o \
display.o \
dovi_meta.o \
downmix_info.o \
@@ -266,6 +268,7 @@ TESTPROGS = adler32 \
des \
dict \
display \
+ dict2 \
encryption_info \
error \
eval \
diff --git a/libavutil/dict2.c b/libavutil/dict2.c
new file mode 100644
index 0000000000..96fb93d471
--- /dev/null
+++ b/libavutil/dict2.c
@@ -0,0 +1,335 @@
+/*
+ * AVDictionary2 implementation using hash table for improved performance
+ * Copyright (c) 2025 FFmpeg Team
+ *
+ * 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
+ */
+
+#include <string.h>
+#include <stddef.h>
+#include <inttypes.h>
+#include <stdio.h>
+
+#include "dict2.h"
+#include "mem.h"
+#include "error.h"
+#include "avstring.h"
+
+/* Dictionary entry */
+typedef struct DictEntry {
+ struct DictEntry *next; // For collision chains
+ char *key;
+ char *value;
+} DictEntry;
+
+/* Dictionary implementation */
+struct AVDictionary2 {
+ DictEntry **entries;
+ int table_size; // Size of hash table
+ int count; // Number of entries
+ int flags; // Dictionary flags
+};
+
+/* Initial table size and resizing constants */
+#define DICT_INITIAL_SIZE 64
+#define DICT_LOAD_FACTOR 0.75 // Resize when count > table_size * load_factor
+
+/* Basic hash function */
+static unsigned int dict_hash(const char *key, int case_sensitive) {
+ unsigned int hash = 0;
+ const unsigned char *p;
+
+ for (p = (const unsigned char *)key; *p; p++) {
+ hash = hash * 31 + (case_sensitive ? *p : av_toupper(*p));
+ }
+ return hash;
+}
+
+/* Set a dictionary entry */
+int av_dict2_set(AVDictionary2 **pm, const char *key, const char *value, int flags) {
+ AVDictionary2 *m;
+ DictEntry *entry;
+ unsigned int hash;
+ int table_idx;
+
+ if (!key)
+ return AVERROR(EINVAL);
+
+ // Create dictionary if it doesn't exist
+ if (!*pm) {
+ *pm = av_mallocz(sizeof(AVDictionary2));
+ if (!*pm)
+ return AVERROR(ENOMEM);
+
+ (*pm)->table_size = DICT_INITIAL_SIZE; // Larger initial size
+ (*pm)->entries = av_mallocz(sizeof(DictEntry*) * (*pm)->table_size);
+ if (!(*pm)->entries) {
+ av_freep(pm);
+ return AVERROR(ENOMEM);
+ }
+
+ // Set flags once at creation
+ (*pm)->flags = flags & AV_DICT2_MATCH_CASE;
+ }
+
+ m = *pm;
+
+ // Get hash index
+ hash = dict_hash(key, m->flags & AV_DICT2_MATCH_CASE);
+ table_idx = hash % m->table_size;
+
+ // Check if key already exists
+ for (entry = m->entries[table_idx]; entry; entry = entry->next) {
+ if ((m->flags & AV_DICT2_MATCH_CASE ?
+ !strcmp(entry->key, key) :
+ !av_strcasecmp(entry->key, key))) {
+
+ // Don't overwrite if flag is set
+ if (flags & AV_DICT2_DONT_OVERWRITE)
+ return 0;
+
+ // Replace value
+ av_free(entry->value);
+ entry->value = av_strdup(value ? value : "");
+ if (!entry->value)
+ return AVERROR(ENOMEM);
+
+ return 0;
+ }
+ }
+
+ // Create new entry
+ entry = av_mallocz(sizeof(DictEntry));
+ if (!entry)
+ return AVERROR(ENOMEM);
+
+ entry->key = av_strdup(key);
+ if (!entry->key) {
+ av_freep(&entry);
+ return AVERROR(ENOMEM);
+ }
+
+ entry->value = av_strdup(value ? value : "");
+ if (!entry->value) {
+ av_freep(&entry->key);
+ av_freep(&entry);
+ return AVERROR(ENOMEM);
+ }
+
+ // Insert at head of chain
+ entry->next = m->entries[table_idx];
+ m->entries[table_idx] = entry;
+ m->count++;
+
+ // Check if we need to resize the hash table
+ if (m->count > m->table_size * DICT_LOAD_FACTOR) {
+ // Resize hash table
+ int new_size = m->table_size * 2;
+ DictEntry **new_entries = av_mallocz(sizeof(DictEntry*) * new_size);
+ if (!new_entries) {
+ // Continue with current table if resize fails
+ return 0;
+ }
+
+ // Rehash all entries
+ for (int i = 0; i < m->table_size; i++) {
+ DictEntry *current = m->entries[i];
+ while (current) {
+ DictEntry *next = current->next;
+
+ // Compute new hash index
+ unsigned int new_hash = dict_hash(current->key, m->flags & AV_DICT2_MATCH_CASE);
+ int new_idx = new_hash % new_size;
+
+ // Insert at head of new chain
+ current->next = new_entries[new_idx];
+ new_entries[new_idx] = current;
+
+ current = next;
+ }
+ }
+
+ // Replace old table with new one
+ av_freep(&m->entries);
+ m->entries = new_entries;
+ m->table_size = new_size;
+ }
+
+ return 0;
+}
+
+/* Get a dictionary entry */
+AVDictionaryEntry2 *av_dict2_get(const AVDictionary2 *m, const char *key,
+ const AVDictionaryEntry2 *prev, int flags) {
+ unsigned int hash;
+ int table_idx;
+ DictEntry *entry;
+
+ static AVDictionaryEntry2 de; // Return value - holds pointers to internal data
+
+ if (!m || !key)
+ return NULL;
+
+ if (prev)
+ return NULL; // 'prev' functionality not implemented
+
+ // Get hash index
+ hash = dict_hash(key, m->flags & AV_DICT2_MATCH_CASE);
+ table_idx = hash % m->table_size;
+
+ // Search in chain
+ for (entry = m->entries[table_idx]; entry; entry = entry->next) {
+ if ((m->flags & AV_DICT2_MATCH_CASE ?
+ !strcmp(entry->key, key) :
+ !av_strcasecmp(entry->key, key))) {
+
+ // Found match
+ de.key = entry->key;
+ de.value = entry->value;
+ return &de;
+ }
+ }
+
+ return NULL; // Not found
+}
+
+/* Count dictionary entries */
+int av_dict2_count(const AVDictionary2 *m) {
+ return m ? m->count : 0;
+}
+
+/* Free dictionary */
+void av_dict2_free(AVDictionary2 **pm) {
+ AVDictionary2 *m;
+ int i;
+
+ if (!pm || !*pm)
+ return;
+
+ m = *pm;
+
+ // Free all entries
+ for (i = 0; i < m->table_size; i++) {
+ DictEntry *entry = m->entries[i];
+ while (entry) {
+ DictEntry *next = entry->next;
+ av_freep(&entry->key);
+ av_freep(&entry->value);
+ av_freep(&entry);
+ entry = next;
+ }
+ }
+
+ av_freep(&m->entries);
+ av_freep(pm);
+}
+
+/* Dictionary iterator state */
+typedef struct {
+ const AVDictionary2 *dict;
+ int table_idx;
+ DictEntry *entry;
+ AVDictionaryEntry2 de;
+} DictIter;
+
+static DictIter iter_state; // Single static iterator state
+
+/* Iterate through dictionary */
+const AVDictionaryEntry2 *av_dict2_iterate(const AVDictionary2 *m,
+ const AVDictionaryEntry2 *prev) {
+ int i;
+
+ if (!m || !m->count)
+ return NULL;
+
+ // Initialize iterator or move to next entry
+ if (!prev) {
+ // Start from beginning
+ iter_state.dict = m;
+ iter_state.table_idx = 0;
+ iter_state.entry = NULL;
+
+ // Find first entry
+ for (i = 0; i < m->table_size; i++) {
+ if (m->entries[i]) {
+ iter_state.table_idx = i;
+ iter_state.entry = m->entries[i];
+ break;
+ }
+ }
+ } else {
+ // Ensure iterator belongs to this dictionary
+ if (iter_state.dict != m)
+ return NULL;
+
+ // Move to next entry in current chain
+ if (iter_state.entry && iter_state.entry->next) {
+ iter_state.entry = iter_state.entry->next;
+ } else {
+ // Move to next chain
+ iter_state.entry = NULL;
+ for (i = iter_state.table_idx + 1; i < m->table_size; i++) {
+ if (m->entries[i]) {
+ iter_state.table_idx = i;
+ iter_state.entry = m->entries[i];
+ break;
+ }
+ }
+ }
+ }
+
+ // Return current entry or NULL if done
+ if (iter_state.entry) {
+ iter_state.de.key = iter_state.entry->key;
+ iter_state.de.value = iter_state.entry->value;
+ return &iter_state.de;
+ }
+
+ return NULL;
+}
+
+/* Set integer value */
+int av_dict2_set_int(AVDictionary2 **pm, const char *key, int64_t value, int flags) {
+ char valuestr[22]; // Enough for INT64_MIN
+ snprintf(valuestr, sizeof(valuestr), "%"PRId64, value);
+ return av_dict2_set(pm, key, valuestr, flags);
+}
+
+/* Copy dictionary */
+int av_dict2_copy(AVDictionary2 **dst, const AVDictionary2 *src, int flags) {
+ const AVDictionaryEntry2 *entry = NULL;
+ int ret;
+
+ if (!src)
+ return 0;
+
+ while ((entry = av_dict2_iterate(src, entry))) {
+ ret = av_dict2_set(dst, entry->key, entry->value, flags);
+ if (ret < 0)
+ return ret;
+ }
+
+ return 0;
+}
+
+/* Parse a string of key-value pairs */
+int av_dict2_parse_string(AVDictionary2 **pm, const char *str,
+ const char *key_val_sep, const char *pairs_sep,
+ int flags) {
+ // Stub implementation - not implemented yet
+ return AVERROR(ENOSYS);
+}
diff --git a/libavutil/dict2.h b/libavutil/dict2.h
new file mode 100644
index 0000000000..63edb3965e
--- /dev/null
+++ b/libavutil/dict2.h
@@ -0,0 +1,167 @@
+/*
+ * copyright (c) 2025 FFmpeg Team
+ *
+ * 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 AVUTIL_DICT2_H
+#define AVUTIL_DICT2_H
+
+#include <stdint.h>
+#include "dict.h"
+
+/**
+ * @file
+ * Public dictionary API with improved performance
+ *
+ * @author FFmpeg Team
+ */
+
+/**
+ * @addtogroup lavu_dict AVDictionary2
+ * @ingroup lavu_data
+ *
+ * @brief Optimized key-value store
+ *
+ * AVDictionary2 is a hash table-based key-value store with improved lookup and
+ * memory usage compared to AVDictionary.
+ *
+ * This API provides the same functionality as AVDictionary with better performance.
+ * The implementation uses a hash table with chaining for collision resolution,
+ * resulting in O(1) average-case lookups and reduced memory allocations.
+ *
+ * @{
+ */
+
+/**
+ * Flag defining case-sensitivity of dictionary keys
+ */
+#define AV_DICT2_MATCH_CASE AV_DICT_MATCH_CASE
+
+/**
+ * Flag preventing overwriting existing entries
+ */
+#define AV_DICT2_DONT_OVERWRITE AV_DICT_DONT_OVERWRITE
+
+/**
+ * Opaque dictionary type
+ */
+typedef struct AVDictionary2 AVDictionary2;
+
+/**
+ * Dictionary entry
+ */
+typedef struct AVDictionaryEntry2 {
+ const char *key; /**< key string */
+ const char *value; /**< value string */
+} AVDictionaryEntry2;
+
+/**
+ * Get a dictionary entry with matching key.
+ *
+ * @param m dictionary to search
+ * @param key key to search for
+ * @param prev previous matched entry or NULL
+ * @param flags search flags: AV_DICT2_MATCH_CASE
+ * @return found entry or NULL if no such entry exists
+ */
+AVDictionaryEntry2 *av_dict2_get(const AVDictionary2 *m, const char *key,
+ const AVDictionaryEntry2 *prev, int flags);
+
+/**
+ * Set the given entry in a dictionary.
+ *
+ * @param pm pointer to dictionary
+ * @param key entry key to add
+ * @param value entry value to add
+ * @param flags see AV_DICT2_* flags
+ * @return 0 on success, negative error code on failure
+ *
+ * @note The dictionary's case sensitivity is determined by the first call
+ * to this function. Subsequent calls will use the dictionary's stored
+ * flag values.
+ */
+int av_dict2_set(AVDictionary2 **pm, const char *key, const char *value, int flags);
+
+/**
+ * Set the given entry in a dictionary using an integer value.
+ *
+ * @param pm pointer to dictionary
+ * @param key entry key to add
+ * @param value entry value to add
+ * @param flags see AV_DICT2_* flags
+ * @return 0 on success, negative error code on failure
+ */
+int av_dict2_set_int(AVDictionary2 **pm, const char *key, int64_t value, int flags);
+
+/**
+ * Parse a string of key value pairs separated with specified separator.
+ *
+ * @param pm pointer to a pointer to a dictionary
+ * @param str string to parse
+ * @param key_val_sep key-value separator character(s)
+ * @param pairs_sep pairs separator character(s)
+ * @param flags flags to use while adding to dictionary
+ * @return 0 on success, negative AVERROR code on failure
+ */
+int av_dict2_parse_string(AVDictionary2 **pm, const char *str,
+ const char *key_val_sep, const char *pairs_sep,
+ int flags);
+
+/**
+ * Copy entries from one dictionary into another.
+ *
+ * @param dst pointer to the destination dictionary
+ * @param src source dictionary
+ * @param flags flags to use while setting entries in the destination dictionary
+ * @return 0 on success, negative AVERROR code on failure
+ */
+int av_dict2_copy(AVDictionary2 **dst, const AVDictionary2 *src, int flags);
+
+/**
+ * Free all memory allocated for a dictionary.
+ *
+ * @param pm pointer to dictionary pointer
+ */
+void av_dict2_free(AVDictionary2 **pm);
+
+/**
+ * Get number of entries in dictionary.
+ *
+ * @param m dictionary
+ * @return number of entries in dictionary
+ */
+int av_dict2_count(const AVDictionary2 *m);
+
+/**
+ * Iterate through a dictionary.
+ *
+ * @param m dictionary to iterate through
+ * @param prev previous entry or NULL to get the first entry
+ * @return next entry or NULL when the end is reached
+ *
+ * @note Entries are enumerated in no particular order due to hash table structure
+ * @note The returned entry should not be freed manually
+ */
+const AVDictionaryEntry2 *av_dict2_iterate(const AVDictionary2 *m,
+ const AVDictionaryEntry2 *prev);
+
+/**
+ * @}
+ */
+
+#endif /* AVUTIL_DICT2_H */
diff --git a/libavutil/version.h b/libavutil/version.h
index 5139883569..4717cd562b 100644
--- a/libavutil/version.h
+++ b/libavutil/version.h
@@ -79,7 +79,7 @@
*/
#define LIBAVUTIL_VERSION_MAJOR 60
-#define LIBAVUTIL_VERSION_MINOR 1
+#define LIBAVUTIL_VERSION_MINOR 2
#define LIBAVUTIL_VERSION_MICRO 100
#define LIBAVUTIL_VERSION_INT AV_VERSION_INT(LIBAVUTIL_VERSION_MAJOR, \
--
ffmpeg-codebot
More information about the ffmpeg-devel
mailing list