israel-lugo/tsarray

Generic type-safe dynamic array library for C

tsarray's Issues

Implement a constructor to create tsarrays

We already have a mandatory destructor, which must be called to free resources. It's inconsistent to allow the tsarray to have automatic storage duration, while still requiring a mandatory cleanup function.

Also, this opens up the possibility of abstracting/obscuring inner details from the user (see issue #2).

Create a non-sparse version, that moves data on deletion instead of leaving holes

The default behavior should be to move data on deletion, instead of leaving holes. Look at Python's lists, for example. People normally care about the order in which they insert things, and don't want things to be inserted "in the first available hole".

We can have an optional flag inside the array, that indicates whether it should behave in a sparse manner or not. Or probably better to have different types altogether.

Create max and min operators

It would be nice to have max and min operators, which return respectively the largest or smallest element. Naturally, they would need to receive a key function as a parameter, which takes an element and returns an ordinal key.

Given an array fooarray of items of type foo_t, the function signature should be something like this:

foo_t *fooarray_max(const fooarray *array, long (*key)(foo_t *));

Problem: we're limiting the key to the width of a long. That may be too limiting, if the items have a larger key space. One alternative would be to receive an abstract comparison function, but that would make an efficient implementation more difficult to achieve.

Implement slicing operation

Something akin to Python's slices:

>>> a1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9 , 10]
>>> a1[2:5]
[2, 3, 4]

Deal with aliasing issues

We're doing a lot of type magic and pointer casting. This is almost certainly breaking C99 strict aliasing rules, which may lead to undefined behaviour in the face of aggressive optimizations by the compiler.

gcc for example is known to aggressively follow a strict interpretation of what may and may not alias under C99 rules, in order to squeeze additional performance out of the code. -fstrict-aliasing is enabled by default at -O2, which is a conservative setting used almost everywhere. It can be disabled, however, with -fno-strict-aliasing.

Under strict aliasing rules, the compiler is free to assume, for example, that objects of different types never alias, rendering this undefined behaviour:

#include <stdio.h>

long foo(int *x, long *y) {
  *x = 0;
  *y = 1;
  return *x;
}
int main() {
  long value;
  printf("%ld\n", foo((int *)&value, &value));
  return 0;
}

gcc assumes that x and y inside foo can never point to the same thing, so it is free to reorder the writes and return 0 unconditionally. Meaning the above code will print 1 without optimizations, and 0 with optimizations.

Create a way for the user to provide a size hint

Sometimes the user already has an idea of the expected size magnitude of the array. Maybe he knows he will be adding around 50 items.

We should have an optional size hint in the tsarray_new constructor. It would preallocate the internal array with the specified capacity, so there would be no need for useless resizing. We should also alter tsarray_resize so that it takes the hint into consideration. That means we should remember the size hint, as an internal variable of struct _tsarray_priv.

What should tsarray_resize do with the size hint?

Hide the tsarray private fields from the user

We can hide the _priv field from the user, with some pointer magic.

Create an internal-only struct _tsarray_desc with all the internal fields we want, and the last field is the publicly accessible struct _tsarray_abs (which only has user-visible fields).

This means we'll need a constructor to create tsarrays. Which is probably better for symmetry anyway, since we already require that the user call tsarray_free(). The constructor will internally create a _tsarray_desc, but will only return a pointer to the public struct _tsarray_abs within it. All public functions receive that pointer, it's the only thing the user ever knows.

Internally, whenever we want to access the containing struct _tsarray_desc of a given struct _tsarray_abs, we use offsetof() pointer arithmetic to calculate the container address.

In fact, in the spirit of having a more array-like experience, we could just give the user a pointer to the items array itself. Any other public items (such as len) would be read by getter functions. More magical and user-friendly, which is good, but more magical, which is bad. Also, not as efficient (we can get around that by defining static inline getters).

Implement automated valgrind/fsanitize checks

Should be completely automated, and only run if the user has valgrind and/or a compiler that can accept -fsanitize=address.

Add source configuration and build system

Add Autoconf scripts to generate a standard GNU build system. Use libtool to produce a dynamic library, as well as a static one.

Add regression tests

It's a good idea to test new features as they come along. We can use libcheck for that.

Implement new constructor operations

It would be nice to have a tsarray_copy(), that takes a tsarray and returns a new tsarray copy of it. Also, a tsarray_from_array(), that receives a pointer to an actual array of objects, and the array's length.

Fix implicit conversions and comparisons between signed and unsigned integers

Compile the code with -Wsign-compare -Wsign-conversion -Wconversion. There are multiple potential issues here regarding signed and unsigned comparisons, and loss of precision and/or signedness. The loss of signedness may lead to undefined behavior as we reach an integer overflow.

We should probably just use signed integers for indices instead of size_t. In fact tsarray_remove is using int for its index argument! That was an accident, but may well be more correct.

Consider using long instead of int, to allow very big arrays.

The thing is, size_t really is defined to be exact thing that we want... but it being unsigned comes at a price.

Note we have to redo the integer overflow protections, i.e. can_size_add and can_size_mult. Rethink that.