I've developed a SkipList with void pointer, and probabilistic way to set the maximum level of it.
those are my structs:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct _Node{
Node **next;
size_t size; //number of pointer in the node
void *item;
}Node;
typedef struct _SkipList{
Node **heads;
size_t max_level; //max height in a single node
size_t max_height; //max possible height in the skiplist
int (*compare)(const void *, const void *);
}SkipList;
double random_probability() {
return (double)rand() / RAND_MAX;
}
size_t random_level(size_t max_height) {
size_t level = 1;
while (random_probability() < 0.5 && level < max_height) {
level++;
}
return level;
}
Node *create_node(void *item, size_t level) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (!newNode) {
fprintf(stderr, "Errore nell'allocazione del nodo.\n");
exit(EXIT_FAILURE);
}
newNode->item = item;
newNode->size = level;
newNode->next = (Node **)malloc(level * sizeof(Node *));
if (!newNode->next) {
fprintf(stderr, "Errore nell'allocazione dei puntatori successivi.\n");
exit(EXIT_FAILURE);
}
for (size_t i = 0; i < level; i++) {
newNode->next[i] = NULL;
}
return newNode;
}
void new_skiplist(SkipList **list, size_t max_height, int (*compare)(const void *, const void *)) {
*list = (SkipList *)malloc(sizeof(SkipList));
if (!*list) {
fprintf(stderr, "Errore nell'allocazione della SkipList.\n");
exit(EXIT_FAILURE);
}
(*list)->heads = (Node **)calloc(max_height, sizeof(Node *));
if (!(*list)->heads) {
fprintf(stderr, "Errore nell'allocazione dei puntatori iniziali.\n");
exit(EXIT_FAILURE);
}
(*list)->max_level = 0;
(*list)->max_height = max_height;
(*list)->compare = compare;
srand((unsigned int)time(NULL));
}
and this are the insert function
void insert_skiplist(SkipList *list, void *item) {
Node **update = (Node **)malloc((list->max_height + 1) * sizeof(Node *));
if (!update) {
fprintf(stderr, "Errore nell'allocazione dell'array di aggiornamento.\n");
exit(EXIT_FAILURE);
}
Node *x = list->heads;
// loop invariant: x[i]->item <= item or item < first element of level i in list
for (size_t i = list->max_level; i > 0; i--) {
while (x->next[i - 1] != NULL && list->compare(x->next[i - 1]->item, item) <= 0) {
x = x->next[i - 1];
}
update[i] = x;
}
// loop end: x[1]->item <= item or item < first element in list
x = x->next[0];
if (x != NULL && list->compare(x->item, item) == 0) {
// Elemento giĆ presente, aggiorna il valore o gestisci il caso a tuo piacimento
// x->item = newValue;
free(update);
return;
}
size_t level = random_level(list->max_height);
if (level > list->max_level) {
for (size_t i = list->max_level + 1; i <= level; i++) {
update[i] = list->heads;
}
list->max_level = level;
}
x = create_node(item, level);
for (size_t i = 1; i <= level; i++) {
x->next[i - 1] = update[i]->next[i - 1];
update[i]->next[i - 1] = x;
}
free(update);
}
const void *search_skiplist(SkipList *list, void *item) {
Node **x = list->heads;
for (size_t i = list->max_level; i > 0; i--) {
while (x[i] != NULL && list->compare(x[i]->item, item) < 0) {
x = x[i]->next;
}
}
if (x[1] != NULL && list->compare(x[1]->item, item) == 0) {
return x[1]->item;
} else {
return NULL;
}
}
now, when i try to create a skiplist from the array on the main:
int compare_int(const void *a, const void *b) {
int x = (int *)a;
int y = (int *)b;
return (x - y);
}
int main() {
srand((unsigned)time(NULL));
SkipList *int_list;
new_skiplist(&int_list, 10, compare_int);
int int_keys[] = {3, 6, 1, 8, 2, 7, 5, 4, 9};
for (size_t i = 0; i < sizeof(int_keys) / sizeof(int_keys[0]); i++) {
insert_skiplist(int_list, int_keys[i]);
}
const void* found=search_skiplist(int_list,9);
if(found!=NULL) printf("FOUNDED\n");
clear_skiplist(int_list);
return 0;
all goes ok, untill i try to insert 8, the problem seems that if my insert have to put a node at the end of the list, it get segmentation fault.
precisely, GDB get this error when i try to insert 8 item:
Program received signal SIGSEGV, Segmentation fault.
Inser into SkipList int: 9
Program received signal SIGSEGV, Segmentation fault.
0x004017ff in insert_skiplist (list=0xad1800, item=0x3) at src/skiplist.c:104
104 x = x->next[0];
(gdb) bt
#0 0x004017ff in insert_skiplist (list=0xad1800, item=0x3) at src/skiplist.c:104
#1 0x00401af6 in main () at src/main_ex2.c:30
(gdb) print (int)item
$1 = 3
(gdb) print (int*)item
$2 = (int *) 0x3
(gdb) print (int)x->item
$3 = 0
(gdb) print x->item
$4 = (void *) 0x0
(gdb) print x->next[0]
Cannot access memory at address 0x0
(gdb)
(gdb)
so it cannot access to the previous item in the k-1 node, and i d'ont understand why because it put the 6 after 3 and 1 without error.
I'm stucked with this error, can someone help me to understand the bug?
Thank you a lot!
the problem was in the adressing, this passage is wrong
it must be
now all work fine