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

CEETRON SAM 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 CEETRON SAM type Vobject*. The type Vobject* is the C language type void*, so that any void* type may be stored in collection objects.

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.

4.1.1. Function Descriptions

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

vsy_List *vsy_ListBegin(void)

create an instance of a

List object

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)

Returns:

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

void vsy_ListEnd(vsy_List *p)

destroy an instance of a List object

See vsy_ListBegin()

Vint vsy_ListError(vsy_List *p)

return the current value of a List object error flag

See vsy_ListBegin()

void vsy_ListDef(vsy_List *p, Vint numobj)

define initial length of storage array

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)

Errors

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

Parameters:

  • p – Pointer to List object.

  • numobj – Estimated number of objects to be held.

void vsy_ListInq(const vsy_List *p, Vint *len)

find the current length of the internal storage

See vsy_ListDef()

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

get number of contained objects

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

Parameters:

  • p – Pointer to List object.

  • num – [out] Number of objects held the in List object.

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

get maximum index

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

Parameters:

  • p – Pointer to List object.

  • maxindex – [out] Maximum index

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

get all indices

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

Parameters:

  • p – Pointer to List object.

  • allindices – [out] Array of all indices

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

place an object in the list

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)

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.

Parameters:

  • p – Pointer to List object.

  • index – Position in list at which object is to be stored.

  • value – Pointer to the object.

void vsy_ListAdd(vsy_List *p, Vobject *value, Vint *idx)

add an object in the list

See vsy_ListInsert()

void vsy_ListAppend(vsy_List *p, Vobject *value)

placed object at the end of the list

See vsy_ListInsert()

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

find the object at a specified location

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.

Parameters:

  • p – Pointer to List object.

  • index – Location of the desired object.

  • value – [out] Object found at location index.

void vsy_ListRemove(vsy_List *p, Vint index)

remove an object from the list

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)

Parameters:

  • p – Pointer to List object.

  • index – Location to be emptied.

void vsy_ListClear(vsy_List *p)

remove all the objects from a List object

See vsy_ListRemove()

void vsy_ListCompact(vsy_List *p)

release any unused internal storage

See vsy_ListRemove()

void vsy_ListInitIter(vsy_List *p)

sequential access to each item in the list

See vsy_ListForEach()

void vsy_ListNextIter(vsy_List *p, Vint *idx, Vobject **value)

sequential access to each item in the list

See vsy_ListForEach()

void vsy_ListForEach(vsy_List *p, Vfunc1 *func)

process each item in the list

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.

Parameters:

  • p – Pointer to List object.

  • func – Pointer to function which is to be applied to each object.

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

4.2.1. Function Descriptions

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

vsy_Stack *vsy_StackBegin(void)

create an instance of a Stack object

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)

Returns:

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

void vsy_StackEnd(vsy_Stack *p)

destroy an instance of a Stack object

See vsy_StackBegin()

Vint vsy_StackError(vsy_Stack *p)

return the current value of a Stack object error flag

See vsy_StackBegin()

void vsy_StackDef(vsy_Stack *p, Vint numobj)

define initial length of storage array

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)

Errors

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

Parameters:

  • p – Pointer to Stack object.

  • numobj – Estimated number of objects to be held.

void vsy_StackInq(const vsy_Stack *p, Vint *len)

find the current length of the internal storage

See vsy_StackDef()

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

get number of contained objects

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

Parameters:

  • p – Pointer to Stack object.

  • num – [out] Number of objects held in the Stack object.

void vsy_StackPush(vsy_Stack *p, Vobject *value)

place an object on the top of the stack

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

Errors

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

Parameters:

  • p – Pointer to Stack object.

  • value – Pointer to the object.

void vsy_StackPop(vsy_Stack *p)

remove an object from the top of the stack

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)

Parameters:

p – Pointer to Stack object.

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

get the object at the top of the stack

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.

Parameters:

  • p – Pointer to Stack object.

  • value – [out] Object found at the top of the stack.

void vsy_StackClear(vsy_Stack *p)

remove all the objects from a Stack object

See vsy_StackPop()

void vsy_StackCompact(vsy_Stack *p)

release any unused internal storage

See vsy_StackPop()

void vsy_StackForEach(vsy_Stack *p, Vfunc1 *func)

process each item in the stack

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.

Parameters:

  • p – Pointer to Stack object.

  • func – Pointer to function which is to be applied to each object.

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

