Memory Testing Issues – Resolved

After discovering a default Mint 13 system (kubuntu backports not used) containing Qt 4.8.1 did not exhibit the sporadic memory errors, some further investigation was done.  The errors also did not occur when Qt 4.8.2 was built from source.  Before blaming the Qt 4.8.2 from the kubuntu backports, the build directory was wiped and the application was rebuilt from scratch.  The sporadic memory errors were no longer occurring, so there must have been a corrupted file in the build directory causing the errors.

Some memory testing investigation was also done on Mint 17 (based on Ubuntu 14.04).  The conclusion previously was that valgrind 3.10.0.SVN reported errors differently than 3.7.0 (Mint 13) or 3.9.0 (built from the latest source available).  The source for 3.10.0 is now available and 3.10.0 built from source on Mint 13 did not report any additional memory errors.  The issue was found to be with the ld-2.19.so library on Mint 17 (Mint 13 has ld-2.15.so).  This library appears to contain low-level memory allocation functions.

A different error suppression file was needed for the newer version of this library.  The CMake build file was modified to detect the presence of ld-2.19.so (either 32-bit or 64-bit).  If present, then a different error suppression file is copied to the build directory.  This error suppression file generated on Mint 17 is independent of the version of Qt (the Qt libraries are not referenced), so no configuration of the file is needed.

The error suppression files generated for Qt 4.8.2 and 4.8.6 are also independent of the version of Qt, however, the one generated for Qt 4.8.4 is not.  To create a suppression file that works with all versions (at least the ones tested), the suppression file needs to be configured for the specific version of Qt.  The file generated from Qt 4.8.4 was used, and this file works with Qt 4.8.1, 4.8.2, and 4.8.6 once all references of "4.8.4" along with the installation directory of Qt are changed.

There are now two error suppression files, one for Mint 13 (ld-2.19.so not present) and one for Mint 17 (ld-2.19.so present).  The one for Mint 13 is configured for the version of Qt detected, but the one for Mint 17 is not.  Mint 17 has Qt 4.8.6, so no other version of Qt should be present.  This commit was put in the develop branch since it is not related to the STL changes.

[branch develop commit 2fb73b6892]

Tester – Standard Input Streams

The run function of the Tester class either read input from the console (standard input) or from the specified test file.  A QTextStream was used to read the input and was either opened to the standard input device or the test file.  The standard input stream does not work the same way in that an input stream is not opened with a device.  Fortunately the sections of code for reading from the console or a file was separate, so input can be read directly from standard input (std::cin) or from an input file stream (std::fstream).

Since reading from standard input or input file stream returns a standard string, the rest of the code in the tester class (the various functions for processing input) was modified to use standard strings.  However, where these functions interfaced to the various classes not yet converted to use standard strings, the string is converted to a C-style string that is acceptable for a QString argument (via implicit conversion).  This is temporary until those classes are modified.

[branch stl commit 2e57346eab]  (The memory bug has been resolved, see next post.)

Tester – Options List

The Tester class contains a static options function that returned a string list of supported testing options.  The constructor of the Command Line class obtained the testing options and added them to the options it supports (version and help) to generate the usage string with the program name.    The testing options in the list were joined with a vertical bar ('OR') separator character using the join function of QStringList.

There was no reason to join the options in this way to generate the usage string.  The options function was changed to simply return its part of the usage string (with the vertical bar characters between the testing options) as a std::string.  The Command Line constructor was modified accordingly.

[branch stl commit fc61d53041]  (The Qt 4.8.2 memory bug persists.)

Command Line – Standard Argument List

The Tester class still contains functions that have an argument or return value that is a QString or QStringList that need to be changed.  The first of these functions modified was the constructor that had a string list argument for the command line arguments.  These arguments come from the Command Line constructor, which in turn is passed from the Main Window constructor that obtains them from the  Qt application instance.

The Main Window constructor was modified to convert the QStringList arguments to a standard list of standard strings.  There are Qt functions for converting lists and strings to the standard equivalents, but there is no function for converting a string list.  A simple for each loop was added to iterate through the argument list and add (emplace back) to a standard list converting each element to a standard string.  This list is then passed (moved) to the command line constructor.

