Implementacja listy tablicowej w języku C

Hej, napisałem array listę w C i proszę o code review :)

Nagłówek

#ifndef ARRAY_LIST_H
#define ARRAY_LIST_H

#include <stdlib.h>

static const int AL_INITIAL_CAPACITY = 16;

struct array_list {
    int *array;
    size_t capacity;
    size_t count;
};

struct array_list *al_new(void);
int al_destroy(struct array_list **list);

int al_ensure_capacity(struct array_list *list, size_t capacity);

int al_push_back(struct array_list *list, int data);
int al_pop_back(struct array_list *list, int *data);
int al_push_front(struct array_list *list, int data);
int al_pop_front(struct array_list *list, int *data);

int al_is_valid_index(struct array_list *list, int index);
int al_get(struct array_list *list, int index, int *data);
int al_set(struct array_list *list, int index, int data);

int al_insert(struct array_list *list, int index, int data);
int al_delete(struct array_list *list, int index);

int al_find(struct array_list *list, int data);
int al_find_last(struct array_list *list, int data);
int al_contains(struct array_list *list, int data);

int al_is_empty(struct array_list *list);
int al_clear(struct array_list *list);

int al_delete_first(struct array_list *list, int data);
int al_delete_last(struct array_list *list, int data);

int al_print(struct array_list *list);

#endif //ARRAY_LIST_H

Źródło

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "array_list.h"

struct array_list *al_new(void) {
    struct array_list *list = malloc(sizeof(*list));
    if (list == NULL) {
        return NULL;
    }
    list->array = malloc(sizeof(*(list->array)) * AL_INITIAL_CAPACITY);
    list->capacity = AL_INITIAL_CAPACITY;
    list->count = 0;
    for (int i = 0; i < list->capacity; ++i) {
        list->array[i] = 0;
    }
    return list;
}

int al_destroy(struct array_list **list) {
    if (list == NULL || *list == NULL) {
        return -1;
    }
    free((*list)->array);
    (*list)->capacity = 0;
    (*list)->count = 0;
    free(*list);
    *list = NULL;
    return 0;
}

int al_ensure_capacity(struct array_list *list, size_t capacity) {
    if (list == NULL) {
        return -1;
    }
    size_t old_capacity = list->capacity;
    if (old_capacity < capacity) {
        list->capacity = (capacity + capacity / 2);
        list->array = realloc(list->array, sizeof(*(list->array)) * list->capacity);
        if (list->array == NULL) {
            return -1;
        }
        for (size_t i = old_capacity; i < list->capacity; ++i) {
            list->array[i] = 0;
        }
    }
    return 0;
}

int al_push_back(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    al_ensure_capacity(list, list->count + 1);
    list->array[list->count] = data;
    ++(list->count);
    return 0;
}

int al_pop_back(struct array_list *list, int *data) {
    if (list == NULL) {
        return -1;
    }
    *data = list->array[list->count - 1];
    list->array[list->count - 1] = 0;
    --(list->count);
    return 0;
}

int al_push_front(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    al_ensure_capacity(list, list->count + 1);
    memmove(&(list->array[1]), list->array, list->count * sizeof(*(list->array)));
    list->array[0] = data;
    ++(list->count);
    return 0;
}

int al_pop_front(struct array_list *list, int *data) {
    if (list == NULL) {
        return -1;
    }
    if (data != NULL) {
        *data = list->array[0];
    }
    memmove(list->array, list->array + 1, list->count * sizeof(*(list->array)));
    list->array[list->count] = 0;
    --(list->count);
    return 0;
}

int al_is_valid_index(struct array_list *list, int index) {
    if (list == NULL) {
        return -1;
    }
    return index >= 0 && index < list->count ? 0 : -1;
}

int al_get(struct array_list *list, int index, int *data) {
    if (list == NULL || !al_is_valid_index(list, index)) {
        return -1;
    }
    *data = list->array[index];
    return 0;
}

int al_set(struct array_list *list, int index, int data) {
    if (list == NULL || !al_is_valid_index(list, index)) {
        return -1;
    }
    list->array[index] = data;
    return 0;
}

