title: Pthreads and recursion
body: <p>I'm struggling with one of my training tasks for getting in touch with a new language. Unfortunately, this time the new language is an old one, it is C. My programming Task for this is to generate Langford-Strings, which should not be the main problem. </p>
  
  <p>My first attempt in C, with a recursive approach works like a charm:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  
  int grade = 0;
  const char* blank = "_";
  const char* alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  
  void generate(int position, char* string) {
  
    if (!string) {
      string = calloc(grade*2+1, sizeof(char));
      for (int i = 0; i &lt; grade*2; i++) {
        string = strcat(string, blank);
      }
    }
  
    if (!strstr(string, blank)) {
      printf("%s\n", string);
      return;
    }
  
    if (position &lt; strlen(string)) {
      if (string[position] != *blank) {
        char* nstring = calloc(grade*2+1, sizeof(char));
        strcpy(nstring, string);
        generate(position+1, nstring);
        free(nstring);
        return;
      } else {
        for (int i = 0; i&lt;strlen(string); i++) {
          if (strchr(string, alphabet[i])){
            continue;
          }
  
          int index = strcspn(alphabet, &amp;alphabet[i])+1;
          if (position+index+1&lt;strlen(string)) {
            if (string[position]==*blank) {
              if (string[position+index+1]==*blank) {
                char* nstring = calloc(grade*2+1, sizeof(char));
                strncat(nstring, string, position);
                strncat(nstring, &amp;alphabet[i], 1);
                strncat(nstring, &amp;string[position+1], index);
                strncat(nstring, &amp;alphabet[i], 1);
                strcat(nstring, &amp;string[position+2+index]);
                if (position&lt;strlen(nstring)) {
                  generate(position+1, nstring);
                }
                free(nstring);
              }
            }
          }
        }
      }
    }
  }
  
  int main(int argc, char* argv[]) {
    if (argc &lt; 2) {
      printf("Missing parameter of langford strings grade!\n");
      return 1;
    }
  
    grade = strtol(argv[1], NULL, 10);
    if (grade % 4 != 0) {
      if ((grade+1) % 4 != 0) {
        printf("Grade must be multiple of 4 or one less\n");
        return 1;
      }
    }
  
    generate(0, NULL);
    return 0;
  }
  </code></pre>
  
  <p>That works great, giving me exactly the results I expected.</p>
  
  <p>But when I try to do it threaded (old-style threaded, spawning a new thread on each level of the recursion), it not only ends with a seqfault every time. It does end in an seqfault in a not predictable time. That means, that it runs indefinitly, printing out doubled and trippled results and always a random number of results, before seqfaulting.</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  #include &lt;pthread.h&gt;
  #include &lt;signal.h&gt;
  #include &lt;errno.h&gt;
  
  size_t grade = 0;
  const char* blank = "_";
  const char* alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  
  struct thread {
    pthread_t* thread;
    size_t position;
    struct thread* threads[26];
    char* string;
  };
  
  void* alloc_thread_data() {
    struct thread* ret = calloc(1, sizeof(struct thread));
    ret-&gt;thread = calloc(1, sizeof(pthread_t));
    ret-&gt;position = 0;
    ret-&gt;string = calloc((grade*2)+1, sizeof(char));
    return (void*)ret;
  }
  
  void free_thread_data(struct thread* dst) {
    free(dst-&gt;string);
    free(dst-&gt;thread);
    free(dst);
  }
  
  void assemble_string(char* dst, char* src, size_t pos, size_t index) {
    strncat(dst, src, pos);
    strncat(dst, &amp;alphabet[index-1], 1);
    strncat(dst, &amp;src[pos+1], index);
    strncat(dst, &amp;alphabet[index-1], 1);
    strncat(dst, &amp;src[pos+2+index], (grade*2)-pos+index+2);
  }
  
  void* generate(void* data) {
    struct thread* args = (struct thread*)data;
  
    if (args-&gt;string &amp;&amp; strlen(args-&gt;string)==0) {
      for (size_t i = 0; i&lt;grade*2; i++) {
        strcat(args-&gt;string, blank);
      }
    }
  
    if (args-&gt;string &amp;&amp; !strstr(args-&gt;string, blank)) {
      printf("%s\n", args-&gt;string);
      return NULL;
    }
  
    if (args-&gt;string &amp;&amp; args-&gt;position&lt;strlen(args-&gt;string)) {
      size_t sub = 0;
      if (args-&gt;string[args-&gt;position]!=*blank) {
        args-&gt;threads[sub] = alloc_thread_data();
        strcpy(args-&gt;threads[sub]-&gt;string, args-&gt;string);
        args-&gt;threads[sub]-&gt;position = args-&gt;position+1;
        pthread_create(args-&gt;threads[sub]-&gt;thread, NULL, generate, (void*)args-&gt;threads[sub]);
        sub++;
      } else {
        for (size_t i = 0; i&lt;grade*2; i++) {
          if (strchr(args-&gt;string, alphabet[i])){
            continue;
          }
  
          int index = strcspn(alphabet, &amp;alphabet[i])+1;
          if (args-&gt;string[args-&gt;position] == *blank) {
            if (args-&gt;string[args-&gt;position+index+1] == *blank) {
              args-&gt;threads[sub] = alloc_thread_data();
              assemble_string(args-&gt;threads[sub]-&gt;string, args-&gt;string, args-&gt;position, index);
              args-&gt;threads[sub]-&gt;position = args-&gt;position+1;
              pthread_create(args-&gt;threads[sub]-&gt;thread, NULL, generate, (void*)args-&gt;threads[sub]);
              sub++;
            }
          }
        }
      }
  
      for (size_t i = 0; i&lt;sub; i++) {
        if (args-&gt;threads[i]-&gt;thread!=NULL) {
          if(pthread_kill(*args-&gt;threads[i]-&gt;thread, 0)==0) {
            pthread_join(*args-&gt;threads[i]-&gt;thread, NULL);
          }
  
          free_thread_data(args-&gt;threads[i]);
        }
      }
    }
  
    return NULL;
  }
  
  int main(int argc, char* argv[]) {
    if (argc &lt; 2) {
      printf("Missing parameter of langford strings grade!\n");
      return 1;
    }
  
    grade = strtol(argv[1], NULL, 10);
    if (grade % 4 != 0) {
      if ((grade+1) % 4 != 0) {
        printf("Grade must be multiple of 4 or one less\n");
        return 2;
      }
    }
  
    struct thread* args = alloc_thread_data();
    pthread_create(args-&gt;thread, NULL, generate, (void*)args);
    if(pthread_kill(*args-&gt;thread, 0)==0) {
      pthread_join(*args-&gt;thread, NULL);
    }
  
    free_thread_data(args);
  }
  </code></pre>
  
  <p>So, as written before, I managed to get around C programming for my whole work-life and do this just for fun - so I do not expect my code to be somewhat comprehensive. Please help me finding out, what is wrong with the threaded approach (and if you see any well-known-codesmell in the first one as well of course). Any hints welcome.</p>