The Command Line constructor was modified to convert the first argument (the program path name) to a base file name and store it into the program name member (which was changed to a std::string).  This first element is removed from the list.  The rest of the constructor was modified to treat this list and a std::list with one less element.  The is version output and is help option functions were modified similarly.  The program name access function was removed since there were no callers.

The Tester constructor was modified to take the program name and argument list (less program path) as separate arguments.  The program name is used as the initializer of the program name member and the rest of the constructor was modified to treat this list and a std::list with one less element.

A minor bug was also discovered and corrected in the translate input function of the Tester class where the header argument was not being output when it was present.  The bug was recently added when the RPN list text function was changed to a standard put stream operator function.

[branch stl commit 3d3f0d3e5c]  (The Qt 4.8.2 memory bug persists.)

Tester – Removed Translation Calls

The rest of the translation tr() calls were removed from the Tester class, which allowed the Qt translation functions declaration macro to be removed.  A number of changes were made to the Command Line class to support these changes.

The copyright statement was put into a constant C-string with a Qt translate macro, which allowed for a delayed translate call.  This string contained QString style place holders for the program name (or version string for the GUI about box) and the copyright year.  There was a static access function to obtain this string, which the callers filled in as desired.

These were replaced with a static copyright statement function, which internally writes to the std::ostringstream and then returns the result as a std::string.  The program name or version string is no included as the caller is now responsible for this.  The copyright year function used to access the year was removed and the year is used directly since this was the only user.  The main window about box function was updated for this new function.

The warranty statements were put into an array of constant C-strings with Qt translate macros, which allowed for delayed translate calls.  There was a static access function to obtain this array.  This function was only called from the Tester class (the GUI has a different statement).  These were removed and the Tester class now outputs these strings directly without translation.

While making these changes, it was noticed that the copyright year set in the CMake build file had not been updated for 2014.  The application version numbers (major, minor and patch), copyright year and release string are transferred to the source code via a template input file from which CMake creates a header file.  This file contained C-style preprocessor defines, which are not type-safe, and were changed to type-safe C++11 constexpr statements.

[branch stl commit d399ff535f]  (The Qt 4.8.2 memory bug persists.)

Tester – String Members

The next items in the Tester class changed were the string members, the program name, test file name, and error message members, which were changed to std::stringg.  The access function for the error message member was also changed to return a std::string.  There were two considerations with these changes.

The first consideration was the issue of [language] translations, which were used with various strings for generating error messages.  I decided for the testing part of the code, that translations are not necessary.  The testing code is for testing the internals of the application and any output does not need to be internationalized.  Therefore, translations (calls to the tr() function returning QStrings) will be completely removed from the Tester class, which started with these error messages.

The second consideration was the QFileInfo class, which is used to extract the file name from a file name path.  There is no equivalent functionality in the standard library.  It is not appropriate to create a similar function when it already exists.  The Boost C++ library does have equivalent functionality, but there is no reason to add another dependent library when Qt is already present and provides the functionality.

Since the goal is to remove all Qt dependencies from the Tester class, a base file name static function was added to the Command Line class (which functions of the Tester class already call; and is the owner of the Tester class instance).  This function takes a std::string file path input and returns a std::string base file name using QFileInfo.  It is expected that the Command Line class will continue to use Qt since it interfaces with the main application.

[branch stl commit 986268caf7]  (The Qt 4.8.2 memory bug persists.)

Tester – Option Enumeration Class

The Tester class is next to transition from Qt to the STL.  When enumerations were changed to C++11 enumeration classes, the Option enumeration in the Tester class was excluded because it was used for a loop iterator and contained a number of enumerators used for various purposes.  These needed to be removed before changing this enumeration to an enumeration class.

The none enumerator used to indicate no option was removed.  The default Option enumerator, Option{}, will be used to indicate no option.  The first enumerator (parser) needed to be set to 1 for this to work (like done with other enumeration classes).

The size of enumerator was used to dimension an array of strings for the names of each of the options, which is used to compare the command line file name to select the appropriate test option.  The option enumerators were used as indexes to set the elements of this array.  This method is error-prone (elements could be missed), and enumeration class enumerators cannot be used as indexes.  This array was changed to a std::unordered_map with an initializer list for each of the options except for the recreator.  The size of enumerator was removed since it is not needed to initialized the map.

