Vector
[Generic Data Structures]

Collaboration diagram for Vector:

A resizable array that can optionally act as a binary heap. More...


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.

Detailed Description

A resizable array that can optionally act as a binary heap.


Define Documentation

#define Enlarge ( vec,
inc   ) 

Value:

Resize(vec, \
    ((inc) > (vec)->size << 1) ? (inc) + ((vec)->size << 1) : (vec)->size << 1)
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.

Parameters:
vec A pointer to the vector to enlarge.
inc The minimum number of additional items that must fit in the array.
Returns:
True if the operation succeeded, false if the memory could not be allocated.
Author:
Jeff Jackowski

Definition at line 76 of file vector.c.

Referenced by VectorInsertMany().

HEAP_CHILD_INDEX (  )  [related, inherited]

Computes the index of the first child item in a binary heap given the parent's index.

Parameters:
i The parent's index.
Returns:
The first child's index.

Definition at line 81 of file vector.h.

Referenced by HeapMoveDown().

#define HEAP_CHILD_INDEX (  )     (((i) << 1) + 1) [related]

Computes the index of the first child item in a binary heap given the parent's index.

Parameters:
i The parent's index.
Returns:
The first child's index.

Definition at line 81 of file vector.h.

HEAP_PARENT_INDEX (  )  [related, inherited]

Computes the index of the parent item in a binary heap given the child's index.

Parameters:
i The child's index.
Returns:
The parent's index.

Definition at line 71 of file vector.h.

Referenced by VectorHeapPush().

#define HEAP_PARENT_INDEX (  )     (((i) - 1) >> 1) [related]

Computes the index of the parent item in a binary heap given the child's index.

Parameters:
i The child's index.
Returns:
The parent's index.

Definition at line 71 of file vector.h.

#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)
Conditionally reduces the size of a vector if only 1/4 of the items in the vector are used.

For internal use only.

Parameters:
vec A pointer to the vector to conditionally shrink.
Author:
Jeff Jackowski

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.

Parameters:
vec A pointer to the Vector with the item.
Returns:
A pointer to the item or NULL if it does not exist.
Author:
Jeff Jackowski

Definition at line 373 of file vector.h.

Referenced by ServiceMessages().

#define VectorFirst ( vec   )     (((vec)->items) ? (vec)->array : NULL) [related]

A convienience macro for getting the first item in a Vector.

Parameters:
vec A pointer to the Vector with the item.
Returns:
A pointer to the item or NULL if it does not exist.
Author:
Jeff Jackowski

Definition at line 373 of file vector.h.

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.

Parameters:
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.
Returns:
The address of the inserted item, or NULL if resizing the vector failed.
Author:
Jeff Jackowski

Definition at line 294 of file vector.h.

#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.

Parameters:
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.
Returns:
The address of the inserted item, or NULL if resizing the vector failed.
Author:
Jeff Jackowski

Definition at line 294 of file vector.h.

VectorItem ( vec,
index   )  [related, inherited]

A convienience macro for getting some item in a Vector.

Parameters:
vec A pointer to the Vector with the item.
index The index of the item to retrieve.
Warning:
Do not write code that modifies the value of index -- it will be run twice.
Returns:
A pointer to the item or NULL if it does not exist.
Author:
Jeff Jackowski

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)
A convienience macro for getting some item in a Vector.

Parameters:
vec A pointer to the Vector with the item.
index The index of the item to retrieve.
Warning:
Do not write code that modifies the value of index -- it will be run twice.
Returns:
A pointer to the item or NULL if it does not exist.
Author:
Jeff Jackowski

Definition at line 398 of file vector.h.

VectorLast ( vec   )  [related, inherited]

A convienience macro for getting the last item in a Vector.

Parameters:
vec A pointer to the Vector with the item.
Returns:
A pointer to the item or NULL if it does not exist.
Author:
Jeff Jackowski

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)
A convienience macro for getting the last item in a Vector.

Parameters:
vec A pointer to the Vector with the item.
Returns:
A pointer to the item or NULL if it does not exist.
Author:
Jeff Jackowski

Definition at line 383 of file vector.h.

VectorRemove ( vec,
index   )  [related, inherited]

Removes an item from a Vector.

Parameters:
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.
Author:
Jeff Jackowski

Definition at line 323 of file vector.h.

Referenced by _AATreeRemove(), and RemoveBadSamples().

#define VectorRemove ( vec,
index   )     VectorRemoveMany(vec, index, 1) [related]

