Zurab Sajaia <[email protected]> has a forward linked list.
That is, he defined something like
struct member {
transmorphic x
pointer(struct member) next
}
He started off his linked list with something like
pointer(struct member) head
head = &(member())
head->x = ...
and then, after that, he added new members to the list,
current = head
for (...) {
current->next = &(member())
current = next
current->x = ...
}
where -current- is a -pointer(struct member)-.
He has now reached the stage where he has N+K members of the list.
He writes that the subsequent K are a function of the first N, and
at this stage, he no longer needs the first N. Not only does he
not need them, he must discard them because he needs the memory back.
Answer to a different question
------------------------------
First, let us assume that he wanted to discard the subsequent K (and keep
the first N). All we have to do is reach into the list, find the Nth
element, and set it's -next- equal to NULL.
Probably Zurab has some -pointer(struct member)- variable laying around that
points the first of the subsequent K elements. If not, he could count his way
there:
Nth = head
for (i=1; i<N; i++) Nth = Nth->next
Note that I coded -i<N- and not -i<=N-.
In any case, Nth points to the Nth member of the list. We could not delete
all the subsequent members by coding
Nth->next = NULL
Answer to the question asked
----------------------------
In this case, however, we do not want to keep 1 through N, we want to get
rid of them. This time, rather than assuming a variable -Nth- pointing
to the Nth member, let's assume a variable K1 pointing to the first
of the K elements. If Zurab does not have K1, he could obtain it easily
enough:
K1th = head
for (i=1; i<=N; i++) K1th = K1th->next
Okay, so I am assuming we have -head- and we have -K1th-. To get rid of
the members up to K1th, all we have to code is
head = NULL
Mata keeps structures around as long as somebody is using them. Mata
decides somebody is using a structure as long as there is a variable
either containing the structure or pointing to it.
When we code
head = NULL
then the old *head is freed. So is everything down the chain IF THE ONLY
REASON FOR THEIR EXISTANCE WAS THAT THEY WERE BEING POINTED TO BY THE
PREVIOUS ELEMENT.
In this case, however, -K1th- points to the first of the K elements,
so that element as two reasons to exist:
because
its predecessor pointed to it, and because K1th points to it. The
predecessor was destroyed. That still left K1th, and so *K1th was
not destroyed. Neither as K1th->next destroyed, because K1th pointed
to it. And neither was K1th->next->next destroyed, and on and on.
Expansion on the answer
-----------------------
My answer is correct as long as the assumptions I made are correct.
The way pointers work, if you have any pointer laying around pointing
to an element of the list, and you forget about it, the list from that
point on will not be freed.
Memory allocation and freeing is automatic in Mata. Mata is very careful
to make sure that it does not destroy anything that could be subsequently
used. Usually, exactly when an element is freed doesn't much matter,
and so programmers can be sloppy. However, if Zurab wants to ensure that the
first N elements really are freed, he cannot be sloppy. He must make sure
that he does not have any other pointers laying around, pointing into the
list, and if he does, he must set them to NULL as well. Once Zurab convinces
Mata that he really can never again refer to a a structure, or a linked list
of structures, Mata frees them.
I'm sure Zurab has nice, clean code, but let me offer some advice.
Many programmers, when they are new to pointers and lists, write long
programs, with many variables, and the same idea expressed over and
over again. I never do that. When I have to work with pointers and
lists, all my programs are short. Very short. And simple. Linked
lists are complicated enough without my code adding to the compliation.
So if I were implementing a linked list, I would have two variables
floating around:
pointer(structure member) head, tail
Variable -head- would point to the first structure. tail would point to
the last one. In Zurab's case, I would probably have a third pointer
laying around called Nth to distinguish the first N from the subsequent
K, although I have to ask: Why not just two linked lists. A first list
with N members, and a second list with K? No doubt there is some good
answer to that question.
Anyway, I would probably have head and tail, although in some cases, I would
not need tail, and then I wouldn't have it. I wouldn't need tail if the
construction process involved adding into the middle of the list.
Anyway, I would have an -insert_into_list- routine:
insert_into_list(pointer(struct member) where, struct member new)
{
struct member copy
copy = new
copy.next = where->next
where->next = ©
}
I could even use -insert_into_list()- to add onto the end:
insert_into_list(tail, mynewstructure)
-- Bill
[email protected]
*
* For searches and help try:
* http://www.stata.com/support/faqs/res/findit.html
* http://www.stata.com/support/statalist/faq
* http://www.ats.ucla.edu/stat/stata/
