Table of Contents

4. Object Collections - List,Stack,Dictionary,HashTable,VHashTable,Tree

DevTools provides modules for managing collections of objects. These collection modules provide a convenient and robust mechanism for the handling of dynamically expandable sets of objects. The List module provides an array of objects which are randomly accessible by index. The Stack module allows the pushing and popping of objects on one end of an extensible sequence. The Dictionary, HashTable and VHashTable modules maintain a one-to-one correspondence between a set of strings or integer keys and a set of objects. The Tree module allows for the storage of objects in a tree data structure, where a child node has only one parent node but a parent may have many children. The object collections store pointers of DevTools type Vobject*. The type Vobject* is the C language type void*, so that any void* type may be stored in collection objects.

Table of Contents

4.1 Randomly Accessible Sequences - List

The List module holds a sequence of objects which are identified by a positional index. It is intended for managing groups of objects which have either no natural indexing information or for which the associated numeric identifiers form a densely packed set beginning with the index zero. If the integer identifiers are sparsely distributed over a wide range of values, then it would be better to store such objects in a HashTable.

The List object may expand or shrink to contain varying numbers of objects. It also supports several "iterator" functions, which are used to successively visit each object in the list.

Instance a List object using vsy_ListBegin. Once a List is instanced, an approximate number of objects to be stored may be defined using vsy_ListDef. This allocates an internal array for the storage of object pointers. As objects are inserted the List module will adjust memory as required. The actual size of the allocated storage may be determined by calling vsy_ListInq.

Each new object is placed in the list by calling vsy_ListInsert, vsy_ListAdd, or vsy_ListAppend. The total number of objects contained in the list may be found by calling vsy_ListCount. The object at a specified index may be found by calling vsy_ListRef. An object may be removed by calling vsy_ListRemove. The method vsy_ListClear removes all objects from the list. Unused storage at the end of the internal array may be released by calling vsy_ListCompact.

Each object in the list may be processed with an "iterator" construct. The single method vsy_ListForEach takes a function as its argument and calls that function repeatedly, each time with one object from the list. The pair of methods vsy_ListInitIter and vsy_ListNextIter are used to visit each element using a loop. Call the first method before the body of the loop to prepare the List object for the iteration. Within the loop body, call vsy_ListNextIter. It will return a pointer to a new object each time it is called. It will return a NULL pointer when all of the objects have been processed.

Table of Contents

4.2 Function Descriptions

The currently available List functions are described in detail in this section.


Table of Contents , List

NAME

*vsy_ListBegin - create an instance of an List object

C SPECIFICATION

vsy_List *vsy_ListBegin ()

ARGUMENTS

None

FUNCTION RETURN VALUE

The function returns a pointer to the newly created List object. If the object creation fails, NULL is returned.

DESCRIPTION

Create an instance of a List object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a List object using

     void vsy_ListEnd (vsy_List *list)

Return the current value of a List object error flag using

     Vint vsy_ListError (vsy_List *list)


Table of Contents , List

NAME

vsy_ListDef - define initial length of storage array

C SPECIFICATION

void vsy_ListDef (vsy_List *list,
                  Vint numobj)

INPUT ARGUMENTS

list         Pointer to List object.
numobj       Estimated number of objects to be held.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Suggest a number of elements to be stored in the List. This is used to allocate the initial array of storage which is used to hold a pointer to each stored object. If the number of inserted elements is greater than this initial estimate, storage space in dynamically expanded to hold the extra objects. This function removes any previously entered objects.

Find the current length of the internal storage of a List using

     void vsy_ListInq (const vsy_List *list,
                       Vint *numobj)


Table of Contents , List

NAME

vsy_ListCount - get number of contained objects

C SPECIFICATION

void vsy_ListCount (const vsy_List *list,
                    Vint *num)

INPUT ARGUMENTS

list         Pointer to List object.

OUTPUT ARGUMENTS

num          Number of objects held the in List object.

DESCRIPTION

Get the number of objects which have been inserted or appended, and not yet removed.


Table of Contents , List

NAME

vsy_ListMaxIndex - get maximum index

C SPECIFICATION

void vsy_ListMaxIndex (const vsy_List *list,
                       Vint *maxindex)

INPUT ARGUMENTS

list         Pointer to List object.

OUTPUT ARGUMENTS

maxindex     Maximum index

DESCRIPTION

Get the maximum index used to store current objects in List.


Table of Contents , List

NAME

vsy_ListAllIndices - get all indices

C SPECIFICATION

void vsy_ListAllIndices (const vsy_List *list,
                         Vint allindices[])

INPUT ARGUMENTS

list         Pointer to List object.

OUTPUT ARGUMENTS

allindices   Array of all indices

DESCRIPTION

