varr.c File Reference

#include "lib/bob.h"
#include "lib/memory.h"
#include "lib/misc.h"
#include "lib/errno.h"
#include "lib/types.h"
#include "lib/string.h"
#include "lib/finject.h"
#include "lib/varr.h"
#include "lib/varr_private.h"
#include <limits.h>
#include "lib/trace.h"

Include dependency graph for varr.c:

Go to the source code of this file.

Macros
#define	M0_TRACE_SUBSYSTEM   M0_TRACE_SUBSYS_LIB
#define	safe_bitshift(num, shift, operator)

Functions
	M0_BOB_DEFINE (M0_INTERNAL, &varr_bobtype, m0_varr)
M0_INTERNAL bool	varr_invariant (const struct m0_varr *arr)
M0_INTERNAL int	varr_buffers_alloc (struct m0_varr *arr)
M0_INTERNAL void	varr_buffers_dealloc (struct m0_varr *arr)
M0_INTERNAL uint32_t	depth_find (const struct m0_varr *arr, uint64_t buff_nr)
M0_INTERNAL uint32_t	index_within_level (const struct m0_varr *arr, uint64_t target_idx, uint32_t depth)
M0_INTERNAL uint32_t	children_of_level (const struct m0_varr *arr, uint32_t level)
M0_INTERNAL void *	cache_fetch (const struct m0_varr *arr, uint64_t index)
M0_INTERNAL void	cache_update (struct m0_varr *arr, void *holder, uint64_t start_index)
M0_INTERNAL unsigned long	varr_obj_nr_in_buff (const struct m0_varr *arr)
M0_INTERNAL uint64_t	total_leaf_buffers (unsigned long nr, unsigned long obj_nr_in_1_cont, uint8_t obj_nr_shift)
M0_INTERNAL uint64_t	max_idx_within_level (const struct m0_varr_cursor *cursor, uint32_t depth)
M0_INTERNAL uint32_t	inc_to_idx_xlate (const struct m0_varr_cursor *cursor, uint64_t carry, uint32_t depth)
M0_INTERNAL uint64_t	inc_for_next_level (const struct m0_varr_cursor *cursor, uint64_t carry, uint32_t depth)
M0_INTERNAL uint8_t	log_radix (const struct m0_varr *arr, uint32_t level)
M0_INTERNAL uint8_t	nearest_power_of_two (size_t num)
M0_INTERNAL uint64_t	last_nbits_set (uint8_t n)
M0_INTERNAL void *	buff_incr (const struct m0_varr *arr, uint32_t depth, void *buff, uint32_t inc)
M0_INTERNAL int	m0_varr_init (struct m0_varr *arr, uint64_t nr, size_t size, size_t bufsize)
M0_INTERNAL int	m0_varr_cursor_init (struct m0_varr_cursor *cursor, const struct m0_varr *arr, uint32_t depth)
M0_INTERNAL void *	m0_varr_cursor_get (struct m0_varr_cursor *cursor)
M0_INTERNAL int	m0_varr_cursor_next (struct m0_varr_cursor *cursor)
M0_INTERNAL int	m0_varr_cursor_move (struct m0_varr_cursor *cursor, uint64_t inc)
M0_INTERNAL void	m0_varr_fini (struct m0_varr *arr)
M0_INTERNAL void *	m0_varr_ele_get (struct m0_varr *arr, uint64_t index)
M0_INTERNAL uint64_t	m0_varr_size (const struct m0_varr *arr)

Variables
M0_INTERNAL const struct m0_bob_type	varr_bobtype

Macro Definition Documentation

M0_TRACE_SUBSYSTEM

#define M0_TRACE_SUBSYSTEM   M0_TRACE_SUBSYS_LIB

Definition at line 39 of file varr.c.

safe_bitshift

#define safe_bitshift	(		num,
			shift,
			operator
	)

Value:

({                                                                       \
        uint8_t     __shift = (shift);                                   \
        typeof(num) __num   = (num);                                     \
        M0_ASSERT(__shift < CHAR_BIT * sizeof __num);                    \
        __num operator __shift;                                          \
})

Shifts a given number to left/right by taking into account sizeof(number)

Definition at line 106 of file varr.c.

Function Documentation

buff_incr()

M0_INTERNAL void * buff_incr	(	const struct m0_varr *	arr,
		uint32_t	depth,
		void *	buff,
		uint32_t	inc
	)

Increments buffer based upon its level in a tree

Definition at line 444 of file varr.c.

Here is the caller graph for this function:

cache_fetch()

