Blender  V3.3
Classes | Namespaces | Macros | Typedefs
BLI_probing_strategies.hh File Reference
#include "BLI_sys_types.h"

Go to the source code of this file.

Classes

class  blender::LinearProbingStrategy
 
class  blender::QuadraticProbingStrategy
 
class  blender::PythonProbingStrategy< LinearSteps, PreShuffle >
 
class  blender::ShuffleProbingStrategy< LinearSteps, PreShuffle >
 

Namespaces

 blender
 

Macros

#define SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX)
 
#define SLOT_PROBING_END()
 

Typedefs

using blender::DefaultProbingStrategy = PythonProbingStrategy<>
 

Detailed Description

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.

Macro Definition Documentation

◆ SLOT_PROBING_BEGIN

#define SLOT_PROBING_BEGIN (   PROBING_STRATEGY,
  HASH,
  MASK,
  R_SLOT_INDEX 
)
Value:
PROBING_STRATEGY probing_strategy(HASH); \
do { \
int64_t linear_offset = 0; \
uint64_t current_hash = probing_strategy.get(); \
do { \
int64_t R_SLOT_INDEX = static_cast<int64_t>((current_hash + static_cast<uint64_t>(linear_offset)) & MASK);
#define MASK
#define HASH(i, j, k)
__int64 int64_t
Definition: stdint.h:89
unsigned __int64 uint64_t
Definition: stdint.h:90

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.

◆ SLOT_PROBING_END

#define SLOT_PROBING_END ( )
Value:
} while (++linear_offset < probing_strategy.linear_steps()); \
probing_strategy.next(); \
} while (true)

Definition at line 226 of file BLI_probing_strategies.hh.