Get all indices used to store current objects in List. The number of index values returned will be equal the the number of indices returned by the function vsy_ListCount.


Table of Contents , List

NAME

vsy_ListInsert - place an object in the list

C SPECIFICATION

void vsy_ListInsert (vsy_List *list,
                     Vint index,
                     Vobject *value)

INPUT ARGUMENTS

list         Pointer to List object.
index        Position in list at which object is to be stored.
value        Pointer to the object.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_VALUE is generated if index is less than zero. SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Place the object value at the location identified by index, replacing any object which may have been previously placed there.

If the index value for an object may be arbitrarily assigned, then insert this object into the list using call

     void vsy_ListAdd (vsy_List *list,
                       Vobject *value,
                       Vint *index)
The location at which the object was placed will be returned in the output argument index.

An object may be placed at the end of the list using

     void vsy_ListAppend (vsy_List *list,
                          Vobject *value)


Table of Contents , List

NAME

vsy_ListRef - find the object at a specified location

C SPECIFICATION

void vsy_ListRef (const vsy_List *list,	
                  Vint index,
                  Vobject **value)

INPUT ARGUMENTS

list         Pointer to List object.
index        Location of the desired object.

OUTPUT ARGUMENTS

value        Object found at location index.

DESCRIPTION

Get a pointer to the object located at the position identified by index. Returns a NULL pointer if no object has been placed there, or if a previously inserted object has since been removed from this location.


Table of Contents , List

NAME

vsy_ListRemove - remove an object from the list

C SPECIFICATION

void vsy_ListRemove (vsy_List *list,
                     Vint index)

INPUT ARGUMENTS

list         Pointer to List object.
index        Location to be emptied.

OUTPUT ARGUMENTS

None

DESCRIPTION

Remove any object found at the location identified by index. This may introduce a "gap" in the list, which may later be filled with one of the insertion methods.

Remove all the objects from a List object using

     void vsy_ListClear (vsy_List *list)

Release any unused internal storage using

     void vsy_ListCompact (vsy_List *list)


Table of Contents , List

NAME

vsy_ListForEach - process each item in the list

C SPECIFICATION

void vsy_ListForEach (vsy_List *list,
                      void (*func)(Vobject*))

INPUT ARGUMENTS

list         Pointer to List object.
func         Pointer to function which is to be applied to each object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Calls the supplied function repeatedly, each time using an object from the list as the sole argument to this function. This is useful for deallocating a collection of objects, prior to calling vsy_ListEnd. Objects are visited in numerically increasing order of their position indices. Empty positions in the list are skipped over.

Sequential access to each item in the list may also be implemented using

     void vsy_ListInitIter (vsy_List *list)

This is followed by repeated calls to the method

     void vsy_ListNextIter (vsy_List *list,
                            Vint *index,
                            Vobject **value)
Each call of the method vsy_ListNextIter will return a new item from the list together with its associated index. After every object has been visited in this manner, vsy_ListNextIter will return a NULL pointer until the iteration is restarted using vsy_ListInitIter. Objects are visited starting from position zero, and empty positions in the list are skipped over.


Table of Contents

4.3 Last-In First-Out Storage - Stack

The Stack module holds a sequence of objects which are accessed in a last-in/first-out fashion. The Stack object may expand or shrink to contain varying numbers of objects. It also supports an "iterator" function, which is used to successively visit each object in the stack.

Instance a Stack object using vsy_StackBegin. Once a Stack is instanced, an approximate number of objects to be stored may be defined using vsy_StackDef. This allocates an internal array for the storage of object pointers. As objects are inserted the Stack module will adjust memory as required. The actual size of the allocated storage may be determined by calling vsy_StackInq.

Each new object is placed in the stack by calling vsy_StackPush. The total number of objects contained in the stack may be found by calling vsy_StackCount. The object which was most recently pushed is accessed using vsy_StackRef. The uppermost object is removed and the stack shortened by one position with each call to the vsy_StackPop method. The method vsy_StackClear removes all objects from the stack. Unused storage at the end of the internal array may be released by calling vsy_StackCompact. This is useful when a very large stack has been greatly shortened from its earlier size.

All objects in the stack may be processed with an "iterator" method, vsy_StackForEach, which takes a function pointer as its argument. It calls that function repeatedly, each time with one object from the stack passed as an argument.

Table of Contents

4.4 Function Descriptions

The currently available Stack functions are described in detail in this section.


Table of Contents , Stack

NAME

*vsy_StackBegin - create an instance of a Stack object

C SPECIFICATION

vsy_Stack *vsy_StackBegin ()

ARGUMENTS

None

FUNCTION RETURN VALUE

The function returns a pointer to the newly created Stack object. If the object creation fails, NULL is returned.

DESCRIPTION

