Shizuka Kamishima avatar Shizuka Kamishima committed 109ce93 Draft

lcthw - list algos

Comments (0)

Files changed (4)

liblcthw/makefile

 CFLAGS=-g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG $(OPTFLAGS)
-
-LIBS=-ldl $(OPTLIBS)
-
+LIBS=-ldl -lbsd $(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 $(PROGRAMS)
 
-
-
 dev: CFLAGS=-g -Wall -Isrc -Wall -Wextra $(OPTFLAGS)
-
 dev: all
 
-
-
-$(TARGET): CFLAGS += -fPIC
-
+$(TARGET): CFLAGS += -fPIC $(LIBS)
 $(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: $(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) $(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_)' 
-
 check:
-
 	@echo Files with potentially dangerous functions.
-
 	@egrep $(BADFUNCS) $(SOURCES) || true
 
-
-
 $(PROGRAMS): CFLAGS += $(TARGET)

liblcthw/src/lcthw/list_algos.c

+#include <lcthw/list_algos.h>
+#include <lcthw/dbg.h>
+
+inline void ListNode_swap(ListNode *a, ListNode *b) {
+    void *temp = a->value;
+    a->value = b->value;
+    b->value = temp;
+}
+
+int List_bubble_sort(List *list, List_compare cmp) {
+    int sorted = 1;
+
+    if (List_count(list) <= 1) {
+        return 0; // list of size 0/1 is already sorted
+    }
+
+    do {
+        sorted = 1;
+        LIST_FOREACH(list, first, next, cur) {
+            if (cur->next) {
+                if (cmp(cur->value, cur->next->value) > 0) {
+                    ListNode_swap(cur, cur->next);
+                    sorted = 0;
+                }
+            }
+        }
+    } while (!sorted);
+
+    return 0;
+}
+
+inline List *List_merge(List *left, List *right, List_compare cmp) {
+    List *result = List_create();
+    void *val = NULL;
+
+    while (List_count(left) > 0 || List_count(right) > 0) {
+        if (List_count(left) > 0 && List_count(right) > 0) {
+            if (cmp(List_first(left), List_first(right)) <= 0) {
+                val = List_unshift(left);
+            } else {
+                val = List_unshift(right);
+            }
+
+            List_push(result, val);
+        } else if (List_count(left) > 0) {
+            val = List_unshift(left);
+            List_push(result, val);
+        } else if (List_count(right) > 0) {
+            val = List_unshift(right);
+            List_push(result, val);
+        }
+    }
+
+    return result;
+}
+
+List *List_merge_sort(List *list, List_compare cmp) {
+    if (List_count(list) <= 1) {
+        return list; // list of size 0/1 is already sorted
+    }
+
+    List *left = List_create();
+    List *right = List_create();
+    int middle = List_count(list) / 2;
+
+    LIST_FOREACH(list, first, next, cur) {
+        if (middle > 0) {
+            List_push(left, cur->value);
+        } else {
+            List_push(right, cur->value);
+        }
+
+        middle--;
+    }
+
+    List *sort_left = List_merge_sort(left, cmp);
+    List *sort_right = List_merge_sort(right, cmp);
+
+    if(sort_left != left) List_destroy(left);
+    if(sort_right != right) List_destroy(right);
+
+    return List_merge(sort_left, sort_right, cmp);
+}

liblcthw/src/lcthw/list_algos.h

+#ifndef lcthw_List_algos_h
+#define lcthw_List_algos_h
+
+#include <lcthw/list.h>
+
+typedef int (*List_compare)(const void *a, const void *b);
+
+int List_bubble_sort(List *list, List_compare cmp);
+
+List *List_merge_sort(List *list, List_compare cmp);
+
+#endif

liblcthw/tests/list_algos_tests.c

+#include "minunit.h"
+#include <lcthw/list_algos.h>
+#include <assert.h>
+#include <string.h>
+
+char *values[] = {"XXXX", "1234", "abcd", "xjvef", "NDSS"};
+#define NUM_VALUES 5
+
+List *create_words() {
+    int i = 0;
+    List *words = List_create();
+    
+    for (i = 0; i < NUM_VALUES; i++) {
+        List_push(words, values[i]);
+    }
+
+    return words;
+}
+
+int is_sorted(List *words) {
+    LIST_FOREACH(words, first, next, cur) {
+        if (cur->next && strcmp(cur->value, cur->next->value) > 0) {
+            debug("%s %s", (char *)cur->value, (char *)cur->next->value);
+            return 0;
+        }
+    }
+
+    return 1;
+}
+
+char *test_bubble_sort() {
+    List *words = create_words();
+
+    // should work on a list that needs sorting
+    int rc = List_bubble_sort(words, (List_compare)strcmp);
+    mu_assert(rc == 0, "Bubble sort failed");
+    mu_assert(is_sorted(words), "Words are not sorted after bubble sort");
+
+    // should work on an already sorted list
+    rc = List_bubble_sort(words, (List_compare)strcmp);
+    mu_assert(rc == 0, "Bubble sort of sorted list failed");
+    mu_assert(is_sorted(words), "Words are unsorted after bubble sort");
+
+    List_destroy(words);
+
+    // should work on an empty list
+    words = List_create(words);
+    rc = List_bubble_sort(words, (List_compare)strcmp);
+    mu_assert(rc == 0, "Bubble sort failed on empty list");
+    mu_assert(is_sorted(words), "Words should be sorted if list is empty");
+
+    List_destroy(words);
+
+    return NULL;
+}
+
+char *test_merge_sort() {
+    List *words = create_words();
+
+    // should work on a list that needs sorting
+    List *res = List_merge_sort(words, (List_compare)strcmp);
+    mu_assert(is_sorted(res), "Words are not sorted after merge sort");
+
+    List *res2 = List_merge_sort(res, (List_compare)strcmp);
+    mu_assert(is_sorted(res2), "Should still be sorted after merge sort");
+
+    List_destroy(res2);
+    List_destroy(res);
+
+    List_destroy(words);
+    return NULL;
+}
+
+char *all_tests() {
+    mu_suite_start();
+
+    mu_run_test(test_bubble_sort);
+    mu_run_test(test_merge_sort);
+
+    return NULL;
+}
+
+RUN_TESTS(all_tests);
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.