Home > Developer > Heap and String Class

SophiaFramework : BREW  C++ Class Library & GUI Framework & XML Middleware

Heap and String Class

Preface

Implement a Heap class that dynamically allocates heap memory, then develop a String class using that Heap class.

Download source code here.

Heap Class

The Heap class dynamically manages heap memory. A chunk of heap memory, reserved in the block will be automatically released when exiting the block.

Implement the Heap Class ( BPPHeap )

The variables in BPPHeap are "m_heap", which is a pointer to actual heap and "m_size", the current heap size.

The function Resize() modifies the heap size ( See list 1 ).

If "0" is specified as the heap size, then the heap memory will be released.

The return value of the REALLOC() function ( realloc() in C) is assigned to a temporary variable (temp), and is only assigned to the member variable m_heap once temp has been tested.

* List 1 Resize() function to modify the heap size
boolean BPPHeap::Resize(unsigned int size)
{
    void* temp;
    if (m_heap == NULL) { // New assignment
        m_heap = MALLOC(size);
        if (m_heap == NULL) {
            return FALSE;
        }
    }
    else { // Modify size
        if (m_size != size) {
            if (size == 0) // Release when size is 0
                Free();
            else {
                temp = REALLOC(m_heap, size); // IMPORTANT!
                if (temp == NULL)	// Testing temp
                    return FALSE;
                m_heap = temp;
                m_size = size;
            }
        }
    }
    return TRUE;
}

List 2 presents the Free() member function that releases the heap.

* List 2 : Free() member function to release heap
void BPPHeap::Free()
{
    if (m_heap != NULL) { 
        FREE(m_heap);	//If argument is NULL
        m_heap = NULL;	//FREE does nothing
    }
    m_size = 0;
    return;
}

When the function foo() ends, heap will be automatically released.

void foo(){
    BPPHeap myheap;
    myheap.Resize(1000);// Process using heap
    // Heap will not be released explicitly
}

The function Free() must be invoked in the destructor of List 3.

* List 3 : Destructor
BPPHeap::~BPPHeap()
{
    Free();
    return;
}

String Class

String Operators

In C, when combining s1 and s2 to generate s3, coding must be done as follows:

strcpy(s3, s1);
strcat(s3, s2);

But it would be easier to write s3 = s1 + s2;

When comparing the contents of s1 and s2,

if (!strcmp(s1, s2)) {
    /* when s1 = s2 ... */
    ...
}

It would be simpler to write it as:

if (s1 == s2) {
    // when s1 = s2 ...
    ...
}

Operator and Member Function

Inserting s2 after the third character of s1, cannot be accomplished with the "=" and "+" operators.
The Copy() function shown in list 4 is required.

* List 4 : Copy() member function
boolean BPPString::Copy(unsigned int index, const BPPString &string);
boolean BPPString::Copy(unsigned int index, const AChar* string, 
                        int length = -1);

index is used in the following C statement.

strcpy(s1 + index, s2);

Overloading is implemented for constant string arguments.

Copy(0, "abracadabra")

"length" is the number of characters to be copied, and if length = -1 is assigned, the whole string is copied. A Compare() function whith the same function as strcmp() in C, is also built.

Return Type of Copy()

Notice that the return value of Copy() is of boolean type ?

When the string to be copied is larger than the target heap area, the heap needs to be extended. But since this process will not always succeed, the return value of Copy() needs to be checked.

Dilemma in conversion to AChar*

Many BREW interfaces take pointers as arguments. By wrapping up BREW APIs, the use of pointers can be avoided. A GetBuffer() function is implemented to return heap as type AChar*

It may seem like an operator to cast values of string class to type AChar* would be useful.

That operator could be used to format file names of the string class, which could then be thrown to the IFILEMGR_OpenFile() function ( BREW API for loading file).
But some BREW APIs have "pointer to pointer" arguments, and store the result via these arguments. For example, pchOut, the 4th parameter of the IRSA_RSA() function which encodes/decodes RSAs is of byte ** type.

