I am writing a program on binary trees.

To initialize the tree, I made a separate procedure, but when I call it, a very strange error appears.

In the code, the procedure is called initTree. The essence of the error is that after it works, the text in the console cannot be displayed normally, writes an error (also to the console):

Untitled^ malloc.c:2403: sysmalloc: Assertation '(old_top == initial_top (av) && old_size == 0) || ((unsigned long (old_size) >= MINSIZE && prev_inus (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed

Also, if I run the debugger, qtCreator tells me about the SIGABRT error.

I experimentally found out that if you add the output of any text to the beginning of this procedure, then this text itself is not displayed, but in the future the error does not manifest itself and the output works fine.

I tested it with both <cstdio> and <iostream> , the result was exactly the same.

Without this procedure, the error does not appear either.

Here is the program code:

 #include <iostream> #include <cstdio> using namespace std; void preparationToCreateTree(int &n, int &posA); void initTree(int &n, int &posA, int tree[], int numTree[], int &posZ); int main() { int posA = 1, posZ; int n; preparationToCreateTree(n, posA); int *numTree = new int[posA + n + 3 + 1]; int *tree = new int[n + 1]; initTree(n, posA, tree, numTree, posZ); cout << "TESTED" << endl; //Без строки ниже тут выкидывает ошибку return 0; } void preparationToCreateTree(int &n, int &posA) { cin >> n; while(posA < n) posA *= 2; } void initTree(int &n, int &posA, int tree[], int numTree[] , int &posZ) { cout << "Ahh.. Touch me, senpai!!"; //Без этой строки появляется ошибка tree[0] = -1; for(int i = 1; i <= posA + n + 3 + 1 - 1; i++) tree[i] = 0; for(int i = 1; i <= n; i++) cin >> tree[i]; for(int i = 1; i <= n; i++) numTree[posA + i - 1] = i; if(n % 2 != 0) n++, tree[posA + n - 1] = 0; if((n / 2) % 2 != 0) n += 2, tree[posA + n - 1] = 0, tree[posA + n - 2] = 0; posZ = posA + n - 1; }

I am writing on archlinux. I use gxx compilers

    4 answers 4

    Your program has an undefined behavior, as there is an attempt to go beyond the allocated memory for arrays.

    In this offer

     int *tree = new int[n + 1];

    allocated memory for n + 1 objects of type int

    However, already in this cycle

     for(int i = 1; i <= posA + n + 3 + 1 - 1; i++) tree[i] = 0;

    there is an appeal to elements whose index is clearly greater than n in view of the condition

     i <= posA + n + 3 + 1 - 1

    which is easier to write as

     i <= posA + n + 3

    In addition, inside the function, the value of the variable n increases even more, and the memory for the array is not redistributed.

     if(n % 2 != 0) n++, tree[posA + n - 1] = 0; ^^^^ if((n / 2) % 2 != 0) n += 2, tree[posA + n - 1] = 0, tree[posA + n - 2] = 0; ^^^^^^

    Pay attention to the style of writing code. It's hard to understand what your program does.

    Try to declare the functions in such a way that they perform one action. For example, in the preparationToCreateTree function, input of the value n should be transferred to another function or to the main code main . As a result, the function can be simplified and not use links.

     int preparationToCreateTree( int n ) { int posA = 1; while( posA < n ) posA *= 2; return posA; }

    In addition, there are questions whether posA calculated posA . Should its final value be less than or equal to n , or is it the closest value from above.

    • posA is calculated absolutely correctly, I give a tooth)) At the expense of the variable n: Do I need to redistribute the memory after that? I after all initially selected cells in an array on 3 more than it is necessary. It remains to reset. The style is really awful, I just didn’t bother with that much, because The task is submitted to the site - witaway
    • @ EgorLevonenko Initially, you allocated memory for n + 1 elements: int * tree = new int [n + 1]; - Vlad from Moscow
    • And the whole thing was that I just mixed up two arrays. In that cycle, you need to change numTree. After that, the garbage with the output disappeared)) - witaway

    No wonder, you have memory errors, because you write beyond the limits of allocated memory. You have posA equal to the first power of two MORE n, and under the tree allocated (n + 1) elements. What do you think, where will the for(int i = 1; i <= posA + n + 3 + 1 - 1; i++) loop go for(int i = 1; i <= posA + n + 3 + 1 - 1; i++) ?

    • But where does the I / O error come from? And why does one line fix everything? - witaway
    • Well, this is the nature of errors with writing to unallocated areas - sometimes they are visible, sometimes not, depending on very many conditions (data composition in memory, etc.). It is possible that the constant that you derive gives an extra supply of "not critical" memory damage. I can't say for sure, of course - it is necessary to analyze the disassembled code. - Vladimir Pavluk 7:27
     int *tree = new int[n + 1]; /* ... */ for(int i = 1; i <= posA + n + 3 + 1 - 1; i++) tree[i] = 0;

    How much memory is allocated for a tree and how much data is written into it?

    And why does one line fix everything?

    It does not fix anything. When the memory of the program is blocked, anything can happen. Another line in the output, another action, launching the program from another directory, a certain system time - all this can mask the error, and maybe format the hard drive, after deleting all your accounts from social networks.

    See " Undefined Behavior ".

    • In other words, I crookedly working with memory received a number of coincidences, because of what the output stopped working normally? - witaway
    • @ YegorLevonenko, a little bit wrong :) The normal code stopped working due to memory errors, and that after some additional error actions it was not visible - this is just a coincidence. - PinkTux
    • Now it became clear that that crutch was not quite a working thing. It is necessary to correct)) - witaway

    I experimentally found out that if you add the output of any text to the beginning of this procedure, then this text itself is not displayed, but in the future the error does not manifest itself and the output works fine.

    As soon as you encounter such behavior - or when changes in one place suddenly entail a change in behavior in a completely different place, or when the program works under a debugger, and without - no - 95% (the estimate is inaccurate, maybe more :) ) that you are spoiling the memory somewhere! Write abroad, delete the uninstalled or delete twice, allocate a small buffer - in a word, recheck work with memory!

    • This is not the first time I've been failing at work with memory. In principle, in this task I could manage without dynamics. But now I know what the "Undefined behavior" looks like :) - witaway
    • @ YegorLevonenko, why did you tell me about valgrind and its analogs? - PinkTux
    • I could not even think that there were problems with working with memory - witaway
    • @ YegorLevonenko, and there’s no need to think about it :) Running the program through valgrind is just part of the development process. And if he cursed, then we must stop and look for the error, and not continue to code. - PinkTux
    • I thought that in simple algorithms problems I would not have such cases when I had to touch valgrind - witaway