Introduction
Everybody knows tree.h and queue.h in The FreeBSD Project. These macro-implemented data structures are always fascinating - they support arbitrary element type, extreme high performance and never fail.
In most of my embedded projects, I use the AVL tree implementation in tree.h for event management. When I need something like message queue, I use queue.h However there really isn't a decent implementation of vector in macro yet. So this is what this project all about - a BSD-style vector implementation. It has been proven to be reliable over time.
Example:
/* Declare a vector of int type, called v: */
VECTOR(int) v;
/* Initialize v, use an initial size of 16: */
SV_INIT(&v, 16, int);
/* Append data: */
SV_PUSH_BACK(&v, 1);
/* Get element at index i: */
SV_AT(&v, i);
/* Erase an element at index i: */
SV_ERASE_AT(&v, i);
/* Clean up: */
SV_RELEASE(&v);
Implementation
Declare: VECTOR(type)
This macro generates the following structure:
struct
{
type *data;
size_t size;
size_t __elementSize;
size_t __allocatedLength;
}
Append: SV_PUSH_BACK(__vector_in, __data_in)
This macro implements the push_back function of a vector. __vector_in is a pointer to the vector, __data_in is the data to be appended to the vector. This macro checks if the allocated space for the vector needs to be expanded:
if((__vector_in)->__allocatedLength - 1 < (__vector_in)->size)
If it does, then double the size of the vector and allocate new memory using realloc() function.
Finally, new data is added to the end of the array.
Get element at index: SV_AT(__vertor_in, __element_index)
Since vector is implemented using array, this macro simply return the item at __element_index.
Note that for performance consideration, this macro does NOT perform boundary test.
Erase element at index: SV_ERASE_AT(__vector, __element_index)
This macro erases an item at __element_index. Since again, vector is implemented using array, it is always expensive to erase an item from it. SV_ERASE_AT() does perform boundary test.
This macro is implemented using MEMCOY() function:
MEMCPY((__vector)->data + (__element_index), \
(__vector)->data + (__element_index) + 1, \
(__vector)->__elementSize * \
((__vector)->size - (__element_index) - 1)); \
(__vector)->size--;
Then it checks if the allocated space for the vector needs to be shortened using __SV_CHECK_SHORTEN() macro.