Chapter 5

1 files changed, 111 insertions, 0 deletions

diff --git a/ex5-7.c b/ex5-7.c
new file mode 100644
index 0000000..2d277ad
--- /dev/null
+++ b/ex5-7.c
@@ -0,0 +1,111 @@
+#include <stdio.h>
+#include <string.h>
+
+// An extremely simple allocation system.
+// Memory must be freed in the reverse order it was allocated.
+#define ALLOCSIZE 10000
+
+static char allocbuf[ALLOCSIZE];
+static char *allocp = allocbuf;
+
+char *alloc(int n) {
+    if (allocbuf + ALLOCSIZE - allocp >= n) {
+        allocp += n;
+        return allocp - n;
+    } else {
+        return NULL;
+    }
+}
+
+void afree(char *p) {
+    if (p >= allocbuf && p < allocbuf + ALLOCSIZE) {
+        allocp = p;
+    }
+}
+
+#define MAXLINES 5000
+
+int readlines(char* lineptr[], int nlines);
+
+void writelines(char* lineptr[], int nlines);
+
+void qsort(char* lineptr[], int left, int right);
+
+int main() {
+    int nlines;
+    char* lineptr[MAXLINES];
+    if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
+        qsort(lineptr, 0, nlines-1);
+        writelines(lineptr, nlines);
+        return 0;
+    } else {
+        fprintf(stderr, "error: input too big to sort\n");
+        return 1;
+    }
+}
+
+#define MAXLEN 1000
+
+int z_getline(char*, int);
+char* alloc(int);
+
+int readlines(char* lineptr[], int maxlines) {
+    int len; 
+    int nlines = 0;
+    char* p;
+    char line[MAXLEN];
+    while ((len = z_getline(line, MAXLEN)) > 0) {
+        if (nlines >= maxlines || (p = alloc(len)) == NULL) {
+            return -1;
+        } else {
+            line[len-1] = '\0'; // delete newline
+            strcpy(p, line);
+            lineptr[nlines++] = p;
+        }
+    }
+    return nlines;
+}
+
+void writelines(char* lineptr[], int nlines) {
+    for (int i=0; i<nlines; i++)
+        printf("%s\n", lineptr[i]);
+}
+
+void qsort(char* v[], int left, int right) {
+    int i, last;
+    void swap(char* v[], int i, int j);
+    if (left >= right) {
+        return;
+    }
+    swap(v, left, (left+right)/2);
+    last = left;
+    for (i=left+1; i<=right; i++) {
+        if (strcmp(v[i], v[left]) < 0) {
+            swap(v, ++last, i);
+        }
+    }
+    swap(v, left, last);
+    qsort(v, left, last-1);
+    qsort(v, last+1, right);
+}
+
+void swap(char* v[], int i, int j) {
+    char* temp = v[i];
+    v[i] = v[j];
+    v[j] = temp;
+}
+
+
+/* getline:  read a line into s, return length */
+int z_getline(char s[], int lim) {
+    int c, i;
+    for (i=0; i<lim-1 && (c=getchar())!=EOF && c!='\n'; ++i) {
+        s[i] = c;
+    }
+    if (c == '\n') {
+        s[i] = c;
+        ++i;
+    }
+    s[i] = '\0';
+    return i;
+}
\ No newline at end of file