The first and number of enumerators were used to bound the loop through the names of the options to compare to the file name from the command line to set the appropriate option.  The number of enumerator did not include the recreator name (there are no recreator test files).  This loop was changed to range-for iterating over the items in the new name map (why the recreator name was not put into the name map).  The starts with Qt comparison call was changed to the standard equal function using a C++11 lambda to do a case insensitive comparison.

The option member was set to the error enumerator when an error was detected to indicate an error.  For each error, the error message string was also set.  The error enumerator was not needed since a non-empty error message string can be used to indicate an error, and was removed.  The has error access function was changed to check for a non-empty error message string.

The option member was defined as an integer so that it could be set to the loop iterator variable (an integer).  Since the option enumerator value is directly accessible in the range loop (the key in the iterator), the option member could be properly re-typed as an Option enumeration class variable.  The test name member was changed to a standard string (to match value in the name map) and the arguments to the is option function was changed to standard strings.

[branch stl commit 5c3a7d6141]  (The Qt 4.8.2 memory bug persists.)

Dictionary – Put Stream Operator

The Dictionary class has now been converted from using Qt to the STL, except for its debug text function.  This function was changed to a put stream operator in the tester source file.  Unlike the other two put functions, this put function was made a friend class so that it can access private members.  The function was modified to write to an output stream instead of into a string.

The writing of a header string was removed from the new put stream operator function since another argument can't be added.  This is not an issue since the caller can write these header strings.  The output of all the dictionaries was contained in a dictionaries debug text function in the Program Model class.  This function was only called once and was removed with the same functionality put into the run function of the Tester class where it was called from.

This concludes work on the Dictionary class.  The sporadic memory mentioned in the last post is still occurring (with Qt 4.8.2 only).

[branch stl commit 1cbe8e41ea]

Dictionary – Improved Case Handling

Three of the dictionary functions converted the key to look up to upper case if the dictionary is not case sensitive (four of the six dictionaries).  Also, essentially a duplicate of the key was stored in the key list vector and the key map, except that the key was converted to uppercase in the key map (excluding two of the six dictionaries) and so the key map could not be used to reproduce the string of the dictionary entry (hence the duplicate key list).

The std::unordered_map class by default uses the standard hash function to put keys with their value into buckets and the standard equal function for comparing keys already in a bucket (to determine if the key is already in the map).  By providing case insensitive hash and equal functions, unconverted strings can be stored for the keys.  The Key Map alias was modified to add key hash and equal structures:

using KeyMap = std::unordered_map<std::string, EntryValue, KeyHash, KeyEqual>;

Both of these private structures contain a case sensitive member.  The function operator function of the key hash checks this member, and if case insensitivity is not selected, the standard hash function is called.  Otherwise the key string is converted to upper case into a temporary string, which is then passed to the standard hash function:

struct KeyHash {
    CaseSensitive caseSensitive;
    size_t operator()(const std::string &s) const
    {
        if (caseSensitive != CaseSensitive::No) {
            return std::hash<std::string>{}(s);
        }
        std::string s2;
        std::transform(s.begin(), s.end(), std::back_inserter(s2), toupper);
        return std::hash<std::string>{}(s2);
    }
};

The key equal structure is setup similarly except the function operator function has two constant string references arguments (to compare) and returns a boolean value.  If case insensitivity is not selected, the strings are compared with the equality operator.  Otherwise the strings are not equal if their sizes are not equal.  For equal length strings, the characters of the strings are looped through converting each to upper case before comparing.  A mismatch indicates the strings are not equal.  If the end of the loop is reached, the strings are equal.

By default, std::unordered_map constructs defaults for the hash and equal structures.  Both of these structures do not initialize the case sensitive member.  Instances of these structures can be given to the map during initialization, which is done in the constructor (the 10 is the number of hash buckets, which is the default if not specified):

Dictionary(CaseSensitive caseSensitive = CaseSensitive::No) :
    m_keyMap {10, KeyHash {caseSensitive}, KeyEqual {caseSensitive}} {}

