一个Segfaulting Skip List，一个毁了的周末（C编程）

Question

我是一名 CS 学生，我的万圣节周末刚刚被我无法调试的编程作业毁了。这可能是这里没有立即标记的少数几个问题之一 "duplicate."

分配是一个 "Skip List," 或单链表（用 C 编程），其中每个节点都有一个可变大小的指针数组，由随机 "coin" 抛掷决定。 3 次成功的投掷导致高度为 3，依此类推。每个数组然后链接到相似高度的其他数组 - 第七层链接到下一个第七层，第六层链接到下一个第六层，一直向下到第一层，或数组元素0，自然链接到列表中的下一个项目。

由于大多数项目没有更高级别，因此这是一种在 log(n) 时间内搜索的好方法，而不是简单的 n。它的插入、删除和搜索速度显着加快，但代价是内存成本更高。这只是理论 - 这是一张图片：Skip List

你们中的许多人已经知道这些东西，但我只是想稍微解释一下，并表明我确实理解这里发生的事情的基础知识。

问题是一个随机段错误，它通过 "CODE 6 - ABORT" 消息搞砸了所有提供的测试。当我运行我的主文件时，我在代码中的指示位置随机出现段错误 (<-----Segfaults) - 它发生在大约一半的时间，并且可以在任何一行。测试也给了我很多 "bad pointer" 和 "minmap chunk error" 消息。

我对此束手无策。我在 class 中有 93 分，但如果我不能完成这件可恶的事情，我的分数会下降到 87 分。

感谢任何帮助，代码如下：

定义

typedef int data_t;

typedef struct skip_node {
    data_t data;
    size_t height;
    struct skip_node **next;
} skip_node_t;

typedef struct skip_set {
    skip_node_t *head;
    size_t max_height;
    size_t size;
} skip_set_t;

导致随机错误的主要方法

skip_set_t set;
skip_set_init(&set);
skip_set_add(&set, 4);
skip_set_add(&set, 3);
skip_set_clear(&set);
skip_set_t set2;
skip_set_init(&set2);
skip_set_add(&set2, 1); //faults here

...最后是恶魔的数据结构：

    #include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "skip_set.h"

/***********************
        PART 1
***********************/

//Initialize
void skip_set_init(skip_set_t *set)
{
   //Set
   set->size = 0;
   set->max_height = 1;
   set->head = malloc(sizeof(skip_node_t));

   //Sentinel
   set->head->data = 0; 
   set->head->height = set->max_height;
   set->head->next = malloc(sizeof(skip_node_t*) * set->max_height); 
}

//Clear
void skip_set_clear(skip_set_t *set)
{   
   if (set->head == NULL)
      return;

   skip_node_t* this;
   skip_node_t* nex;
   this = set->head->next[0];
   while(this != NULL)
   {
      nex = this->next[0];
      free(this->next);
      this->next = NULL;
      free(this);
      this = nex;
   } 
   set->size = 0;

   for (int ii = 0; ii < set->max_height; ii++)
      set->head->next[ii] = NULL; 
}

//Size
size_t skip_set_size(skip_set_t *set)
{
   return set->size;
}

//Free
void skip_set_free(skip_set_t *set)
{
   skip_set_clear(set);

   free(set->head->next);
   set->head->next = NULL;

   free(set->head);
   set->head = NULL;
}

//Add
void skip_set_add(skip_set_t *set, data_t value)
{
   printf("Add Start\n");
   if (skip_set_contains(set, value))
      return;

   int new_height = 1;    

   while(rand() % 2 == 0)
   {
      new_height++;
   }
   printf("Add One\n");
   if (set->max_height < new_height)
   {
      skip_node_t** arr = malloc(sizeof(skip_node_t*) * new_height);

      for (int ii = 0; ii < set->max_height; ii++)
         arr[ii] = set->head->next[ii];

      for (int jj = set->max_height; jj < new_height; jj++)
         arr[jj] = NULL; 
      printf("Add Two\n");
      free(set->head->next);
      set->head->next = NULL;  
      set->head->next = arr;
      set->max_height = new_height;
      set->head->height = new_height; 
      printf("Add Three\n");  
   } 

   skip_node_t* new_node = (skip_node_t*)malloc(sizeof(skip_node_t));

   skip_node_t** arr = calloc(new_height, sizeof(skip_node_t*));
   new_node->next = arr;
   new_node->height = new_height;
   new_node->data = value;

   skip_node_t* cur_node = set->head; 
   int cur_level = set->max_height - 1; 
   printf("Add Four\n");
   while (cur_level >= 0)
   {
      printf("ABreak 1\n");
      while ((cur_node->next[cur_level] != NULL) && (cur_node->next[cur_level]->data < value))//<-----Segfaults
      {
         printf("ABreak 2\n");
         cur_node = cur_node->next[cur_level];
         printf("ABreak 3\n");
      }
      printf("ABreak 4\n");
      if (cur_level < new_height)
      {
         printf("ABreak 5\n");
         new_node->next[cur_level] = cur_node->next[cur_level];
         cur_node->next[cur_level] = new_node;
         printf("ABreak 6\n");
      }
      printf("ABreak 7\n");
      cur_level--;       
   }

   set->size++;
   printf("Add End\n");   
}