int al_insert(struct array_list *list, int index, int data) {
    if (list == NULL || al_is_valid_index(list, index) < 0) {
        return -1;
    }
    al_ensure_capacity(list, list->count + 1);
    memmove(&(list->array[index + 1]),
            &(list->array[index]),
            (list->count - index) * sizeof(*(list->array)));
    list->array[index] = data;
    ++(list->count);
    return 0;
}

int al_delete(struct array_list *list, int index) {
    if (list == NULL || al_is_valid_index(list, index) < 0) {
        return -1;
    }
    memmove(&(list->array[index]),
            &(list->array[index + 1]),
            sizeof(*(list->array)) * list->count);
    list->array[list->count] = 0;
    --(list->count);
    return 0;
}

int al_find(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    for (int i = 0; i < list->count; ++i) {
        if (list->array[i] == data) {
            return data;
        }
    }
    return -1;
}

int al_find_last(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    for (int i = (int)list->count - 1; i >= 0; --i) {
        if (list->array[i] == data) {
            return data;
        }
    }
    return -1;
}

int al_contains(struct array_list *list, int data) {
    return al_find(list, data) ? 0 : -1;
}

int al_delete_first(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    int index = al_find(list, data);
    if (index >= 0) {
        al_delete(list, index);
    }
    return 0;
}

int al_delete_last(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    int index = al_find_last(list, data);
    if (index >= 0) {
        al_delete(list, index);
    }
    return 0;
}

int al_is_empty(struct array_list *list) {
    if (list == NULL) {
        return -1;
    }
    return list->count == 0 ? 0 : -1;
}

int al_clear(struct array_list *list) {
    if (list == NULL) {
        return -1;
    }
    for (int i = 0; i < list->count; ++i) {
        list->array[i] = 0;
    }
    list->count = 0;
    return 0;
}

int al_print(struct array_list *list) {
    if (list == NULL) {
        return -1;
    }
    if (list->count == 0) {
        printf("list is empty\n");
        return 0;
    }
    for (int i = 0; i < list->count; ++i) {
        printf("array list node %d: %d\n", i, list->array[i]);
    }
    return 0;
}

Znacznie łatwiej byłoby robić review, gdybyś wrzucił to gdzieś na githuba, żeby można było wstawiać komentarze w konkretnych linijkach.

1. Rozważ użycie typedef, żeby nie pisać struct za każdym razem.
2. linia 11: rozważ użycie calloc zamiast malloc. calloc: inicjalizuje alokowany obszar zerami, używając malloca jest zawsze ryzyko, że mnożenie przepełni ci rejestr (choć raczej nie w tym przypadku), również w przypadku alokacji większych obszarów pamięci może być wydajniejszy niż malloc. Analogicznie, jeśli programujesz na Linuksa, możesz użyć reallocarray zamiast realloc. Poza tym, sizeof(struct array_list). Tak chyba jest czytelniej.
3. 25,26: po co zerujesz zmienne w pamięci, którą zaraz potem zwalniasz?
4. 64: w al_pop_front pozwalasz, żeby parametr data == NULL i to brzmi rozsądnie, jeśli nie obchodzi Cię usuwana wartość. Generalnie nie podoba mi się rozwiązanie ze zwracaniem przez wskaźnik w parametrze, ale w C każde rozwiązanie tego problemu będzie jakimś mało fajnym kompromisem. Ja bym po prostu nie robił testu i zwracał wartość normalnie, licząc że wywołujący sprawdzi poprawność (jeśli już piszę w C).
5. Oba popy nie sprawdzają czy jest co usuwać z listy!
6. 101: operacje get it set nie mają wiele sensu w tym przypadku. Co innego gdybyś usunął deklarację pól struktury array_list z nagłówka (wstawił w plik z kodem) i zostawił tylko struct array_list. Wtedy miałbyś ładną enkapsulację. A jeśli masz publiczną deklarację to w ogóle zrezygnowałbym z alokowania obiektów array_list dynamicznie tylko zwracał przez wartość. Współczesny kompilator sobie z tym spokojnie poradzi, a unikniesz trochę zabawy z dynamiczną alokacją.

Tak poza tym wygląda całkiem spoko i porządnie. Tylko te 3linijkowe wywołania memmove bym wydzielił do osobnej funkcje.