Serious bug in array!

[Vox]

Huh, this one was driving me crazy. I had serious problems, looking what the hell is wrong with my code?

But it is Irrlicht! Here:

Code: Select all

	void push_back(const T& element)
	{
		if (used + 1 > allocated)
			reallocate(used * 2 +1);

		data[used++] = element;
		is_sorted = false;
	}

It is o.k. if element belongs to another array or something else, but what if element belongs to same array?

Input element is pased to function as reference. If there is need for reallocation, element is still referencing to old memory block!

[hybrid]

I'm always a little slow on such kind of C++ errors, but isn't it the case that we still have a handle to the object, and thus the object still exists? It's not a pointer, it's a reference?!
Otherwise, how could one implement such a datat type without always copying objects?

[Vox]

Have you ever seen this?

Code: Select all

{
     Something* param = new Something();

     function(*param);
}

void function(Something& param)
{

}

Pointer converted to reference? Reference is a pointer.

[Electron]

The element passed to the push_back function is indeed a memory location not actual data. But at this point

Code: Select all

data[used++] = element;

that shouldn't matter. The last array slot holds an actual data copy of the memory the element reference pointed to. I don't see a problem.

[Vox]

If you don't see it, it doesn't mean that it doesn't exists.

Element is copied, but after reallocation. Value is taken from the memory where element is referenced.

Please do following, and tell me what last element will be:

Code: Select all

  array<s32> data;
  data.push_back(0);
  data.push_back(1);
  data.push_back(2);

  data.push_back(data[0]);

Now, if last push_back needs reallocation (I don' know if really needs it, use push_backs until last push_back will cause reallocation), data[used++] will push data stored in last allocated memory before reallocation. If you think that 0 value will be assigned to last element, you are probably wrong. In my case, it doesn't because reallocated memory is overwriting old memory block.

One solution for this problem could be:

Code: Select all

   void push_back(const T& element)
   {
      if (used + 1 > allocated)
      {
         T e = element; // element should be copied first
         reallocate(used * 2 +1);
         data[used++] = e;
         is_sorted = false;
         return;
     }

      data[used++] = element;
      is_sorted = false;
   }

[Vox]

Temporary solution for this problem in my code (not real code, just example above):

Code: Select all

  array<s32> data;
  data.push_back(0);
  data.push_back(1);
  data.push_back(2);

  s32 value = data[0]:
  data.push_back(value);

[Electron]

Oh, now I see your point. Sorry I missed it earlier. Probably the array method should be changed to pass by value. 90% of the time I use arrays of 4-byte elements so its not as though passing by reference really saves any time.

[Vox]

Probably. But using reference is faster, much faster when using objects. I would prefer to copy object only before reallocation.

Another way is to put reallocation after assignment. But then again, it could happen that memory usage will be doubled unnecessary.

[hybrid]

Have you ever seen this?

Code: Select all

{
     Something* param = new Something();
     function(*param);
}

void function(Something& param)
{
}

Pointer converted to reference? Reference is a pointer.

Now, I don't see any pointer converted here
You're passing an object to function which will be passed by reference, though. Remember that Something *param and *param are different things. First declares a pointer, second gets the object the pointer points to (commonly called dereferencing, but this would make it even worse now )
So indeed both pointer and reference link to the same address as Electron mentioned, but pointers are in no way references nor is it vice versa.
One important point to references is that they can't be NULL (read the C++ reference for this one), but apparently this does not help if somewhere the destructor is called.
BTW: STL also has lots of these reference pitfalls. They have a warning with most container classes that references are only valid until next reallocation, so I should have known before

[hybrid]

Probably. But using reference is faster, much faster when using objects. I would prefer to copy object only before reallocation.

Another way is to put reallocation after assignment. But then again, it could happen that memory usage will be doubled unnecessary.

The first version would however introduce unnecessary overhead for all objects which are not part of the array themselves. The second version won't introduce that much wasted memory, should be only one array element on the average. And it's much more elegant in that it needs no special case to check.

[Vox]

Hybrid, you must be kidding me

This topic is about bug report, not about advanced C++ knowledge.

But if you want to, we can discuss it.

So indeed both pointer and reference link to the same address as Electron mentioned, but pointers are in no way references nor is it vice versa.
One important point to references is that they can't be NULL (read the C++ reference for this one), but apparently this does not help if somewhere the destructor is called.

Now please execute this code, and tell me what you will got (and why)?

Code: Select all

#include <iostream>
using namespace std;

class Something
{
public:
    int test;
    Something() { test = 0; }
};

void function(Something& param)
{ 
   param.test = 1;
}

int main()
{
     Something* param = NULL;
     function(*param);
     
     cout << param->test << endl;

     return 0;
}

[hybrid]

Now please execute this code, and tell me what you will got (and why)?

Code: Select all

void function(Something& param)
{ 
   param.test = 1;
}

int main()
{
     Something* param = NULL;
     function(*param);     
}

(I stripped the unnecessary parts from the quote)
So the program core dumps due to NULL dereferencing. But you're not passing a pointer to function!?
But I guess you wanted to have a reference with NULL? I did not find the official quote right now, but here is a similar one from some C++ introduction:

Appearances aside, const pointers differ from references in one subtle but significant way. A valid reference must refer to an object; a pointer need not. A pointer, even a const pointer, can have a null value. A null pointer doesn't point to anything.

So it might be the problem of using pointers in your code. Is the same example still possible without pointer handling or similar?
But hey, you already won with your bug report - was my fault! So why not going back to fixing it?

[Vox]

So the program core dumps due to NULL dereferencing. But you're not passing a pointer to function!?

Exactly. We are pasing memory address. In this case reference is NULL because address is taken from pointer.

It is big difference between:

One important point to references is that they can't be NULL (read the C++ reference for this one)

and

Appearances aside, const pointers differ from references in one subtle but significant way. A valid reference must refer to an object; a pointer need not.

Valid reference will contain valid address. Invalid will have NULL.

[jox]

I think Vox is right. To push back elements from the same array is probably not such a common practice, but it should be considered a valid procedure so it is a bug in my opinion. To copy the element before reallocation (as proposed by Vox) would be a solution.

Another thing that could be considered a bug is, that core::array is not self-assignment save. So if you do something like this:

Code: Select all

core::array<s32> data;

data.push_back(0);
data.push_back(1);
data.push_back(2);

data = data;

// data is corrupt here

you have a problem, because the assignment operator does not check if the other array is the same as the one that gets assigned. And so it gets deleted before copied.

[Electron]

My knowledge of exactly what makes faster code isn't wonderful, but if you're going to make a temporary copy of new the element before reallocation then it should be faster to just pass by value,except of course in situation where reallocation isn't needed. So I'm not sure what the most efficient solution would be.