MySQL 8.0.30
Source Code Documentation
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

◆ dynarray_idxes_in_prev_levels