tpop

The Practice of Programming - Solutions
Log | Files | Refs

exercise-2-4.c (2470B)

      1 #include <error.h>
      2 #include <stdio.h>
      3 #include <stdlib.h>
      4 #include <string.h>
      5 /* Solution - Exercise 2-4 
      6  * Compare insertion sort and quick sort (library routine)
      7  * strings are used as opposed to integers
      8  * 
      9  * Observation:
     10  * Found that insertion sort took ~9 mins to sort a string array
     11  * of size 12.3 MB in comparison with qsort which took <1 min.
     12  */
     13 
     14 void delstr(char *);
     15 void genstrstore(void);
     16 void isort(int (*)(const void *, const void *));
     17 void store(char);
     18 void strstore(char *);
     19 
     20 char *buf;
     21 char *end;
     22 char *nextelem;
     23 char **strbuf;
     24 char **strnextelem;
     25 char **strend;
     26 
     27 int
     28 comp(const void *a, const void *b)
     29 {
     30 	char *k = (char *)a;
     31 	char *j = (char *)b;
     32 
     33 	return *k - *j;
     34 }
     35 
     36 int
     37 qcomp(const void *a, const void *b)
     38 {
     39 	char *s = *(char **)a;
     40 	char *t = *(char **)b;
     41 
     42 	return *s - *t;
     43 }
     44 
     45 
     46 int
     47 main(int argc, char **argv)
     48 {
     49 	char c;
     50 
     51 	while ((c = getc(stdin)) != EOF) {
     52 		store(c);
     53 	}
     54 
     55 	genstrstore();
     56 	
     57 	qsort(strbuf, strnextelem - strbuf, sizeof(char *), qcomp);
     58 	/* isort(comp); */
     59 	for (char **t = strbuf; t < strnextelem ; t++) {
     60 		printf("%s\n", *t);
     61 	}
     62 	
     63 	free(strbuf);
     64 	free(buf);
     65 	
     66 	return 0;
     67 }
     68 
     69 void
     70 genstrstore(void)
     71 {
     72 	for (char *c = buf; c < nextelem; c++) {
     73 		if (c == buf)
     74 			strstore(c);
     75 
     76 		if(*c == '\n') {
     77 			*c = '\0';
     78 			c++;
     79 			strstore(c);
     80 		}
     81 	}
     82 }
     83 
     84 
     85 void
     86 store(char c)
     87 {
     88 	static int growthfact = 1;
     89 	char *t;
     90 
     91 	if (nextelem == end) {
     92 		if ((t = realloc(buf, growthfact * 512 * sizeof(char))) == NULL)
     93 			error(1, 1, "realloc");
     94 		
     95 		nextelem = t + (nextelem - buf);
     96 		buf = t;
     97 		end = buf + (growthfact * 512);
     98 		growthfact++;
     99 	}
    100 	
    101 	if (nextelem != end)
    102 		*nextelem++ = c;
    103 }
    104 
    105 void
    106 strstore(char *s)
    107 {
    108 	static int growthfact = 1;
    109 	char **t;
    110 
    111 	if (strnextelem == strend) {
    112 		if ((t = realloc(strbuf, growthfact * 512 * sizeof(char *))) == NULL)
    113 			error(1, 1, "realloc");
    114 		strnextelem = t + (strnextelem - strbuf);
    115 		strbuf = t;
    116 		strend = strbuf + (growthfact * 512);
    117 		growthfact++;
    118 	}
    119 	
    120 	if (strnextelem != strend)
    121 		*strnextelem++ = s;
    122 }
    123 
    124 void
    125 delstr(char *s)
    126 {
    127 	for (char **t = strbuf; t < strnextelem; t++) {
    128 		if (strcmp(*t,s) == 0) {
    129 			memmove(t, t + 1,
    130 				(strnextelem - t + 1) * sizeof(char *));
    131 			strnextelem--;
    132 			return;
    133 		}
    134 	}
    135 }
    136 
    137 void
    138 isort(int (*cmp)(const void *a, const void *b))
    139 {
    140 	void **j;
    141 		
    142 	for (void **t = (void **) strbuf; t < (void **) strnextelem; t++) {
    143 		j = t - 1;
    144 		void *val = *t;
    145 		while ((j - (void **) strbuf) >= 0 && cmp(*j, val) > 0) {
    146 			*(j + 1)  = *j;
    147 			j--;
    148 		}
    149 		*(j + 1) = val;
    150 	}
    151 }
    152