The key list vector was removed.  However, a way to look up dictionary entry keys by index was still required, so a vector of iterators was added in its place.  Each iterator points to a key/value pair in the key map.  When a new entry is added, its iterator is put into this vector.  When an entry is removed, the end iterator of the key map (points to one past the end) is put into this vector.

In the add function, the map emplace functions return the iterator of the key/value inserted.  This iterator is put into the iterator vector.  The remove function no longer needs to find the iterator for the index, which is now obtained from the iterator vector.  After removing the key/value, the iterator for the index is set to the key map end iterator.  The debug text function also no longer needs to find the iterator for the index, and it checks if the iterator for the index is the end iterator to determine if there is no entry for the index (instead of a blank key).

For some reason, there is a sporadic memory error occurring when memory testing with these changes.  It is another error from Qt, but it doesn't occur with the same tests each time.  It is also only occurring with Qt 4.8.2, and not with Qt 4.8.4 or Qt 4.8.6.  For now, this problem will be monitored.

[branch stl commit 1f2483e82c]

Dictionary – Entry Use Counts

Mentioned in the last post, the use count vector member was removed and a use count was put into the value of the map.  A new private Entry Value structure was created to hold the index and the use count of the entry.  Both were defined as unsigned 16-bit integers.  A constructor was added taking a single index argument and the use count is initialized to 1.

For the add function, the entry in the use count vector no longer needs to be added or initialized (in the case of a reused entry).  Instead of assigning a key to an index using the bracket operator, the map emplace function is used with a single index.  The use count get set to 1 whether it is a new or a reused entry by the constructor of the Entry Value structure.  For an existing entry, the iterator is used to increment the use count.

For the remove function, since the use count is no longer available by index, the index is used to get the key from the key list member.  The key is converted to upper case for case insensitive dictionaries and used to find an iterator for the key.  While the index is available in the iterator, it is used to clear the entry in the key list and pushed to the free stack.  The iterator is used to erase the entry from the key map (entries can be erased either by key value or iterator).