Create an instance of a Stack object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a Stack object using

     void vsy_StackEnd (vsy_Stack *stack)

Return the current value of a Stack object error flag using

     Vint vsy_StackError (vsy_Stack *stack)


Table of Contents , Stack

NAME

vsy_StackDef - define initial length of storage array

C SPECIFICATION

void vsy_StackDef (vsy_Stack *stack,
                   Vint numobj)

INPUT ARGUMENTS

stack        Pointer to Stack object.
numobj       Estimated number of objects to be held.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Suggest a number of elements to be stored in the Stack. This is used to allocate the initial array of storage which is used to hold a pointer to each stored object. If the number of inserted elements is greater than this initial estimate, storage space is dynamically expanded to hold the extra objects. This function removes any previously entered objects.

Find the current length of the internal storage of a Stack using

     void vsy_StackInq (const vsy_Stack *stack,
                        Vint *numobj)


Table of Contents , Stack

NAME

vsy_StackCount - get number of contained objects

C SPECIFICATION

void vsy_StackCount (const vsy_Stack *stack,
                     Vint *num)

INPUT ARGUMENTS

stack         Pointer to Stack object.

OUTPUT ARGUMENTS

num          Number of objects held in the Stack object.

DESCRIPTION

Get the number of objects which have been pushed onto the stack, and not yet popped from the stack.


Table of Contents , Stack

NAME

vsy_StackPush - place an object on the top of the stack

C SPECIFICATION

void vsy_StackPush (vsy_Stack *stack,
                    Vobject *value)

INPUT ARGUMENTS

stack        Pointer to Stack object.
value        Pointer to the object.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Place the object value on the top of the stack, expanding the internal storage of the Stack module as needed.


Table of Contents , Stack

NAME

vsy_StackRef - get the object at the top of the stack

C SPECIFICATION

void vsy_StackRef (const vsy_Stack *stack,	
                   Vobject **value)

INPUT ARGUMENTS

stack        Pointer to Stack object.

OUTPUT ARGUMENTS

value        Object found at the top of the stack.

DESCRIPTION

Get a pointer to the uppermost object in the stack. This is the object which was pushed most recently, and not yet popped from its position. Returns a NULL pointer if no object has been placed on the stack, or if all previously pushed objects have since been removed.


Table of Contents , Stack

NAME

vsy_StackPop - remove an object from the top of the stack

C SPECIFICATION

void vsy_StackPop (vsy_Stack *stack)

INPUT ARGUMENTS

stack         Pointer to Stack object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Remove the object found at the top of the stack, reducing the height of the stack by one. If the stack is already empty, then no action is performed.

Remove all the objects from a Stack object using

     void vsy_StackClear (vsy_Stack *stack)

Release any unused internal storage using

     void vsy_StackCompact (vsy_Stack *stack)


Table of Contents , Stack

NAME

vsy_StackForEach - process each item in the stack

C SPECIFICATION

void vsy_StackForEach (vsy_Stack *stack,
                       void (*func)(Vobject*))

INPUT ARGUMENTS

stack        Pointer to Stack object.
func         Pointer to function which is to be applied to each object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Calls the supplied function repeatedly, each time using an object from the stack as a sole argument to this function. This is useful for deallocating a collection of objects, prior to calling vsy_StackEnd. The first object visited is on the bottom of the stack, and the top of the stack is visited last.


Table of Contents

4.5 Storage Accessed by Name - Dictionary

The Dictionary module holds a collection of objects which are each identified by name. The matching of names during object retrieval is case sensitive. The Dictionary object may expand to contain increasing numbers of objects. It also supports several "iterator" functions, which are used to successively visit each object in the dictionary.

Instance a Dictionary object using vsy_DictionaryBegin. Once a Dictionary is instanced, an approximate number of objects to be stored may defined using vsy_DictionaryDef. As objects are inserted the Dictionary module will adjust memory as required. The actual size of the allocated storage may be determined by calling vsy_DictionaryInq.

Each new object is placed in the dictionary by calling vsy_DictionaryInsert. The total number of objects contained in the dictionary may be found with vsy_DictionaryCount. The object with a specified name may be found by calling vsy_DictionaryLookup. An object may be removed using vsy_DictionaryRemove. The method vsy_DictionaryClear removes all objects from the dictionary.

Each object in the dictionary may be processed with an "iterator" construct. The single method vsy_DictionaryForEach takes a function as its argument and calls that function repeatedly; each call of the function is supplied one object from the dictionary. The pair of methods vsy_DictionaryInitIter and vsy_DictionaryNextIter are used to visit each name/object pair using a loop. Call the first method before the body of the loop to prepare the Dictionary object for the iteration. Within the loop body, call vsy_DictionaryNextIter. It will return the name of and a pointer to an object each time it is called. It will return two NULL pointers when all of the objects have been visited. Use vsy_DictionaryInitIterOrder to visit the objects in name alphabetical order

