From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sat, 9 Apr 2022 09:43:53 +0200
Subject: neue Verzeichnisstruktur

---
 src/list.c | 264 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 264 insertions(+)
 create mode 100644 src/list.c

(limited to 'src/list.c')

diff --git a/src/list.c b/src/list.c
new file mode 100644
index 0000000..d18dae4
--- /dev/null
+++ b/src/list.c
@@ -0,0 +1,264 @@
+/* simple Implementation of single linked lists */
+/* written and placed in the public domain by Thomas Schmucker */
+
+/* Standard C */
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+/* Project */
+#include "util.h"
+
+/* --8<-- list_type */
+typedef int T;
+
+struct list_item {
+	struct list_item *next;
+	T                 data;
+};
+/* -->8-- */
+
+/* --8<-- list_add */
+struct list_item *
+list_add(struct list_item *next, T data)
+{
+	struct list_item *new_item;
+
+	new_item = malloc(sizeof *new_item);
+	if ( new_item ) {
+		new_item->data = data;
+		new_item->next = next;
+	}
+	else {
+		ERROR("out of memory");
+	}
+
+	return new_item;
+}
+/* -->8-- */
+
+/* --8<-- list_insert_next */
+void
+list_insert_next(struct list_item *list, T data)
+{
+	struct list_item *new_item;
+
+	new_item = list_add(list->next, data);
+	if ( new_item ) {
+		list->next = new_item;
+	}
+	else {
+		ERROR("out of memory");
+	}
+}
+/* -->8-- */
+
+/* --8<-- list_delete */
+struct list_item *
+list_delete(struct list_item *list, T data)
+{
+	struct list_item *prev = NULL;
+
+	for ( struct list_item *p = list; p; p = p->next ) {
+		if ( p->data == data ) {
+			if ( prev == NULL ) { /* first element in list? */
+				list = p->next;
+			}
+			else {
+				prev->next = p->next;
+			}
+
+			free(p);
+
+			return list;
+		}
+		prev = p;
+	}
+#ifdef LIST_REPORT_ERROR
+	ERROR("data not found");
+#endif
+	return list;
+}
+/* -->8-- */
+
+/* --8<-- list_delete_next */
+void
+list_delete_next(struct list_item *list)
+{
+	if ( list->next ) {
+		struct list_item *temp = list->next;
+
+		list->next = list->next->next;
+
+		free(temp);
+	}
+}
+/* -->8-- */
+
+/* --8<-- list_length */
+size_t
+list_length(struct list_item *list)
+{
+	size_t len = 0;
+
+	for ( ; list; list = list->next ) {
+		++len;
+	}
+
+	return len;
+}
+/* -->8-- */
+
+/* --8<-- list_copy */
+struct list_item *
+list_copy(struct list_item *list)
+{
+	struct list_item *head = NULL, **p = &head;
+
+	for ( ; list; list = list->next ) {
+		*p = malloc(sizeof **p);
+		if ( *p ) {
+			(*p)->data = list->data; // copy elements
+			p          = &(*p)->next;
+		}
+		else {
+			ERROR("out of memory");
+		}
+	}
+	*p = NULL;
+	return head;
+}
+/* -->8-- */
+
+/* --8<-- list_reverse */
+struct list_item *
+list_reverse(struct list_item *list)
+{
+	struct list_item *head = NULL, *next;
+
+	for ( ; list; list = next ) {
+		next       = list->next;
+		list->next = head;
+		head       = list;
+	}
+	return head;
+}
+/* -->8-- */
+
+/* --8<-- list_apply */
+void
+list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl)
+{
+	for ( ; list; list = list->next ) {
+		visit(list->data, cl);
+	}
+}
+/* -->8-- */
+
+/* --8<-- list_merge */
+struct list_item *
+list_merge(struct list_item *a, struct list_item *b)
+{
+	struct list_item  dummy = { .next = NULL };
+	struct list_item *head = &dummy, *c = head;
+
+	while ( a && b )
+		if ( a->data < b->data ) {
+			c->next = a, c = a, a = a->next;
+		}
+		else {
+			c->next = b, c = b, b = b->next;
+		}
+
+	c->next = a ? a : b;
+
+	return head->next;
+}
+/* -->8-- */
+
+/* --8<-- list_sort */
+struct list_item *
+list_sort(struct list_item *c)
+{
+	if ( c == NULL || c->next == NULL )
+		return c;
+
+	struct list_item *a = c,
+	                 *b = c->next;
+
+	while ( b && b->next ) {
+		c = c->next, b = b->next->next;
+	}
+
+	b = c->next, c->next = NULL;
+
+	return list_merge(list_sort(a), list_sort(b));
+}
+/* -->8-- */
+
+/* --8<-- list_free */
+void
+list_free(struct list_item *list)
+{
+	struct list_item *next;
+
+	for ( ; list; list = next ) {
+		next = list->next;
+		free(list);
+	}
+}
+/* -->8-- */
+
+/* --8<-- list_apply_sample */
+static void
+print_data(T data, void *cl)
+{
+	fprintf(cl, "%d\n", data);
+}
+/* -->8-- */
+
+int
+main()
+{
+	clock_t start;
+
+	/*
+	struct list_item *mylist = NULL;
+
+	mylist = list_add(mylist, 42);
+	mylist = list_add(mylist, 43);
+	mylist = list_add(mylist, 44);
+
+	mylist = list_delete(mylist, 45);
+
+	list_apply(mylist, print_data, stdout);
+
+	struct list_item *mylist2 = list_reverse(list_copy(mylist));
+
+	list_free(mylist);
+	list_apply(mylist2, print_data);
+	list_free(mylist2);
+	*/
+
+	srand(time(NULL));
+
+	static const int COUNT = 10000000;
+
+	struct list_item *x = NULL;
+	for ( int i = 0; i != COUNT; ++i ) {
+		int r = rand();
+		x     = list_add(x, r);
+	}
+
+	puts("start");
+	start = clock();
+	x     = list_sort(x);
+	printf("Fertig: %.3lf sec\n", (double) (clock() - start) / CLOCKS_PER_SEC);
+
+	//list_apply(x, print_data);
+	printf("Len: %zu\n", list_length(x));
+
+	list_free(x);
+
+	return EXIT_SUCCESS;
+}
-- 
cgit v1.3