0

I was trying to solve the following LeetCode question in C: https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

I want to maintain a static array of pointers to the yet unconnected TreeNodes in the tail of each row in the given perfect binary tree so that I can use it and update it while traversing the tree in-order. For this, I need the tree height. I can use the problem constraints to find an upper bound for it, 12, which is good enough. However, I was aiming at a more general solution in which I can also practice dynamic memory allocation.

I came up with the following attempt (which was accepted):

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *left;
 *     struct Node *right;
 *     struct Node *next;
 * };
 */

int curr_height = 0;
int height = 0;
int have_height = 0;

struct Node ** ptr_to_table = NULL;

void allocate_direct_table(){
    int SIZE = height + 9;
    ptr_to_table = calloc(SIZE, sizeof(struct Node *));

    struct Node * arr[SIZE];
    for(int i=0; i<SIZE; i++){
        arr[i] = NULL;
    }

    *ptr_to_table = arr;

    
    // ptr_to_table = malloc((height + 1) * sizeof(struct Node *));
    // memset(ptr_to_table, 0, (height + 1) * sizeof(struct Node *));
}

void process(struct Node* root){
    int index = curr_height;
    if(ptr_to_table[index]){
        ptr_to_table[index] -> next = root;
    }
    ptr_to_table[index] = root;
    root -> next = NULL;
}

void preprocess(){
    height = curr_height;
    allocate_direct_table();
}

struct Node* connect(struct Node* root) {
    if(!root && !have_height){
        preprocess();
        have_height = 1;
        return NULL;
    }
    if(!root) return NULL;

    curr_height ++;
    connect(root -> left);
    curr_height --;

    process(root);

    curr_height ++;
    connect(root -> right);
    curr_height --;

    return root;
    
}

I found a behavior of this code that I could not explain. It involves the dynamic memory allocation in the allocate_direct_table() function:

  1. When debugging, I can use SIZE = height, and everything works.
  2. When submitting, I get an AddressSanitizer: heap-buffer-overflow error, so I have to increase the height. I have no idea why, and I have no idea why 9 is enough. It probably has to do with the problem constraints, which means my solution is not general.

Here is the error when submitting the version with SIZE = height:

Problematic input:

[-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13]

Runtime Error:

=================================================================
==30==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x603000000178 at pc 0x55979bc921c2 bp 0x7ffd997833a0 sp 0x7ffd99783390
READ of size 8 at 0x603000000178 thread T0
    #5 0x7f179e0460b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x603000000178 is located 0 bytes to the right of 24-byte region [0x603000000160,0x603000000178)
allocated by thread T0 here:
    #0 0x7f179ec8bdc6 in calloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10ddc6)
    #7 0x7f179e0460b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c067fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff8000: fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00
  0x0c067fff8010: 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa
=>0x0c067fff8020: 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00 00[fa]
  0x0c067fff8030: fa fa 00 00 06 fa fa fa 00 00 00 00 fa fa 00 00
  0x0c067fff8040: 00 fa fa fa 00 00 00 fa fa fa 00 00 00 00 fa fa
  0x0c067fff8050: 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00
  0x0c067fff8060: fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00
  0x0c067fff8070: 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==30==ABORTING

Questions:

  1. Why does SIZE = height not work in debug mode?
  2. Why is it 9 or more that I need to add?

Any help is much appreciated!

Update 1:

I had a mistake in my allocator function. Here's a fix:

void allocate_direct_table(){
    int SIZE = height;
    ptr_to_table = calloc(SIZE, sizeof(struct Node *));

    for(int i=0; i<SIZE; i++){
        ptr_to_table[i] = NULL;
    }
}

The same questions remain.

Update 2:

Rewrote the code following suggestions from the comments.

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *left;
 *     struct Node *right;
 *     struct Node *next;
 * };
 */

struct Node ** ptr_to_table = NULL;
int have_height = 0;

struct Node ** allocate_direct_table(int height){
    struct Node ** tmp = malloc(height * sizeof(struct Node *));
    for(int i=0; i<height; i++){
        tmp[i] = NULL;
    }

    return tmp;
}

void process(struct Node* root, int curr_height){
    int index = curr_height;
    if(ptr_to_table[index]){
        ptr_to_table[index] -> next = root;
    }
    ptr_to_table[index] = root;
    root -> next = NULL;
}

struct Node * helper(struct Node * root, int curr_height){
    if(!root && !have_height){
        ptr_to_table = allocate_direct_table(curr_height+9);
        have_height = 1;
        return NULL;
    }
    if(!root) return NULL;

    curr_height ++;
    helper(root -> left, curr_height);
    curr_height --;

    process(root, curr_height);

    curr_height ++;
    helper(root -> right, curr_height);
    curr_height --;

    return root;
}

