Solved

Segmentation Fault in between loops

Posted on 2006-06-21
31
428 Views
Last Modified: 2012-05-05
I have a function that is performing two loops as follows:

bool test2(int i){
   cout << i << endl;
   return true;
}

void itree::CharmExtend(list<int>& C, int minSupp){
   for(int i = 0; test2(7) && i<this->count && this->itsets[i]!=NULL; i++){
      itree* Px = new itree(count-i);
      itset X;// = new itset();
      int j=0;
      j=i+1;
      for(; j<this->count && this->itsets[j]!=NULL; j++){
       X.ItemUnion(*(this->itsets[i]), *(this->itsets[j]));
       X.TransIntersection(*(this->itsets[i]), *(this->itsets[j]));
       if(X.TransCount() >= minSupp)
          if(itsets[i]->Transactions() == itsets[j]->Transactions()){
             this->RemoveItset(j);
          }
          else if(itsets[i]->Subset(itsets[j])){
             //Replace Xi with X
          }
       else if(itsets[j]->Subset(itsets[i])){
             this->Remove(j);
             Pi.AddItset(X, j);
             }
          else if(itsets[i]->Transactions() != itsets[j]->Transactions()){
             //Pi.AddItset(X, j);
          }
      
      
       //CharmProperty
       //CharmProperty
       //CharmProperty
      }

      if(Px->Count()>0){
       Px->Sort(minSupp);
       Px->CharmExtend(C, minSupp);
      }
      delete Px;
      Px =NULL;
      cout << "End of loop... " << endl;
      //Add X to C
      //X = NULL;
   }
   cout << "Outside Loop" << endl;
}

My problem is that after printing "End of loop..." and before printing "7" I get a segmentation fault.  I have put cout's in my destructors for X and Px and both are finishing before the segmentation fault occurs.  I have no idea where to go to look for the error.

Sterling
0
Comment
Question by:SterlingMcClung
  • 18
  • 11
31 Comments
 
LVL 30

Expert Comment

by:Axter
ID: 16956920
Hi SterlingMcClung,
Why are you using new and delete in this loop.
You should not use new and delete, unless you're sure your code requires it.
The above code does not require it, and you can use concrete type like itset X;

Cheers!
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16956924
Yes I know it does not need it.  I did that because without calling delete that way the destructor for Px does not get called at the end of the loop.

Sterling
0
 
LVL 30

Expert Comment

by:Axter
ID: 16956970
>>I did that because without calling delete that way the destructor for Px does not get called at the end of the loop.

You still don't need it for that.
You can accomplish the same thing, by putting it into an explicit scope using {}
Once the code gets out of the scope, the destructor will get called automatically.

for(int i = 0; test2(7) && i<this->count && this->itsets[i]!=NULL; i++)
{ //For loop scope
  itset X;
  { //Explicit scope
     itree Px(count-i);
     //.... other code
  } //End explicit scope
  //... other code
} //End for loop
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16956973
Just tried it again with concrete type and I get the segmentation fault after the destructor for X is called, but before the destructor for Px is called.

Sterling
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16956979
I guess my orginal question should have included my last comment.

Sterling
0
 
LVL 30

Expert Comment

by:Axter
ID: 16956991
Please post the code for the X type.
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16956993
I added another itree in an explicit scope at the end of the loop as follows:

. . .
 if(Px->Count()>0){
      Px->Sort(minSupp);
      Px->CharmExtend(C, minSupp);
      }
      delete Px;
      Px =NULL;
      cout << "End of loop... " << endl;
      //Add X to C
      //X = NULL;
     {
        itree test;
      }
   }
   cout << "Outside Loop" << endl;
}

and the test itree's destructor is called and completes, but I can't get Px to destroy.

Sterling
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16956999
Here is the .h file.  
#pragma once

#include <queue>
#include <list>
#include <iostream>

using namespace std;

class itset{

 private:
  int transCount;
  int itemCount;
  int weight;
  list<int> items;
  list<int> transactions;
  bool weighed;
 
