Doubly Linked Lists¶

To use the doubly linked list implementation, create an instance of the double_list type using dl_create(). You can then use the data management functions to add and remove elements from the list. You can also use the functional data operations to transform, reduce, or filter the data in the list.

/* double_list.h - Reverse and take the absolute value of a list of numbers
 *                 using a doubly linked list as a stack.
 * Copyright (C) 2018 Quytelda Kahja
 *
 * This file is part of focs.
 *
 * focs is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * focs is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with focs.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdio.h>
#include <stdlib.h>
#include <list/double_list.h>
#include <focs/generics/hof.h>

static const struct ds_properties props = {
	.data_size = sizeof(int),
};

static int my_abs(int n)
{
	if(n < 0)
		n = (-n);

	return n;
}
WRAP_MAPPABLE(my_abs, int, my_abs_mappable);

int main(int argc, char * argv[])
{
	int *  inputs;
	int ** outputs;

	double_list my_list;

	inputs  = calloc(argc, sizeof(int));
	outputs = calloc(argc, sizeof(int *));
	if(!inputs || !outputs)
		return -1; // out of memory

	my_list = dl_create(&props);

	/* Push the numbers onto the stack. */
	for(int i = 1; i < argc; i++) {
		inputs[i] = atoi(argv[i]);
		dl_push_head(my_list, &inputs[i]);
	}

	/* Transform the list by mapping my_abs over the list. */
	map(my_list, my_abs_mappable);

	/* Output each number popped from the stack. */
	for(int i = 1; i < argc; i++) {
		outputs[i] = dl_pop_head(my_list);
		printf("%d ", *outputs[i]);
	}

	putchar('\n');

	free(inputs);
	free(outputs);
	dl_destroy(&my_list);
	return 0;
}

Creation and Destruction¶

double_list dl_create(const struct ds_properties *props)¶

Allocate and initialize a new doubly linked list.

Allocates a new doubly linked list at the structure pointer pointed to by list.

Parameters

props: The data structure properties

Return: Upon successful completion, dl_create() shall return a new double_list. Otherwise, NULL shall be returned and errno set to indicate the error.

void dl_destroy(double_list *list)¶

Destroy and deallocate a doubly linked list.

De-allocates the doubly linked list at the structure pointer pointed to by list, as well as de-allocating all data elements contained within list.

Parameters

list: A pointer to a struct double_list pointer.

Data Management¶

bool dl_empty(const double_list list)¶

Determine if a list is empty.

Return

true if list is empty, false otherwise.

Parameters

list: The list to check

size_t dl_size(const double_list list)¶

Determine the number of data elements stored in a doubly linked list.

Return

This function shall return the number of data elements stored in list.

Parameters

list: The list to check (non-NULL)

void dl_push_head(double_list list, void *data)¶

Push a new data element to the head of the list.

Push a newly allocated copy of data onto the head of list.

Parameters

list: The list to push onto
data: A pointer to the data to push

void dl_push_tail(double_list list, void *data)¶

Push a new data element to the tail of the list.

Push a newly allocated copy of data onto the tail of list.

Parameters

list: The list to push onto
data: A pointer to the data to push

void *dl_pop_head(double_list list)¶

Pop a data element from the head of a list.

Remove and return the data element at the head of list. After this operation the returned data element will no longer be stored in list.

Parameters

list: The list to pop from

Return: A pointer to the data element at the head of list. This pointer must be explicitly freed with free() when it is no longer needed. It is not equivalent to the pointer which was used to insert the data into list.

void *dl_pop_tail(double_list list)¶

Pop a data element from the tail of a list.

Remove and return the data element at the tail of list. After this operation the returned data element will no longer be stored in list.

Parameters

list: The list to pop from

Return: A pointer to the data element at the tail of list. This pointer must be explicitly freed with free() when it is no longer needed. It is not equivalent to the pointer which was used to insert the data into list.

bool dl_elem(double_list list, void *data)¶

Determine if a list contains a value.

Determines if list contains an entry matching data. The operation compares the contents of the memory pointed to by data, and not the memory addresses of the data pointers.

Parameters

list: The list to search
data: The data to search for in the list

Return: true if a matching entry is found, otherwise false

bool dl_insert(double_list list, void *data, size_t pos)¶

Insert a new data element to a given position in a list.

Insert a newly allocated copy of data into list at the index indicated by pos.

Parameters

list: The list to inesrt into
data: A pointer to the data to insert
pos: The position to insert the element at (must be an index in the range 0..DS_PRIV(list)->length)

Return: true if the insertion succeeds, otherwise false.

bool dl_delete(double_list list, size_t pos)¶

