🔒 Locked

Stack overflow in quadtree

Started by Jappie Jan 5, 2002 at 9:20 AM 11 replies 1.7k views

Original Post

Jan 5, 2002 at 9:20 AM

Perhaps someone can point out why I''m getting a stack overflow in this piece of code. Assume all resources are freed correctly, but that isn''t really even an issue here, as the problem arises during the setup of the quadtree, more specifically during the allocation of memory for the vertices. Don''t know exactly which node causes the problem, though a tree with a LEAF_SIZE of 512 (I start off with a map size of 1024), resulting in 4 leaves and 5 nodes (including the root), works fine, and a LEAF_SIZE of 256 (resulting in 16 leaves and 21 nodes including the root) causes the overflow. Here''s the node initialization function:

  
bool node::Init(int nBoundingCoords[], char *cHeightMap)
{
  // Set node''s type

  if((nBoundingCoords[1] - nBoundingCoords[0]) <= LEAF_SIZE)
  {
    nType = LEAF_TYPE;

    // Set node''s vertices

    v_BoundingCoords = new vertex[4];
    if(v_BoundingCoords == NULL)
      return false;

    // Top-left vertex

    v_BoundingCoords[0].v[0] = nBoundingCoords[0];
    v_BoundingCoords[0].v[1] = 0;
    v_BoundingCoords[0].v[2] = nBoundingCoords[2];

    // Top-right vertex

    v_BoundingCoords[1].v[0] = nBoundingCoords[1];
    v_BoundingCoords[1].v[1] = 0;
    v_BoundingCoords[1].v[2] = nBoundingCoords[2];

    // Bottom-left vertex

    v_BoundingCoords[2].v[0] = nBoundingCoords[0];
    v_BoundingCoords[2].v[1] = 0;
    v_BoundingCoords[2].v[2] = nBoundingCoords[3];

    // Bottom-right vertex

    v_BoundingCoords[3].v[0] = nBoundingCoords[1];
    v_BoundingCoords[3].v[1] = 0;
    v_BoundingCoords[3].v[2] = nBoundingCoords[3];
  }
  else
  {
    nType = NODE_TYPE;

    // Enable children

    int nNewBoundingCoords[4];

    // Enable top-left child

    n_TopLeftChild = new node;
    if(n_TopLeftChild == NULL)
      return false;

    nNewBoundingCoords[0] = nBoundingCoords[0];
    nNewBoundingCoords[1] = (nBoundingCoords[1] - nBoundingCoords[0]) / 2;
    nNewBoundingCoords[2] = nBoundingCoords[2];
    nNewBoundingCoords[3] = (nBoundingCoords[3] - nBoundingCoords[2]) / 2;

    if(!n_TopLeftChild->Init(nNewBoundingCoords, cHeightMap))
      return false;

    // Enable top-right child

    n_TopRightChild = new node;
    if(n_TopRightChild == NULL)
      return false;

    nNewBoundingCoords[0] = (nBoundingCoords[1] - nBoundingCoords[0]) / 2;
    nNewBoundingCoords[1] = nBoundingCoords[1];
    nNewBoundingCoords[2] = nBoundingCoords[2];
    nNewBoundingCoords[3] = (nBoundingCoords[3] - nBoundingCoords[2]) / 2;

    if(!n_TopRightChild->Init(nNewBoundingCoords, cHeightMap))
      return false;

    // Enable bottom-left child

    n_BottomLeftChild = new node;
    if(n_BottomLeftChild == NULL)
      return false;

    nNewBoundingCoords[0] = nBoundingCoords[0];
    nNewBoundingCoords[1] = (nBoundingCoords[1] - nBoundingCoords[0]) / 2;
    nNewBoundingCoords[2] = (nBoundingCoords[3] - nBoundingCoords[2]) / 2;
    nNewBoundingCoords[3] = nBoundingCoords[3];

    if(!n_BottomLeftChild->Init(nNewBoundingCoords, cHeightMap))
      return false;

    // Enable bottom-right child

    n_BottomRightChild = new node;
    if(n_BottomRightChild == NULL)
      return false;

    nNewBoundingCoords[0] = (nBoundingCoords[1] - nBoundingCoords[0]) / 2;
    nNewBoundingCoords[1] = nBoundingCoords[1];
    nNewBoundingCoords[2] = (nBoundingCoords[3] - nBoundingCoords[2]) / 2;
    nNewBoundingCoords[3] = nBoundingCoords[3];

    if(!n_BottomRightChild->Init(nNewBoundingCoords, cHeightMap))
      return false;
  }
  return true;
}

Anyone have a clue? I know I don''t

----------------------------- Jappie BabJap Productions "There''s no such things as bugs; they''re just unintentional extra features"

Kippesoep

Jan 5, 2002 at 9:39 AM

I don''t see anything wrong with your code. Stack overflows may be caused by stuff outside the function in which they become apparent, though. Do you perhaps have some large local variables in the functions up the call stack? Stuff like this:

  
class CBloat
{
  char classBytes [500000];
}
void main ()
{
  char localvars [500000];
  CBloat useStack;
  ...
}

That''ll severely limit your available stack space. Try seeing if the problem occurs if you have nothing but the initialisation of these nodes. Somehow, I doubt it...

Jappie

Author

Jappie

Jan 5, 2002 at 2:29 PM

Well, I tried what you suggested and stripped my classes of everything except those node pointers. Still doesn''t work. I even removed everything in the base program (essentially nothing more than a skybox) but to no avail. I thought I''d just post everything I''ve got on this, and you''ll ofcourse point out one tiny stupid-ass mistake I made

  
// Header file for landscape


// Created on 05-01-2002


#ifndef LANDSCAPE_H
#define LANDSCAPE_H

#include "BJUtil.h"

extern const int NODE_TYPE;
extern const int LEAF_TYPE;

extern const int LEAF_SIZE;

class node
{
  private:
    node *n_TopLeftChild;
    node *n_TopRightChild;
    node *n_BottomLeftChild;
    node *n_BottomRightChild;

  public:
    node() {}
    ~node();

    bool Init(int nBoundingCoords[]);
};

class landscape
{
  private:
    node *n_Root;

  public:
    landscape();
    ~landscape();

    bool Init(int nSize);
};

#endif

  
// Source file for landscape


// Created on 05-01-2002


#include <windows.h>
#include <stdio.h>
#include <gl/gl.h>

#include "BJUtil.h"
#include "landscape.h"

const int NODE_TYPE = 0;
const int LEAF_TYPE = 1;

const int LEAF_SIZE = 256;

// N O D E //


node::~node()
{
  if(n_TopLeftChild != NULL)
    delete n_TopLeftChild;
  if(n_TopRightChild != NULL)
    delete n_TopRightChild;
  if(n_BottomLeftChild != NULL)
    delete n_BottomLeftChild;
  if(n_BottomRightChild != NULL)
    delete n_BottomRightChild;
}

bool node::Init(int nBoundingCoords[])
{
  // Set node''s type

  if((nBoundingCoords[1] - nBoundingCoords[0]) <= LEAF_SIZE)
  {

  }
  else
  {
    // Enable children

    int nNewBoundingCoords[4];

    // Enable top-left child

    n_TopLeftChild = new node;
    if(n_TopLeftChild == NULL)
      return false;

    nNewBoundingCoords[0] = nBoundingCoords[0];
    nNewBoundingCoords[1] = (nBoundingCoords[1] - nBoundingCoords[0]) / 2;
    nNewBoundingCoords[2] = nBoundingCoords[2];
    nNewBoundingCoords[3] = (nBoundingCoords[3] - nBoundingCoords[2]) / 2;

    if(!n_TopLeftChild->Init(nNewBoundingCoords))
      return false;

    // Enable top-right child

    n_TopRightChild = new node;
    if(n_TopRightChild == NULL)
      return false;

    nNewBoundingCoords[0] = (nBoundingCoords[1] - nBoundingCoords[0]) / 2;
    nNewBoundingCoords[1] = nBoundingCoords[1];
    nNewBoundingCoords[2] = nBoundingCoords[2];
    nNewBoundingCoords[3] = (nBoundingCoords[3] - nBoundingCoords[2]) / 2;

    if(!n_TopRightChild->Init(nNewBoundingCoords))
      return false;

    // Enable bottom-left child

    n_BottomLeftChild = new node;
    if(n_BottomLeftChild == NULL)
      return false;

    nNewBoundingCoords[0] = nBoundingCoords[0];
    nNewBoundingCoords[1] = (nBoundingCoords[1] - nBoundingCoords[0]) / 2;
    nNewBoundingCoords[2] = (nBoundingCoords[3] - nBoundingCoords[2]) / 2;
    nNewBoundingCoords[3] = nBoundingCoords[3];

    if(!n_BottomLeftChild->Init(nNewBoundingCoords))
      return false;

    // Enable bottom-right child

    n_BottomRightChild = new node;
    if(n_BottomRightChild == NULL)
      return false;

    nNewBoundingCoords[0] = (nBoundingCoords[1] - nBoundingCoords[0]) / 2;
    nNewBoundingCoords[1] = nBoundingCoords[1];
    nNewBoundingCoords[2] = (nBoundingCoords[3] - nBoundingCoords[2]) / 2;
    nNewBoundingCoords[3] = nBoundingCoords[3];

    if(!n_BottomRightChild->Init(nNewBoundingCoords))
      return false;
  }
  return true;
}

// L A N D S C A P E //


landscape::landscape()
{

}

landscape::~landscape()
{
  if(n_Root)
    delete n_Root;
}

bool landscape::Init(int nSize)
{
  // Setup the root node

  n_Root = new node;
  if(n_Root == NULL)
    return false;

  int nBoundingCoords[4];

  nBoundingCoords[0] = 0;
  nBoundingCoords[1] = nSize;
  nBoundingCoords[2] = 0;
  nBoundingCoords[3] = nSize;

  if(!n_Root->Init(nBoundingCoords))
    return false;

  return true;
}

Still, if you don''t know either, thanks anyway man. (btw, funny how 2 ppl from Holland keep on babbling in English

-----------------------------
Jappie
BabJap Productions

"There''s no such things as bugs; they''re just unintentional extra features"

Kippesoep

Jan 5, 2002 at 7:46 PM

English is for the benefit of other readers who wouldn't understand als ik het in het Nederlands zou zeggen...

Doing a quick test revealed an endless loop, which is caused by something I should have seen before. You calculate the midpoint between two sides like this:

(nBoundingCoords [ b ] - nBoundingCoords [ a ]) / 2;

when it should be this:

(nBoundingCoords [ b ] + nBoundingCoords [ a ]) / 2;

Oh, and just a small hint:

if (a) delete a;

isn't necessary. Deleting a NULL-pointer is a valid operation, so just use

delete a;

Edited by - Kippesoep on January 5, 2002 8:48:10 PM

kamrann

Jan 6, 2002 at 5:47 AM

Just to add something. This won't be anything to do with your stack overflow, which I think Kippesoep has already solved, but it may prevent another problem. Unless all your coordinate values are always positive, I think you might want an abs call in your if statement -

if(abs(..[1] - ..[0]) <= LEAF_SIZE)
...

Cameron

Edited by - kamrann on January 6, 2002 6:49:33 AM

python_regious

103

python_regious

Jan 6, 2002 at 6:24 AM

quote:
Original post by Kippesoep
Deleting a NULL-pointer is a valid operation, so just use
delete a;

Well, it isn''t for me. Whenever I try to delete a pointer thats pointing to memoryspace 0, the program crashes and windows throws an exception error at me.

sprochet

Jan 6, 2002 at 6:43 AM

quote:
Original post by python_regious
[quote]Original post by Kippesoep
Deleting a NULL-pointer is a valid operation, so just use
delete a;

Well, it isn''t for me. Whenever I try to delete a pointer thats pointing to memoryspace 0, the program crashes and windows throws an exception error at me.

yup

Jappie

Author

Jappie

Jan 6, 2002 at 6:50 AM

Thanks a bunch all you people. Haven''t had time to test everything yet, but I''ve already smacked myself on the forehead a couple of times

-----------------------------
Jappie
BabJap Productions

"There''s no such things as bugs; they''re just unintentional extra features"

Kippesoep

Jan 6, 2002 at 1:04 PM

Well, python_regious and sprochet, there are two explanations for this. Either your C++ compiler/library don''t adhere to the standard in this case or you''ve overload the (global) new operator somewhere and forgot to check for a NULL pointer. MSVC does it correctly (for once).

This bit is directly from the C++ standard document:

The required behavior is to accept a value of ptr that is null or that was returned by an earlier call to operator new(size_t).

Jappie

Author

Jappie

Jan 7, 2002 at 1:24 AM

Kippesoep, tried your suggestion, only to find that the stack overflow now occurs even at a LEAF_SIZE of 512. This means performance is now actually worse than before (no offense ofcourse, still grateful for your help). I stripped the node class of it''s boundingcoords info, and tried using a simple variable to trace into the tree. This works perfectly for some reason. I think I''ll just recalculate the entire boundingcoords system next, as the error must lie somewhere inside of it.

-----------------------------
Jappie
BabJap Productions

"There''s no such things as bugs; they''re just unintentional extra features"

python_regious

103

python_regious

Jan 8, 2002 at 10:10 AM

quote:
Original post by Kippesoep
Well, python_regious and sprochet, there are two explanations for this. Either your C++ compiler/library don''t adhere to the standard in this case or you''ve overload the (global) new operator somewhere and forgot to check for a NULL pointer. MSVC does it correctly (for once).

This bit is directly from the C++ standard document:

The required behavior is to accept a value of ptr that is null or that was returned by an earlier call to operator new(size_t).

Well, I''m not overloading the new operator, and I use MSVC++ 6 SP2. So I''m not up to date on service packs for it, would that make a difference?

Death of one is a tragedy, death of a million is just a statistic.

Kippesoep

Jan 8, 2002 at 6:49 PM

I use both MSVC5 and MSVC6/SP3. Both work perfectly.

Have you tried a simple piece of code?

  
int main ()
{
  char *a = new char [100];
  char *b = NULL;
  delete [] a;
  delete [] b;
  return 0;
}

should be enough. If that crashes, then something is seriously wrong...

Kippesoep

Jan 8, 2002 at 7:00 PM

Jappie, I tried again with the - changed to + and it works perfectly for me, even with LEAF_SIZE = 16. What doesn''t work, however, is the destructor of the node class. You haven''t initialised the pointers to NULL, so it tries to delete invalid pointers.

Always do stuff like

  
class node
{
private:
  node *n_TopLeftChild;
  node *n_TopRightChild;
  node *n_BottomLeftChild;
  node *n_BottomRightChild;

public:
  node();
  ~node();

  bool Init(int nBoundingCoords[]);
};

node::node ()
{
  n_TopLeftChild = NULL;
  n_TopRightChild = NULL;
  n_BottomLeftChild = NULL;
  n_BottomRightChild = NULL;
}

And, of course, the same for n_Root in the landscape class.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.