I need help on understanding how to properly allocate memory for use in implementing a Skip List

[twin night]

For anyone who is unfamiliar as to what a Skip List is, all that matters is that it's a linked list that has an array of pointers for the next (And in my case, also previous), pointing to specific other entries in the linked list.
I am currently implementing the Node that contains the the value and the pointer references for the next relevant nodes.
When I run it in Valgrind, I get the following error:

Invalid write of size 8
==3201==    at 0x109492: main (testfile.c:53)
==3201==  Address 0x1ffefffde0 is on thread 1's stack
==3201==  240 bytes below stack pointer
==3201== 
==3201== Invalid write of size 8
==3201==    at 0x1094AD: main (testfile.c:54)
==3201==  Address 0x1ffefffd90 is on thread 1's stack
==3201==  320 bytes below stack pointer

I would like to know how I am supposed to implement an array of pointers such that it does not give me memory errors, or whether I am supposed to ignore Valgrind's messages.

typedef struct s_SkipElement {
    int value, level;
    struct s_SkipElement** next;
    struct s_SkipElement** previous;
} SkipElement;

SkipElement* skipelement_create(int level) {
    SkipElement *e = malloc(2*sizeof(SkipElement)+2*sizeof(int));
    e->level = level;
    SkipElement *tempNext[level];
    SkipElement *tempPrev[level];
    //printf("tempNext:%li\n",sizeof(tempNext));
    e->next = tempNext;
    e->previous = tempPrev;
    return e;
}

int main () {
    SkipElement* e = skipelement_create(10); //Tests the memory allocation of skipelement_create;
    SkipElement* t = skipelement_create(10);
    //printf("t%li %li\n",sizeof(t),sizeof(*t));
    //printf("e%li %li\n",sizeof(e),sizeof(*t));
    for (int i=0; i<e->level;i++) {
        //printf("run\n");
        e->next[i] = t;
        e->previous[i] = t;
        //printf("run2\n");
    }
    e->value=5;
    //printf("%i %i\n",e->value,e->level);
    //printf("%li\n",sizeof(e->next[4]));
    (void)e;
    return 0;
}

[idle phoenix]

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 use !howto ask.

[dusky harbor]

what happens to tempNext and tempPrev after skipelement_create returns?

[kind ridge]

First question, did you want tempNext to a pointer to an array or an array of pointers

Either way, as it is here, tempNext is an array, and as such, the memory for it is on the stack (temporary memory to hold local variables until the function returns)
You have a pointer to that temporary memory, so after you return, the memory no longer belongs to that array

What you can do is one of two things. You can have the struct itself hold an array (but the size needs to be static) or you use malloc to reserve sizeof(SkipElement*) * level bytes

[dusky harbor]

from the wiki it looks like it's intended to be an array of pointers for the head

[kind ridge]

Okay then the rest of what I said stands

[dusky harbor]

yes

[twin night]

So, if I understand correctly, I am not properly telling the program that I want to reserve memory specifically for this struct

[twin night]

    SkipElement *tempNext[level] = malloc(sizeof(SkipElement*) * level);
    SkipElement *tempPrev[level] = malloc(sizeof(SkipElement*) * level);

Am I understanding correctly in that this is what I would modify to get that result?

also, have I properly utilised SkipElement *e = malloc(2*sizeof(SkipElement)+2*sizeof(int)); to allocate the initial memory space?

sizeof(e) tells me 24, so I assume that's correct (8+8+4+4)

[kind ridge]

Why not just sizeof(SkipElement) why the * 2 and + 2 ints?

[twin night]

Now that I look at it, you're right

[kind ridge]

Also fun fact
SkipElement *e = malloc(sizeof(*e)); is valid :p

[twin night]

It's an artifact from my initial allocation code, SkipElement *e = malloc(2*level*sizeof(SkipElement)+2*sizeof(int));

[twin night]

that's actually amazing

since e gets its typeinfo by the declaration

[kind ridge]

Double checking, are you trying to allocate just one skip element or an array of skip elements?

[twin night]

an array

[kind ridge]

Ah, in that case
malloc(sizeof(type) * size)

My apologies

[twin night]

I create a SkipElement by passing level, which initialises the type with two internal SkipElement arrays of size level, containing pointers to SkipElements

I see, thanks for the help! We'll see if these changes get rid of the errors!

@kind ridgeDo I need the array syntax if I'm using malloc?

[idle phoenix]

@twin night Has your question been resolved? If so, type !solved :)

[kind ridge]

You don't need the []
Pointer are already an array (sort of)

Okay so I'm going to avoid the specific question and just give a quick lesson on pointers and arrays by themselves

For one, pointers by themselves can act like arrays

;compile

#include <stdio.h>
#include <stdlib.h>

int main() {
  int *a = malloc(sizeof(int) * 10);
  for (int i = 0; i < 10; i++) {
      a[i] = i; // equivalent to *(a + i) = i
  }
  for (int i = 0; i < 10; i++) {
      printf("Value at %p = %d\n", a + i, a[i]);
  }
}

[trail tartan]

Program Output

Value at 0x13732a0 = 0
Value at 0x13732a4 = 1
Value at 0x13732a8 = 2
Value at 0x13732ac = 3
Value at 0x13732b0 = 4
Value at 0x13732b4 = 5
Value at 0x13732b8 = 6
Value at 0x13732bc = 7
Value at 0x13732c0 = 8
Value at 0x13732c4 = 9

zeropointer#0000 | 33ms | c | x86-64 gcc 13.2 | godbolt.org

[kind ridge]

Using int as a metaphor

Do you want a pointer to an array of ints, that's the same as just a pointer to an int (just makes sure you allocate enough space)

int *a = malloc(sizeof(int) * 10);

Do you want an array of pointers to ints, that is when you have to either use malloc to create pointer to pointers, or a more basic array syntax.
What is important with the second solution is that when you first create the array of pointers, the pointers aren't pointing to anything, so you have to either have to assign pointers individually by passing the address of a variable, or doing another malloc

int *a[2] = {NULL, NULL}
int **b = malloc(sizeof(int*) * 2);

int c = 5;
a[0] = &c;
a[1] = malloc(sizeof(int));

Also lastly, the data pointed to by the pointer returned from malloc is considered "uninitialized" meaning it does not have any meaningful value. in the case of int* a = malloc(sizeof(int)), *a can result in any value, so make sure to assign a value to it *a = 5;
For pointers to structs, you can initialize each field directly instead

struct S {
  int a, b;
}

struct S* a = malloc(sizeof(struct S));
a->a = 5;
a->b = 10;

[twin night]

I see, that answers my questions exactly as that was the mechanical knowledge I was missing

Perfect!

[kind ridge]

🫡

[twin night]

Alright, I don't have any more time to look at this today, but I might have a few more questions tomorrow once I get back around to it. I seem to have encountered a new issue and I'm unable to properly use free() to delete the lists, but we'll see if my implementation is just incomplete