2

我正在尝试实现一个跳过列表，但我遇到了插入部分的问题。Valgrind 在第 44 行给了我无效的 4 读取，即这一行：

while(node->next_pointers[i] != NULL && node->next_pointers[i]->value < value)

正是 node->next_pointers[i] 给出了它。

void insert_to_skip_list(SkipList *skip_list, int value) {
SkipListNode* updated[skip_list->max_level + 1];
SkipListNode* node = skip_list->header;
int i;
for(i = skip_list->max_level;i >=0; i--) {
    while(node->next_pointers[i] != NULL && node->next_pointers[i]->value < value) {
        node = node->next_pointers[i];
    }
    updated[i] = node;
}
node = node->next_pointers[0];
if(node->value == value) {
    return;
}else {
    int level = decide_level(skip_list->max_level);
    if(level > skip_list->max_level) {
        level = skip_list->max_level + 1;
        skip_list->max_level = level;
        updated[level] = skip_list->header;
    }
    node->levels = level;
    node->value = value;
    for(i = 0; i <= skip_list->max_level; i++) {
        node->next_pointers[i] = updated[i]->next_pointers[i];
        updated[i]->next_pointers[i] = node;
    }
}
}

这是我的结构：

typedef struct skiplistNode {
    int value;
    int levels;
    struct skiplistNode **next_pointers;
    struct skiplistNode **prev_pointers;
} SkipListNode;

typedef struct {
   int max_level;
   SkipListNode *header;
} SkipList;

这是我得到的 valgrind 跟踪：

==5746== Invalid read of size 4
==5746==    at 0x804B56D: insert_to_skip_list (skiplist.c:44)
==5746==    by 0x404A7DA: srunner_run (check_run.c:396)
==5746==    by 0x404A892: srunner_run_all (check_run.c:587)
==5746==  Address 0x4256c34 is 0 bytes after a block of size 12 alloc'd
==5746==    at 0x402CE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==5746==    by 0x404A7DA: srunner_run (check_run.c:396)
==5746==    by 0x404A892: srunner_run_all (check_run.c:587)
==5746== Invalid read of size 4
==5746==    at 0x804B5AE: insert_to_skip_list (skiplist.c:50)
==5746==    by 0x404A7DA: srunner_run (check_run.c:396)
==5746==    by 0x404A892: srunner_run_all (check_run.c:587)
==5746==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==5746==
==5746==
==5746== Process terminating with default action of signal 11 (SIGSEGV)
==5746==  Access not within mapped region at address 0x0
==5746==    at 0x804B5AE: insert_to_skip_list (skiplist.c:50)
==5746==    by 0x404A7DA: srunner_run (check_run.c:396)
==5746==    by 0x404A892: srunner_run_all (check_run.c:587)
==5746==  If you believe this happened as a result of a stack
==5746==  overflow in your program's main thread (unlikely but
==5746==  possible), you can try to increase the size of the
==5746==  main thread stack using the --main-stacksize= flag.
==5746==  The main thread stack size used in this run was 8388608.
==5746==
==5746== HEAP SUMMARY:
==5746==     in use at exit: 3,542 bytes in 196 blocks
==5746==   total heap usage: 260 allocs, 64 frees, 39,914 bytes allocated
==5746==
==5746== LEAK SUMMARY:
==5746==    definitely lost: 12 bytes in 1 blocks
==5746==    indirectly lost: 0 bytes in 0 blocks
==5746==      possibly lost: 0 bytes in 0 blocks
==5746==    still reachable: 3,530 bytes in 195 blocks
==5746==         suppressed: 0 bytes in 0 blocks
==5746== Rerun with --leak-check=full to see details of leaked memory
==5746==
==5746== For counts of detected and suppressed errors, rerun with: -v
==5746== Use --track-origins=yes to see where uninitialised values come from
==5746== ERROR SUMMARY: 6 errors from 3 contexts (suppressed: 0 from 0)

编辑 感谢 jlcin 我挺身而出，但我现在仍然遇到这个问题。

现在的代码是：

SkipListNode* updated[skip_list->max_level + 1];
SkipListNode* node = skip_list->header;
int i;
for(i = skip_list->max_level - 1; i >=0; i--) {
    while(node->next_pointers[i] != NULL && value > node->next_pointers[i]->value) {
        node = node->next_pointers[i];
    }
    updated[i] = node;
}
if(node->next_pointers[0] != NULL && node->next_pointers[0]->value == value) {
    return;
}else {
    int level = decide_level(skip_list->max_level);
    if(level > skip_list->max_level) {
        level = skip_list->max_level + 1;
        skip_list->max_level = level;
        updated[level] = skip_list->header;
    }
    for(i = skip_list->max_level -1; i >=0; i--) {
        node->next_pointers[i] = updated[i]->next_pointers[i];
        updated[i]->next_pointers[i] = node;
    }
}

和 valgrind：

==8844== Invalid write of size 4   ==8844==    at 0x804B6D8: insert_to_skip_list (skiplist.c:59)

那条线是：

node->next_pointers[i] = updated[i]->next_pointers[i];

再次感谢！

4

1 回答 1

4

我看到了一个错误，你可以找到

SkipListNode* updated[skip_list->max_level + 1];

和

int level = decide_level(skip_list->max_level);
if(level > skip_list->max_level) {
    level = skip_list->max_level + 1;
    skip_list->max_level = level;
    updated[level] = skip_list->header;
}

在声明中，updated数组只有 0 来max_level索引，并且完全有max_level+1元素。但是在代码level = skip_list->max_level + 1;中， 的值level是max_level+1，这是数组的错误索引。

而且我不知道 的确切含义skip_list->max_level。它是最大索引还是最大大小next_pointers？

for(i = skip_list->max_level;i >=0; i--)
    while(node->next_pointers[i]

如果它是最大大小，则意味着 next_pointers 只有索引 0 到max_level-1，因此，我认为next_pointers[i]哪里i = skip_list->max_level是错误的索引。

以及第 50 行的错误

49 node = node->next_pointers[0];
50 if(node->value == value)

node指针为 NULL 并且尝试获取(NULL)->value无效并导致段错误。

于 2013-09-23T09:53:01.563 回答