Delete a data element from a given position in a list.

Delete the copy of data stored in list at the index indicated by pos.

Parameters

list: The list to delete from
pos: The position to delete the element at (must be an index in the range 0..DS_PRIV(list)->length - 1)

Return: true if the deletion succeeds, otherwise false.

void *dl_remove(double_list list, size_t pos)¶

Delete and return a data element from a given position in a list.

Delete the reference to data stored in list at the index indicated by pos.

Parameters

list: The list to delete from
pos: The position to delete the element at (must be an index in the range 0..DS_PRIV(list)->length - 1)

Return: A pointer to the data removed from list, or NULL on failure. This pointer must be explicitly freed with free() when it is no longer needed. It is not equivalent to the pointer which was used to insert the data into list.

void *dl_fetch(double_list list, size_t pos)¶

Fetch a data element from a given position in a list.

Fetch the data stored at index pos in list.

Parameters

list: The list to fetch from
pos: The index to fetch the element from (must be an index in the range 0..DS_PRIV(list)->length - 1)

Return: A pointer to the data at index pos, or NULL on failure. This pointer should not be free()d explicitly, or the list will become corrupted. This pointer will be free()d when dl_destroy() is called, so if the data is needed after the list is destroyed, make a copy of it, or make sure to call dl_remove() on the data’s index before destroying the list.

Higher Order Functions¶

void dl_map(double_list list, map_fn fn)¶

Map a function over a linked list in-place.

A map operation iterates over list and transforms each data element using the function fn, replacing the old value with the result of the transformation. In pseudo-code:

for i from 0 to DS_PRIV(list)->length:
    list[i] = fn(list[i])

Parameters

list: A list of values
fn: A function that will transform each value in the list

void *dl_foldr(const double_list list, foldr_fn fn, const void *init)¶

Right associative fold for doubly linked lists.

A right associative fold uses the binary function fn to sequentially reduce a list of values to a single value, starting from some initial value init:

fn(init, fn(list[0], fn(list[1], ...)))

Parameters

list: A list of values to reduce
fn: A binary function that will sequentially reduce values
init: An initial value for the fold

Return: The result of a right associate fold over list. If list is empty, the fold will be equal to the value of init.

void *dl_foldl(const double_list list, foldl_fn fn, const void *init)¶

Left associative fold for doubly linked lists.

A left associative fold uses the binary function fn to sequentially reduce a list of values to a single value, starting from some initial value init:

fn(fn(fn(..., init), list[0]), list[1])

Parameters

list: A list of values to reduce
fn: A binary function that will sequentially reduce values
init: An initial value for the fold

Return: The result of a left associate fold over list. If list is empty, the fold will be equal to the value of init.

bool dl_any(double_list list, pred_fn p)¶

Determine if any value in a list satisifies some condition.

Iterate over each value stored in list, and determine if any of them satisfies p (e.g. p returns true when passed that value).

Parameters

list: A list of values
p: The predicate function (representing a condition to be satisfied).

Return: true if there is at least one value that satisfies the predicate. Otherwise, it returns false.

bool dl_all(double_list list, pred_fn p)¶

Determines if all values in a list satisify some condition.

Iterate over each value stored in list, and determine if all of them satisfy p (e.g. p returns true when passed that value).

Parameters

list: A list of values
p: The predicate function (representing a condition to be satisfied).

Return: false if there is at least one value that does not satisfy the predicate. Otherwise, it returns true.

bool dl_filter(double_list list, pred_fn p)¶

Filter a list to contain only values that satisfy some predicate.

Filter list in-place by removing elements that do not satisfy the predicate p. Elements that do satisfy the predicate p are not removed from the list.

Parameters

list: The list to filter
p: The predicate

bool dl_drop_while(double_list list, pred_fn p)¶

Drop elements from the head of the list until the predicate is unsatisfied.

Drop each element that satisfies the predicate p, starting at the beginning of list and continuing until reaching the first element that does not satisfy the predicate p.

This function is an in-place equivalent of Haskell’s dropWhile.

bool dl_take_while(double_list list, pred_fn p)¶

Keep elements from the head of the list until the predicate is unsatisfied.

Iterate over each element of list, starting at the beginning, that satisfies the predicate p. Once an element that does not satisfy the predicate p is reached, drop the rest of the list, including that element.

This function is an in-place equivalent of Haskell’s takeWhile.

Debugging¶

void dl_dump(const double_list list)¶

Dump the contents of a ring_buffer to standard output.

Prints the contents of list in nice format, including information on addresses, data, and the locations of the head and tail pointers.

Parameters

list: The list to display.