3
\$\begingroup\$

I attempted to make a smart/dynamic array implementation in C which is supposed to be a hybrid between a C++ vector/stack/queue.

This is what i came up with:

Header (smart_array.h):

#pragma once

#include <stddef.h>

typedef struct smart_array smart_array_t;

void smart_array_alloc(smart_array_t** array, size_t capacity);
void smart_array_free(smart_array_t** array);
int  smart_array_resize(smart_array_t* array, size_t capacity);

void smart_array_capacity(smart_array_t* array, size_t* capacity);
void smart_array_total(smart_array_t* array, size_t* total);
void smart_array_empty(smart_array_t* array, int* empty);

int  smart_array_set(smart_array_t* array, size_t index, void* item);
int  smart_array_set_back(smart_array_t* array, void* item);
int  smart_array_set_top(smart_array_t* array, void* item);

void smart_array_get(smart_array_t* array, size_t index, void** item);
void smart_array_get_back(smart_array_t* array, void** item);
void smart_array_get_top(smart_array_t* array, void** item);

int  smart_array_push_back(smart_array_t* array, void* item);
int  smart_array_push_top(smart_array_t* array, void* item);

int  smart_array_pop(smart_array_t* array, size_t index);
int  smart_array_pop_back(smart_array_t* array);
int  smart_array_pop_top(smart_array_t* array);
int  smart_array_clear(smart_array_t* array);

Source File: (smart_array.c):

#include "smart_array.h"
#include <stdlib.h>

struct smart_array {
    void** items;
    size_t total;
    size_t capacity;
};

void smart_array_alloc(smart_array_t** array, size_t capacity) {
    if(!(*array = malloc(sizeof(struct smart_array))))
        return;
    if(!((*array)->items = malloc(sizeof(void*) * capacity))) {
        free(*array);
        *array = 0;
        return;
    }
    (*array)->capacity = capacity;
    (*array)->total = 0;
}

void smart_array_free(smart_array_t** array) {
    if(array && *array) {
        free((*array)->items);
        free(*array);
        *array = 0;
    }
}

int smart_array_resize(smart_array_t* array, size_t capacity) {
    if(array) {
        void **items = realloc(array->items, sizeof(void*) * capacity);
        if(items) {
            array->items = items;
            array->capacity = capacity;
            return 0;
        }
    }
    return 1;
}

void smart_array_capacity(smart_array_t* array, size_t* capacity) {
    *capacity = !array ? 0 : array->capacity;
}

void smart_array_total(smart_array_t* array, size_t* total) {
    *total = !array ? 0 : array->total;
}

void smart_array_empty(smart_array_t* array, int* empty) {
    *empty = array->total == 0;
}

int smart_array_set(smart_array_t* array, size_t index, void* item) {
    if(array) {
        if (index >= 0 && index < array->total) {
            array->items[index] = item;
            return 0;
        }
    }
    return 1;
}

int smart_array_set_back(smart_array_t* array, void* item) {
    size_t total;
    smart_array_total(array, &total);
    return smart_array_set(array, total - 1, item);
}

int smart_array_set_top(smart_array_t* array, void* item) {
    return smart_array_set(array, 0, item);
}

void smart_array_get(smart_array_t* array, size_t index, void** item) {
    if(array && item) {
        if (index >= 0 && index < array->total)
            *item = array->items[index];
        else 
            *item = 0;
    }
}

void smart_array_get_back(smart_array_t* array, void** item) {
    size_t total;
    smart_array_total(array, &total);
    smart_array_get(array, total - 1, item);
}

void smart_array_get_top(smart_array_t* array, void** item) {
    smart_array_get(array, 0, item);
}

int smart_array_push_back(smart_array_t* array, void* item) {
    if(array) {
        if(array->capacity == array->total) {
            if(smart_array_resize(array, array->capacity * 2))
                return 1;
        }
        array->items[array->total++] = item;
        return 0;
    }
    return 1;
}

int smart_array_push_top(smart_array_t* array, void* item) {
    if(array) {
        if(array->capacity == array->total) {
            if(smart_array_resize(array, array->capacity * 2))
                return 1;
        }
        array->total++;
        for(size_t s = array->total; s > 0; --s) 
            array->items[s] = array->items[s - 1];
        array->items[0] = item;
        return 0;
    }
    return 1;
}

