c Valgrind无效的读取大小4 - >分段错误

我想实现一个跳过列表，但我遇到了插入部分的问题。 Valgrind的让我在44排4号的无效读这是这一行：c Valgrind无效的读取大小4 - >分段错误

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

而且这这给它的节点 - > next_pointers [1]。

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];

谢谢！

来源

2013-09-23 Pasha

我看到的off-by-一个错误，你可以找到

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-23 09:53:01 jclin

c Valgrind无效的读取大小4 - >分段错误

回答

相关问题