0

I have run this code before editing a function(unionSet), once I ran the program after editing this error showed. I am working in C++ on XCode, and I have yet to see this before.

malloc: * error for object 0x100519860: pointer being freed was not allocated * set a breakpoint in malloc_error_break to debug

#include "Set.hpp"
#include <string>
#include <sstream>
#include <cassert>

using namespace std;

// Function for the default constructor.
Set::Set()
{
    // default constructor
    theSet = new int[0];
};

// Function for the overloaded constructor taking an element and building an array for it.
Set::Set(int element)
{
    // take element
    // make one memory box
    // put element in that single box

    numElements = 1;
    theSet = new int[numElements];
    for(int i = 0; i < numElements; i++)
    theSet[i] = element;
};

// Function for the destructor.
Set::~Set()
{
    // deletes the dynamic array
    if (theSet != nullptr)
    {
        delete [] theSet;
        // removes the posibility of a dangling pointer
        theSet = nullptr;
    }
};

// Function building the copy constructor.
Set::Set(const Set& copy)
{
    // sets the value of copy constructor size equal to the current size by reference
    numElements = copy.numElements;

    // Allocate the memory.
    theSet = new int[numElements];

    // Copy all the data over.
    for (int i = 0; i < numElements; i++)
        theSet[i] = copy.theSet[i];
};

// Function for finding the elements in the intersection of set A and set B.
void Set::intersectSet(const Set& otherSet)
{
    // only the elements in both sets

    int *newSet = new int[otherSet.getCardinality()];
    int x = 0;

    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++){
            if (theSet[i] < otherSet.theSet[j])
            {
                i++;
            }

            else if (otherSet.theSet[j]< theSet[i])
            {
                j++;
            }

            else if (theSet[i] == otherSet.theSet[j])
            {
                theSet[i] = newSet[x];
                i++;
                j++;
                x++;
            }
            theSet = newSet;
        }
    }
};

// Function for finding the elements in the union of set A and set B.
void Set::unionSet(const Set& otherSet)
{
    // combine the two sets but no repeats

    theSet = otherSet.theSet;

}

// Function for retreiving the difference between set A and set B.
void Set::setDifference(const Set& otherSet)
{
    // the compliment of a set
    // an array with values from array A and only array A(cannot be in B)

    int *newSet = new int[otherSet.getCardinality()];
    int x = 0;

    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++){
            if (theSet[i] < otherSet.theSet[j])
            {
                i++;
                theSet[i] = newSet[x];
                x++;
            }

            else if (otherSet.theSet[j] < theSet[i])
            {
                j++;
            }

            else if (theSet[i] == otherSet.theSet[j])
            {
                i++;
                j++;
            }
            theSet = newSet;
        }
    }
};

// Function for checking if the "otherSet" is a subset of "theSet".
bool Set::isSubset(const Set& otherSet) const
{
    // all elements of a must be in set b to be a subset
    int i = 0, j = 0;
    for ( i = 0; i < numElements; i++)
    {
        for ( j = 0; j < numElements; j++)
        {
            if ( theSet[i] == theSet[j] )
                break;
        }

        if ( j == numElements)
            return false;
            // returns false if variable j is equal to the number of elements
    }
    return true;
    // return true if the statement is not changed
};

// Function for checking if the set is empty.
bool Set::isEmptySet() const
{
    // empty set = no memory
    if (theSet != nullptr)
        return false;
        // returns true if the set is empty
    return true;
        // returns false if the set is not empty
};

// Function for checking if an element is a member of the set.
bool Set::isMember(int element) const
{
    // check function looking for the element in the set
    for (int i = 0; i < numElements; ++i)
    {
        if (theSet[i] == element) return true;
        // returning true if the element is found
    }
    return false;
    // return false if element is not found
};

// Function for retreiving the number of elements in the set.
int Set::getCardinality() const
{
    // returns the size of the set over the first position
    return (sizeof(theSet)/sizeof(*theSet));
};

string Set::toString()
{
    // Builds the stream for output
    stringstream stream;

    // Opening stream statements when called
    stream << "{ ";

    // For loop for outputing the contents of set
    for (int i = 0; i < numElements; i++)
        stream << theSet[i] << ", ";
    // Closing stream statements
    stream << "}";

    // Returns the whole statement to the output location.
    return stream.str();
};

This code is definitely a work in progress but I cannot move forward without figuring out why the error occurs.

Test file looks as below:

#include <iostream>
#include "Set.hpp"
#include <string>

using namespace std;

// This function takes a method call as a string, a boolean value returned
// by a call and the expected boolean value and pretty prints the result.
void boolExpected(string method, bool val, bool expected)
{
    if (expected)
        cout << method << " = " << val << " expected true (1) ";
    else
        cout << method << " = " << val << " expected false (0) ";

    if (expected == val)
        cout << " [ PASS ]\n";
    else
        cout << " [ FAIL ]\n";
}