4.3.1. Function Descriptions

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

vsy_Dictionary *vsy_DictionaryBegin(void)

create an instance of a Dictionary object

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)

Returns:

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

void vsy_DictionaryEnd(vsy_Dictionary *p)

destroy an instance of a Dictionary object

See vsy_DictionaryBegin()

Vint vsy_DictionaryError(vsy_Dictionary *p)

return the current value of a Dictionary object error

See vsy_DictionaryBegin()

void vsy_DictionaryDef(vsy_Dictionary *p, Vint numobj)

define initial size

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,

Errors

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

Parameters:

  • p – Pointer to Dictionary object.

  • numobj – Estimated number of objects to be held.

void vsy_DictionaryInq(const vsy_Dictionary *p, Vint *nument)

find the number of objects which may be managed by the currently allocated internal storage

See vsy_DictionaryDef()

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

get number of contained objects

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

Parameters:

  • p – Pointer to Dictionary object.

  • num – [out] Number of objects held the in Dictionary object.

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

place an object in the dictionary

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.

Errors

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

Parameters:

  • p – Pointer to Dictionary object.

  • name – String which identifies the object.

  • value – Pointer to the object.

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

find the object at a specified location

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.

Parameters:

  • p – Pointer to Dictionary object.

  • name – Name of the desired object.

  • value – [out] Object associated with the specified name.

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

remove an object from the dictionary

Remove the object with the specified name.

Remove all the objects from a Dictionary object using 

void vsy_DictionaryClear (vsy_Dictionary *dictionary)

Parameters:

  • p – Pointer to Dictionary object.

  • name – Name of the object to be removed.

void vsy_DictionaryClear(vsy_Dictionary *p)

remove all the objects from a Dictionary object

See vsy_DictionaryRemove()

void vsy_DictionaryForEach(vsy_Dictionary *p, Vfunc1 *func)

process each item in the dictionary

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.

Parameters:

  • p – Pointer to Dictionary object.

  • func – Pointer to function which is to be applied to each object.

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

4.4.1. Function Descriptions

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

vsy_HashTable *vsy_HashTableBegin(void)

create an instance of a HashTable object

Create an instance of a 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)

Returns:

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

void vsy_HashTableEnd(vsy_HashTable *p)

destroy an instance of a HashTable object

See vsy_HashTableBegin()

Vint vsy_HashTableError(vsy_HashTable *p)

return the current value of a HashTable object error flag

See vsy_HashTableBegin()

void vsy_HashTableDef(vsy_HashTable *p, Vint numobj)

define initial length of storage array

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)

Errors

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

Parameters:

  • p – Pointer to HashTable object.

  • numobj – Estimated number of objects to be held.

void vsy_HashTableInq(const vsy_HashTable *p, Vint *nument)

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

See vsy_HashTableDef()

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

get number of contained objects

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

Parameters:

  • p – Pointer to HashTable object.

  • num – [out] Number of objects held the in HashTable object.

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

get maximum key value

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

Parameters:

  • p – Pointer to HashTable object.

  • maxkey – [out] Maximum key value

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

get all key values

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

Parameters:

  • p – Pointer to HashTable object.

  • allkeys – [out] Array of all keys

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

place an object in the hashtable

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.

Errors

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

Parameters:

  • p – Pointer to HashTable object.

  • key – Integer key value.

  • value – Pointer to the object.

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

find the object at a specified location

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.

Parameters:

  • p – Pointer to HashTable object.

  • key – Integer key of the desired object.

  • value – [out] Object associated with key.

void vsy_HashTableRemove(vsy_HashTable *p, Vint key)

remove an object from the hashtable

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)

Parameters:

  • p – Pointer to HashTable object.

  • key – Key of object to be removed.

void vsy_HashTableClear(vsy_HashTable *p)

remove an object from the hashtable

See vsy_HashTableRemove()

void vsy_HashTableInitIter(vsy_HashTable *p)

sequential access to each item

See vsy_HashTableForEach()

void vsy_HashTableInitIterOrder(vsy_HashTable *p)

sequential access to each item in numerical order

See vsy_HashTableForEach()

void vsy_HashTableNextIter(vsy_HashTable *p, Vint *key, Vobject **value)

sequential access to each item in numerical order

See vsy_HashTableForEach()

void vsy_HashTableForEach(vsy_HashTable *p, Vfunc1 *func)

process each item in the hashtable

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.

