Immutable C lists experiment

im-pair.c

#include "im-pair.h"
#include <stdio.h>
#include <stdlib.h>

bool imPairHeap_defaultOnEmpty(imPairHeap* heap)
{
	fprintf(stderr, "heap 0x%p empty", heap);
	exit(1);
}


void imPairHeap_init(imPairHeap* heap, imPairHeapHandler onEmpty, void* nodes, size_t nodeSize, size_t nodeNum)
{
	const imPair* prev = NULL;
	heap->size = nodeNum;
	while(nodeNum-- > 0)
	{
		imPair* node = (imPair*)nodes;
		node->x = prev;
		node->y = NULL;
		prev = node;
		nodes += nodeSize;
	}
	heap->failed = false;
	heap->onEmpty = onEmpty == NULL? imPairHeap_defaultOnEmpty : onEmpty;
	heap->free = prev;
}

/** Take a single node from the heap
 *
 * @returns a new node, or NULL on failure.
 */
imPair* imPairHeap_take(imPairHeap* heap, const void* x, const void* y)
{
	if (heap->failed)
		return NULL;
	
	if (heap->free == NULL && !heap->onEmpty(heap))
	{
		heap->failed = true;
		return NULL; /* failed */
	}
	
	imPair* node = (imPair*)heap->free;
	heap->free = node->x;
	heap->size -= 1;
	node->x = x;
	node->y = y;
	return node;
}

/** Copy a single node using the heap 
 *
 * @returns a new node, or NULL on heap failure.
 */
const imPair* imPairHeap_copy(imPairHeap* heap, const imPair* node)
{
	return imPairHeap_take(heap, node->x, node->y);
}

/** Return a single imPair node to the heap */
void imPair_give(imPair* node, imPairHeap* heap)
{
	if (heap->failed)
		return;
	
	node->x = heap->free;
	node->y = NULL;
	heap->free = node;
	heap->size += 1;
}

/** Return an xlist portion to the heap.
 *
 * Implicitly mutating!  As such, sets *fromp to NULL.
 *
 * @param fromp    reference to the first node to return, or NULL.
 * @param to      the first node not to return, or NULL.
 * @returns NULL, for convenience.
 */
void* xlist_give(const imPair** fromp, const imPair* to, imPairHeap* heap)
{
	if (fromp == NULL || *fromp == NULL)
		return NULL;
	
	/* nullify all the y fields of the list */
	imPair* node = (imPair*)*fromp;
	while(node->x != to)
	{
		node->y = NULL;
		node = (imPair*)node->x;
		heap->size += 1;
	}

	/* prepend the list to the free list */
	node->x = heap->free;
	heap->free = *fromp;
	*fromp = NULL; /* To make reuse impossible without an error */
	
	return NULL;
}

size_t xlist_size(const imPair* list)
{
	size_t size = 0;
	while(list != NULL)
	{
		size += 1;
		list = list->x;
	}
	return size;
}

const imPair* xlist_last(const imPair* list)
{
	while(list->x != NULL)
		list = list->x;
	return list;
}

/** Make a reversed copy of an xlist
 *
 * @param prev   An optional xlist to append the new list nodes to, or NULL 
 * @returns a new node, or NULL on heap failure.
 */
const imPair* xlist_rcopy(const imPair* list, const imPair* prev, imPairHeap* heap)
{
	const imPair const* origPrev = prev;
	while(list != NULL)
	{
		prev = imPairHeap_take(heap, prev, list->y);
		if (heap->failed)
			/* Oops! */
			return xlist_give(&prev, origPrev, heap);
		list = list->x;
	}
	return (const imPair*)prev;
}


/** Reverses a list in-place
 *
 * Traverses the list, altering each node to point to the previous node as next.
 *
 * @param list  the list to reverse
 * @param prev  an optional xlist to append the new list nodes to, or NULL
 * @returns     The reversed list.
 */
const imPair* xlist_mutating_reverse(imPair* list, const imPair* prev)
{
	while(list != NULL)
	{
		imPair* next = (imPair*)list->x;
		list->x = prev;
		prev = list;
		list = next;
	}
	return prev;
}



/** Make a copy of an xlist
 *
 * @returns a new node, or NULL on heap failure.
 */
const imPair* xlist_copy(const imPair* list, const imPair* prev, imPairHeap* heap)
{
	/* Sneakily mutating a private list before returning it */
	return xlist_mutating_reverse((imPair*)xlist_rcopy(list, NULL, heap), prev);
}

/** Find the Nth item in a list satisfying a condition 
 */
const imPair* xlist_findNth(const imPair* list, size_t n, imPairPredicate condition, const void* params)
{
	if (n == 0)
		return NULL;
	
	while(list != NULL && n > 0)
	{
		if (condition(list, params))
			n -= 1;

		list = list->x;
	} 

	return list;
}

/** Find the Nth-from-last item in a list satisfying a condition 
 *
 * Traverses the list, storing up to the last N items.
 *
 * @returns the Nth last, or NULL if fewer were found.
 */
