3
\$\begingroup\$

I wrote a small program that initializes a 3D array in C based on command-line arguments and prints it. I did my best to avoid undefined behavior and memory errors. I wrote comments as if I had an exported API. I don’t know if “owns” is standard terminology, I use it here to mean that a function is responsible for freeing these resources if it exits the program.

#include <ctype.h>
#include <errno.h>
#include <inttypes.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

// Unless specified otherwise, all functions have the implicit precondition of
// all their arguments being defined. Unless specified otherwise, all functions
// taking pointers have the implicit precondition that these pointers are valid,
// and their pointees, if they are pointers, also satisfy the property the
// argument itself satisfies. If an effect is not qualified by "may" or does not
// express a mere possibility, it is guaranteed.

// Element of our array
typedef unsigned long elem;

// Report number of successful allocations
// - Argument allocs: number of allocations to report
// - Returns: if printing was successful
// - Effects: Prints to stdout, may print to stderr
bool print_allocs(size_t allocs) {
    if (printf("successfully allocated %zu times\n", allocs) < 0) {
        perror("value output");
        return false;
    }
    return true;
}

// Parse argument to size_t
// - Argument argno: argument index in argv
// - Argument argid: argument name to be printed
// - Argument argv: argument array
// - Returns: parsed argument as size_t
// - Preconditions:
// + argv[argno] is defined
// + argid is nul-terminated
// - Effects: May exit program, may print to stderr
size_t get_arg_size_t(int argno, char *argid, char **argv) {
    char *arg = argv[argno];
    char *argptrcpy = arg;
    while (isspace(*argptrcpy))
        argptrcpy++;
    if (*argptrcpy == '-') {
        fprintf(stderr, "argument %s must be positive\n", argid);
        exit(EXIT_FAILURE);
    }
    char *endptr;
    errno = 0;
    uintmax_t val = strtoumax(arg, &endptr, 10);
    if (arg[0] == '\0' || *endptr != '\0') {
        fprintf(stderr, "failed to parse argument %s\n", argid);
        exit(EXIT_FAILURE);
    }
    if (errno == ERANGE || val > SIZE_MAX) {
        fprintf(stderr, "argument %s is too large\n", argid);
        exit(EXIT_FAILURE);
    }
    return (size_t)val;
}

// Free array and subarrays, and exit
// - Argument arr: array to free
// - Argument x: size of arr
// - Argument y: size of elements of arr
// - Argument i: index of latest element of arr for which allocation has begun,
// or x if allocation is finished
// - Argument j: index of latest element of arr[i] for which allocation has
// begun, or y if allocation is finished
// - Argument ecode: exit code with which to exit
// - Preconditions:
// + (1) For all i_ < i, arr[i_] is allocated
// + (2) For all i_ < i, j_ < y, arr[i_][j_] is defined
// + (3) For all j_ < j, arr[i][j_] is defined
// + arr is allocated
// - Correctness conditions:
// + In (1), these are the only such i_
// + In (2), these are the only such i_, j_
// + In (3), these are the only such j_
// - Owns:
// + arr
// + arr[i_] for i_ in (1)
// + arr[i_][j_] for i_, j_ in (2)
// + arr[i][j_] for j_ in (3)
// - Effects: frees all elem values in arr, exits program
void free_and_exit(elem ***arr, size_t x, size_t y, size_t i, size_t j,
                   int ecode) {
    for (size_t i_ = 0; i_ < i; i_++) {
        for (size_t j_ = 0; j_ < y; j_++)
            free(arr[i_][j_]);
        free(arr[i_]);
    }
    if (i < x) {
        for (size_t j_ = 0; j_ < j; j_++)
            free(arr[i][j_]);
        free(arr[i]);
    }
    free(arr);
    exit(ecode);
}