// This function takes a method call as a string, an integer value returned
// by a call and the expected integer value and pretty prints the result.
void intExpected(string method, int val, int expected)
{
    cout << method << " = " << val << " expected " << expected;
    if (expected == val)
        cout << " [ PASS ]\n";
    else
        cout << " [ FAIL ]\n";
}

// This function takes a method call as a string, an integer value returned
// by a call and the expected integer value and pretty prints the result.
void stringExpected(string method, string val, string expected)
{
    cout << method << " = " << val << " expected " << expected;
    if (expected == val)
        cout << " [ PASS ]\n";
    else
        cout << " [ FAIL ]\n";
}

// Tests the isEmptySet() method.
void testIsEmptySet()
{
    Set mySet;
    Set mySet2(3);

    // added to see contents of array
    cout << " mySet contains " << mySet.toString() << ". " << endl;
    cout << " mySet2 contains " << mySet2.toString() << ". " << endl;

    boolExpected("mySet.isEmptySet()", mySet.isEmptySet(), true);
    boolExpected("mySet2.isEmptySet()", mySet2.isEmptySet(), false);
}

// Tests the isMember() method.
void testIsMember()
{
    Set mySet;
    Set* tmp;

    // Build up a set.
    Set mySet2(3);

    tmp = new Set(4);
    mySet2.unionSet(*tmp);
    delete tmp;

    tmp = new Set(7);
    mySet2.unionSet(*tmp);
    delete tmp;

    // added to see what contents of array are
    cout << " mySet contains " << mySet.toString() << ". " << endl;
    cout << " mySet2 contains " << mySet2.toString() << ". " << endl;

    boolExpected("mySet.isMember(5)", mySet.isMember(5), false);
    boolExpected("mySet.isMember(7)", mySet.isMember(7), false);
    boolExpected("mySet2.isMember(7)", mySet2.isMember(7), true);
    boolExpected("mySet2.isMember(4)", mySet2.isMember(4), true);
    boolExpected("mySet2.isMember(3)", mySet2.isMember(3), true);
    boolExpected("mySet2.isMember(15)", mySet2.isMember(15), false);
}

// Tests the isSubset method.
void testIsSubset()
{
    Set mySet(7);
    Set* tmp;

    // Build up a set.
    Set mySet2(3);

    tmp = new Set(4);
    mySet2.unionSet(*tmp);
    delete tmp;

    tmp = new Set(7);
    mySet2.unionSet(*tmp);
    delete tmp;

    // added to see what contents of array are
    cout << " mySet contains " << mySet.toString() << ". " << endl;
    cout << " mySet2 contains " << mySet2.toString() << ". " << endl;

    boolExpected("mySet.isSubset(mySet2)", mySet.isSubset(mySet2), true);
    boolExpected("mySet2.isSubset(mySet)", mySet2.isSubset(mySet), false);
}

// Tests the getCardinality method.
void testGetCardinality()
{
    Set emptySet;
    Set mySet(7);
    Set* tmp;

    // Build up a set.
    Set mySet2(3);

    tmp = new Set(4);
    mySet2.unionSet(*tmp);
    delete tmp;

    tmp = new Set(7);
    mySet2.unionSet(*tmp);
    delete tmp;

    // added to see what contents of array are
    cout << " mySet contains " << mySet.toString() << ". " << endl;
    cout << " mySet2 contains " << mySet2.toString() << ". " << endl;

    intExpected("mySet.getCardinality()", mySet.getCardinality(), 1);
    intExpected("mySet2.getCardinality()", mySet2.getCardinality(), 3);
    intExpected("emptySet.getCardinality()", emptySet.getCardinality(), 0);
}

// Tests the unionSet method.
void testUnionSet()
{
    Set emptySet;
    Set mySet(7);
    Set* tmp;

    // Build up a set.
    Set mySet2(3);

    tmp = new Set(4);
    mySet2.unionSet(*tmp);
    delete tmp;

    stringExpected("{ 3 } union { 4 } ", mySet2.toString(), "{ 3, 4 }");

    tmp = new Set(7);
    mySet2.unionSet(*tmp);
    delete tmp;

    stringExpected("{ 3, 4 } union { 7 } ", mySet2.toString(), "{ 3, 4, 7 }");

    emptySet.unionSet(mySet);
    stringExpected("{ } union { 7 }", emptySet.toString(), "{ 7 }");
}

// This tests the intersectSet() method.
void testIntersectSet()
{
    Set emptySet;
    Set mySet(7);
    Set* tmp;

    // Build up a set.
    Set mySet2(3);

    tmp = new Set(4);
    mySet2.unionSet(*tmp);
    delete tmp;

    tmp = new Set(7);
    mySet2.unionSet(*tmp);
    delete tmp;

    emptySet.intersectSet(mySet);
    stringExpected("{ } intersect { 7 }", emptySet.toString(), "{ }");

    mySet.intersectSet(mySet2);
    stringExpected("{ 7 } intersect { 3, 4, 7 }", mySet.toString(), "{ 7 }");

    mySet2.intersectSet(mySet);
    stringExpected("{ 3, 4, 7 } intersect { 7 }", mySet2.toString(), "{ 7 }");
}

