xlib_playground

commit 8695f15c06360bb9d2562ea596570c3884da4341
parent f22c0e4a778cec855691d29c2498d5d8b8f2a58f
Author: Matsuda Kenji <info@mtkn.jp>
Date:   Mon,  9 Jan 2023 15:18:14 +0900

add list files

Diffstat:
A
ex9/list.c
 | 
107
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
ex9/list.h
 | 
10
++++++++++

2 files changed, 117 insertions(+), 0 deletions(-)
diff --git a/ex9/list.c b/ex9/list.c
@@ -0,0 +1,107 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "list.h"
+
+
+static void __lqsort(struct List *lp, struct List *tail,
+	int (* cmp)(void *, void *));
+static void __lprint(struct List *lp, struct List *tail, void (* pfnc)(void *));
+
+struct List *
+addfront(struct List *lp, void *item)
+{
+	struct List *newlp;
+	if((newlp = (struct List *)malloc(sizeof(struct List))) == NULL)
+		return NULL;
+	newlp->item = item;
+	newlp->next = lp;
+	return newlp;
+}
+
+void
+lprint(struct List *lp, void (* pfnc)(void *))
+{
+	for (;lp != NULL; lp = lp->next) {
+		(*pfnc)(lp->item);
+		printf("%s", lp->next == NULL ? "\n" : "->");
+	}
+}
+
+void
+__lprint(struct List *lp, struct List *tail, void (* pfnc)(void *))
+{
+	if (lp == NULL) {
+		printf("\n");
+	}
+	for (;lp != tail; lp = lp->next) {
+		(*pfnc)(lp->item);
+		printf("%s", lp->next == tail ? "\n" : "->");
+	}
+}
+
+/*
+ * Bubble sort
+ */
+void
+lbsort(struct List *p, int (* cmp)(void *, void *))
+{
+	struct List *q;
+
+	for (;p != NULL && p->next != NULL; p = p->next) {
+		for (q = p->next; q != NULL; q = q->next) {
+			if (cmp(p->item, q->item) > 0) {
+				lswap(p, q);
+			}
+		}
+	}
+}
+
+/*
+ * Quick sort
+ * Tail is the next of the last item in List *p.
+ * Tail can be NULL;
+ */
+void
+lqsort(struct List *p, int (* cmp)(void *, void *))
+{
+	__lqsort(p, NULL, cmp);
+}
+
+static void
+__lqsort(struct List *lp, struct List *tail, int (* cmp)(void *, void *))
+{
+	if (lp == tail || lp->next == tail)
+		return;
+
+	struct List *pivot, *q, *last;
+	int i;
+
+	/* select the pivot randomly */
+	for (i = 0, q = lp; q != tail; q = q->next) {
+		if (rand() % ++i == 0)
+			pivot = q;
+	}
+
+	lswap(lp, pivot);
+	last = lp;
+	for (q = lp->next; q != tail; q = q->next) {
+		if (cmp(lp->item, q->item) > 0) {
+			last = last->next;
+			lswap(last, q);
+		}
+	}
+	lswap(lp, last);
+
+	__lqsort(last->next, tail, cmp);
+	__lqsort(lp, last, cmp);
+}
+
+void
+lswap(struct List *p, struct List *q)
+{
+	void *tmp;
+	tmp = p->item;
+	p->item = q->item;
+	q->item = tmp;
+}
diff --git a/ex9/list.h b/ex9/list.h
@@ -0,0 +1,10 @@
+struct List * addfront(struct List *lp, void *item);
+void lprint(struct List *lp, void (* pfnc)(void *));
+void lbsort(struct List *p, int (* cmp)(void *, void *));
+void lqsort(struct List *p, int (* cmp)(void *, void *));
+void lswap(struct List *p, struct List *q);
+
+struct List {
+	struct List *next;
+	void *item;
+};