lf_dynarray.cc File Reference

Analog of DYNAMIC_ARRAY that never reallocs (so no pointer into the array may ever become invalid). More...

#include <string.h>
#include <sys/types.h>
#include <algorithm>
#include "lf.h"
#include "my_compiler.h"
#include "my_inttypes.h"
#include "my_macros.h"
#include "my_sys.h"
#include "mysql/service_mysql_alloc.h"
#include "mysys/mysys_priv.h"

Functions
void	lf_dynarray_init (LF_DYNARRAY *array, uint element_size)
static void	recursive_free (std::atomic< void * > *alloc, int level)
void	lf_dynarray_destroy (LF_DYNARRAY *array)
void *	lf_dynarray_lvalue (LF_DYNARRAY *array, uint idx)
void *	lf_dynarray_value (LF_DYNARRAY *array, uint idx)
static int	recursive_iterate (LF_DYNARRAY *array, void *ptr, int level, lf_dynarray_func func, void *arg)
int	lf_dynarray_iterate (LF_DYNARRAY *array, lf_dynarray_func func, void *arg)

Variables
static const ulong	dynarray_idxes_in_prev_levels [LF_DYNARRAY_LEVELS]
static const ulong	dynarray_idxes_in_prev_level [LF_DYNARRAY_LEVELS]

Detailed Description

Analog of DYNAMIC_ARRAY that never reallocs (so no pointer into the array may ever become invalid).

Memory is allocated in non-contiguous chunks. This data structure is not space efficient for sparse arrays.

Every element is aligned to sizeof(element) boundary (to avoid false sharing if element is big enough).

LF_DYNARRAY is a recursive structure. On the zero level LF_DYNARRAY::level[0] it's an array of LF_DYNARRAY_LEVEL_LENGTH elements, on the first level it's an array of LF_DYNARRAY_LEVEL_LENGTH pointers to arrays of elements, on the second level it's an array of pointers to arrays of pointers to arrays of elements. And so on.

With four levels the number of elements is limited to 4311810304 (but as in all functions index is uint, the real limit is 2^32-1)

Actually, it's wait-free, not lock-free ;-)

Function Documentation

lf_dynarray_destroy()

void lf_dynarray_destroy

(

LF_DYNARRAY *

array

)

lf_dynarray_init()

void lf_dynarray_init	(	LF_DYNARRAY *	array,
		uint	element_size
	)

lf_dynarray_iterate()

int lf_dynarray_iterate	(	LF_DYNARRAY *	array,
		lf_dynarray_func	func,
		void *	arg
	)

lf_dynarray_lvalue()

void * lf_dynarray_lvalue	(	LF_DYNARRAY *	array,
		uint	idx
	)

lf_dynarray_value()

void * lf_dynarray_value	(	LF_DYNARRAY *	array,
		uint	idx
	)

recursive_free()

static void recursive_free ( std::atomic< void * > *  alloc, int  level  )

static

recursive_iterate()

static int recursive_iterate ( LF_DYNARRAY *  array, void *  ptr, int  level, lf_dynarray_func  func, void *  arg  )

static

Variable Documentation

dynarray_idxes_in_prev_level

const ulong dynarray_idxes_in_prev_level[LF_DYNARRAY_LEVELS]

static

Initial value:

= {
    0, 
    LF_DYNARRAY_LEVEL_LENGTH,
    LF_DYNARRAY_LEVEL_LENGTH *LF_DYNARRAY_LEVEL_LENGTH,
    LF_DYNARRAY_LEVEL_LENGTH *LF_DYNARRAY_LEVEL_LENGTH
        *LF_DYNARRAY_LEVEL_LENGTH,
}

dynarray_idxes_in_prev_levels

const ulong dynarray_idxes_in_prev_levels[LF_DYNARRAY_LEVELS]

static

Initial value:

= {
    0, 
    LF_DYNARRAY_LEVEL_LENGTH,
    LF_DYNARRAY_LEVEL_LENGTH *LF_DYNARRAY_LEVEL_LENGTH +
        LF_DYNARRAY_LEVEL_LENGTH,
    LF_DYNARRAY_LEVEL_LENGTH *LF_DYNARRAY_LEVEL_LENGTH
            *LF_DYNARRAY_LEVEL_LENGTH +
        LF_DYNARRAY_LEVEL_LENGTH *LF_DYNARRAY_LEVEL_LENGTH +
        LF_DYNARRAY_LEVEL_LENGTH}