A BSD-Style Vector Implementation in C
February 21, 2014 BY YUCHONG LI


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.


/* 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: */


Declare: VECTOR(type)

This macro generates the following structure:

    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));                        \

Then it checks if the allocated space for the vector needs to be shortened using __SV_CHECK_SHORTEN() macro.


By definition, this project is released under BSD license.


Available on Bitbucket

© 2013 - 2017 Yuchong Li