Shizuka Kamishima avatar Shizuka Kamishima committed 5089db9 Draft

liblcthw - double linked list

Comments (0)

Files changed (5)

liblcthw/makefile

 CFLAGS=-g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG $(OPTFLAGS)
+
 LIBS=-ldl $(OPTLIBS)
+
 PREFIX?=/usr/local
 
+
+
 SOURCES=$(wildcard src/**/*.c src/*.c)
+
 OBJECTS=$(patsubst %.c,%.o,$(SOURCES))
 
+
+
 TEST_SRC=$(wildcard tests/*_tests.c)
+
 TESTS=$(patsubst %.c,%,$(TEST_SRC))
 
+
+
+PROGRAMS_SRC=$(wildcard bin/*.c)
+
+PROGRAMS=$(patsubst %.c,%,$(PROGRAMS_SRC))
+
+
+
 TARGET=build/liblcthw.a
+
 SO_TARGET=$(patsubst %.a,%.so,$(TARGET))
 
+
+
 # The Target Build
-all: $(TARGET) $(SO_TARGET) tests
+
+all: $(TARGET) $(SO_TARGET) tests $(PROGRAMS)
+
+
 
 dev: CFLAGS=-g -Wall -Isrc -Wall -Wextra $(OPTFLAGS)
+
 dev: all
 
+
+
 $(TARGET): CFLAGS += -fPIC
+
 $(TARGET): build $(OBJECTS)
+
 	ar rcs $@ $(OBJECTS)
+
 	ranlib $@
 
+
+
 $(SO_TARGET): $(TARGET) $(OBJECTS)
+
 	$(CC) -shared -o $@ $(OBJECTS)
 
+
+
 build:
+
 	@mkdir -p build
+
 	@mkdir -p bin
 
+
+
 # The Unit Tests
+
 .PHONY: tests
-tests: CFLAGS += $(TARGET)
+
 tests: $(TESTS)
+
 	sh ./tests/runtests.sh
 
+
+
+$(TESTS): $(TARGET)
+
+	$(CC) $(CFLAGS) $@.c $< -o $@
+
+
+
 valgrind:
+
 	VALGRIND="valgrind --log-file=/tmp/valgrind-%p.log" $(MAKE)
 
+
+
 # The Cleaner
+
 clean:
-	rm -rf build $(OBJECTS) $(TESTS)
-	rm -f tests/tests.log
+
+	rm -rf build $(OBJECTS) $(TESTS) $(PROGRAMS)
+
+	rm -f tests/tests.log 
+
 	find . -name "*.gc*" -exec rm {} \;
+
 	rm -rf `find . -name "*.dSYM" -print`
 
+
+
 # The Install
+
 install: all
+
 	install -d $(DESTDIR)/$(PREFIX)/lib/
+
 	install $(TARGET) $(DESTDIR)/$(PREFIX)/lib/
 
+
+
 # The Checker
-BADFUNCS='[^_.>a-zA-Z0-9](str(n?cpy|n?cat|xfrm|n?dup|str|pbrk|tok|_)|stpn?cpy|a?sn?printf|byte_)'
+
+BADFUNCS='[^_.>a-zA-Z0-9](str(n?cpy|n?cat|xfrm|n?dup|str|pbrk|tok|_)|stpn?cpy|a?sn?printf|byte_)' 
+
 check:
+
 	@echo Files with potentially dangerous functions.
+
 	@egrep $(BADFUNCS) $(SOURCES) || true
+
+
+
+$(PROGRAMS): CFLAGS += $(TARGET)

liblcthw/src/lcthw/list.c

+#include <lcthw/list.h>
+#include <lcthw/dbg.h>
+
+List *List_create() {
+    return calloc(1, sizeof(List));
+}
+
+void List_destroy(List *list) {
+    LIST_FOREACH(list, first, next, cur) {
+        if (cur->prev) {
+            free(cur->prev);
+        }
+    }
+
+    free(list->last);
+    free(list);
+}
+
+void List_clear(List *list) {
+    LIST_FOREACH(list, first, next, cur) {
+        free(cur->value);
+    }
+}
+
+void List_clear_destroy(List *list) {
+    List_clear(list);
+    List_destroy(list);
+}
+
+void List_push(List *list, void *value) {
+    ListNode *node = calloc(1, sizeof(ListNode));
+    check_mem(node);
+
+    node->value = value;
+
+    if (list->last == NULL) {
+        list->first = node;
+        list->last = node;
+    } else {
+        list->last->next = node;
+        node->prev = list->last;
+        list->last = node;
+    }
+
+    list->count++;
+
+error:
+    return;
+}
+
+void *List_pop(List *list) {
+    ListNode *node = list->last;
+    return node != NULL ? List_remove(list, node) : NULL;
+}
+
+void List_shift(List *list, void *value) {
+    ListNode *node = calloc(1, sizeof(ListNode));
+    check_mem(node);
+
+    node->value = value;
+
+    if (list->first == NULL) {
+        list->first = node;
+        list->last = node;
+    } else {
+        node->next = list->first;
+        list->first->prev = node;
+        list->first = node;
+    }
+
+    list->count++;
+
+error:
+    return;
+}
+
+void *List_unshift(List *list) {
+    ListNode *node = list->first;
+    return node != NULL ? List_remove(list, node) : NULL;
+}
+
+void *List_remove(List *list, ListNode *node) {
+    void *result = NULL;
+
+    check(list->first && list->last, "List is empty");
+    check(node, "node can't be NULL");
+
+    if (node == list->first && node == list->last) {
+        list->first = NULL;
+        list->last = NULL;
+    } else if (node == list->first) {
+        list->first = node->next;
+        check(list->first != NULL, "Invalid list, somehow got a first that is NULL");
+        list->first->prev = NULL;
+    } else if (node == list->last) {
+        list->last = node->prev;
+        check(list->last != NULL, "Invalid list, somehow got a last that is NULL");
+        list->last->next = NULL;
+    } else {
+        ListNode *after = node->next;
+        ListNode *before = node->prev;
+        after->prev = before;
+        before->next = after;
+    }
+
+    list->count--;
+    result = node->value;
+    free(node);
+
+error:
+    return result;
+}

liblcthw/src/lcthw/list.h

+#ifndef lcthw_List_h
+#define lcthw_List_h
+
+#include <stdlib.h>
+
+struct ListNode;
+
+typedef struct ListNode {
+    struct ListNode *prev;
+    struct ListNode *next;
+    void *value;
+} ListNode;
+
+typedef struct List {
+    int count;
+    ListNode *first;
+    ListNode *last;
+} List;
+
+List *List_create();
+void List_destroy(List *list);
+void List_clear(List *list);
+void List_clear_destroy(List *list);
+
+#define List_count(A) ((A)->count)
+#define List_first(A) ((A)->first != NULL ? (A)->first->value : NULL)
+#define List_last(A) ((A)->last != NULL ? (A)->last->value : NULL)
+
+void List_push(List *list, void *value);
+void *List_pop(List *list);
+
+void List_shift(List *list, void *value);
+void *List_unshift(List *list);
+
+void *List_remove(List *list, ListNode *node);
+
+#define LIST_FOREACH(L, S, M, V) ListNode *_node = NULL; \
+    ListNode *V = NULL; \
+    for(V = _node = L->S; _node != NULL; V = _node = _node->M)
+
+#endif

liblcthw/tests/list_tests.c

+#include "minunit.h"
+#include <lcthw/list.h>
+#include <assert.h>
+
+static List *list = NULL;
+char *test1 = "test1 data";
+char *test2 = "test2 data";
+char *test3 = "test3 data";
+
+char *test_create() {
+    list = List_create();
+    mu_assert(list != NULL, "Failed to create list");
+    return NULL;
+}
+
+char *test_destroy() {
+    List_clear_destroy(list);
+    return NULL;
+}
+
+char *test_push_pop() {
+    List_push(list, test1);
+    mu_assert(List_last(list) == test1, "Wrong last value");
+
+    List_push(list, test2);
+    mu_assert(List_last(list) == test2, "Wrong last value");
+
+    List_push(list, test3);
+    mu_assert(List_last(list) == test3, "Wrong last value");
+    mu_assert(List_count(list) == 3, "Wrong count after push");
+
+    char *val = List_pop(list);
+    mu_assert(val == test3, "Wrong value on pop");
+
+    val = List_pop(list);
+    mu_assert(val == test2, "Wrong value on pop");
+
+    val = List_pop(list);
+    mu_assert(val == test1, "Wrong value on pop");
+    mu_assert(List_count(list) == 0, "Wrong count after pop");
+
+    return NULL;
+}
+
+char *test_shift() {
+    List_shift(list, test1);
+    mu_assert(List_first(list) == test1, "Wrong first value");
+
+    List_shift(list, test2);
+    mu_assert(List_first(list) == test2, "Wrong first value");
+
+    List_shift(list, test3);
+    mu_assert(List_first(list) == test3, "Wrong first value");
+    mu_assert(List_count(list) == 3, "Wrong count on shift");
+
+    return NULL;
+}
+
+char *test_remove() {
+    // we only need to test the middle remove case
+    // push/shift tests the first and last case
+
+    char *val = List_remove(list, list->first->next);
+    mu_assert(val == test2, "Wrong removed element");
+    mu_assert(List_count(list) == 2, "Wrong count after remove");
+    mu_assert(List_first(list) == test3, "Wrong first after remove");
+    mu_assert(List_last(list) == test1, "Wrong last after remove");
+
+    return NULL;
+}
+
+char *test_unshift() {
+    char *val = List_unshift(list);
+    mu_assert(val == test3, "Wrong value on unshift");
+
+    val = List_unshift(list);
+    mu_assert(val == test1, "Wrong value on unshift");
+    mu_assert(List_count(list) == 0, "Wrong count after unshift");
+
+    return NULL;
+}
+
+char *all_tests() {
+    mu_suite_start();
+
+    mu_run_test(test_create);
+    mu_run_test(test_push_pop);
+    mu_run_test(test_shift);
+    mu_run_test(test_remove);
+    mu_run_test(test_unshift);
+    mu_run_test(test_destroy);
+
+    return NULL;
+}
+
+;
+RUN_TESTS(all_tests);

liblcthw/tests/minunit.h

 #ifndef _minunit_h
 #define _minunit_h
 
-#include <stdio.h>
+#include <stdio.h> 
 #include <lcthw/dbg.h>
 #include <stdlib.h>
 
-#define mu_suite_start() char *message = NULL
-
-#define mu_assert(test, message) if (!(test)) { log_err(message); return message; }
-#define mu_run_test(test) debug("\n-----%s", " " #test); {\
-    message = test(); tests_run++; if (message) return message;
-
-#define RUN_TESTS(name) int main(int argc char *argv[]) {\
-    argc = 1; \
-    debug("----- RUNNING: %s", argv[0]); \
-    printf("----\nRUNNING: %s\n", argv[0]); \
-    char *result = name(); \
-    if (result != 0) { \
-        printf("FAILED: %s\n", result); \
-    } else { \
-        printf("ALL TESTS PASSED\n"); \
-    } \
-    printf("Tests run: %d\n", tests_run); \
-    exit(result != 0); \
-}
+#define mu_suite_start() char *message = NULL 
+ 
+#define mu_assert(test, message) if (!(test)) { log_err(message); return message; } 
+#define mu_run_test(test) debug("\n-----%s", " " #test); message = test(); tests_run++; if (message) return message;
+ 
+#define RUN_TESTS(name) int main(int argc, char *argv[]) { argc = 1; debug("----- RUNNING: %s", argv[0]); printf("----\nRUNNING: %s\n", argv[0]); char *result = name(); if (result != 0) { printf("FAILED: %s\n", result); } else { printf("ALL TESTS PASSED\n"); } printf("Tests run: %d\n", tests_run); exit(result != 0); }
 
 int tests_run;
 
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.