c - 一个Segfaulting Skip List，一个毁了的周末(C编程)

Question

我是一名 CS 学生，我的万圣节周末刚刚被我无法调试的编程作业毁了。这可能是这里为数不多的不会立即被标记为“重复”的问题之一。

分配是一个“跳跃列表”或单链表(用 C 语言编程)，其中每个节点都有一个可变大小的指针数组，由随机“硬币”抛掷决定。 3 次成功的 throw 导致高度为 3，依此类推。每个数组然后链接到相似高度的其他数组 - 第七层链接到下一个第七层，第六层链接到下一个第六层，一直向下到第一层，或数组元素0，自然链接到列表中的下一个项目。

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

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

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

我对此束手无策。我在类得了 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);   
}

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

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

Answer 1

标准建议是这样的:

1. 使用 -Wall 确保您的代码编译时没有警告 - 这会捕获一堆东西。

2. 在 valgrind 下运行您的代码并确保它在没有警告的情况下运行 - 这会捕获更多内容。

3. 在 gdb(或您使用的任何调试器)中运行您的代码并仔细查看堆栈跟踪。

4. 复制您的代码，并尝试删除和简化一些东西，直到您得到一个最小的示例(可能删除一些东西会修复它，在这种情况下您知道什么坏了)

5. 万一您仍然遇到问题，请在此处发布生成的最少代码。调试起来会更容易。

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

1. 使用 calloc() 而不是 malloc() 分配内存，这会将所有内容清零(添加一个额外的虚拟参数 1)。这使得查找问题变得更加容易。在我写这篇文章(但尚未发布)大约 10 秒后，WeatherVane 发布了一个答案，其中显示了一个本可以由此解决的问题 - 或者至少使它更明显。

2. 编写一个函数来检查跳跃列表的一致性。这可能也会让您获得额外的荣誉，但非常适合调试。

3. 当您增加跳过列表条目数组时，realloc() 会让您的生活更轻松，并且不易出错。我想我以 10 秒的优势击败了WeatherVane。