Случайный Segfault при перестановке двусвязного списка - PullRequest
Новая
       20

Случайный Segfault при перестановке двусвязного списка

0 голосов
/ 05 мая 2019

Извините, если кому-то это может показаться тривиальным, но за прошедший день я не могу понять, из-за чего произошла эта ошибка. У меня есть массив двусвязных списков, в которых я поддерживаю определенный порядок. Каждый раз, когда к узлу в списке обращаются или обновляют, он перемещается в начало списка, и это происходит в каждом связанном списке в массиве. Я предоставлю код того, как я инициализирую массив связанных списков и как я организую заказ. Любая помощь приветствуется. Если это помогает, массив двусвязных списков предназначен для имитации кэша. Я просто надеюсь, что это что-то явно очевидное, так как я немного новичок в malloc и C. Впервые использую этот сайт, поэтому, пожалуйста, дайте мне знать, если я не соблюдаю соглашение или делаю что-то не так с моим постом

Я попытался распечатать структуру массива связанных списков, и он, кажется, всегда структурно обоснован. Segfault происходит только при перестановке узлов, особенно когда я пытаюсь получить доступ к Node-> prev-> next. Не только это, это происходит, когда я обновляю хвостовой узел специально 

void maintainLRU(cacheBlock* ptr, int index)//rearranges a list with node passed in to be head
{
    if(ptr->next == NULL)//Tail
    {
        ptr->next = cache[index].head;
        cache[index].head = ptr;
        cache[index].tail = ptr->prev;
        ptr->prev->next = NULL;
        ptr->prev = NULL;
    }
    else
    {
        ptr->prev->next = ptr->next;
        ptr->next = cache[index].head;
        cache[index].head = ptr;
        ptr->prev->next = NULL;
        ptr->prev = NULL;
    }
}

//following code exists within main and is how i initialize the'cache'
numLines = cacheSize/(blockSize*assocType); //determines number of linked lists in my array. 
cache = malloc(sizeof(cacheLine)*numLines);
for(int i = 0; i < numLines; i++)
{
        cacheBlock* temp = malloc(sizeof(cacheBlock));
        temp->valid = 0; //whether the node holds data yet or not
        cache[i].head = temp;
        for(int j = 1; j < assocType; j++)//assoctype is just how many nodes in the list
        {
            temp->next = malloc(sizeof(cacheBlock));
            temp->next->prev = temp;
            temp->next->valid = 0;
            temp = temp->next;
        }
        cache[i].tail = temp;
}//cacheblock is just a node with next, prev, and a valid bit
//cacheLine is just a struct with a pointer to a headnode
//the maintain order function is explicitly called only if the node updated or accessed is not the head.```

1 Ответ

1 голос
/ 05 мая 2019

case 1: ptr находится в конце списка вы удаляете себя должным образом, ставите себя во главе списка, но не заставляете «старый» заголовок списков указывать на вас; значит, ваш список поврежден.

case 2: ptr не находится в конце списка Вы указываете свой предыдущий на следующий, но не указываете свой предыдущий на предыдущий, поэтому ваш список поврежден.

все случаи: вы должны предоставить достаточно программы, чтобы кто-то мог ее скомпилировать и попробовать. Частично это заставит вас проанализировать свою работу достаточно, чтобы заметить очевидные ошибки. Тонкие - это то, для чего предназначен этот форум.

3 десятилетия назад очень важно было тщательно оптимизировать операции со связанными списками; в то время ботаники компилятора настолько улучшили свою игру, что вы сможете написать keepLRU как: 

void maintainLRU(cacheBlock* ptr, int index) {
    list_remove(&cache[index], ptr);
    list_insert_before(&cache[index], cache[index].head, ptr);
}

так что вы не станете жертвой простых ошибок.

...