Exercise 5-7 (readlines)

Chapter_5     Exercise_5-6     Exercise_5-6-10 Exercise_5-8





Exercise 5-7     K&R, p. 110


Exercise 5-7. Rewrite readlines() to store lines in an array supplied by main(), rather than calling alloc() to maintain storage. How much faster is the program?




CONTENTS:     lines1.c     lines2.c




lines1.c     K&R, p. 101-102, 108-110         download


#include <stdio.h> // for getchar(), printf(), EOF, NULL, FILE, fopen(), fclose()
#include <string.h> // for strcpy(), strcmp()
#include <time.h> // for clock_t, clock(), CLOCKS_PER_SEC

#define MAXLINES 20000 // max no of lines to be sorted
#define MAXLEN 100 // max line length

int readlines (char *lineptr[], int nlines);
void writelines (char *lineptr[], int nlines, char *filename);

void qSort(char *lineptr[], int left, int right); // qsort() is declared by stdlib.h

int main()
{
char *lineptr[MAXLINES];

int nlines; // no of input lines read

clock_t start, end;
double time;

start = clock();
if ((nlines = readlines(lineptr, MAXLINES)) >= 0)
{
qSort(lineptr, 0, nlines-1);
writelines(lineptr, nlines, "sorted1.txt");
}
else
{
printf("Error: input too big to sort\n");
return 1; // exit program, signalling error
}
end = clock();
time = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("(1) Execution time: %f\n", time);

return 0;
}

int getLine(char *, int); // getline() is declared in stdio.h
char* alloc(int); // allocate storage

int readlines (char *lineptr[], int maxlines) // read input lines
{
int len, nlines;
char *p, line[MAXLEN];

nlines = 0;
while ((len = getLine(line, MAXLEN)) > 0)
{
if(nlines >= maxlines || (p = alloc(len+1)) == NULL)
{return -1;} // len+1 for ending '\0'
else
{
strcpy(p, line);
lineptr[nlines++] = p;
}
}

return nlines;
}

int getLine(char *s, int lim)
{
int c = EOF; // initialize
char *p;
// getchar() is only executed if ((p-s) < (lim-1)):
for (p = s; (p-s) < (lim-1) && (c = getchar()) != EOF && c != '\n'; p++)
{ // from 0 to lim-2; s[lim-2]='\n', s[lim-1]='\0'
*p = c;
}
if (c == '\n')
{*p++ = c;}

*p = '\0'; // the null character ends a string

return p-s; // max(p-s) == (lim-1)
}

#define ALLOCSIZE (MAXLINES * MAXLEN)

static char allocbuf[ALLOCSIZE]; // storage for alloc()
static char *allocp = allocbuf; // next free position

char* alloc(int n) // return pointer to n chars
{
if (allocbuf + ALLOCSIZE - allocp >= n) // it fits
{
allocp += n;
return allocp-n; // old pointer
}
else {return 0;} // null pointer
}
void afree(char *p) // free storage pointed to by p
{
if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
{allocp = p;}
}

void writelines (char *lineptr[], int nlines, char *filename) // write output lines
{
FILE *f = fopen(filename, "w"); // open for writing

while (nlines-- > 0)
{fprintf(f, "%s", *lineptr++);}

fclose(f);
}

void swap(char *v[], int i, int j); // interchange v[i], v[j]

// sort v[left] ... v[right] into increasing order
void qSort(char *v[], int left, int right) // qsort() in declared in stdlib.h
{
int i, last;

if (left >= right) // do nothing if array contains fewer than 2 elements
{return;} // stopping condition for recursion

swap(v, left, (left + right) / 2); // move partition element to v[left]
last = left; // start moving elements to last position
for (i = left + 1; i <= right; i++)
{
if (strcmp(v[i], v[left]) < 0) // v[i] < v[left]
{swap(v, ++last, i);} // smaller to the left, bigger to the right
}

swap(v, left, last); // return partition element to the middle position
qSort(v, left, last-1); // sort smaller elements
qSort(v, last+1, right); // sort bigger elements
}

void swap(char *v[], int i, int j) // interchange v[i], v[j]
{
char *temp;

temp = v[i]; // swap pointers
v[i] = v[j];
v[j] = temp;
}

/*
gcc lines1.c -o lines1
./lines1 < me.txt
(1) Execution time: 0.055364
*/









lines2.c         download


#include <stdio.h> // for getchar(), printf(), EOF, NULL, FILE, fopen(), fclose()
#include <string.h> // for strcpy(), strcmp()
#include <time.h> // for clock_t, clock(), CLOCKS_PER_SEC

#define MAXLINES 20000 // max no of lines to be sorted
#define MAXLEN 100 // max line length

int readlines (char lines[][MAXLEN], int nlines);
void writelines (char *lineptr[], int nlines, char *filename);

void qSort(char *lineptr[], int left, int right); // qsort() is declared by stdlib.h