  int unions(list<int>& left, list<int>& right, list<int>& result);
  int difference(list<int>& left, list<int>& right, list<int>& result);
  int intersection(list<int>& left, list<int>& right, list<int>& result);

 public:
  itset();
  ~itset();

  list<int>& Items();
  list<int>& Transactions();
  int& Weight();
  int TransCount();

  void AddItem(int);
  void AddTransaction(int);
  void ItemUnion(itset& left, itset& right);
  void ItemDifference(itset& left, itset& right);
  void ItemIntersection(itset& left, itset&);
  void TransUnion(itset& left, itset& right);
  void TransDifference(itset& left, itset& right);
  void TransIntersection(itset& left, itset& right);


  bool operator<(itset) const;
  bool operator==(itset) const;
  itset operator+(itset&);
  friend ostream& operator<<(ostream&, const itset&);


};

I am going to have to clean up the .cpp file before I can post it...
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957004
I tried this with Px removed completely, as I am just trying to add it in now, and I still get the seg fault without itree Px.
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957010
Here is the cpp file.


#include "itset.h"
#include <queue>
#include <list>
#include <algorithm>

using namespace std;

itset::itset(){
  transCount=0;
  itemCount=0;
  weighed=false;
};
itset::~itset(){
   cout << "Destroying itset..." << endl;
   transCount=0;
   itemCount=0;
   weighed=false;
   cout << "Destroyed itset" << endl;
};

list<int>& itset::Items(){
  return this->items;
}

int itset::unions(list<int>& left, list<int>& right, list<int>& result){  
   set_union(left.begin(), left.end(),
                right.begin(), right.end(),
           result.begin());
   return result.size();
}

int itset::difference(list<int>& left, list<int>& right, list<int>& result){
   set_difference(left.begin(), left.end(),
              right.begin(), right.end(),
              result.begin());
   return result.size();
}

int itset::intersection(list<int>& left, list<int>& right, list<int>& result){

   int size=0;
   for(list<int>::iterator it=left.begin(); it!=left.end(); it++){
      for(list<int>::iterator it2=right.begin(); it2!=right.end(); it2++){
       if(*it==*it2){
          result.push_back(*it);
          size++;
       }
      }
   }
   return size;
}

list<int>& itset::Transactions(){
  return this->transactions;
}

int itset::TransCount(){
  return transCount;
}

int& itset::Weight(){
   return this->weight;
}

void itset::AddItem(int value){
  this->items.push_back(value);
  itemCount++;
}

void itset::AddTransaction(int value){
  this->transactions.push_back(value);
  transCount++;
}

void itset::ItemUnion(itset& left, itset& right){
   itemCount = unions(left.items, right.items, this->items);
}

void itset::ItemDifference(itset& left, itset& right){
   itemCount = difference(left.items, right.items, this->items);
}

void itset::ItemIntersection(itset& left, itset& right){
   itemCount = intersection(left.items, right.items, this->items);
}

void itset::TransUnion(itset& left, itset& right){
   transCount = unions(left.transactions,
                   right.transactions, this->transactions);
}

void itset::TransDifference(itset& left, itset& right){
   transCount = difference(left.transactions,
                     right.transactions, this->transactions);
}

void itset::TransIntersection(itset& left, itset& right){
   transCount = intersection(left.transactions,
                       right.transactions, this->transactions);
   
}


bool itset::operator<(itset right) const{
    return this->transCount < right.transCount;
}

bool itset::operator==(itset right) const{
  return this->transCount == right.transCount;
}
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957013
Just realized I have code in my ~itset that shouldn't be there.  I will remove and try(although I don't think it is causing problems).
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957023
With the following:
itset::~itset(){
   cout << "Destroying itset..." << endl;
//    transCount=0;
//    itemCount=0;
//    weighed=false;
   cout << "Destroyed itset" << endl;
};

I still get the segmentation fault inbetween loops.

Sterling
0
 
LVL 30

Expert Comment

by:Axter
ID: 16957047
I don't see anything that stands out in the itset class.

Can you post the header for itree?
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957121
#pragma once