struct Node* connect(struct Node* root) {
    return helper(root, 0);
    
}

I still have no idea why +9 is needed for allocation.

Louie_the_unsolver
  • 45
  • 5
  • 1
    The assignment `*ptr_to_table = arr` is equal to `ptr_to_table[0] = &arr[0]`. Besides being sematically wrong in itself (because mismatching types), you make `*ptr_to_table` point to that element, which will vanish as soon as the function returns. The pointer really will become invalid. Any attempt to use `ptr_to_table[0]` after that point is going to lead to undefined behavior. And there's no more elements in your "array" `ptr_to_table` either. – Some programmer dude Nov 06 '22 at 17:06
  • 1
    And I'm sorry for the assumption, but you really have made some rather grave mistakes in your code, so please take a step back and refresh the chapters on pointers, variable scope, and variable life-time. – Some programmer dude Nov 06 '22 at 17:07
  • 1
    We've established that (a) your code is incorrect, even though (b) one compiler (leetcode's) seems to have accepted it. But it's important to understand: Are you asking about this situation because (1) you're curious to learn how it's possible that, even though the code is incorrect, one compiler somehow managed to do the right thing with it? Or, (2) You suspect that, since one compiler did the right thing with it, the code really *is* okay, and the other compiler was wrong to reject it? – Steve Summit Nov 06 '22 at 17:11
  • "init and assign" are also discussed here: https://stackoverflow.com/questions/74331760/bridging-struct-initializations-on-the-heap-when-using-dynamically-allocated-me/74332021#74332021 – Louie_the_unsolver Nov 06 '22 at 17:12
  • I don't understand what you guys say: This code works in debug mode in LeetCode. Are you saying the compiler there is malfunctioning? Seriously? – Louie_the_unsolver Nov 06 '22 at 17:14
  • We are saying: the code seems to work, even though it is WRONG. – Steve Summit Nov 06 '22 at 17:17
  • You were disappointed when SomeProgrammerDude seemed to have failed to read, before commenting. So please read our words when we say: that line `*ptr_to_table = arr;` is completely broken, on a couple of different levels. It's a miracle it could ever work. – Steve Summit Nov 06 '22 at 17:19
  • If there is some undefined behaviour, the code can behave differently in debug mode. – Weather Vane Nov 06 '22 at 17:19
  • 1
    If a compiler processes a program containing undefined behavior, and produces a program that does something, and if the thing that it does seems to match the programmer's intent, that does not count as "malfunctioning". That's because "undefined behavior" means a program can do *anything*. It's allowed to give an error. It's allowed to do what you expected. It's allowed to do something completely different or unexpected. – Steve Summit Nov 06 '22 at 17:23
  • In any case, thank you for answering. – Louie_the_unsolver Nov 06 '22 at 17:23
  • 3
    (continued) Nevertheless, given the declarations in your code, I do believe (seriously) that if a compiler does not issue a diagnostic for the line `*ptr_to_table = arr;`, the compiler is malfunctioning. – Steve Summit Nov 06 '22 at 17:23
  • ...cont'd. It can be particularly tricky if the faulty code doesn't *directly* cause a segfault, but corrupts something apparently unrelated, and *that* causes a segfault in a place different to where the bug was. In debug mode, memory usage isn't the same, and perhaps the corruption is now benign. – Weather Vane Nov 06 '22 at 17:26
  • I tried to fix the allocation function (feel free to correct me. I am not experienced in C). It still works in debug mode and not when submitting. Same reason. – Louie_the_unsolver Nov 06 '22 at 17:39
  • @Someprogrammerdude : Your comment about mismatched types is correct. Thank you. – Louie_the_unsolver Nov 06 '22 at 17:42
  • @SteveSummit, I wouldn't call my comment pride: I know I am utterly clueless about C, and I am posting questions about it here because I know there are experts here who are nice enough to share their knowledge. But I also know I am doing a lot to improve, which includes reading books and official docs, doing exercises and analyzing problems with solutions. Some of these problems are on LeetCode. Hearing that I am clueless, while accurate, is draining. Thank you for joining the discussion, and if you have a better suggestion for where I can practice for code interviews in C, I am all ears. – Louie_the_unsolver Nov 06 '22 at 17:52

1 Answers1

0

Drop the use of arr completely, including its initialization loop. All you really need is that calloc call:

void allocate_direct_table(){
    ptr_to_table = calloc(height + 9, sizeof(struct Node *));
}

After you call allocate_direct_table() you have the variable ptr_to_table which you can use as an array of pointers to Node.

Next step is to remove your use of global variables, and pass values as needed to the functions as arguments. And rework the allocate_direct_table function to return the array.

I also recommend you take some time to think about why you need size + 9 in the allocation. I don't think that should be needed in a working program.

Some programmer dude
  • 400,186
  • 35
  • 402
  • 621