int main()
{
char *lineptr[MAXLINES];
char lines[MAXLINES][MAXLEN];

int i, nlines; // no of input lines read

clock_t start, end;
double time;

start = clock();
if ((nlines = readlines(lines, MAXLINES)) >= 0)
{
for (i = 0; i < nlines; i++)
{lineptr[i] = lines[i];}
qSort(lineptr, 0, nlines-1);
writelines(lineptr, nlines, "sorted2.txt");
}
else
{
printf("Error: input too big to sort\n");
return 1; // exit program, signalling error
}
end = clock();
time = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("(2) Execution time: %f\n", time);

return 0;
}

int getLine(char *, int); // getline() is declared in stdio.h

int readlines (char lines[][MAXLEN], int maxlines) // read input lines
{
int nlines = 0;

while (getLine(lines[nlines], MAXLEN) > 0)
{
nlines++;
if(nlines >= maxlines)
{return -1;}
}

return nlines;
}

int getLine(char *s, int lim)
{
int c = EOF; // initialize
char *p;
// getchar() is only executed if ((p-s) < (lim-1)):
for (p = s; (p-s) < (lim-1) && (c = getchar()) != EOF && c != '\n'; p++)
{ // from 0 to lim-2; s[lim-2]='\n', s[lim-1]='\0'
*p = c;
}
if (c == '\n')
{*p++ = c;}

*p = '\0'; // the null character ends a string

return p-s; // max(p-s) == (lim-1)
}

void writelines (char *lineptr[], int nlines, char *filename) // write output lines
{
FILE *f = fopen(filename, "w"); // ope for writing

while (nlines-- > 0)
{fprintf(f, "%s", *lineptr++);}

fclose(f);
}

void swap(char *v[], int i, int j); // interchange v[i], v[j]

// sort v[left] ... v[right] into increasing order
void qSort(char *v[], int left, int right) // qsort() in declared in stdlib.h
{
int i, last;

if (left >= right) // do nothing if array contains fewer than 2 elements
{return;} // stopping condition for recursion

swap(v, left, (left + right) / 2); // move partition element to v[left]
last = left; // start moving elements to last position
for (i = left + 1; i <= right; i++)
{
if (strcmp(v[i], v[left]) < 0) // v[i] < v[left]
{swap(v, ++last, i);} // smaller to the left, bigger to the right
}

swap(v, left, last); // return partition element to the middle position
qSort(v, left, last-1); // sort smaller elements
qSort(v, last+1, right); // sort bigger elements
}

void swap(char *v[], int i, int j) // interchange v[i], v[j]
{
char *temp;

temp = v[i]; // swap pointers
v[i] = v[j];
v[j] = temp;
}

/*
gcc lines2.c -o lines2
./lines2 < me.txt
(2) Execution time: 0.043825

diff -s sorted1.txt sorted2.txt
Files sorted1.txt and sorted2.txt are identical

meld sorted1.txt sorted2.txt // Files are identical

rm sorted* // clean
*/





Notes:

For the contents of text file me.txt see Martin_Eden on Project_Gutenberg.
Redefine MAXLINES and MAXLEN if you use other input file.
getLine() should return after reading '\n' or EOF (upon reaching the end of file), otherwise it may need ungetch(), see Chapter_4, Sec. 4.3.







Chapter_5     Exercise_5-6     Exercise_5-6-10 BACK_TO_TOP Exercise_5-8



Comments

Post a Comment

Popular posts from this blog

Contents

Programming_Languages_blog     C_Prog_blogs Chapter_1     Advanced_Linux_Prog     C_in_C++ NAVIGATION     CHAPTERS     CONTENTS     EXERCISES     INDEX     ABOUT     CONTACT Chapter_1  (Introduction) Hello     Exercise_1-1     Exercise_1-2     quotes     Temperature_Programs     Truncate     Exercise_1-3     Exercise_1-4     for()_variant     Exercise_1-5     #define_directive     copy     Exercise_1-6     Exercise_1-7     copyEOF     count     Exercise_1-8     Exercise_1-9 ...
Read more

Blogger Page Margins in Contempo

NAVIGATION     CHAPTERS     CONTENTS     EXERCISES     INDEX     ABOUT     CONTACT Navigate Blogger left panel   →   Theme   →   CUSTOMIZE drop-down menu   →   Edit HTML CONTENTS:     Left_Margin     Right_Margin     Page_Content_Fills_the_Screen Left Margin No Left Margin .centered-bottom,.centered-top-container,.centered-top-placeholder{ padding:0 0px } Original CSS .centered-bottom,.centered-top-container,.centered-top-placeholder{ padding:0 16px } Right Margin No Right Margin (No Vertical Ads on blog) .vertical-ad-container { float: right; margin-right: 0px; width: 0px; } .page_body.has-vertical-ads .centered .centered-bottom { display: inline-block; width: calc(100% - 0px); } Original CSS .vertical-ad-contain...
Read more