Table of Contents

4.6 Function Descriptions

The currently available Dictionary functions are described in detail in this section.


Table of Contents , Dictionary

NAME

*vsy_DictionaryBegin - create an instance of an Dictionary object

C SPECIFICATION

vsy_Dictionary *vsy_DictionaryBegin ()

ARGUMENTS

None

FUNCTION RETURN VALUE

The function returns a pointer to the newly created Dictionary object. If the object creation fails, NULL is returned.

DESCRIPTION

Create an instance of a Dictionary object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a Dictionary object using

     void vsy_DictionaryEnd (vsy_Dictionary *dictionary)

Return the current value of a Dictionary object error flag using

     Vint vsy_DictionaryError (vsy_Dictionary *dictionary)


Table of Contents , Dictionary

NAME

vsy_DictionaryDef - define initial size

C SPECIFICATION

void vsy_DictionaryDef (vsy_Dictionary *dictionary,
                        Vint numobj)

INPUT ARGUMENTS

dictionary   Pointer to Dictionary object.
numobj       Estimated number of objects to be held.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Suggest a number of elements to be stored in the Dictionary. This is used to allocate an initial array of storage which is used to hold the pointer to each stored object. Since the name/object pairs are stored sparsely within the Dictionary module, the actual length of the internal array is larger than this supplied number. This function removes any previously entered objects.

