253 lines
8.7 KiB
C
253 lines
8.7 KiB
C
|
|
||
|
|
|
||
|
|
|
||
|
|
/**
|
||
|
|
* @file vector.h
|
||
|
|
* @brief Functions for creating and manipulating vectors.
|
||
|
|
*
|
||
|
|
* A vector is an array that can be resized to meet changing storage
|
||
|
|
* requirements. Usage is typically as follows:
|
||
|
|
|
||
|
|
\include vector_test.c
|
||
|
|
|
||
|
|
|
||
|
|
*
|
||
|
|
* @author Jon Schutz
|
||
|
|
* @date 05-Feb-2001
|
||
|
|
**/
|
||
|
|
|
||
|
|
#ifndef __VECTOR_H
|
||
|
|
#define __VECTOR_H /* To stop multiple inclusions. */
|
||
|
|
|
||
|
|
#include <stddef.h>
|
||
|
|
#include <stdint.h>
|
||
|
|
|
||
|
|
/** Vector */
|
||
|
|
typedef struct _vector {
|
||
|
|
/** The array to hold the data. */
|
||
|
|
void *array;
|
||
|
|
/** The size of the array. */
|
||
|
|
size_t array_size;
|
||
|
|
/** The used size, assuming vector_append is the only operation
|
||
|
|
which adds elements to the vector. */
|
||
|
|
size_t index;
|
||
|
|
} vector;
|
||
|
|
|
||
|
|
|
||
|
|
/** Add a new item to the end of a vector.
|
||
|
|
|
||
|
|
@param v The vector to which to add an item.
|
||
|
|
@param item The item to add.
|
||
|
|
@param increment The capacity to add when the array is resized.
|
||
|
|
Should be >0, or at least =0 if factor>1.
|
||
|
|
@param factor The factor by which to increase storage when the array is
|
||
|
|
resized. Should be >1, or at least =1 if increment>0.
|
||
|
|
@return 0 on success, -1 if vector_resize() fails.
|
||
|
|
*/
|
||
|
|
#define vector_append(v, item, increment, factor) \
|
||
|
|
({ \
|
||
|
|
int rv=0; \
|
||
|
|
\
|
||
|
|
if ((v)->index >= (v)->array_size) \
|
||
|
|
rv = vector_resize((v), \
|
||
|
|
(v)->array_size * factor + increment, sizeof(item)); \
|
||
|
|
if (0 == rv) \
|
||
|
|
((typeof(item) *)(v)->array)[(v)->index++] = item; \
|
||
|
|
rv; \
|
||
|
|
})
|
||
|
|
|
||
|
|
/** Insert space for several items into a vector at the given
|
||
|
|
position. No items are actually inserted.
|
||
|
|
|
||
|
|
If the given position exceeds the current end index of the array,
|
||
|
|
the new end index, then item is inserted before the specified
|
||
|
|
position and the end index points to the next position after the
|
||
|
|
inserted item.
|
||
|
|
|
||
|
|
If necessary, the vector is resized to accommodate the request.
|
||
|
|
|
||
|
|
@param v The vector to which to insert space.
|
||
|
|
@param item An instance or type of the items in the vector.
|
||
|
|
@param pos The position at which to insert space.
|
||
|
|
@param n The number of items for which to insert space.
|
||
|
|
@param increment The capacity to add when the array is resized.
|
||
|
|
Should be >0, or at least =0 if factor>1.
|
||
|
|
@param factor The factor by which to increase storage when the array is
|
||
|
|
resized. Should be >1, or at least =1 if increment>0.
|
||
|
|
@return 0 on success, -1 if vector_resize() fails.
|
||
|
|
*/
|
||
|
|
#define vector_insert_space(v, item, pos, n, increment, factor) \
|
||
|
|
({ \
|
||
|
|
int _rv=0; \
|
||
|
|
int new_end = ((pos)>(v)->index)?((pos)+(n)):((v)->index+(n)); \
|
||
|
|
if (new_end > (v)->array_size) { \
|
||
|
|
size_t new_size = (v)->array_size * factor + increment; \
|
||
|
|
if (new_end > new_size) \
|
||
|
|
new_size = new_end; \
|
||
|
|
_rv = vector_resize((v), new_size, sizeof(item)); \
|
||
|
|
} \
|
||
|
|
if (0 == _rv) { \
|
||
|
|
if ((v)->index > pos) { \
|
||
|
|
memmove(((char *)(v)->array) + sizeof(item)*((pos)+(n)), \
|
||
|
|
((char *)(v)->array) + sizeof(item)*(pos), \
|
||
|
|
sizeof(item)*((v)->index - pos)); \
|
||
|
|
(v)->index += (n); \
|
||
|
|
} \
|
||
|
|
else \
|
||
|
|
(v)->index = new_end; \
|
||
|
|
} \
|
||
|
|
_rv; \
|
||
|
|
})
|
||
|
|
|
||
|
|
|
||
|
|
/** Add a new item to the vector at a given position. The item is
|
||
|
|
inserted before the specified position.
|
||
|
|
|
||
|
|
If the given position exceeds the current end index of the array,
|
||
|
|
the new end index, the item is inserted before the specified
|
||
|
|
position and the end index points to the next position after the
|
||
|
|
inserted item.
|
||
|
|
|
||
|
|
If necessary, the vector is resized to accommodate the request.
|
||
|
|
|
||
|
|
@param v The vector to which to insert an item.
|
||
|
|
@param item The item to insert.
|
||
|
|
@param pos The position at which to insert the item.
|
||
|
|
@param increment The capacity to add when the array is resized.
|
||
|
|
Should be >0, or at least =0 if factor>1.
|
||
|
|
@param factor The factor by which to increase storage when the array is
|
||
|
|
resized. Should be >1, or at least =1 if increment>0.
|
||
|
|
@return 0 on success, -1 if vector_resize() fails.
|
||
|
|
*/
|
||
|
|
#define vector_insert(v, item, pos, increment, factor) \
|
||
|
|
({ \
|
||
|
|
const int c_pos = pos; \
|
||
|
|
int rv = vector_insert_space(v, item, pos, 1, increment, factor); \
|
||
|
|
if (0 == rv) { \
|
||
|
|
((typeof(item) *)(v)->array)[c_pos] = item; \
|
||
|
|
} \
|
||
|
|
rv; \
|
||
|
|
}) \
|
||
|
|
|
||
|
|
/** Delete several item from a vector.
|
||
|
|
|
||
|
|
@param v The vector in which to delete the item.
|
||
|
|
@param item An instance or type of the item to delete.
|
||
|
|
@param pos The first position at which to delete.
|
||
|
|
@param n The number of items to delete.
|
||
|
|
*/
|
||
|
|
#define vector_delete_n(v, item, pos, n) \
|
||
|
|
if ((v)->index > ((pos) + (n))) { \
|
||
|
|
memmove((v)->array + sizeof(item)*(pos), \
|
||
|
|
(v)->array + sizeof(item)*((pos)+(n)), \
|
||
|
|
sizeof(item)*((v)->index - (pos) - (n))); \
|
||
|
|
(v)->index -= (n); \
|
||
|
|
} \
|
||
|
|
else \
|
||
|
|
(v)->index = pos;
|
||
|
|
|
||
|
|
/** Delete an item from a vector.
|
||
|
|
|
||
|
|
@param v The vector in which to delete the item.
|
||
|
|
@param item An instance or type of the item to delete.
|
||
|
|
@param pos The position at which to delete.
|
||
|
|
*/
|
||
|
|
#define vector_delete(v, item, pos) \
|
||
|
|
vector_delete_n(v, item, pos, 1)
|
||
|
|
|
||
|
|
|
||
|
|
/** Access a member of a vector.
|
||
|
|
@param v The vector to access
|
||
|
|
@param index The index to read.
|
||
|
|
@param element_type The type name or an instance of the
|
||
|
|
type of which the vector is comprised.
|
||
|
|
|
||
|
|
@return v[index]
|
||
|
|
*/
|
||
|
|
#define element_at(v, index, element_type) \
|
||
|
|
(((typeof(element_type) *)(v)->array)[index])
|
||
|
|
|
||
|
|
/** Reverse items in a vector.
|
||
|
|
@param v The vector in which to reverse items.
|
||
|
|
@param item The type name or an instance of the
|
||
|
|
type of which the vector is comprised.
|
||
|
|
@param start The starting index of the sequence to be reversed.
|
||
|
|
@param end The index following the end of the sequence to be
|
||
|
|
reversed.
|
||
|
|
*/
|
||
|
|
#define vector_reverse(v, item, start, end) { \
|
||
|
|
int _i; \
|
||
|
|
int _half = (end-start)/2; \
|
||
|
|
typeof(item) _temp; \
|
||
|
|
for (_i=0; _i<_half; _i++) { \
|
||
|
|
_temp = element_at(v, (start)+_i, item); \
|
||
|
|
element_at(v, (start)+_i, item) = element_at(v, (end)-_i-1, item); \
|
||
|
|
element_at(v, (end)-_i-1, item) = _temp; \
|
||
|
|
} \
|
||
|
|
}
|
||
|
|
|
||
|
|
int vector_resize(vector *v, size_t size, size_t element_size);
|
||
|
|
int vector_create(vector *v, size_t size, size_t element_size);
|
||
|
|
void vector_destroy(vector *v);
|
||
|
|
|
||
|
|
|
||
|
|
/** Finds the next unused slot in a vector, by comparing the contents
|
||
|
|
* of a given \a field with \a thing that indicates a free slot.
|
||
|
|
*
|
||
|
|
* @param v The vector to search through.
|
||
|
|
* @param item The type of data held by the vector.
|
||
|
|
* @param field A field of a struct which is held in the vector's array.
|
||
|
|
* @param thing If the contents of the above field match this thing, we
|
||
|
|
* have found an unused slot.
|
||
|
|
*
|
||
|
|
* @return the index of the first unused slot.
|
||
|
|
**/
|
||
|
|
#define vector_find_next_free_slot(v, item, field, thing) \
|
||
|
|
({ \
|
||
|
|
int i = 0; \
|
||
|
|
if ((NULL != (v)->array) && (0 < (v)->index)) \
|
||
|
|
for (i = 0; i < (v)->index; i++) \
|
||
|
|
if (thing == ((typeof(item) *)(v)->array)[i]field) \
|
||
|
|
break; \
|
||
|
|
i; \
|
||
|
|
})
|
||
|
|
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Stores a \a token of type \a item into \a v, in the first location in
|
||
|
|
* \a v whose \a field matches \a thing. If all \a v->index slots in \a
|
||
|
|
* v are in use, a new element is inserted at the end of the vector and
|
||
|
|
* \a v->index is incremented, otherwise, \a token is inserted at the
|
||
|
|
* first available slot, and \a v->index is left unchanged. An
|
||
|
|
* extension of the "vector" class, which can be used when
|
||
|
|
* "vector_delete" is not suitable (e.g. if the index into the vector
|
||
|
|
* is being remembered by external software, then vector_delete will not
|
||
|
|
* work, because it deletes from the middle of a vector and moves all
|
||
|
|
* the top entries down to fill the vacated slot(s)).
|
||
|
|
*
|
||
|
|
* @param v Vector into which we will insert the token.
|
||
|
|
* @param token The object to store in the vector.
|
||
|
|
* @param item The data-type of the token that we're inserting.
|
||
|
|
* @param size The size of the token that we're inserting.
|
||
|
|
* @param field A field of a struct which is held in the vector's array.
|
||
|
|
* (May be empty if not using a struct).
|
||
|
|
* @param thing If the contents of the above field match this thing, we
|
||
|
|
* have found an unused slot.
|
||
|
|
*
|
||
|
|
* @return The location of the slot in the vector where the data was
|
||
|
|
* stored.
|
||
|
|
**/
|
||
|
|
#define vector_store(v, token, item, size,field, thing) \
|
||
|
|
({ \
|
||
|
|
int pos = vector_find_next_free_slot(v, item,field, thing); \
|
||
|
|
if (pos == (v)->index) \
|
||
|
|
/* Increment (v)->index */ \
|
||
|
|
vector_append((v), token, size, 1); \
|
||
|
|
else \
|
||
|
|
/* Ignore (v)->index */ \
|
||
|
|
element_at((v), pos, item) = token; \
|
||
|
|
pos; \
|
||
|
|
})
|
||
|
|
|
||
|
|
#endif /* __VECTOR_H */
|