// Allocate and initialize 3D array
// - Argument x: desired size of first layer of array
// - Argument y: desired size of each second layer of array
// - Argument z: desired size of each third layer of array
// - Argument allocs: pointer to store allocation count
// - Effects: allocates, writes *allocs, may print to stderr, may exit program
elem ***mk_arr(size_t x, size_t y, size_t z, size_t *allocs) {
    *allocs = 0;
    elem ***arr = malloc(x * sizeof(elem **));
    if (arr == NULL) {
        perror("array allocation");
        print_allocs(*allocs);
        exit(EXIT_FAILURE);
    }
    ++*allocs;
    for (size_t i = 0; i < x; i++) {
        arr[i] = malloc(y * sizeof(elem *));
        if (arr[i] == NULL) {
            perror("array allocation");
            print_allocs(*allocs);
            free_and_exit(arr, x, y, i, 0, EXIT_FAILURE);
        }
        ++*allocs;
        for (size_t j = 0; j < y; j++) {
            arr[i][j] = malloc(z * sizeof(elem));
            if (arr[i][j] == NULL) {
                perror("array allocation");
                print_allocs(*allocs);
                free_and_exit(arr, x, y, i, j, EXIT_FAILURE);
            }
            ++*allocs;
            for (size_t k = 0; k < z; k++)
                arr[i][j][k] = pow(2, i) + pow(3, j) + pow(5, k);
        }
    }
    return arr;
}

// Check argument count, correct user, and exit
// - Argument argc: argument count
// - Argument argv: argument array
// - Preconditions: for all i < argc, argv[i] is defined and nul-terminated
// - Effects: may print to stderr, may exit program
void ensure_usage(int argc, char **argv) {
    if (argc != 4) {
        char *pname = argc == 0 ? "<program>" : argv[0];
        fprintf(stderr,
                "wrong usage!\n"
                "usage: %s <x> <y> <z>\n",
                pname);
        exit(EXIT_FAILURE);
    }
}

// Print elements of array
// - Argument arr: array to print
// - Argument x: size of arr
// - Argument y: size of elements of arr
// - Argument z: size of elements of elements of arr
// - Preconditions: for all i < x, j < y, k < z, arr[i][j][k] is defined
// - Owns:
// + arr
// + arr[i] for all i < x
// + arr[i][j] for all i < x, j < y
// - Effects: prints to stdout, may print to stderr, may exit program
void print_arr(elem ***arr, size_t x, size_t y, size_t z) {
    for (size_t i = 0; i < x; i++)
        for (size_t j = 0; j < y; j++)
            for (size_t k = 0; k < z; k++)
                if (printf("arr[%zu][%zu][%zu] = %lu\n", i, j, k,
                           arr[i][j][k]) < 0) {
                    perror("value output");
                    free_and_exit(arr, x, y, x, y, EXIT_FAILURE);
                }
}