#include <queue>
#include "itset.h"

#define DEFAULT_ARRAY_SIZE 1000

using namespace std;

struct lessp{
  bool operator()(itset* left, itset* right){
    return (*left) < (*right);
  }
};

class itree{
 private:
  itset** itsets;
  int size;
  int count;

 public:
  //  itree();
  itree(int sz=DEFAULT_ARRAY_SIZE);
  ~itree();

  itset* Itsets();

  int Count(){return count;};

//  void AddItset(itset);
//  void AddItset(itset*);
  void AddItset(int item, int transaction);
  void AddItset(itset*, int);
  void RemoveItset(int);
//  void RemoveItset(itset*);
  void Sort();
  void Sort(int);
  void CharmExtend(list<int>&, int);
  void CalculateWeights(int);

  itset* operator[](int i){return itsets[i];};
 
  void DoForEachItset(void (*f)(itset&));
  void DoForEachItsetGreater(itset& Xi, void(*f)(itset&));

};
0
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 
LVL 30

Expert Comment

by:Axter
ID: 16957158
>>itset** itsets;

This is dangerous, and I'm pretty sure it's related to the runtime error.

I recommend using std::vector<itset> or std::vector<itset*> instead of a raw pointer of pointer type.
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957198
I was trying to avoid vectors due to speed concerns...  This array is used to translate a db from horizontal format to vertical format, so I need to do over 4,000,000 finds on this structure, which is going to take too long using a vector.  I am able to use the array as a perfect hashtable based on the item number in the db.  I have not come up with a better way of doing this.

Sterling
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957207
I have trouble using a sorted datastructure due to the fact that I don't know my sort criteria until after the db is read completly.

Sterling
0
 
LVL 30

Expert Comment

by:Axter
ID: 16957246
>>I was trying to avoid vectors due to speed concerns...

vector is very fast and efficient, and on some implementations, vector is faster then using C style arrays.

On most implementations, there's very little difference in performance between a vector and a C style array.
You can verify this by doing a performance test on non-debug version of the code.  If you use debug version of the code, then vector will normally perform badly, but debug version of the code should never be used for performance test.
0
 
LVL 30

Expert Comment

by:Axter
ID: 16957277
>>which is going to take too long using a vector.

It should not take any longer using a vector, if it's correctly implemented.
If you can determine your size at runtime, you can increase the vector efficiency by calling vector.reserve

>>I am able to use the array as a perfect hashtable based on the item number in the db
You may want to use std::map instead, which you can link directly to the item number in the db.
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957292
I just remembered that we had problems with calling the size() function on the list<int> transactions found in itset.h.  I found that I was still calling that function on the list<int> items found in the same file from the function unions() in itsets.cpp.  I rewrote the code and it works now.

I am still concerned about your concern for the pointer to pointer and will continue to look for a way to not use it, but for the moment it is working again....

Sterling
0
 
LVL 30

Expert Comment

by:Axter
ID: 16957311
>>I just remembered that we had problems with calling the size() function on the list<int> transactions found in itset.h.

Calling the size function by itself, should never cause a runtime error, unless there is another problem that is currupting memory.
Just removing the size function, will only hide the real problem.
The real problem will probably cause other runtime errors in some other part of the code.
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957370
I will have to wait untill tomorrow night to work on switching things around.  As it is, I still don't really understand how this might be causing my problems.  I am able to loop thru my pointer to pointer array with other functions without problems.  It is just when I call the size() function on a list<int> that I am getting into trouble.  Is this dangerous only because it makes it difficult to follow the pointers properly, or does it make the compiler more suseptable to errors?
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957409
I thought that vectors suffered from slow lookup times.  Since I am able to use my pointer to pointer array as a perferct hash I get constant time lookups, while I thought vectors were much slower.

I am storing, something similar to, pair<int item, list<int>trans> in the array to begin with.  As I read a new item in a transaction, I must find that item pair in the array, or create it if it does not exist, and add another transaction number into the list.  With a vector won't this mean manually iterating through the vector each time?
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16957422
I looked into the std::map as well, and decided it did not fit well due to the need to have the items ordered and maps inability to guarantee order.

