Multi-purpose generic pointer array with optional type-checking

Question

I've been using this data structure in my projects for a while and finally decided to clean it up a bit and publish it online, but first I'm posting it here for code review. (EDIT: It has now been published on github if anyone is interested.)

It's simply a dynamic array of void pointers with lots of different functions that allow it to be used for all kinds of purposes. In some ways, it's similar to Javascript's arrays as they can also be used as more than just arrays e.g. stacks or queues. The main benefit of this is that I only ever need the one parray.h instead of having to write a separate one for each purpose (e.g. a separate pstack.h and pqueue.h for stacks and queues respectively).

The basic parray works with void pointers, allowing it to contain pointers to any kind of data. As an optional extension, the PARRAY_TYPED macro can be used to enforce type-checking through generated wrapper-functions. Because it is only an extension and StackExchange doesn't format macros very well you may want to skip over the macro section when reading the code. All the important functionality (along with documentation in the form of comments) comes after it anyway.

The code below is in the form of a header-only library. Anyone unfamiliar with this can (roughly) think of everything before #ifdef PARRAY_IMPLEMENTATION as being the header file, and everything after as being the source file.

//include only once
#ifndef PARRAY_H
#define PARRAY_H
//process configuration
#ifdef PARRAY_STATIC
 #define PARRAY_IMPLEMENTATION
 #define PADEF static
#else //PARRAY_EXTERN
 #define PADEF extern
#endif
//macros
#define PARRAY_TYPED(TYPE, NAME, FUNC) \
 TYPE; struct NAME; \
 static struct NAME* FUNC##New () { \
 return (struct NAME*)parrayNew(); \
 } \
 static int FUNC##Length (struct NAME* parr) { \
 return parrayLength((struct parray*)parr); \
 } \
 static int FUNC##Set (struct NAME* parr, int ind, TYPE* ele) { \
 return parraySet((struct parray*)parr, ind, (void*)ele); \
 } \
 static int FUNC##IndexOf (struct NAME* parr, TYPE* ele) { \
 return parrayIndexOf((struct parray*)parr, (void*)ele); \
 } \
 static TYPE* FUNC##Get (struct NAME* parr, int ind) { \
 return (TYPE*)parrayGet((struct parray*)parr, ind); \
 } \
 static TYPE* FUNC##GetFirst (struct NAME* parr) { \
 return (TYPE*)parrayGetFirst((struct parray*)parr); \
 } \
 static TYPE* FUNC##GetLast (struct NAME* parr) { \
 return (TYPE*)parrayGetLast((struct parray*)parr); \
 } \
 static void FUNC##Clear (struct NAME* parr) { \
 parrayClear((struct parray*)parr); \
 } \
 static void FUNC##Free (struct NAME* parr) { \
 parrayFree((struct parray*)parr); \
 } \
 static int FUNC##Push (struct NAME* parr, TYPE* ele) { \
 return parrayPush((struct parray*)parr, (void*)ele); \
 } \
 static TYPE* FUNC##Pop (struct NAME* parr) { \
 return (TYPE*)parrayPop((struct parray*)parr); \
 } \
 static TYPE* FUNC##Dequeue (struct NAME* parr) { \
 return (TYPE*)parrayDequeue((struct parray*)parr); \
 } \
 static int FUNC##FindIndex (struct NAME* parr, int(*comp)(const void*, const TYPE**), const void* key) { \
 return parrayFindIndex((struct parray*)parr, (int(*)(const void*, const void**))comp, key); \
 } \
 static TYPE* FUNC##FindElement (struct NAME* parr, int(*comp)(const void*, const TYPE**), const void* key) { \
 return (TYPE*)parrayFindElement((struct parray*)parr, (int(*)(const void*, const void**))comp, key); \
 } \
 static void FUNC##SortInsert (struct NAME* parr, int(*comp)(const TYPE**, const TYPE**)) { \
 parraySortInsert((struct parray*)parr, (int(*)(const void**, const void**))comp); \
 } \
 static void FUNC##SortStandard (struct NAME* parr, int(*comp)(const TYPE**, const TYPE**)) { \
 parraySortStandard((struct parray*)parr, (int(*)(const void**, const void**))comp); \
 } \
 static int FUNC##Insert (struct NAME* parr, int ind, TYPE* ele) { \
 return parrayInsert((struct parray*)parr, ind, (void*)ele); \
 } \
 static TYPE* FUNC##Remove (struct NAME* parr, int ind) { \
 return (TYPE*)parrayRemove((struct parray*)parr, ind); \
 } \
 static TYPE* FUNC##Ditch (struct NAME* parr, int ind) { \
 return (TYPE*)parrayDitch((struct parray*)parr, ind); \
 } \
 static int FUNC##Capacity (struct NAME* parr, int cap) { \
 return parrayCapacity((struct parray*)parr, cap); \
 }