Find the number of objects which may be managed by the currently allocated internal storage of a Dictionary using

     void vsy_DictionaryInq (const vsy_Dictionary *dictionary,
                             Vint *numobj,


Table of Contents , Dictionary

NAME

vsy_DictionaryCount - get number of contained objects

C SPECIFICATION

void vsy_DictionaryCount (const vsy_Dictionary *dictionary,
                          Vint *num)

INPUT ARGUMENTS

dictionary   Pointer to Dictionary object.

OUTPUT ARGUMENTS

num          Number of objects held the in Dictionary object.

DESCRIPTION

Get the number of objects which have been inserted and not yet removed.


Table of Contents , Dictionary

NAME

vsy_DictionaryInsert - place an object in the dictionary

C SPECIFICATION

void vsy_DictionaryInsert (vsy_Dictionary *dictionary,
                           const Vchar *name,
                           Vobject *value)

INPUT ARGUMENTS

dictionary   Pointer to Dictionary object.
name         String which identifies the object.
value        Pointer to the object.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Place the object value in the dictionary, associated with the specified name. This will replace any object which may have previously inserted with the same name. All name comparisons are case sensitive. A copy of the name is made internal to the Dictionary object.


Table of Contents , Dictionary

NAME

vsy_DictionaryLookup - find the object at a specified location

C SPECIFICATION

void vsy_DictionaryLookup (const vsy_Dictionary *dictionary,	
                           const Vchar *name,
                           Vobject **value)

INPUT ARGUMENTS

dictionary   Pointer to Dictionary object.
name         Name of the desired object.

OUTPUT ARGUMENTS

value        Object associated with the specified name.

DESCRIPTION

Get a pointer to the object with the specified name. Returns a NULL pointer if no object with that name has been previously inserted into the dictionary. All name comparisons are case sensitive.


Table of Contents , Dictionary

NAME

vsy_DictionaryRemove - remove an object from the dictionary

C SPECIFICATION

void vsy_DictionaryRemove (vsy_Dictionary *dictionary,
                           const Vchar *name)

INPUT ARGUMENTS

dictionary   Pointer to Dictionary object.
name         Name of the object to be removed. 

OUTPUT ARGUMENTS

None

DESCRIPTION

Remove the object with the specified name.

Remove all the objects from a Dictionary object using

     void vsy_DictionaryClear (vsy_Dictionary *dictionary)


Table of Contents , Dictionary

NAME

vsy_DictionaryForEach - process each item in the dictionary

C SPECIFICATION

void vsy_DictionaryForEach (vsy_Dictionary *dictionary,
                            void (*func)(Vobject*))

INPUT ARGUMENTS

dictionary   Pointer to Dictionary object.
func         Pointer to function which is to be applied to each object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Calls the supplied function repeatedly, each time using an object from the dictionary as the sole argument to this function. This is useful for deallocating a collection of objects, prior to calling vsy_DictionaryEnd. The objects are visited in an unspecified order.

Sequential access to each item in the dictionary may also be implemented using

     void vsy_DictionaryInitIter (vsy_Dictionary *dictionary)

Sequential access to each item in alphabetical order of the dictionary name using.

     void vsy_DictionaryInitIterOrder (vsy_Dictionary *dictionary)

This is followed by repeated calls to the method

     void vsy_DictionaryNextIter (vsy_Dictionary *dictionary,
                                  Vchar **name,
                                  Vobject **value)
Each call of the method vsy_DictionaryNextIter will return one object from the dictionary. It will also return a pointer to the name used within the dictionary. Do not deallocate this string! It is a pointer to the storage used within the Dictionary object itself. After every object has been visited in this manner, vsy_DictionaryNextIter will return two NULL pointers until the iteration is restarted using vsy_DictionaryInitIter. The objects are visited in an unspecified order.


Table of Contents

4.7 Storage Accessed by Integer - HashTable

The HashTable module holds a collection of objects which are identified by integer key values. The HashTable object may expand to contain an increasing number of objects. It also supports several "iterator" functions, which are used to successively visit each object stored in the hashtable.

Instance a HashTable object using vsy_HashTableBegin. Once a HashTable is instanced, an approximate number of objects to be stored may be defined using vsy_HashTableDef. This allocates an internal array for the storage of object pointers. As objects are inserted HashTable module will expand its internal storage as required. The method vsy_HashTableInq returns the number of objects which may be managed by the presently allocated storage.

Each new object is placed in the hashtable using vsy_HashTableInsert. The total number of objects contained in the hashtable may be found by calling vsy_HashTableCount. An object with a specified integer key may be retrieved using vsy_HashTableLookup. An object with a given key value may be removed with vsy_HashTableRemove. The method vsy_HashTableClear removes all objects from the hashtable. The maximum key used to store any object may be queried using vsy_HashTableMaxKey. All keys may be queried using vsy_HashTableAllKeys. In this case the number of keys returned will be equal to the number of keys returned by vsy_HashTableCount.

Each object in the hashtable may be processed with an "iterator" construct. The method vsy_HashTableForEach takes a function as its argument and calls that function repeatedly, each time with an object from the hashtable. The pair of methods vsy_HashTableInitIter and vsy_HashTableNextIter are used to visit each key/object pair using a loop. Call the first method before the body of the loop to prepare the HashTable object for the iteration. Within the loop body, call vsy_HashTableNextIter. It will return an integer key and an object each time it is called. It will return zero and a NULL pointer when all of the objects have been processed.

Table of Contents

4.8 Function Descriptions

The currently available HashTable functions are described in detail in this section.


Table of Contents , HashTable

NAME

*vsy_HashTableBegin - create an instance of a HashTable object

C SPECIFICATION

vsy_HashTable *vsy_HashTableBegin ()

ARGUMENTS

None

FUNCTION RETURN VALUE

The function returns a pointer to the newly created HashTable object. If the object creation fails, NULL is returned.

DESCRIPTION

Create an instance of an HashTable object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a HashTable object using

     void vsy_HashTableEnd (vsy_HashTable *hashtable)

Return the current value of a HashTable object error flag using

     Vint vsy_HashTableError (vsy_HashTable *hashtable)


Table of Contents , HashTable

NAME

vsy_HashTableDef - define initial length of storage array

C SPECIFICATION

void vsy_HashTableDef (vsy_HashTable *hashtable,
                       Vint numobj)

INPUT ARGUMENTS

hashtable    Pointer to HashTable object.
numobj       Estimated number of objects to be held.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Suggest a number of elements to be stored in the HashTable. This is used to allocate the initial array of storage which is used to hold each integer/object pair. If the number of inserted elements is eventually greater than this initial estimate, storage space will dynamically expanded to hold the extra objects. This function removes any previously entered objects.

Find the number of objects which may be managed with the presently allocated storage using

     void vsy_HashTableInq (const vsy_HashTable *hashtable,
                            Vint *num)


Table of Contents , HashTable

NAME

vsy_HashTableCount - get number of contained objects

C SPECIFICATION

void vsy_HashTableCount (const vsy_HashTable *hashtable,
                         Vint *num)

INPUT ARGUMENTS

hashtable    Pointer to HashTable object.

OUTPUT ARGUMENTS

num          Number of objects held the in HashTable object.

DESCRIPTION

Get the number of objects which have been inserted and not yet removed.


Table of Contents , HashTable

NAME

vsy_HashTableMaxKey - get maximum key value

C SPECIFICATION

void vsy_HashTableMaxKey (const vsy_HashTable *hashtable,
                          Vint *maxkey)

INPUT ARGUMENTS

hashtable    Pointer to HashTable object.

OUTPUT ARGUMENTS

maxkey       Maximum key value

DESCRIPTION

Get the maximum key value used to store current objects in HashTable.


Table of Contents , HashTable

NAME

vsy_HashTableAllKeys - get all key values

C SPECIFICATION

void vsy_HashTableAllKeys (const vsy_HashTable *hashtable,
                           Vint allkeys[])

INPUT ARGUMENTS

hashtable    Pointer to HashTable object.

OUTPUT ARGUMENTS

allkeys      Array of all keys

DESCRIPTION

Get all key values used to store current objects in HashTable. The number of key values returned will be equal the the number of keys returned by the function vsy_HashTableCount.


Table of Contents , HashTable

NAME

vsy_HashTableInsert - place an object in the hashtable

C SPECIFICATION

void vsy_HashTableInsert (vsy_HashTable *hashtable,
                          Vint key,
                          Vobject *value)

INPUT ARGUMENTS

hashtable    Pointer to HashTable object.
key          Integer key value. 
value        Pointer to the object.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Place the object value in the HashTable object. Associate the integer key with this new object, and remove any object which may have been previously associated with this same key.


Table of Contents , HashTable

NAME

vsy_HashTableLookup - find the object at a specified location

C SPECIFICATION

void vsy_HashTableLookup (const vsy_HashTable *hashtable,	
                          Vint key,
                          Vobject **value)

INPUT ARGUMENTS

hashtable    Pointer to HashTable object.
key          Integer key of the desired object. 

OUTPUT ARGUMENTS

value        Object associated with key.

DESCRIPTION

Get a pointer to the object associated the specified key. Returns a NULL pointer if no object has been entered with this key, or if the previously inserted object with this key has since been removed.


Table of Contents , HashTable

NAME

vsy_HashTableRemove - remove an object from the hashtable

C SPECIFICATION

void vsy_HashTableRemove (vsy_HashTable *hashtable,
                          Vint key)

INPUT ARGUMENTS

hashtable    Pointer to HashTable object.
key          Key of object to be removed.

OUTPUT ARGUMENTS

None

DESCRIPTION

Remove any object associated with the specified key. If no such object is found, then no action is performed.

Remove all the objects from a HashTable object using

     void vsy_HashTableClear (vsy_HashTable *hashtable)


Table of Contents , HashTable

NAME

vsy_HashTableForEach - process each item in the hashtable

C SPECIFICATION

void vsy_HashTableForEach (vsy_HashTable *hashtable,
                           void (*func)(Vobject*))

INPUT ARGUMENTS

hashtable    Pointer to HashTable object.
func         Pointer to function which is to be applied to each object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Calls the supplied function repeatedly, each time using an object from the hashtable as the sole argument to this function. This is useful for deallocating a collection of objects, prior to calling vsy_HashTableEnd. The objects are visited in an unspecified order.

Sequential access to each item in the hashtable may also be implemented using

     void vsy_HashTableInitIter (vsy_HashTable *hashtable)

Sequential access to each item in numerical order of the hashtable key using.

     void vsy_HashTableInitIterOrder (vsy_HashTable *hashtable)

This is followed by repeated calls to the method

     void vsy_HashTableNextIter (vsy_HashTable *hashtable,
                                 Vint *key
                                 Vobject **value)
Each call of the method vsy_HashTableNextIter will return a new item from the hashtable, together with its associated key. After every object has been visited in this manner, vsy_HashTableNextIter will return a key of zero and a NULL pointer. If the iteration is started using vsy_HashTableInitIter, these key/value pairs are visited in arbitrary order. If the iteration is started using vsy_HashTableInitIterOrder, these key/value pairs are visited in numerical order of the key.


Table of Contents

4.9 Multiple Integer Key Hashtable - VHashTable

The VHashTable module is similar to the HashTable module except that the scalar integer key is generalized to an arbitrarily sized vector of integer keys.

Instance a VHashTable object using vsy_VHashTableBegin. Once a VHashTable is instanced, define the size of the vector of integer keys and an approximate number of objects to be stored using vsy_VHashTableDef. As objects are inserted VHashTable module will expand its internal storage as required. The method vsy_VHashTableInq returns the number of integers defined in a vector key and the number of objects which may be managed by the presently allocated storage.

Each new object is placed in the hashtable using vsy_VHashTableInsert. The total number of objects contained in the hashtable may be found by calling vsy_VHashTableCount. An object with a specified vector of integer keys may be retrieved using vsy_VHashTableLookup. The method vsy_VHashTableClear removes all objects from the hashtable.

Each object in the hashtable may be processed with an "iterator" construct. The pair of methods vsy_VHashTableInitIter and vsy_VHashTableNextIter are used to visit each key-vector/object pair using a loop. Call the first method before the body of the loop to prepare the VHashTable object for the iteration. Within the loop body, call vsy_VHashTableNextIter. It will return an integer key and an object value each time it is called. It will return a zero value when all of the objects have been processed.

Table of Contents

4.10 Function Descriptions

The currently available VHashTable functions are described in detail in this section.


Table of Contents , VHashTable

NAME

*vsy_VHashTableBegin - create an instance of a VHashTable object

C SPECIFICATION

vsy_VHashTable *vsy_VHashTableBegin ()

ARGUMENTS

None

FUNCTION RETURN VALUE

The function returns a pointer to the newly created VHashTable object. If the object creation fails, NULL is returned.

DESCRIPTION

Create an instance of an VHashTable object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a VHashTable object using

     void vsy_VHashTableEnd (vsy_VHashTable *vhashtable)

Return the current value of a VHashTable object error flag using

     Vint vsy_VHashTableError (vsy_VHashTable *vhashtable)


Table of Contents , VHashTable

NAME

vsy_VHashTableDef - define initial length of storage array

C SPECIFICATION

void vsy_VHashTableDef (vsy_VHashTable *vhashtable,
                        Vint size,
                        Vint numobj)

INPUT ARGUMENTS

vhashtable   Pointer to VHashTable object.
size         Number of integers per key-vector
numobj       Estimated number of objects to be held.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Suggest a number of objects to be stored in the VHashTable. This is used to allocate the initial array of storage which is used to hold each integer/object pair. If the number of inserted elements is eventually greater than this initial estimate, storage space will dynamically expanded to hold the extra objects. This function removes any previously entered objects.

Find the number of objects which may be managed with the presently allocated storage using

     void vsy_VHashTableInq (const vsy_VHashTable *vhashtable,
                             Vint *size,
                             Vint *numobj)


Table of Contents , VHashTable

NAME

vsy_VHashTableCount - get number of contained objects

C SPECIFICATION

void vsy_VHashTableCount (const vsy_VHashTable *vhashtable,
                          Vint *num)

INPUT ARGUMENTS

vhashtable   Pointer to VHashTable object.

OUTPUT ARGUMENTS

num          Number of objects held the in VHashTable object.

DESCRIPTION

Get the number of objects which have been inserted and not yet removed.


Table of Contents , VHashTable

NAME

vsy_VHashTableInsert - place an object in the hashtable

C SPECIFICATION

void vsy_VHashTableInsert (vsy_VHashTable *vhashtable,
                           Vint key[],
                           Vobject *value)

INPUT ARGUMENTS

vhashtable   Pointer to VHashTable object.
key          Integer key values. 
value        Object value.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated. SYS_ERROR_VALUE is generated if value is zero.

DESCRIPTION

Place the object value in the VHashTable object. Associate the integers key with this new object, and replace any object which may have been previously associated with this same key.


Table of Contents , VHashTable

NAME

vsy_VHashTableLookup - find the object at a specified location

C SPECIFICATION

void vsy_VHashTableLookup (const vsy_VHashTable *vhashtable,	
                           Vint key[],
                           Vobject **value)

INPUT ARGUMENTS

vhashtable   Pointer to VHashTable object.
key          Integer key values of the desired object. 

OUTPUT ARGUMENTS

value        object associated with key.

DESCRIPTION

Get the object associated the specified key. Returns a NULL value if no object has been entered with this key.


Table of Contents , VHashTable

NAME

vsy_VHashTableRemove - remove an object from the hashtable

C SPECIFICATION

void vsy_VHashTableRemove (vsy_VHashTable *vhashtable,
                           Vint key[])

INPUT ARGUMENTS

vhashtable   Pointer to VHashTable object.
key          Keys of object to be removed.

OUTPUT ARGUMENTS

None

DESCRIPTION

Remove any object associated with the specified key. If no such object is found, then no action is performed.

Remove all the objects from a VHashTable object using

     void vsy_VHashTableClear (vsy_VHashTable *vhashtable)


Table of Contents , VHashTable

NAME

vsy_VHashTableInitIter,vsy_VHashTableNextIter - successively visit each object

C SPECIFICATION

void vsy_VHashTableInitIter (vsy_VHashTable *vhashtable)

void vsy_VHashTableNextIter (vsy_VHashTable *vhashtable,
                             Vint *key)
                             Vobject **value)

