Blender
V3.3
|
#include "BLI_sys_types.h"
Go to the source code of this file.
Namespaces | |
blender | |
Macros | |
#define | SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX) |
#define | SLOT_PROBING_END() |
Typedefs | |
using | blender::DefaultProbingStrategy = PythonProbingStrategy<> |
This file implements different probing strategies. Those can be used by different hash table implementations like blender::Set and blender::Map. A probing strategy produces a sequence of values based on an initial hash value.
A probing strategy has to implement the following methods:
Using linear probing steps between larger jumps can result in better performance, due to improved cache usage. It's a way of getting the benefits or linear probing without the clustering issues. However, more linear steps can also make things slower when the initial hash produces many collisions.
Every probing strategy has to guarantee, that every possible uint64_t is returned eventually. This is necessary for correctness. If this is not the case, empty slots might not be found.
The SLOT_PROBING_BEGIN and SLOT_PROBING_END macros can be used to implement a loop that iterates over a probing sequence.
Probing strategies can be evaluated with many different criteria. Different use cases often have different optimal strategies. Examples:
Definition in file BLI_probing_strategies.hh.
Both macros together form a loop that iterates over slot indices in a hash table with a power-of-two size.
You must not break
out of this loop. Only return
is permitted. If you don't return out of the loop, it will be an infinite loop. These loops should not be nested within the same function.
PROBING_STRATEGY: Class describing the probing strategy. HASH: The initial hash as produced by a hash function. MASK: A bit mask such that (hash & MASK) is a valid slot index. R_SLOT_INDEX: Name of the variable that will contain the slot index.
Definition at line 218 of file BLI_probing_strategies.hh.
#define SLOT_PROBING_END | ( | ) |
Definition at line 226 of file BLI_probing_strategies.hh.