//structs
struct parray; //forward declaration
//general functions
PADEF struct parray* parrayNew();
 //creates a new parray instance and returns a pointer to it
PADEF int parrayLength(struct parray*);
 //returns the current number of elements in the given parray
PADEF int parraySet(struct parray*, int, void*);
 //overwrites the element at given index in given parray with given value
 //returns the index the value was placed at, or -1 on failure
PADEF int parrayIndexOf(struct parray*, void*);
 //returns the index of given element in given parray, -1 if not found
PADEF void* parrayGet(struct parray*, int);
 //returns the element at the given index in given parray, or NULL on failure
PADEF void* parrayGetFirst(struct parray*);
 //returns the first element in the given parray, or NULL if empty
PADEF void* parrayGetLast(struct parray*);
 //returns the last element in the given parray, or NULL if empty
PADEF void parrayClear(struct parray*);
 //clears the given parray of all its elements
PADEF void parrayFree(struct parray*);
 //frees the given parray and all its internal data
//stack-like functions
PADEF int parrayPush(struct parray*, void*);
 //appends the given element to the end of the given parray and returns its index
PADEF void* parrayPop(struct parray*);
 //removes the last element in the given parray and returns it (NULL if empty)
//queue-like functions
PADEF void* parrayDequeue(struct parray*);
 //removes the first element in the given parray and returns it (NULL if empty)
//sort/search functions
PADEF int parrayFindIndex(struct parray*, int(*)(const void*, const void**), const void*);
 //returns the index of an element that evaluates as equal to given key according to given function
 //parray must be sorted for this function to work correctly, otherwise the result is undefined
PADEF void* parrayFindElement(struct parray*, int(*)(const void*, const void**), const void*);
 //returns an element that evaluates as equal to given key according to given comparison function
 //parray must be sorted for this function to work correctly, otherwise the result is undefined
PADEF void parraySortInsert(struct parray*, int(*)(const void**, const void**));
 //insertion sorts the elements in the given parray according to given comparison function
 //comparison function should return 1 if first argument is greater than second argument
 //0 if it is equal, and -1 if it is smaller, parray will be sorted smallest to greatest
PADEF void parraySortStandard(struct parray*, int(*)(const void**, const void**));
 //same as parraySortInsert but uses the C standard qsort function for sorting instead
//insert/remove functions
PADEF int parrayInsert(struct parray*, int, void*);
 //inserts the given element at the given index in given parray, shifting other elements forward
 //returns the index the element was placed at, or -1 on failure
PADEF void* parrayRemove(struct parray*, int);
 //removes and returns the element at given index while maintaining order of remaining elements
 //returns NULL if given index is outside the bounds of the parray
PADEF void* parrayDitch(struct parray*, int);
 //faster alternative to parrayRemove that doesn't maintain order of remaining elements
//memory-related functions
PADEF int parrayCapacity(struct parray*, int);
 //adjusts the internal capacity of the given parray to most closely match the given number of elements
 //returns the resulting capacity after resizing, which may not match what was requested
