MESSAGE
| DATE | 2011-04-05 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [NYLXS - HANGOUT] Re: double deletes C++ Workshop
|
I essentially debugged this situation and worked around the double
delete.
Once i rolled up my sleeves, then what I understood as the principles
behind the destructors was confirmed to be correct. The issues layed in
my destructor. The destructor was fine at removing all the nodes. What
it failed to do was keep the List object up to date to its state.
Essentially, the biggest bug that I had was that as I was deleting
nodes, I failed to update the List's front_ and end_ data. They bother
had to be returned to NULL at the end so that when the destructor is
called again, if need be from a local copy of the List object, that it's
front() returns a null. Checking to make sure the Node was already
valid, which is what I was trying to do, is useless because when a Node
is deleted, that doesn't mean the pointer to that Node is NULL. It
still points to the Heap location which is being shared, only you have
garbage.
I also failed, FWIW, to do a return when font is NULL, causing the
destructor to continue down and do more intructions, similar to a case
without a break.
The degugger was less useful at helping solve this then I thought it
should be. There were other mimor issues with the find_next_value as
well. It is still very sloppy. It was sloppy in the first example as
well. I just know there has to be an easier way to do what I'm
attempting to do. The language looks like a big patch...
template < class T >
Node& List::find_next_value (const T& value, Node& last_node_searched)
{
cursor(&last_node_searched);
if(cursor() == endd()){
cursor() = 0;
return *cursor();
}
cursor() = cursor()->next();
while(value != *(cursor()->value()) ){
if(cursor() == endd()){
if( *(endd()->value()) == value){
return *(endd());
}else{
cursor() = 0;
return *cursor();//is this a problem. Does setting the Node *
//to zero return a zero address on all platforms?
}
}
cursor() = cursor()->next();
}
return *cursor();
} /* ----- end of method List::find_next_value ----- */
I am trying to avoid shifting the cursor past the end and becoming a
NULL pointer and then testing on that because you were critical of that
technique. The result was that I accidently tested for values that
didn't exist instead. I fixed it by checking if the sent Node is the
end Node right at the start of the function before I shift to the next
node.
I'm probably boring you to death with all this easy crap. Sorry about
it.
I'm going to change the find_next_node to returning pointers to Node
instread of Nodes, just to keep the API consistant, if for no other
reason.
BTW - one interesting thing to not
This Allorithm
srand(12345);
int i,j;
chainlist::List outside = creating_int_list();
chainlist::List a[10];
for( i=0; i < 10; ++i){
std::cout << "CREATING LIST for ARRAY -------------------------------\n";
a[i] = creating_int_list();
}
for( i=0; i < 10; ++i){
std::cout << "NEW SEARCH -------------------------------\n";
for(j=0;j < 10; j++){
find_all_examples(a[i], j);
}
}
for( i=0; i < 10; ++i){
std::cout << "Removing Nodes -------------------------------\n";
a[i].remove_all();
}
chainlist::List &creating_int_list(){
// chainlist::List set = new chainlist::List;
chainlist::List * set = new chainlist::List;
int ran;
for(int i = 0; i < 5; ++i){
ran=rand();
set->insert(ran % 10);
}
set->display();
return *set;
}
It MUST test EVERY possible permutation that a list can through at you.
Ruben
On Sun, Apr 03, 2011 at 03:18:48PM -0400, Billy Donahue wrote:
> Interestingly, I think you might be getting away with it due to RVO
>
> On Sunday, April 3, 2011, Ruben Safir wrote:
> > On Sun, Apr 03, 2011 at 11:13:38AM -0400, Billy Donahue wrote:
> >> Creating_int_list can't return a reference to local variable 'set'.
> >> That will be a dangling reference.
> >>
> >
> > right - local set has to be made to be new and allocated
> >
> >> The only real solution is to implement copy constructor and assignment
> >> operator for List.
> >>
> >> A really interesting challenge would be to also implement a swap() so
> >> that you can avoid copies.
> >>
> >>
> >> List makealist() {
> >> ? List tmp;
> >> ? for (int i = 0; i < 100000; ++i) {
> >> ? ? tmp.push_back(i);
> >> ? }
> >> ? return tmp;
> >> }
> >>
> >> // ......... ?Lame
> >> List b = makealist(); ?// copy the entire temporary, which then dies.
> >>
> >> // ......... ?Better
> >> List b;
> >> using std::swap;
> >> swap(b, makealist()); ?// steal nodes directly from the temporary.
> >> Then empty temporary dies.
> >>
> >> Yes in this case, RVO could have elided the copy in the first example.
> >> In a more complex example that wouldn't be possible. ?Swap is a useful
> >> primary operation for containers. You should try writing it.
> >>
> >>
> >>
> >> On Saturday, April 2, 2011, Ruben Safir wrote:
> >> > On Sat, Apr 02, 2011 at 11:11:33PM -0400, Billy Donahue wrote:
> >> >> This is doomed. ?You are passing lists by value in multiple places.
> >> >> Does list have a valid assignment operator yet?
> >> >>
> >> >
> >> >
> >> > Its supposed to be doomed. ?It is an exact duplication of the error.
> >> > The solution (there is really two of them) is to return references.
> >> > The other will be done tomorrow, to build the copy constructor and the
> >> > assignment operator. ?Meanwhile I'm having fun playing with variations
> >> > of this to see how many ways I can segfault or double delete.
> >> >
> >> > Ruben
> >> >> --
> >> >> Typed on a tiny virtual keyboard
> >> >>
> >> >> On Apr 2, 2011, at 23:06, Ruben Safir wrote:
> >> >>
> >> >> > This coutlines the bug
> >> >> >
> >> >> > /*
> >> >> > * =====================================================================================
> >> >> > *
> >> >> > * ? ? ? Filename: ?test_del.cpp
> >> >> > *
> >> >> > * ? ?Description: ?Testing DOuble Deletes
> >> >> > *
> >> >> > * ? ? ? ?Version: ?1.0
> >> >> > * ? ? ? ?Created: ?04/02/2011 05:12:24 PM
> >> >> > * ? ? ? Revision: ?none
> >> >> > * ? ? ? Compiler: ?gcc
> >> >> > *
> >> >> > * ? ? ? ? Author: ?YOUR NAME Ruben Safir,
> >> >> > * ? ? ? ?Company: ?NYLXS
> >> >> > *
> >> >> > * =====================================================================================
> >> >> > */
> >> >> >
> >> >> >
> >> >> >
> >> >> > #ifndef ?LINKLIST
> >> >> > #define LINKLIST
> >> >> > #include ? ?"linklist.h"
> >> >> > #endif ? ? /* ----- ?not LINKLIST ?----- */
> >> >> >
> >> >> > #include ? ?
> >> >> > #include ? ?
> >> >> > #include ? ?
> >> >> > #include ? ?
> >> >> >
> >> >> > /*
> >> >> > * === ?FUNCTION
> >> >> > * ======================================================================
> >> >> > * ? ? ? ? Name: ?main
> >> >> > * ?Description:
> >> >> > * =====================================================================================
> >> >> > */
> >> >> >
> >> >> >
> >> >> > chainlist::List creating_int_list();
> >> >> > void find_all_examples(chainlist::List, int);
> >> >> >
> >> >> >
> >> >> > int main ( int argc, char *argv[] )
> >> >> > {
> >> >> >
> >> >> > ? chainlist::List outside = creating_int_list();
> >> >> > ? outside.display();
> >> >> > ? find_all_examples(outside, 4);
> >> >> >
> >> >> > ? outside.find_value(4);
> >> >> >
> >> >> >
> >> >> > ? std::cout <<
> >> >> > "****************************************OUTSIDE**************************************************"
> >> >> > << std::endl;
> >> >> > ? chainlist::Node * found = outside.cursor();
> >> >> > ? std::cout << "Found first value ==> '" << *found->value() << "' at
> >> >> > node =='" << outside.cursor() << std::endl;
> >> >> > ? found = &(outside.find_next_value(4, *found));
> >> >> > ? while( found ){
> >> >> > ? ? ?std::cout << "Found next value ==> '" << *(found->value()) << "'
> >> >> > at node =='" << outside.cursor() << std::endl;
> >> >> > ? ? ?found = &(outside.find_next_value(4, *found));
> >> >> > ? }
> >> >> >
> >> >> > ? return EXIT_SUCCESS;
> >> >> > } ? ? ? ? ? ? ? ?/* ---------- ?end of function main
> >> >> > ---------- */
> >> >> >
> >> >> >
> >> >> > chainlist::List creating_int_list(){
> >> >> > ? // chainlist::List ?set = new chainlist::List;
> >> >> > ? chainlist::List ?set;
> >> >> > ? srand(12345);
> >> >> > ? int ran;
> >> >> > ? for(int i = 0; i < 50000; ++i){
> >> >> > ? ? ?ran=rand();
> >> >> > ? ? ?set.insert(ran % 101);
> >> >> > ? }
> >> >> > ? return set;
> >> >> > }
> >> >> >
> >> >> > void find_all_examples ( chainlist::List glob, int search_value )
> >> >> > {
> >> >> > ? glob.find_value(search_value);
> >> >> > ? chainlist::Node * found = glob.cursor();
> >> >> > ? std::cout << "Found first value ==> '" << *found->value() << "' at
> >> >> > node =='" << glob.cursor() << std::endl;
> >> >> > ? found = &(glob.find_next_value(search_value, *found));
> >> >> > ? while( found ){
> >> >> > ? ? ?std::cout << "Found next value ==> '" << *(found->value()) <> >>> ? Copyright for the Digital Millennium
> >> >> >
> >> >> > --
> >> >> > http://www.mrbrklyn.com - Interesting Stuff
> >> >> > http://www.nylxs.com - Leadership Development in Free Software
> >> >> >
> >> >> > So many immigrant groups have swept through our town that Brooklyn, like Atlantis, reaches mythological proportions in the mind of the world ?- RI Safir 1998
> >> >> >
> >> >> > http://fairuse.nylxs.com ?DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
> >> >> >
> >> >> > "Yeah - I write Free Software...so SUE ME"
> >> >> >
> >> >> > "The tremendous problem we face is that we are becoming sharecroppers to our own cultural heritage -- we need the ability to participate in our own society."
> >> >> >
> >> >> > "> I'm an engineer. I choose the best tool for the job, politics be damned.<
> >> >> > You must be a stupid engineer then, because politcs and technology have been attached at the hip since the 1st dynasty in Ancient Egypt. ?I guess you missed that one."
> >> >> >
> >> >> > ? Copyright for the Digital Millennium
> >> >
> >> > --
> >> > http://www.mrbrklyn.com - Interesting Stuff
> >> > http://www.nylxs.com - Leadership Development in Free Software
> >> >
> >> > So many immigrant groups have swept through our town that Brooklyn, like Atlantis, reaches mythological proportions in the mind of the world ?- RI Safir 1998
> >> >
> >> > http://fairuse.nylxs.com ?DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
> >> >
> >> > "Yeah - I write Free Software...so SUE ME"
> >> >
> >> > "The tremendous problem we face is that we are becoming sharecroppers to our own cultural heritage -- we need the ability to participate in our own society."
> >> >
> >> > "> I'm an engineer. I choose the best tool for the job, politics be damned.<
> >> > You must be a stupid engineer then, because politcs and technology have been attached at the hip since the 1st dynasty in Ancient Egypt. ?I guess you missed that one."
> >> >
> >> > ? Copyright for the Digital Millennium
> >> >
> >>
> >> --
> >> ?n??uop ?ll?q
> >
> > --
> > http://www.mrbrklyn.com - Interesting Stuff
> > http://www.nylxs.com - Leadership Development in Free Software
> >
> > So many immigrant groups have swept through our town that Brooklyn, like Atlantis, reaches mythological proportions in the mind of the world ?- RI Safir 1998
> >
> > http://fairuse.nylxs.com ?DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
> >
> > "Yeah - I write Free Software...so SUE ME"
> >
> > "The tremendous problem we face is that we are becoming sharecroppers to our own cultural heritage -- we need the ability to participate in our own society."
> >
> > "> I'm an engineer. I choose the best tool for the job, politics be damned.<
> > You must be a stupid engineer then, because politcs and technology have been attached at the hip since the 1st dynasty in Ancient Egypt. ?I guess you missed that one."
> >
> > ? Copyright for the Digital Millennium
> >
>
> --
> ?n??uop ?ll?q
--
http://www.mrbrklyn.com - Interesting Stuff
http://www.nylxs.com - Leadership Development in Free Software
So many immigrant groups have swept through our town that Brooklyn, like Atlantis, reaches mythological proportions in the mind of the world - RI Safir 1998
http://fairuse.nylxs.com DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
"Yeah - I write Free Software...so SUE ME"
"The tremendous problem we face is that we are becoming sharecroppers to our own cultural heritage -- we need the ability to participate in our own society."
"> I'm an engineer. I choose the best tool for the job, politics be damned.<
You must be a stupid engineer then, because politcs and technology have been attached at the hip since the 1st dynasty in Ancient Egypt. I guess you missed that one."
? Copyright for the Digital Millennium
|
|
