i need help with this. The program give me a segmentation fault when enters to test2().
I believe the segmentation fault occurs when the skiplist_free() function is called but i don't know why. could you guys help me with this? here i leave my code so you guys can take a look at it.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct node {
void *data;
int key;
struct node *right;
struct node *down;
};
struct skiplist {
struct node *head;
int level;
};
struct skiplist *skiplist_alloc(){
struct skiplist *sl = (struct skiplist *) malloc(sizeof(struct skiplist));
if (sl == NULL){
printf("ERROR: Malloc failed for skiplist");
exit(1);
}
return sl;
}
int rand_level(int limit)
{
int i = 1, r = rand();
while (r & 1 && i < limit) {
++i;
r >>= 1;
}
return i;
}
struct node *make_node(void *data, struct node *right, struct node *down, int key)
{
struct node *node = malloc(sizeof (struct node));
if (node == NULL) {
return NULL;
}
node->data = data;
node->right = right;
node->down = down;
node->key = key;
return node;
}
void destroy_node(struct node *node)
{
free(node);
}
void skiplist_free(struct skiplist *slist)
{
struct node *here;
struct node *start = slist->head;
struct node *next;
int i;
for (i = slist->level; i > 0; i--){
if(start !=NULL){
next = start->right;
here = start;
start = start->down;
}
while (next != NULL) {
if(here !=NULL){
free(here);
}
here = next;
next = next->right;
}
}
free(slist);
}
void skiplist_insert(struct skiplist *slist, int key, void *data)
{
struct node *x, *save = NULL;
int i, level = rand_level(slist->level + 1);
while (level > slist->level) {
++slist->level;
slist->head = make_node(0, NULL, slist->head, -2);
}
x = slist->head;
for (i = slist->level; x != NULL; i--) {
while (x->right != NULL && key > x->right->key) {
x = x->right;
}
if ( i <= level ) {
if (x->right == NULL || key != x->right->key) {
x->right = make_node(data, x->right, NULL, key);
}
if (save != NULL) {
save->down = x->right;
}
save = x->right;
}
x = x->down;
}
}
void skiplist_remove(struct skiplist *slist, int key)
{
struct node *x, *save;
x = slist->head;
while (x != NULL) {
while (x->right != NULL && key > x->right->key) {
x = x->right;
}
if (x->right != NULL && key == x->right->key) {
save = x->right;
x->right = save->right;
destroy_node(save);
}
x = x->down;
}
while (slist->head != NULL && slist->head->right == NULL) {
save = slist->head;
slist->head = slist->head->down;
destroy_node(save);
}
}
void *skiplist_search(struct skiplist *slist, int key)
{
struct node *x = slist->head;
int i;
for (i = slist->level; i > 0; i--){
while(x->right != NULL && x->right->key < key){
x=x->right;
}
if(x->down != NULL){
x=x->down;
}
}
if(x != NULL && x->right->key == key){
return x->right->data;
}
return 0;
}
Code:
struct skiplist;
struct skiplist *skiplist_alloc();
void skiplist_free(struct skiplist *slist);
void *skiplist_search(struct skiplist *slist, int key);
void skiplist_insert(struct skiplist *slist, int key, void *data);
void skiplist_remove(struct skiplist *slist, int key);
Code:
/*skiplist_main.c*/
Code:
#include <stdio.h>
#include <stdlib.h>
#include "skiplist.h"
void test1() {
struct skiplist *slist = skiplist_alloc();
int i;
skiplist_insert(slist, 0, "zero");
skiplist_insert(slist, 2, "two");
skiplist_insert(slist, 4, "four");
skiplist_insert(slist, 6, "six");
skiplist_insert(slist, 8, "eight");
skiplist_insert(slist, 1, "one");
skiplist_insert(slist, 3, "three");
skiplist_insert(slist, 5, "five");
skiplist_insert(slist, 7, "seven");
skiplist_insert(slist, 9, "nine");
for (i = 0; i <= 9; i++)
printf("%d %s\n", i, (char *) skiplist_search(slist, i));
skiplist_remove(slist, 0);
skiplist_remove(slist, 2);
skiplist_remove(slist, 4);
skiplist_remove(slist, 6);
skiplist_remove(slist, 8);
for (i = 0; i <= 9; i++)
printf("%d %s\n", i, (char *) skiplist_search(slist, i));
skiplist_free(slist);
}
int crand() {
static unsigned int x = 0xCAFEBABE;
x = 1103515245 * x + 12345;
return x & 0x7FFFFFFF;
}
int test2(int n) {
struct skiplist *slist = skiplist_alloc();
int *array, i, j, temp;
int success = 1;
if ((array = malloc(sizeof(int) * 2 * n)) == NULL) {
fprintf(stderr, "malloc failed");
exit(1);
}
for (i = 0; i < 2 * n; i++)
array[i] = i;
for (i = 2 * n - 1; i >= 0; i--) {
j = crand() % (i + 1);
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
for (i = 0; i < 2 * n; i++){
skiplist_insert(slist, array[i], &array[i]);
}
for (i = 0; i < 2 * n; i++) {
int *p = skiplist_search(slist, i);
if (*p != i)
success = 0;
}
for (i = 0; i < 2 * n; i += 2) {
skiplist_remove(slist, array[i]);
array[i] = -1;
}
for (i = 2 * n - 1; i >= 0; i--) {
int *p = skiplist_search(slist, array[i]);
if ((p == NULL && array[i] != -1)
|| (p != NULL && p != &array[i]))
success = 0;
}
free(array);
skiplist_free(slist);
return success;
}
void test3(int n) {
struct skiplist *slist = skiplist_alloc();
int i;
for (i = 0; i < n; i++)
skiplist_insert(slist, crand(), slist);
for (i = 0; i < 3 * n; i++)
switch (crand() % 3) {
case 0:
skiplist_insert(slist, crand(), slist);
break;
case 1:
skiplist_remove(slist, crand());
break;
case 2:
skiplist_search(slist, crand());
break;
}
skiplist_free(slist);
}
int main() {
int score = 0, i;
printf("test 1:\n");
test1();
printf("test 2:\n");
for (i = 0; i < 250; i++){
if (test2(100)){
score++;}
printf("%d %d\n", i ,score);
}
printf("%g\n", score / 10.0);
printf("test 3:\n");
for (i = 0; i < 100; i++)
test3(1 << 16);
return 0;
}
