Sign in to follow this  

[SOLVED]Segmentation fault in find method of an STL map with uses a struct as key.

This topic is 3741 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello everybody, I am not able to fix a Segmentation Fault that raises inside the find method of an STL map. Perhaps you can give me some clue. The map stores a one to many relationship between Usage and Resources. I use this struct to store the UsageId (the ResourceId is analogous):
typedef std::string UsageName;
typedef unsigned int UsageIndex;

struct UsageId {
    UsageName name;
    UsageIndex index;
    UsageId(UsageName, UsageIndex = 0);
    UsageId();
    bool operator<(const UsageId &) const;
     bool operator==(const UsageId &) const;
};

bool UsageId::operator<(const UsageId &other) const {
	if(name < other.name)
		return true;
	else if(name > other.name)
		return false;
	else {
		return ((unsigned int)(index) < (unsigned int)(other.index));
	}
}

bool UsageId::operator==(const UsageId &other) const {
    return ( ( name == other.name ) &
             ( (unsigned int)(index) == (unsigned int)(other.index) ) );
}

UsageId::UsageId(): name(""), index(UsageIndex(0)) {}
UsageId::UsageId(UsageName _name, UsageIndex _index): name(_name), index(_index) {}



As you can see I provide a default constructor that set the name and index to "" and 0 respectively. Now the class that stores the map:
class ResourceAssignationTable {
public:
    void assign(UsageId usage, ResourceId resource);
    ResourceId get_assigned_to(UsageId usage);
private:
    std::map<UsageId, std::list<ResourceId> > assigned;
}

ResourceId ResourceAssignationTable::get_assigned_to(UsageId usage) {

    map<UsageId, list<ResourceId> >::const_iterator it_assigned;
    it_assigned = assigned.find(usage);

    if(it_assigned == assigned.end()) throw "Usage not found";

    const list<ResourceId> &assigned = (*it_assigned).second;

    return *assigned.begin();
}



The Segmentation Fault raises inside the get_assigned_to method, concretely in the line:
it_assigned = assigned.find(usage);



I debugged that method and I found the exception raises in the comparison between names (strings) in the first line of the comparison method of UsageId:
bool UsageId::operator<(const UsageId &other) const {
	if(name < other.name)
		return true;
	else if(name > other.name)
		return false;
	else {
		return ((unsigned int)(index) < (unsigned int)(other.index));
	}
}



The variable "other" contains the UsageId provided to the find method, as expected, but the member variables "name" and "id" seems to be uninitialized and contain garbage. So when the comparison operator tries to access the string "name" it raises the segmentation fault. I don't understand how UsageId object can contain garbage since I provide a default constructor. I use a large test, and this method works perfectly for hundred of calls. But it always raises the exception in the same point, when asked for a particular UsageId. This UsageId was requested early in the test and the method worked! Well, that's all. Any clue will be welcomed. Regards Chema [Edited by - chema on September 18, 2007 8:21:13 AM]

Share this post


Link to post
Share on other sites
I don't see anything that's strictly incorrect either, but I did notice this:
return *assigned.begin();
You didn't show how you go about adding resources to the map, so I'll go ahead and ask: are you sure the lists can never be empty?

A couple of other random comments:

1. A couple of your functions take their 'usage ID' arguments by value (I just mention this because you pass UsageID objects by constant reference elsewhere, which is probably better given that the UsageID struct incorporates a string object).

2. Have you considered using a multimap, rather than a map with a list as its value type?

3. Some would discourage the throwing of string literals (see this page for a discussion of the issue).

Share this post


Link to post
Share on other sites
Quote:
Original post by chema
I am not able to fix a Segmentation Fault that raises inside the find method of an STL map. Perhaps you can give me some clue.


It has been my unfortunately frequent experience that find() will barf if your orderting function does not model Strict Weak Ordering.

Double-check your operator<(). Make absolutely sure comp(i,j) != comp(j,i).

--smw

Share this post


Link to post
Share on other sites
Is it possible that you're calling the function through a null or corrupt ResourceAssignationTable* ?

Bregma: it looks like a valid lexicographical ordering to me.

Share this post


Link to post
Share on other sites
Hello again,

It makes sense that there's a memory corruption originated elsewhere, as DrEvil and Zahlman pointed. In other parts of the program large data blocks are being moved. So as nobody has found anything incorrect I will investigate in the data blocks sections.

About jyk questions:

Quote:
You didn't show how you go about adding resources to the map, so I'll go ahead and ask: are you sure the lists can never be empty?


Lists shouldn't become empty, the key is erased when a list is empty.

Quote:
1. A couple of your functions take their 'usage ID' arguments by value (I just mention this because you pass UsageID objects by constant reference elsewhere, which is probably better given that the UsageID struct incorporates a string object).


I use references inside the methods to give a meaningful name to variables without having to copy them. I pass arguments and return by value, I know it's not the most efficient way but efficiency is not critical in this program.

Quote:
2. Have you considered using a multimap, rather than a map with a list as its value type?


No, because my knowledge of STL is very limited. Probably a multimap will be better. I will read some STL book when I have some time.

Quote:
3. Some would discourage the throwing of string literals (see this page for a discussion of the issue).


Yes, I agree. The throw will be subsituted by an error function in final version.

Chema

Share this post


Link to post
Share on other sites
Hello

I found the error! I was giving wrong arguments to a memcpy function in another place, so memory got corrupted.

Thank you everybody for helping me to discard STL and focus on the memory operations.

Chema

Share this post


Link to post
Share on other sites
Quote:
Original post by chema
Hello

I found the error! I was giving wrong arguments to a memcpy function in another place, so memory got corrupted.

Thank you everybody for helping me to discard STL and focus on the memory operations.

Chema


?!

Use the modern standard C++ library to *address* your memory-operation problems. Instead of memcpy(), use std::copy() from <algorithm>. It works on container ranges as well as arrays, and on user-defined types rather than raw bytes, and is type-safe.

Share this post


Link to post
Share on other sites

This topic is 3741 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this