int main(int argc, char **argv) {
    ensure_usage(argc, argv);
    size_t x = get_arg_size_t(1, "x", argv);
    size_t y = get_arg_size_t(2, "y", argv);
    size_t z = get_arg_size_t(3, "z", argv);
    size_t allocs;
    elem ***arr = mk_arr(x, y, z, &allocs);
    if (!print_allocs(allocs)) {
        perror("value output");
        free_and_exit(arr, x, y, x, y, EXIT_FAILURE);
    }
    print_arr(arr, x, y, z);
    free_and_exit(arr, x, y, x, y, EXIT_SUCCESS);
}
```
\$\endgroup\$
1
  • \$\begingroup\$ Not enough for an answer, but you seem to like comments (which is mostly a good thing), so get into the habit of using the doxygen conventions. \$\endgroup\$ Jul 17, 2023 at 12:32

3 Answers 3

6
\$\begingroup\$

Don’t Write “Three-Star Code”

This is the major issue. An array of pointers to pointers to pointers to arrays is just a terrible data structure, and you should never use it. It uses memory inefficiently. It requires three dereferences with poor locality, so they’re likely to cause cache misses. It requires a huge number of heap allocations and deallocations that are easy to get wrong.

If the rows and columns are a known constant size, you want a “rectangular” or “box-shaped” array of constant dimension. You can create one with a single call to the heap, or even automatically on the stack. Access to any of the elements takes constant time. The last dimension of the array can even grow, and keep all these advantages, allowing you to dynamically add rows to a two-dimensional array or layers to a three-dimensional one.

If your rows are so ragged that it wouldn’t be acceptable to allocate a maximum dimension for them, you have a sparse matrix, and would be better off using a sparse format.

In this instance, you have a very wordy comment to the effect of which indices are defined (excerpting)

// + (1) For all i_ < i, arr[i_] is allocated
// + (2) For all i_ < i, j_ < y, arr[i_][j_] is defined
// + (3) For all j_ < j, arr[i][j_] is defined

Where y is defined as some kind of fixed element size. This suggests that you flatten the array into a single linear array whose logical [i][j] indices can be converted into physical offsets and looked up in constant time. Just don’t store any of the missing elements. If it’s worth the effort, that will improve your code more than anything else. You can think of this as taking advantage of the structure of the array to make a perfect hash function.

If calculating and debugging the index expressions are too much math, at least consider whether you can set the first two dimensions of the array to a maximum size.

\$\endgroup\$
6
\$\begingroup\$

I mostly like your style, but I think the code is too complex for what it does right now. Instead of addressing the complexity by writing a lot of comments, look for ways to simplify the code so that it won't require so much commenting in the first place.

  • free_and_exit is complicated enough that it's a likely place for an off-by-one error—either in implementation or in usage. Instead of passing in the number of elements for which allocation has succeeded, you could just delete these two arguments and assume that pointers are either valid or NULL (take advantage of the fact that free(NULL) does nothing). Then, when you allocate the arrays of pointers, either use calloc instead of malloc, or set everything to NULL after malloc but before doing anything else.

  • free_and_exit does two unrelated things.

  • You're doing way more allocations than are necessary. Since the array has a regular shape, you can allocate all the elems with a single malloc, then access the element at (i, j, k) with array[i * m * n + j * n + k]. This is actually the usual way to do multi-dimensional arrays in C. If you have to use pointers to pointers (required by an assignment?), then you can do three allocations: first allocate the elems, then allocate an array of pointers and fill it, and finally allocate an array of pointers to pointers and fill it. This will simplify the freeing code as well (and let you remove the allocation counter).

  • get_arg_size_t(int argno, char *argid, char **argv) is a strange type signature when you're only using argv and argno once, to get a single argument. Why not get_arg_size_t(const char *arg, const char *arg_name)?

  • You use too many early frees and early exits. This is going to become a nightmare to maintain as your program grows. For example, imagine that you're managing not just an array, but also an open file and a buffer. If you continue to code in this style, it's going to be very difficult to ensure that every execution path is correct.

    Instead of doing that, you usually only want to exit in main or another one of your top-level functions. Functions which exist to manage a helper data structure should only do two things on error: ensure that things are in a consistent state matching the documentation, and pass the error to the caller. The error can be passed via a return value (e.g. NULL) or a pointer (e.g. int *error)—your choice.

    Then, in your main function, you can use this pattern:

    int main(int argc, char **argv) {
        int exit_status = EXIT_SUCCESS;
    
        A *a = a_acquire();
        if (a == NULL) {
            exit_status = EXIT_FAILURE;
            goto error_a;
        }
    
        B *b = b_acquire();
        if (b == NULL) {
            exit_status = EXIT_FAILURE;
            goto error_b;
        }
    
        do_stuff_with(a, b);
    
        b_release(b);
    
    error_b:
        a_release(a);
    
    error_a:
        return exit_status;
    }
    

And some comments on style:

  • The long comment at the beginning of the file tells me nothing that isn't obvious, and it's not entirely clear what you mean by "defined".

  • There's also no need to state that strings are null-terminated in the comments, since that's the default assumption for C strings.

  • I recommend you use braces around the body of every if, for, and while. Since you're already using the "one true brace style", this won't waste too much space, but it may prevent you from making a goto fail-style error in the future.

  • I find it a bit confusing that x, y, z are sizes. Usually, people use l, m, n for sizes, i, j, k for indices, and x, y, z for coordinates.

  • If you want to add more operations to your 3D arrays, you could make the API for them a bit nicer by using a struct to wrap the things you're usually passing together anyway, using an enum of possible errors, and naming things with a consistent prefix:

    typedef unsigned long arr3_elem;
    
    typedef struct {
        arr3_elem *data;
        size_t l;
        size_t m;
        site_t n;
    } arr3;
    
    typedef enum {
        ARR3_S_OK,
        ARR3_S_ALLOC,
        ARR3_S_IO
    } arr3_status;
    
    arr3 arr3_create(size_t l, size_t m, size_t n, arr3_status *error);
    // or
    arr3_status arr3_create(arr3 *arr, size_t l, size_t m, size_t n);
    
    void arr3_destroy(arr3 arr);
    
    void arr3_print(arr3 arr, arr3_status *error);
    // or
    arr3_status arr3_print(arr3 arr);
    

I disagree with the other answer that suggests ++i instead of i++. They're going to compile to the same thing, and I find i++ a tiny bit easier to read.

\$\endgroup\$
4
\$\begingroup\$

This comment:

// Unless specified otherwise, all functions have the implicit precondition of
// all their arguments being defined. Unless specified otherwise, all functions
// taking pointers have the implicit precondition that these pointers are valid,
// and their pointees, if they are pointers, also satisfy the property the
// argument itself satisfies. If an effect is not qualified by "may" or does not
// express a mere possibility, it is guaranteed.

is.. litigious, and only serves to muddy the waters. What does an argument being "defined" mean? How could it ever not be defined? This should probably just be deleted.

printf is one of the very few calls where it's basically always OK to ignore the return value and assume success. Once error checking for this is gone, code like print_allocs can go away and that printf can just be inlined.

You need to use more const, for example in the arguments argid and argv to get_arg_size_t.

The integer parsing in get_arg_size_t is a little gross. The API doesn't make this easy (allowing strtou* to blindly negate-wrap an unsigned integer is nonsense), but there are easier ways. One such way is to call strtoimax instead, and if the resulting value is negative, bail. Then you don't have to consume the whitespace or negative sign yourself. You lose half of the range, which - on what will usually be 63 bits - means that you can only allocate ten to the power of

$$ 63 \frac {\ln 2} {\ln 10} \approx 19 $$

elements per axis. Let me know when you have that much memory.

free_and_exit is a little awkward. For a program of this size and complexity, it's pretty OK to just exit normally without freeing anything, because it's single-use and the free is implied by program exit. If you wanted to make a reusable module, this is still a little awkward, because you need to decouple the free from the exit. Generally, being exit()-happy leads to non-reusable (non-reentrant) code. Especially for the happy path, but also just generally, you should be returning from main and not exiting unless something has gone catastrophically wrong and you can't allow a normal stack unwind.

In print_arr, only enclosing the inner-most loop in braces is probably not a good idea; mostly it's just visually jarring. I'm not militant when it comes to requiring braces around everything, but generally if there are braces around an inner block there should be braces around all of the blocks above it.

Prefer pre-increment ++i over post-increment i++ whenever possible. There are many reasons for this, including that the execution model is simpler, especially in different lands (C++ with iterators, for instance). There's nothing here that will make a functional or performance difference, but it's a habit to get into.

C allows for an implicit return 0 but I don't like the inconsistency and recommend that that be included explicitly.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ While it's extremely common to ignore the return value of printf(), it's actually not OK, unless it's printing an error to stderr. If you can't write the expected results correctly to stdout (which might be redirect to a file and not seen by a human that can spot the error), you should indeed exit with a non-zero exit code. However, it is tedious to do this for every printf() call. What you can do is ignore the return value of printf(), but at the end of the program do an fflush(stdout) and then check the return value of ferror(sdtout): if true, something went wrong earlier. \$\endgroup\$
    – G. Sliepen
    Jul 16, 2023 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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