//Remove
void skip_set_remove(skip_set_t *set, data_t value)
{
   printf("Remove Start\n");
   if (!skip_set_contains(set, value))
      return;

   skip_node_t* tbf;
   skip_node_t* cur_node = set->head;

   int cur_level = set->max_height - 1;
   printf("Remove 1\n");
   while (cur_level >= 0)
   {
      while ((cur_node->next[cur_level] != NULL) && (cur_node->next[cur_level]->data < value))
      {
         cur_node = cur_node->next[cur_level];
      }

      if ((cur_node->next[cur_level] != NULL) && (cur_node->next[cur_level]->data == value))
      {
         tbf = cur_node->next[0];
         cur_node->next[cur_level] = cur_node->next[cur_level]->next[cur_level];
         if (cur_node == NULL && cur_node->next[cur_level] == NULL)
            set->max_height--;
      }      
      cur_level--;       
   }
   printf("Remove 2\n");
   free(tbf->next);
   printf("Remove 3\n");
   free(tbf);
   set->size--;   
   printf("Remove End\n");
}

//Pop
data_t skip_set_pop(skip_set_t *set)
{
   printf("Pop Start\n");
   data_t lazyCSstudent = set->head->next[0]->data;
   skip_set_remove(set, lazyCSstudent);
   printf("Pop End\n");
   return lazyCSstudent;
}

//Contains
bool skip_set_contains(skip_set_t *set, data_t value)
{ 
   printf("Contains Start\n");
   skip_node_t* this = set->head;
   int i = set->max_height - 1;
   printf("Contains Mid\n");
   while(i >= 0)
   {
      printf("CBreak One\n");
      while((this->next[i] != NULL) && (this->next[i]->data < value)) ///<-----Segfaults
      {
         printf("CBreak Two\n");
         this = this->next[i];
         printf("CBreak Three\n");
      }
      i--;
      printf("CBreak Four\n");
   }
   printf("Contains End\n");
   return (this->next[0] != NULL) && (this->next[0]->data == value);   
}

包含和添加是问题所在，但也可能有其他问题。奇怪的是，这通常发生在我释放另一个列表之后，但我无法在我的代码中找到任何工件。

如果你帮我解决这个问题，我会邮寄 20 美元和一盘饼干到你选择的地址。

Answer 1

skip_set_init() 将 max_height 设置为 1 并为指针数组分配内存

set->max_height = 1;
...
set->head->next = malloc(sizeof(skip_node_t*) * set->max_height);

但不初始化数组的元素next。然后在 skip_set_add()

for (int ii = 0; ii < set->max_height; ii++)
    arr[ii] = set->head->next[ii];

for (int jj = set->max_height; jj < new_height; jj++)
    arr[jj] = NULL;

第一个元素从未初始化的数组中复制，其他元素[1..]设置为NULL。

所以第一个元素arr[0]是一个未初始化的值。

我没有比这更进一步了。

Answer 2

标准建议是这样的：

使用 -Wall 确保您的代码编译时没有警告 - 这会捕获一堆东西。
运行你的代码在 valgrind 下并确保它在没有警告的情况下运行 - 这会捕获更多东西。
运行您在 gdb 中的代码（或您正在使用的任何调试器）并仔细查看堆栈跟踪。
复制你的代码，并尝试删除和简化一些东西，直到你得到一个最小的例子（可能删除一些东西会修复它，在这种情况下你知道什么坏了）
万一您仍然遇到问题，post 这里是生成的最少代码。调试起来会更容易。

以下是基于阅读您的代码的一些建议：

使用 calloc() 而不是 malloc() 分配内存，这会将所有内容归零（添加一个虚拟额外参数 1）。这使得查找问题变得更加容易。在我写这篇文章后大约 10 秒（但还没有发布）WeatherVane posted 了一个答案，显示了一个可以通过这个解决的问题 - 或者至少已经解决了更明显了。
写一个函数来检查跳表的一致性。这可能也会让您获得额外的荣誉，但非常适合调试。
当您增加跳过列表条目数组时，realloc() 会让您的生活更轻松，并且更不容易出错。我想我比 WeatherVane 快了 10 秒。

Answer 3

已修复！我自由了！我终于自由了！

user3386109 和我都得出了相同的结论 - 我找到了它，并检查了董事会，他也提到了同样的事情。

在init中，我忘记将set->head->next[0]初始化为NULL，或者在其他函数中检查。未初始化的指针，并且很可能在运行时导致段错误异常 - 特别是在我之前构建了另一组之后。不确定结果如何，我也不想推测太多。

感谢您在万圣节花时间帮助一位犯错的 CS 学生。稍微测试一下，我只因为迟到损失了 10%。

编辑：此外，WeatherVane 的 post 也有帮助。谢谢！

一个Segfaulting Skip List，一个毁了的周末（C编程）

One Segfaulting Skip List, One Ruined Weekend (C Programming)

c

debugging

list

segmentation-fault

skip-lists