The designer of this string class will know to cast this argument as an Achar* type array that will be processed by the function, and then cast back as a string class object. But any other programmer will not know that this is argument is actually a string, and might mistake it as a regular Achar* type.

It would be safer to use the GetBuffer() function to receive the argument of string class and return it as type Achar*.

Error Handling in the Operator

In standard C++, if there is an error with the Concat() function, the error type can be known by checking the return value. Or when the "+" operator is used to combine strings, errors can be caught using exception handling. But these options are not available in BREW.

Building custom C++ style exception handling on BREW would be a lot of work. The simplest solution is to store the error inside the class and check it from outside the class.

    string3 = string1 + string2;
    if (string3.GetError()) {
        // What to do when error occur
        ...
    }

When using an object which has inccurred an error:

    string1 = "PI = ";
    // Failed to allocate heap
    string2 = "3.1415926535897932384626433832795028841971...";
    string3 = string1 + string2;

Should string3 be considered as error free?

Consider the next example.

BPPString foo(int x, int y)
{
    BPPString ret;
    ...  // Process to modify ret
         // Failed to reserve heap
    return ret;
}

    // code in another function
    BPPString result = foo(100, 200);

The function foo() does some calculations with the given arguments, then returns a result of type BPPString. When "return ret" is called, a copy of "ret" is generated, and the contents of this copied ret are assigned to "result".

If error information is not inherited, the validity of "result" can not be verified. To insure the integrety of the entire code, the Copy() function must inherit error information.

If Copy() does inherit error information, then it can determined that string3 is not error free.

Implement String Class

Member Variable

Member variables should be private.

Heap is required to handle strings. Since it takes time to re-assign heap, reducing heap size should be avoided.

Therefore, a variable to save string length and a variable to save error information are required.

BPPHeap m_string; // Heap
unsigned int m_length; // Length of current string
boolean m_error; // For saving error information

Changing Heap Size

SetHeapSize() is the function which modifies heap size. Its implementation is such that modifying heap size is avoided as much as possible. ( See list 5 )

* List 5 : Changing heap size
boolean BPPString::SetHeapSize(unsigned int size)
{
    boolean ret = TRUE;
    // Resize only when enlarging the heap size
    if (m_string.GetSize() < size) {
        ret = m_string.Resize(size);
        // Always check error
        if (!ret)
            m_error = TRUE;
    }
    return ret;
}

Copying Strings

The Copy() function is the most important function in the string class. It is necessary when creating a new string object, copying strings objects with the assignment operator and concatenating string objects.

List 6 implement's the Copy() function.

*List 6 : AChar* is an argument
boolean BPPString::Copy(unsigned int index, 
                        const AChar* string, int length)
{
    // To avoid error, when string is empty, length is 0
    if (!string)
        length = 0;

    // Calculate the length of the string
    if (length < 0)
        length = STRLEN(string);

    unsigned int newlength = index + length;
    if (!SetHeapSize(newlength + 1))
        return FALSE;
    MEMCPY((AChar*)m_string.GetHeap() + index, string, length);

    // Always add NULL character at the end of the string
    *((AChar*)m_string.GetHeap() + (m_length = newlength)) = '\0';
    return TRUE;
}

Default value for length is -1.

List 7 implements the Copy() function which will take BPPString as argument.

*List 7 : BPPString is an argument
boolean BPPString::Copy(unsigned int index, const BPPString &string)
{
    if (!string.m_error)
        m_error = string.m_error;
    return Copy(index, (const AChar*)string.m_string.GetHeap(), 
                        string.m_length);
}

This function calls the Copy() function of List 6, and uses it on an BPPString object. The thrown object's error information should always be inherited.

Inline function or not ?

List 7 will not be defined as an inline function.

If the function is invoked, the actual argument is saved on the stack. But the size of the stack on a mobile handset is very limited.

When there is a great number of functions, defining them as inline should be considered.

Array operator

Array operators can easily access characters through their index. But when an incorrect index is assigned, an invalid area may be accessed.

The AEE_SIMULATOR macro is available in BREW SDK. It creates two sets of application code, one for the emulator and one for the actual handset.

For example, checking array indexes degrades application performance and should only be done on the emulator.