Statalist The Stata Listserver


[Date Prev][Date Next][Thread Prev][Thread Next][Date index][Thread index]

Re: st: Mata: dropping structures from memory


From   [email protected] (William Gould, Stata)
To   [email protected]
Subject   Re: st: Mata: dropping structures from memory
Date   Tue, 13 Jun 2006 16:00:36 -0500

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 = &copy
        }

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/



© Copyright 1996–2024 StataCorp LLC   |   Terms of use   |   Privacy   |   Contact us   |   What's new   |   Site index