INPUT ARGUMENTS

vhashtable   Pointer to VHashTable object.

OUTPUT ARGUMENTS

key          Integer keys.
value        Object associated with key

DESCRIPTION

Each call of the method vsy_VHashTableNextIter will return a new item from the hashtable, together with its associated keys. These key/value pairs are visited in arbitrary order. After every object has been visited in this manner, vsy_VHashTableNextIter will return a key of zeros and a zero value until the iteration is restarted using vsy_VHashTableInitIter.


Table of Contents

4.11 Tree Data Structure - Tree

The Tree module holds a collection of objects in a tree-like structure. It also supports an "iterator" function which can be called simultaneously at multiple levels of the tree to request a node's children.

Instance a Tree object using vsy_TreeBegin. Once a Tree is instanced, the root node is generated by using vsy_TreeAddNode with the parent node identified as 0. Nodes can be added to the tree by calling vsy_TreeAddNode with a specific parent node id. An object can be set into a node using vsy_TreeSetValue and may be retrieved for later use with vsy_TreeGetValue.

Each parent node the tree may be processed with an "iterator" construct. The method vsy_TreeFirstChild takes a parent node as its argument and returns the node's first child. Subsequent calls to vsy_TreeNextChild returns the next sibling of the given child. A returned value of zero indicates that all children have been visited.