Parameters:

  • p – Pointer to HashTable object.

  • func – Pointer to function which is to be applied to each object.

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

4.5.1. Function Descriptions

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

vsy_VHashTable *vsy_VHashTableBegin(void)

create an instance of a VHashTable object

Create an instance of a 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)

Returns:

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

void vsy_VHashTableEnd(vsy_VHashTable *p)

destroy an instance of a VHashTable object

See vsy_VHashTableBegin()

Vint vsy_VHashTableError(vsy_VHashTable *p)

return the current value of a VHashTable object error flag

See vsy_VHashTableBegin()

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

define initial length of storage array

Suggest a number of elements 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 *isize,
                       Vint *numobj)

Errors

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

Parameters:

  • p – Pointer to VHashTable object.

  • size – Number of integers per key-vector

  • numobj – Estimated number of objects to be held.

void vsy_VHashTableInq(const vsy_VHashTable *p, Vint *size, Vint *nument)

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

See vsy_VHashTableDef()

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

get number of contained objects

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

Parameters:

  • p – Pointer to VHashTable object.

  • num – [out] Number of objects held the in VHashTable object.

void vsy_VHashTableInsert(vsy_VHashTable *p, const Vint *key, Vobject *value)

place an object in the hashtable

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

Errors

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

  • SYS_ERROR_VALUE is generated if value is zero.

Parameters:

  • p – Pointer to VHashTable object.

  • key – Integer key value.

  • value – Object value.

void vsy_VHashTableLookup(const vsy_VHashTable *p, const Vint *key, Vobject **value)

find the object at a specified location

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

Parameters:

  • p – Pointer to VHashTable object.

  • key – Integer key of the desired object.

  • value – [out] Object associated with key.

void vsy_VHashTableRemove(vsy_VHashTable *p, const Vint *key)

remove an object from the hashtable

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)

Parameters:

  • p – Pointer to VHashTable object.

  • key – Key of object to be removed.

void vsy_VHashTableClear(vsy_VHashTable *p)

remove an object from the hashtable

See vsy_VHashTableRemove()

void vsy_VHashTableInitIter(vsy_VHashTable *p)

successively visit each object

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 and a zero value until the iteration is restarted using vsy_VHashTableInitIter().

Parameters:

p – Pointer to VHashTable object.

void vsy_VHashTableNextIter(vsy_VHashTable *p, Vint key[], Vobject **value)

successively visit each object

See vsy_VHashTableInitIter()

Parameters:

  • p – Pointer to VHashTable object.

  • key – [out] Integer keys.

  • value – [out] Object associated with key

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

4.6.1. Function Descriptions

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

vsy_Tree *vsy_TreeBegin(void)

create an instance of a Tree object

Create an instance of a 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)

Returns:

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

void vsy_TreeEnd(vsy_Tree *p)

destroy an instance of a Tree object

See vsy_TreeBegin()

Vint vsy_TreeError(vsy_Tree *p)

return the current value of a Tree object error

See vsy_TreeBegin()

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

add a node to a parent node

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.

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.

Parameters:

  • p – Pointer to Tree object.

  • pkey – Integer parent node id

  • ckey – [out] Integer child node id

void vsy_TreeDelNode(vsy_Tree *p, Vint key)

delete a node and its children

Delete a node and all its children from the tree.

Errors

SYS_ERROR_OPERATION is generated if the node does not exist.

Parameters:

  • p – Pointer to Tree object.

  • key – Integer id of the node to be deleted along with its children.

void vsy_TreeFirstChild(vsy_Tree *p, Vint pkey, Vint *child)

sequential access to each item in the tree

See vsy_TreeForEach()

void vsy_TreeNextChild(vsy_Tree *p, Vint ckey, Vint *child)

sequential access to each item in the tree

See vsy_TreeForEach()

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

place an object in a node

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

Errors

SYS_ERROR_OPERATION is generated if the node does not exist.

Parameters:

  • p – Pointer to Tree object.

  • key – Integer id of node that will hold the object

  • value – Pointer to the object.

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

retrieves object from specified node

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.

Parameters:

  • p – Pointer to Tree object.

  • key – Integer id of node holding the object

  • value – [out] Object associated with key.

void vsy_TreeForEach(vsy_Tree *p, Vfunc1 *func)

process each item in the tree

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);
}

Parameters:

  • p – Pointer to Tree object.

  • func – Pointer to function which is to be applied to each object.