美文网首页
[习题32]双链表（Makefile、完整源码、单元测试）

[习题32]双链表（Makefile、完整源码、单元测试）

作者: AkuRinbu | 来源:发表于2018-12-30 22:24 被阅读32次

    使用教材

    《“笨办法” 学C语言（Learn C The Hard Way）》
    https://www.jianshu.com/p/b0631208a794

    • 完整源码 : liblcthw

    https://github.com/zedshaw/liblcthw

    代码说明

    • Makefile，使用make，自动构建、测试；
    • 双链表，实现：链表创建(List_create)、头部插入(List_unshift)、头部删除(List_shift)、尾部插入(List_push)、尾部删除(List_pop)、元素删除(List_remove)、链表清空(List_clear)、链表销毁(List_destory)等操作；

    命令行操作

    • 查看当前文件结构
    liblcthw$ ls -R
.:
bin  LICENSE  Makefile  README.md  src  tests

./bin:

./src:
lcthw

./src/lcthw:
dbg.h  list.c  list.h

./tests:
list_tests.c  minunit.h  runtests.sh
    • 执行 make 操作
    liblcthw$ make
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  -fPIC   -c -o src/lcthw/list.o src/lcthw/list.c
ar rcs build/liblcthw.a src/lcthw/list.o
ranlib build/liblcthw.a
cc -shared -o build/liblcthw.so src/lcthw/list.o
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG     tests/list_tests.c  -ldl build/liblcthw.a -o tests/list_tests

sh ./tests/runtests.sh
Running unit tests:
----
RUNNING: ./tests/list_tests
ALL TESTS PASSED
Tests run: 6
tests/list_tests PASS
    • 再次查看文件结构
    liblcthw$ ls -R
.:
bin  build  LICENSE  Makefile  README.md  src  tests

./bin:

./build:
liblcthw.a  liblcthw.so

./src:
lcthw

./src/lcthw:
dbg.h  list.c  list.h  list.o

./tests:
list_tests  list_tests.c  minunit.h  runtests.sh  tests.log

    函数说明

    • lsit.h 中的遍历宏
    #define LIST_FOREACH(L, S, M, V) ListNode *_node = NULL;\
                                ListNode *V = NULL;\
for(V = _node = L->S; _node != NULL; V = _node = _node->M)
    • 在list.c中的使用方法
     LIST_FOREACH(list, first, next, cur) 

会被替换成：
ListNode *_node = NULL;
ListNode *cur = NULL;
for(cur = _node = list->first;  _node != NULL; cur = _node = _node->next)

    完整源码

    Makefile

    CFLAGS=-g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG $(OPTFLAGS)
LDFLAGS=$(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))

TARGET=build/liblcthw.a
SO_TARGET=$(patsubst %.a,%.so,$(TARGET))


LDLIBS=-ldl

# The Target Build
all: $(TARGET) $(SO_TARGET) tests

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: LDLIBS += $(TARGET)
tests: $(TESTS)
    sh ./tests/runtests.sh

valgrind:
    VALGRIND="valgrind --log-file=/tmp/valgrind-%p.log" $(MAKE)

# The Cleaner
clean:
    rm -rf build $(OBJECTS) $(TESTS)
    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
check:
    @echo Files with potentially dangerous functions.
    @egrep '[^_.>a-zA-Z0-9](str(n?cpy|n?cat|xfrm|n?dup|str|pbrk|tok|_)|stpn?cpy|a?sn?printf|byte_)' $(SOURCES) || true

    list.h

    #ifndef lcthw_List_h
#define lcthw_List_h

#include <stdlib.h>

struct ListNode;

typedef struct ListNode {
    struct ListNode *next;
    struct ListNode *prev;
    void *value;
} ListNode;

typedef struct List {
    int count;
    ListNode *first;
    ListNode *last;
} List;

List *List_create();
void List_destory(List * list);
void List_clear(List * list);
void List_clear_destory(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_unshift(List *list, void *value);
void *List_shift(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

    list.c

    #include <lcthw/list.h>
#include <lcthw/dbg.h>

List *List_create() 
{
    return calloc(1, sizeof(List));
}

void List_destory(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_destory(List *list)
{
    List_clear(list);
    List_destory(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_unshift(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_shift(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 lsit, 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 next 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;
}

    单元测试 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_destory()
{
    List_clear_destory(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 on 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_unshift() 
{
    List_unshift(list, test1);
    mu_assert(List_first(list) == test1, "Wrong first value.");

    List_unshift(list, test2);
    mu_assert(List_first(list) == test2, "Wrong first value.");

    List_unshift(list, test3);
    mu_assert(List_first(list) == test3, "Wrong first value.");
    mu_assert(List_count(list) == 3, "Wrong count on unshift.");

    return NULL;
}

char *test_remove() 
{
    // we only need to test the middle remove case since push/shift
    // already tests the other cases

    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_shift() 
{
    mu_assert(List_count(list) != 0, "Wrong count before shift.");
    
    char *val = List_shift(list);
    mu_assert(val == test3, "Wrong value on shift.");

    val = List_shift(list);
    mu_assert(val == test1, "Wrong value on shift.");
    mu_assert(List_count(list) == 0, "Wrong count after shift.");

    return NULL;
}

char *all_tests()
{
    mu_suite_start();

    mu_run_test(test_create);
    mu_run_test(test_push_pop);
    mu_run_test(test_unshift);
    mu_run_test(test_remove);
    mu_run_test(test_shift);
    mu_run_test(test_destory);

    return NULL;
}

RUN_TESTS(all_tests);

    相关文章

      网友评论

          本文标题：[习题32]双链表（Makefile、完整源码、单元测试）

          本文链接：https://www.haomeiwen.com/subject/jxyblqtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|[习题32]双链表（Makefile、完整源码、单元测试）|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！