Enumerating an alphabet

Question

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?

Answer 1

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.