#Initialising and deleting skiplists

13 messages · Page 1 of 1 (latest)

lofty trout
#

Im a bit stuck on how to delete skiplists without leaking any memory. Here is my skiplist definition:

typedef struct s_LinkedElement {
    int value;
    int nbpt;
    struct s_LinkedElement **previous;
    struct s_LinkedElement **next;
} LinkedElement;

struct s_Skiplist {
    RNG sk_proba;
    int nbLevels;
    LinkedElement *sentinel;
    int size;
};

My initialisation of an empty skiplist:

SkipList skiplist_create(int nblevels) {
    SkipList l = malloc(sizeof(struct s_SkipList));
    l->sentinel=malloc(sizeof(struct s_LinkedElement));
    l->sentinel->next = malloc(sizeof(struct s_LinkedElement)*nblevels);
    l->sentinel->previous = malloc(sizeof(struct s_LinkedElement)*nblevels);
    for (int i = 0; i < nbLevels; i++) {
        l -> sentinel -> previous[i]  = l -> sentinel;
        l -> sentinel -> next[i]  = l -> sentinel;
    }
    l->size = 0;
    return l;
}

To delete them, I thought about iterating through the sentinel and the next and previous tables and freeing all of the elements individually, is there any better way to do it? Is mine even valid?

grave radishBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

fervent rain
#

Yours isn't valid - as you would've realized by simply compiling the code - because you're casting a pointer to an instance of SkipList.

You need to write SkipList *l = malloc(...);

#

Other than that I won't check your code if you don't even know whether it's faulty

lofty trout
# 
typedef struct s_SkipList *SkipList;
#

This is in the header file\

#

It compiles just fine

lofty trout
fervent rain
fervent rain
lofty trout
#

Im positive that my initialization implementation is working properly, i think I managed to get deletion down too

#

Valgrind 😍