#include <stdio.h>
#include <stdlib.h> //for atof(), atoi()
#include <string.h> //for strcpy()
#include <ctype.h> //for tolower(), isalnum(), isdigit()
//compile with: gcc -Wall -Wextra cc-c.c -o cc-c
//run with: printf 'pointer\t102\n#define\t89\nPointer\t94\ndefine\t14\npointer\t98\n' | ./cc-c # #define 89, Pointer 94, define 14, pointer 102, pointer 98
// or: printf 'pointer\t102\n#define\t89\nPointer\t94\ndefine\t14\npointer\t98\n' | ./cc-c +1 -df +2 -n # define 14, #define 89, Pointer 94, pointer 98, pointer 102
// or: printf 'pointer\t102\n#define\t89\nPointer\t94\ndefine\t14\npointer\t98\n' | ./cc-c +1 -df +2 -nr # #define 89, define 14, pointer 102, pointer 98, Pointer 94
// or: printf 'a-d\nAC\nab\n' | ./cc-c -dfr # a-d AC ab (no +N: whole line, as in 5-16)
//K&R2 exercise 5-17: add a field-searching capability, so sorting may
//be done on fields within lines, each field sorted according to an
//independent set of options. (The index for this book was sorted with
//-df for the index category and -n for the page numbers.)
//
//Builds on exercise 5-16 (archived just below).
//
//FIELDS: a line is split into fields at each TAB. In "pointer\t102",
//field 1 is "pointer" and field 2 is "102". Field 0 means the whole
//line. A field past the end of a line counts as an empty string.
//
//KEYS: "+N" on the command line starts a sort key on field N, and the
//flags that follow it (-n -r -f -d) belong to that key alone:
//
// ./cc-c +1 -df +2 -n
// ^^^^^^ ^^^^^
// key 1: field 1, directory order, fold case
// key 2: field 2, numeric
//
//Two lines are compared on key 1 first. Only if key 1 calls them equal
//does key 2 get a say -- exactly how the book's index works: entries
//sort by name, and entries with the same name sort by page number.
//Flags given BEFORE any +N make a key on the whole line (field 0), so
//every command from 5-14 to 5-16 still works unchanged.
//
//Each key's flags are kept as bits in one int (chapter 2's bitwise
//operators), one bit per flag:
//
// #define NUMERIC 1 0001
// #define REVERSE 2 0010
// #define FOLD 4 0100
// #define DIR 8 1000
//
//-df sets opt |= DIR, then opt |= FOLD, giving 1100. Testing a flag is
//opt & FOLD: non-zero if that bit is on. Two parallel arrays hold the
//keys: kfield[i] is key i's field number, kopt[i] its flag bits.
//(Chapter 6's structs will be the neater way to bundle these.)
//
//What changed from 5-16:
//1. my_qsort now always gets ONE comparison, fieldcmp. For each key in
// turn it copies that field out of both lines, compares the copies
// with that key's flags, and returns the first non-zero answer.
//2. fold and dir are no longer globals: fieldcmp calls charcmp
// directly, so it can simply pass them as arguments. Only my_qsort's
// calls are limited to two arguments, and fieldcmp is the only
// function my_qsort calls now.
//3. basecmp and revcmp are gone. -r is handled inside fieldcmp by the
// same trick as revcmp -- comparing (b, a) instead of (a, b) -- but
// per key, so +1 -df +2 -nr sorts names up and page numbers down.
#define MAXLINES 5000 //max #lines to be sorted
#define MAXLEN 10000 //max length of any input line (book: 1000)
#define ALLOCSIZE 1000000 //size of available space for alloc
#define MAXKEYS 10 //max #sort keys (+N) on the command line
#define NUMERIC 1 //-n: compare as numbers
#define REVERSE 2 //-r: decreasing order
#define FOLD 4 //-f: fold upper and lower case
#define DIR 8 //-d: only letters, digits and blanks
char *lineptr[MAXLINES]; //pointers to text lines
int nkeys = 0; //number of sort keys
int kfield[MAXKEYS]; //kfield[i]: field that key i sorts on
int kopt[MAXKEYS]; //kopt[i]: key i's flag bits
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void my_qsort(void *lineptr[], int left, int right,
int (*comp)(void *, void *));
int fieldcmp(void *, void *);
void getfield(char *s, int n, char *field);
int numcmp(char *, char *);
int charcmp(char *, char *, int fold, int dir);
//sort input lines
int main(int argc, char *argv[])
{
int nlines; //number of input lines read
int bad = 0; //1 if the command line is wrong
char *p, *q;
int c;
while (--argc > 0 && !bad) {
p = *++argv;
if (*p == '+') { //+N: start a key on field N
for (q = p+1; isdigit((unsigned char) *q); q++)
;
if (q == p+1 || *q != '\0') { //no digits, or junk after them
printf("sort: bad field %s\n", p);
bad = 1;
} else if (nkeys >= MAXKEYS) {
printf("sort: more than %d keys\n", MAXKEYS);
bad = 1;
} else {
kfield[nkeys] = atoi(p+1);
kopt[nkeys++] = 0;
}
} else if (*p == '-') { //flags for the current key
if (nkeys == 0) { //no +N yet: key on whole line
kfield[0] = 0;
kopt[0] = 0;
nkeys = 1;
}
while ((c = *++p))
switch (c) {
case 'n':
kopt[nkeys-1] |= NUMERIC;
break;
case 'r':
kopt[nkeys-1] |= REVERSE;
break;
case 'f':
kopt[nkeys-1] |= FOLD;
break;
case 'd':
kopt[nkeys-1] |= DIR;
break;
default:
printf("sort: illegal option %c\n", c);
bad = 1;
break;
}
} else {
printf("sort: unexpected argument %s\n", p);
bad = 1;
}
}
if (bad) {
printf("usage: sort [+N] -n -r -f -d ... e.g. ./cc-c +1 -df +2 -n\n");
return 1;
}
if (nkeys == 0) { //no arguments: plain text sort
kfield[0] = 0;
kopt[0] = 0;
nkeys = 1;
}
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
my_qsort((void **) lineptr, 0, nlines-1, fieldcmp);
writelines(lineptr, nlines);
return 0;
} else {
printf("input too big to sort\n");
return 1;
}
}
//fieldcmp: compare lines a and b key by key; the first key that
//finds a difference decides
int fieldcmp(void *a, void *b)
{
char fa[MAXLEN], fb[MAXLEN]; //the current field of a and of b
char *s1, *s2;
int i, r;
for (i = 0; i < nkeys; i++) {
getfield(a, kfield[i], fa);
getfield(b, kfield[i], fb);
if (kopt[i] & REVERSE) { //swap arguments, as revcmp did
s1 = fb;
s2 = fa;
} else {
s1 = fa;
s2 = fb;
}
if (kopt[i] & NUMERIC)
r = numcmp(s1, s2);
else
r = charcmp(s1, s2, kopt[i] & FOLD, kopt[i] & DIR);
if (r != 0)
return r;
}
return 0; //equal on every key
}
//getfield: copy field n of line s into field; fields are separated
//by tabs, field 0 is the whole line, a missing field is empty
void getfield(char *s, int n, char *field)
{
if (n == 0) {
strcpy(field, s);
return;
}
while (--n > 0) { //skip the n-1 fields before field n
while (*s != '\0' && *s != '\t')
s++;
if (*s == '\0') { //line has fewer than n fields
*field = '\0';
return;
}
s++; //step over the tab
}
while (*s != '\0' && *s != '\t')
*field++ = *s++;
*field = '\0';
}
//numcmp: compare s1 and s2 numerically
int numcmp(char *s1, char *s2)
{
double v1, v2;
v1 = atof(s1);
v2 = atof(s2);
if (v1 < v2)
return -1;
else if (v1 > v2)
return 1;
else
return 0;
}
//dirchar: 1 if c counts in directory order (letter, digit, blank)
int dirchar(int c)
{
return isalnum(c) || c == ' ' || c == '\t';
}
//charcmp: compare s1 and s2 as text; if fold, upper and lower case
//compare equal; if dir, only letters, digits and blanks are compared
int charcmp(char *s1, char *s2, int fold, int dir)
{
unsigned char *p1 = (unsigned char *) s1;
unsigned char *p2 = (unsigned char *) s2;
int c1, c2;
for (;;) {
if (dir) {
while (*p1 != '\0' && !dirchar(*p1))
p1++;
while (*p2 != '\0' && !dirchar(*p2))
p2++;
}
c1 = fold ? tolower(*p1) : *p1;
c2 = fold ? tolower(*p2) : *p2;
if (c1 != c2)
return c1 - c2;
if (c1 == '\0') //both strings ended together
return 0;
p1++;
p2++;
}
}
//my_qsort: sort v[left]...v[right] into increasing order
void my_qsort(void *v[], int left, int right,
int (*comp)(void *, void *))
{
int i, last;
void swap(void *v[], int, int);
if (left >= right) //do nothing if array contains
return; //fewer than two elements
swap(v, left, (left + right)/2);
last = left;
for (i = left+1; i <= right; i++)
if ((*comp)(v[i], v[left]) < 0)
swap(v, ++last, i);
swap(v, left, last);
my_qsort(v, left, last-1, comp);
my_qsort(v, last+1, right, comp);
}
//swap: interchange v[i] and v[j]
void swap(void *v[], int i, int j)
{
void *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
//--- from section 5.6 ---
int my_getline(char *, int);
char *alloc(int);
//readlines: read input lines
int readlines(char *lineptr[], int maxlines)
{
int len, nlines;
char *p, line[MAXLEN];
nlines = 0;
while ((len = my_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;
}
//writelines: write output lines
void writelines(char *lineptr[], int nlines)
{
int i;
for (i = 0; i < nlines; i++)
printf("%s\n", lineptr[i]);
}
//my_getline: read one line (including '\n') into s, return its length
int my_getline(char *s, int lim)
{
int c = 0;
char *p = s;
while (--lim > 0 && (c = getchar()) != EOF && c != '\n')
*p++ = c;
if (c == '\n')
*p++ = c;
*p = '\0';
return p - s;
}
//alloc: return pointer to n characters from one static buffer
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;
}
/*
#include <stdio.h>
#include <stdlib.h> //for atof()
#include <string.h> //for strcpy()
#include <ctype.h> //for tolower(), isalnum()
//compile with: gcc -Wall -Wextra cc-c.c -o cc-c
//run with: printf 'a-d\nAC\nab\n' | ./cc-c # AC a-d ab
// or: printf 'a-d\nAC\nab\n' | ./cc-c -f # a-d ab AC
// or: printf 'a-d\nAC\nab\n' | ./cc-c -d # AC ab a-d
// or: printf 'a-d\nAC\nab\n' | ./cc-c -df # ab AC a-d
// or: printf 'a-d\nAC\nab\n' | ./cc-c -dfr # a-d AC ab
//K&R2 exercise 5-16: add the -d ("directory order") option, which
//makes comparisons only on letters, numbers and blanks. Make sure it
//works in conjunction with -f.
//
//Builds on exercise 5-15 (archived just below). -d means: while
//comparing, act as if every character that isn't a letter, a digit, a
//space or a tab weren't there. So "a-d" compares as "ad", and sorts
//AFTER "ab" -- without -d, '-' (45) is smaller than 'b' (98), and
//"a-d" sorts first.
//
//Why one comparison instead of more: -d and -f are independent, so
//separate functions would need four (plain, fold, dir, dir+fold), and
//every future flag would double that. Instead ONE function, charcmp,
//does both jobs, switched on and off by two flags:
//
// 1. if dir: skip ahead in each string past characters -d ignores
// 2. if fold: compare tolower() of the two characters, else the
// characters themselves
// 3. differ? return the difference; both at '\0'? return 0
// 4. otherwise step both pointers and go round again
//
//With neither flag, charcmp is just strcmp, so strcmp_v and 5-15's
//strcmp_f are both gone.
//
//fold and dir moved OUT of main and became globals, for the same
//reason basecmp is one: my_qsort calls charcmp with exactly two
//arguments, so charcmp has no other way to learn what the flags are.
//
//-n still overrides -d and -f (numbers have no case or punctuation to
//skip), and 5-14's revcmp still reverses whichever comparison was
//picked, so -r works with everything.
//
//Note: in the default "C" locale, isalnum() is true only for ASCII
//letters and digits. Bytes of a UTF-8 character like 乾 are >= 128, so
//-d skips them entirely.
#define MAXLINES 5000 //max #lines to be sorted
#define MAXLEN 10000 //max length of any input line (book: 1000)
#define ALLOCSIZE 1000000 //size of available space for alloc
char *lineptr[MAXLINES]; //pointers to text lines
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void my_qsort(void *lineptr[], int left, int right,
int (*comp)(void *, void *));
int numcmp(void *, void *);
int charcmp(void *, void *);
int revcmp(void *, void *);
int (*basecmp)(void *, void *); //the comparison revcmp reverses
int fold = 0; //1 if -f: fold upper and lower case
int dir = 0; //1 if -d: compare only letters, digits, blanks
//sort input lines
int main(int argc, char *argv[])
{
int nlines; //number of input lines read
int numeric = 0; //1 if -n: numeric sort
int reverse = 0; //1 if -r: decreasing order
int c;
while (--argc > 0 && (*++argv)[0] == '-')
while ((c = *++argv[0]))
switch (c) {
case 'n':
numeric = 1;
break;
case 'r':
reverse = 1;
break;
case 'f':
fold = 1;
break;
case 'd':
dir = 1;
break;
default:
printf("sort: illegal option %c\n", c);
argc = -1; //force the usage message below
break;
}
if (argc != 0) {
printf("usage: sort -n -r -f -d e.g. printf 'a-d\\nAC\\nab\\n' | ./cc-c -df\n");
return 1;
}
basecmp = numeric ? numcmp : charcmp;
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
my_qsort((void **) lineptr, 0, nlines-1,
reverse ? revcmp : basecmp);
writelines(lineptr, nlines);
return 0;
} else {
printf("input too big to sort\n");
return 1;
}
}
//dirchar: 1 if c counts in directory order (letter, digit, blank)
int dirchar(int c)
{
return isalnum(c) || c == ' ' || c == '\t';
}
//charcmp: compare s1 and s2 as text; if fold, upper and lower case
//compare equal; if dir, only letters, digits and blanks are compared
int charcmp(void *s1, void *s2)
{
unsigned char *p1 = s1, *p2 = s2;
int c1, c2;
for (;;) {
if (dir) {
while (*p1 != '\0' && !dirchar(*p1))
p1++;
while (*p2 != '\0' && !dirchar(*p2))
p2++;
}
c1 = fold ? tolower(*p1) : *p1;
c2 = fold ? tolower(*p2) : *p2;
if (c1 != c2)
return c1 - c2;
if (c1 == '\0') //both strings ended together
return 0;
p1++;
p2++;
}
}
//revcmp: the comparison in basecmp, with its arguments swapped --
//so whatever basecmp calls "smaller" now sorts later
int revcmp(void *a, void *b)
{
return (*basecmp)(b, a);
}
//my_qsort: sort v[left]...v[right] into increasing order
void my_qsort(void *v[], int left, int right,
int (*comp)(void *, void *))
{
int i, last;
void swap(void *v[], int, int);
if (left >= right) //do nothing if array contains
return; //fewer than two elements
swap(v, left, (left + right)/2);
last = left;
for (i = left+1; i <= right; i++)
if ((*comp)(v[i], v[left]) < 0)
swap(v, ++last, i);
swap(v, left, last);
my_qsort(v, left, last-1, comp);
my_qsort(v, last+1, right, comp);
}
//numcmp: compare s1 and s2 numerically
int numcmp(void *s1, void *s2)
{
double v1, v2;
v1 = atof(s1);
v2 = atof(s2);
if (v1 < v2)
return -1;
else if (v1 > v2)
return 1;
else
return 0;
}
//swap: interchange v[i] and v[j]
void swap(void *v[], int i, int j)
{
void *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
//--- from section 5.6 ---
int my_getline(char *, int);
char *alloc(int);
//readlines: read input lines
int readlines(char *lineptr[], int maxlines)
{
int len, nlines;
char *p, line[MAXLEN];
nlines = 0;
while ((len = my_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;
}
//writelines: write output lines
void writelines(char *lineptr[], int nlines)
{
int i;
for (i = 0; i < nlines; i++)
printf("%s\n", lineptr[i]);
}
//my_getline: read one line (including '\n') into s, return its length
int my_getline(char *s, int lim)
{
int c = 0;
char *p = s;
while (--lim > 0 && (c = getchar()) != EOF && c != '\n')
*p++ = c;
if (c == '\n')
*p++ = c;
*p = '\0';
return p - s;
}
//alloc: return pointer to n characters from one static buffer
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;
}
*/
/*
#include <stdio.h>
#include <stdlib.h> //for atof()
#include <string.h> //for strcmp(), strcpy()
#include <ctype.h> //for tolower()
//compile with: gcc -Wall -Wextra cc-c.c -o cc-c
//run with: printf 'b\nA\na\nB\n' | ./cc-c (A B a b)
// or: printf 'b\nA\na\nB\n' | ./cc-c -f (A a b B)
// or: printf 'b\nA\na\nB\n' | ./cc-c -fr (B b A a)
// or: printf '10\n9\n100\n' | ./cc-c -nr (100 10 9)
//K&R2 exercise 5-15: add the option -f to fold upper and lower case
//together, so that case distinctions are not made during sorting; for
//example, a and A compare equal.
//
//Builds on exercise 5-14 (archived just below). Why plain sorting
//needs fixing: strcmp compares character CODES, and in ASCII every
//upper-case letter comes before every lower-case one ('A' is 65, 'Z'
//is 90, 'a' is 97). So without -f, "B" sorts before "a" -- the output
//is A B a b, not a dictionary order.
//
//The fix is one new comparison, strcmp_f. It walks both strings like
//strcmp does, but compares tolower() of each character, so 'A' and
//'a' both look like 'a'. It returns the difference of the first pair
//that differs (after folding), or 0 if the strings match to the end.
//
//Two details inside strcmp_f:
//1. tolower(c) is only defined for c that fits in an unsigned char (or
// is EOF). A plain char holding a byte >= 128 (e.g. part of a UTF-8
// character) can be NEGATIVE, so each byte is read through an
// unsigned char pointer first.
//2. The loop tests for '\0' only on s1. That's enough: if s2 ends
// first, its '\0' differs from s1's character, so the loop stops on
// the mismatch anyway.
//
//Nothing else changes. main just picks the base comparison:
//
// basecmp = numeric ? numcmp : (fold ? strcmp_f : strcmp_v);
//
//and 5-14's revcmp reverses whichever one was picked, so -f works with
//-r for free (-n ignores -f: numbers have no case).
//
//Note: "a" and "A" compare EQUAL under -f, so which one prints first is
//up to my_qsort -- it isn't a stable sort, so equal lines may come out
//in either order.
#define MAXLINES 5000 //max #lines to be sorted
#define MAXLEN 10000 //max length of any input line (book: 1000)
#define ALLOCSIZE 1000000 //size of available space for alloc
char *lineptr[MAXLINES]; //pointers to text lines
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void my_qsort(void *lineptr[], int left, int right,
int (*comp)(void *, void *));
int numcmp(void *, void *);
int strcmp_v(void *, void *);
int strcmp_f(void *, void *);
int revcmp(void *, void *);
int (*basecmp)(void *, void *); //the comparison revcmp reverses
//sort input lines
int main(int argc, char *argv[])
{
int nlines; //number of input lines read
int numeric = 0; //1 if -n: numeric sort
int reverse = 0; //1 if -r: decreasing order
int fold = 0; //1 if -f: fold upper and lower case
int c;
while (--argc > 0 && (*++argv)[0] == '-')
while ((c = *++argv[0]))
switch (c) {
case 'n':
numeric = 1;
break;
case 'r':
reverse = 1;
break;
case 'f':
fold = 1;
break;
default:
printf("sort: illegal option %c\n", c);
argc = -1; //force the usage message below
break;
}
if (argc != 0) {
printf("usage: sort -n -r -f e.g. printf 'b\\nA\\na\\n' | ./cc-c -f\n");
return 1;
}
basecmp = numeric ? numcmp : (fold ? strcmp_f : strcmp_v);
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
my_qsort((void **) lineptr, 0, nlines-1,
reverse ? revcmp : basecmp);
writelines(lineptr, nlines);
return 0;
} else {
printf("input too big to sort\n");
return 1;
}
}
//strcmp_f: like strcmp, but upper and lower case compare equal
int strcmp_f(void *s1, void *s2)
{
unsigned char *p1 = s1, *p2 = s2;
for ( ; tolower(*p1) == tolower(*p2); p1++, p2++)
if (*p1 == '\0')
return 0;
return tolower(*p1) - tolower(*p2);
}
//revcmp: the comparison in basecmp, with its arguments swapped --
//so whatever basecmp calls "smaller" now sorts later
int revcmp(void *a, void *b)
{
return (*basecmp)(b, a);
}
//my_qsort: sort v[left]...v[right] into increasing order
void my_qsort(void *v[], int left, int right,
int (*comp)(void *, void *))
{
int i, last;
void swap(void *v[], int, int);
if (left >= right) //do nothing if array contains
return; //fewer than two elements
swap(v, left, (left + right)/2);
last = left;
for (i = left+1; i <= right; i++)
if ((*comp)(v[i], v[left]) < 0)
swap(v, ++last, i);
swap(v, left, last);
my_qsort(v, left, last-1, comp);
my_qsort(v, last+1, right, comp);
}
//numcmp: compare s1 and s2 numerically
int numcmp(void *s1, void *s2)
{
double v1, v2;
v1 = atof(s1);
v2 = atof(s2);
if (v1 < v2)
return -1;
else if (v1 > v2)
return 1;
else
return 0;
}
//strcmp_v: strcmp with the (void *, void *) type my_qsort expects
int strcmp_v(void *s1, void *s2)
{
return strcmp(s1, s2);
}
//swap: interchange v[i] and v[j]
void swap(void *v[], int i, int j)
{
void *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
//--- from section 5.6 ---
int my_getline(char *, int);
char *alloc(int);
//readlines: read input lines
int readlines(char *lineptr[], int maxlines)
{
int len, nlines;
char *p, line[MAXLEN];
nlines = 0;
while ((len = my_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;
}
//writelines: write output lines
void writelines(char *lineptr[], int nlines)
{
int i;
for (i = 0; i < nlines; i++)
printf("%s\n", lineptr[i]);
}
//my_getline: read one line (including '\n') into s, return its length
int my_getline(char *s, int lim)
{
int c = 0;
char *p = s;
while (--lim > 0 && (c = getchar()) != EOF && c != '\n')
*p++ = c;
if (c == '\n')
*p++ = c;
*p = '\0';
return p - s;
}
//alloc: return pointer to n characters from one static buffer
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;
}
*/
/*
#include <stdio.h>
#include <stdlib.h> //for atof()
#include <string.h> //for strcmp(), strcpy()
//compile with: gcc -Wall -Wextra cc-c.c -o cc-c
//run with: printf '10\n9\n100\n' | ./cc-c -n (9 10 100)
// or: printf '10\n9\n100\n' | ./cc-c -nr (100 10 9)
// or: printf 'pear\napple\nfig\n' | ./cc-c -r (pear fig apple)
//K&R2 exercise 5-14: modify the sort program to handle a -r flag, which
//indicates sorting in reverse (decreasing) order. Be sure that -r works
//with -n.
//
//Builds on section 5.11's sort (archived just below). Two changes:
//
//1. Flags are read the way section 5.10's find reads -x and -n, so
// they can be given separately (-n -r) or combined (-nr, -rn):
// while (--argc > 0 && (*++argv)[0] == '-')
// while ((c = *++argv[0]))
// switch (c) ...
// Anything else -- an unknown letter, or a word that isn't a flag --
// prints a usage message.
//
//2. Reversing needs NO new comparison for text or for numbers. The
// chosen comparison (strcmp_v or numcmp) is kept in a function
// pointer, basecmp, and one small function wraps it:
//
// int revcmp(void *a, void *b) { return (*basecmp)(b, a); }
//
// It calls the same comparison with its arguments SWAPPED. Asking
// "how does b compare to a?" instead of "a to b" flips every answer,
// so my_qsort -- unchanged -- sorts in decreasing order. Because
// basecmp can point at either function, -r works with -n and without
// it, for free. (Swapping is safer than writing -(*basecmp)(a, b):
// negating the smallest possible int overflows, swapping can't.)
//
// main then hands my_qsort one of three functions:
// strcmp_v or numcmp (normal order)
// revcmp (reverse; revcmp calls basecmp)
//
//Same limits as 5.11: at most 5000 lines, 10000 bytes per line.
#define MAXLINES 5000 //max #lines to be sorted
#define MAXLEN 10000 //max length of any input line (book: 1000)
#define ALLOCSIZE 1000000 //size of available space for alloc
char *lineptr[MAXLINES]; //pointers to text lines
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void my_qsort(void *lineptr[], int left, int right,
int (*comp)(void *, void *));
int numcmp(void *, void *);
int strcmp_v(void *, void *);
int revcmp(void *, void *);
int (*basecmp)(void *, void *); //the comparison revcmp reverses
//sort input lines
int main(int argc, char *argv[])
{
int nlines; //number of input lines read
int numeric = 0; //1 if -n: numeric sort
int reverse = 0; //1 if -r: decreasing order
int c;
while (--argc > 0 && (*++argv)[0] == '-')
while ((c = *++argv[0]))
switch (c) {
case 'n':
numeric = 1;
break;
case 'r':
reverse = 1;
break;
default:
printf("sort: illegal option %c\n", c);
argc = -1; //force the usage message below
break;
}
if (argc != 0) {
printf("usage: sort -n -r e.g. printf '10\\n9\\n' | ./cc-c -nr\n");
return 1;
}
basecmp = numeric ? numcmp : strcmp_v;
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
my_qsort((void **) lineptr, 0, nlines-1,
reverse ? revcmp : basecmp);
writelines(lineptr, nlines);
return 0;
} else {
printf("input too big to sort\n");
return 1;
}
}
//revcmp: the comparison in basecmp, with its arguments swapped --
//so whatever basecmp calls "smaller" now sorts later
int revcmp(void *a, void *b)
{
return (*basecmp)(b, a);
}
//my_qsort: sort v[left]...v[right] into increasing order
void my_qsort(void *v[], int left, int right,
int (*comp)(void *, void *))
{
int i, last;
void swap(void *v[], int, int);
if (left >= right) //do nothing if array contains
return; //fewer than two elements
swap(v, left, (left + right)/2);
last = left;
for (i = left+1; i <= right; i++)
if ((*comp)(v[i], v[left]) < 0)
swap(v, ++last, i);
swap(v, left, last);
my_qsort(v, left, last-1, comp);
my_qsort(v, last+1, right, comp);
}
//numcmp: compare s1 and s2 numerically
int numcmp(void *s1, void *s2)
{
double v1, v2;
v1 = atof(s1);
v2 = atof(s2);
if (v1 < v2)
return -1;
else if (v1 > v2)
return 1;
else
return 0;
}
//strcmp_v: strcmp with the (void *, void *) type my_qsort expects
int strcmp_v(void *s1, void *s2)
{
return strcmp(s1, s2);
}
//swap: interchange v[i] and v[j]
void swap(void *v[], int i, int j)
{
void *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
//--- from section 5.6 ---
int my_getline(char *, int);
char *alloc(int);
//readlines: read input lines
int readlines(char *lineptr[], int maxlines)
{
int len, nlines;
char *p, line[MAXLEN];
nlines = 0;
while ((len = my_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;
}
//writelines: write output lines
void writelines(char *lineptr[], int nlines)
{
int i;
for (i = 0; i < nlines; i++)
printf("%s\n", lineptr[i]);
}
//my_getline: read one line (including '\n') into s, return its length
int my_getline(char *s, int lim)
{
int c = 0;
char *p = s;
while (--lim > 0 && (c = getchar()) != EOF && c != '\n')
*p++ = c;
if (c == '\n')
*p++ = c;
*p = '\0';
return p - s;
}
//alloc: return pointer to n characters from one static buffer
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;
}
*/