const imPair* xlist_findNthLast(const imPair* list, size_t n, imPairPredicate condition, const void* params)
{
	if (n == 0)
		return NULL;
	const imPair* cache[n];

	size_t count = 0;
	while(list != NULL)
	{
		if (condition(list, params))
			cache[count++ % n] = list;

		list = list->x;
	} 

	return cache[count % n];
}

/** Maps a list into a new one
 *
 * Each node in the list is copied with a new x supplied by map(node->x, params).
 *
 * @returns the new list, or NULL on heap failure.
 */
const imPair* xlist_mapx(const imPair* list, Mapper map, const void* params, imPairHeap* heap)
{
	imPair head = {0};
	imPair* tail = &head;
	while(list != NULL)
	{
		tail->x = imPairHeap_take(heap, map(list->x, params), NULL);
		if (heap->failed)
			return xlist_give((const imPair**)&head.x, NULL, heap);
			
		tail = (imPair*)tail->x;
		list = list->x;
	}

	return (const imPair*)head.x;
}

/** Filters a list into a new one
 *
 * Each node in the list is copied if the condition is true.
 *
 * @returns the new list, or NULL on heap failure.
 */
const imPair* xlist_filterx(const imPair* list, imPairPredicate condition, const void* params, imPairHeap* heap)
{
	imPair head = {0};
	imPair* tail = &head;
	while(list != NULL)
	{
		if (condition(list, params))
		{
			tail->x = imPairHeap_take(heap, list->x, NULL);
			if (heap->failed)
				return xlist_give((const imPair**)&head.x, NULL, heap);
			
			tail = (imPair*)tail->x;
		}

		list = list->x;
	}

	return head.x;
}

/** Reduces a list into a new value
 *
 */
const void* xlist_reducex(const imPair* list, Mapper map, const void* params)
{
	while(list != NULL)
	{
		params = map(list->x, params);
		list = list->x;
	}

	return params;
}

// sort
// zip

im-pair.h

#ifndef IM_PAIR_H
#define IM_PAIR_H

/**
 * @file im-pair.h
 *
 * @brief An immutable singly-linked list implementation, loosely Lisp-inspired.
 *
 * @page Overview
 *
 *
 * Inspired by Lisp, and pure functional programming.
 *
 * xlists are lists linked by the x fields.
 * The y fields are treated as payload in this case.
 * ylists could also exist, or association-lists, trees, etc.
 *
 * Intention that generic iterators can be implemented, and thereby
 * generic algorithms.
 * 
 * Possibly I should come up with a better name than imPair.
 *
 * @section Synopisis
 *
 * This example ...
 *
 */

#include <stdbool.h>
#include <stddef.h>

struct imPairHeap;
typedef bool (*imPairHeapHandler)(struct imPairHeap* heap);

typedef bool (*imPairPredicate)(const void* x, const void* y);

typedef const void* (*Mapper)(const void* x, const void* y);

typedef struct imPair
{
	const void* x; /**< a link to another datastructure */
	const void* y; /**< a link to another datastructure */
} imPair;


typedef struct imPairHeap
{
	bool failed; /**< Set to true when onEmpty fails, disables this heap from then on. */
	const imPair* free; /**< A list of free nodes */
	size_t size; /**< A count of free nodes */
	imPairHeapHandler onEmpty; /**< A callback to attempt to secure more free nodes.
								  Should either throw, or return false on failure.*/
} imPairHeap;


#endif

im-pair_test.c

// This uses the Cmocka test/mocking framework. See http://cmocka.org

#define DEBUG(fmt, ...) print_message("   " fmt, ##__VA_ARGS__)

#include "im-pair.c"
#include "iter.c"
#include "ary-iter.h"
#include "ptr-iter.h"
#include <stddef.h>
#include <stdbool.h>
#include <setjmp.h>
#include <stdarg.h>
#include <cmocka.h>
#include <stdio.h>
#include <string.h>

/* Our test fixture and setup function */

#define HEAP_SIZE 100

imPair s_nodes[HEAP_SIZE];

/**
 * Test case: read an iteration formed by a concatenation of
 * sub-iterations, using both with a user-supplied buffer and without
 * (hence mallocing).
 *
 * Also test-drives strIterType and ptrIterType
 */
static void test_imPair(void **state)
{
	(void)state; // ignore this var

	printf("begin\n");
	imPairHeap heap;
	imPairHeap_init(&heap, NULL, s_nodes, sizeof(imPair), HEAP_SIZE);
	assert_int_equal(heap.size, HEAP_SIZE);
	
	const char* name = "foo";
	const imPair* list = NULL;
	for(const char* ch = name; *ch != 0; ch++)
	{
		list = imPairHeap_take(&heap, list, ch);
	}

	const imPair* list2 = xlist_rcopy(list, NULL, &heap);

	assert_int_equal(heap.size, HEAP_SIZE-strlen(name)*2);
	xlist_give(&list, NULL, &heap);
	
	assert_int_equal(heap.size, HEAP_SIZE-strlen(name));
	
	for(const imPair* node = list2; node != NULL; node = node->x)
		printf("node: %c\n", *(const char*)node->y);
	
}



int main(void) {

    const UnitTest tests[] = {
        unit_test(test_imPair),
    };
    return run_tests(tests);
}