Singly Linked Lists¶

To use the singly linked list implementation, create an instance of the single_list type using sl_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.

/* single_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/single_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;

	single_list my_list;

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

	my_list = sl_create(&props);

	/* Push the numbers onto the stack. */
	for(int i = 1; i < argc; i++) {
		inputs[i] = atoi(argv[i]);
		sl_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] = sl_pop_head(my_list);
		printf("%d ", *outputs[i]);
	}

	putchar('\n');

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

Creation and Destruction¶

single_list sl_create(const struct ds_properties *props)¶

Allocate and initialize a new singly linked list.

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

Parameters

props: The data structure properties

Return: Upon successful completion, sl_alloc() shall return 0. Otherwise, -1 shall be returned and errno set to indicate the error.

void sl_destroy(single_list *list)¶

Destroy and deallocate a singly linked list.

De-allocates the singly 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 single_list instance.

Data Management¶

bool sl_empty(const single_list list)¶

Determine if a list is empty.

Return

true if list is empty, false otherwise.

Parameters

list: The list to check

void sl_push_head(single_list list, const 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 sl_push_tail(single_list list, const 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 *sl_pop_head(single_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 *sl_pop_tail(single_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 sl_elem(const single_list list, const 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 sl_insert(single_list list, const void *data, const 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..list->length)

Return: true if the insertion succeeds, otherwise false.

bool sl_delete(single_list list, const 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..list->length - 1)

Return: true if the deletion succeeds, otherwise false.

void *sl_remove(single_list list, const 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..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 *sl_fetch(single_list list, const 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..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 sl_destroy() is called, so if the data is needed after the list is destroyed, make a copy of it, or make sure to call sl_remove() on the data’s index before destroying the list.

Higher Order Functions¶

void sl_map(single_list list, const 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 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 *sl_foldr(const single_list list, const foldr_fn fn, const void *init)¶

Right associative fold for singly 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 *sl_foldl(const single_list list, const foldl_fn fn, const void *init)¶

Left associative fold for singly 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 sl_any(single_list list, const pred_fn pred)¶

Determine if any value in a list satisifies some condition.

Iterate over each value stored in list, and determine if any of them satisfies pred.

Parameters

list: A list of values
pred: The predicate function

Return: This function shall return true if the predicate pred is satisfied by any data element in list; otherwise false shall be returned.

bool sl_all(single_list list, const pred_fn pred)¶

Determines if all values in a list satisify some condition.

Iterate over each value stored in list, and determine if all of them satisfy pred.

Parameters

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

Return: This function shall return true if the predicate pred is satisfied by all data elements in list; otherwise false shall be returned.

bool sl_filter(single_list list, const pred_fn pred)¶

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

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

Parameters

list: The list to filter
pred: The predicate

bool sl_drop_while(single_list list, const pred_fn pred)¶

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

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

Parameters

list: The list to drop from
pred: The predicate

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

bool sl_take_while(single_list list, const pred_fn pred)¶

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 pred. Once an element that does not satisfy the predicate pred is reached, drop the rest of the list, including that element.

Parameters

list: The list to take from
pred: The predicate

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

Debugging¶

void sl_dump(const single_list list)¶