M0_INTERNAL void * cache_fetch	(	const struct m0_varr *	arr,
		uint64_t	index
	)

Fetches address of a buffer in which object with index 'index' resides. Returns NULL in case address of the buffer is not present in cache.

Definition at line 535 of file varr.c.

Here is the caller graph for this function:

cache_update()

M0_INTERNAL void cache_update	(	struct m0_varr *	arr,
		void *	holder,
		uint64_t	start_index
	)

Updates the cache with address of a buffer and range of indices residing in it.

Definition at line 547 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

children_of_level()

M0_INTERNAL uint32_t children_of_level	(	const struct m0_varr *	arr,
		uint32_t	level
	)

Returns total number of children for a node at given level in a tree.

Definition at line 301 of file varr.c.

Here is the caller graph for this function:

depth_find()

M0_INTERNAL uint32_t depth_find	(	const struct m0_varr *	arr,
		uint64_t	buff_nr
	)

Evaluates the height of the tree based upon total number of leaf-level buffers to be allocated.

Definition at line 220 of file varr.c.

Here is the caller graph for this function:

inc_for_next_level()

M0_INTERNAL uint64_t inc_for_next_level	(	const struct m0_varr_cursor *	cursor,
		uint64_t	carry,
		uint32_t	depth
	)

Definition at line 396 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

inc_to_idx_xlate()

M0_INTERNAL uint32_t inc_to_idx_xlate	(	const struct m0_varr_cursor *	cursor,
		uint64_t	carry,
		uint32_t	depth
	)

Definition at line 388 of file varr.c.

Here is the caller graph for this function:

index_within_level()

M0_INTERNAL uint32_t index_within_level	(	const struct m0_varr *	arr,
		uint64_t	target_idx,
		uint32_t	depth
	)

Returns index within a buffer at given depth, for a given target_index in an array.

Definition at line 417 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

last_nbits_set()

M0_INTERNAL uint64_t last_nbits_set

(

uint8_t

n

)

Returns a 64-bit number whose last 'n' bits are set, and rest are zero.

Definition at line 437 of file varr.c.

Here is the caller graph for this function:

log_radix()

M0_INTERNAL uint8_t log_radix	(	const struct m0_varr *	arr,
		uint32_t	level
	)

Definition at line 404 of file varr.c.

Here is the caller graph for this function:

M0_BOB_DEFINE()

M0_BOB_DEFINE	(	M0_INTERNAL	,
		&	varr_bobtype,
		m0_varr
	)

max_idx_within_level()

M0_INTERNAL uint64_t max_idx_within_level	(	const struct m0_varr_cursor *	cursor,
		uint32_t	depth
	)

Returns index of the highest numbered node at given depth.

Definition at line 376 of file varr.c.

Here is the caller graph for this function:

nearest_power_of_two()

M0_INTERNAL uint8_t nearest_power_of_two

(

size_t

num

)

Returns the ceiling of logarithm to the base two.

Definition at line 157 of file varr.c.

Here is the caller graph for this function:

total_leaf_buffers()

M0_INTERNAL uint64_t total_leaf_buffers	(	unsigned long	nr,
		unsigned long	obj_nr_in_1_cont,
		uint8_t	obj_nr_shift
	)

Computes number of buffers required at the leaf-level.

Definition at line 178 of file varr.c.

Here is the caller graph for this function:

varr_buffers_alloc()

M0_INTERNAL int varr_buffers_alloc

(

struct m0_varr *

arr

)

Constructs a tree to hold buffers.

Definition at line 237 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

varr_buffers_dealloc()

M0_INTERNAL void varr_buffers_dealloc

(

struct m0_varr *

arr

)

Frees a tree holding buffers.

Definition at line 459 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

varr_invariant()

M0_INTERNAL bool varr_invariant

(

const struct m0_varr *

arr

)

Definition at line 498 of file varr.c.

Here is the caller graph for this function:

varr_obj_nr_in_buff()

M0_INTERNAL unsigned long varr_obj_nr_in_buff

(

const struct m0_varr *

arr

)

Returns number of objects that can fit in a single buffer.

Definition at line 171 of file varr.c.

Here is the caller graph for this function:

Variable Documentation

varr_bobtype

M0_INTERNAL const struct m0_bob_type varr_bobtype

Initial value:

= {
        .bt_name         = "virtual_array",
        .bt_magix_offset = offsetof(struct m0_varr, va_magic),
        .bt_magix        = M0_LIB_GENARRAY_MAGIC,
        .bt_check        = NULL,
}

Definition at line 42 of file varr.c.