void insertSkipList(SkipList* list, void* I){
Node* new_node=createNode(I, randomLevel(list->max_level));
if (new_node->size > list->max_level)
Node* actual_node=list->head;
unsigned int k;
for (k = list->max_level;k>=1;k--){
if (actual_node->next[k] == NULL || list->compare(I, actual_node->next[k]->item)<0){
if (k < new_node->size) {
new_node->next[k] = actual_node->next[k];
actual_node->next[k]=new_node;
}
else{
actual_node->next = &actual_node->next[k];
k=k+1;
}
}
}
}
I'm having troubles with the command list->compare(I, actual_node->next[k]->item
as it doesn't execute at all. The problem is most likely here actual_node->next[k]->item but I can't see why.
These are the definitions of node and list
typedef struct _SkipList SkipList;
typedef struct _Node Node;
struct _SkipList {
Node *head;
unsigned int max_level;
int (*compare)(void*, void*);
};
struct _Node {
Node **next;
unsigned int size;
void *item;
};
The complete minimal reproducible example contained within the question itself is:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_LENGTH 20
#define MAX_HEIGHT 5
typedef struct _SkipList SkipList;
typedef struct _Node Node;
struct _SkipList {
Node *head;
unsigned int max_level;
int (*compare)(void*, void*);
};
struct _Node {
Node **next;
unsigned int size;
void *item;
};
unsigned int randomLevel(unsigned int height);
static int compare_int(void* x_void,void* y_void){
int x=(int)x_void;
int y=(int)y_void;
return x-y;
}
static Node* createNode(void* item, unsigned int lvl) {
Node* n = (Node*) malloc(sizeof(Node));
if(n == NULL) {
printf("\nError! Node memory not allocated.");
exit(0);
}
n->item = item;
n->next = NULL;
n->size = lvl;
return n;
}
SkipList* createSkipList(unsigned int height, int (*compare)(void*, void*)){
SkipList* skiplist = (SkipList*) malloc(sizeof(SkipList));
if(skiplist == NULL) {
printf("\nError! Skiplist memory not allocated.");
exit(0);
}
skiplist->head=createNode(NULL,height);
skiplist->max_level=1;
skiplist->compare=(*compare);
return skiplist;
}
void insertSkipList(SkipList* list, void* I){
Node* new_node=createNode(I, randomLevel(list->max_level));
if (new_node->size > list->max_level)
list->max_level = new_node->size;
Node* actual_node=list->head;
unsigned int k;
printf("here it's before the loop\n");
for (k = list->max_level;k>=1;k--){
if (actual_node->next[k] == NULL || list->compare(I, actual_node->next[k]->item)<0){ //here the code stops completely
if (k < new_node->size) {
new_node->next[k] = actual_node->next[k];
actual_node->next[k]=new_node;
}
}
else{
actual_node->next = &actual_node->next[k];
k=k+1;
}
}
printf("here it's after the loop (and actually this wont get printed idk why\n");
}
unsigned int randomLevel(unsigned int height){
unsigned int lvl = 1;
time_t t;
srand((unsigned) time(&t));
while (rand() < 0.5 && lvl < height)
lvl = lvl + 1;
return lvl;
}
int main() //creates a skiplist that goes from 0 to MAX_LENGTH
{
skiplist=createSkipList(MAX_HEIGHT,(*compare_int));
int found[MAX_LENGTH];
int expected[MAX_LENGTH];
for(int i=0;i<MAX_LENGTH;i++){
insertSkipList(skiplist,(void*) i);
}
return 0;
}