Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel
os
linux
1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright 2023 Red Hat
4 */
5
6/**
7 * DOC:
8 *
9 * Hash table implementation of a map from integers to pointers, implemented using the Hopscotch
10 * Hashing algorithm by Herlihy, Shavit, and Tzafrir (see
11 * http://en.wikipedia.org/wiki/Hopscotch_hashing). This implementation does not contain any of the
12 * locking/concurrency features of the algorithm, just the collision resolution scheme.
13 *
14 * Hopscotch Hashing is based on hashing with open addressing and linear probing. All the entries
15 * are stored in a fixed array of buckets, with no dynamic allocation for collisions. Unlike linear
16 * probing, all the entries that hash to a given bucket are stored within a fixed neighborhood
17 * starting at that bucket. Chaining is effectively represented as a bit vector relative to each
18 * bucket instead of as pointers or explicit offsets.
19 *
20 * When an empty bucket cannot be found within a given neighborhood, subsequent neighborhoods are
21 * searched, and one or more entries will "hop" into those neighborhoods. When this process works,
22 * an empty bucket will move into the desired neighborhood, allowing the entry to be added. When
23 * that process fails (typically when the buckets are around 90% full), the table must be resized
24 * and the all entries rehashed and added to the expanded table.
25 *
26 * Unlike linear probing, the number of buckets that must be searched in the worst case has a fixed
27 * upper bound (the size of the neighborhood). Those entries occupy a small number of memory cache
28 * lines, leading to improved use of the cache (fewer misses on both successful and unsuccessful
29 * searches). Hopscotch hashing outperforms linear probing at much higher load factors, so even
30 * with the increased memory burden for maintaining the hop vectors, less memory is needed to
31 * achieve that performance. Hopscotch is also immune to "contamination" from deleting entries
32 * since entries are genuinely removed instead of being replaced by a placeholder.
33 *
34 * The published description of the algorithm used a bit vector, but the paper alludes to an offset
35 * scheme which is used by this implementation. Since the entries in the neighborhood are within N
36 * entries of the hash bucket at the start of the neighborhood, a pair of small offset fields each
37 * log2(N) bits wide is all that's needed to maintain the hops as a linked list. In order to encode
38 * "no next hop" (i.e. NULL) as the natural initial value of zero, the offsets are biased by one
39 * (i.e. 0 => NULL, 1 => offset=0, 2 => offset=1, etc.) We can represent neighborhoods of up to 255
40 * entries with just 8+8=16 bits per entry. The hop list is sorted by hop offset so the first entry
41 * in the list is always the bucket closest to the start of the neighborhood.
42 *
43 * While individual accesses tend to be very fast, the table resize operations are very, very
44 * expensive. If an upper bound on the latency of adding an entry to the table is needed, we either
45 * need to ensure the table is pre-sized to be large enough so no resize is ever needed, or we'll
46 * need to develop an approach to incrementally resize the table.
47 */
48
49#include "int-map.h"
50
51#include <linux/minmax.h>
52
53#include "errors.h"
54#include "logger.h"
55#include "memory-alloc.h"
56#include "numeric.h"
57#include "permassert.h"
58
59#define DEFAULT_CAPACITY 16 /* the number of neighborhoods in a new table */
60#define NEIGHBORHOOD 255 /* the number of buckets in each neighborhood */
61#define MAX_PROBES 1024 /* limit on the number of probes for a free bucket */
62#define NULL_HOP_OFFSET 0 /* the hop offset value terminating the hop list */
63#define DEFAULT_LOAD 75 /* a compromise between memory use and performance */
64
65/**
66 * struct bucket - hash bucket
67 *
68 * Buckets are packed together to reduce memory usage and improve cache efficiency. It would be
69 * tempting to encode the hop offsets separately and maintain alignment of key/value pairs, but
70 * it's crucial to keep the hop fields near the buckets that they use them so they'll tend to share
71 * cache lines.
72 */
73struct bucket {
74 /**
75 * @first_hop: The biased offset of the first entry in the hop list of the neighborhood
76 * that hashes to this bucket.
77 */
78 u8 first_hop;
79 /** @next_hop: The biased offset of the next bucket in the hop list. */
80 u8 next_hop;
81 /** @key: The key stored in this bucket. */
82 u64 key;
83 /** @value: The value stored in this bucket (NULL if empty). */
84 void *value;
85} __packed;
86
87/**
88 * struct int_map - The concrete definition of the opaque int_map type.
89 *
90 * To avoid having to wrap the neighborhoods of the last entries back around to the start of the
91 * bucket array, we allocate a few more buckets at the end of the array instead, which is why
92 * capacity and bucket_count are different.
93 */
94struct int_map {
95 /** @size: The number of entries stored in the map. */
96 size_t size;
97 /** @capacity: The number of neighborhoods in the map. */
98 size_t capacity;
99 /** @bucket_count: The number of buckets in the bucket array. */
100 size_t bucket_count;
101 /** @buckets: The array of hash buckets. */
102 struct bucket *buckets;
103};
104
105/**
106 * mix() - The Google CityHash 16-byte hash mixing function.
107 * @input1: The first input value.
108 * @input2: The second input value.
109 *
110 * Return: A hash of the two inputs.
111 */
112static u64 mix(u64 input1, u64 input2)
113{
114 static const u64 CITY_MULTIPLIER = 0x9ddfea08eb382d69ULL;
115 u64 hash = (input1 ^ input2);
116
117 hash *= CITY_MULTIPLIER;
118 hash ^= (hash >> 47);
119 hash ^= input2;
120 hash *= CITY_MULTIPLIER;
121 hash ^= (hash >> 47);
122 hash *= CITY_MULTIPLIER;
123 return hash;
124}
125
126/**
127 * hash_key() - Calculate a 64-bit non-cryptographic hash value for the provided 64-bit integer
128 * key.
129 * @key: The mapping key.
130 *
131 * The implementation is based on Google's CityHash, only handling the specific case of an 8-byte
132 * input.
133 *
134 * Return: The hash of the mapping key.
135 */
136static u64 hash_key(u64 key)
137{
138 /*
139 * Aliasing restrictions forbid us from casting pointer types, so use a union to convert a
140 * single u64 to two u32 values.
141 */
142 union {
143 u64 u64;
144 u32 u32[2];
145 } pun = {.u64 = key};
146
147 return mix(sizeof(key) + (((u64) pun.u32[0]) << 3), pun.u32[1]);
148}
149
150/**
151 * allocate_buckets() - Initialize an int_map.
152 * @map: The map to initialize.
153 * @capacity: The initial capacity of the map.
154 *
155 * Return: VDO_SUCCESS or an error code.
156 */
157static int allocate_buckets(struct int_map *map, size_t capacity)
158{
159 map->size = 0;
160 map->capacity = capacity;
161
162 /*
163 * Allocate NEIGHBORHOOD - 1 extra buckets so the last bucket can have a full neighborhood
164 * without have to wrap back around to element zero.
165 */
166 map->bucket_count = capacity + (NEIGHBORHOOD - 1);
167 return vdo_allocate(map->bucket_count, "struct int_map buckets", &map->buckets);
168}
169
170/**
171 * vdo_int_map_create() - Allocate and initialize an int_map.
172 * @initial_capacity: The number of entries the map should initially be capable of holding (zero
173 * tells the map to use its own small default).
174 * @map_ptr: Output, a pointer to hold the new int_map.
175 *
176 * Return: VDO_SUCCESS or an error code.
177 */
178int vdo_int_map_create(size_t initial_capacity, struct int_map **map_ptr)
179{
180 struct int_map *map;
181 int result;
182 size_t capacity;
183
184 result = vdo_allocate(1, "struct int_map", &map);
185 if (result != VDO_SUCCESS)
186 return result;
187
188 /* Use the default capacity if the caller did not specify one. */
189 capacity = (initial_capacity > 0) ? initial_capacity : DEFAULT_CAPACITY;
190
191 /*
192 * Scale up the capacity by the specified initial load factor. (i.e to hold 1000 entries at
193 * 80% load we need a capacity of 1250)
194 */
195 capacity = capacity * 100 / DEFAULT_LOAD;
196
197 result = allocate_buckets(map, capacity);
198 if (result != VDO_SUCCESS) {
199 vdo_int_map_free(vdo_forget(map));
200 return result;
201 }
202
203 *map_ptr = map;
204 return VDO_SUCCESS;
205}
206
207/**
208 * vdo_int_map_free() - Free an int_map.
209 * @map: The int_map to free.
210 *
211 * NOTE: The map does not own the pointer values stored in the map and they are not freed by this
212 * call.
213 */
214void vdo_int_map_free(struct int_map *map)
215{
216 if (map == NULL)
217 return;
218
219 vdo_free(vdo_forget(map->buckets));
220 vdo_free(vdo_forget(map));
221}
222
223/**
224 * vdo_int_map_size() - Get the number of entries stored in an int_map.
225 * @map: The int_map to query.
226 *
227 * Return: The number of entries in the map.
228 */
229size_t vdo_int_map_size(const struct int_map *map)
230{
231 return map->size;
232}
233
234/**
235 * dereference_hop() - Convert a biased hop offset within a neighborhood to a pointer to the bucket
236 * it references.
237 * @neighborhood: The first bucket in the neighborhood.
238 * @hop_offset: The biased hop offset to the desired bucket.
239 *
240 * Return: NULL if hop_offset is zero, otherwise a pointer to the bucket in the neighborhood at
241 * hop_offset - 1.
242 */
243static struct bucket *dereference_hop(struct bucket *neighborhood, unsigned int hop_offset)
244{
245 BUILD_BUG_ON(NULL_HOP_OFFSET != 0);
246 if (hop_offset == NULL_HOP_OFFSET)
247 return NULL;
248
249 return &neighborhood[hop_offset - 1];
250}
251
252/**
253 * insert_in_hop_list() - Add a bucket into the hop list for the neighborhood.
254 * @neighborhood: The first bucket in the neighborhood.
255 * @new_bucket: The bucket to add to the hop list.
256 *
257 * The bucket is inserted it into the list so the hop list remains sorted by hop offset.
258 */
259static void insert_in_hop_list(struct bucket *neighborhood, struct bucket *new_bucket)
260{
261 /* Zero indicates a NULL hop offset, so bias the hop offset by one. */
262 int hop_offset = 1 + (new_bucket - neighborhood);
263
264 /* Handle the special case of adding a bucket at the start of the list. */
265 int next_hop = neighborhood->first_hop;
266
267 if ((next_hop == NULL_HOP_OFFSET) || (next_hop > hop_offset)) {
268 new_bucket->next_hop = next_hop;
269 neighborhood->first_hop = hop_offset;
270 return;
271 }
272
273 /* Search the hop list for the insertion point that maintains the sort order. */
274 for (;;) {
275 struct bucket *bucket = dereference_hop(neighborhood, next_hop);
276
277 next_hop = bucket->next_hop;
278
279 if ((next_hop == NULL_HOP_OFFSET) || (next_hop > hop_offset)) {
280 new_bucket->next_hop = next_hop;
281 bucket->next_hop = hop_offset;
282 return;
283 }
284 }
285}
286
287/**
288 * select_bucket() - Select and return the hash bucket for a given search key.
289 * @map: The map to search.
290 * @key: The mapping key.
291 */
292static struct bucket *select_bucket(const struct int_map *map, u64 key)
293{
294 /*
295 * Calculate a good hash value for the provided key. We want exactly 32 bits, so mask the
296 * result.
297 */
298 u64 hash = hash_key(key) & 0xFFFFFFFF;
299
300 /*
301 * Scale the 32-bit hash to a bucket index by treating it as a binary fraction and
302 * multiplying that by the capacity. If the hash is uniformly distributed over [0 ..
303 * 2^32-1], then (hash * capacity / 2^32) should be uniformly distributed over [0 ..
304 * capacity-1]. The multiply and shift is much faster than a divide (modulus) on X86 CPUs.
305 */
306 return &map->buckets[(hash * map->capacity) >> 32];
307}
308
309/**
310 * search_hop_list() - Search the hop list associated with given hash bucket for a given search
311 * key.
312 * @bucket: The map bucket to search for the key.
313 * @key: The mapping key.
314 * @previous_ptr: Output. if not NULL, a pointer in which to store the bucket in the list preceding
315 * the one that had the matching key
316 *
317 * If the key is found, returns a pointer to the entry (bucket or collision), otherwise returns
318 * NULL.
319 *
320 * Return: An entry that matches the key, or NULL if not found.
321 */
322static struct bucket *search_hop_list(struct bucket *bucket, u64 key,
323 struct bucket **previous_ptr)
324{
325 struct bucket *previous = NULL;
326 unsigned int next_hop = bucket->first_hop;
327
328 while (next_hop != NULL_HOP_OFFSET) {
329 /*
330 * Check the neighboring bucket indexed by the offset for the
331 * desired key.
332 */
333 struct bucket *entry = dereference_hop(bucket, next_hop);
334
335 if ((key == entry->key) && (entry->value != NULL)) {
336 if (previous_ptr != NULL)
337 *previous_ptr = previous;
338 return entry;
339 }
340 next_hop = entry->next_hop;
341 previous = entry;
342 }
343
344 return NULL;
345}
346
347/**
348 * vdo_int_map_get() - Retrieve the value associated with a given key from the int_map.
349 * @map: The int_map to query.
350 * @key: The key to look up.
351 *
352 * Return: The value associated with the given key, or NULL if the key is not mapped to any value.
353 */
354void *vdo_int_map_get(struct int_map *map, u64 key)
355{
356 struct bucket *match = search_hop_list(select_bucket(map, key), key, NULL);
357
358 return ((match != NULL) ? match->value : NULL);
359}
360
361/**
362 * resize_buckets() - Increase the number of hash buckets.
363 * @map: The map to resize.
364 *
365 * Resizes and rehashes all the existing entries, storing them in the new buckets.
366 *
367 * Return: VDO_SUCCESS or an error code.
368 */
369static int resize_buckets(struct int_map *map)
370{
371 int result;
372 size_t i;
373
374 /* Copy the top-level map data to the stack. */
375 struct int_map old_map = *map;
376
377 /* Re-initialize the map to be empty and 50% larger. */
378 size_t new_capacity = map->capacity / 2 * 3;
379
380 vdo_log_info("%s: attempting resize from %zu to %zu, current size=%zu",
381 __func__, map->capacity, new_capacity, map->size);
382 result = allocate_buckets(map, new_capacity);
383 if (result != VDO_SUCCESS) {
384 *map = old_map;
385 return result;
386 }
387
388 /* Populate the new hash table from the entries in the old bucket array. */
389 for (i = 0; i < old_map.bucket_count; i++) {
390 struct bucket *entry = &old_map.buckets[i];
391
392 if (entry->value == NULL)
393 continue;
394
395 result = vdo_int_map_put(map, entry->key, entry->value, true, NULL);
396 if (result != VDO_SUCCESS) {
397 /* Destroy the new partial map and restore the map from the stack. */
398 vdo_free(vdo_forget(map->buckets));
399 *map = old_map;
400 return result;
401 }
402 }
403
404 /* Destroy the old bucket array. */
405 vdo_free(vdo_forget(old_map.buckets));
406 return VDO_SUCCESS;
407}
408
409/**
410 * find_empty_bucket() - Probe the bucket array starting at the given bucket for the next empty
411 * bucket, returning a pointer to it.
412 * @map: The map containing the buckets to search.
413 * @bucket: The bucket at which to start probing.
414 * @max_probes: The maximum number of buckets to search.
415 *
416 * NULL will be returned if the search reaches the end of the bucket array or if the number of
417 * linear probes exceeds a specified limit.
418 *
419 * Return: The next empty bucket, or NULL if the search failed.
420 */
421static struct bucket *
422find_empty_bucket(struct int_map *map, struct bucket *bucket, unsigned int max_probes)
423{
424 /*
425 * Limit the search to either the nearer of the end of the bucket array or a fixed distance
426 * beyond the initial bucket.
427 */
428 ptrdiff_t remaining = &map->buckets[map->bucket_count] - bucket;
429 struct bucket *sentinel = &bucket[min_t(ptrdiff_t, remaining, max_probes)];
430 struct bucket *entry;
431
432 for (entry = bucket; entry < sentinel; entry++) {
433 if (entry->value == NULL)
434 return entry;
435 }
436
437 return NULL;
438}
439
440/**
441 * move_empty_bucket() - Move an empty bucket closer to the start of the bucket array.
442 * @hole: The empty bucket to fill with an entry that precedes it in one of its enclosing
443 * neighborhoods.
444 *
445 * This searches the neighborhoods that contain the empty bucket for a non-empty bucket closer to
446 * the start of the array. If such a bucket is found, this swaps the two buckets by moving the
447 * entry to the empty bucket.
448 *
449 * Return: The bucket that was vacated by moving its entry to the provided hole, or NULL if no
450 * entry could be moved.
451 */
452static struct bucket *move_empty_bucket(struct bucket *hole)
453{
454 /*
455 * Examine every neighborhood that the empty bucket is part of, starting with the one in
456 * which it is the last bucket. No boundary check is needed for the negative array
457 * arithmetic since this function is only called when hole is at least NEIGHBORHOOD cells
458 * deeper into the array than a valid bucket.
459 */
460 struct bucket *bucket;
461
462 for (bucket = &hole[1 - NEIGHBORHOOD]; bucket < hole; bucket++) {
463 /*
464 * Find the entry that is nearest to the bucket, which means it will be nearest to
465 * the hash bucket whose neighborhood is full.
466 */
467 struct bucket *new_hole = dereference_hop(bucket, bucket->first_hop);
468
469 if (new_hole == NULL) {
470 /*
471 * There are no buckets in this neighborhood that are in use by this one
472 * (they must all be owned by overlapping neighborhoods).
473 */
474 continue;
475 }
476
477 /*
478 * Skip this bucket if its first entry is actually further away than the hole that
479 * we're already trying to fill.
480 */
481 if (hole < new_hole)
482 continue;
483
484 /*
485 * We've found an entry in this neighborhood that we can "hop" further away, moving
486 * the hole closer to the hash bucket, if not all the way into its neighborhood.
487 */
488
489 /*
490 * The entry that will be the new hole is the first bucket in the list, so setting
491 * first_hop is all that's needed remove it from the list.
492 */
493 bucket->first_hop = new_hole->next_hop;
494 new_hole->next_hop = NULL_HOP_OFFSET;
495
496 /* Move the entry into the original hole. */
497 hole->key = new_hole->key;
498 hole->value = new_hole->value;
499 new_hole->value = NULL;
500
501 /* Insert the filled hole into the hop list for the neighborhood. */
502 insert_in_hop_list(bucket, hole);
503 return new_hole;
504 }
505
506 /* We couldn't find an entry to relocate to the hole. */
507 return NULL;
508}
509
510/**
511 * update_mapping() - Find and update any existing mapping for a given key, returning the value
512 * associated with the key in the provided pointer.
513 * @neighborhood: The first bucket in the neighborhood that would contain the search key
514 * @key: The key with which to associate the new value.
515 * @new_value: The value to be associated with the key.
516 * @update: Whether to overwrite an existing value.
517 * @old_value_ptr: a pointer in which to store the old value (unmodified if no mapping was found)
518 *
519 * Return: true if the map contains a mapping for the key, false if it does not.
520 */
521static bool update_mapping(struct bucket *neighborhood, u64 key, void *new_value,
522 bool update, void **old_value_ptr)
523{
524 struct bucket *bucket = search_hop_list(neighborhood, key, NULL);
525
526 if (bucket == NULL) {
527 /* There is no bucket containing the key in the neighborhood. */
528 return false;
529 }
530
531 /*
532 * Return the value of the current mapping (if desired) and update the mapping with the new
533 * value (if desired).
534 */
535 if (old_value_ptr != NULL)
536 *old_value_ptr = bucket->value;
537 if (update)
538 bucket->value = new_value;
539 return true;
540}
541
542/**
543 * find_or_make_vacancy() - Find an empty bucket.
544 * @map: The int_map to search or modify.
545 * @neighborhood: The first bucket in the neighborhood in which an empty bucket is needed for a new
546 * mapping.
547 *
548 * Find an empty bucket in a specified neighborhood for a new mapping or attempt to re-arrange
549 * mappings so there is such a bucket. This operation may fail (returning NULL) if an empty bucket
550 * is not available or could not be relocated to the neighborhood.
551 *
552 * Return: a pointer to an empty bucket in the desired neighborhood, or NULL if a vacancy could not
553 * be found or arranged.
554 */
555static struct bucket *find_or_make_vacancy(struct int_map *map,
556 struct bucket *neighborhood)
557{
558 /* Probe within and beyond the neighborhood for the first empty bucket. */
559 struct bucket *hole = find_empty_bucket(map, neighborhood, MAX_PROBES);
560
561 /*
562 * Keep trying until the empty bucket is in the bucket's neighborhood or we are unable to
563 * move it any closer by swapping it with a filled bucket.
564 */
565 while (hole != NULL) {
566 int distance = hole - neighborhood;
567
568 if (distance < NEIGHBORHOOD) {
569 /*
570 * We've found or relocated an empty bucket close enough to the initial
571 * hash bucket to be referenced by its hop vector.
572 */
573 return hole;
574 }
575
576 /*
577 * The nearest empty bucket isn't within the neighborhood that must contain the new
578 * entry, so try to swap it with bucket that is closer.
579 */
580 hole = move_empty_bucket(hole);
581 }
582
583 return NULL;
584}
585
586/**
587 * vdo_int_map_put() - Try to associate a value with an integer.
588 * @map: The int_map to attempt to modify.
589 * @key: The key with which to associate the new value.
590 * @new_value: The value to be associated with the key.
591 * @update: Whether to overwrite an existing value.
592 * @old_value_ptr: A pointer in which to store either the old value (if the key was already mapped)
593 * or NULL if the map did not contain the key; NULL may be provided if the caller
594 * does not need to know the old value
595 *
596 * Try to associate a value (a pointer) with an integer in an int_map. If the map already contains
597 * a mapping for the provided key, the old value is only replaced with the specified value if
598 * update is true. In either case the old value is returned. If the map does not already contain a
599 * value for the specified key, the new value is added regardless of the value of update.
600 *
601 * Return: VDO_SUCCESS or an error code.
602 */
603int vdo_int_map_put(struct int_map *map, u64 key, void *new_value, bool update,
604 void **old_value_ptr)
605{
606 struct bucket *neighborhood, *bucket;
607
608 if (unlikely(new_value == NULL))
609 return -EINVAL;
610
611 /*
612 * Select the bucket at the start of the neighborhood that must contain any entry for the
613 * provided key.
614 */
615 neighborhood = select_bucket(map, key);
616
617 /*
618 * Check whether the neighborhood already contains an entry for the key, in which case we
619 * optionally update it, returning the old value.
620 */
621 if (update_mapping(neighborhood, key, new_value, update, old_value_ptr))
622 return VDO_SUCCESS;
623
624 /*
625 * Find an empty bucket in the desired neighborhood for the new entry or re-arrange entries
626 * in the map so there is such a bucket. This operation will usually succeed; the loop body
627 * will only be executed on the rare occasions that we have to resize the map.
628 */
629 while ((bucket = find_or_make_vacancy(map, neighborhood)) == NULL) {
630 int result;
631
632 /*
633 * There is no empty bucket in which to put the new entry in the current map, so
634 * we're forced to allocate a new bucket array with a larger capacity, re-hash all
635 * the entries into those buckets, and try again (a very expensive operation for
636 * large maps).
637 */
638 result = resize_buckets(map);
639 if (result != VDO_SUCCESS)
640 return result;
641
642 /*
643 * Resizing the map invalidates all pointers to buckets, so recalculate the
644 * neighborhood pointer.
645 */
646 neighborhood = select_bucket(map, key);
647 }
648
649 /* Put the new entry in the empty bucket, adding it to the neighborhood. */
650 bucket->key = key;
651 bucket->value = new_value;
652 insert_in_hop_list(neighborhood, bucket);
653 map->size += 1;
654
655 /* There was no existing entry, so there was no old value to be returned. */
656 if (old_value_ptr != NULL)
657 *old_value_ptr = NULL;
658 return VDO_SUCCESS;
659}
660
661/**
662 * vdo_int_map_remove() - Remove the mapping for a given key from the int_map.
663 * @map: The int_map from which to remove the mapping.
664 * @key: The key whose mapping is to be removed.
665 *
666 * Return: the value that was associated with the key, or NULL if it was not mapped.
667 */
668void *vdo_int_map_remove(struct int_map *map, u64 key)
669{
670 void *value;
671
672 /* Select the bucket to search and search it for an existing entry. */
673 struct bucket *bucket = select_bucket(map, key);
674 struct bucket *previous;
675 struct bucket *victim = search_hop_list(bucket, key, &previous);
676
677 if (victim == NULL) {
678 /* There is no matching entry to remove. */
679 return NULL;
680 }
681
682 /*
683 * We found an entry to remove. Save the mapped value to return later and empty the bucket.
684 */
685 map->size -= 1;
686 value = victim->value;
687 victim->value = NULL;
688 victim->key = 0;
689
690 /* The victim bucket is now empty, but it still needs to be spliced out of the hop list. */
691 if (previous == NULL) {
692 /* The victim is the head of the list, so swing first_hop. */
693 bucket->first_hop = victim->next_hop;
694 } else {
695 previous->next_hop = victim->next_hop;
696 }
697
698 victim->next_hop = NULL_HOP_OFFSET;
699 return value;
700}