(git:27c966b)
Loading...
Searching...
No Matches
dbm_shard.h File Reference
#include <omp.h>

Go to the source code of this file.

Data Structures

struct  dbm_block_t
 Internal struct for storing a block's metadata. More...
struct  dbm_shard_t
 Internal struct for storing a matrix shard. More...

Functions

void dbm_shard_init (dbm_shard_t *shard)
 Internal routine for initializing a shard.
void dbm_shard_copy (dbm_shard_t *shard_a, const dbm_shard_t *shard_b)
 Internal routine for copying content of shard_b into shard_a.
void dbm_shard_release (dbm_shard_t *shard)
 Internal routine for releasing a shard.
static unsigned int dbm_shard_hash (const unsigned int row, const unsigned int col)
 Internal hash function based on Cantor pairing function. https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function Szudzik's elegant pairing proved to be too asymmetric wrt. row / col. Using unsigned int to return a positive number even after overflow.
static int dbm_shard_slot (const dbm_shard_t *shard, const int row, const int col)
 Internal routine for the slot of a block in the shard's hashtable.
static int dbm_shard_nextslot (const dbm_shard_t *shard, const int slot)
 Internal routine for the slot following the given one (probing).
static void dbm_shard_prefetch_slot (const dbm_shard_t *shard, const int row, const int col)
 Internal routines for prefetching an upcoming lookup in two stages: the hashtable slot first, then (once cached) the block it refers to. A lookup otherwise waits for two dependent cache misses.
static void dbm_shard_prefetch_block (const dbm_shard_t *shard, const int row, const int col)
dbm_block_t * dbm_shard_lookup (const dbm_shard_t *shard, const int row, const int col)
 Internal routine for looking up a block from a shard.
void dbm_shard_reserve (dbm_shard_t *shard, int nblocks)
 Internal routine for growing the block metadata of a shard such that it holds nblocks blocks in total without growing again.
dbm_block_t * dbm_shard_promise_new_block (dbm_shard_t *shard, const int row, const int col, const int block_size)
 Internal routine for allocating the metadata of a new block.
void dbm_shard_allocate_promised_blocks (dbm_shard_t *shard)
 Internal routine for allocating and zeroing any promised block's data.
dbm_block_t * dbm_shard_get_or_promise_block (dbm_shard_t *shard, const int row, const int col, const int block_size)
 Internal routine for getting block or promising a new one.
dbm_block_t * dbm_shard_get_or_allocate_block (dbm_shard_t *shard, const int row, const int col, const int block_size)
 Internal routine for getting block or allocating a new one.

Function Documentation

◆ dbm_shard_init()

void dbm_shard_init ( dbm_shard_t * shard)

Internal routine for initializing a shard.

Author
Ole Schuett

Definition at line 63 of file dbm_shard.c.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_copy()

void dbm_shard_copy ( dbm_shard_t * shard_a,
const dbm_shard_t * shard_b )

Internal routine for copying content of shard_b into shard_a.

Author
Ole Schuett

Definition at line 79 of file dbm_shard.c.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_release()

void dbm_shard_release ( dbm_shard_t * shard)

Internal routine for releasing a shard.

Author
Ole Schuett

Definition at line 128 of file dbm_shard.c.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_hash()

unsigned int dbm_shard_hash ( const unsigned int row,
const unsigned int col )
inlinestatic

Internal hash function based on Cantor pairing function. https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function Szudzik's elegant pairing proved to be too asymmetric wrt. row / col. Using unsigned int to return a positive number even after overflow.

Author
Ole Schuett

Definition at line 72 of file dbm_shard.h.

Here is the caller graph for this function:

◆ dbm_shard_slot()

int dbm_shard_slot ( const dbm_shard_t * shard,
const int row,
const int col )
inlinestatic

Internal routine for the slot of a block in the shard's hashtable.

Author
Hans Pabst

Definition at line 81 of file dbm_shard.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_nextslot()

int dbm_shard_nextslot ( const dbm_shard_t * shard,
const int slot )
inlinestatic

Internal routine for the slot following the given one (probing).

Author
Hans Pabst

Definition at line 91 of file dbm_shard.h.

Here is the caller graph for this function:

◆ dbm_shard_prefetch_slot()

void dbm_shard_prefetch_slot ( const dbm_shard_t * shard,
const int row,
const int col )
inlinestatic

Internal routines for prefetching an upcoming lookup in two stages: the hashtable slot first, then (once cached) the block it refers to. A lookup otherwise waits for two dependent cache misses.

Author
Hans Pabst

Definition at line 101 of file dbm_shard.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_prefetch_block()

void dbm_shard_prefetch_block ( const dbm_shard_t * shard,
const int row,
const int col )
inlinestatic

Definition at line 105 of file dbm_shard.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_lookup()

dbm_block_t * dbm_shard_lookup ( const dbm_shard_t * shard,
const int row,
const int col )

Internal routine for looking up a block from a shard.

Author
Ole Schuett

Definition at line 160 of file dbm_shard.c.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_reserve()

void dbm_shard_reserve ( dbm_shard_t * shard,
const int nblocks )

Internal routine for growing the block metadata of a shard such that it holds nblocks blocks in total without growing again.

Author
Ole Schuett and Hans Pabst

Definition at line 185 of file dbm_shard.c.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_promise_new_block()

dbm_block_t * dbm_shard_promise_new_block ( dbm_shard_t * shard,
const int row,
const int col,
const int block_size )

Internal routine for allocating the metadata of a new block.

Author
Ole Schuett

Definition at line 209 of file dbm_shard.c.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_allocate_promised_blocks()

void dbm_shard_allocate_promised_blocks ( dbm_shard_t * shard)

Internal routine for allocating and zeroing any promised block's data.

Author
Ole Schuett

Definition at line 229 of file dbm_shard.c.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_get_or_promise_block()

dbm_block_t * dbm_shard_get_or_promise_block ( dbm_shard_t * shard,
const int row,
const int col,
const int block_size )

Internal routine for getting block or promising a new one.

Author
Ole Schuett

Definition at line 258 of file dbm_shard.c.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dbm_shard_get_or_allocate_block()

dbm_block_t * dbm_shard_get_or_allocate_block ( dbm_shard_t * shard,
const int row,
const int col,
const int block_size )

Internal routine for getting block or allocating a new one.

Author
Ole Schuett

Definition at line 273 of file dbm_shard.c.

Here is the call graph for this function:
Here is the caller graph for this function: