i have to delete the entire skipList. I was trying to use the features of a skipList to have a bettere complexity of the algorithm but when i try to run and debug give me segmentation fault.
EDIT: i was trying to make a O(n log n) algorithm but it was a mistake...solution require O(log n) algorithm. I'll edit with the solution that work but it free the memory correctly?
main:
int main(int argc, char const *argv[])
{
srand(time(NULL));
SkipList *list = malloc(sizeof(SkipList));
list->max_level = 0;
list->compare = NULL;
list->head = create_node(NULL,MAX_HEIGHT);
insert_skip_list(list,(int*)5);
insert_skip_list(list,(int*)4);
insert_skip_list(list,(int*)3);
insert_skip_list(list,(int*)1);
insert_skip_list(list,(int*)0);
list=delete_skip_list(list);
read_skip_list(list);
return 0;
}
function to delete:
SkipList* delete_skip_list(SkipList *list){
delete_node_array(list->head);
free(list);
list=NULL;
return list;
}
void delete_node_array(Node* node){
if(node == NULL) return;
delete_node_array(node->next[0]);
free(node);
node = NULL;
}
structure:
struct _SkipList {
Node *head;
unsigned int max_level;
int (*compare)(void*, void*);
};
struct _Node {
Node **next;
unsigned int size;
void *item;
};
EDIT:
Node* create_node(void* item, int level){
Node *node = malloc(sizeof(Node));
if(node == NULL){
printf("error malloc node");
}
node->item = item;
node->size = level;
node->next = (Node**)malloc(level * sizeof(Node));
for (int i = 0; i < node->size; i++)
{
node->next[i] = NULL;
}
if(node == NULL){
printf("error malloc node->next");
}
return node;
}
float float_rand( float min, float max )
{
float scale = rand() / (float) RAND_MAX; /* [0, 1.0] */
return min + scale * ( max - min ); /* [min, max] */
}
int random_level(){
int level = 1;
while(level<MAX_HEIGHT && float_rand(0,1) < 0.5){
level++;
}
return level;
}
void insert_skip_list(SkipList* list,void* item){
Node* node = create_node(item,random_level());
if(node == NULL){
printf("\nisert_skip_list:error malloc node");
}
if (list == NULL)
{
printf("\nisert_skip_list:list null");
exit(EXIT_FAILURE);
}
if(node->size > list->max_level){
list->max_level = node->size;
}
Node *x = list->head;
for (int k = list->max_level-1; k >= 0; k--)
{
if(x->next[k] == NULL || item < x->next[k]->item){
if(k < node->size){
node->next[k] = x->next[k];
x->next[k] = node;
}
}else{
x = x->next[k];
}
}
}
I tried to print the size of the node and i foud out that give me random value :
node size: 1 node size: 1 node size: 1 node size: 1 node size: 12004376 Program received signal SIGSEGV, Segmentation fault.
like node is null and not have access to field size.