array get/set in constant time

constant_array.c

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

struct array {
        int* data;
        int* set_list;
        int* set_pos_list;
        int set_count;
        int length;
        int default_value;
};

void array_print(struct array* a) {
        printf("\ndata: ");
        for (int i = 0; i < a->length; i++) {
                printf("%d ", a->data[i]);
        }
        printf("\nsetl: ");
        for (int i = 0; i < a->set_count; i++) {
                printf("%d ", a->set_list[i]);
        }
        printf("\nspos: ");
        for (int i = 0; i < a->length; i++) {
                printf("%d ", a->set_pos_list[i]);
        }
        printf("\nset_count: %d\n", a->set_count);
}

struct array* array_init(int size, int default_val) {
        struct array *a = malloc(sizeof(struct array));
        a->data = malloc(size * sizeof(int));
        a->set_list = malloc(size * sizeof(bool));
        a->set_pos_list = malloc(size * sizeof(int));
        a->set_count = 0;
        a->default_value = default_val;
        a->length = size;
}

bool is_set(struct array* a, int index) {
        // 1st try with O(n)
        /*
         for (int i = 0; i < a->set_count; i++) {
                if (a->set_list[i] == index) {
                        return true;
                }
        }
        return false;
        */

        // 2nd try to improve to the O(1)
        int pos = a->set_pos_list[index];
        if (pos >= a->set_count || a->set_list[pos] != index) {
                return false;
        }
        return true;
}

void mark_as_set(struct array* a, int index) {
        if (!is_set(a, index)) {
                a->set_list[a->set_count] = index;
                a->set_pos_list[index] = a->set_count;
                a->set_count++;
        }
}