From: softworkz <ffmpegagent@gmail.com> To: ffmpeg-devel@ffmpeg.org Cc: softworkz <softworkz@hotmail.com> Subject: [FFmpeg-devel] [PATCH 1/3] avutil/dict2: Add AVDictionary2 with hash-based lookup Date: Sat, 12 Apr 2025 15:11:56 +0000 Message-ID: <b73334be1412100028fa04680a6f964beca85cbb.1744470718.git.ffmpegagent@gmail.com> (raw) In-Reply-To: <pull.64.ffstaging.FFmpeg.1744470718.ffmpegagent@gmail.com> From: softworkz <softworkz@hotmail.com> see doc/dict2.md Signed-off-by: softworkz <softworkz@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 _______________________________________________ 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".
next prev parent reply other threads:[~2025-04-12 15:12 UTC|newest] Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top 2025-04-12 15:11 [FFmpeg-devel] [PATCH 0/3] " ffmpegagent 2025-04-12 15:11 ` softworkz [this message] 2025-04-16 21:24 ` [FFmpeg-devel] [PATCH 1/3] " Michael Niedermayer 2025-04-16 22:38 ` softworkz . 2025-04-12 15:11 ` [FFmpeg-devel] [PATCH 2/3] doc/dict2: Add doc and api change for AVDictionary2 softworkz 2025-04-16 21:48 ` Michael Niedermayer 2025-04-16 22:43 ` softworkz . 2025-04-16 23:15 ` softworkz . 2025-04-16 23:40 ` Michael Niedermayer 2025-04-17 22:38 ` softworkz . 2025-04-19 2:28 ` Michael Niedermayer 2025-04-19 13:43 ` softworkz . 2025-04-20 20:37 ` Michael Niedermayer 2025-04-12 15:11 ` [FFmpeg-devel] [PATCH 3/3] tests/dict2: Add tests and benchmark " softworkz 2025-04-14 11:02 ` [FFmpeg-devel] [PATCH 0/3] avutil/dict2: Add AVDictionary2 with hash-based lookup Nicolas George 2025-04-14 11:50 ` softworkz . 2025-04-14 13:21 ` softworkz .
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=b73334be1412100028fa04680a6f964beca85cbb.1744470718.git.ffmpegagent@gmail.com \ --to=ffmpegagent@gmail.com \ --cc=ffmpeg-devel@ffmpeg.org \ --cc=softworkz@hotmail.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
Git Inbox Mirror of the ffmpeg-devel mailing list - see https://ffmpeg.org/mailman/listinfo/ffmpeg-devel This inbox may be cloned and mirrored by anyone: git clone --mirror https://master.gitmailbox.com/ffmpegdev/0 ffmpegdev/git/0.git # If you have public-inbox 1.1+ installed, you may # initialize and index your mirror using the following commands: public-inbox-init -V2 ffmpegdev ffmpegdev/ https://master.gitmailbox.com/ffmpegdev \ ffmpegdev@gitmailbox.com public-inbox-index ffmpegdev Example config snippet for mirrors. AGPL code for this site: git clone https://public-inbox.org/public-inbox.git