Blender: BLI_memiter.c File Reference

Blender V4.3

#include <stdlib.h>
#include <string.h>
#include "BLI_asan.h"
#include "BLI_utildefines.h"
#include "BLI_memiter.h"
#include "MEM_guardedalloc.h"
#include "BLI_strict_flags.h"

Go to the source code of this file.

Classes
struct	BLI_memiter_elem

struct	BLI_memiter_chunk

struct	BLI_memiter

Macros
#define	PADUP(num, pad) (((num) + ((pad)-1)) & ~((pad)-1))

Typedefs
typedef uintptr_t	data_t

typedef intptr_t	offset_t

typedef struct BLI_memiter_elem	BLI_memiter_elem

typedef struct BLI_memiter_chunk	BLI_memiter_chunk

typedef struct BLI_memiter	BLI_memiter

Functions
BLI_INLINE uint	data_offset_from_size (uint size)

static void	memiter_set_rewind_offset (BLI_memiter *mi)

static void	memiter_init (BLI_memiter *mi)

Public API's
BLI_memiter *	BLI_memiter_create (uint chunk_size_min)

void *	BLI_memiter_alloc (BLI_memiter *mi, uint elem_size)

void *	BLI_memiter_calloc (BLI_memiter *mi, uint elem_size)

void	BLI_memiter_alloc_from (BLI_memiter mi, uint elem_size, const void data_from)

static void	memiter_free_data (BLI_memiter *mi)

void	BLI_memiter_destroy (BLI_memiter *mi)

void	BLI_memiter_clear (BLI_memiter *mi)

uint	BLI_memiter_count (const BLI_memiter *mi)

Helper API's
void *	BLI_memiter_elem_first (BLI_memiter *mi)

void *	BLI_memiter_elem_first_size (BLI_memiter mi, uint r_size)

Iterator API's
Note We could loop over elements until a NULL chunk is found, however this means every allocation needs to preemptively run memiter_set_rewind_offset (see #USE_TERMINATE_PARANOID). Unless we have a call to finalize allocation (which complicates usage). So use a counter instead.
void	BLI_memiter_iter_init (BLI_memiter mi, BLI_memiter_handle iter)

bool	BLI_memiter_iter_done (const BLI_memiter_handle *iter)

BLI_INLINE void	memiter_chunk_step (BLI_memiter_handle *iter)

void *	BLI_memiter_iter_step_size (BLI_memiter_handle iter, uint r_size)

void *	BLI_memiter_iter_step (BLI_memiter_handle *iter)

Detailed Description

Simple, fast memory allocator for allocating many small elements of different sizes in fixed size memory chunks, although allocations bigger than the chunk size are supported. They will reduce the efficiency of this data-structure. Elements are pointer aligned.

Supports:

Allocation of mixed sizes.
Iterating over allocations in-order.
Clearing for re-use.

Unsupported:

Freeing individual elements.

Note: We could inline iteration stepping, but tests show this doesn't give noticeable speedup.

Definition in file BLI_memiter.c.

Macro Definition Documentation

◆ PADUP

#define PADUP	(		num,
			pad ) (((num) + ((pad)-1)) & ~((pad)-1))

Definition at line 53 of file BLI_memiter.c.

Referenced by data_offset_from_size().

Typedef Documentation

◆ BLI_memiter

typedef struct BLI_memiter BLI_memiter

◆ BLI_memiter_chunk

typedef struct BLI_memiter_chunk BLI_memiter_chunk

◆ BLI_memiter_elem

typedef struct BLI_memiter_elem BLI_memiter_elem

◆ data_t

typedef uintptr_t data_t

Definition at line 42 of file BLI_memiter.c.

◆ offset_t

typedef intptr_t offset_t

Definition at line 43 of file BLI_memiter.c.

Function Documentation

◆ BLI_memiter_alloc()

void * BLI_memiter_alloc	(	BLI_memiter *	mi,
		uint	elem_size )

◆ BLI_memiter_alloc_from()

void BLI_memiter_alloc_from	(	BLI_memiter *	mi,
		uint	elem_size,
		const void *	data_from )

Definition at line 200 of file BLI_memiter.c.

References BLI_memiter_alloc().

◆ BLI_memiter_calloc()

void * BLI_memiter_calloc	(	BLI_memiter *	mi,
		uint	elem_size )

Definition at line 193 of file BLI_memiter.c.

References BLI_memiter_alloc(), and data.

◆ BLI_memiter_clear()

void BLI_memiter_clear ( BLI_memiter * mi )

Definition at line 226 of file BLI_memiter.c.

References memiter_free_data(), and memiter_init().

◆ BLI_memiter_count()

uint BLI_memiter_count ( const BLI_memiter * mi )

Definition at line 232 of file BLI_memiter.c.

References BLI_memiter::count.

◆ BLI_memiter_create()

BLI_memiter * BLI_memiter_create ( unsigned int chunk_size_min )

Parameters

