qht header¶

The documentation of QEMU’s qemu/qht.h header.

struct qht_stats¶: Statistics of a QHT

Definition

struct qht_stats {
  size_t head_buckets;
  size_t used_head_buckets;
  size_t entries;
  struct qdist chain;
  struct qdist occupancy;
};

Members

head_buckets: number of head buckets
used_head_buckets: number of non-empty head buckets
entries: total number of entries
chain: frequency distribution representing the number of buckets in each chain, excluding empty chains.
occupancy: frequency distribution representing chain occupancy rate. Valid range: from 0.0 (empty) to 1.0 (full occupancy).

Description

An entry is a pointer-hash pair. Each bucket can host several entries. Chains are chains of buckets, whose first link is always a head bucket.

void qht_init(struct qht * ht, qht_cmp_func_t cmp, size_t n_elems, unsigned int mode)¶: Initialize a QHT

Parameters

struct qht * ht: QHT to be initialized
qht_cmp_func_t cmp: default comparison function. Cannot be NULL.
size_t n_elems: number of entries the hash table should be optimized for.
unsigned int mode: bitmask with OR’ed QHT_MODE_*

void qht_destroy(struct qht * ht)¶: destroy a previously initialized QHT

Parameters

struct qht * ht: QHT to be destroyed

Description

Call only when there are no readers/writers left.

bool qht_insert(struct qht * ht, void * p, uint32_t hash, void ** existing)¶: Insert a pointer into the hash table

Parameters

struct qht * ht: QHT to insert to
void * p: pointer to be inserted
uint32_t hash: hash corresponding to p
void ** existing: address where the pointer to an existing entry can be copied to

Description

Attempting to insert a NULL p is a bug. Inserting the same pointer p with different hash values is a bug.

In case of successful operation, smp_wmb() is implied before the pointer is inserted into the hash table.

Returns true on success. Returns false if there is an existing entry in the table that is equivalent (i.e. ht->cmp matches and the hash is the same) to p-h. If existing is !NULL, a pointer to this existing entry is copied to it.

void * qht_lookup_custom(const struct qht * ht, const void * userp, uint32_t hash, qht_lookup_func_t func)¶: Look up a pointer using a custom comparison function.

Parameters

const struct qht * ht: QHT to be looked up
const void * userp: pointer to pass to func
uint32_t hash: hash of the pointer to be looked up
qht_lookup_func_t func: function to compare existing pointers against userp

Description

Needs to be called under an RCU read-critical section.

smp_read_barrier_depends() is implied before the call to func.

The user-provided func compares pointers in QHT against userp. If the function returns true, a match has been found.

Returns the corresponding pointer when a match is found. Returns NULL otherwise.

void * qht_lookup(const struct qht * ht, const void * userp, uint32_t hash)¶: Look up a pointer in a QHT

Parameters

const struct qht * ht: QHT to be looked up
const void * userp: pointer to pass to the comparison function
uint32_t hash: hash of the pointer to be looked up

Description

Calls qht_lookup_custom() using ht‘s default comparison function.

bool qht_remove(struct qht * ht, const void * p, uint32_t hash)¶: remove a pointer from the hash table

Parameters

struct qht * ht: QHT to remove from
const void * p: pointer to be removed
uint32_t hash: hash corresponding to p

Description

Attempting to remove a NULL p is a bug.

Just-removed p pointers cannot be immediately freed; they need to remain valid until the end of the RCU grace period in which qht_remove() is called. This guarantees that concurrent lookups will always compare against valid data.

Returns true on success. Returns false if the p-hash pair was not found.

void qht_reset(struct qht * ht)¶: reset a QHT

Parameters

struct qht * ht: QHT to be reset

Description

All entries in the hash table are reset. No resizing is performed.

If concurrent readers may exist, the objects pointed to by the hash table must remain valid for the existing RCU grace period – see qht_remove(). See also: qht_reset_size()

bool qht_reset_size(struct qht * ht, size_t n_elems)¶: reset and resize a QHT

Parameters

struct qht * ht: QHT to be reset and resized
size_t n_elems: number of entries the resized hash table should be optimized for.

Description

Returns true if the resize was necessary and therefore performed. Returns false otherwise.

If concurrent readers may exist, the objects pointed to by the hash table must remain valid for the existing RCU grace period – see qht_remove(). See also: qht_reset(), qht_resize().

bool qht_resize(struct qht * ht, size_t n_elems)¶: resize a QHT

Parameters

struct qht * ht: QHT to be resized
size_t n_elems: number of entries the resized hash table should be optimized for

Description

Returns true on success. Returns false if the resize was not necessary and therefore not performed. See also: qht_reset_size().

void qht_iter(struct qht * ht, qht_iter_func_t func, void * userp)¶: Iterate over a QHT

Parameters

struct qht * ht: QHT to be iterated over
qht_iter_func_t func: function to be called for each entry in QHT
void * userp: additional pointer to be passed to func

Description

Each time it is called, user-provided func is passed a pointer-hash pair, plus userp.

Note

ht cannot be accessed from func See also: qht_iter_remove()

void qht_iter_remove(struct qht * ht, qht_iter_bool_func_t func, void * userp)¶: Iterate over a QHT, optionally removing entries

Parameters

struct qht * ht: QHT to be iterated over
qht_iter_bool_func_t func: function to be called for each entry in QHT
void * userp: additional pointer to be passed to func

Description

Each time it is called, user-provided func is passed a pointer-hash pair, plus userp. If func returns true, the pointer-hash pair is removed.

Note

ht cannot be accessed from func See also: qht_iter()

void qht_statistics_init(const struct qht * ht, struct qht_stats * stats)¶: Gather statistics from a QHT

Parameters

const struct qht * ht: QHT to gather statistics from
struct qht_stats * stats: pointer to a struct qht_stats to be filled in

Description

Does NOT need to be called under an RCU read-critical section, since it does not dereference any pointers stored in the hash table.

When done with stats, pass the struct to qht_statistics_destroy(). Failing to do this will leak memory.

void qht_statistics_destroy(struct qht_stats * stats)¶: Destroy a struct qht_stats

Parameters

struct qht_stats * stats: struct qht_stats to be destroyed

Description