C рекурсивно сглаживающий нодлист

Question

C рекурсивно сглаживающий нодлист

Я получаю некоторые ошибки памяти C, которые я действительно изо всех сил пытаюсь выяснить. Я довольно новичок в C, и мы используем его в дизайне компиляторов, и мне очень нравится язык, с указателями действительно интересно играть.

Задача, которую я пытаюсь выполнить, - это рекурсивный спуск по дереву и его упрощение, и я застрял в списках.

Список определяется следующим образом: Statement_list -> Statement_list Statement | заявление

Цель состоит в том, чтобы создать узел Statement_List со многими дочерними объектами оператора, выравнивая рекурсивно определенную структуру.

Идея состоит в том, чтобы использовать структуру списка следующим образом: при поиске списка операторов я определяю массив указателей, затем спускаюсь к левому узлу Statement_list до тех пор, пока не останется только один дочерний элемент, затем выделяю массив и заполняю операторы как I восходить. Таким образом, мне придется выделить только один раз. Я надеюсь, что код сделает это немного яснее:

// Takes a list, truncates all list children into a node array
void list_flatten ( Node_t* root, int depth ){
fprintf(stderr, "## List flatten ##\n");

// We allocate a reference to the array
Node_t** array = malloc(sizeof(Node_t**));
int size = 0;

// We start the recursive call
left_flatten( root, 0, &array, &size, depth );

root->children = array;
root->n_children = size;
}


void left_flatten ( Node_t* root, int counter, Node_t*** array_ptr, int* size, int depth ){

// This is for testing
if(outputStage == 4)
    printf( "%*cSimplify %s \n", depth, ' ', root->nodetype.text );

// We increment size 
(*size)++;

// If there is only one child we know we are at the last statement_list, so we extract the statement
if(root->n_children == 1){
    node_t** array  = *array_ptr;
    *array = malloc((*size)*sizeof(Node_t*));
    Node_t* test = root->children[0]->simplify(root->children[0], depth + 1);

    fprintf(stderr, "Adding a %s to index %d\n", root->children[0]->nodetype.text, 0 );
    *(array + 0) = test;
}

// If else we keep descending
else{
    // We make a nother recursive call
    left_flatten( root->children[0], counter + 1, array_ptr, size, depth + 1);

    // The recursive call wil lhave allocated the memory we need
    node_t** array  = *array_ptr;
    int index = *size - counter - 1;

    // We fire off the recursive simplification for the right child
    Node_t* test = root->children[1]->simplify(root->children[1], depth + 1);

    fprintf(stderr, "Adding a %s to index %d\n", root->children[1]->nodetype.text, index );
    *(array + index) = test;
}
}

Он выполнил то, что предполагалось в 28 из 30 программ, которые я пытался проанализировать, столкнувшись с какими-то загадочными ошибками сегментов, поэтому я попытался использовать valgrind, чтобы выяснить, что происходит, и получил журнал ниже:

## List flatten ##
Adding a STATEMENT to index 0
Adding a STATEMENT to index 1
==19604== Invalid write of size 8
==19604==    at 0x406CF8: left_flatten (simplifynodes.c:271)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==    by 0x406C63: left_flatten (simplifynodes.c:261)
==19604==  Address 0x520d5b8 is 0 bytes after a block of size 8 alloc'd
==19604==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==19604==    by 0x406AFD: list_flatten (simplifynodes.c:228)
==19604==    by 0x40691B: simplify_list (simplifynodes.c:176)
==19604==    by 0x4067C5: simplify_function (simplifynodes.c:75)
==19604==    by 0x406A33: left_flatten_null (simplifynodes.c:211)
==19604==    by 0x406964: list_flatten_null (simplifynodes.c:197)
==19604==    by 0x4068F5: simplify_list_with_null (simplifynodes.c:168)
==19604==    by 0x406E21: simplify_children (simplifynodes.c:296)
==19604==    by 0x4065E4: simplify_default (simplifynodes.c:28)
==19604==    by 0x4010BE: main (vslc.c:95)
==19604== 
Adding a STATEMENT to index 2
Adding a STATEMENT to index 3
Adding a STATEMENT to index 4
Adding a STATEMENT to index 5
Adding a STATEMENT to index 6
Adding a STATEMENT to index 7
Adding a STATEMENT to index 8
Adding a STATEMENT to index 9
Adding a STATEMENT to index 10
Adding a STATEMENT to index 11
Adding a STATEMENT to index 12
Adding a STATEMENT to index 13


// Takes a list, truncates all list children into a node array
void list_flatten ( Node_t* root, int depth ){
    fprintf(stderr, "## List flatten ##\n");

    // We allocate a reference to the array
    Node_t** array = malloc(sizeof(Node_t**));
    int size = 0;

    // We start the recursive call
    left_flatten( root, 0, &array, &size, depth );

    root->children = array;
    root->n_children = size;
}


void left_flatten ( Node_t* root, int counter, Node_t*** array_ptr, int* size, int depth ){

    // This is for testing
    if(outputStage == 4)
        printf( "%*cSimplify %s \n", depth, ' ', root->nodetype.text );

    // We increment size 
    (*size)++;

    // If there is only one child we know we are at the last statement_list, so we extract the statement
    if(root->n_children == 1){
        node_t** array  = *array_ptr;
        *array = malloc((*size)*sizeof(Node_t*));
        Node_t* test = root->children[0]->simplify(root->children[0], depth + 1);

        fprintf(stderr, "Adding a %s to index %d\n", root->children[0]->nodetype.text, 0 );
        *(array + 0) = test;
    }

    // If else we keep descending
    else{
        // We make a nother recursive call
        left_flatten( root->children[0], counter + 1, array_ptr, size, depth + 1);

        // The recursive call wil lhave allocated the memory we need
        node_t** array  = *array_ptr;
        int index = *size - counter - 1;

        // We fire off the recursive simplification for the right child
        Node_t* test = root->children[1]->simplify(root->children[1], depth + 1);

        fprintf(stderr, "Adding a %s to index %d\n", root->children[1]->nodetype.text, index );
        *(array + index) = test;
    }
}

Программа также ужасно взрывается, когда я пытаюсь освободить узлы, и я предполагаю, что это связано с основными проблемами с памятью. Первоначально я реализовал это с помощью обычных двойных указателей, но я получил тот же результат.

Я, вероятно, просто переделаю его менее эффективным способом, так как у нас есть крайний срок доставки, и он оценен, но я действительно хочу выяснить, что здесь происходит, поскольку это может добавить некоторую проницательность. Если кому-то понадобится весь код, просто скажите, и я его выложу. PS первый пост, если я нарушаю какой-либо кодекс поведения, дайте мне знать:)

1

c recursion pass-by-reference valgrind dataflow

Источник

user4564307 13 фев '15 в 17:13

0 ответов

Другие вопросы по тегам c recursion pass-by-reference valgrind dataflow