List on array

My own implementation of a lists on C. For best performance implemented using array!

This is the header with API: ft_list_on_arr.h and this is the implementation folder: sources/ft_list_on_arr/

If you are confused and do not understand why I bother with implementing a list on an array, read this or this or this or google something like array vs list, access memory time/test, cpu & cache & paging & tact or etc.

• Structure

typedef struct			s_alst_item
{
	size_t			self;
	size_t			next;
}				t_alst_item;

typedef struct			s_list_on_arr
{
	void *restrict		mem;
	__uint64_t *restrict	free_space_mask;
	void *restrict		items;
	t_alst_item *restrict	list;
	size_t			head;
	size_t			tail;
	size_t			curlen;
	size_t			item_size;
	size_t			max_size;
}				t_alst;

This is a dynamic structure! If the reserved memory is over, reallocation will be made with a 2-fold increase in size!

• # define ALST_SPEC_VALUE __SIZE_MAX__

This is a special value (aka NULL for classic list) to indicate empty value. If curlen = 0 head == tail == ALST_SPEC_VALUE Also tail.next always equal ALST_SPEC_VALUE.

• Function

Definition	Description
void alst_init(t_alst *self, size_t item_size, size_t init_len)	Initializes the alst self. init_len - initial size of alst (number of elements), must be > 0.
void alst_del(t_alst *self)	Free memory and fill self by zero.
void alst_extend(t_alst *self)	Doubles the self
size_t alst_get_space(t_alst *self)	Finds a place for a new item and reserve it.
void *alst(t_alst *self, size_t item)	Returns pointer to the i-th element of a alst (not by order but by mem).
void *alst_head(t_alst *self)	Returns pointer to the first (head) element of a alst
void *alst_tail(t_alst *self)	Returns pointer to the last (tail) element of a alst
t_alst_item *alst_add_head(t_alst *self, void *data)	Adds an element from data to the head of the alst. Extends alst if necessary.
t_alst_item *alst_add_tail(t_alst *self, void *data)	Adds an element from data to the tail of the alst. Extends alst if necessary.
t_alst_item *alst_add_after(t_alst *self, size_t item, void *data)	Adds an element from data to the the alst after particular item. Extends alst if necessary.
void *alst_pop_head(t_alst *self)	Removes and returns pointer to the item at the head of the alst. Save the data from this pointer, otherwise it will be lost.
void *alst_pop_after(t_alst *self, size_t item)	Removes and returns pointer to the item after particular item of the alst. Save the data from this pointer, otherwise it will be lost.
void alst_map(t_alst *self, void (*func)(void *))	Iterates over the entire alst from the beginning, applying the func function to each element.

• Example №1

#include <libft.h>

void	print(void *data)
{
	ft_printf("%d ", *(int *)data);
}

void	test(void)
{
	t_alst	lst[1];

	alst_init(lst, sizeof(int), 2);

	alst_add_head(lst, ft_i(10));
	alst_add_tail(lst, ft_i(20));
	alst_add_tail(lst, ft_i(30));
	alst_add_head(lst, ft_i(40));
	alst_add_after(lst, lst->head ,ft_i(50));
	alst_map(lst, print);

	alst_del(lst);
	return ;
}

int	main(void)
{
	ft_memman_init();
	test();
	ft_printf("\n");
	ft_force_buff();
	ft_memman_clean();
	return (0);
}

Output:

> a.out
40 50 10 20 30

• Example №2

Implementation of the alst_map() function (traversal of the list):

void	alst_map(t_alst *restrict self, void (*func)(void *))
{
	size_t		cur;
	t_alst_item	tmp;

	cur = self->head;
	while (cur != ALST_SPEC_VALUE)
	{
		tmp = self->list[cur];
		func(alst(self, tmp.self));
		cur = tmp.next;
	}
}

GO TO NEXT PAGE --->