HW3: 目前僅有 sort 功能

author: LAN-TW <lantw44@gmail.com> 2013-12-15 00:43:18 +0800
committer: LAN-TW <lantw44@gmail.com> 2013-12-15 00:43:18 +0800
commit: 2a4d432bed58c80040aeb8b9339dfc55a09b08f4 (patch)
tree: 7343bece162b06594316a8851ad9d2605899799c
parent: 5e828344275978133f77ed535a8ed2620e94315b (diff)
download: sp2013-2a4d432bed58c80040aeb8b9339dfc55a09b08f4.tar.gz
sp2013-2a4d432bed58c80040aeb8b9339dfc55a09b08f4.tar.zst
sp2013-2a4d432bed58c80040aeb8b9339dfc55a09b08f4.zip
7 files changed, 292 insertions, 0 deletions
diff --git a/hw3/Makefile.am b/hw3/Makefile.am
new file mode 100644
index 0000000..89c7d5b
--- /dev/null
+++ b/hw3/Makefile.am
@@ -0,0 +1,20 @@
+EXTRA_DIST = Makefile.simple README.txt
+bin_PROGRAMS = merger
+noinst_LIBRARIES = libsphw3.a
+libsphw3_a_SOURCES = xwrap.c xwrap.h
+merger_SOURCES = merger.c
+merger_CFLAGS = -pthread
+merger_LDADD = $(top_builddir)/libsphw3.a
+
+dist-hook:
+	cp -a $(distdir)/Makefile.simple $(distdir)/Makefile
+
+submit_tarball_name=SPHW3_b01902062.tar.gz
+submit_dir_name=b01902062
+
+submit: $(submit_tarball_name)
+$(submit_tarball_name): $(PACKAGE)-$(VERSION).tar.gz
+	tar -zxf $(PACKAGE)-$(VERSION).tar.gz
+	mv $(PACKAGE)-$(VERSION) $(submit_dir_name)
+	tar -zcf $(submit_tarball_name)	$(submit_dir_name)
+	rm -rf $(submit_dir_name)
diff --git a/hw3/Makefile.simple b/hw3/Makefile.simple
new file mode 100644
index 0000000..24e5964
--- /dev/null
+++ b/hw3/Makefile.simple
@@ -0,0 +1,31 @@
+# Programs
+CC=         c99
+RM=         rm -f
+
+# Internal flags
+SP_CFLAGS=  -D_POSIX_C_SOURCE=200809L $(CFLAGS)
+SP_LIBS=    $(LDFLAGS)
+
+# Let user to override these variables
+CFLAGS=     -O2 -D_REENTRANT
+LDFLAGS=    -lpthread
+
+# Build dependencies
+all_tasks=         merger
+merger_objs=       xwrap.o merger.o
+
+# Phony target
+.PHONY: all clean auto
+auto:
+	if [ ! -f configure ]; then autoreconf -iv; fi; ./configure && make
+all: $(all_tasks)
+clean:
+	$(RM) $(all_tasks) $(merger_objs)
+
+# Suffix rules
+.SUFFIXES: .c.o
+.c.o:
+	$(CC) $(SP_CFLAGS) -c $< -o $@
+
+merger: $(merger_objs)
+	$(CC) $(SP_CFLAGS) $(merger_objs) -o $@ $(SP_LIBS)
diff --git a/hw3/autogen.sh b/hw3/autogen.sh
new file mode 100755
index 0000000..6d8492f
--- /dev/null
+++ b/hw3/autogen.sh
@@ -0,0 +1,4 @@
+#!/bin/sh
+
+autoreconf -iv
+[ -z "$1" ] && exit 0
diff --git a/hw3/configure.ac b/hw3/configure.ac
new file mode 100644
index 0000000..ad614bd
--- /dev/null
+++ b/hw3/configure.ac
@@ -0,0 +1,23 @@
+#                                               -*- Autoconf -*-
+# Process this file with autoconf to produce a configure script.
+
+AC_INIT([sphw-b01902062], [3])
+AC_CONFIG_SRCDIR([merger.c])
+AC_CONFIG_HEADERS([config.h])
+
+AM_INIT_AUTOMAKE([foreign])
+AM_SILENT_RULES([yes])
+
+# Checks for programs.
+AC_PROG_CC
+AC_PROG_CC_C99
+AC_PROG_RANLIB
+
+# Checks for typedefs, structures, and compiler characteristics.
+AC_TYPE_SIZE_T
+
+# Checks for library functions.
+AC_FUNC_MALLOC
+
+AC_CONFIG_FILES([Makefile])
+AC_OUTPUT
diff --git a/hw3/merger.c b/hw3/merger.c
new file mode 100644
index 0000000..32ddc9e
--- /dev/null
+++ b/hw3/merger.c
@@ -0,0 +1,142 @@
+/* b01902062 藍挺瑋 */
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "xwrap.h"
+
+#include <inttypes.h>
+#include <pthread.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#define  SORT_DATA(x)     ((SortData*)(x))
+typedef struct {
+	int_least32_t* s;
+	int start;
+	int len;
+} SortData;
+
+#define  MERGE_DATA(x)    ((MergeData*)(x))
+typedef struct {
+	int_least32_t* s;
+	int start1;
+	int len1;
+	int start2;
+	int len2;
+} MergeData;
+
+static int_least32_t read_32b_integer (FILE* fp) {
+	int_least32_t n;
+	switch (fscanf (fp, "%" SCNdLEAST32, &n)) {
+		case 0:
+			fputs ("Invalid input!\n", stderr);
+			exit (3);
+		case EOF:
+			fputs ("Why EOF?\n", stderr);
+			exit (4);
+	}
+	return n;
+}
+
+static int qsort_cmp_cb (const void* a, const void* b) {
+	int_least32_t aa = *(int_least32_t*)a;
+	int_least32_t bb = *(int_least32_t*)b;
+	if (aa > bb) {
+		return 1;
+	} else if (aa == bb) {
+		return 0;
+	} else {
+		return -1;
+	}
+}
+
+static FILE* msg_dev;
+
+static void* task_sort (void* sd_generic) {
+	SortData* sd = SORT_DATA (sd_generic);
+	qsort (sd->s + sd->start, sd->len, sizeof (int_least32_t), qsort_cmp_cb);
+	fprintf (msg_dev, "Sorted %d elements.\n", sd->len);
+	return NULL;
+}
+
+static void* task_merge (void* sd_generic) {
+}
+
+int main (int argc, char* argv[]) {
+	if (argc < 2) {
+		fprintf (stderr, "Usage: %s segment_size\n", argv[0]);
+		return 1;
+	}
+
+	char* merger_stderr = getenv ("MERGE_STDERR");
+	if (merger_stderr == NULL || *merger_stderr == '\0') {
+		msg_dev = stdout;
+	} else {
+		msg_dev = stderr;
+	}
+
+	long ss;
+	if (xatol (argv[1], &ss) < 0) {
+		fprintf (stderr, "%s: %s is not an integer\n", argv[0], argv[1]);
+		return 2;
+	}
+	if (ss <= 0) {
+		fprintf (stderr, "%s: %ld is not a valid segment size\n", argv[0], ss);
+		return 2;
+	}
+
+	int_least32_t  n = read_32b_integer (stdin);
+	int_least32_t* s = xmalloc (sizeof (int_least32_t) * n);
+
+	for (int i = 0; i < n; i++) {
+		s[i] = read_32b_integer (stdin);
+	}
+
+	int t = n / ss;
+	int r;
+	if (t * ss != n) {
+		t++;
+	}
+	pthread_t* tid = xmalloc (sizeof (pthread_t) * t);
+
+	/* Sort */
+	SortData* sd_list = xmalloc (sizeof (SortData) * t);
+	for (int i = 0, st = 0; i < t; i++, st += ss) {
+		sd_list[i] = (SortData) { 
+			.s = s,
+			.start = st, 
+			.len = (st + ss >= n) ? (n - st) : ss
+		};
+		r = pthread_create (&tid[i], NULL, task_sort, &sd_list[i]);
+		if (r != 0) {
+			perror ("sort: pthread_create");
+			exit (5);
+		}
+	}
+	for (int i = 0; i < t; i++) {
+		pthread_join (tid[i], NULL);
+	}
+	free (sd_list);
+
+	/* Merge */
+	MergeData* md_list = xmalloc (sizeof (MergeData) * t);
+
+
+	/* Output */
+	for (int i = 0; i < n; i++) {
+		if (i) {
+			putchar (' ');
+		}
+		printf ("%" PRIdLEAST32, s[i]);
+	}
+	putchar ('\n');
+
+	free (s);
+	free (tid);
+	free (md_list);
+
+	return 0;
+}
diff --git a/hw3/xwrap.c b/hw3/xwrap.c
new file mode 100644
index 0000000..bff218e
--- /dev/null
+++ b/hw3/xwrap.c
@@ -0,0 +1,59 @@
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "xwrap.h"
+
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+
+#define RETRY_SEC     0
+#define RETRY_NSEC    250000000
+
+static const char fail_msg[] = "Fail to allocate memory. Retry ...\n";
+static const size_t fail_len = STATIC_STRLEN (fail_msg);
+
+int xatol (const char* str, long* result) {
+	int errno_save, rval;
+	long lres;
+	char* endptr;
+
+	errno_save = errno;
+	errno = 0, rval = 0;
+
+	lres = strtol (str, &endptr, 10);
+	if (str == endptr || errno != 0) {
+		rval = -1;
+	} else {
+		*result = lres;
+	}
+
+	errno = errno_save;
+
+	return rval;
+}
+
+void* xmalloc (size_t size) {
+	void* memptr;
+
+	while ((memptr = malloc (size)) == NULL) {
+		nanosleep (&(struct timespec) { RETRY_SEC, RETRY_NSEC }, NULL);
+		write (STDERR_FILENO, fail_msg, fail_len);
+	}
+
+	return memptr;
+}
+
+void* xrealloc (void* ptr, size_t size) {
+	void* newptr;
+
+	while ((newptr = realloc (ptr, size)) == NULL) {
+		nanosleep (&(struct timespec) { RETRY_SEC, RETRY_NSEC }, NULL);
+		write (STDERR_FILENO, fail_msg, fail_len);
+	}
+
+	return newptr;
+}
diff --git a/hw3/xwrap.h b/hw3/xwrap.h
new file mode 100644
index 0000000..7c64cf7
--- /dev/null
+++ b/hw3/xwrap.h
@@ -0,0 +1,13 @@
+#ifndef X_GENERAL_WRAPPER
+#define X_GENERAL_WRAPPER
+
+#include <stddef.h>
+
+#define STATIC_STRLEN(x) (sizeof(x)/sizeof(char) - 1)
+#define ARRAY_LEN(x,t)   (sizeof(x)/sizeof(t))
+
+int     xatol (const char* str, long* result);
+void*   xmalloc (size_t size);
+void*   xrealloc (void* ptr, size_t size);
+
+#endif /* X_GENERAL_WRAPPER */
author	LAN-TW <lantw44@gmail.com>	2013-12-15 00:43:18 +0800
committer	LAN-TW <lantw44@gmail.com>	2013-12-15 00:43:18 +0800
commit	2a4d432bed58c80040aeb8b9339dfc55a09b08f4 (patch)
tree	7343bece162b06594316a8851ad9d2605899799c
parent	5e828344275978133f77ed535a8ed2620e94315b (diff)
download	sp2013-2a4d432bed58c80040aeb8b9339dfc55a09b08f4.tar.gz sp2013-2a4d432bed58c80040aeb8b9339dfc55a09b08f4.tar.zst sp2013-2a4d432bed58c80040aeb8b9339dfc55a09b08f4.zip