//implementation section
#ifdef PARRAY_IMPLEMENTATION
//includes
#include <stdlib.h> //memory allocation
#include <string.h> //memmove/memcpy
//structs
struct parray {
 int offset;
 int length;
 int capacity;
 void** data;
};
//general functions
PADEF struct parray* parrayNew () {
 //creates a new parray instance and returns a pointer to it
 struct parray* parr = malloc(sizeof(struct parray));
 parr->offset = parr->length = 0; parr->capacity = 8; //initial capacity of 8
 parr->data = malloc(sizeof(void*)*parr->capacity);
 //return
 return parr;
}
PADEF int parrayLength (struct parray* parr) {
 //returns the current number of elements in the given parray
 return parr->length;
}
PADEF int parraySet (struct parray* parr, int ind, void* ele) {
 //overwrites the element at given index in given parray with given value
 //returns the index the value was placed at, or -1 on failure
 if ((ind < 0)||(ind >= parr->length)) return -1;
 parr->data[parr->offset+ind] = ele;
 return ind;
}
PADEF int parrayIndexOf (struct parray* parr, void* ele) {
 //returns the index of given element in given parray, -1 if not found
 for (int i = 0; i < parr->length; i++)
 if (parr->data[parr->offset+i] == ele) return i;
 return -1;
}
PADEF void* parrayGet (struct parray* parr, int ind) {
 //returns the element at the given index in given parray, or NULL on failure
 if ((ind < 0)||(ind >= parr->length)) return NULL;
 return parr->data[parr->offset+ind];
}
PADEF void* parrayGetFirst (struct parray* parr) {
 //returns the first element in the given parray, or NULL if empty
 if (!parr->length) return NULL;
 return parr->data[parr->offset];
}
PADEF void* parrayGetLast (struct parray* parr) {
 //returns the last element in the given parray, or NULL if empty
 if (!parr->length) return NULL;
 return parr->data[parr->offset+parr->length-1];
}
PADEF void parrayClear (struct parray* parr) {
 //clears the given parray of all its elements
 parr->offset = parr->length = 0;
}
PADEF void parrayFree (struct parray* parr) {
 //frees the given parray and all its internal data
 free(parr->data); free(parr);
}
//stack-like functions
PADEF int parrayPush (struct parray* parr, void* ele) {
 //appends the given element to the end of the given parray and returns its index
 if (parr->offset+parr->length == parr->capacity)
 if (parr->offset >= parr->length) {
 //double the available capacity by offset reset
 memcpy(&parr->data[0], &parr->data[parr->offset], sizeof(void*)*parr->length);
 parr->offset = 0;
 } else {
 //double the available capacity by reallocation
 parr->data = realloc(parr->data, sizeof(void*)*(parr->capacity *= 2));
 }
 parr->data[parr->offset+parr->length] = ele;
 return parr->length++;
}
PADEF void* parrayPop (struct parray* parr) {
 //removes the last element in the given parray and returns it (NULL if empty)
 if (!parr->length) return NULL;
 parr->length--; //reduce length
 return parr->data[parr->offset+parr->length];
}
//queue-like functions
PADEF void* parrayDequeue (struct parray* parr) {
 //removes the first element in the given parray and returns it (NULL if empty)
 if (!parr->length) return NULL;
 parr->length--; //reduce length
 return parr->data[parr->offset++];
}
//sort/search functions
PADEF int parrayFindIndex (struct parray* parr, int(*comp)(const void*, const void**), const void* key) {
 //returns the index of an element that evaluates as equal to given value according to given function
 //parray must be sorted for this function to work correctly, otherwise the result is undefined
 void** res = bsearch(key, &parr->data[parr->offset], parr->length, sizeof(void*), (int(*)(const void*, const void*))comp);
 if (!res) return -1; //element not found
 return (res - &parr->data[parr->offset])/(sizeof(void*));
}
PADEF void* parrayFindElement (struct parray* parr, int(*comp)(const void*, const void**), const void* key) {
 //returns an element that evaluates as equal to given value according to given comparison function
 //parray must be sorted for this function to work correctly, otherwise the result is undefined
 void** res = bsearch(key, &parr->data[parr->offset], parr->length, sizeof(void*), (int(*)(const void*, const void*))comp);
 if (!res) return NULL; //element not found
 return *res;
}
PADEF void parraySortInsert (struct parray* parr, int(*comp)(const void**, const void**)) {
 //insertion sorts the elements in the given parray according to given comparison function
 //comparison function should return 1 if first argument is greater than second argument
 //0 if it is equal, and -1 if it is smaller, parray will be sorted smallest to greatest
 for (int j = 1; j < parr->length; j++)
 for (int i = parr->offset+j; (i > parr->offset)&&(comp((const void**)&parr->data[i-1], (const void**)&parr->data[i]) > 0); i--) {
 void* temp = parr->data[i];
 parr->data[i] = parr->data[i-1];
 parr->data[i-1] = temp;
 }
}
PADEF void parraySortStandard (struct parray* parr, int(*comp)(const void**, const void**)) {
 //same as parraySortInsert but uses the C standard qsort function for sorting instead
 qsort(&parr->data[parr->offset], parr->length, sizeof(void*), (int(*)(const void*, const void*))comp);
}
//insert/remove functions
PADEF int parrayInsert (struct parray* parr, int ind, void* ele) {
 //inserts the given element at the given index in given parray, shifting other elements forward
 //returns the index the element was placed at, or -1 on failure
 if ((ind < 0)||(ind >= parr->length)) return -1;
 if (parr->offset+parr->length == parr->capacity)
 if (parr->offset >= parr->length) {
 memcpy(&parr->data[0], &parr->data[parr->offset], parr->length);
 parr->offset = 0;
 } else
 parr->data = realloc(parr->data, sizeof(void*)*(parr->capacity *= 2));
 memmove(&parr->data[parr->offset+ind+1], &parr->data[parr->offset+ind], sizeof(void*)*(parr->length-ind));
 parr->data[parr->offset+ind] = ele; parr->length++;
 return ind;
}
PADEF void* parrayRemove (struct parray* parr, int ind) {
 //removes and returns the element at given index while maintaining order of remaining elements
 //returns NULL if given index is outside the bounds of the parray
 if ((ind < 0)||(ind >= parr->length)) return NULL;
 void* ele = parr->data[parr->offset+ind]; parr->length--;
 memmove(&parr->data[parr->offset+ind], &parr->data[parr->offset+ind+1], sizeof(void*)*(parr->length-ind));
 return ele;
}
PADEF void* parrayDitch (struct parray* parr, int ind) {
 //faster alternative to parrayRemove that doesn't maintain order of remaining elements
 if ((ind < 0)||(ind >= parr->length)) return NULL;
 void* ele = parr->data[parr->offset+ind]; parr->data[parr->offset+ind] = parrayPop(parr);
 return ele;
}
//memory-related functions
PADEF int parrayCapacity (struct parray* parr, int cap) {
 //adjusts the internal capacity of the given parray to most closely match the given number of elements
 //returns the resulting capacity after resizing, which may not match what was requested
 if (cap < parr->length) cap = parr->length;
 if (parr->offset) {
 memmove(&parr->data[0], &parr->data[parr->offset], parr->length);
 parr->offset = 0;
 }
 parr->data = realloc(parr->data, sizeof(void*)*(parr->capacity = cap));
 return parr->capacity;
}
#endif //PARRAY_IMPLEMENTATION
#endif //PARRAY_H