Table of Contents

4.12 Function Descriptions

The currently available Tree functions are described in detail in this section.


Table of Contents , Tree

NAME

*vsy_TreeBegin - create an instance of a Tree object

C SPECIFICATION

vsy_Tree *vsy_TreeBegin ()

ARGUMENTS

None

FUNCTION RETURN VALUE

The function returns a pointer to the newly created Tree object. If the object creation fails, NULL is returned.

DESCRIPTION

Create an instance of an Tree object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a Tree object using

     void vsy_TreeEnd (vsy_Tree *tree)

Return the current value of a Tree object error flag using

     Vint vsy_TreeError (vsy_Tree *tree)


Table of Contents , Tree

NAME

vsy_TreeAddNode - add a node to a parent node

C SPECIFICATION

void vsy_TreeAddNode (vsy_Tree *tree,
                      Vint pkey,
                      Vint *ckey)

INPUT ARGUMENTS

tree    Pointer to Tree object.
pkey    Integer parent node id

OUTPUT ARGUMENTS

ckey    Integer child node id

ERRORS

SYS_ERROR_OPERATION is generated if the parent node does not exist. SYS_ERROR_MEMORY is generated if the tree's growth is memory-limited.

DESCRIPTION

Add a node to the parent with node id pkey. The newly created node will have a node id ckey which can be used for later reference.