Sterling
0
 
LVL 30

Expert Comment

by:Axter
ID: 16958654
>>difficult to follow the pointers properly, or does it make the compiler more suseptable to errors?

It makes the code more suseptable to errors.

>>I thought that vectors suffered from slow lookup times.
No.  It has the fastest lookup time.  The C++ standard recommends it as the default container.


>>I am storing, something similar to, pair<int item, list<int>trans> in the array to begin with.  As I read a new item in a transaction, I must find that item pair in the
>>array, or create it if it does not exist, and add another transaction number into the list.  With a vector won't this mean manually iterating through the vector each
>>time?

For above requirement, a vector would not be the best choice, and it would be better to use a std::map.
An std::map should be far faster then using above method.
std::map<int item, vector<int> > itsets;

If your compiler or your STL library supports it, you can also think about using hash_map.
hash_map<int item, vector<int> > itsets;

But I suspect, that just using std::map will be a great improvement, and will make the code far safer then using a pointer of pointers.
0
 
LVL 30

Expert Comment

by:Axter
ID: 16958692
>>I looked into the std::map as well, and decided it did not fit well due to the need to have the items ordered and maps inability to guarantee order.

I think you're misunderstanding std::map, and you're real requirement.

What you need is to be able to access the contents of the container in constant time.  It really shouldn't matter if the container has the contents in order, as long as the lookup time is fast.
So it shouldn't matter if std::map has the contents in order, as long as it can find the contents quickly.

If for what ever reason you still require the contents to be in order, then consider using std::hash_map.
If your implementation doesn't support it, you can download it from boost or other free STL libraries.
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16961006
Your right, I don't really know the STL containers very well yet.  I have one question about map.  While I am reading the data from the file, I need to have things with quick lookup based on the item number, but after that I need this sorted based on the number of transactions a single item has.  After reading the file, I no longer need the constant lookup times, since all my calculations, quite a bit, will be based strictly on the order of the items, so I will be just iterating over the structure.  With map is it difficult to resort based on a new criteria?  Or might I be better off to use a vector and then sort using qsort?

Sterling

I don't have any time during the day to rewrite the code, but I will try some of these options early this evening.
0
 
LVL 30

Accepted Solution

by:
Axter earned 500 total points
ID: 16961318
>>With map is it difficult to resort based on a new criteria?  Or might I be better off to use a vector and then sort using qsort?

This gets a little tricky, and there are many ways to tackle this problem.
Method 1:
Have three containers, with only one of the containers storing the acutal data.
Example:

std::vector<std::vector<int> > My_RealData;
std::map<int, size_t> MyMapPointingToMyRealDataViaSortCriteria1;
std::map<int, size_t> MyMapPointingToMyRealDataViaSortCriteria2;

Now each time you add an item to the My_RealData, you want to also add and index to that item current location in the map containers.
 My_RealData.push_back(somecontainerdata);
MyMapPointingToMyRealDataViaSortCriteria1[ItemNumber] =  My_RealData.size()-1;
MyMapPointingToMyRealDataViaSortCriteria1[SomeOtherLookupValue] =  My_RealData.size()-1;

This method should be efficient as long as you don't have to delete containers in the My_RealData container, and you don't have to change your ItemNumbers or other key-lookup values.


If you need to delete values in the  My_RealData container, then another method you can use is to store a class in the  My_RealData container that would hold the lookup values in the std::map containers, so that you can safely remove the std::map items before deleting the contents from  My_RealData container.
0
 
LVL 7

Author Comment

by:SterlingMcClung
ID: 16969243
I was able to switch things aroung last night.  I decided to use a vector<itset> and then call sort on it after I was finished reading.  While this may not be the best way to handle this, it did require the least amount of rewriting, and I need to show results today...  Thanx for everything. I now have this working better than I thought it would be.  Later I may try implementing this with the map as suggested, but for now, I have a program that runs.

Sterling
0

Featured Post

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now