chunk_size_min Should be a power of two and significantly larger than the average element size used.

While allocations of any size are supported, they won't be efficient (effectively becoming a single-linked list).

Its intended that many elements can be stored per chunk.

Definition at line 116 of file BLI_memiter.c.

References BLI_memiter::chunk_size_in_bytes_min, MEM_mallocN, MEM_SIZE_OVERHEAD, and memiter_init().

Referenced by DRW_text_cache_create(), memiter_empty_test(), memiter_string_test(), memiter_words10k_test(), and TEST().

◆ BLI_memiter_destroy()

void BLI_memiter_destroy ( BLI_memiter * mi )

Definition at line 220 of file BLI_memiter.c.

References MEM_freeN(), and memiter_free_data().

Referenced by DRW_text_cache_destroy(), memiter_empty_test(), memiter_string_test(), memiter_words10k_test(), and TEST().

◆ BLI_memiter_elem_first()

void * BLI_memiter_elem_first ( BLI_memiter * mi )

Support direct lookup for the first item.

Definition at line 243 of file BLI_memiter.c.

References BLI_memiter_chunk::data, BLI_memiter_elem::data, BLI_memiter::head, and NULL.

◆ BLI_memiter_elem_first_size()

void * BLI_memiter_elem_first_size	(	BLI_memiter *	mi,
		uint *	r_size )

Definition at line 253 of file BLI_memiter.c.

References BLI_memiter_chunk::data, BLI_memiter_elem::data, BLI_memiter::head, NULL, and BLI_memiter_elem::size.

◆ BLI_memiter_iter_done()

bool BLI_memiter_iter_done ( const BLI_memiter_handle * iter )

Definition at line 283 of file BLI_memiter.c.

References BLI_memiter_handle::elem_left.

◆ BLI_memiter_iter_init()

void BLI_memiter_iter_init	(	BLI_memiter *	mi,
		BLI_memiter_handle *	iter )

Definition at line 277 of file BLI_memiter.c.

References BLI_memiter::count, BLI_memiter_chunk::data, BLI_memiter_handle::elem, BLI_memiter_handle::elem_left, BLI_memiter::head, and NULL.

◆ BLI_memiter_iter_step()

void * BLI_memiter_iter_step ( BLI_memiter_handle * iter )

Definition at line 314 of file BLI_memiter.c.

References BLI_assert, BLI_memiter_elem::data, data, data_offset_from_size(), BLI_memiter_handle::elem, BLI_memiter_handle::elem_left, memiter_chunk_step(), NULL, BLI_memiter_elem::size, and UNLIKELY.

Referenced by DRW_text_cache_draw(), and drw_text_cache_draw_ex().

◆ BLI_memiter_iter_step_size()

void * BLI_memiter_iter_step_size	(	BLI_memiter_handle *	iter,
		uint *	r_size )

Definition at line 297 of file BLI_memiter.c.

References BLI_assert, BLI_memiter_elem::data, data, data_offset_from_size(), BLI_memiter_handle::elem, BLI_memiter_handle::elem_left, memiter_chunk_step(), NULL, BLI_memiter_elem::size, size(), and UNLIKELY.

◆ data_offset_from_size()

BLI_INLINE uint data_offset_from_size ( uint size )

Definition at line 85 of file BLI_memiter.c.

References PADUP.

Referenced by BLI_memiter_alloc(), BLI_memiter_iter_step(), and BLI_memiter_iter_step_size().

◆ memiter_chunk_step()

BLI_INLINE void memiter_chunk_step ( BLI_memiter_handle * iter )

Definition at line 288 of file BLI_memiter.c.

References BLI_assert, BLI_memiter_chunk::data, BLI_memiter_handle::elem, BLI_memiter_chunk::next, NULL, and BLI_memiter_elem::size.

Referenced by BLI_memiter_iter_step(), and BLI_memiter_iter_step_size().

◆ memiter_free_data()

static void memiter_free_data ( BLI_memiter * mi )

static

Definition at line 206 of file BLI_memiter.c.

References BLI_asan_unpoison, BLI_memiter::head, MEM_allocN_len, MEM_freeN(), and BLI_memiter_chunk::next.

Referenced by BLI_memiter_clear(), and BLI_memiter_destroy().

◆ memiter_init()

static void memiter_init ( BLI_memiter * mi )

static

Definition at line 100 of file BLI_memiter.c.

References BLI_memiter::count, BLI_memiter::data_curr, BLI_memiter::data_last, BLI_memiter::head, NULL, and BLI_memiter::tail.

Referenced by BLI_memiter_clear(), and BLI_memiter_create().

◆ memiter_set_rewind_offset()

static void memiter_set_rewind_offset ( BLI_memiter * mi )

static

Definition at line 90 of file BLI_memiter.c.

References BLI_asan_unpoison, BLI_assert, BLI_memiter::data_curr, BLI_memiter_elem::size, and BLI_memiter::tail.

Referenced by BLI_memiter_alloc().