Saturday, January 30, 2010

New List Class – Release

The test_stack program was modified to include a new test_list() function that tests all the new list functions. The existing stack test functions test to make sure all the existing stack functions are still working correctly. The print_stack functions were renamed to print_list along with the arguments since these functions are really printing the underlying list. (Besides, it didn't make sense calling print_stack() from the test_list() function.) The ibcp_0.0.3-src.zip file has been uploaded at Sourceforge IBCP Project. The binaries for the test programs have now also been uploaded so compilation is not necessary.

One last minor fix was needed to the List class in the destructor. Upon scanning through the ANSI-ISO_C++.pdf document, I learned there is a distinction between using new to allocate a single item and new[] to allocate an array. You must use the corresponding delete and delete[] to deallocate the memory. For the List class, "new Element" is used throughout so there are no issues with that. However, the master element is allocated using new[]:

    master = (Element *)new char[sizeof(Element) – sizeof(T)];

This is used because the master element only contains previous and next element pointers, but no value. The statement above subtracts the size of the value (template generic type T) from the size of the element. Since delete[] needs to be used with new[], in the destructor, the delete master statement was changed to:

    delete[] (char *)master;

This gives delete[] the character pointer originally obtained from the new char[...] statement before is was type cast to an Element pointer.

Now it is time to get back to the Parser implementation.

New List Class – Implementation

A problem occurred during the update of the list class. It was desired that the append, insert and remove functions to not be inline functions. Defining them in the class automatically makes them inline. Therefore, they were defined outside the main List class. They are still in the list.h include file, but because they are template functions, no code is generated until a class is instantiated and the function is used.

The problem occurred for the functions that return an element pointer. The List class contains the public Element structure (next and previous element pointers and the generic value of type T). The Element structure needs to be defined within the List class since it contains the type T of the template. Inside the class definition, the Element structure can be simply referred to as “Element” or “Element *” for pointers. Outside the function, the syntax “List<type>::Element” and “List<type>::Element *” is needed where “type” is the instantiated type. For defining template functions “List<T>::Element” and “List<T>::Element *” are used.

Therefore, to define a template function that returns and Element pointer and takes an Element pointer as an argument would appear that it should be written as:

    template <class T> List<T>::Element *List<T>::fun(List<T>::Element *element)

Unfortunately, the compiler gave the error: error: expected constructor, destructor, or type conversion before '*' token. The problem was with the return value since the argument syntax was in the List class previously causing no issues.

List Class – Updated

The List class needs to be updated to include more list like functions. The first implementation was really oriented towards the support of stack like functions (i.e. push and pop). For a list, elements need to be added to any position in the list, not just the end. This will be needed for the Translator as the RPN list is built. The following operations are therefore needed:
  • Add a value to a new element after an element (append)
  • Add a value to a new element before an element (insert)
  • Get a value and remove it's element (remove)
Several other changes will be made to the list class.