|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Copyright (c) 2020 Red Hat, Inc.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This program is free software; you can redistribute it and/or
|
|
Packit Service |
310c69 |
* modify it under the terms of the GNU General Public License
|
|
Packit Service |
310c69 |
* as published by the Free Software Foundation; either version 2
|
|
Packit Service |
310c69 |
* of the License, or (at your option) any later version.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This program is distributed in the hope that it will be useful,
|
|
Packit Service |
310c69 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
310c69 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit Service |
310c69 |
* GNU General Public License for more details.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* You should have received a copy of the GNU General Public License
|
|
Packit Service |
310c69 |
* along with this program; if not, write to the Free Software
|
|
Packit Service |
310c69 |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
|
|
Packit Service |
310c69 |
* 02110-1301, USA.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* $Id: //eng/vdo-releases/aluminum/src/c++/vdo/base/pointerMap.c#1 $
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Hash table implementation of a map from integers to pointers, implemented
|
|
Packit Service |
310c69 |
* using the Hopscotch Hashing algorithm by Herlihy, Shavit, and Tzafrir (see
|
|
Packit Service |
310c69 |
* http://en.wikipedia.org/wiki/Hopscotch_hashing). This implementation does
|
|
Packit Service |
310c69 |
* not contain any of the locking/concurrency features of the algorithm, just
|
|
Packit Service |
310c69 |
* the collision resolution scheme.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* Hopscotch Hashing is based on hashing with open addressing and linear
|
|
Packit Service |
310c69 |
* probing. All the entries are stored in a fixed array of buckets, with no
|
|
Packit Service |
310c69 |
* dynamic allocation for collisions. Unlike linear probing, all the entries
|
|
Packit Service |
310c69 |
* that hash to a given bucket are stored within a fixed neighborhood starting
|
|
Packit Service |
310c69 |
* at that bucket. Chaining is effectively represented as a bit vector
|
|
Packit Service |
310c69 |
* relative to each bucket instead of as pointers or explicit offsets.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* When an empty bucket cannot be found within a given neighborhood,
|
|
Packit Service |
310c69 |
* subsequent neighborhoods are searched, and one or more entries will "hop"
|
|
Packit Service |
310c69 |
* into those neighborhoods. When this process works, an empty bucket will
|
|
Packit Service |
310c69 |
* move into the desired neighborhood, allowing the entry to be added. When
|
|
Packit Service |
310c69 |
* that process fails (typically when the buckets are around 90% full), the
|
|
Packit Service |
310c69 |
* table must be resized and the all entries rehashed and added to the
|
|
Packit Service |
310c69 |
* expanded table.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* Unlike linear probing, the number of buckets that must be searched in the
|
|
Packit Service |
310c69 |
* worst case has a fixed upper bound (the size of the neighborhood). Those
|
|
Packit Service |
310c69 |
* entries occupy a small number of memory cache lines, leading to improved
|
|
Packit Service |
310c69 |
* use of the cache (fewer misses on both successful and unsuccessful
|
|
Packit Service |
310c69 |
* searches). Hopscotch hashing outperforms linear probing at much higher load
|
|
Packit Service |
310c69 |
* factors, so even with the increased memory burden for maintaining the hop
|
|
Packit Service |
310c69 |
* vectors, less memory is needed to achieve that performance. Hopscotch is
|
|
Packit Service |
310c69 |
* also immune to "contamination" from deleting entries since entries are
|
|
Packit Service |
310c69 |
* genuinely removed instead of being replaced by a placeholder.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* The published description of the algorithm used a bit vector, but the paper
|
|
Packit Service |
310c69 |
* alludes to an offset scheme which is used by this implementation. Since the
|
|
Packit Service |
310c69 |
* entries in the neighborhood are within N entries of the hash bucket at the
|
|
Packit Service |
310c69 |
* start of the neighborhood, a pair of small offset fields each log2(N) bits
|
|
Packit Service |
310c69 |
* wide is all that's needed to maintain the hops as a linked list. In order
|
|
Packit Service |
310c69 |
* to encode "no next hop" (i.e. NULL) as the natural initial value of zero,
|
|
Packit Service |
310c69 |
* the offsets are biased by one (i.e. 0 => NULL, 1 => offset=0, 2 =>
|
|
Packit Service |
310c69 |
* offset=1, etc.) We can represent neighborhoods of up to 255 entries with
|
|
Packit Service |
310c69 |
* just 8+8=16 bits per entry. The hop list is sorted by hop offset so the
|
|
Packit Service |
310c69 |
* first entry in the list is always the bucket closest to the start of the
|
|
Packit Service |
310c69 |
* neighborhood.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* While individual accesses tend to be very fast, the table resize operations
|
|
Packit Service |
310c69 |
* are very very expensive. If an upper bound on the latency of adding an
|
|
Packit Service |
310c69 |
* entry to the table is needed, we either need to ensure the table is
|
|
Packit Service |
310c69 |
* pre-sized to be large enough so no resize is ever needed, or we'll need to
|
|
Packit Service |
310c69 |
* develop an approach to incrementally resize the table.
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#include "pointerMap.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#include "errors.h"
|
|
Packit Service |
310c69 |
#include "logger.h"
|
|
Packit Service |
310c69 |
#include "memoryAlloc.h"
|
|
Packit Service |
310c69 |
#include "numeric.h"
|
|
Packit Service |
310c69 |
#include "permassert.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
enum {
|
|
Packit Service |
310c69 |
DEFAULT_CAPACITY = 16, // the number of neighborhoods in a new table
|
|
Packit Service |
310c69 |
NEIGHBORHOOD = 255, // the number of buckets in each neighborhood
|
|
Packit Service |
310c69 |
MAX_PROBES = 1024, // limit on the number of probes for a free bucket
|
|
Packit Service |
310c69 |
NULL_HOP_OFFSET = 0, // the hop offset value terminating the hop list
|
|
Packit Service |
310c69 |
DEFAULT_LOAD = 75 // a compromise between memory use and performance
|
|
Packit Service |
310c69 |
};
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Buckets are packed together to reduce memory usage and improve cache
|
|
Packit Service |
310c69 |
* efficiency. It would be tempting to encode the hop offsets separately and
|
|
Packit Service |
310c69 |
* maintain alignment of key/value pairs, but it's crucial to keep the hop
|
|
Packit Service |
310c69 |
* fields near the buckets that they use them so they'll tend to share cache
|
|
Packit Service |
310c69 |
* lines.
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
typedef struct __attribute__((packed)) bucket {
|
|
Packit Service |
310c69 |
uint8_t firstHop; // the biased offset of the first entry in the hop list
|
|
Packit Service |
310c69 |
// of the neighborhood that hashes to this bucket
|
|
Packit Service |
310c69 |
uint8_t nextHop; // the biased offset of the next bucket in the hop list
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
const void *key; // the key stored in this bucket
|
|
Packit Service |
310c69 |
void *value; // the value stored in this bucket (NULL if empty)
|
|
Packit Service |
310c69 |
} Bucket;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* The concrete definition of the opaque PointerMap type. To avoid having to
|
|
Packit Service |
310c69 |
* wrap the neighborhoods of the last entries back around to the start of the
|
|
Packit Service |
310c69 |
* bucket array, we allocate a few more buckets at the end of the array
|
|
Packit Service |
310c69 |
* instead, which is why capacity and bucketCount are different.
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
struct pointerMap {
|
|
Packit Service |
310c69 |
/** the number of entries stored in the map */
|
|
Packit Service |
310c69 |
size_t size;
|
|
Packit Service |
310c69 |
/** the number of neighborhoods in the map */
|
|
Packit Service |
310c69 |
size_t capacity;
|
|
Packit Service |
310c69 |
/** the number of buckets in the bucket array */
|
|
Packit Service |
310c69 |
size_t bucketCount;
|
|
Packit Service |
310c69 |
/** the array of hash buckets */
|
|
Packit Service |
310c69 |
Bucket *buckets;
|
|
Packit Service |
310c69 |
/** the function for comparing keys for equality */
|
|
Packit Service |
310c69 |
PointerKeyComparator *comparator;
|
|
Packit Service |
310c69 |
/** the function for getting a hash code from a key */
|
|
Packit Service |
310c69 |
PointerKeyHasher *hasher;
|
|
Packit Service |
310c69 |
};
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Initialize a PointerMap.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param map the map to initialize
|
|
Packit Service |
310c69 |
* @param capacity the initial capacity of the map
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int allocateBuckets(PointerMap *map, size_t capacity)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
map->size = 0;
|
|
Packit Service |
310c69 |
map->capacity = capacity;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Allocate NEIGHBORHOOD - 1 extra buckets so the last bucket can have a
|
|
Packit Service |
310c69 |
// full neighborhood without have to wrap back around to element zero.
|
|
Packit Service |
310c69 |
map->bucketCount = capacity + (NEIGHBORHOOD - 1);
|
|
Packit Service |
310c69 |
return ALLOCATE(map->bucketCount, Bucket, "PointerMap buckets",
|
|
Packit Service |
310c69 |
&map->buckets);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
int makePointerMap(size_t initialCapacity,
|
|
Packit Service |
310c69 |
unsigned int initialLoad,
|
|
Packit Service |
310c69 |
PointerKeyComparator comparator,
|
|
Packit Service |
310c69 |
PointerKeyHasher hasher,
|
|
Packit Service |
310c69 |
PointerMap **mapPtr)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
// Use the default initial load if the caller did not specify one.
|
|
Packit Service |
310c69 |
if (initialLoad == 0) {
|
|
Packit Service |
310c69 |
initialLoad = DEFAULT_LOAD;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (initialLoad > 100) {
|
|
Packit Service |
310c69 |
return UDS_INVALID_ARGUMENT;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
PointerMap *map;
|
|
Packit Service |
310c69 |
int result = ALLOCATE(1, PointerMap, "PointerMap", &map);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
map->hasher = hasher;
|
|
Packit Service |
310c69 |
map->comparator = comparator;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Use the default capacity if the caller did not specify one.
|
|
Packit Service |
310c69 |
size_t capacity = (initialCapacity > 0) ? initialCapacity : DEFAULT_CAPACITY;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Scale up the capacity by the specified initial load factor.
|
|
Packit Service |
310c69 |
// (i.e to hold 1000 entries at 80% load we need a capacity of 1250)
|
|
Packit Service |
310c69 |
capacity = capacity * 100 / initialLoad;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
result = allocateBuckets(map, capacity);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
freePointerMap(&map);
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
*mapPtr = map;
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Free the bucket array for the map.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param map the map whose bucket array is to be freed
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void freeBuckets(PointerMap *map)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
FREE(map->buckets);
|
|
Packit Service |
310c69 |
map->buckets = NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
void freePointerMap(PointerMap **mapPtr)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
if (*mapPtr != NULL) {
|
|
Packit Service |
310c69 |
freeBuckets(*mapPtr);
|
|
Packit Service |
310c69 |
FREE(*mapPtr);
|
|
Packit Service |
310c69 |
*mapPtr = NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
size_t pointerMapSize(const PointerMap *map)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
return map->size;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Convert a biased hop offset within a neighborhood to a pointer to the
|
|
Packit Service |
310c69 |
* bucket it references.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param neighborhood the first bucket in the neighborhood
|
|
Packit Service |
310c69 |
* @param hopOffset the biased hop offset to the desired bucket
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return NULL if hopOffset is zero, otherwise a pointer to
|
|
Packit Service |
310c69 |
* the bucket in the neighborhood at hopOffset - 1
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static Bucket *dereferenceHop(Bucket *neighborhood, unsigned int hopOffset)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
if (hopOffset == NULL_HOP_OFFSET) {
|
|
Packit Service |
310c69 |
return NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
STATIC_ASSERT(NULL_HOP_OFFSET == 0);
|
|
Packit Service |
310c69 |
return &neighborhood[hopOffset - 1];
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Add a bucket into the hop list for the neighborhood, inserting it into the
|
|
Packit Service |
310c69 |
* list so the hop list remains sorted by hop offset.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param neighborhood the first bucket in the neighborhood
|
|
Packit Service |
310c69 |
* @param newBucket the bucket to add to the hop list
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void insertInHopList(Bucket *neighborhood, Bucket *newBucket)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
// Zero indicates a NULL hop offset, so bias the hop offset by one.
|
|
Packit Service |
310c69 |
int hopOffset = 1 + (newBucket - neighborhood);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Handle the special case of adding a bucket at the start of the list.
|
|
Packit Service |
310c69 |
int nextHop = neighborhood->firstHop;
|
|
Packit Service |
310c69 |
if ((nextHop == NULL_HOP_OFFSET) || (nextHop > hopOffset)) {
|
|
Packit Service |
310c69 |
newBucket->nextHop = nextHop;
|
|
Packit Service |
310c69 |
neighborhood->firstHop = hopOffset;
|
|
Packit Service |
310c69 |
return;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Search the hop list for the insertion point that maintains the sort
|
|
Packit Service |
310c69 |
// order.
|
|
Packit Service |
310c69 |
for (;;) {
|
|
Packit Service |
310c69 |
Bucket *bucket = dereferenceHop(neighborhood, nextHop);
|
|
Packit Service |
310c69 |
nextHop = bucket->nextHop;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
if ((nextHop == NULL_HOP_OFFSET) || (nextHop > hopOffset)) {
|
|
Packit Service |
310c69 |
newBucket->nextHop = nextHop;
|
|
Packit Service |
310c69 |
bucket->nextHop = hopOffset;
|
|
Packit Service |
310c69 |
return;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Select and return the hash bucket for a given search key.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param map the map to search
|
|
Packit Service |
310c69 |
* @param key the mapping key
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static Bucket *selectBucket(const PointerMap *map, const void *key)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Scale the 32-bit hash to a bucket index by treating it as a binary
|
|
Packit Service |
310c69 |
* fraction and multiplying that by the capacity. If the hash is uniformly
|
|
Packit Service |
310c69 |
* distributed over [0 .. 2^32-1], then (hash * capacity / 2^32) should be
|
|
Packit Service |
310c69 |
* uniformly distributed over [0 .. capacity-1]. The multiply and shift is
|
|
Packit Service |
310c69 |
* much faster than a divide (modulus) on X86 CPUs.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
uint64_t hash = map->hasher(key);
|
|
Packit Service |
310c69 |
return &map->buckets[(hash * map->capacity) >> 32];
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Search the hop list associated with given hash bucket for a given search
|
|
Packit Service |
310c69 |
* key. If the key is found, returns a pointer to the entry (bucket or
|
|
Packit Service |
310c69 |
* collision), otherwise returns NULL .
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param [in] map the map being searched
|
|
Packit Service |
310c69 |
* @param [in] bucket the map bucket to search for the key
|
|
Packit Service |
310c69 |
* @param [in] key the mapping key
|
|
Packit Service |
310c69 |
* @param [out] previousPtr if not NULL , a pointer in which to
|
|
Packit Service |
310c69 |
* store the bucket in the list preceding the one
|
|
Packit Service |
310c69 |
* that had the matching key
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return an entry that matches the key, or NULL if not found
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static Bucket *searchHopList(PointerMap *map,
|
|
Packit Service |
310c69 |
Bucket *bucket,
|
|
Packit Service |
310c69 |
const void *key,
|
|
Packit Service |
310c69 |
Bucket **previousPtr)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
Bucket *previous = NULL;
|
|
Packit Service |
310c69 |
unsigned int nextHop = bucket->firstHop;
|
|
Packit Service |
310c69 |
while (nextHop != NULL_HOP_OFFSET) {
|
|
Packit Service |
310c69 |
// Check the neighboring bucket indexed by the offset for the desired key.
|
|
Packit Service |
310c69 |
Bucket *entry = dereferenceHop(bucket, nextHop);
|
|
Packit Service |
310c69 |
if ((entry->value != NULL) && map->comparator(key, entry->key)) {
|
|
Packit Service |
310c69 |
if (previousPtr != NULL) {
|
|
Packit Service |
310c69 |
*previousPtr = previous;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return entry;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
nextHop = entry->nextHop;
|
|
Packit Service |
310c69 |
previous = entry;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
void *pointerMapGet(PointerMap *map, const void *key)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
Bucket *match = searchHopList(map, selectBucket(map, key), key, NULL);
|
|
Packit Service |
310c69 |
return ((match != NULL) ? match->value : NULL);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Increase the number of hash buckets and rehash all the existing entries,
|
|
Packit Service |
310c69 |
* storing them in the new buckets.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param map the map to resize
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int resizeBuckets(PointerMap *map)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
// Copy the top-level map data to the stack.
|
|
Packit Service |
310c69 |
PointerMap oldMap = *map;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Re-initialize the map to be empty and 50% larger.
|
|
Packit Service |
310c69 |
size_t newCapacity = map->capacity / 2 * 3;
|
|
Packit Service |
310c69 |
logInfo("%s: attempting resize from %zu to %zu, current size=%zu",
|
|
Packit Service |
310c69 |
__func__, map->capacity, newCapacity, map->size);
|
|
Packit Service |
310c69 |
int result = allocateBuckets(map, newCapacity);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
*map = oldMap;
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Populate the new hash table from the entries in the old bucket array.
|
|
Packit Service |
310c69 |
for (size_t i = 0; i < oldMap.bucketCount; i++) {
|
|
Packit Service |
310c69 |
Bucket *entry = &oldMap.buckets[i];
|
|
Packit Service |
310c69 |
if (entry->value == NULL) {
|
|
Packit Service |
310c69 |
continue;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
result = pointerMapPut(map, entry->key, entry->value, true, NULL);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
// Destroy the new partial map and restore the map from the stack.
|
|
Packit Service |
310c69 |
freeBuckets(map);
|
|
Packit Service |
310c69 |
*map = oldMap;
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Destroy the old bucket array.
|
|
Packit Service |
310c69 |
freeBuckets(&oldMap);
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Probe the bucket array starting at the given bucket for the next empty
|
|
Packit Service |
310c69 |
* bucket, returning a pointer to it. NULL will be returned if
|
|
Packit Service |
310c69 |
* the search reaches the end of the bucket array or if the number of linear
|
|
Packit Service |
310c69 |
* probes exceeds a specified limit.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param map the map containing the buckets to search
|
|
Packit Service |
310c69 |
* @param bucket the bucket at which to start probing
|
|
Packit Service |
310c69 |
* @param maxProbes the maximum number of buckets to search
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the next empty bucket, or NULL if the search failed
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static Bucket *findEmptyBucket(PointerMap *map,
|
|
Packit Service |
310c69 |
Bucket *bucket,
|
|
Packit Service |
310c69 |
unsigned int maxProbes)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
// Limit the search to either the nearer of the end of the bucket array or a
|
|
Packit Service |
310c69 |
// fixed distance beyond the initial bucket.
|
|
Packit Service |
310c69 |
size_t remaining = &map->buckets[map->bucketCount] - bucket;
|
|
Packit Service |
310c69 |
Bucket *sentinel = &bucket[minSizeT(remaining, maxProbes)];
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
for (Bucket *entry = bucket; entry < sentinel; entry++) {
|
|
Packit Service |
310c69 |
if (entry->value == NULL) {
|
|
Packit Service |
310c69 |
return entry;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Move an empty bucket closer to the start of the bucket array. This searches
|
|
Packit Service |
310c69 |
* the neighborhoods that contain the empty bucket for a non-empty bucket
|
|
Packit Service |
310c69 |
* closer to the start of the array. If such a bucket is found, this swaps the
|
|
Packit Service |
310c69 |
* two buckets by moving the entry to the empty bucket.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param map the map containing the bucket
|
|
Packit Service |
310c69 |
* @param hole the empty bucket to fill with an entry that precedes it in one
|
|
Packit Service |
310c69 |
* of its enclosing neighborhoods
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the bucket that was vacated by moving its entry to the provided
|
|
Packit Service |
310c69 |
* hole, or NULL if no entry could be moved
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static Bucket *moveEmptyBucket(PointerMap *map __attribute__((unused)),
|
|
Packit Service |
310c69 |
Bucket *hole)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Examine every neighborhood that the empty bucket is part of, starting
|
|
Packit Service |
310c69 |
* with the one in which it is the last bucket. No boundary check is needed
|
|
Packit Service |
310c69 |
* for the negative array arithmetic since this function is only called when
|
|
Packit Service |
310c69 |
* hole is at least NEIGHBORHOOD cells deeper into the array than a valid
|
|
Packit Service |
310c69 |
* bucket.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
for (Bucket *bucket = &hole[1 - NEIGHBORHOOD]; bucket < hole; bucket++) {
|
|
Packit Service |
310c69 |
// Find the entry that is nearest to the bucket, which means it will be
|
|
Packit Service |
310c69 |
// nearest to the hash bucket whose neighborhood is full.
|
|
Packit Service |
310c69 |
Bucket *newHole = dereferenceHop(bucket, bucket->firstHop);
|
|
Packit Service |
310c69 |
if (newHole == NULL) {
|
|
Packit Service |
310c69 |
// There are no buckets in this neighborhood that are in use by this one
|
|
Packit Service |
310c69 |
// (they must all be owned by overlapping neighborhoods).
|
|
Packit Service |
310c69 |
continue;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Skip this bucket if its first entry is actually further away than the
|
|
Packit Service |
310c69 |
// hole that we're already trying to fill.
|
|
Packit Service |
310c69 |
if (hole < newHole) {
|
|
Packit Service |
310c69 |
continue;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* We've found an entry in this neighborhood that we can "hop" further
|
|
Packit Service |
310c69 |
* away, moving the hole closer to the hash bucket, if not all the way
|
|
Packit Service |
310c69 |
* into its neighborhood.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// The entry that will be the new hole is the first bucket in the list,
|
|
Packit Service |
310c69 |
// so setting firstHop is all that's needed remove it from the list.
|
|
Packit Service |
310c69 |
bucket->firstHop = newHole->nextHop;
|
|
Packit Service |
310c69 |
newHole->nextHop = NULL_HOP_OFFSET;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Move the entry into the original hole.
|
|
Packit Service |
310c69 |
hole->key = newHole->key;
|
|
Packit Service |
310c69 |
hole->value = newHole->value;
|
|
Packit Service |
310c69 |
newHole->value = NULL;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Insert the filled hole into the hop list for the neighborhood.
|
|
Packit Service |
310c69 |
insertInHopList(bucket, hole);
|
|
Packit Service |
310c69 |
return newHole;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// We couldn't find an entry to relocate to the hole.
|
|
Packit Service |
310c69 |
return NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Find and update any existing mapping for a given key, returning the value
|
|
Packit Service |
310c69 |
* associated with the key in the provided pointer.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param [in] map the PointerMap to attempt to modify
|
|
Packit Service |
310c69 |
* @param [in] neighborhood the first bucket in the neighborhood that
|
|
Packit Service |
310c69 |
* would contain the search key
|
|
Packit Service |
310c69 |
* @param [in] key the key with which to associate the new value
|
|
Packit Service |
310c69 |
* @param [in] newValue the value to be associated with the key
|
|
Packit Service |
310c69 |
* @param [in] update whether to overwrite an existing value
|
|
Packit Service |
310c69 |
* @param [out] oldValuePtr a pointer in which to store the old value
|
|
Packit Service |
310c69 |
* (unmodified if no mapping was found)
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return true if the map contains a mapping for the key
|
|
Packit Service |
310c69 |
* false if it does not
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static bool updateMapping(PointerMap *map,
|
|
Packit Service |
310c69 |
Bucket *neighborhood,
|
|
Packit Service |
310c69 |
const void *key,
|
|
Packit Service |
310c69 |
void *newValue,
|
|
Packit Service |
310c69 |
bool update,
|
|
Packit Service |
310c69 |
void **oldValuePtr)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
Bucket *bucket = searchHopList(map, neighborhood, key, NULL);
|
|
Packit Service |
310c69 |
if (bucket == NULL) {
|
|
Packit Service |
310c69 |
// There is no bucket containing the key in the neighborhood.
|
|
Packit Service |
310c69 |
return false;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Return the value of the current mapping (if desired) and update the
|
|
Packit Service |
310c69 |
// mapping with the new value (if desired).
|
|
Packit Service |
310c69 |
if (oldValuePtr != NULL) {
|
|
Packit Service |
310c69 |
*oldValuePtr = bucket->value;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (update) {
|
|
Packit Service |
310c69 |
// We're dropping the old key pointer on the floor here, assuming it's a
|
|
Packit Service |
310c69 |
// property of the value or that it's otherwise safe to just forget.
|
|
Packit Service |
310c69 |
bucket->key = key;
|
|
Packit Service |
310c69 |
bucket->value = newValue;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return true;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Find an empty bucket in a specified neighborhood for a new mapping or
|
|
Packit Service |
310c69 |
* attempt to re-arrange mappings so there is such a bucket. This operation
|
|
Packit Service |
310c69 |
* may fail (returning NULL) if an empty bucket is not available or could not
|
|
Packit Service |
310c69 |
* be relocated to the neighborhood.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param map the PointerMap to search or modify
|
|
Packit Service |
310c69 |
* @param neighborhood the first bucket in the neighborhood in which
|
|
Packit Service |
310c69 |
* an empty bucket is needed for a new mapping
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return a pointer to an empty bucket in the desired neighborhood, or
|
|
Packit Service |
310c69 |
* NULL if a vacancy could not be found or arranged
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static Bucket *findOrMakeVacancy(PointerMap *map, Bucket *neighborhood)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
// Probe within and beyond the neighborhood for the first empty bucket.
|
|
Packit Service |
310c69 |
Bucket *hole = findEmptyBucket(map, neighborhood, MAX_PROBES);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Keep trying until the empty bucket is in the bucket's neighborhood or we
|
|
Packit Service |
310c69 |
// are unable to move it any closer by swapping it with a filled bucket.
|
|
Packit Service |
310c69 |
while (hole != NULL) {
|
|
Packit Service |
310c69 |
int distance = hole - neighborhood;
|
|
Packit Service |
310c69 |
if (distance < NEIGHBORHOOD) {
|
|
Packit Service |
310c69 |
// We've found or relocated an empty bucket close enough to the initial
|
|
Packit Service |
310c69 |
// hash bucket to be referenced by its hop vector.
|
|
Packit Service |
310c69 |
return hole;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// The nearest empty bucket isn't within the neighborhood that must
|
|
Packit Service |
310c69 |
// contain the new entry, so try to swap it with bucket that is closer.
|
|
Packit Service |
310c69 |
hole = moveEmptyBucket(map, hole);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
return NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
int pointerMapPut(PointerMap *map,
|
|
Packit Service |
310c69 |
const void *key,
|
|
Packit Service |
310c69 |
void *newValue,
|
|
Packit Service |
310c69 |
bool update,
|
|
Packit Service |
310c69 |
void **oldValuePtr)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
if (newValue == NULL) {
|
|
Packit Service |
310c69 |
return UDS_INVALID_ARGUMENT;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Select the bucket at the start of the neighborhood that must contain any
|
|
Packit Service |
310c69 |
// entry for the provided key.
|
|
Packit Service |
310c69 |
Bucket *neighborhood = selectBucket(map, key);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Check whether the neighborhood already contains an entry for the key, in
|
|
Packit Service |
310c69 |
// which case we optionally update it, returning the old value.
|
|
Packit Service |
310c69 |
if (updateMapping(map, neighborhood, key, newValue, update, oldValuePtr)) {
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Find an empty bucket in the desired neighborhood for the new entry or
|
|
Packit Service |
310c69 |
* re-arrange entries in the map so there is such a bucket. This operation
|
|
Packit Service |
310c69 |
* will usually succeed; the loop body will only be executed on the rare
|
|
Packit Service |
310c69 |
* occasions that we have to resize the map.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
Bucket *bucket;
|
|
Packit Service |
310c69 |
while ((bucket = findOrMakeVacancy(map, neighborhood)) == NULL) {
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* There is no empty bucket in which to put the new entry in the current
|
|
Packit Service |
310c69 |
* map, so we're forced to allocate a new bucket array with a larger
|
|
Packit Service |
310c69 |
* capacity, re-hash all the entries into those buckets, and try again (a
|
|
Packit Service |
310c69 |
* very expensive operation for large maps).
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
int result = resizeBuckets(map);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Resizing the map invalidates all pointers to buckets, so recalculate
|
|
Packit Service |
310c69 |
// the neighborhood pointer.
|
|
Packit Service |
310c69 |
neighborhood = selectBucket(map, key);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Put the new entry in the empty bucket, adding it to the neighborhood.
|
|
Packit Service |
310c69 |
bucket->key = key;
|
|
Packit Service |
310c69 |
bucket->value = newValue;
|
|
Packit Service |
310c69 |
insertInHopList(neighborhood, bucket);
|
|
Packit Service |
310c69 |
map->size += 1;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// There was no existing entry, so there was no old value to be returned.
|
|
Packit Service |
310c69 |
if (oldValuePtr != NULL) {
|
|
Packit Service |
310c69 |
*oldValuePtr = NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
void *pointerMapRemove(PointerMap *map, const void *key)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
// Select the bucket to search and search it for an existing entry.
|
|
Packit Service |
310c69 |
Bucket *bucket = selectBucket(map, key);
|
|
Packit Service |
310c69 |
Bucket *previous;
|
|
Packit Service |
310c69 |
Bucket *victim = searchHopList(map, bucket, key, &previous);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
if (victim == NULL) {
|
|
Packit Service |
310c69 |
// There is no matching entry to remove.
|
|
Packit Service |
310c69 |
return NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// We found an entry to remove. Save the mapped value to return later and
|
|
Packit Service |
310c69 |
// empty the bucket.
|
|
Packit Service |
310c69 |
map->size -= 1;
|
|
Packit Service |
310c69 |
void *value = victim->value;
|
|
Packit Service |
310c69 |
victim->value = NULL;
|
|
Packit Service |
310c69 |
victim->key = 0;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// The victim bucket is now empty, but it still needs to be spliced out of
|
|
Packit Service |
310c69 |
// the hop list.
|
|
Packit Service |
310c69 |
if (previous == NULL) {
|
|
Packit Service |
310c69 |
// The victim is the head of the list, so swing firstHop.
|
|
Packit Service |
310c69 |
bucket->firstHop = victim->nextHop;
|
|
Packit Service |
310c69 |
} else {
|
|
Packit Service |
310c69 |
previous->nextHop = victim->nextHop;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
victim->nextHop = NULL_HOP_OFFSET;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
return value;
|
|
Packit Service |
310c69 |
}
|