[linked lists] Initialization doubly linked lists

[tzushky]

Good morning coders !,

I stumbled accross an initialization this morning and even though I get it , it's not 100%. I'll simplify it this way:

I have an array declaration:

uint8_t  MyArray[MAX_SIZE]

I have a linked list structure:

struct MyLL{
  struct MyLL  * next;
  struct MyLL * previous;
  uint16_t  whatever;}

and two globals :

MyLL * FirstBlock;
MyLL * LastBlock;

And then using these in an initialization function this way:

void MyInitFunc(void)
{
    MyLL     * first;
    MyLL     * last;
    uint8_t * mystart;
    uint8_t * myend;

    FirstBlock = NULL;
    LastBlock = NULL;

    mystart = &MyArray[0];
    myend   = &MyArray[MAX_SIZE];

    first = (MyLL *) mystart;
    last = (MyLL *) myend;
    last--;

    first-> whatever= init_whatever;
    first->next         = last;
    first-> previous  = NULL;

    last-> whatever = init_whatever;
    last->next          = NULL;
    last-> previous  = first;

    FirstBlock = first;
    LastBlock =last;
}

Why is that array so useful? Is it a sort of method to save up space for consecutive linked list pointers ?

I could really sue your help because the moment I thought linked lists were clear , this is shaking my confidence...

Thanks in advance,

T

[Ancient Dragon]

Where did you get that crappy code from??? Toss it out and forget it.

>> myend = &MyArray[MAX_SIZE];
Wrong -- myend is set to point one element beyond the end of the array, a common mistake. should be myend = &MyArray[MAX_SIZE=1]; >>first = (MyLL *) mystart;
Illegal operation. mystart can not be converted to MyLL structure.

[tzushky]

Hi,

Thanks for the quick answer... The MAX_SIZE was one of the things I wondered about at first read. Then the casting made it even worse, so thank's for confirming that it should be MAX_SIZE-1 ... I found it in an old project so I guess in some strange way it actually worked in the past... I'll investigate more, but thanks again, it makes me feel better to not be a total mess at this...

T

[nezachem]

Where did you get that crappy code from??? Toss it out and forget it.

With all due respect, you are wrong. The code is quite ugly yet perfectly valid.

>> myend = &MyArray[MAX_SIZE];
Wrong -- myend is set to point one element beyond the end of the array, a common mistake. should be myend = &MyArray[MAX_SIZE=1];

It is OK to point an element one beyond the end. In most platforms it is OK to point anywhere, but the Standard specifically allows pointing off by one. Of course, you shall not dereference such a pointer, and the code does no do that (see line 16 of the last listing).

>>first = (MyLL *) mystart;
Illegal operation. mystart can not be converted to MyLL structure.

May I ask what lead you to this conclusion?

Good morning coders !,
Why is that array so useful? Is it a sort of method to save up space for consecutive linked list pointers ?

I could really sue your help because the moment I thought linked lists were clear , this is shaking my confidence...

Thanks in advance,

T

With just an initialization code, one may only guess how it is used. Please inspect what else (and in what circumstances) happens with the list and the array in general; if you still have questions, the details are appreciated.
My guess would be it is a poor man's malloc in a malloc-less environment. Each MyLL (appearing in the array wherever necessary) serve as a header for the block immediately following it (note that given an MyLL pointer it is easy to calculate the size of such block).
One thing for sure - after initialization, the list represents one solid block of unstructured data.

[tzushky]

Hi,

Thanks for explaining it some more... the doubly linked list is used to store received /to be sent messages in a communication protocol. My problem came from not really understanding the use of having and array from which we grab the extreme pointers to make the first and last list components. I believe it is the "poor man's no malloc environment", isn't it? Having a fixed length array fixed a memory area, the fixed length is long enough to have it divided in several linked structures in the list. Plus there was also another operation I didn't add in the example, of placing those pointers to integer multiples of the CPU word.

If you can confirm that the array is the way to go when malloc isn't used, than I will consider this problem solved. It had just seemd like going through 3 pointer types until getting to the final list ends, looked weird...

Thanks a lot,

T

[Ancient Dragon]

>>May I ask what lead you to this conclusion?

Yes, just think about it for a second.

1. mystart is an integer pointer
2. MyArray is an array of integers
3. first is a pointer to a structure
4. The compiler can not convert an array of integers into an array of structures. Well, it can by typecasting but the result will be just so much shit.

[nezachem]

>>May I ask what lead you to this conclusion?

Yes, just think about it for a second.

1. mystart is an integer pointer
2. MyArray is an array of integers
3. first is a pointer to a structure
4. The compiler can not convert an array of integers into an array of structures. Well, it can by typecasting but the result will be just so much shit.

Strictly speaking, it is an array of uint_8, and given the lack of the context we may only guess what uint_8 really is, especially what its alignment requirements are.
Now, the only reason for shittiness (which I believe is a nice way to say UB) would be a structure (in this case a pointer, actually) having stricter alignment. As a side note, IA32 forgives even that.
Otherwise, the code is 100% valid C.

[Ancient Dragon]

It may well compile, but its far from "valid c". All you are going to achieve from those typecasts is undefined behavior. Why? An array of uint8_t can not be successfully typecast into an array of structures. It seems like what that code is attempting to do is similate a union between the structure and char array. What do you think will happen to that program if I define MAX_SIZE as 1? Or any other number less than 12 (the most likely size of the structure)?.

[ssharish2005]

I would agree with AC, it is a crappy code, which dosnt follow any standard. If you still say that a valid code, then have a look at this

MyLL     * first;    MyLL     * last;

What is MyLL. Is it typedef ? No!

~ssharish

[tzushky]

Okok,

MyLL type pointers hsould have been declared with

struct MyLL * ptr;

That was my forgetfulness. Otherwise, consider it a typedef.

Secondly, I believe that I have a slightly different view on this now. Imagine you can use use no malloc function. The declaration of the array is not for the actual use of the array , but just to save a memory space and to get its end pointers, and retranslate them into a different type of pointers.

As for the size, the original code contains a size test: end_ptr- start_ptr has to be at least 2 times bigger than the MyLL size.

There are additional functions to this, which allow creating a new structure in the list, checking if there's enough space after a given pointer etc.... The whole point of this post was just to understand the whole array use.

I still see it as pretty ugly, but I can understand its workaround.

So, did I get it right?

Thanks,
T