I love C so much, and I really want to hate sepples, but I can't help but think that generic programming in C is shit! Macros are no good for generic data structures, as they are clunky and blow out code size, nor are void pointers, as you need to allocate separate memory just to store an integer (don't stuff ints into pointers; zeros won't work on architectures where the null pointer constant is non-zero). I really want to write my data structure library in sepples, where templates allow type genericism without issue. What should I do, /prague/; what should I do?!
Name:
Anonymous2012-01-12 8:21
I wrote this up today, it's not very well tested but it has worked in the cases that I tested it.
Part 1 of 2:
#ifndef VECTOR_H__
#define VECTOR_H__
/*
* Please avoid side effects in the arguments
* to these macros.
*
* Note that these macros attempt to do the right
* thing when it comes to handling errors, generally
* they will return VECTOR_ERROR (default: NULL)
* casted to the type the vector carries upon error
* but more often than not the vector will be invalidated
* upon error.
*
* So if the vector is of type vector(int) then the error
* return will be (int) NULL, which might be a valid value
* for successful return depending on the input, therefore
* it is recommended that you define the VECTOR_ERROR macro
* to be some value that makes sense for your application.
*/
/**
* VECTOR_EMPTY_INITIALIZER
* Provides a valid constant sized empty
* vector of any type.
*/
#define VECTOR_EMPTY_INITIALIZER \
{NULL, NULL, NULL}
/**
* vector(type)
* Generic vector that provides
* - O(1)
* - append (amortized)
* - capacity
* - clear
* - is_empty
* - get
* - get_safe
* - pop
* - set
* - size
* - O(n)
* - insert
* - pop_first
* - prepend
* - remove
* - trim
* operations.
*/
#define vector(type) \
struct { \
type * base; \
type * head; \
type * end; \
}
/* returns the new size based
on VECTOR_SIZE_REFACTOR and
the old size*/
#define vector_newsize__(oldsize) \
((size_t) ((VECTOR_RESIZE_FACTOR + 1.0) * \
(oldsize)) + 1)
/**
* vector_append
* Adds element to the end of vector.
*
* @param (vector(type) *) vector in question
* @param (type) element to be added
* @return (type) element that was added
*/
#define vector_append(v, e) \
({ \
typeof(v) v__ = (v); \
typeof(*v__->base) e__ = (e); \
typeof(v__->base) b__ = v__->base; \
\
if (v__->head == v__->end) { \
ptrdiff_t cap__; \
cap__ = (v__->end - v__->base); \
\
b__ = realloc(v__->base, \
vector_newsize__(cap__) * \
sizeof(*v__->base)); \
\
if (b__ != NULL) { \
v__->base = b__; \
v__->head = b__ + cap__; \
v__->end = b__ + \
vector_newsize__(cap__); \
} \
} \
\
b__ == NULL ? \
(typeof(*v__->base)) VECTOR_ERROR : \
(*v__->head++ = e__); \
})
/**
* vector_capacity
* Returns the number of elements the current
* allocated underlying array may hold.
*
* @param (const vector(type) *) vector in question
* @return (ptrdiff_t) capacity of vector
*/
#define vector_capacity(v) \
({ \
typeof(v) v__ = (v); \
\
v__->end - v__->base; \
})
/**
* vector_clear
* Removes every element from vector
* and frees the underlying array.
*
* @param (vector(type) *) vector to clear
* @return (vector(type) *) the cleared vector
*/
#define vector_clear(v) \
({ \
typeof(v) v__ = (v); \
\
free(v__->base); \
v__->base = NULL; \
v__->head = NULL; \
v__->end = NULL; \
\
v__; \
})
/**
* vector_is_empty
* Returns whether the vector is empty.
*
* @param (const vector(type) *) vector in question
* @return (int) zero if the vector isn't empty and non-zero otherwise
*/
#define vector_is_empty(v) \
({ \
typeof(v) v__ = (v); \
\
v__->base == v__->head; \
})
/**
* vector_get
* Returns the element at a certain
* position in the vector without
* removing it.
*
* @param (const vector(type) *) the vector in question
* @param (int) index of element in vector
* @return (type) the element at index in vector
*/
#define vector_get(v, i) \
((v)->base[(i)])
/**
* vector_get_safe
* Returns the element at a certain
* position in the vector without
* removing it.
*
* This returns NULL casted to type
* upon error.
*
* @param (const vector(type) *) the vector in question
* @param (int) index of element in vector
* @return (type) the element at index in vector
*/
#define vector_get_safe(v, i) \
({ \
typeof(v) v__ = (v); \
int i__ = (i); \
\
i__ < vector_size(v) ? \
v__->base[i__] : \
(typeof(*v__->base)) VECTOR_ERROR; \
})
/**
* vector_insert
* Inserts an element at a certain position
* in vector without removing any elements.
*
* @param (vector(type) *) the vector in question
* @param (int) the index of the new element
* @param (type) the element to be added
* @return (type) the added elemenet
*/
#define vector_insert(v, i, e) \
({ \
typeof(v) v__ = (v); \
typeof(*v__->base) e__ = (e); \
typeof(*v__->base) l__; \
int i__ = (i); \
ptrdiff_t size__ = vector_size(v); \
\
l__ = (typeof(*v__->base)) VECTOR_ERROR; \
\
if (i__ < 0) \
l__ = l__; \
else if (i__ == size__) \
l__ = vector_append(v, e); \
else if (i__ < size__) { \
typeof(*v__->base) p__; \
int j__; \
\
p__ = v__->base[size__-1]; \
\
for (j__ = size__-1; j__ > i__; j__--) \
v__->base[j__] = v__->base[j__-1]; \
\
v__->base[i__] = e__; \
\
l__ = vector_append(v, p__) == \
(typeof(*v__->base)) VECTOR_ERROR ? \
l__ : \
e__; \
} else \
l__ = l__; \
\
l__; \
})
/**
* vector_pop
* Removes and returns the element
* at the end of the vector.
*
* @param (vector(type) *) vector in question
* @return (type) the removed element
*/
#define vector_pop(v) \
({ \
typeof(v) v__ = (v); \
\
v__->head == v__->base ? \
(typeof(*v__->base)) VECTOR_ERROR : \
*--v__->head; \
})
/**
* vector_pop_first
* Removes and returns the first
* element of the vector.
*
* @param (vector(type) *) vector in question
* @return (type) the removed element
*/
#define vector_pop_first(v) \
({ \
typeof(v) v__ = (v); \
typeof(*v__->base) l__; \
ptrdiff_t size__; \
\
size__ = vector_size(v); \
\
if (size__ > 1) { \
int i__; \
\
l__ = v__->base[0]; \
\
for (i__ = 0; i__ < size__-1; i__++) \
v__->base[i__] = v__->base[i__+1]; \
\
v__->head -= 1; \
} else { \
l__ = vector_pop(v); \
} \
\
l__; \
})
/**
* vector_prepend
* Adds element to the front of vector.
*
* @param (vector(type) *) vector in question
* @param (type) element to be added to vector
* @return (type) element that was added
*/
#define vector_prepend(v, e) \
({ \
typeof(v) v__ = (v); \
typeof(*v__->base) e__ = (e); \
typeof(*v__->base) l__; \
ptrdiff_t size__ = vector_size(v); \
\
if (size__ > 0) { \
int i__; \
\
l__ = v__->base[size__-1]; \
\
for (i__ = size__ - 1; i__ > 0; i__--) \
v__->base[i__] = v__->base[i__-1]; \
\
v__->base[0] = e__; \
} else { \
l__ = e__; \
} \
\
vector_append(v, l__) == \
(typeof(*v__->base)) VECTOR_ERROR ? \
(typeof(*v__->base)) VECTOR_ERROR : \
e__; \
})
/**
* vector_remove
* Removes and returns an element at a
* certain position in vector.
*
* @param (vector(type) *) vector in question
* @param (int) index of element
* @param (type) the removed element
*/
#define vector_remove(v, i) \
({ \
typeof(v) v__ = (v); \
typeof(*v__->base) l__; \
int i__ = (i); \
ptrdiff_t size__ = vector_size(v); \
\
l__ = (typeof(*v__->base)) VECTOR_ERROR; \
\
if (i__ < 0) \
l__ = l__; \
else if (i__ == size__-1) \
l__ = vector_pop(v); \
else if (i__ < size__) { \
int j__; \
\
l__ = v__->base[i__]; \
\
for (j__ = i__; j__ < size__-1; j__++) \
v__->base[j__] = v__->base[j__+1]; \
\
v__->head -= 1; \
} else \
l__ = l__; \
\
l__; \
})
/**
* vector_set
* Sets the element at a certain position
* in the vector and removes the old element.
*
* @param (vector(type) *) the vector in question
* @param (int) index of new element
* @param (type) element to be added
* @return (type) element that was added
*/
#define vector_set(v, i, e) \
({ \
typeof(v) v__ = (v); \
typeof(*v__->base) e__ = (e); \
typeof(*v__->base) l__; \
int i__ = (i); \
ptrdiff_t size__; \
\
size__ = vector_size(v); \
l__ = (typeof(*v__->base)) VECTOR_ERROR; \
\
if (i__ < 0) \
l__ = l__; \
else if (i__ < size__) \
l__ = (v__->base[i__] = e__); \
else if (i__ == size__) \
l__ = vector_append(v, e); \
else \
l__ = l__; \
\
l__; \
})
/**
* vector_size
* Returns the current number of elements
* in the vector.
*
* @param (const vector(type) *) vector in question
* @return (ptrdiff_t) number of elements in vector
*/
#define vector_size(v) \
({ \
typeof(v) v__ = (v); \
\
v__->head - v__->base; \
})
/**
* vector_trim
* Resizes the underlying array so only the
* elements currently in vector fits.
*
* @param (vector(type) *) the vector in question
* @return (vector(type) *) the trimmed vector
*/
#define vector_trim(v) \
({ \
typeof(v) v__ = (v); \
typeof(v__->base) b__; \
ptrdiff_t size__ = vector_size(v); \
\
b__ = realloc(v__->base, \
size__ * sizeof(*v__->base)); \
\
if (b__ != VECTOR_ERROR) { \
v__->base = b__; \
v__->head = b__ + size__; \
v__->end = b__ + size__; \
} \
\
b__ == VECTOR_ERROR ? \
VECTOR_ERROR : \
v__; \
})