Project Euler #12 in C (memory management)

Question

I haven't written one bit of C code in well over a decade, being mostly in C#, Rust and Elixir. That being said I have a work reason to work in some C code (much to my dismay) and I'm trying to get back in the groove of actually having to care about memory management.

To do this I'm working through project Euler problems, and for problem #12 I have the following code:

Utils.h:

#ifndef C_SCRATCHPAD_UTILS_H
#define C_SCRATCHPAD_UTILS_H

#define BOOL char
#define TRUE 1
#define FALSE 0

typedef struct {
    long *values;
    int size;
    int capacity;
} long_list;

long_list *get_primes_to_index(int index);

long_list *new_long_list();
void add_to_long_list(long_list *list, long value);

#endif //C_SCRATCHPAD_UTILS_H

Utils.c

#include <stdlib.h>
#include <string.h>
#include "utils.h"

long_list *get_primes_to_index(int index)
{
    long_list *primes = new_long_list();
    add_to_long_list(primes, 2);

    long current_number = 3;
    while (primes->size < index + 1)
    {
        BOOL divisor_found = FALSE;
        for (int iterator = 0; iterator < primes->size; iterator++)
        {
            if (current_number % primes->values[iterator] == 0)
            {
                divisor_found = TRUE;
                break;
            }
        }

        if (divisor_found == FALSE)
        {
            add_to_long_list(primes, current_number);
        }

        current_number++;
    }

    return primes;
}

long_list *new_long_list()
{
    long_list *list = malloc(sizeof(long_list));
    list->values = malloc(sizeof(long));
    list->size = 0;
    list->capacity = 1;

    return list;
}

void add_to_long_list(long_list *list, long value)
{
    if (list->size + 1 > list->capacity)
    {
        long *temp = list->values;
        list->values = malloc(list->capacity * 2 * sizeof(long));
        memcpy(list->values, temp, list->capacity * sizeof(long));
        list->capacity = list->capacity * 2;
        free(temp);
    }

    list->values[list->size] = value;
    list->size++;
}

euler.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "euler.h"
#include "utils.h"

typedef struct {
    long *factors;
    int factor_count;
    long triangle_value;
} data;

data *get_factors_of_xth_triangle_number(int triangle_number, long_list *primes)
{
    long_list *numbers = new_long_list();
    long total = 0;
    for (int x = 1; x <= triangle_number; x++)
    {
        total += x;
        add_to_long_list(numbers, x);
    }

    // Find the factors
    long_list *factors = new_long_list();
    long sqrt_of_total = (long)sqrt(total);
    for (int index = -1;index < primes->size; index++)
    {
        long prime = index >= 0 ? primes->values[index] : 1;
        if (prime > sqrt_of_total)
        {
            break;
        }

        if (total % prime == 0)
        {
            int multiplier = 1;
            while(1)
            {
                long test_number = prime * multiplier;
                if ((prime == 1 && multiplier > 1) || test_number > sqrt_of_total)
                {
                    break;
                }

                BOOL already_has_value = FALSE;
                for (int x = 0; x < factors->size; x++)
                {
                    if (test_number == factors->values[x])
                    {
                        already_has_value = TRUE;
                        break;
                    }
                }

                if (already_has_value == FALSE && test_number < total && total % test_number == 0)
                {
                    add_to_long_list(factors, test_number);
                    if (total / test_number != test_number)
                    {
                        add_to_long_list(factors, total / test_number);
                    }
                }

                multiplier++;
            }
        }
    }

    data *results = malloc(sizeof(data));
    results->factor_count = factors->size;
    results->triangle_value = total;
    results->factors = factors->values;

    free(numbers);
    free(factors);

    return results;
}

void run_euler_problem()
{
    printf("Problem #12\n");

    long_list *primes = get_primes_to_index(500);

    int number = 1;
    while (1)
    {
        data *results = get_factors_of_xth_triangle_number(number, primes);
        int factor_count = results->factor_count;
        long total = results->triangle_value;
        free(results->factors);
        free(results);

        if (factor_count > 500)
        {
            printf("Result: %ld\n", total);
            break;
        }

        number++;
    }

    free(primes->values);
    free(primes);
}

I'm less concerned with algorithmic efficiency as much as I am that I'm allocating things correctly, freeing things correctly, and generally not missing any C-specific gotchas that I'm not aware of.

Answer 1

Memory leak / useless variable

You have a variable numbers that is a long_list filled with the numbers 1..triangle_number, but you never use this list. Later, when you free the list, you forgot to also free numbers->values.

I would suggest writing a free_long_list() function so that you don't have to remember to free the values field everywhere you free a long_list.

Answer 2

Generally, when you free something, it's a good idea to null out the pointer afterwards. While in a program this small, you'd be unlikely to make a mistake, when you null a pointer, most platforms will terminate the program rather than have potentially undefined behavior from a dangling pointer if you accidentally reuse it. You should get in the habit of doing this.

There is a function called realloc that performs a malloc/memcpy/free cycle for you on your behalf. Some platforms can also resize the memory without moving it (assuming enough contiguous space exists after the allocated memory), which can be a performance benefit. You should use realloc instead of malloc/memcpy/free, because it will always be at least as fast, and often faster.

That said, your code appears to be free of memory leaks, accessing invalid memory, buffer overflows, etc. There's a lot of minor optimizations that could be recommended, but this code is at least logically sound.

Answer 3

It's a small point, but it's better to write, for example

long_list *list = malloc(sizeof *list);

than

long_list *list = malloc(sizeof(long_list));

The point being that if you ever change the type of list you don't have to change the sizeof.

Another small point is that it would, I would say, be more idiomatic to use a for loop rather than a while in run_euler_problem().