int smart_array_pop(smart_array_t* array, size_t index) {
    if(array && (index >= 0) && (index < array->total)) {
        array->items[index] = 0;
        for (int i = index; i < array->total - 1; ++i) {
            array->items[i] = array->items[i + 1];
            array->items[i + 1] = NULL;
        }
        array->total--;
        if ((array->total > 0) && ((array->total) == (array->capacity / 4))) {
            if(smart_array_resize(array, array->capacity / 2))
                return 0;
        }
    }
    return 1;
}

int smart_array_pop_back(smart_array_t* array) {
    size_t total;
    smart_array_total(array, &total);
    return smart_array_pop(array, total - 1);
}

int smart_array_pop_top(smart_array_t* array) {
    return smart_array_pop(array, 0);
}

int smart_array_clear(smart_array_t* array) {
    int empty;
    smart_array_empty(array, &empty);
    while(!empty) {
        smart_array_pop_top(array);
        smart_array_empty(array, &empty);
    }
    return 0;
}

Test (main.c):

#include "smart_array.h"
#include <stdlib.h>
#include <stdio.h>

void print_smart_array(smart_array_t* array) {
    size_t total, capacity;
    
    smart_array_total(array, &total);
    smart_array_capacity(array, &capacity);
    
    printf("Array total: %i\n", total);
    printf("Array capacity: %i\n", capacity);
    
    printf("Array items:\n");
    for(size_t i = 0; i < total; ++i) {
        int* val;
        smart_array_get(array, i, (void**)&val);
        printf("\t%i\n", *val);
    }
}

int main(void) {
    smart_array_t* a;
    smart_array_alloc(&a, 4);
    
    int* x = malloc(sizeof(int));
    int* y = malloc(sizeof(int));
    int* z = malloc(sizeof(int));
    int* w = malloc(sizeof(int));
    
    *x = 3;
    *y = 56;
    *z = 100;
    *w = 87;
    
    smart_array_push_back(a, x);
    smart_array_push_back(a, x);
    smart_array_push_top(a, w);
    smart_array_push_back(a, w);
    smart_array_push_top(a, y);
    
    print_smart_array(a);
    
    smart_array_clear(a);
    
    print_smart_array(a);
    
    free(x);
    free(y);
    free(z);
    free(w);
    smart_array_free(&a);
}
```
\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

File Structure

The code is well organised into testing, implementation, and headers. Including stddef.h is appropriate in your header since you use size_t.

Consistency

Consider making sure the pointers are valid, for example, with assert, or at least in documentation, before writing to them. The users of this code might not understand, and it's not ideal for them to go sifting through your code to find the problem. At least, have it consistent; in smart_array_set it checks for null when the others do not.

typedef struct smart_array smart_array_t is potentially problematic. See discussion type followed by _t represent and Linux Kernel Style Guide. I think that one's users should be free to express it as a typedef, so I would just stick with struct smart_array; C and C++ are different languages.

Return Values

Returning void from smart_array_alloc is problematic because there are two different paths it could take; one would have to query the pointer to see if it succeeded. It should be easy to use properly, and as it stands, using this without checking is an (undocumented) mistake.

I would expect smart_array_get(_*) to return the item. As it stands, one has a pointer to the item passed in and it returns void. This can be annoying when functional composition is desired. Same thing with most of one's other functions. At least shortly document them explaining the change from C++.

I expect some sort of error or feedback when accessing out-of-bounds, but this does nothing. It is arguably not the best choice.

Constructor Simplification

I would expect smart_array_alloc is going to be called with the default constructor most of the time, so I would consider make one not including capacity that calls the one that does.

The two allocations are properly handled by smart_array_alloc, but they could be simplified by calling smart_array_free instead. One doesn't need two allocations, since it's aligned already, it would be simpler to allocate it as one.

if(!(*array = malloc(sizeof struct smart_array + sizeof(void*) * capacity)
    return (fail);
(*array)->items = (void *)(*array + 1);

In fact, there are multiple memory allocations that could be all calling smart_array_resize.

If ptr is a null pointer, realloc() shall be equivalent to malloc() for the specified size.

I would consider exposing the struct smart_pointer in the header for allocation on the stack and simplifying this even more, but that's a design decision that is not always appropriate.

Zero Values

smart_array_set_back and smart_array_set_top will have undefined behaviour when empty or capacity is zero.

Use of Private Members

I think it's okay to use total as a data member in this private code instead of getting it through the public outward-facing smart_array_total. smart_array_clear, with access to private members, should be very simple.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.