Table of Contents , Tree

NAME

vsy_TreeDelNode - delete a node and its children

C SPECIFICATION

void vsy_TreeDelNode (vsy_Tree *tree,	
                      Vint key)

INPUT ARGUMENTS

tree    Pointer to Tree object.
key     Integer id of the node to be deleted along with its children.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_OPERATION is generated if the node does not exist.

DESCRIPTION

Delete a node and all its children from the tree.


Table of Contents , Tree

NAME

vsy_TreeSetValue - place an object in a node

C SPECIFICATION

void vsy_TreeSetValue (vsy_Tree *tree,
                       Vint key,
                       Vobject *value)

INPUT ARGUMENTS

tree    Pointer to Tree object.
key     Integer id of node that will hold the object
value   Pointer to the object.

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_OPERATION is generated if the node does not exist.

DESCRIPTION

Place the object value in the node of id key. Removes any object which may have been previously associated with this same node.


Table of Contents , Tree

NAME

vsy_TreeGetValue - retrieves object from specified node

C SPECIFICATION

void vsy_TreeGetValue (vsy_Tree *tree,	
                       Vint key,
                       Vobject **value)

INPUT ARGUMENTS

tree    Pointer to Tree object.
key     Integer id of node holding the object

OUTPUT ARGUMENTS

value   Object associated with key.

DESCRIPTION

Get a pointer to the object associated the specified node key. Returns a NULL pointer if no object has been entered into this node, or if the previously inserted object has since been removed.


Table of Contents , Tree

NAME

vsy_TreeForEach - process each item in the tree

C SPECIFICATION

void vsy_TreeForEach (vsy_Tree *tree,
                      void (*func)(Vobject*))

INPUT ARGUMENTS

tree    Pointer to Tree object.
func    Pointer to function which is to be applied to each object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Calls the supplied function repeatedly, each time using an object from the tree retrieved internally with vsy_TreeGetValue as the sole argument to this function. This is useful for deallocating a collection of objects, prior to calling vsy_TreeEnd. The objects are visited in an unspecified order.

Sequential access to each item in the tree may also be implemented by retrieving the first child of a node using

     Vint vsy_TreeFirstChild (vsy_Tree *tree,
                              Vint key,
                              Vint *child)

This is followed by repeated calls to the method

     Vint vsy_TreeNextChild (vsy_Tree *tree,
                             Vint key,
                             Vint *child)
Each call of the method vsy_TreeNextChild will return a new item from the tree. After every object has been visited in this manner, vsy_TreeNextChild will return a value of zero. The list of siblings is returned in an arbitrary order.

A typical construct for looping over a node's children is as follows:

   Vint parent, child;

   vsy_TreeFirstChild (tree,parent,&child);
   while(child != 0) {
      /* your code here */
      ...;
      vsy_TreeNextChild (tree,child,&child);
   }