From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by master.gitmailbox.com (Postfix) with ESMTP id EA216492D6 for ; Wed, 7 Feb 2024 10:16:43 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id C606F68D0ED; Wed, 7 Feb 2024 12:16:40 +0200 (EET) Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-db3eur04olkn2089.outbound.protection.outlook.com [40.92.74.89]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id C6C4168C856 for ; Wed, 7 Feb 2024 12:16:33 +0200 (EET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=a14w9KEkg00px/bdnuBXDJZyp+uViL25VuTU/WzWVxLxp7LKjAHhqC4dVg7Uct5LQQBjHFclyNNqlmtgRj/hme0vIUoSoW6EOK8KV7qdYFhcjqqHWYddzQImhQq5QjLHrHJgCHu6iTC0f80qRkoD7TJZQWupi6qLObUVGCoNfleB5Oz7wNeQ255PIbRdkUN9kLGB+/EQ1E4W2fAripHzQCo6ItDoUYAjLylz9holbrd2Vbp36DPjY/y3oEKCPXG/pN6e6dAyz5aQdqGQkqNYopUdq1SewB/ohsNXtgWXtUSVU3liKZpYDKGsZUUNp3cclECw+Dg4JAxFiQSoXIpDIg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=UMXI4wj38p3qS+YESZXPLagWjqxO22lfvfvr6ly8TFM=; b=PVwX8Pe4TO2k4In6KO6jiPjuR4T/Sn/zSspQSMUvwPwaXRqYLs5oL/ZnrultFYmGSytjVO24PsyyGbXzSKXhu8IW0aJYP3AZch+jzutKdEISsEbH9cLao73eNwDTV7Mqa1MJDiIAw5ExV/LeXdxbStfp+SS6uMAHM+KD2h6Fc9vRnXcAIELkack5ds8FDfwIlCp+KlBWXi+gBdg7CbB6UOK3a7f4xPyt2aCqy2V9+mt4N9pJKb+m/7i1LXVW+J1/hb+Y5NkQQCJlOV9ysn5xTeaMWeFXxOjnx9eAVWz4GCGyHfe9U7E3PJgvyIcC9Cu3bDEXMbXmN+QVMqh1CQjbzQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=outlook.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=UMXI4wj38p3qS+YESZXPLagWjqxO22lfvfvr6ly8TFM=; b=ndGgmaUBYkDqlGyf3bxuQ0SFeB1M3CKCT6U9w+r0ewy5R906FgadFiZa6pgR8zhPmVpG63s8vZHGdccMm17MHBWWugr/M1dleEaYJDVC5/jomR4QXDUbghMs7FklDRLsBz4y3oCe9uozzXoACahJZ7G/joBpe0gEHyL33hGCYDCIpqpNxPgraqOn/SVxiFVcQ86cuVBi9fOXU6fBzny02i0FnUd0/ATlZou/UMv13Yy7+m9i5z7nBIJzGFYVVuKjlDtYE6cb8uq0h5aIGATfArVJRSlKcgzS3VR5YgAK9OIM9prSvP3cePYd2VAvQSRY2lFEDT0SHgmtRRGtcsNwTA== Received: from AS8P250MB0744.EURP250.PROD.OUTLOOK.COM (2603:10a6:20b:541::14) by AS8P250MB0086.EURP250.PROD.OUTLOOK.COM (2603:10a6:20b:371::18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7249.37; Wed, 7 Feb 2024 10:16:28 +0000 Received: from AS8P250MB0744.EURP250.PROD.OUTLOOK.COM ([fe80::65aa:deb0:a18e:d48d]) by AS8P250MB0744.EURP250.PROD.OUTLOOK.COM ([fe80::65aa:deb0:a18e:d48d%5]) with mapi id 15.20.7249.035; Wed, 7 Feb 2024 10:16:28 +0000 Message-ID: Date: Wed, 7 Feb 2024 11:18:22 +0100 User-Agent: Mozilla Thunderbird Content-Language: en-US To: ffmpeg-devel@ffmpeg.org References: <20240206105754.94877-1-connorbworley@gmail.com> From: Andreas Rheinhardt In-Reply-To: <20240206105754.94877-1-connorbworley@gmail.com> X-TMN: [10lYlMZw68L+jnh8aBClDallLM1x219Y9+jii1W8/Lg=] X-ClientProxiedBy: ZR0P278CA0213.CHEP278.PROD.OUTLOOK.COM (2603:10a6:910:6a::19) To AS8P250MB0744.EURP250.PROD.OUTLOOK.COM (2603:10a6:20b:541::14) X-Microsoft-Original-Message-ID: MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AS8P250MB0744:EE_|AS8P250MB0086:EE_ X-MS-Office365-Filtering-Correlation-Id: 0b99a866-e99d-48ba-a7ac-08dc27c5d90c X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: rGiU0VWkiA91EDOicuf7IMTgSCqqPiZd+0eAvZJu/lOXSnCzay3vAFkMp4C3xlUeN1/824TnPbWmcmuvy8Gn0tl1Y1U9VBfIGqdWZISrPFSfKay74J3WWQEP4Ov/rbGWp3KgKw5kpcQaaG7AnC8rgrB1hEglN0b9sGfBrkAgIKWEhN60VTzanOO1vGhO28dFXjDhzdsCppac0jF/i880se3bWKG5K2vS/chqAbe5enCY5q6hZjpLys6Wjxvlyw8eKrU3pOvI1/WNpQIAyt8BIId8wGxMVLJkAxUbnRrAGSE0cnFmwK64/FNJ66hOrC91IYINb9MlH1ZCgu9YDPkhWtytn6XQyht3xrB4LE9G4rOO4pQhbtJ61eQeBhryeOcrCqoaxnt18kVi5SVMSei+bBKadWZkTW3alWulEX8rTIsbg8uP/4iuN69H7TtefCqH8oOVwU0CcGdRE6WhuQAgGVWRELHVcTvpqiR01NkRzawJ1CZt5xTE+t+n/mqN5nF6RMP6fonhJ38uffKZiB/GZ3LbpBbrvnIMprPs6MKqYqM= X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?KzN2TTlOSzBSM2pWdkMyYThIL2pQVW92V0txWFJXb3FRUHZQUGcxT3pKSFpk?= =?utf-8?B?OHFLaWp1dUk3bWJWUkNlR3BIYzc3Q3BJUFRQdjRZMTVjT2hlUjIvMjdFeFpR?= =?utf-8?B?dWtVMU53MlNKUUhST09GbkRLdkZPSkRYb25RUXZsd1JoMXRPVnNLQlRZOFN6?= =?utf-8?B?TUFiakNRYjYwMFRtWTBnaCs5Y2pjT2FxZHlsUFVmMUxIN2Z0NnJGbTVzRlA2?= =?utf-8?B?TTdzOGpaVlRHZUZNUjB1Um5UMHE1Z2NaZWxPeU96Q2ZMU09oRDhSNGUvWWVP?= =?utf-8?B?MTRWWUtOVlA1V1ZhalZ2eFliQjhqTHQ4Y0tWWnBqUW93WTNTL0xJT2VBdHE2?= =?utf-8?B?WkF3bVNzaUJlTzJYR01WYll6YmF1SExWem1GcW1yTDVMdjJBNXV2NzZIYlpa?= =?utf-8?B?aTFESjFCMmVtQkxwQ0tnNWkvQkVoR2J3QzhZMXpGTTl6N0J2VXpkcGJrQjJH?= =?utf-8?B?MnAwb1p0YjgwT2laellVR1FaQ05pUTNpT3ZvOVR6YnNwUGdWSFVQK2x6cE1p?= =?utf-8?B?b3BsMFlyUmJZcGlheDFZUWM1WWkwd1FESFhNOFEvWnoxNWhOYWhlcXZLQ1Rr?= =?utf-8?B?M1lCZXlvR1duTzU4Z3JjRytxb29rNEI4WEt4TmNFTGVxRTNnSVVYMElPMTV4?= =?utf-8?B?MUlBbWluMkd3bjlXaS82Z1VvY2lCY3diRTNxaURDbjR1eTU1YjFpWitndkht?= =?utf-8?B?TENETVU1OEdwR0JaSHpFWkpwc055dUR2N3JrWEl2VVNabmp4L1lSUjFlKzZN?= =?utf-8?B?R0pRaFg0c3ErVVpnUFF4NGNqSHl4L3pyR1p3RVZLVGdTUi9Pditad3dRRUVH?= =?utf-8?B?NXgxMkpjM2NXQ1dmYkQrS25xZnZzbmRoV3JzNDNOLzk2YkFEb1BVY1VvTXFK?= =?utf-8?B?dDNCejF4V0lHNUVCVUx1dldxUlVCOWwweW5VZ1pGZ3NBbXBkU0REYlNHSFBy?= =?utf-8?B?Yjd1Y2hleTF4TGFBU0dmWm5hSlExTTdYc3c5T0FmOWJibVF6aGJNOHJyTnEy?= =?utf-8?B?ZTVBKzl0d1BiSmhGS1kxKzNDa3VmalkzMjdQYTZlVFlxZTI1cDloUm8vcE4y?= =?utf-8?B?YUVtaGNRakxLSTU5ZW8yb01ZS1R6dGo1Y2ovdmZTY3BhTlYwWW5PMVk3V2VI?= =?utf-8?B?RTNQbVpLUGZsYWN5Q1FDNGRLTjV3VTNweTJpRTJsRkdmVGduQVlJcllpaDF4?= =?utf-8?B?TExTVU13VktwdktEZUM5bTFLVlYzRUcxOEhoclArbGxkbjBjcUxQSlZUK0Ez?= =?utf-8?B?eS8wbVBsOUNqc2NDcW5hcEJkMmt4N3dkZTNDTTBBR2tBRHJmZDBUbDczc1VT?= =?utf-8?B?bWhVdHJKeU4vWHRjbUdyTm55ZnpiOTFjNmg0b0FkaVZUL01rWGtrdW93ZEJG?= =?utf-8?B?QXExT3RzbWYzYUVJU1FJandPbnJNZTdNeWppL05mTmJsc0Y0Z3dnMVZLSDRS?= =?utf-8?B?Zm9OTjVDaml3bmJXVklPNG1ZR0d0UXNkRVl0VXNadnhJZUs4b1R6QzEwL2xL?= =?utf-8?B?Nzcxa2NGSjMwN09rM2wxaUNiWkdCeWtlNE5QZElOMktLS0NwZHVNVldZYXc0?= =?utf-8?B?NFdLSitQZm5KUHliWWUvcXZ6Z3BTUkd2N3VnU201aGZkRDBkNWFIbDlHUlNl?= =?utf-8?B?Y1piUkwybjlsZ1NNQnVqWERFSkhXUEpDait2TWdpTmJzTFR1ZHk4SFEvdnpE?= =?utf-8?Q?GEd+esDyiQ3Dco9k4KSt?= X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 0b99a866-e99d-48ba-a7ac-08dc27c5d90c X-MS-Exchange-CrossTenant-AuthSource: AS8P250MB0744.EURP250.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 07 Feb 2024 10:16:28.5032 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8P250MB0086 Subject: Re: [FFmpeg-devel] [PATCH v2 1/2] lavu/hashtable: create generic robin hood hash table X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: Connor Worley: > Signed-off-by: Connor Worley > --- > libavutil/Makefile | 2 + > libavutil/hashtable.c | 183 ++++++++++++++++++++++++++++++++++++ > libavutil/hashtable.h | 47 +++++++++ > libavutil/tests/hashtable.c | 108 +++++++++++++++++++++ > 4 files changed, 340 insertions(+) > create mode 100644 libavutil/hashtable.c > create mode 100644 libavutil/hashtable.h > create mode 100644 libavutil/tests/hashtable.c > > diff --git a/libavutil/Makefile b/libavutil/Makefile > index e7709b97d0..be75d464fc 100644 > --- a/libavutil/Makefile > +++ b/libavutil/Makefile > @@ -138,6 +138,7 @@ OBJS = adler32.o \ > fixed_dsp.o \ > frame.o \ > hash.o \ > + hashtable.o \ > hdr_dynamic_metadata.o \ > hdr_dynamic_vivid_metadata.o \ > hmac.o \ > @@ -251,6 +252,7 @@ TESTPROGS = adler32 \ > file \ > fifo \ > hash \ > + hashtable \ > hmac \ > hwdevice \ > integer \ > diff --git a/libavutil/hashtable.c b/libavutil/hashtable.c > new file mode 100644 > index 0000000000..6fa2af8af3 > --- /dev/null > +++ b/libavutil/hashtable.c > @@ -0,0 +1,183 @@ > +/* > + * Generic hashtable > + * Copyright (C) 2024 Connor Worley > + * > + * 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 > +#include > + > +#include "crc.h" > +#include "error.h" > +#include "mem.h" > +#include "hashtable.h" > + > +struct AVHashtableContext { > + size_t key_size; > + size_t val_size; > + size_t entry_size; > + size_t max_entries; > + size_t utilization; > + const AVCRC *crc; > + uint8_t *table; > + uint8_t *swapbuf; > +}; > + > +#define ENTRY_PSL(entry) (entry) > +#define ENTRY_OCC(entry) (ENTRY_PSL(entry) + sizeof(size_t)) > +#define ENTRY_KEY(entry) (ENTRY_OCC(entry) + 4) > +#define ENTRY_VAL(entry) (ENTRY_KEY(entry) + FFALIGN(ctx->key_size, 4)) > + It seems you misunderstood what I said about alignment in my last review. You should align entry_size and not align the size of key and val fields. The way you are doing it now does not prevent unaligned accesses: Imagine the common case of size_t having an alignment requirement of 8 and key_size and val_size being four. Then entry_size is not a multiple of 8 and therefore of two consecutive entries, only one can be properly aligned (e.g. the second entry ctx->table+ctx->entry_size is misaligned). (For the same reason, the alignment of a struct is a multiple of the alignment of every member of said struct.) The way you are doing it also adds FFALIGN to every access to val. > +#define KEYS_EQUAL(k1, k2) !memcmp(k1, k2, ctx->key_size) > + > +int av_hashtable_alloc(struct AVHashtableContext** ctx, size_t key_size, size_t val_size, size_t max_entries) > +{ > + struct AVHashtableContext *res = av_malloc(sizeof(struct AVHashtableContext)); > + if (!res) > + return AVERROR(ENOMEM); > + res->key_size = key_size; > + res->val_size = val_size; You mostly only need key_size and key_size+val_size; val_size is not used that often, so if you only store two sizes, it should not be stored. > + res->entry_size = sizeof(size_t) + 4 + FFALIGN(key_size, 4) + FFALIGN(val_size, 4); > + res->max_entries = max_entries; > + res->utilization = 0; > + res->crc = av_crc_get_table(AV_CRC_32_IEEE); > + if (!res->crc) { > + av_hashtable_freep(&res); > + return AVERROR_BUG; > + } > + res->table = av_calloc(res->max_entries, res->entry_size); > + if (!res->table) { > + av_hashtable_freep(&res); > + return AVERROR(ENOMEM); > + } > + res->swapbuf = av_calloc(2, FFALIGN(key_size, 4) + FFALIGN(val_size, 4)); > + if (!res->swapbuf) { > + av_hashtable_freep(&res); > + return AVERROR(ENOMEM); > + } > + *ctx = res; > + return 0; > +} > + > +static size_t hash_key(const struct AVHashtableContext* ctx, const void* key) > +{ > + return av_crc(ctx->crc, 0, key, ctx->key_size) % ctx->max_entries; > +} > + > +int av_hashtable_get(const struct AVHashtableContext* ctx, const void* key, void* val) > +{ > + size_t hash = hash_key(ctx, key); > + > + if (!ctx->utilization) > + return 0; > + > + for (size_t psl = 0; psl < ctx->max_entries; psl++) { > + size_t wrapped_index = (hash + psl) % ctx->max_entries; > + uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size; > + if (!*ENTRY_OCC(entry) || *(size_t*)ENTRY_PSL(entry) < psl) > + return 0; > + if (KEYS_EQUAL(ENTRY_KEY(entry), key)) { > + memcpy(val, ENTRY_VAL(entry), ctx->val_size); > + return 1; > + } > + } > + return 0; > +} > + > +int av_hashtable_set(struct AVHashtableContext* ctx, const void* key, const void* val) > +{ > + int swapping = 0; > + size_t psl = 0; > + size_t hash = hash_key(ctx, key); > + uint8_t *set = ctx->swapbuf; > + uint8_t *tmp = ctx->swapbuf + FFALIGN(ctx->key_size, 4) + FFALIGN(ctx->val_size, 4); > + > + memcpy(set, key, ctx->key_size); > + memcpy(set + FFALIGN(ctx->key_size, 4), val, ctx->val_size); > + > + for (size_t i = 0; i < ctx->max_entries; i++) { > + size_t wrapped_index = (hash + i) % ctx->max_entries; > + uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size; > + if (!*ENTRY_OCC(entry) || (!swapping && KEYS_EQUAL(ENTRY_KEY(entry), set))) { > + if (!*ENTRY_OCC(entry)) > + ctx->utilization++; > + *(size_t*)ENTRY_PSL(entry) = psl; > + *ENTRY_OCC(entry) = 1; > + memcpy(ENTRY_KEY(entry), set, FFALIGN(ctx->key_size, 4) + ctx->val_size); > + return 1; > + } > + if (*(size_t*)ENTRY_PSL(entry) < psl) { > + if (ctx->utilization == ctx->max_entries) > + return 0; > + swapping = 1; > + // set needs to swap with entry > + memcpy(tmp, ENTRY_KEY(entry), FFALIGN(ctx->key_size, 4) + ctx->val_size); > + memcpy(ENTRY_KEY(entry), set, FFALIGN(ctx->key_size, 4) + ctx->val_size); > + FFSWAP(uint8_t*, set, tmp); > + FFSWAP(size_t, psl, *(size_t*)ENTRY_PSL(entry)); > + } > + psl++; > + } > + return 0; > +} > + > +int av_hashtable_delete(struct AVHashtableContext* ctx, const void* key) > +{ > + uint8_t *next_entry; > + size_t hash = hash_key(ctx, key); > + > + if (!ctx->utilization) > + return 0; > + > + for (size_t psl = 0; psl < ctx->max_entries; psl++) { > + size_t wrapped_index = (hash + psl) % ctx->max_entries; > + uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size; > + if (!*ENTRY_OCC(entry) || *(size_t*)ENTRY_PSL(entry) < psl) > + return 0; > + if (KEYS_EQUAL(ENTRY_KEY(entry), key)) { > + *ENTRY_OCC(entry) = 0; > + for (psl++; psl < ctx->max_entries; psl++) { > + wrapped_index = (hash + psl) % ctx->max_entries; > + next_entry = ctx->table + wrapped_index * ctx->entry_size; > + if (!*ENTRY_OCC(next_entry) || !*(size_t*)ENTRY_PSL(next_entry)) { > + ctx->utilization--; > + return 1; > + } > + memcpy(ENTRY_OCC(entry), ENTRY_OCC(next_entry), ctx->entry_size); > + *(size_t*)ENTRY_PSL(entry)--; > + *ENTRY_OCC(next_entry) = 0; > + entry = next_entry; > + } > + } > + }; This ';' is a null statement. > + return 0; > +} > + > +void av_hashtable_clear(struct AVHashtableContext* ctx) > +{ > + memset(ctx->table, 0, ctx->entry_size * ctx->max_entries); > +} > + > +void av_hashtable_freep(struct AVHashtableContext** ctx) > +{ > + if (*ctx) { > + av_freep(&(*ctx)->table); > + av_freep(&(*ctx)->swapbuf); > + } > + av_freep(ctx); > +} > diff --git a/libavutil/hashtable.h b/libavutil/hashtable.h > new file mode 100644 > index 0000000000..90c6cad68a > --- /dev/null > +++ b/libavutil/hashtable.h > @@ -0,0 +1,47 @@ > +/* > + * Generic hashtable > + * Copyright (C) 2024 Connor Worley > + * > + * 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_HASHTABLE_H > +#define AVUTIL_HASHTABLE_H > + > +#include > + > +/* Implements a hash table using Robin Hood open addressing. > + * See: https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf > + * > + * Entry slots are layed out in memory as follows: > + * - [1 byte] occupancy flag that indicates whether a slot if occupied. > + * - [key_size bytes] entry key. > + * - [val_size bytes] entry value. > + * - [sizeof(size_t) bytes] PSL (probe sequence length), used by the Robin Hood > + * algorithm. This is no longer true and it definitely does not belong in a header. > + */ > + > +struct AVHashtableContext; > + > +int av_hashtable_alloc(struct AVHashtableContext** ctx, size_t key_size, size_t val_size, size_t max_entries); > +int av_hashtable_get(const struct AVHashtableContext* ctx, const void* key, void* val); > +int av_hashtable_set(struct AVHashtableContext* ctx, const void* key, const void* val); > +int av_hashtable_delete(struct AVHashtableContext* ctx, const void* key); > +void av_hashtable_clear(struct AVHashtableContext* ctx); > +void av_hashtable_freep(struct AVHashtableContext** ctx); > + > +#endif > diff --git a/libavutil/tests/hashtable.c b/libavutil/tests/hashtable.c > new file mode 100644 > index 0000000000..0b38b34c5c > --- /dev/null > +++ b/libavutil/tests/hashtable.c > @@ -0,0 +1,108 @@ > +/* > + * Generic hashtable tests > + * Copyright (C) 2024 Connor Worley > + * > + * 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 "libavutil/avassert.h" > +#include "libavutil/hashtable.h" > + > +int main(void) > +{ > + struct AVHashtableContext *ctx; > + uint8_t k; > + uint64_t v; > + > + // impossibly large allocation should fail gracefully Actually, av_hashtable_alloc is missing overflow checks. > + av_assert0(av_hashtable_alloc(&ctx, -1, -1, -1) < 0); > + > + // hashtable can store up to 3 uint8_t->uint64_t entries > + av_assert0(!av_hashtable_alloc(&ctx, sizeof(k), sizeof(v), 3)); > + > + // unsuccessful deletes return 0 > + k = 1; > + av_assert0(!av_hashtable_delete(ctx, &k)); > + > + // unsuccessful gets return 0 > + k = 1; > + av_assert0(!av_hashtable_get(ctx, &k, &v)); > + > + // successful sets returns 1 > + k = 1; > + v = 1; > + av_assert0(av_hashtable_set(ctx, &k, &v)); > + > + // get should now contain 1 > + k = 1; > + v = 0; > + av_assert0(av_hashtable_get(ctx, &k, &v)); > + av_assert0(v == 1); > + > + // updating sets should return 1 > + k = 1; > + v = 2; > + av_assert0(av_hashtable_set(ctx, &k, &v)); > + > + // get should now contain 2 > + k = 1; > + v = 0; > + av_assert0(av_hashtable_get(ctx, &k, &v)); > + av_assert0(v == 2); > + > + // fill the table > + k = 2; > + v = 2; > + av_assert0(av_hashtable_set(ctx, &k, &v)); > + k = 3; > + v = 3; > + av_assert0(av_hashtable_set(ctx, &k, &v)); > + > + // inserting sets on a full table should return 0 > + k = 4; > + v = 4; > + av_assert0(!av_hashtable_set(ctx, &k, &v)); > + > + // updating sets on a full table should return 1 > + k = 1; > + v = 4; > + av_assert0(av_hashtable_set(ctx, &k, &v)); > + v = 0; > + av_assert0(av_hashtable_get(ctx, &k, &v)); > + av_assert0(v == 4); > + > + // successful deletes should return 1 > + k = 1; > + av_assert0(av_hashtable_delete(ctx, &k)); > + > + // get should now return 0 > + av_assert0(!av_hashtable_get(ctx, &k, &v)); > + > + // sanity check remaining keys > + k = 2; > + v = 0; > + av_assert0(av_hashtable_get(ctx, &k, &v)); > + av_assert0(v == 2); > + k = 3; > + v = 0; > + av_assert0(av_hashtable_get(ctx, &k, &v)); > + av_assert0(v == 3); > + > + av_hashtable_freep(&ctx); > + > + return 0; > +} _______________________________________________ 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".