• πάντα ῥεῖ: C provides type safety, just use it!
• Wingblade: @πάνταῥεῖ What are you talking about? If you want a generic pointer array there's nothing better than void* and if you don't there's PARRAY_TYPED which leverages C's type safety, I'm not sure I understand your objection.
• πάντα ῥεῖ: Just take a look at what's implemented with inet_addr. There's no need for void* pointers as long you're able to avoid completely opaque pointers. If not, use handles, instead.
• Wingblade: @πάνταῥεῖ I think you misunderstand. Using void* is the point, giving you a generic pointer array that'll store any kind of pointer (even different kinds together), PARRAY_TYPED is then simply an extension ontop of that for when you want only one kind of pointer (e.g. struct foo* instead of void*).
• Wingblade: @chux Just generic as-in void pointers, so just for objects/data and not functions. PARRAY_TYPED then optionally allows you to get specific to just one type of pointer, e.g. only struct foo*.

Answer 1

1. Any form of container should use minimal resources when empty. In parrayNew(), I recommend parr->capacity = 0; parr->data = NULL;

2. parrayFree(), like free() should tolerate parrayFree(NULL). Add NULL check.

3. malloc()/realloc() calls lack NULL checks.

4. Rather than allocate to the sizeof a type, allocate to the sizeof of the element. It is easier to code right, review and maintain.

   //parr->data = malloc(sizeof(void*)*parr->capacity);
   parr->data = malloc(sizeof *(parr->data) * parr->capacity);
   // or 
   parr->data = malloc(sizeof parr->data[0] * parr->capacity);
   

