NewList() - Do we need to allocate memory?

[nyteschayde]

When using the NewList() function described in exec/lists.h (at least in SAS/C 6.58), does one need to allocate memory for a new list separately? What does NewList() do exactly?

Code: [Select]


/* Is NewList(struct List *) the same as the following? */
struct List *list;

list = (struct List *)AllocMem(sizeof(struct List), MEMF_ANY);
memset(list, 0L, sizeof(struct List));

/* Or does it do some magic black box stuff? And if I want to pass
    my list around, should I malloc() the memory for the list and then
    remember to free it myself later; after passing it around */
list = (struct List *)malloc(sizeof(struct List));
NewList(list);
// ... use the list
free(list);


[nyteschayde]

Also, do the Amiga link list style methods include one that counts or one that counts the number of items in the list? Is there a method that will walk the link list until next points to null or next points to the head and count or should we have to write that ourselves?

[guest11527]

When using the NewList() function described in exec/lists.h (at least in SAS/C 6.58), does one need to allocate memory for a new list separately? What does NewList() do exactly?

NewList() does not care where the memory came from, but you need to provide enough memory to hold a list structure. Certainly, the lifetime of the memory must be at least as long as you wish to keep the list around.

That is, if you need the list only in a particular function, and the function called from there, a "struct List" on the stack will certainly do, once initalized correctly. If, however, you need to access the list after the function that initialized it returned, you'd better allocate it from the heap, or place it outside of a function.

NewList() doesn't do particularly much, which is why exec traditionally doesn't include a function for it (amiga.lib does):

Code: [Select]

void NewList(struct List *lh)
{
 lh->lh_Head = (struct Node *)&(lh->lh_Tail);
 lh->lh_Tail = NULL
 lh->lh_TailPred = (struct Node *)&(lh->lh_Head);
}

[CODE]

/* Is NewList(struct List *) the same as the following? */
struct List *list;

list = (struct List *)AllocMem(sizeof(struct List), MEMF_ANY);
memset(list, 0L, sizeof(struct List));

No. NewList() doesn't allocate memory, and setting all elements to zero is not appropriate to initialize a list. I gave a possible implementation above.

/* Or does it do some magic black box stuff? And if I want to pass
    my list around, should I malloc() the memory for the list and then
    remember to free it myself later; after passing it around */

Whether you malloc the list or not, i.e. whether you place the object on the stack or the heap actually depends on the very same question as for every other C object: It is a matter of the lifetime of the object. An object on the stack deceases as soon as you leave the function within which it was created. If that lifetime is too short, you need to take the memory from the heap, i.e. malloc() it.

[guest11527]

Also, do the Amiga link list style methods include one that counts or one that counts the number of items in the list?

No.

Is there a method that will walk the link list until next points to null or next points to the head and count or should we have to write that ourselves?

You need to write this yourself. Essentially, you are asking the question whether there is an "iterator" for a list. As said, the answer is "no", but it is trivial to write one. The following idiom will iterate over the elements of a list:

Code: [Select]

struct List *lh = ...
for(struct Node *node = lh->lh_Head;node->ln_Succ;node = node->ln_Succ) {
 ... do something with node ...
}
Node (ehem ;-) in particular that the check for aborting the iteration is not "node" but "node->ln_Succ", i.e. you have reached the end of the list as soon as you have found a node whose Succ pointer is NULL. *NOT* as soon as you have reached a NULL node pointer.

In fact, if you have a struct Node * with node->ln_Succ == NULL, then that is not a struct Node * at all. You instead hold a pointer to lh->ln_Tail, which is the whole trick how exec lists work.

Iterating backwards is easily simple:

Code: [Select]

struct List *lh = ...
for(struct Node *node = lh->lh_TailPred;node->ln_Pred;node = node->ln_Pred) {
 ... do something with node ...
}


[nyteschayde]

As usual, you are a fantastic teacher. You hold so much in the way of domain knowledge. Thanks for taking the time and teaching. I may have more questions along different topic lines. I'll post in new threads so others can benefit from my learning and your teaching.

<3