Collaboration diagram for Vector:
Files | |
file | vector.c |
The implementation of a generic vector in C. | |
file | vector.h |
The interface to a generic vector with binary heap functionality. | |
Data Structures | |
struct | Vector_t |
A generic vector that can hold a varying number of items that are all the same size. More... | |
Defines | |
#define | Enlarge(vec, inc) |
Unconditionally enlarges a vector by at least doubling its size, or more if inc is greater than the current vector size. | |
Vector_t::HEAP_CHILD_INDEX(i) | |
Computes the index of the first child item in a binary heap given the parent's index. | |
#define | HEAP_CHILD_INDEX(i) (((i) << 1) + 1) |
Computes the index of the first child item in a binary heap given the parent's index. | |
Vector_t::HEAP_PARENT_INDEX(i) | |
Computes the index of the parent item in a binary heap given the child's index. | |
#define | HEAP_PARENT_INDEX(i) (((i) - 1) >> 1) |
Computes the index of the parent item in a binary heap given the child's index. | |
#define | Shrink(vec) |
Conditionally reduces the size of a vector if only 1/4 of the items in the vector are used. | |
Vector_t::VectorFirst(vec) | |
A convienience macro for getting the first item in a Vector. | |
#define | VectorFirst(vec) (((vec)->items) ? (vec)->array : NULL) |
A convienience macro for getting the first item in a Vector. | |
Vector_t::VectorInsert(vec, index) | |
Inserts an uninitalized item within the given vector. | |
#define | VectorInsert(vec, index) VectorInsertMany(vec, index, 1) |
Inserts an uninitalized item within the given vector. | |
Vector_t::VectorItem(vec, index) | |
A convienience macro for getting some item in a Vector. | |
#define | VectorItem(vec, index) |
A convienience macro for getting some item in a Vector. | |
Vector_t::VectorLast(vec) | |
A convienience macro for getting the last item in a Vector. | |
#define | VectorLast(vec) |
A convienience macro for getting the last item in a Vector. | |
Vector_t::VectorRemove(vec, index) | |
Removes an item from a Vector. | |
#define | VectorRemove(vec, index) VectorRemoveMany(vec, index, 1) |
Removes an item from a Vector. | |
Typedefs | |
typedef void(*) | DestructorOp (void *item) |
A function that handles deinitialization for an item. | |
typedef Bool(*) | LessThanOp (void *item1, void *item2) |
A function that determines if an item is less than another. | |
typedef Vector_t | Vector |
Functions | |
void | GenericPointerFree (void *item) |
A generic destructor for use with vectors of pointers. | |
static void | HeapMoveDown (Vector *vec, unsigned int index, void *temp) |
Takes an item in the vector that is not in heap order and moves it down in the array to restore heap order. | |
static Bool | Resize (Vector *vec, unsigned int newSize) |
Changes the size of a vector's array. | |
void * | Vector_t::VectorAdd (Vector *vec) |
Adds an item to the end of the Vector and returns a pointer to the new, uninitialized item. | |
void | Vector_t::VectorClear (Vector *vec) |
Destroys the contents of a Vector, but not the Vector. | |
Bool | Vector_t::VectorCopy (Vector *target, Vector *source) |
Copies the contents of a Vector into a new vector. | |
void | Vector_t::VectorDestroy (Vector *vec) |
Destroys the contents of a Vector and deallocates its array. | |
void | Vector_t::VectorHeapPop (Vector *vec) |
Removes the first item in the Vector and maintains heap order. | |
void * | Vector_t::VectorHeapPush (Vector *vec, void *item) |
Copies the given item into the Vector and places it in heap order. | |
void | Vector_t::VectorHeapSort (Vector *vec) |
Uses the heap sort algorithm to sort the items in the Vector. | |
Bool | Vector_t::VectorInit (Vector *vec, unsigned int initSize) |
Initializes a Vector by setting some initial values and allocating space for the array. | |
void * | Vector_t::VectorInsertMany (Vector *vec, unsigned int index, unsigned int count) |
Makes room for multiple items in the Vector. | |
void | Vector_t::VectorMakeHeap (Vector *vec) |
Reorders the items in a Vector into heap order. | |
void | Vector_t::VectorPop (Vector *vec) |
Removes the item at the end of a Vector. | |
void * | Vector_t::VectorPush (Vector *vec, void *item) |
Copies the given item to the end of the Vector and returns a pointer to the item within the Vector. | |
void | Vector_t::VectorRemoveMany (Vector *vec, unsigned int index, unsigned int count) |
Removes multiple items from a Vector. | |
Bool | Vector_t::VectorReserve (Vector *vec, unsigned int size) |
Reserves space for a given number of items. |
#define Enlarge | ( | vec, | |||
inc | ) |
Value:
Unconditionally enlarges a vector by at least doubling its size, or more if inc is greater than the current vector size.
For internal use only.
vec | A pointer to the vector to enlarge. | |
inc | The minimum number of additional items that must fit in the array. |
Definition at line 76 of file vector.c.
Referenced by VectorInsertMany().
HEAP_CHILD_INDEX | ( | i | ) | [related, inherited] |
Computes the index of the first child item in a binary heap given the parent's index.
i | The parent's index. |
Definition at line 81 of file vector.h.
Referenced by HeapMoveDown().
#define HEAP_CHILD_INDEX | ( | i | ) | (((i) << 1) + 1) [related] |
HEAP_PARENT_INDEX | ( | i | ) | [related, inherited] |
Computes the index of the parent item in a binary heap given the child's index.
i | The child's index. |
Definition at line 71 of file vector.h.
Referenced by VectorHeapPush().
#define HEAP_PARENT_INDEX | ( | i | ) | (((i) - 1) >> 1) [related] |
#define Shrink | ( | vec | ) |
Value:
if (((vec)->size > (vec)->minSize) && \ (((vec)->size >> 2) >= (vec)->items)) \ Resize(vec, \ ((vec)->size >> 1 > (vec)->minSize) ? (vec)->size >> 1 : (vec)->minSize)
For internal use only.
vec | A pointer to the vector to conditionally shrink. |
Definition at line 88 of file vector.c.
Referenced by VectorClear(), VectorHeapPop(), VectorPop(), and VectorRemoveMany().
VectorFirst | ( | vec | ) | [related, inherited] |
A convienience macro for getting the first item in a Vector.
vec | A pointer to the Vector with the item. |
Definition at line 373 of file vector.h.
Referenced by ServiceMessages().
#define VectorFirst | ( | vec | ) | (((vec)->items) ? (vec)->array : NULL) [related] |
VectorInsert | ( | vec, | |||
index | ) | [related, inherited] |
Inserts an uninitalized item within the given vector.
When compiled for debugging, each byte of the new item data will be initialized to 0xCD to help find cases where data is incorrectly used uninitialized.
vec | A pointer to the Vector to operate on. | |
index | The index to place the new item. All items presently at or past this index will be moved to a higher index. The index may be any value from zero to one past the end of the vector. |
#define VectorInsert | ( | vec, | |||
index | ) | VectorInsertMany(vec, index, 1) [related] |
Inserts an uninitalized item within the given vector.
When compiled for debugging, each byte of the new item data will be initialized to 0xCD to help find cases where data is incorrectly used uninitialized.
vec | A pointer to the Vector to operate on. | |
index | The index to place the new item. All items presently at or past this index will be moved to a higher index. The index may be any value from zero to one past the end of the vector. |
VectorItem | ( | vec, | |||
index | ) | [related, inherited] |
A convienience macro for getting some item in a Vector.
vec | A pointer to the Vector with the item. | |
index | The index of the item to retrieve. |
Definition at line 398 of file vector.h.
Referenced by ServiceGameConfig().
#define VectorItem | ( | vec, | |||
index | ) | [related] |
Value:
(((unsigned)(index) < (vec)->items) ? \ &(((char*)(vec)->array)[index * (vec)->itemSize]) : NULL)
vec | A pointer to the Vector with the item. | |
index | The index of the item to retrieve. |
VectorLast | ( | vec | ) | [related, inherited] |
A convienience macro for getting the last item in a Vector.
vec | A pointer to the Vector with the item. |
Definition at line 383 of file vector.h.
Referenced by BufferNew(), and MessageNew().
#define VectorLast | ( | vec | ) | [related] |
Value:
(((vec)->items) ? \ &(((char*)(vec)->array)[((vec)->items - 1) * (vec)->itemSize]) : \ NULL)
vec | A pointer to the Vector with the item. |
VectorRemove | ( | vec, | |||
index | ) | [related, inherited] |
Removes an item from a Vector.
vec | A pointer to the Vector to operate on. | |
index | The index to remove. All items past this index will be moved to a lower index. |
Definition at line 323 of file vector.h.
Referenced by _AATreeRemove(), and RemoveBadSamples().
#define VectorRemove | ( | vec, | |||
index | ) | VectorRemoveMany(vec, index, 1) [related] |
typedef void(*) DestructorOp(void *item) |
typedef Bool(*) LessThanOp(void *item1, void *item2) |
void GenericPointerFree | ( | void * | item | ) |
A generic destructor for use with vectors of pointers.
It calls free() on the pointer in the Vector if the pointer is non-NULL.
item | The item to deinitialize by deallocating it. The item is really a double pointer. |
Definition at line 422 of file vector.c.
Referenced by MessageInit().
static void HeapMoveDown | ( | Vector * | vec, | |
unsigned int | index, | |||
void * | temp | |||
) | [static] |
Takes an item in the vector that is not in heap order and moves it down in the array to restore heap order.
It is assumed that with the exception of the item, the vector is already in heap order.
For internal use only.
vec | The Vector to operate upon. | |
index | The index of the item that must be moved. | |
temp | A pointer to the item that is being placed into the heap. |
Definition at line 105 of file vector.c.
References Vector_t::array, Vector_t::HEAP_CHILD_INDEX, Vector_t::items, Vector_t::itemSize, and Vector_t::lessOp.
Referenced by VectorHeapPop(), VectorHeapSort(), and VectorMakeHeap().
Changes the size of a vector's array.
If it is made smaller, elements from the end of the array will be destroyed. If it is made larger, the space for the new elements will be uninitalized. Other element data will remain in the array, but their location in memory may change.
For internal use only.
vec | The vector to operate upon. | |
newSize | The number of elements the resized array will contain. |
Definition at line 49 of file vector.c.
References Vector_t::array, FALSE, Vector_t::itemSize, Vector_t::size, and TRUE.
Referenced by VectorAdd(), VectorHeapPush(), VectorPush(), and VectorReserve().
void * VectorAdd | ( | Vector * | vec | ) | [related, inherited] |
Adds an item to the end of the Vector and returns a pointer to the new, uninitialized item.
vec | The Vector to add upon. |
Definition at line 212 of file vector.c.
Referenced by AATreeAdd(), GetSamples(), MakeAreaBuffers(), MakeBuffers(), MessageInit(), ReadAreaParams(), and StartLoadConfig().
void VectorClear | ( | Vector * | vec | ) | [related, inherited] |
Destroys the contents of a Vector, but not the Vector.
The Vector's array is not deallocated, but it may shrink. If Vector::destructOp is not NULL, it will be called for each item still inside the vector.
vec | The vector to operate on. |
Definition at line 194 of file vector.c.
Referenced by AATreeDestroy(), and CancelAllMessages().
Copies the contents of a Vector into a new vector.
target | An uninitialzied vector that will receive the copy. Unlike with VectorInit(), there is no need to initialize any fields because they will be copied from the source vector. | |
source | The vector with the contents to copy. |
void VectorDestroy | ( | Vector * | vec | ) | [related, inherited] |
Destroys the contents of a Vector and deallocates its array.
If Vector::destructOp is not NULL, it will be called for each item still inside the vector.
vec | The vector to destroy. The array will be deallocated, but vec will not so that it can be allocated somewhere other than the heap. The fields of vec will not be changed unless compiled for debugging. Debug builds will fill every byte of vec with 0xAB to assist in finding inappropriate use of destroyed vectors. |
Definition at line 155 of file vector.c.
Referenced by ClientSync(), MakeBuffers(), MessageUninit(), and treeExit().
void VectorHeapPop | ( | Vector * | vec | ) | [related, inherited] |
Removes the first item in the Vector and maintains heap order.
If Vector::destructOp is not NULL, it will be called on the removed item.
The given vector must have a function set for Vector::lessOp prior to calling this function.
vec | The Vector to operate on. |
Definition at line 283 of file vector.c.
Referenced by ServiceMessages().
void * VectorHeapPush | ( | Vector * | vec, | |
void * | item | |||
) | [related, inherited] |
Copies the given item into the Vector and places it in heap order.
The given vector must have a function set for Vector::lessOp prior to calling this function.
vec | The Vector to operate on. | |
item | The item to copy into the Vector. |
Definition at line 242 of file vector.c.
Referenced by AddMessage(), and ServiceMessages().
void VectorHeapSort | ( | Vector * | vec | ) | [related, inherited] |
Uses the heap sort algorithm to sort the items in the Vector.
vec | The Vector to operate on. |
Initializes a Vector by setting some initial values and allocating space for the array.
This function assumes the array pointer in the given vector is uninitialized. When compiled for debugging, each byte of the array data will be initialized to 0xCD to help find cases where data is incorrectly used uninitialized.
vec | The vector to initialize. |
initSize | The initial size of the vector given in the number of items. |
Definition at line 133 of file vector.c.
Referenced by AATreeAdd(), ClientSync(), InitGameConfig(), MessageInit(), and StartLoadConfig().
void * VectorInsertMany | ( | Vector * | vec, | |
unsigned int | index, | |||
unsigned int | count | |||
) | [related, inherited] |
Makes room for multiple items in the Vector.
The new items will be uninitialzied. When compiled for debugging, each byte of the new item data will be initialized to 0xCD to help find cases where data is incorrectly used uninitialized.
vec | The Vector to operate on. | |
index | The first index of the range to insert. All items presently at or past this index will be moved to a higher index. The index may be any value from zero to one past the end of the vector. | |
count | The number of items to insert. |
void VectorMakeHeap | ( | Vector * | vec | ) | [related, inherited] |
Reorders the items in a Vector into heap order.
vec | The Vector to operate on. |
Definition at line 389 of file vector.c.
Referenced by VectorHeapSort().
void VectorPop | ( | Vector * | vec | ) | [related, inherited] |
Removes the item at the end of a Vector.
If Vector::destructOp is not NULL, it will be called on the item.
vec | The Vector to operate on. |
Definition at line 269 of file vector.c.
Referenced by StartLoadConfig().
void * VectorPush | ( | Vector * | vec, | |
void * | item | |||
) | [related, inherited] |
Copies the given item to the end of the Vector and returns a pointer to the item within the Vector.
vec | The Vector to operate upon. | |
item | The item to copy into the Vector. |
Definition at line 225 of file vector.c.
Referenced by BufferFree(), and MessageFree().
void VectorRemoveMany | ( | Vector * | vec, | |
unsigned int | index, | |||
unsigned int | count | |||
) | [related, inherited] |
Removes multiple items from a Vector.
vec | The Vector to operate on. | |
index | The first index to remove. All items past this index will be moved to a lower index. | |
count | The number of items to remove. The items to remove must not go past the end of the items in the Vector's array. |
Reserves space for a given number of items.
If the Vector can already store the specified number of items or more, no action is taken.
vec | The Vector to operate on. | |
size | The minimum number of items the Vector should store after this function is finished. |