For the debug text function, since the use count is no longer available by index, a non-empty entry in the key list is used to identify if an entry is used.  The key is used to find an iterator to the entry.  An error check was added if the key was not found (shouldn't happen).  The iterator is used to get the use count.  When outputting the indexes of the free stack, the check for a non-zero use count was removed since the use count is no longer available (the entry in the map with the use count was erased, and an entry is not pushed to the free stack unless the use count was zero).

[branch stl commit e79c179ad5]

Dictionary – Case Sensitive Member

The next changes for the Dictionary class are some improvements in its implementation.  One of these changes is to integrate the use count into the value of the key map instead of using a separate vector for the use counts of each entry.  Putting the use count into the key map value will require the use of iterators to get to the use count since they will no longer be in an indexed vector.

The debug text function (which will be changed to a put stream operator function) will need to use an iterator to look up a key to get the use count.  When using iterators, the debug text function will also need to convert the key to upper case for case sensitive dictionaries, which implies that it would also need a case sensitive flag argument like the add and remove function.

This made me realize that passing a case sensitive flag to all of these functions was not the best design.  A better design is to have a case sensitive flag as a member variable initialized once when the dictionary is constructed.  Using arguments allows different case sensitivities on a dictionary and this will cause problems.  A case sensitive member was added, the constructors were added or modified, and the case sensitive arguments were removed.

[branch stl commit b78217c5a4]

Dictionary – Key Map

The remaining member of the Dictionary class to change to a standard class is the key hash, which was defined as a QHash.  This class is equivalent to the std::unordered_map, which also stores keys using a hash.  The member was renamed to key map and a Key Map alias was added since the the map type is rather lengthy:

using KeyMap = std::unordered_map<std::string, int>;

The add routine, was changed to use the key as a standard string.  The standard string class does not have a member function for converting the string to upper case.  For case insensitive dictionaries, the string is converted to upper case using the standard transform function:

std::transform(key.begin(), key.end(), key.begin(), toupper);

The first two arguments specify the range of the string to transform (the entire string).  The third argument specifies the destination (back into the string).  The last argument is function that takes and returns a character.  To find a key value in the map, the map find function is used, which returns an iterator.  A key not found is detected if the iterator is the end iterator of the map.  The value in the map (the index of the entry) is obtained using the iterator:

auto iterator = m_keyMap.find(key);
if (iterator == m_keyMap.end())  // key not found?
...
index = iterator->index;

Similar changes were made in the remove function for converting the key to upper case for case insensitive dictionaries.  The map erase function is used to remove a key from the map.

[branch stl commit 66561d4532]

Dictionary – Start STL Transition

The Dictionary class will be next to have its debug text function changed to a put stream operator function.  Unlike the RPN List and Token classes, access to some of private variables will be necessary, so the put stream operator function will need to be a friend function.  First, these private variables needs to be changed from Qt classes to STL classes.  Other dependencies on Qt will also be removed.  This was started with these changes:

• Changed the quint16 type to the standard uint16_t type.
• Changed the use count list member to a standard vector.
• Changed the free stack member to a standard stack.
• Replaced the use of the Q_UNUSED macro to just (void), which is just as simple.
• Replaced the use of Qt case sensitivity enumerators with a simple yes/no case sensitive enumeration class.  The enumerators were never passed to Qt functions, so there was really no reason to use the Qt enumerators.

The next change was to change the QStringList for the list of keys with a standard vector or standard strings.  The string access function was changed to return a standard string, which required the change of the return value of the various operator text functions accessing dictionaries to a standard string.  Several conversions from and to QString values were temporarily added as needed until more variables are changed to standard strings (though some will be needed when interfacing to the GUI).

[branch stl commit 84875530db]

Token – Put Stream Operator

The Token class was next to have its text function changed to a put stream operator function.  Again, it was not necessary to make the new function a friend of the Token class since there are sufficient access functions.  The put stream operator function for the RPN List class was changed to use the new token put stream operator.

[branch stl commit 2b5c581d31]

RPN List – Put Stream Operator

There are a number of member functions in various classes that create text from an instance for outputting while running tests.  A better implementation of this is to overload the put stream operator (<<).  The RPN List class was the first class changed.  An RPN list instance is now output like this:

std::cout << rpnList;

The text member function was moved from the RPN List class source file to the Tester class source file (the only current caller) and renamed to the put operator (operator<<).  The return value and first argument was changed to an output stream reference.  A second argument was added for a constant reference to the RPN list instance.  Normally these put stream operator function are made friend functions of the class so that private members can be accessed, but the RPN List class already provides the necessary access functions.

A few changes made to the new.  The output stream argument is used to output to instead of the local string stream variable, which was removed.  The local index variable (used to create an RPN item pointer to index map) is used to detect the first item in the list instead of the number of characters written to the output stream.  And the output stream argument is returned instead of the contents of the local string stream.

If there is a future need for this operator beyond the Tester class, the function can be moved and a function prototype provided in a header file.  If this future need is for a string, the string can be obtained by using an output string stream and getting its string:

std::ostringstream oss;
oss << rpnList;
std::string string = oss.str();

[branch stl commit 365d20b2b]

Tester – Standard Output Stream

The non-GUI classes use many strings that will be changed from QString to std::string.  In the Tester class, these strings are output using Qt text output streams.  The next step in the STL transition was to change the Tester class to use std::ostream instead of QTextStream.  This also required changes to the Command Line class, which provides the tester instance with the output stream to use for output.

The text stream member of the Command Line class (where either stdout or stderr was opened) was changed to a pointer to an std::ostream (which is now set to a pointer to either std::cout or std::cerr).  The cout() member function was changed to return a reference to the output stream and allowing the output stream member to be set from is argument (defaulting to std::cout).  Since nothing is opened, nothing needs to be closed so the coutClose() member function and destructor was removed.

Where ever a QString is output to the output stream, the toStdString() function was added since QString is not supported by std::ostream.  This is temporary until most of the QString instances are changed to std::string.  The usage string member was changed to a local std::string since no other code used it and it's access function was removed.

The text stream member of the Tester class was changed to an output stream reference.  The toStdString() was added to QString instances (temporary).  All uses of endl were changed to the new line character ('\n').  The endl manipulator (both Qt and STL) not only outputs the new line character, it also flushes the stream and this flush was not needed.

[branch stl commit 5cc2438dd0]