From 824b6c414b62598f2fc141d39f3ae95a4730c5da Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Mon, 6 Mar 2017 17:00:12 +0100 Subject: [PATCH] TP 11 exo1: Add the tweaked Makefile to make the linked list a library MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- TP_11/exo1/Makefile | 94 +++++++++++++++++++ TP_11/exo1/clist.c | 216 ++++++++++++++++++++++++++++++++++++++++++++ TP_11/exo1/clist.h | 24 +++++ TP_11/exo1/exo1.c | 46 ++++++++++ 4 files changed, 380 insertions(+) create mode 100644 TP_11/exo1/Makefile create mode 100644 TP_11/exo1/clist.c create mode 100644 TP_11/exo1/clist.h create mode 100644 TP_11/exo1/exo1.c diff --git a/TP_11/exo1/Makefile b/TP_11/exo1/Makefile new file mode 100644 index 0000000..6f138af --- /dev/null +++ b/TP_11/exo1/Makefile @@ -0,0 +1,94 @@ +# Sample Makefile to build simple project. +# +# This Makefile expect all source files (.c) to be at the same level, in the +# current working directory. +# +# It will automatically generate dependencies, compile all files, and produce a +# binary using the provided name. +# +# Set BINARY_NAME to the name of the binary file to build. +# Set BUILD_TYPE to either debug or release +# +# Automatic dependencies code from: +# http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/#tldr +BINARY_NAME=exo1 +LIBOBJS=clist.o # object to put in the library +LIBRARY_NAME=libtpC +BUILD_TYPE=debug + +# ==================================== +# DO NOT CHANGE STUFF BEYOND THIS LINE +# ==================================== + +all: $(LIBRARY_NAME).a $(BINARY_NAME) + +CC=gcc +LD=gcc +AR=ar + +WARN_FLAGS = -Wall -Wextra +STD_FLAG = -std=c11 + +ifeq ($(BUILD_TYPE),debug) +BUILDDIR := .build/debug +DEBUG_FLAG = -g +STRIP_FLAG = +OPTI_FLAG = -O0 +else +BUILDDIR := .build/release +DEBUG_FLAG = +STRIP_FLAG = -s +OPTIFLAG = -O3 +endif + +CFLAGS := $(CFLAGS) $(WARN_FLAGS) $(STD_FLAG) $(OPTI_FLAG) $(DEBUG_FLAG) +LDFLAGS := $(LDFLAGS) $(STRIP_FLAG) +LIBLDFLAGS := -shared $(LDFLAGS) + +OBJDIR := $(BUILDDIR)/objs +$(shell mkdir -p $(OBJDIR)) + +SRCS=$(wildcard *.c) +OBJS=$(patsubst %.c,$(OBJDIR)/%.o,$(SRCS)) +OBJSLIB=$(addprefix $(OBJDIR)/,$(LIBOBJS)) + +DEPDIR := $(BUILDDIR)/deps +$(shell mkdir -p $(DEPDIR)) +DEPFLAGS = -MT $@ -MMD -MP -MF $(DEPDIR)/$*.Td +POSTCOMPILE = mv -f $(DEPDIR)/$*.Td $(DEPDIR)/$*.d + +$(BINARY_NAME): $(OBJS) + @echo "[LD ] $@" + @$(LD) $(CFLAGS) $(LDFLAGS) $^ $(LDLIBS) -o $@ + +$(LIBRARY_NAME).so: $(OBJSLIB) $(BINARY_NAME) + @echo "[LD ShO] $@" + @$(LD) $(CFLAGS) $(LDLIBFLAGS) $^ $(LDLIBS) -o $@ + +$(LIBRARY_NAME).a: $(OBJS) + @echo "[AR StO] $@" + @$(AR) rcs $@ $^ + +$(OBJDIR)/%.o: %.c $(DEPDIR)/%.d + @echo "[C ] $*" + @$(CC) $(DEPFLAGS) $(CFLAGS) -c $< -o $@ + @$(POSTCOMPILE) + +$(DEPDIR)/%.d: ; + +.PRECIOUS: $(DEPDIR)/%.d + +include $(wildcard $(patsubst %,$(DEPDIR)/%.d,$(basename $(SRCS)))) + +clean: + @echo "[CLN]" + -@rm -r $(BUILDDIR) + -@rm $(BINARY_NAME) + -@rm $(LIBRARY_NAME).so + -@rm $(LIBRARY_NAME).a + +disassemble: $(BINARY_NAME) + objdump -d $< | less + +symbols: $(BINARY_NAME) + objdump -t $< | sort | less diff --git a/TP_11/exo1/clist.c b/TP_11/exo1/clist.c new file mode 100644 index 0000000..244a687 --- /dev/null +++ b/TP_11/exo1/clist.c @@ -0,0 +1,216 @@ +#include +#include +#include + +#include "clist.h" + +link_t* list_new(int value) { + link_t* link_new; + link_new = malloc(sizeof(link_t)); + link_new->value = value; + link_new->next = NULL; + return link_new; +} + +link_t* list_append(link_t* head, int value) { + + if (head == NULL) { + return head = list_new(value); + } else { + link_t* head_first = head; + while (head->next != NULL) { + head = head->next; + } + head->next = list_new(value); + return head_first; + } +} + +link_t* list_prepend(link_t* head, int value) { + link_t* first_link = list_new(value); + + first_link->next = head; + return first_link; +} + +link_t* list_insert(link_t* head, unsigned index, int value) { + + if (index == 0) { + return list_prepend(head, value); + } else if (index == list_count(head)) { + return list_append(head, value); + } else { + link_t* link_insrt = list_new(value); + link_t* head_first = head; + link_t* head_next = NULL; + for (unsigned i = 0; i < index-1; i++) { + head = head->next; + } + head_next = head->next; + head->next = link_insrt; + head = link_insrt; + head->next = head_next; + return head_first; + } +} + +link_t* list_delete(link_t* head, unsigned index) { + link_t* head_prev = NULL; + link_t* head_next = NULL; + link_t* head_ret = NULL; + + if (head == NULL) { + return NULL; + } else if (index == 0) { + head_next = head->next; + free(head); + head = head_next; + head_ret = head; + } else { + link_t* head_first = head; + for (unsigned i = 0; i < index-1; i++) { + head = head->next; + } + head_prev = head; + head = head->next; + head_next = head->next; + free(head); + head = head_prev; + head->next = head_next; + head_ret = head_first; + } + if (head_ret != NULL) { + return head_ret; + } else { + return NULL; + } +} + +link_t* list_concat(link_t* first, link_t* second) { + link_t* head_first = first; + + while (first->next != NULL) { + first = first->next; + } + first->next = second; + return head_first; +} + +link_t* list_sort(link_t* head) { + int tmp; + bool isswaped; + link_t* head_first = head; + + do { + isswaped = false; + while (head->next != NULL) { + if (head->value > head->next->value) { + tmp = head->value; + head->value = head->next->value; + head->next->value = tmp; + isswaped = true; + } + head = head->next; + } + /* Reloop at the beginning of the list until there's values swaped */ + head = head_first; + } while (isswaped); + return head_first; +} + +static link_t* _list_merge_sort(link_t* head1, link_t* head2) { + link_t* head_result = NULL; + + if (head1 == NULL) { + return head2; + } + if (head2 == NULL) { + return head1; + } + if (head1->value < head2->value) { + head_result = head1; + head_result->next = _list_merge_sort(head1->next, head2); + } else { + head_result = head2; + head_result->next = _list_merge_sort(head1, head2->next); + } + return head_result; +} + +link_t* list_merge_sort(link_t* head) { + link_t* head1; + link_t* head2; + + if (head == NULL || head->next == NULL) { + return head; + } + + head1 = head; + head2 = head->next; + while (head2 != NULL && head2->next != NULL) { + head = head->next; + head2 = head->next->next; + } + head2 = head->next; + head->next = NULL; + + head1 = list_merge_sort(head1); + head2 = list_merge_sort(head2); + return _list_merge_sort(head1, head2); +} + +unsigned list_count(link_t* head) { + unsigned count = 0; + + while (head != NULL) { + ++count; + head = head->next; + } + return count; +} + +void list_set(link_t* head, unsigned index, int value) { + unsigned count = 0; + + while (head != NULL && count < index) { + ++count; + head = head->next; + } + if (head != NULL) { head->value = value; } +} + +int list_get(link_t* head, unsigned index) { + unsigned count = 0; + + while (head != NULL && count < index) { + ++count; + head = head->next; + } + if (head != NULL) { + return head->value; + } else { + return -1; + } +} + +void list_clear(link_t* head) { + link_t* next_link = NULL; + + while (head != NULL) { + next_link = head->next; + free(head); + head = next_link; + } +} + +void list_display_values(link_t* head) { + unsigned i = 0; + + printf("------Begin------\n"); + while (head != NULL) { + printf("value at [%d]=%d\n", i, head->value); + head = head->next; + i++; + } + printf("------End------\n"); +} diff --git a/TP_11/exo1/clist.h b/TP_11/exo1/clist.h new file mode 100644 index 0000000..2ca5752 --- /dev/null +++ b/TP_11/exo1/clist.h @@ -0,0 +1,24 @@ +#ifndef CLIST_H +#define CLIST_H + +/** Linked list of int */ +typedef struct link_s { + int value; + struct link_s* next; +} link_t; + +link_t* list_new(int value); +link_t* list_append(link_t* head, int value); +link_t* list_prepend(link_t* head, int value); +link_t* list_insert(link_t* head, unsigned index, int value); +link_t* list_delete(link_t* head, unsigned index); +link_t* list_concat(link_t* first, link_t* second); +link_t* list_sort(link_t* head); +link_t* list_merge_sort(link_t* head); +unsigned list_count(link_t* head); +void list_set(link_t* head, unsigned index, int value); +int list_get(link_t* head, unsigned index); +void list_clear(link_t* head); +void list_display_values(link_t* head); + +#endif /* CLIST_H */ diff --git a/TP_11/exo1/exo1.c b/TP_11/exo1/exo1.c new file mode 100644 index 0000000..810bd9e --- /dev/null +++ b/TP_11/exo1/exo1.c @@ -0,0 +1,46 @@ +#include + +#include "clist.h" + +int main() { + link_t* head1 = NULL; + link_t* head2 = NULL; + link_t* head = NULL; + + printf("Longueur de la liste: %d\n", list_count(head1)); + head1 = list_append(head1, 1); + head1 = list_append(head1, 2); + head1 = list_append(head1, 3); + head1 = list_append(head1, 4); + printf("Longueur de la liste: %d\n", list_count(head1)); + list_display_values(head1); + head1 = list_prepend(head1, 5); + printf("Longueur de la liste: %d\n", list_count(head1)); + list_display_values(head1); + list_set(head1, 0, 78); + list_display_values(head1); + head1 = list_insert(head1, 2, 7); + list_display_values(head1); + head1 = list_delete(head1, 3); + list_display_values(head1); + head1 = list_append(head1, 5); + head1 = list_append(head1, 12); + head1 = list_append(head1, 65); + head1 = list_append(head1, 21); + head1 = list_sort(head1); + list_display_values(head1); + head2 = list_insert(head2, 0, 8); + head2 = list_append(head2, 6); + head2 = list_prepend(head2, 5); + list_display_values(head2); + head = list_concat(head1, head2); + list_display_values(head); + head = list_merge_sort(head); + //head = list_sort(head); + list_display_values(head); + //list_clear(head1); + //list_clear(head2); + list_clear(head); + + return 0; +} -- 2.34.1