Memory allocation error

I don't know what to make of these two errors. One happens when I'm trying to create a new instance of a custom class which is defined as:

Code:

---

struct Patricia::Node
{
  bool reversed;
  string key;
  set<Node*> from;
  set<Node*> to;

  Node();
  void findLCS(const string&, PATH*);
  void horizontalCollapse(UINT);
  void print(ostream&, Patricia*);
  void graphVizPrint(ostream&, Patricia*);
  void classify(Patricia*, UINT = 0);
  bool isInPath(const Node*);
};

---

When I try to create a new Node, I get an error and the backtrace is not helping me out at all:

Code:

---

*** glibc detected *** malloc(): memory corruption (fast): 0x0805d408 ***

Program received signal SIGABRT, Aborted.
0xb7fcf410 in ?? ()
(gdb) up
#1  0xbf82f878 in ?? ()
(gdb) up
#2  0x00000006 in ?? ()
(gdb) up
#3  0x000006ed in ?? ()
(gdb) up
#4  0xb7daa9a1 in raise () from /lib/tls/i686/cmov/libc.so.6
(gdb) up
#5  0xb7dac2b9 in abort () from /lib/tls/i686/cmov/libc.so.6
(gdb) up
#6  0xb7dde87a in __fsetlocking () from /lib/tls/i686/cmov/libc.so.6
(gdb) up
#7  0xb7de5ea4 in free () from /lib/tls/i686/cmov/libc.so.6
(gdb) up
#8  0xb7de7411 in malloc () from /lib/tls/i686/cmov/libc.so.6
(gdb) up
#9  0xb7f87e26 in operator new () from /usr/lib/libstdc++.so.6
(gdb) up
#10 0x0804c4a1 in Patricia::insert (this=0xbf83012c, s=@0x805d848, thresh=1) at patricia.cpp:322
(gdb) up
#11 0x080547c1 in main (argc=1, argv=0xbf830244) at patricia_test.cpp:56

---

The other error happens when I try to copy from one container to another:

Code:

---

set<Node*> A, B;
//initialize B
A = B;

---

And this is the backtrace from the stack:

Code:

---

Program received signal SIGSEGV, Segmentation fault.
0xb7d1d401 in free () from /lib/tls/i686/cmov/libc.so.6
(gdb) up
#1  0xb7d1f411 in malloc () from /lib/tls/i686/cmov/libc.so.6
(gdb) up
#2  0xb7ebfe26 in operator new () from /usr/lib/libstdc++.so.6
(gdb) up
#3  0x08052327 in __gnu_cxx::new_allocator<std::_Rb_tree_node<Patricia::Node*> >::allocate (this=0xbf8eea10, __n=1) at new_allocator.h:88
(gdb) up
#4  0x0805234b in std::_Rb_tree<Patricia::Node*, Patricia::Node*, std::_Identity<Patricia::Node*>, std::less<Patricia::Node*>, std::allocator<Patricia::Node*> >::_M_get_node
    (this=0xbf8eea10) at stl_tree.h:356
(gdb) up
#5  0x08052360 in std::_Rb_tree<Patricia::Node*, Patricia::Node*, std::_Identity<Patricia::Node*>, std::less<Patricia::Node*>, std::allocator<Patricia::Node*> >::_M_create_node (this=0xbf8eea10, __x=@0x805da68) at stl_tree.h:365
(gdb) up
#6  0x080523c3 in std::_Rb_tree<Patricia::Node*, Patricia::Node*, std::_Identity<Patricia::Node*>, std::less<Patricia::Node*>, std::allocator<Patricia::Node*> >::_M_clone_node (this=0xbf8eea10, __x=0x805da58) at stl_tree.h:379
(gdb) up
#7  0x08052403 in std::_Rb_tree<Patricia::Node*, Patricia::Node*, std::_Identity<Patricia::Node*>, std::less<Patricia::Node*>, std::allocator<Patricia::Node*> >::_M_copy (
    this=0xbf8eea10, __x=0x805da58, __p=0x805d4d0) at stl_tree.h:1057
(gdb) up
#8  0x0805243c in std::_Rb_tree<Patricia::Node*, Patricia::Node*, std::_Identity<Patricia::Node*>, std::less<Patricia::Node*>, std::allocator<Patricia::Node*> >::_M_copy (
    this=0xbf8eea10, __x=0x805dd98, __p=0x805d628) at stl_tree.h:1063
(gdb) up
#9  0x080524ae in std::_Rb_tree<Patricia::Node*, Patricia::Node*, std::_Identity<Patricia::Node*>, std::less<Patricia::Node*>, std::allocator<Patricia::Node*> >::_M_copy (
    this=0xbf8eea10, __x=0x805e3b8, __p=0x805dac8) at stl_tree.h:1073
(gdb) up
#10 0x0805258f in std::_Rb_tree<Patricia::Node*, Patricia::Node*, std::_Identity<Patricia::Node*>, std::less<Patricia::Node*>, std::allocator<Patricia::Node*> >::operator= (
    this=0xbf8eea10, __x=@0xbf8ee9f8) at stl_tree.h:775
(gdb) up
#11 0x08052608 in std::set<Patricia::Node*, std::less<Patricia::Node*>, std::allocator<Patricia::Node*> >::operator= (this=0xbf8eea10, __x=@0xbf8ee9f8) at stl_set.h:214
(gdb) up
#12 0x0804adbd in Patricia::graphVizPrint (this=0xbf8ee9ec, os=0xbf8ee820) at patricia.cpp:483
(gdb) up
#13 0x080547f4 in main (argc=1, argv=0xbf8eeb04) at patricia_test.cpp:58
(gdb)

---

Any help would be appreciated.

Both errors are indications that you are "messing with memory you shouldn't be touching".

The first error is almost certainly caused by overwriting the end of memory allocated with new or malloc.

In the second case, you are going off into the weeds, so the processor says "There's no memory there". What is the constructor for your Node doing?

--
Mats

Quote:

---

Originally Posted by matsp

What is the constructor for your Node doing?

---

Not much

Code:

---

Patricia::Node::Node()
{
  reversed = false;
  key = "";
}

---

As for copy/assignment error, I guess I'll have to look into where I got my algorithm wrong.

Actually, looking at the call-stack, it may well be that the heap is corrupted by that point.

Perhaps it's when you are populating B that you are overwriting some buffer of some sort.

Edit: So what I'm trying to say is that both problems are caused by similar things - usually by writing past the end of some array.

Edit2: To show the whole stack in your application in gdb, use "bt" - saves you hitting "up" 11 times [yes, hitting enter will repeat the previous command, but still easier to just type one command and be done with it].

--
Mats

Yup. Turns out that memory deallocation that I was doing elsewhere (I was doing it twice for some nodes) was throwing me on a loop in weird places.

As for 'bt' thanks for the reminder but I try to avoid it at the moment, since the FSM I'm writing sometimes falls into an infinite loop then just blasts me with pages and pages of identical messages.

Thanks for the help.

Quote:

---

Originally Posted by cunnus88

Yup. Turns out that memory deallocation that I was doing elsewhere (I was doing it twice for some nodes) was throwing me on a loop in weird places.

As for 'bt' thanks for the reminder but I try to avoid it at the moment, since the FSM I'm writing sometimes falls into an infinite loop then just blasts me with pages and pages of identical messages.

Thanks for the help.

---

You can use "bt 10" to get the last 10 frames on the stack, in that case.

It's always good to set pointers to NULL after deleting them - that way, you CAN'T delete them twice, as delete automatically understands NULL pointers and don't do anything with that.

--
Mats