shithub: libds

Download patch

ref: cfd7660a044c8bd3ad0c33a237155b05248c0b0b
parent: 4ef01c1a0db8591883c74126cb81684ae4298b48
author: henesy <henesy.dev@gmail.com>
date: Fri Mar 4 00:21:44 EST 2022 

init from stream


--- /dev/null
+++ b/ds.h
@@ -1,0 +1,4 @@
+#pragma src "/usr/glenda/src/ds"
+#pragma lib "libds.a"
+
+extern void* ecalloc(ulong, ulong);
--- /dev/null
+++ b/list.c
@@ -1,0 +1,66 @@
+#include <u.h>
+#include <libc.h>
+#include "ds.h"
+#include "list.h"
+
+// Return an allocated, empty, list. 
+List*
+mklist(void)
+{
+	List *l = ecalloc(1, sizeof (List));
+	l->size = 0;
+	return l;
+}
+
+// Prepend to the front of the list. 
+List*
+listprepend(List *l, void *datum)
+{
+	if(l == nil)
+		// Nil pointer
+		return l;
+
+	ListNode *n = ecalloc(1, sizeof (ListNode));
+
+	if(l->head == nil){
+		// Empty list, be the head
+		l->head = n;
+	}else{
+		// Replace head
+		n->next = l->head;
+		l->head = n;
+	}
+
+	l->head->datum = datum;
+	l->size++;
+
+	return l;
+}
+
+// Append to the end of the list. 
+List*
+listappend(List *l, void *datum)
+{
+	if(l == nil)
+		// Nil pointer
+		return l;
+
+	ListNode *n = ecalloc(1, sizeof (ListNode));
+
+	if(l->head == nil){
+		// Empty list, be the head
+		l->head = n;
+	}else{
+		// Replace tail
+		ListNode *ln;
+		for(ln = l->head; ln->next != nil; ln = ln->next)
+			;
+		ln->next = n;
+		n->next = nil;
+	}
+
+	n->datum = datum;
+	l->size++;
+
+	return l;
+}
--- /dev/null
+++ b/list.h
@@ -1,0 +1,28 @@
+// Defines a node in a list
+typedef struct ListNode ListNode;
+struct ListNode {
+	void *datum;			// Data stored in node
+	ListNode *next;			// Next node in the list
+
+	// Doubly-linked things
+	union {
+		ListNode *prev;		// Previous node in the list
+		char empty;			// Stub for space savings in single
+	};
+};
+
+// Defines a list from the head;
+typedef struct List List;
+struct List {
+	ListNode	*head;
+	usize		size;
+};
+
+// Return an allocated, empty, list. 
+List*	mklist(void);
+
+// Prepend to the front of the list. 
+List*	listprepend(List*, void*);
+
+// Append to the end of the list. 
+List*	listappend(List*, void*);
--- /dev/null
+++ b/mkfile
@@ -1,0 +1,22 @@
+</$objtype/mkfile
+
+LIBDIR = 
+LIB = /$objtype/lib/libds.a
+
+OFILES=\
+	util.$O \
+	list.$O \
+
+HFILES=/sys/include/ds.h
+
+UPDATE=\
+	mkfile\
+	$HFILES\
+	${OFILES:%.$O=%.c}\
+	${LIB:/$objtype/%=/386/%}\
+
+</sys/src/cmd/mksyslib
+
+test:V: all
+	cd tests
+	mk test
--- /dev/null
+++ b/tests/main.c
@@ -1,0 +1,120 @@
+#include <u.h>
+#include <libc.h>
+#include "../ds.h"
+#include "../list.h"
+
+usize passed = 0;
+usize failed = 0;
+
+// Print whether a given test passes or fails. 
+void
+tfail(char *t, int tf, char *msg)
+{
+	if(tf){
+		passed++;
+		fprint(2, "pass: %s\n", t);
+	}else{
+		failed++;
+		fprint(2, "fail: %s failed → %s\n", t, msg);
+	}
+	free(msg);
+}
+
+// End testing if a given test does not pass. 
+void
+tfatal(char *t, int tf, char *msg)
+{
+	if(tf){
+		passed++;
+		fprint(2, "pass: %s\n", t);
+		free(msg);
+	}else{
+		failed++;
+		sysfatal("fail: %s hard failed → %s", t, msg);
+	}
+}
+
+// Test whether we can create a list. 
+void
+testmklist(void)
+{
+	char *t = "mklist";
+	List *l = mklist();
+	tfatal(t, l != nil, smprint("list allocation failed"));
+	free(l);
+}
+
+void
+testprependlist(void)
+{
+	char *t = "prependlist";
+	List *l = mklist();
+	int i;
+	int n = 7;
+	for(i = 0; i < n; i++){
+		int v = i*i;
+		listprepend(l, &v);
+	}
+	
+	tfail(t, l->size == n, 
+	smprint("size → expected %d, got %ld", n, l->size)
+	);
+
+	ListNode *ln;
+	usize count = 0;
+	for(ln = l->head; ln != nil; ln = ln->next)
+		count++;
+
+	tfail(t, l->size == n, 
+	smprint("size → iteration %d, got %ld", n, l->size)
+	);
+
+	// TODO - delete/free contents
+
+	free(l);
+}
+
+void
+testappendlist(void)
+{
+	char *t = "appendlist";
+	List *l = mklist();
+	int i;
+	int n = 7;
+	for(i = 0; i < n; i++){
+		int v = i*i;
+		listappend(l, &v);
+	}
+	
+	tfail(t, l->size == n, 
+	smprint("size → expected %d, got %ld", n, l->size)
+	);
+
+	ListNode *ln;
+	usize count = 0;
+	for(ln = l->head; ln != nil; ln = ln->next)
+		count++;
+
+	tfail(t, l->size == n, 
+	smprint("size → iteration %d, got %ld", n, l->size)
+	);
+
+	// TODO - delete/free contents
+
+	free(l);
+}
+
+void
+main(int, char*[])
+{
+	// Lists
+	testmklist();
+	testprependlist();
+	testappendlist();
+
+	// Final output
+	double percent = (double)((double)passed/(double)(passed+failed))*100.0;
+	print("%ld passed. %ld failed. %3.0f%% passing.\n", passed, failed, percent);
+
+	exits(nil);
+}
--- /dev/null
+++ b/tests/mkfile
@@ -1,0 +1,10 @@
+</$objtype/mkfile
+
+LDFLAGS = ($LDFLAGS '-I../')
+
+OFILES = main.$O\
+
+</sys/src/cmd/mkone
+
+test:V: all
+	$O.out
--- /dev/null
+++ b/util.c
@@ -1,0 +1,13 @@
+#include <u.h>
+#include <libc.h>
+#include "ds.h"
+
+// Guarded calloc(2)
+void*
+ecalloc(ulong n, ulong size)
+{
+	void *m = calloc(n, size);
+	if(m == nil)
+		sysfatal("err: calloc failed → %r");
+	return m;
+}