1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
|
/*
* Generic hashtable
* Copyright (C) 2025 Emma Worley <emma@emma.gg>
*
* 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 <stdint.h>
#include <string.h>
#include "libavutil/attributes.h"
#include "libavutil/crc.h"
#include "libavutil/error.h"
#include "libavutil/macros.h"
#include "libavutil/mem.h"
#include "hashtable.h"
#define ALIGN _Alignof(size_t)
struct FFHashtableContext {
size_t key_size;
size_t val_size;
size_t entry_size;
size_t max_entries;
size_t nb_entries;
const AVCRC *crc;
uint8_t *table;
uint8_t swapbuf[];
};
/*
* Hash table entries are comprised of a probe sequence length (PSL), key, and
* value. When the PSL of an entry is zero, it means it is not occupied by a
* key/value pair. When the PSL is non-zero, it represents the "distance" of
* the entry from its "home" location plus one, where the "home" location is
* hash(key) % max_entries.
*/
#define ENTRY_PSL_VAL(entry) (*(size_t*)(entry))
#define ENTRY_KEY_PTR(entry) ((entry) + sizeof(size_t))
#define ENTRY_VAL_PTR(entry) (ENTRY_KEY_PTR(entry) + ctx->key_size)
#define KEYS_EQUAL(k1, k2) (!memcmp((k1), (k2), ctx->key_size))
av_cold int ff_hashtable_alloc(FFHashtableContext **ctx, size_t key_size,
size_t val_size, size_t max_entries)
{
const size_t keyval_size = key_size + val_size;
if (keyval_size < key_size || // did (unsigned,defined) wraparound happen?
keyval_size > FFMIN(SIZE_MAX - sizeof(size_t) - (ALIGN - 1),
(SIZE_MAX - sizeof(FFHashtableContext)) / 2))
return AVERROR(ERANGE);
FFHashtableContext *res = av_mallocz(sizeof(*res) + 2 * keyval_size);
if (!res)
return AVERROR(ENOMEM);
res->key_size = key_size;
res->val_size = val_size;
res->entry_size = FFALIGN(sizeof(size_t) + keyval_size, ALIGN);
res->max_entries = max_entries;
res->nb_entries = 0;
res->crc = av_crc_get_table(AV_CRC_32_IEEE);
if (!res->crc) {
ff_hashtable_freep(&res);
return AVERROR_BUG;
}
res->table = av_calloc(res->max_entries, res->entry_size);
if (!res->table) {
ff_hashtable_freep(&res);
return AVERROR(ENOMEM);
}
*ctx = res;
return 0;
}
static size_t hash_key(const struct FFHashtableContext *ctx, const void *key)
{
return av_crc(ctx->crc, 0, key, ctx->key_size) % ctx->max_entries;
}
int ff_hashtable_get(const struct FFHashtableContext *ctx, const void *key, void *val)
{
if (!ctx->nb_entries)
return 0;
size_t hash = hash_key(ctx, key);
for (size_t psl = 1; 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_PSL_VAL(entry) < psl)
// When PSL stops increasing it means there are no further entries
// with the same key hash.
return 0;
if (KEYS_EQUAL(ENTRY_KEY_PTR(entry), key)) {
memcpy(val, ENTRY_VAL_PTR(entry), ctx->val_size);
return 1;
}
}
return 0;
}
int ff_hashtable_set(struct FFHashtableContext *ctx, const void *key, const void *val)
{
int swapping = 0;
size_t psl = 1;
size_t hash = hash_key(ctx, key);
size_t wrapped_index = hash % ctx->max_entries;
uint8_t *set = ctx->swapbuf;
uint8_t *tmp = ctx->swapbuf + ctx->key_size + ctx->val_size;
memcpy(set, key, ctx->key_size);
memcpy(set + ctx->key_size, val, ctx->val_size);
for (size_t i = 0; i < ctx->max_entries; i++) {
if (++wrapped_index == ctx->max_entries)
wrapped_index = 0;
uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
if (!ENTRY_PSL_VAL(entry) || (!swapping && KEYS_EQUAL(ENTRY_KEY_PTR(entry), set))) {
if (!ENTRY_PSL_VAL(entry))
ctx->nb_entries++;
ENTRY_PSL_VAL(entry) = psl;
memcpy(ENTRY_KEY_PTR(entry), set, ctx->key_size + ctx->val_size);
return 1;
}
if (ENTRY_PSL_VAL(entry) < psl) {
// When PSL stops increasing it means there are no further entries
// with the same key hash. We can only hope to find an unoccupied
// entry.
if (ctx->nb_entries == ctx->max_entries)
// The table is full so inserts are impossible.
return 0;
// Robin Hood hash tables "steal from the rich" by minimizing the
// PSL of the inserted entry.
swapping = 1;
// set needs to swap with entry
memcpy(tmp, ENTRY_KEY_PTR(entry), ctx->key_size + ctx->val_size);
memcpy(ENTRY_KEY_PTR(entry), set, ctx->key_size + ctx->val_size);
FFSWAP(uint8_t*, set, tmp);
FFSWAP(size_t, psl, ENTRY_PSL_VAL(entry));
}
psl++;
}
return 0;
}
int ff_hashtable_delete(struct FFHashtableContext *ctx, const void *key)
{
if (!ctx->nb_entries)
return 0;
uint8_t *next_entry;
size_t hash = hash_key(ctx, key);
size_t wrapped_index = hash % ctx->max_entries;
for (size_t psl = 1; psl <= ctx->max_entries; psl++) {
if (++wrapped_index == ctx->max_entries)
wrapped_index = 0;
uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
if (ENTRY_PSL_VAL(entry) < psl)
// When PSL stops increasing it means there are no further entries
// with the same key hash.
return 0;
if (KEYS_EQUAL(ENTRY_KEY_PTR(entry), key)) {
ENTRY_PSL_VAL(entry) = 0;
// Shift each following entry that will benefit from a reduced PSL.
for (psl++; psl <= ctx->max_entries; psl++) {
if (++wrapped_index == ctx->max_entries)
wrapped_index = 0;
next_entry = ctx->table + wrapped_index * ctx->entry_size;
if (ENTRY_PSL_VAL(next_entry) <= 1) {
ctx->nb_entries--;
return 1;
}
memcpy(entry, next_entry, ctx->entry_size);
ENTRY_PSL_VAL(entry)--;
ENTRY_PSL_VAL(next_entry) = 0;
entry = next_entry;
}
}
}
return 0;
}
void ff_hashtable_clear(struct FFHashtableContext *ctx)
{
memset(ctx->table, 0, ctx->entry_size * ctx->max_entries);
}
av_cold void ff_hashtable_freep(FFHashtableContext **ctx)
{
if (*ctx) {
av_freep(&(*ctx)->table);
av_freep(ctx);
}
}
|
