I'm a CS student, and my Halloween weekend just got ruined by a programming assignment I can't debug. This might be one of the few questions on here that doesn't immediately get marked "duplicate."
The assignment is a "Skip List," or a singly-linked list (programmed in C) where each node has a variable-size array of pointers, determined by random "coin" tosses. 3 successful tosses results in a height of 3, etc. Each array is then linked to other arrays at similar heights - a seventh level linked to the next seventh level, sixth to the next sixth, all the way down to first, or array element 0, which is naturally linked to the very next item in the list.
Since most items don't have a higher level, this acts as a great way for searching in log(n) time, rather than simply n. It's dramatically faster for insert, remove, and search, at the cost of being more expensive in memory. This is just the theory - here's a picture: Skip List
Many of you will already know this stuff, but I just wanted to explain it a little and show that I actually do understand the basics of what's happening here.
The issue is a random segfault that's screwing up all of the provided tests with "CODE 6 - ABORT" messages. When I run my main file, I randomly get segfaults at the indicated locations in the code (<-----Segfaults) - it happens about half the time, and can be at either line. The tests also give me a lot of "bad pointer" and "minmap chunk error" messages.
I'm at my wits' end on this. I have a 93 in the class, but that drops to an 87 if I can't get this abominable thing finished.
Any assistance is appreciated, and here's the code:
Definitions
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;
Main method causing the random fault
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
...And finally, the devil's data structure:
#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 and Add are the problem, though there might be other stuff, too. Weirdly, this usually happens after I free another list, but I can't find any artifacts from it in my code.
If you solve this for me, I'll mail a $20 and a plate of cookies to the address of your choice.
skip_set_init() sets max_height to 1 and allocates memory for a pointer array
set->max_height = 1;
...
set->head->next = malloc(sizeof(skip_node_t*) * set->max_height);
but does not not initialise the elements of the array next. Then in 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;
the first element is copied from the uninitialised array, and the other elements [1..] are set to NULL.
So the first element arr[0] is an uninitialised value.
I haven't looked any further than this.