Weird behaviour working on a skip list using void pointers

94 Views Asked by At
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;
}
0

There are 0 best solutions below