Avoid name-space pollution
You have carefully suffixed all your function names with the name of the type they operate on. This is good.
On the other hand, your header file spams macro definitions for LT, EQ and TYPE into each file that #includes it. This is evil. TYPE is a far too generic name that might legitimately be used otherwise. LT and EQ are even worse. Besides, you're never using them. I suggest you get rid of all three macros as they are not needed. If you do need to #define macros in public header files, prefix them with your package name, for example, DYN_ARRAY_TYPE.
Declare helper functions static
You have some helper functions that are only needed inside the dynamicArray.c file. You have suffixed them with an underscore to indicate this. It would be better to (additionally) declare them static. This way, they will be truly private to your implementation file and cannot clash with other functions in other files. It might also make the code smaller and faster.
The function createDynArr is never defined. On the other hand, there is initDynArr which is not declared in the header. This is good, because the function is not needed by clients. You should delete the declaration of createDynArr from the header file and make initDynArr a static function.
Consider putting the type name first: sizeDynArr → DynArr_size
As discussed above, putting the type name into the function name is good because it avoids name clashes with functions that operate on other types that might also provide similar operations.
I prefer prefixing the type name, though. This makes the textual appearance of the function names more cohesive and supports auto-completion.
I find it more readable to put an underscore between type name and function name.
Avoid confusing names
You have the following functions:
newDynArrcreateDynArr / initDynArr (see above)freeDynArrdeleteDynArr
Without looking at the code, it is hard to guess what the functions do. I recommend you seek for pairs of matching names. For example:
DynArr_new – allocates memory for a DynArr and initializes itDynArr_init – initializes an already allocated DynArrDynArr_fini – deinitializes a DynArrDynArr_del – deinitializes a DynArr and deallocates it
Since DynArr is an opaque type, the init and fini functions need not / should not be exposed by the header file.
You might be interested in my answer to this question on Stack Overflow about initializing (non) opaque types.
Consider bool instead of int for logical values
C99 introduced <stdbool.h> which provides true, false and bool. Using these makes your intent clearer than using 1, 0 and int.
Consider size_t (or ptrdiff_t) instead of int
Some people say that when a value must not be negative, an unsigned integer type should be used. Others argue that unsigned arithmetic is a confusing source of bugs and it was a mistake to chose unsigned integer types for array sizes. Anyway, this choice is now baked so tightly into the language that it will never change. Having to switch between signed and unsigned types combines the worst of both worlds so you might as well accept it and use size_t for your array sizes and indices consistently. If you still want to use a signed integer, use ptrdiff_t as it is guaranteed to be large enough. int is only required to be at least 16 bit wide although it will be 32 bit on almost any modern platform.
size_t and ptrdiff_t are provided by the <stddef.h> header.
Be const correct
If a function does not modify the object, it should take it by pointer-to-const. For example, DynArr_size certainly shouldn't alter the DynArr object, so declare it like this.
size_t DynArr_size(const DynArr * self);
// ^^^^^
What is a TYPE?
Your header file #defines the macro TYPE (which should really be named DYN_ARRAY_TYPE) to int. It would be handy if I could #define DYN_ARRAY_TYPE double before #includeing your header and instead get a dynamic array of doubles. Except, it doesn't work like this. While the code will compile and (unfortunately) probably also link happily, it will invoke tons of undefined behavior when executed. The problem is that your implementation file is still compiled for int.
If you don't want your users to #define the element type, just spell out int or use a typedef in your header file that cannot be changed from the outside. (But please pick a more specific name than type.)
If you want to be generic, it can be done even in C but it is ugly. First, you have to put all your code into the header file. That's not too bad but don't forget to declare all functions as inline.
Second, you have to change your names according to the type via some macro magic. For example, instead of
size_t DynArr_size(const DynArr * self);
you would write
#define DYN_ARRAY_CONCAT_R(FIRST, SECOND) FIRST ## SECOND
#define DYN_ARRAY_CONCAT(FIRST, SECOND) DYN_ARRAY_CONCAT_R(FIRST, SECOND)
#define DYN_ARRAY_SELF DYN_ARRAY_CONCAT(DynArr_, DYN_ARRAY_TYPE)
inline size_t
DYN_ARRAY_CONCAT(DYN_ARRAY_SELF, _size)(const DYN_ARRAY_SELF * self);
#undef DYN_ARRAY_SELF
After pre-processing with -DDYN_ARRAY_TYPE=float, you will get this.
inline size_t
DynArr_float_size(const DynArr_float *self);
Which is a proper unambiguous declaration yet without a definition.
But you still cannot have DynArrs for different types in the same translation unit because of your #include guards.
If this sounds like black magic to you, then because it is. Just hard-code int or learn C++. Even writing a place-holder like @TYPE@ in your code and manually stamping out concrete versions by running
$sed 's,@TYPE@,float,g' dyn_array.h.in > dyn_array_float.h
can be simpler and less frustrating.
Document your contracts and report contract violations loudly
You were careful to detect certain erroneous conditions, such as passing NULL as the pointer to the DynArr or asking to pop an element off an empty stack. Writing defensive code is a Good Thing. I'm not a fan of the way you respond to the error conditions, though.
The first thing you should do is document the contract of your functions. There are two ways to specify contracts.
- Functions with a wide contract allow for them to be called with nonsensical arguments. If they detect a problem, they report an error and do nothing.
- Functions with narrow contract put the responsibility to only call them with valid arguments on the caller. If they are called with invalid arguments, their behavior is undefined and arbitrary bad things might happen.
Both types of contracts have their place. However, wide contracts are much harder to implement and are not always as useful as they might appear at first.
Let's look at element lookup as an example. It is pretty obvious that it can only perform a meaningful action when the position is non-negative and less than the size of the array.
You have implemented it like this.
TYPE getDynArr(DynArr *v, int pos)
{
TYPE value;
if(v != NULL && v->size != 0 && v->size >= pos) {
value = v->data[pos];
}
return value;
}
Is the contract of this function narrow or wide? Okay, v->size >= pos must be v->size < pos, the check v->size != 0 is redundant and you should also check pos >= 0. But apart from that, what does the function do if it detects invalid arguments? It simply returns an uninitialized value. This itself is undefined behavior but if TYPE is int, chances are good that it won't crash your program and instead produce some garbage value.
So, even though the function verifies its arguments, its behavior is undefined when called with invalid arguments. You could easily make the behavior well-defined by initializing value with 0. But would that be useful? When getDynArr gives me 0, how can I know whether it is an indication of failure or whether there happened to be the value 0 at the position?
So, implementing DynArr_get with a proper wide contract could look like this.
/**
* Retrieves the value of an element at a given index.
*
* If `self == NULL` or if `pos` is not a valid index for the given array,
* `false` is `return`ed and `*result` is not touched. Otherwise, `*result`
* is set to the value at index `pos` and `true` is `return`ed.
*
* @param self
* `DynArr` to operate on
*
* @param pos
* index of the element to retrieve
*
* @param result
* address to store the result at
*
* @returns
* whether a valid value was stored at `*result`
*
*/
bool DynArr_get(const DynArr *const self, const size_t pos, int *const result)
{
// I don't have to check `(pos < 0)` because `size_t` is unsigned.
if ((self == NULL) || (pos >= self->size)) {
return false;
}
*result = self->data[pos];
return true;
}
It can be used like this.
int value;
if (DynArr_get(array, 2, &value)) {
printf("The value is: %d\n", value);
} else {
fprintf(stderr, "Oh no, I made a mistake!\n");
}
I would say that this is convoluted and not useful. Whoever is using a DynArr had better make sure they only ask for elements at valid indices. If in doubt, they can always ask for the size of the array before they ask for the element.
So let's implement DynArr_get with a narrow contract instead.
/**
* Retrieves the value of an element at a given index.
*
* If `self == NULL` or if `pos` is not a valid index for the given array,
* the behavior is undefined.
*
* @param self
* `DynArr` to operate on
*
* @param pos
* index of the element to retrieve
*
* @returns
* value of the element at index `pos`
*
*/
int DynArr_get(const DynArr *const self, const size_t pos)
{
return self->data[pos];
}
This is a perfectly valid and reasonable implementation. If the function is called with invalid arguments, it will invoke undefined behavior but that's just what its documentation says. However, you can do your users a favor by crashing their application loudly when you detect a contract violation.
int DynArr_get(const DynArr *const self, const size_t pos)
{
assert((self != NULL) && (pos < self->size));
return self->data[pos];
}
Triggering an assertion failure is a valid form of undefined behavior so we still fulfill our contract but we give the programmer a clear hint what to fix in their code. On the other hand, the assert will vaporize away when the NDEBUG macro is #defined so we don't force users to pay the overhead for the argument validation if they don't want to.
If you still haven't enough about design-by-contract and defensive programming, I recommend you watch John Lakos' talk “Defensive Programming Done Right” (part 1, part 2) from CppCon '14. Some of it is specific to C++ but the general concepts are language agnostic. Alisdair Meredith's talk “Details Matter” (video, slides) at C++ Now '15 covers some of the same ideas.
Don't handle out-of-memory with assert
The assert macro should be used to detect contract violations and verify assumptions, that is unveil bugs. It is not an appropriate tool for handling general run-time errors. Even a bug-free program can run out of memory.
Apart from that, not every failure of malloc should immediately terminate the program. It might be an appropriate reaction for many applications but a library type like your DynArr should not force this on its users. So, make the functions that need to allocate memory react gracefully to out-of-memory conditions and report the error back to their caller. DynArr_new could just return NULL and do nothing if it fails to allocate memory and DynArr_add could return a bool that indicates whether the operation succeeded and not modify the array when it cannot allocate memory but the current size is at the capacity limit.
Note that while modern computers have plenty of memory, users might artificially constrain it for certain applications. For example, I might want to set the memory limit for a server process that handles simple requests to 10 MiB to prevent denial of service attacks that send maliciously crafted queries that exploit worst-case characteristics of my algorithm. Now imagine what happens when your code asserts on malloc to succeed and the program was compiled with NDEBUG. The allocation will fail but instead of having defeated the DoS attack, we have provided the attacker with a way to corrupt memory!
Consider a “constructor” that creates a zero-initialized non-empty array
If I want a zero-filled DynArr of size n, I currently have to do this.
DynArr * array = DynArr_new(n);
while (DynArr_size(array) != n) {
DynArr_push(array, 0);
}
This is awkward and inefficient.
On the other hand, why do I have to specify an explicit capacity when I create a DynArr?
I would consider the following interface more useful.
/**
* Allocates a zero-initialized dynamic array.
*
* If `n == 0`, no internal storage is allocated yet.
*
* @param n
* initial size for the array
*
* @returns
* a pointer to the array or `NULL` if allocation failed
*
*/
DynArr * DynArr_new(size_t n);
/**
* Reserves internal memory without changing the size.
*
* If the current capacity is already equal to or greater than `n`, this
* function does nothing. If allocation fails, the `return`ed new capacity
* will be less than `n`.
*
* @param n
* minimum capacity to ensure
*
* @returns
* new capacity
*
*/
size_t DynArr_reserve(size_t n);
It can do everything your current interface can do and more but is simpler to use and more efficient.
Why is there add and push?
The functions addDynArr and pushDynArr do exactly the same thing. I don't think that you need both. Just stick with push for the stack semantics.
Make removing elements more convenient
Suppose I have a DynArr and want to remove all occurrences of 42 from it. How do you code it?
while (DynArr_contains(array, 42)) {
DynArr_remove(42);
}
This is not only awkward to write but also hilariously inefficient.
I would recommend the following improvement to your interface.
/**
* Removes the first occurrence of a value from the array and shifts the
* remaining elements towards the front.
*
* If the value is not found, then this function has no effect.
*
* @param self
* `DynArr` to operate on
*
* @param value
* value to remove
*
* @returns
* whether the value was found and removed
*
*/
bool DynArr_remove(DynArr * self, int value);
/**
* Removes all occurrence of a value from the array, shifting the remaining
* elements towards the front.
*
* @param self
* `DynArr` to operate on
*
* @param value
* value to remove
*
* @returns
* number of removed occurrences
*
*/
size_t DynArr_removeAll(DynArr * self, int value);
If you implement it wisely, removeAll can be much more efficient than calling remove repetitively.
Think about shrinking your backing storage again
You have implemented a strategy of doubling the capacity of your array when needed, which is good. However, your capacity never shrinks again when elements are removed from the DynArr. This is a valid choice but not the only possible one.
If you decide to shrink, be sure to do it like this: If the size drops below 1/4 of the capacity, reduce the capacity to twice the size. If you shrink more, your operations can become very inefficient.
Be lazy or else do useful stuff
Your containsDynArr function always loops over the entire array even if it has already found the value. It should either return true immediately or else count the elements that are equal to the target value and return that count. (Of course, such a function should then be named DynArr_count, not DynArr_contains.)
Keep interfaces small
Are all your functions really needed in this interface? For example, the algorithms to remove elements, check whether they are present or swap their values can all be implemented via the public interface to query the array size and access elements by-index. If you guarantee that your internal storage is contiguous, I can even take the address of the first element and use it as a pointer to a raw array. C is a language that doesn't encourage generic programming but you can still draw ideas from it.
There is a bug in _dynArrSetCapacity
The statement v = temp in _dynArrSetCapacity has no effect outside the function, which means that the entire function does basically nothing. You should assign *v = *temp. Before you do that, you should call DynArr_fini(v) or you will leak the memory for the old array.
Don't cast the result of malloc
C has the infamous rule that void * is implicitly convertible to any pointer type. So you can just write
int * p = malloc(100 * sizeof(int));
and it is perfectly correct. Casting explicitly to int * brings no benefit and might hide other bugs.
See this post on stack Overflow for a more detailed discussion.
Avoid uninitialized variables
You have a lot of code of the following form.
int foo;
// …
foo = something();
This is an unnecessary potential entry hole for bugs. If you only declare the variable in the same statement that initializes it
int foo = something();
the code will become shorter and you cannot accidentally use foo uninitialized.
Trust boolean logic
This logic
if (v->size == 0) {
return 1;
}
else {
return 0;
}
is convoluted. Truth is not how you define it. Just use
return (v->size == 0);
instead. The parenthesis are not needed but I prefer to parenthesize expressions with logical comparisons for readability.
Consider using memcpy and memmove instead of manual loops
The standard library has highly optimized routines available to copy memory:
memcpy if the regions don't overlap for sure andmemmove if the regions might overlap.
Consider using them in your code for simplicity and performance.
Consider using ralloc to grow or shrink your storage
The standard library already provides the realloc function to grow or shrink an allocated buffer while keeping its contents (those that were valid before and are still valid afterwards) intact. Consider using it for performance and simplicity.
