7
\$\begingroup\$

Since train rides can be long and boring, I've decided to make use of that time and fiddle around with some good ol' C.

What I did was to create a way to enumerate words of a certain length of an arbitrary alphabet. Basically, suppose you have an alphabet

{ '0', '1' }

(ooh, binary!) and want to get all words of length 7, you'd call

enumerate("01", 7);

and have a nice array of pointers containing the strings "0000000" to "1111111". What for, you ask? Dunno. Stuff.

I've written it on my phone, so it may be a tad slimmer than the usual 80 characters. It's also not split into files for the very same reason.

#include <math.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *translate(
  unsigned long value,
  const char *alphabet,
  size_t length
) {
  size_t base;
  char *result;

  if (!alphabet || (base = strlen(alphabet)) < 2) {
    return NULL;
  }

  if (length == 0) {
    length = 1 + floor(log(value) / log(base));
  }

  result = malloc(length + 1);

  if (!result) {
    return NULL;
  }

  memset(result, alphabet[0], length);
  result[length] = 0;

  for (int i = length - 1; i >= 0 && value > 0; --i) {
    unsigned long mod = value % base;
    result[i] = alphabet[mod];

    value -= mod;
    value /= base;
  }

  return result;
}

char **enumerate(
  const char *alphabet,
  const size_t length
) {
  size_t base;

  if (!alphabet || (base = strlen(alphabet)) < 2) {
    return NULL;
  }

  if (length == 0) {
    return NULL;
  }

  unsigned long end = pow(base, length);
  char **array = malloc((end + 1) * sizeof(char*));

  if (!array) {
    return NULL;
  }

  array[end] = NULL;

  for (int i = 0; i != end; ++i) {
    char *storage = malloc(length + 1);
    char *translated = translate(i, alphabet, length);

    if (!storage || !translated) {
      if (storage) {
        free(storage);
      }

      if (translated) {
        free(translated);
      }

      array[i] = NULL;
      goto error_cleanup;
    }

    strcpy(storage, translated);
    free(translated);
    array[i] = storage;
  }

  return array;


  error_cleanup:

  for (int i = 0; array[i] != NULL; ++i) {
    free(array[i]);
  }

  free(array);
  return NULL;
}

Example usage; simply concatenate the listings.

int main(int argc, char *argv[]) {
  if (argc < 2) {
    printf("Usage: %s <length> <alphabet>",
          argv[0]);
    exit(0);
  }

  size_t length = atoi(argv[1]);
  char *alphabet = argv[2];

  char **array = enumerate(alphabet, length);

  if (!array) {
    printf("Error while enumerating.");
    exit(1);
  }

  for (int i = 0; array[i] != NULL; ++i) {
    printf("%s\n", array[i]);

    free(array[i]);
  }

  free(array);
  exit(0);
}

What I'm most concerned about is idiomaticality (is that even a word?) of the code, since my C is rusty and self-taught, especially concerning the use of that string array. Also, is my goto used well and with good reason?

\$\endgroup\$
  • \$\begingroup\$ Oh wow, after taking a step back, I see some strange types used. Particularly, in for (int i = 0; i != end; ++i), i should have the same type as end, unsigned long. I blame it on the shaky ride and the small screen! \$\endgroup\$ – Phil Kiener Apr 1 '17 at 16:02
  • \$\begingroup\$ Apparently, some parts got swallowed by copying and pasting. I hope you don't mind me having edited them back in. \$\endgroup\$ – Phil Kiener Apr 1 '17 at 16:36
2
\$\begingroup\$
  1. If you want to improve usability, you should introduce some kind of type for your array (typedef the pointer, or introduce some type of struct that will contain useful metadata) and provide the appropriate free function for it. This way, the user doesn't have to free all the elements themselves and can just call my_free(&my_type_ptr) when he's done. Your error_cleanup should just call this function as well.
  2. This bit of code does unnecessary work:

    char *storage = malloc(length + 1);
    char *translated = translate(i, alphabet, length);
    
    if (!storage || !translated) {
      if (storage) {
        free(storage);
      }
    
      if (translated) {
        free(translated);
      }
    
      array[i] = NULL;
      goto error_cleanup;
    }
    
    strcpy(storage, translated);
    free(translated);
    array[i] = storage;
    

    in the form of allocating an extra block of memory and copying things there from an already allocated block of memory. Simplify to:

    array[i] = translate(i, alphabet, length);
    if (array[i] == NULL) {
        // Error in translating, abort
        goto error_cleanup;
    }
    
  3. is my goto used well and with good reason?

    No. You only have one user of the goto. If you look above at the more concise version of your function, it's completely reasonable just to say "no more goto" and replace it with free_word_array(array); return NULL;. Any time you have a need to clean multiple resources on any failure, goto can be a good choice.

  4. (argc < 2) needs to be (argc < 3). As it is written, running your program with only one extra argument ./main 6 results in Error while enumerating. instead of printing the help message. Remember, the program invocation is the 0th argument but counts in the count as well.

  5. I prefer return from main rather than exit.

  6. translate could use more comments within the algorithm, for quicker reading/understanding. It looks like you're just enumerating all possible words within a given set, and this recovers the word.

  7. Maybe it makes sense not to have an array of arrays, but rather an array of numbers that you then convert to the string representation if the user wants to print it? But then the logical conclusion of that is that you don't really need to allocate memory at all then: you can just as easily return the number of permutations, and work out the appropriate requested permutation when it is requested.

  8. Your code will only work with single-wide characters, and produce gibberish for any alphabet that contains characters that aren't (think UTF-8, for instance, where the character can be wider than a byte, meaning that you'll shuffle the character incorrectly). This might not be in your requirements, but thought I'd mention it since this always plagues non-ASCII character stuff in C.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback! Regarding the second point... I guess I simply overlooked the redundancy of that code on the tiny display. Your first, third and seventh point together sparked an idea in my head... maybe I'll implement that one some time. As for your fourth point... guess that simply was a typo, duh. I myself prefer exit to return, since it clearly states that the program completely terminates here. For your eigth point; if I implement my aforementioned idea, I might take unicode into consideration. It's a thing I mostly don't care about in small toy programs. :D \$\endgroup\$ – Phil Kiener Apr 7 '17 at 1:14
  • \$\begingroup\$ I've had some time to think about it, and for a performant system I'd probably just spit out the number of possible permutations that let the caller iterate over any of them (or directly access any word within that range). For the printing and actual text representation, I'd require a buffer of the same size to be passed in. This removes all the free/malloc calls from your code, but does mean the print calls have more overhead (which would have been in the generation step within your code). \$\endgroup\$ – russianfool Apr 8 '17 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.