// This tests the setDifference method.
void testSetDifference()
{
    Set mySet(7);
    Set* tmp;

    // Build up a set.
    Set mySet2(3);

    tmp = new Set(4);
    mySet2.unionSet(*tmp);
    delete tmp;

    tmp = new Set(7);
    mySet2.unionSet(*tmp);
    delete tmp;

    mySet.setDifference(mySet2);
    stringExpected("{ 7 } difference { 3, 4, 7 }", mySet.toString(), "{ }");

    Set mySet3(7);

    mySet2.setDifference(mySet3);
    stringExpected("{ 3, 4, 7 } difference { 7 }", mySet2.toString(), "{ 3, 4 }");
}

int main()
{
    cout << "Testing isEmptySet()\n";
    cout << "--------------------\n";
    testIsEmptySet();
    cout << endl << endl;

    cout << "Testing isMember()\n";
    cout << "------------------\n";
    testIsMember();
    cout << endl << endl;

    cout << "Testing isSubset()\n";
    cout << "------------------\n";
    testIsSubset();
    cout << endl << endl;

    cout << "Testing getCardinality()\n";
    cout << "------------------------\n";
    testGetCardinality();
    cout << endl << endl;

    cout << "Testing unionSet()\n";
    cout << "------------------\n";
    testUnionSet();
    cout << endl << endl;

    cout << "Testing intersectSet()\n";
    cout << "----------------------\n";
    testIntersectSet();
    cout << endl << endl;


    cout << "Testing setDifference()\n";
    cout << "-----------------------\n";
    testSetDifference();
    cout << endl << endl;


    return 0;
}

Output is shown in the terminal as:

>Testing isEmptySet()
>--------------------
> mySet contains { }. 
> mySet2 contains { 3, }. 
>mySet.isEmptySet() = 0 expected true (1)  [ FAIL ]
>mySet2.isEmptySet() = 0 expected false (0)  [ PASS ]
>
>
>Testing isMember()
>------------------
> mySet contains { }. 
> mySet2 contains { 0, }. 
>mySet.isMember(5) = 0 expected false (0)  [ PASS ]
>mySet.isMember(7) = 0 expected false (0)  [ PASS ]
>mySet2.isMember(7) = 0 expected true (1)  [ FAIL ]
>mySet2.isMember(4) = 0 expected true (1)  [ FAIL ]
>mySet2.isMember(3) = 0 expected true (1)  [ FAIL ]
>mySet2.isMember(15) = 0 expected false (0)  [ PASS ]
>Set(13123,0x1003a8380) malloc: *** error for object 0x100519860: pointer being freed was not allocated
>*** set a breakpoint in malloc_error_break to debug

Any help is greatly appreciated.

ed1298
  • 11
  • 2
    You are missing the user-defined assignment operator for `Set`, i.e. `Set& operator=(const Set&);`. You should read about the [rule of 3](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three). But why not simply use `std::vector` and not have to worry about having to provide user-defined copy operations? – PaulMcKenzie Feb 13 '19 at 01:01
  • Side note: After the destructor the object is gone, so there is no chance of a dangling pointer without first abusing another dangling pointer to the `Set` itself. – user4581301 Feb 13 '19 at 01:02
  • Side note: `Set::intersectSet` doesn't seem to `delete[] theSet;` before leaking it with `theSet = newSet;`. – user4581301 Feb 13 '19 at 01:03
  • Your test cases are missing the obvious simple scenario: `Set set1(10); Set set2(10); set2 = set1;` -- You will then see why the assignment operator is important. – PaulMcKenzie Feb 13 '19 at 01:07
  • I stopped counting after observing four obvious bugs in the shown code. One memory leak. Three different bugs that will result in memory corruption. There's probably more. This is likely the end result of trying to write the entire program at once, and then attempting to debug the whole thing altogether. This is not the most efficient approach. You're better off starting from the beginning, and writing only a few lines of code, and then not writing the next few lines until after fully testing and verifying that the first chunk of code works correctly. – Sam Varshavchik Feb 13 '19 at 02:00
  • Your code is not a [mcve] as it is far from minimal. Everything after the call to `isMember` is not needed, nor are the functions those tests call. – 1201ProgramAlarm Feb 13 '19 at 02:00
  • So, did you set a breakpoint in malloc_error_break to debug? – Jeremy Friesner Feb 13 '19 at 03:26

1 Answers1

0

Your immediate problem is caused by unionSet. It doesn't do a union operation, and you're copying a pointer that will be deleted by the caller. That freed memory might be reused before getting deleted a second time.

You need to properly implement your set union operation.

To avoid future problems, you need to implement the assignment operator for Set as well.

1201ProgramAlarm
  • 32,384
  • 7
  • 42
  • 56