The code below is an attempt to mimic std::vector from the C++ standard library in the C language.
The implementation is purely macros, in the C99 dialect, and requires the non-standard __typeof__ keyword.
I am interested to learn of both coding mistakes and design mistakes.
The project resides on SourceForge, in case example code is needed for the review process.
//
// ctnr - Containers for the C language
//
// Written in 2016 by Andrei Bondor, [email protected]
//
// To the extent possible under law, the author(s) have dedicated all copyright
// and related and neighboring rights to this software to the public domain
// worldwide. This software is distributed without any warranty.
//
// You should have received a copy of the CC0 Public Domain Dedication along
// with this software (as file "copying.txt"). If not, see:
//
// http://creativecommons.org/publicdomain/zero/1.0/
//
///
/// @file
/// @brief Implements the Dynamic Array data structure.
/// @details
///
/// Memory management:
/// ------------------
/// DYNARRAY_MALLOC
/// DYNARRAY_REALLOC
/// DYNARRAY_FREE
///
/// General functions:
/// ------------------
/// DynArrayType dynarray (ElemType)
/// bool dynarray_create (DynArray, Capacity)
/// void dynarray_ptrcopy (DynArray, ElemPtr, Count)
/// void dynarray_destroy (DynArray)
/// void dynarray_clear (DynArray)
/// size_t dynarray_size (DynArray)
/// void dynarray_search (DynArray, ValidFunc, DynArrayRes)
/// void dynarray_count (DynArray, ElemVal, CountRes)
/// bool dynarray_empty (DynArray)
///
/// Iterator support:
/// -----------------
/// ElemIterType dynarrayiter (DynArray)
/// ElemVal dynarrayiter_deref (ElemIter)
/// void dynarrayiter_inc (ElemIter)
/// ElemIter dynarrayiter_begin (DynArray)
/// ElemIter dynarrayiter_end (DynArray)
///
/// Container-specific functions:
/// -----------------------------
/// size_t dynarray_capacity (DynArray)
/// void dynarray_reserve (DynArray, Capacity)
/// void dynarray_resize (DynArray, Count)
/// void dynarray_resizefill (DynArray, Count, ElemVal)
/// void dynarray_pushfront (DynArray, ElemVal)
/// void dynarray_pushback (DynArray, ElemVal)
/// void dynarray_insert (DynArray, Index, ElemVal)
/// void dynarray_remove (DynArray, Index)
/// void dynarray_fill (DynArray, ElemVal)
/// void dynarray_popfront (DynArray)
/// void dynarray_popback (DynArray)
/// ElemPtr dynarray_ptrdata (DynArray)
/// ElemVal dynarray_front (DynArray)
/// ElemVal dynarray_back (DynArray)
/// ElemVal dynarray_at (DynArray, Index)
///
/// Debugging support:
/// ------------------
/// void dynarray_print (DynArray, Format, Stream)
///
#pragma once
#define VERSION_DYNARRAY 1000
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#ifndef DYNARRAY_MALLOC
#define DYNARRAY_MALLOC malloc
#endif
#ifndef DYNARRAY_REALLOC
#define DYNARRAY_REALLOC realloc
#endif
#ifndef DYNARRAY_FREE
#define DYNARRAY_FREE free
#endif
///
/// @brief Retrieves the type of the Dynamic Array containing `ElemType`.
/// @details This macro is needed for declaring the Dynamic Array objects.
///
#define dynarray(ElemType) \
struct { \
ElemType *data; \
size_t count; \
size_t capacity; \
}
///
/// @brief Creates a new Dynamic Array with a capacity of `Capacity` elements.
/// @param [out] DynArray The Dynamic Array.
/// @param [in] Capacity The capacity of the Dynamic Array.
/// @returns Whether or not the operation was successful.
/// @retval true OK.
/// @retval false Failure (most likely due to memory
/// allocation).
///
#define dynarray_create(DynArray, Capacity) ( \
(DynArray).data = DYNARRAY_MALLOC((Capacity) * (sizeof *(DynArray).data)), \
(DynArray).count = 0, \
(DynArray).capacity = (DynArray).data != NULL ? (Capacity) : 0, \
(DynArray).data != NULL \
)
///
/// @brief Copies `Count` elements from `ElemPtr` to the Dynamic Array.
/// @warning The old contents of the Dynamic Array will be lost.
/// @remarks If needed memory cannot be allocated, the contents of the
/// Dynamic Array will not be changed.
/// @param [out] DynArray The Dynamic Array.
/// @param [in] ElemPtr Pointer to the elements array.
/// @param [in] Count Number of elements to be copied.
///
#define dynarray_ptrcopy(DynArray, ElemPtr, Count) if (true) { \
void *ptrdata = DYNARRAY_REALLOC( \
(DynArray).data, \
(sizeof *(DynArray).data) * (Count)); \
if (ptrdata != NULL) { \
(DynArray).data = ptrdata; \
(DynArray).count = (Count); \
(DynArray).capacity = (Count); \
memcpy( \
(DynArray).data, \
(ElemPtr), \
(sizeof *(DynArray).data) * (Count)); \
} \
} else (void)0
///
/// @brief Destroys the Dynamic Array.
/// @param [out] DynArray The Dynamic Array.
///
#define dynarray_destroy(DynArray) if (true) { \
DYNARRAY_FREE((DynArray).data); \
(DynArray).count = 0; \
(DynArray).capacity = 0; \
} else (void)0
///
/// @brief Clears the data from the Dynamic Array.
/// @note Actually it just sets the element count to 0.
/// @param [in,out] DynArray The Dynamic Array.
///
#define dynarray_clear(DynArray) if (true) { \
(DynArray).count = 0; \
} else (void)0
///
/// @brief Returns the number of elements in the Dynamic Array.
/// @param [in] DynArray The Dynamic Array.
/// @returns `DynArray.count`.
///
#define dynarray_size(DynArray) ( \
(DynArray).count \
)
///
/// @brief Searches the Dynamic Array for elements that satisfy `ValidFunc`
/// and stores the results in `DynArrayRes`.
/// @param [in] DynArray The Dynamic Array to be searched.
/// @param [in] ValidFunc Function or macro to check which elements
/// are valid.
/// @param [out] DynArrayRes The Dynamic Array to store the search
/// results.
/// @note `ValidFunc` will be used as if it had the signature:
/// `bool ValidFunc(ElemType)`
/// @note `DynArrayRes` is a Dynamic Array created and destroyed by the caller.
/// Its old contents will be cleared by this function.
///
#define dynarray_search(DynArray, ValidFunc, DynArrayRes) if (true) { \
dynarray_clear(DynArrayRes); \
for (size_t i=0; i < (DynArray).count; ++i) { \
if (ValidFunc((DynArray).data[i])) { \
dynarray_pushback((DynArrayRes), (DynArray).data[i]); \
} \
} \
} else (void)0
///
/// @brief Searches the Dynamic Array for elements equal to `ElemVal`
/// and stores the total number in `CountRes`.
/// @param [in] DynArray The Dynamic Array to be searched.
/// @param [in] ElemVal Element value to search for.
/// @param [out] CountRes Count of elements.
///
#define dynarray_count(DynArray, ElemVal, CountRes) if (true) { \
(CountRes) = 0; \
for (size_t i=0; i < (DynArray).count; ++i) { \
if ((DynArray).data[i] == (ElemVal)) { \
++(CountRes); \
} \
} \
} else (void)0
///
/// @brief Returns if the Dynamic Array is empty.
/// @param [in] DynArray The Dynamic Array.
/// @retval true The Dynamic Array is empty.
/// @retval false The Dynamic Array has elements.
///
#define dynarray_empty(DynArray) ( \
(DynArray).count == 0 \
)
///
/// @brief Retrieves the iterator type of a Dynamic Array containing `ElemType`.
/// @details This macro is needed for declaring the Dynamic Array iterators.
/// @param [in] DynArray The Dynamic Array.
///
#define dynarrayiter(DynArray) \
__typeof__ ((DynArray).data)
///
/// @brief Dereferences the `ElemIter` iterator to retrieve the element value.
/// @param [in] ElemIter The Element Iterator.
/// @returns The element data.
///
#define dynarrayiter_deref(ElemIter) ( \
*(ElemIter) \
)
///
/// @brief Increments the `ElemIter` iterator.
/// @param [in,out] ElemIter The Element Iterator.
///
#define dynarrayiter_inc(ElemIter) ( \
++(ElemIter) \
)
///
/// @brief Returns iterator to the beginning of the Dynamic Array.
/// @param [in] DynArray The Dynamic Array.
/// @returns Pointer to the first element.
///
#define dynarrayiter_begin(DynArray) ( \
(DynArray).data \
)
///
/// @brief Returns iterator to the end of the Dynamic Array.
/// @param [in] DynArray The Dynamic Array.
/// @returns Pointer to the imaginary element after the last one.
///
#define dynarrayiter_end(DynArray) ( \
(DynArray).data + (DynArray).count \
)
///
/// @brief Returns how many elements can be stored in the Dynamic Array.
/// @param [in] DynArray The Dynamic Array.
/// @returns `DynArray.capacity`.
///
#define dynarray_capacity(DynArray) ( \
(DynArray).capacity \
)
///
/// @brief Reserves memory in the Dynamic Array.
/// @remarks If needed memory cannot be allocated, the contents of the
/// Dynamic Array will not be changed.
/// @param [in,out] DynArray The Dynamic Array.
/// @param [in] Capacity How many elements the Dynamic Array must
/// hold.
///
#define dynarray_reserve(DynArray, Capacity) if (true) { \
void *ptrdata = DYNARRAY_REALLOC( \
(DynArray).data, \
(sizeof *(DynArray).data) * (Capacity)); \
if (ptrdata != NULL) { \
(DynArray).data = ptrdata; \
(DynArray).count = (Capacity) < (DynArray).count ? \
(Capacity) : (DynArray).count; \
(DynArray).capacity = (Capacity); \
} \
} else (void)0
///
/// @brief Resizes the Dynamic Array to hold `Count` elements.
/// @remarks If `Count` is the same as the original element count,
/// nothing will be done.
/// @remarks Memory allocation will only occur if `Count` is greater
/// than the original element count.
/// @remarks If needed memory cannot be allocated, the contents of the
/// Dynamic Array will not be changed.
/// @param [in,out] DynArray The Dynamic Array.
/// @param [in] Count How many elements the Dynamic Array must
/// hold.
///
#define dynarray_resize(DynArray, Count) if (true) { \
if ((DynArray).count > (Count)) { \
(DynArray).count = (Count); \
} else \
if ((DynArray).count < (Count)) { \
void *ptrdata = DYNARRAY_REALLOC( \
(DynArray).data, \
(sizeof *(DynArray).data) * (Count)); \
if (ptrdata != NULL) { \
(DynArray).data = ptrdata; \
(DynArray).count = (Count); \
(DynArray).capacity = (Count); \
} \
} \
} else (void)0
///
/// @brief Resizes the Dynamic Array to hold `Count` elements.
/// New, if any, elements will be assigned `ElemVal`.
/// @remarks If `Count` is the same as the original element count,
/// nothing will be done.
/// @remarks Memory allocation will only occur if `Count` is greater
/// than the original element count.
/// @remarks If needed memory cannot be allocated, the contents of the
/// Dynamic Array will not be changed.
/// @param [in,out] DynArray The Dynamic Array.
/// @param [in] Count How many elements the Dynamic Array must
/// hold.
/// @param [in] ElemVal Default value for new elements.
///
#define dynarray_resizefill(DynArray, Count, ElemVal) if (true) { \
if ((DynArray).count > (Count)) { \
(DynArray).count = (Count); \
} else \
if ((DynArray).count < (Count)) { \
void *ptrdata = DYNARRAY_REALLOC( \
(DynArray).data, \
(sizeof *(DynArray).data) * (Count)); \
if (ptrdata != NULL) { \
(DynArray).data = ptrdata; \
const size_t begin = (DynArray).count; \
const size_t end = (Count); \
for (size_t i = begin; i < end; ++i) { \
(DynArray).data[i] = (ElemVal); \
} \
(DynArray).count = (Count); \
(DynArray).capacity = (Count); \
} \
} \
} else (void)0
///
/// @brief Adds a new element to the front of the Dynamic Array.
/// @remarks The capacity will be more than doubled if it is too low.
/// @remarks If needed memory cannot be allocated, the contents of the
/// Dynamic Array will not be changed.
/// @param [in,out] DynArray The Dynamic Array.
/// @param [in] ElemVal Value of the element to be added.
///
#define dynarray_pushfront(DynArray, ElemVal) if (true) { \
void *ptrdata = (DynArray).data; \
size_t ncapacity = (DynArray).capacity; \
if ((DynArray).count + 1 > (DynArray).capacity) { \
ptrdata = DYNARRAY_REALLOC( \
(DynArray).data, \
(sizeof *(DynArray).data) * ((DynArray).count + 1) * 2); \
ncapacity = ((DynArray).count + 1) * 2; \
} \
if (ptrdata != NULL) { \
memmove( \
(unsigned char *)ptrdata + (sizeof *(DynArray).data), \
ptrdata, \
(sizeof *(DynArray).data) * (DynArray).count); \
(DynArray).data = ptrdata; \
(DynArray).data[0] = (ElemVal); \
(DynArray).count += 1; \
(DynArray).capacity = ncapacity; \
} \
} else (void)0
///
/// @brief Adds a new element to the back of the Dynamic Array.
/// @remarks The capacity will be more than doubled if it is too low.
/// @remarks If needed memory cannot be allocated, the contents of the
/// Dynamic Array will not be changed.
/// @param [in,out] DynArray The Dynamic Array.
/// @param [in] ElemVal Value of the element to be added.
///
#define dynarray_pushback(DynArray, ElemVal) if (true) { \
void *ptrdata = (DynArray).data; \
size_t ncapacity = (DynArray).capacity; \
if ((DynArray).count + 1 > (DynArray).capacity) { \
ptrdata = DYNARRAY_REALLOC( \
(DynArray).data, \
(sizeof *(DynArray).data) * ((DynArray).count + 1) * 2); \
ncapacity = ((DynArray).count + 1) * 2; \
} \
if (ptrdata != NULL) { \
(DynArray).data = ptrdata; \
(DynArray).data[(DynArray).count] = (ElemVal); \
(DynArray).count += 1; \
(DynArray).capacity = ncapacity; \
} \
} else (void)0
///
/// @brief Adds a new element at the index `Index` in the Dynamic Array.
/// @remarks The capacity will be more than doubled if it is too low.
/// @remarks If needed memory cannot be allocated, the contents of the
/// Dynamic Array will not be changed.
/// @param [in,out] DynArray The Dynamic Array.
/// @param [in] Index Index of the new element.
/// @param [in] ElemVal Value of the element to be added.
///
#define dynarray_insert(DynArray, Index, ElemVal) if (true) { \
void *ptrdata = (DynArray).data; \
size_t ncapacity = (DynArray).capacity; \
if ((DynArray).count + 1 > (DynArray).capacity) { \
ptrdata = DYNARRAY_REALLOC( \
(DynArray).data, \
(sizeof *(DynArray).data) * ((DynArray).count + 1) * 2); \
ncapacity = ((DynArray).count + 1) * 2; \
} \
if (ptrdata != NULL) { \
(DynArray).data = ptrdata; \
memmove( \
(DynArray).data + (Index) + 1, \
(DynArray).data + (Index), \
(sizeof *(DynArray).data) * ((DynArray).count - (Index))); \
(DynArray).data[(Index)] = (ElemVal); \
(DynArray).count += 1; \
(DynArray).capacity = ncapacity; \
} \
} else (void)0
///
/// @brief Removes the element at the index `Index` from the Dynamic Array.
/// @remarks If the Dynamic Array is empty, nothing will be done.
/// @param [in,out] DynArray The Dynamic Array.
/// @param [in] Index Index of the element to be removed.
///
#define dynarray_remove(DynArray, Index) if (true) { \
if ((DynArray).count != 0) { \
memmove( \
(DynArray).data + (Index), \
(DynArray).data + (Index) + 1, \
(sizeof *(DynArray).data) * ((DynArray).count - (Index) - 1)); \
(DynArray).count -= 1; \
} \
} else (void)0
///
/// @brief Fills the Dynamic Array will `ElemVal` values.
/// @warning The old contents of `DynArray` will be overwritten.
/// @param [in,out] DynArray The Dynamic Array.
/// @param [in] ElemVal New value for all elements.
///
#define dynarray_fill(DynArray, ElemVal) if (true) { \
for (size_t i=0; i < (DynArray).count; ++i) { \
(DynArray).data[i] = (ElemVal); \
} \
} else (void)0
///
/// @brief Removes the element at the front of the Dynamic Array.
/// @pre There must be at least one element in the Dynamic Array.
/// @param [in,out] DynArray The Dynamic Array.
///
#define dynarray_popfront(DynArray) if (true) { \
assert((DynArray).count != 0); \
memmove( \
(DynArray).data, \
(DynArray).data + 1, \
(sizeof *(DynArray).data) * ((DynArray).count - 1)); \
(DynArray).count -= 1; \
} else (void)0
///
/// @brief Removes the element at the back of the Dynamic Array.
/// @pre There must be at least one element in the Dynamic Array.
/// @param [in,out] DynArray The Dynamic Array.
///
#define dynarray_popback(DynArray) if (true) { \
assert((DynArray).count != 0); \
(DynArray).count -= 1; \
} else (void)0
///
/// @brief Returns a pointer to the raw data of the Dynamic Array.
/// @warning The returned pointer is invalid if the Dynamic Array contains
/// no elements.
/// @param [in] DynArray The Dynamic Array.
/// @returns Pointer to the first element.
///
#define dynarray_ptrdata(DynArray) ( \
(DynArray).data \
)
///
/// @brief Retrieves the element value at the front of the Dynamic Array.
/// @pre There must be at least one element in the Dynamic Array.
/// @note Precondition is not checked so that this macro can be used as a
/// modifiable lvalue.
/// @param [in] DynArray The Dynamic Array.
/// @returns The first element.
///
#define dynarray_front(DynArray) ( \
(DynArray).data[0] \
)
///
/// @brief Retrieves the element value at the back of the Dynamic Array.
/// @pre There must be at least one element in the Dynamic Array.
/// @note Precondition is not checked so that this macro can be used as a
/// modifiable lvalue.
/// @param [in] DynArray The Dynamic Array.
/// @returns The last element.
///
#define dynarray_back(DynArray) ( \
(DynArray).data[(DynArray).count - 1] \
)
///
/// @brief Returns the element value at `Index` in the Dynamic Array.
/// @warning No bounds checking shall be performed.
/// @param [in] DynArray The Dynamic Array.
/// @param [in] Index Index of the element to be retrieved.
/// @returns The requested element.
///
#define dynarray_at(DynArray, Index) ( \
(DynArray).data[(Index)] \
)
///
/// @brief Prints Dynamic Array information and contents to the `Stream` file
/// stream.
/// @param [in] DynArray The Dynamic Array.
/// @param [in] Format Format string for printing `ElemType`.
/// @param [in] Stream File stream to print to.
///
#define dynarray_print(DynArray, Format, Stream) if (true) { \
const size_t maxelem = 10; \
fprintf((Stream), "--- DYNAMIC ARRAY PRINT --------------------------\n"); \
fprintf((Stream), "`" #DynArray "` at %p\n\n", (void *)&(DynArray)); \
fprintf((Stream), "Size: %zu\n", (DynArray).count); \
fprintf((Stream), "Capacity: %zu\n", (DynArray).capacity); \
fprintf((Stream), "Data at: %p\n\n", (void *)(DynArray).data); \
fprintf((Stream), "Contents:\n"); \
for (size_t i=0; i < (DynArray).count; ++i) { \
if (i % maxelem == 0) { \
fprintf((Stream), " "); \
} \
fprintf((Stream), Format, (DynArray).data[i]); \
if ((i + 1) % maxelem == 0) { \
fprintf((Stream), "\n"); \
} \
} \
fprintf((Stream), "\n"); \
fprintf((Stream), "--------------------------------------------------\n"); \
} else (void)0
