title: Use heap storage instead of stack (K&R 5.7)
body: <p>I have a program that sorts input lines lexicographically, and I've come to this exercise in K&amp;R:</p>
  
  <blockquote>
    <p>Rewrite readlines to store lines in an array supplied by main, rather than calling alloc to maintain storage. How much faster is the program?</p>
  </blockquote>
  
  <p>Here is the original program, using <code>malloc</code> to maintain storage for lines.</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  
  #define MAXLINES 5000
  
  char *lineptr[MAXLINES];
  
  int readlines(char *lineptr[], int nlines);
  void writelines(char *lineptr[], int nlines);
  
  void qsort(char *lineptr[], int left, int right);
  
  char *alloc(int n);
  
  #define MAXSIZE 10000
  int main(int argc, char *argv[])
  {
       int nlines;
  
       if((nlines = readlines(lineptr, MAXLINES)) &gt;= 0) {
            qsort(lineptr, 0, nlines-1);
            writelines(lineptr, nlines);
            getchar();
            return 0;
       } 
       else {
            printf("error: input too big to sort\n");
            getchar();
            return 1;
       }
  
  }
  
  
  #define MAXLEN 1000
  int getline(char *, int);
  
  int readlines(char *lineptr[], int maxlines)
  {
      int len, nlines;
      char *p;
      char line[MAXLEN];
  
      nlines = 0;
      while((len = getline(line, MAXLEN)) &gt; 0)
         if(nlines &gt;= maxlines || (p = alloc(len)) == NULL)
            return -1;
         else {
              line[len-1] = '\0';
              strcpy(p, line);
              lineptr[nlines++] = p;
         }
  
      return nlines;
  }
  
  void writelines(char *lineptr[], int nlines)
  {
       while(nlines-- &gt; 0)
           printf("%s\n", *lineptr++);
  }
  
  #define MAXALLOC 5000
  char allocbuf[MAXALLOC];
  char *allocp = allocbuf;
  
  char *alloc(int n)
  {
       if(allocbuf + MAXALLOC - allocp &gt;= n) {
          allocp += n;
          return allocp - n;
       }
       else
           return 0;
  }
  
  int getline(char s[], int lim)
  {
    int c, i;
  
    for (i = 0; i &lt; lim - 1 &amp;&amp; (c = getchar()) != EOF &amp;&amp; c != '\n'; i++)
      s[i] = c;                                                         
    if (c == '\n') {
      s[i++] = c;   
    }
    s[i] = '\0';
    return i;
  }
  
  void swap(char *v[], int i, int j)
  {
       char *temp;
  
       temp = v[i];
       v[i] = v[j];
       v[j] = temp;
  }
  
  void qsort(char *v[], int left, int right) {
  
      int i, last;
  
      if(left &gt;= right) 
         return;
  
      swap(v, left, (left+right)/2);
      last = left;
  
      for(i = left + 1; i &lt;= right; i++)
        if(strcmp(v[i], v[left]) &lt; 0)
           swap(v, ++last, i);
  
      swap(v, left, last);
      qsort(v, left, last-1);
      qsort(v, last+1, right);
  }
  </code></pre>
  
  <p>I edited it this way:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  
  #define MAXLINES 5000
  
  char *lineptr[MAXLINES];
  
  int readlines(char *lineptr[], int nlines, char buf[]);
  void writelines(char *lineptr[], int nlines);
  
  void qsort(char *lineptr[], int left, int right);
  
  #define MAXSIZE 10000
  int main(int argc, char *argv[])
  {
       int nlines;
       char buf[MAXSIZE];
  
       if((nlines = readlines(lineptr, MAXLINES, buf)) &gt;= 0) {
            qsort(lineptr, 0, nlines-1);
            writelines(lineptr, nlines);
            getchar();
            return 0;
       } 
       else {
            printf("error: input too big to sort\n");
            getchar();
            return 1;
       }
  }
  
  #define MAXLEN 1000
  int getline(char *, int);
  
  int readlines(char *lineptr[], int maxlines, char buf[])
  {
      int len, nlines;
      char *p = buf;
      char line[MAXLEN];
  
      nlines = 0;
      while((len = getline(line, MAXLEN)) &gt; 0)
         if(nlines &gt;= maxlines || MAXSIZE + buf - p &lt; len)
            return -1;
         else {
              line[len-1] = '\0';
              strcpy(p, line);
              lineptr[nlines++] = p;
              p+=len;
         }
  
      return nlines;
  }
  
  void writelines(char *lineptr[], int nlines)
  {
       while(nlines-- &gt; 0)
           printf("%s\n", *lineptr++);
  }
  
  int getline(char s[], int lim)
  {
    int c, i;
  
    for (i = 0; i &lt; lim - 1 &amp;&amp; (c = getchar()) != EOF &amp;&amp; c != '\n'; i++)
      s[i] = c;                                                         
    if (c == '\n') {
      s[i++] = c;   
    }
    s[i] = '\0';
    return i;
  }
  
  void swap(char *v[], int i, int j)
  {
       char *temp;
       temp = v[i];
       v[i] = v[j];
       v[j] = temp;
  }
  
  void qsort(char *v[], int left, int right) {
      int i, last;
  
      if(left &gt;= right) 
         return;
  
      swap(v, left, (left+right)/2);
      last = left;
  
      for(i = left + 1; i &lt;= right; i++)
        if(strcmp(v[i], v[left]) &lt; 0)
           swap(v, ++last, i);
  
      swap(v, left, last);
      qsort(v, left, last-1);
      qsort(v, last+1, right);
  }
  </code></pre>
  
  <p>Is this what the author wanted, or did I do it wrong?</p>
  
  <p>Also, measuring time diffrence, is it correct to just start the clock at the begining of the main and then stop it after reading lines is over, and compare the time taken?</p>
  
  <hr>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  
  #define MAXLINES 5000
  
  char *lineptr[MAXLINES];
  
  int readlines(char *lineptr[], int nlines);
  void writelines(char *lineptr[], int nlines);
  
  void qsort(char *lineptr[], int left, int right);
  
  char *alloc(int n);
  
  #define MAXSIZE 10000
  int main(int argc, char *argv[])
  {
       int nlines;
  
       if((nlines = readlines(lineptr, MAXLINES)) &gt;= 0) {
            qsort(lineptr, 0, nlines-1);
            writelines(lineptr, nlines);
            getchar();
            return 0;
       } 
       else {
            printf("error: input too big to sort\n");
            getchar();
            return 1;
       }
  
  }
  
  
  #define MAXLEN 1000
  int getline(char *, int);
  
  int readlines(char *lineptr[], int maxlines)
  {
      int len, nlines;
      char *p;
      char line[MAXLEN];
  
      nlines = 0;
      while((len = getline(line, MAXLEN)) &gt; 0)
         if(nlines &gt;= maxlines || (p = alloc(len)) == NULL)
            return -1;
         else {
              line[len-1] = '\0';
              strcpy(p, line);
              lineptr[nlines++] = p;
         }
  
      return nlines;
  }
  
  void writelines(char *lineptr[], int nlines)
  {
       while(nlines-- &gt; 0)
           printf("%s\n", *lineptr++);
  }
  
  #define MAXALLOC 5000
  char allocbuf[MAXALLOC];
  char *allocp = allocbuf;
  
  char *alloc(int n)
  {
       if(allocbuf + MAXALLOC - allocp &gt;= n) {
          allocp += n;
          return allocp - n;
       }
       else
           return 0;
  }
  
  int getline(char s[], int lim)
  {
    int c, i;
  
    for (i = 0; i &lt; lim - 1 &amp;&amp; (c = getchar()) != EOF &amp;&amp; c != '\n'; i++)
      s[i] = c;                                                         
    if (c == '\n') {
      s[i++] = c;   
    }
    s[i] = '\0';
    return i;
  }
  
  void swap(char *v[], int i, int j)
  {
       char *temp;
  
       temp = v[i];
       v[i] = v[j];
       v[j] = temp;
  }
  
  void qsort(char *v[], int left, int right) {
  
      int i, last;
  
      if(left &gt;= right) 
         return;
  
      swap(v, left, (left+right)/2);
      last = left;
  
      for(i = left + 1; i &lt;= right; i++)
        if(strcmp(v[i], v[left]) &lt; 0)
           swap(v, ++last, i);
  
      swap(v, left, last);
      qsort(v, left, last-1);
      qsort(v, last+1, right);
  }
  </code></pre>
  
  <p>This is the original code.</p>