Removes an item from a Vector.

Parameters:
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.
Author:
Jeff Jackowski

Definition at line 323 of file vector.h.


Typedef Documentation

typedef void(*) DestructorOp(void *item)

A function that handles deinitialization for an item.

Parameters:
item The item to deinitialize. It must not be deallocated in this funtion.

Definition at line 53 of file vector.h.

typedef Bool(*) LessThanOp(void *item1, void *item2)

A function that determines if an item is less than another.

Parameters:
item1 The address within the vector of the first operand.
item2 The address within the vector of the second operand.
Returns:
True if item1 < item2.

Definition at line 45 of file vector.h.

typedef struct Vector_t Vector

Definition at line 130 of file vector.h.


Function Documentation

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.

Parameters:
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.

Parameters:
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.
Author:
Jeff Jackowski

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().

static Bool Resize ( Vector vec,
unsigned int  newSize 
) [inline, static]

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.

Parameters:
vec The vector to operate upon.
newSize The number of elements the resized array will contain.
Returns:
True if successful, false if the memory could not be obtained.
Author:
Jeff Jackowski

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.

Parameters:
vec The Vector to add upon.
Returns:
The address of the new item, or NULL if resizing the vector failed.
Author:
Jeff Jackowski

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.

Parameters:
vec The vector to operate on.
Author:
Jeff Jackowski

Definition at line 194 of file vector.c.

Referenced by AATreeDestroy(), and CancelAllMessages().

Bool VectorCopy ( Vector target,
Vector source 
) [related, inherited]

Copies the contents of a Vector into a new vector.

Parameters:
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.
Returns:
True on success. Failure will occur if there is inadequate memory.
Author:
Jeff Jackowski

Definition at line 177 of file vector.c.

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.

Parameters:
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.
Author:
Jeff Jackowski

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.

Precondition:
All items already in the Vector are in heap order, or the vector is empty.

The given vector must have a function set for Vector::lessOp prior to calling this function.

Parameters:
vec The Vector to operate on.
Author:
Jeff Jackowski

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.

Precondition:
All items already in the vector are in heap order, or the vector is empty.

The given vector must have a function set for Vector::lessOp prior to calling this function.

Parameters:
vec The Vector to operate on.
item The item to copy into the Vector.
Returns:
The address of the item in the Vector, or NULL if resizing the vector failed.
Author:
Jeff Jackowski

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.

Precondition:
The given vector must have a function set for Vector::lessOp prior to calling this function.
Postcondition:
The vector's items are in accending order, not heap order.
Parameters:
vec The Vector to operate on.
Author:
Jeff Jackowski

Definition at line 300 of file vector.c.

Bool VectorInit ( Vector vec,
unsigned int  initSize 
) [related, inherited]

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.

Parameters:
vec The vector to initialize.
Precondition:
The following fields must be set prior to calling this function:
Postcondition:
The following fields are not initalized by this function and can be set before or after the call:
Parameters:
initSize The initial size of the vector given in the number of items.
Warning:
The value of initSize must not be less than Vector::minSize.
Returns:
True on success, false if the array could not be allocated (inadequate memory).
Author:
Jeff Jackowski

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.

Parameters:
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.
Returns:
The address of the first inserted item, or NULL if resizing the vector failed.
Author:
Jeff Jackowski

Definition at line 331 of file vector.c.

void VectorMakeHeap ( Vector vec  )  [related, inherited]

Reorders the items in a Vector into heap order.

Precondition:
The given vector must have a function set for Vector::lessOp prior to calling this function.
Postcondition:
The vector's items are in heap order.
Parameters:
vec The Vector to operate on.
Author:
Jeff Jackowski

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.

Parameters:
vec The Vector to operate on.
Author:
Jeff Jackowski

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.

Parameters:
vec The Vector to operate upon.
item The item to copy into the Vector.
Returns:
The address of the item in the Vector, or NULL if resizing the vector failed.
Author:
Jeff Jackowski

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.

Parameters:
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.
Author:
Jeff Jackowski

Definition at line 359 of file vector.c.

Bool VectorReserve ( Vector vec,
unsigned int  size 
) [related, inherited]

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.

Parameters:
vec The Vector to operate on.
size The minimum number of items the Vector should store after this function is finished.
Returns:
True on success.
Author:
Jeff Jackowski

Definition at line 412 of file vector.c.


Generated on Mon May 28 04:41:44 2007 for Retro Tank Super Attack by  doxygen 1.5.2