5. (削除) Bug? Test in parraySet()/parrayGet() looks wrong: (削除ここまで) Hmm, I'll review later.

   // if ((ind < 0)||(ind >= parr->length)) return -1;
   if ((ind < 0)||((parr->offset+ind) >= parr->length)) return -1;
   parr->data[parr->offset+ind] = ele;
   

6. Questionable architecture: The below does not distinguish between returning NULL as a error condition and NULL as the value of parr->data[parr->offset+ind]. This restricts use of this generic container. Better to use an alternative to indicate range error. Perhaps instead return the address of the element or pass in a destination parameter?

   if ((ind < 0)||(ind >= parr->length)) return NULL;
   return parr->data[parr->offset+ind];
   

7. Bug

   // memcpy(&parr->data[0], &parr->data[parr->offset], parr->length);
   memcpy(&parr->data[0], &parr->data[parr->offset], parr->length*sizeof parr->data[0]);
   

8. Do not recommend repeated comments. Functions definitions repeat the comment of the function declarations. This eventually breaks down with maintenance. Comment well the declaration and in the definition refer to the declaration comments. Stay DRY.

9. For arithmetic compares, I prefer arithmetic operators rather than logical ones:

   // if (!parr->length) return NULL;
   if (parr->length <= 0) return NULL;
   

10. Lack of {} tends to incur maintenance problems. Better to add them.

    // if (parr->offset+parr->length == parr->capacity)
    // if (parr->offset >= parr->length) {
    // memcpy(&parr->data[0], &parr->data[parr->offset], parr->length);
    // parr->offset = 0;
    // } else
    // parr->data = realloc(parr->data, sizeof(void*)*(parr->capacity *= 2));
    if (parr->offset+parr->length == parr->capacity) {
     if (parr->offset >= parr->length) {
     memcpy(&parr->data[0], &parr->data[parr->offset], parr->length);
     parr->offset = 0;
     } else
     parr->data = realloc(parr->data, sizeof(void*)*(parr->capacity *= 2));
     }
    

11. For functions that do not change struct parray, add const to better convey codes intent and allow for some optimizations and wider application.

     // parrayGet (struct parray* parr, int ind) 
     parrayGet (const struct parray* parr, int ind) 
    

• chux: Maybe more later, GTG.
• Wingblade: 1, 2: Agree. 3: If more memory cannot be allocated, that's a fatal error and there's no alternative to just failing outright, is there? 4: Fair point. 6: Don't disagree, but not convinced by your alternative. Perhaps the solution is to think of values outside the actual array as empty space, for which NULL is an appropriate representation. 7: Good catch. 8: Strongly believe in DRY myself, disagree it applies to comments. Could see keeping comments only in definitions as this is single-file. 9, 10: Fair points, but down to subjective coding style. 11: Considered this myself, will change.
• chux: @Wingblade " there's no alternative to just failing outright, is there?" the 2 usually candidates are to 1) exit right away (maybe with a message) and 2) return to the calling code in a manner to let it know allocation failed and let the caller handle it. Presently this code does neither. A 3rd idea is to call an error handler that is re-definable by the user. There is no "best" and it is highly case dependent. OTOH, there are weak approaches including "nothing".
• Wingblade: AFAIK C provides no facilities to exit with a message (no throw "ERROR MESSAGE";). Presently the code does do an implicit form of option 1 as it (should) produce a crash through de-referencing the returned NULL pointer, and a crash is what you'd expect from most applications when RAM runs out (I have yet to see an application that doesn't crash on OOM). Now it's not great, but a true "nothing" approach like returning without doing anything would be much worse and harder to debug.
• chux: @Wingblade "as it (should) produce a crash through de-referencing the returned NULL pointer" --> C does not specify this. De-referencing a NULL is undefined behavior. On OOM, I'd expect an indication, as code is able to report (case specific) the OOM event and then exit, not crash. "a crash is what you'd expect from most applications when RAM runs out" --> is not robust programming. Code as you like but crashing is usually not acceptable when selling your application.