Thread: Free linked list in 2D list

I'm building 2D linked list.

OTU list has pointer to rep node. Say I've 5 OTU nodes, each will have same amount of nodes in rep pointer (say 120).

My doubt is on free-ing OTU.
Would my code below of free be good?
Or should I free the rep* list added with each OTU?

Code:

struct rep{
  int number;
  int count;
  struct rep *next;
};

struct otu{
  int otu_number;
  struct otu *next; //hold next otu
  struct rep *rep_seq;
} *start_otu;

void free_otu_list(){

    struct otu *temp=start_otu;

    while(temp !=NULL){
        start_otu=temp->next;
        free(temp);
        temp=start_otu;
    }
}

Thanks.

My apologies, I didn't receive e-mail notification, hence delay in replying.

Originally Posted by Nominal Animal

Perhaps, but what you showed is a linked list, each member of which just happen to have a different linked list:

otu → rep → rep → ... → rep → ?
 ↓
otu → rep → rep → ... → rep → ?
 ↓
otu → rep → rep → ... → rep → ?
 ↓
otu → rep → rep → ... → rep → ?
 ↓
otu → rep → rep → ... → rep → ?
 ↓
(?)

Yes, this is the exact frame I worked with.

Originally Posted by Nominal Animal

The question is, what do the question marks point to? The end of the otu list does not matter, that's why I put it in parentheses.

The ? points to the end. Sorry, I didn't understand properly.

Originally Posted by Nominal Animal

If each rep node is part of exactly one list, then you should have a similar inner loop to free each rep entry, too.

If the rep nodes form a single singly linked list, with the otu nodes just specifying specific nodes in the rep lists, then you should leave the rep lists alone when freeing otu nodes. Instead, you'd need a second function, that frees the rep list just like you free the otu list now. Of course, you'll also need to store the pointer to the first rep somewhere, because you cannot rely on having any otu nodes to keep track of it.

Sorry, I am unable to decipher you.
My struct O.T.U has pointer to rep list's start (the grid you showed).

I can do something like:

while otu list:
pick the otu node
free its rep list //this was main query, if should I do this or not?
free the otu node

Thanks much for your attention to my query, and reply.

Originally Posted by deathmetal

The ? points to the end. Sorry, I didn't understand properly.

You say you are trying to free a 2D linked list. I say your data structure is not a 2D linked list. It is something else. What it is, we don't know, because you didn't say.

I suspect you have a linked list, where each node contains another linked list, but I'm not sure. I tried to ask. There are other possibilities too, more common ones, and you did not give enough information to be certain.

For example, the nodes in the otu list could just refer to specific nodes in the rep list, with otu nodes forming one independent list, and rep nodes forming another independent list, thus:

This is very common in practice.

What you should do when freeing the otu list, depends entirely on how the otu and rep nodes are related. Which you didn't describe. Thus, we cannot help with this, until you describe exactly how you intend to use your data structures.

For example, if each otu list contains a separate rep list, you could describe it something like this:

I have a singly-linked list of otu nodes. Each otu node can contain a singly-linked list of rep nodes. (Each rep node belongs to exactly one list.)

If your structure is like the image shown above, then

I have one singly-linked list of otu nodes, and another singly-linked list of rep nodes. The otu nodes refer to some rep nodes (actually in order, but possibly skipping some nodes).

Or, who knows, perhaps you have something as arcane as

I have one or more singly-linked lists of otu nodes, which refer to one shared singly-linked ring of rep nodes. There is no separate handle for the rep ring; I want to free it automatically when the last otu node referring to the ring is freed.

Even this last one matches your question!

If you find it difficult to frame things technically like above, use analogies, or give more detail:

I have a singly-linked list of otu nodes, each one describing one type of microbe. Each microbe may have a list of samples it was found in, stored as a singly-linked list of rep nodes.

To repeat:

Whether you should or should not free the rep list when freeing the corresponding otu node, depends entirely on how you use your data structures.

In that case, yes, you should have an inner loop to free the rep list too:

Code:

void free_rep_list(struct rep *list)
{
    while (list != NULL) {
        struct rep *const curr = list;
        list = list->next;

        /* "Poison" entry before freeing it.
         * This helps in detecting use-after-free bugs.
        */
        curr->number = -1;
        curr->count = -1;
        curr->next = NULL;

        free(curr);
    }
}

void free_otu_list(struct otu *list)
{
    while (list != NULL) {
        struct otu *const curr = list;
        list = list->next;

        /* Discard rep list, if any. */
        free_rep_list(curr->rep_seq);

        /* "Poison" data, then free it. */
        curr->otu_number = -1;
        curr->next = NULL;
        curr->rep_seq = NULL;
        free(curr);
    }
}

Although you could insert the rep list free loop within the function, it is much more manageable to put it in a separate function, as I did above. It should be easy to read and understand, and thus easy to maintain in the long term. ("Long term".. make that anything longer than a couple of weeks.)

Poisoning the entry before freeing it is a very easy and simple way to make sure you don't accidentally rely on being able to access recently freed data. It costs very, very little in CPU time used; certainly not enough to matter. It is surprisingly easy to accidentally use already freed data, especially if you use temporary pointers to the nodes in complex code. Such code usually stops working the next time you try to compile and run the code -- or, when your teacher/lecturer/advisor/peer tries to compile the code, and all you can say is "it works on my machine, it must be something wrong on your end". Which is not good at all.

There is no need to poison all data, really; the pointers and whatever critical fields it has, suffice. (That is, the minimum set of fields that all code has to access, when accessing the node).

Hello Nominal,
Thanks much for your support and explaining.

- I've Never seen or read about poisoning data else where.

- I've following queries:
1) Please see the comment I've added for creating pointer in free_rep_list
Why not have a single pointer initialization just after we enter the function?

2) Why have you used const pointer, if we're ultimately free-ing the node?
Thanks.

Originally Posted by Nominal Animal

In that case, yes, you should have an inner loop to free the rep list too:

Code:

void free_rep_list(struct rep *list)
        //struct rep *curr = list;
//why not start a point at the start, so that will help not create multiple times?
{
    while (list != NULL) {
        struct rep *const curr = list; //remove this line 
        list = list->next;

        /* "Poison" entry before freeing it.
         * This helps in detecting use-after-free bugs.
        */
        curr->number = -1;
        curr->count = -1;
        curr->next = NULL;

        free(curr);
    }
}

Poisoning the entry before freeing it is a very easy and simple way to make sure you don't accidentally rely on being able to access recently freed data. It costs very, very little in CPU time used; certainly not enough to matter. It is surprisingly easy to accidentally use already freed data, especially if you use temporary pointers to the nodes in complex code. Such code usually stops working the next time you try to compile and run the code -- or, when your teacher/lecturer/advisor/peer tries to compile the code, and all you can say is "it works on my machine, it must be something wrong on your end". Which is not good at all.

Originally Posted by deathmetal

I've Never seen or read about poisoning data else where.

It is a common technique in memory management. Just look up memory poisoning.

Originally Posted by deathmetal

Why not have a single pointer initialization just after we enter the function?

Because that would not work. Note that my code does not use global variables, either.

There are two approaches how you can traverse a list while releasing the nodes in it. One is recursive, and utterly silly, and the other uses a loop and a temporary pointer to hold a reference to the node that is to be released. We need the temporary pointer, because we detach the element from the list, and move on to the next. If we didn't use a temporary pointer (nor a recursive function call), we would try to access already freed memory (namely, the next field in the structure).

Originally Posted by deathmetal

Why have you used const pointer, if we're ultimately free-ing the node?

Only the curr variable itself is constant (as it won't be modified during its scope). The data it points to is not const, so there is no problem whatsoever.

Look. If you have four pointers,

char *a;
const char *b;
char *const c;
const char *const d;

then it is okay to modify the data pointed to by a and c, including freeing them if they were dynamically allocated; the data pointed to by b and d is immutable/constant/read-only. You can change where a or b point to, but you cannot change where c or d point to. So, all four are different.

When reading pointer qualifiers, you read them from right to left, delimited by asterisks '*' (which you read as a pointer to between the right and left sides).

This means that you can read the above as

a is a pointer to char
b is a pointer to const char
c is a const pointer to char
d is a const pointer to const char

Note that "const pointer" refers to a pointer you cannot change -- that is, you cannot change where such a pointer points to --, and "const char" refers to constant data, chars you cannot change.

Originally Posted by Nominal Animal

Look. If you have four pointers,

char *a;
const char *b;
char *const c;
const char *const d;

then it is okay to modify the data pointed to by a and c, including freeing them if they were dynamically allocated; the data pointed to by b and d is immutable/constant/read-only. You can change where a or b point to, but you cannot change where c or d point to. So, all four are different.

It's sometimes useful also to free a pointer to const, such as b and d. I do that all the time--I'll dynamically allocate an object, initialize it, and then assign it to a pointer to const to ensure that I don't modify it later; when I'm done with it, I free it as usual. Unfortunately, the C standard is faulty in that free() takes a pointer to non-const void, rather than a pointer to const void. The Linux kernel equivalent, kfree(), gets it right and takes a pointer to const void. You'll have to cast away the const to avoid compiler warnings.

Originally Posted by christop

It's sometimes useful also to free a pointer to const, such as b and d. I do that all the time--I'll dynamically allocate an object, initialize it, and then assign it to a pointer to const to ensure that I don't modify it later; when I'm done with it, I free it as usual. Unfortunately, the C standard is faulty in that free() takes a pointer to non-const void, rather than a pointer to const void. The Linux kernel equivalent, kfree(), gets it right and takes a pointer to const void. You'll have to cast away the const to avoid compiler warnings.

Hi chris,
Thanks for adding valuable points. That helps.

Hello nominal,

Thanks much for confirming on my free-ing code. That keeps me going, correctly.

Appreciate your supportive reply.

Originally Posted by Nominal Animal

What I do not like, is drive-by claims with zero basis, substance or reasoning behind them, and especially totally ignoring it when pointed out, and not admitting to erring in any way. It feels like opinions are treated as somehow equal to verifiable facts, and I don't like it. To me, this is technical discussion, not idle chit-chat where everyone is entitled to have their opinion heard. I can never agree with a demonstrably false statement, and I do get irrationally irritated when others do; that's why I feel I need to ignore some members here. (To keep myself in check.)

I'm pretty sure you're referring to me. Ok, so you want some basis/substance/reasoning behind my post. Here it is.

TL;DR summary: Linux, C++, Unix file systems, and probably many other systems have no problem with deleting a const/read-only object, and C has no problem with freeing an automatically-allocated const object. So why does (or why should) C have a problem with dynamically freeing a const object?


Most of what I want to say about the subject has already been discussed at length so I will quote salient posts about it and include some of my own commentary afterwards.

This discussion is in reference to the Linux memory allocation system but mentions the C memory allocator. Here is the Linux memory allocator API (static/inline/other qualifiers removed for clarity):

Code:

void *kmalloc(size_t, gfp_t);
void *krealloc(const void *, size_t, gfp_t);
void kfree(const void *);

The only major difference is that kmalloc() and krealloc() take an extra argument that tell the allocator how and where to allocate memory, and kfree() takes a pointer to const void (which I've pointed out already as a flaw in the standard). Otherwise the memory allocator is virtually the same as C's malloc()/free(). They're conceptually identical. (Note that the memory allocator in C++ is also conceptually similar, the only major difference being that it also invokes a class's constructor and destructor; the "delete" keyword, like kfree(), also allows you to delete a pointer to const.)

(Both quotes are from Linus Torvalds.)

https://lkml.org/lkml/2008/1/16/227:

In the particular case of kfree(), the pointer argument *should* be const,
and the fact that the C library gets this wrong is not the kernels
problem, it's a problem with the C library.

Why?

- From a very obvious and very *real* caller perspective, "free()" really
doesn't change the thing the pointer points to. It does something
totally different: it makes the *pointer* itself invalid.

In other words, if you think that "kfree()" changed the thing you
free'd, you're simply wrong. It did no such thing. The memory is 100%
the same, it's just that you cannot access it any more, and if you try,
you'll get somebody elses memory.

In other words, "kfree()" can be const.

- Anything that *can* take a const pointer should always do so.

Why? Because we want the types to be as tight as possible, and normal
code should need as few casts as possible.

Here's a question for you: let's say that you have a structure that
has a member that is never changed. To make that obvious, and to allow
the compiler to warn about mis-use of a pointer, the structure should
look something like

Code:

        struct mystruct {
            const char *name;
            ..

and let's look at what happens if the allocation of that const thing is
dynamic.

The *correct* way to do that is:

Code:

        char *name = kmalloc(...)
        /* Fill it in */
        snprintf(name, ...)
        mystruct->name = name;

and there are no casts anywhere, and you get exactly the semantics you
want: "name" itself isn't constant (it's obviously modified), but at
the same time the type system makes it very clear that trying to change
it through that mystruct member pointer is wrong.

How do you free it?

That's right, you do:

Code:

        kfree(mystruct->name);

and this is why "kfree()" should take a const pointer. If it doesn't,
you have to add an *incorrect* and totally useless cast to code that
was correct.

https://lkml.org/lkml/2008/1/18/287:

Here's an idea. Think it through.

Why don't we need write permissions to a file to unlink it?

Here's a hint: because unlinking doesn't *write* to it. In fact, it
doesn't read from it either. It doesn't do any access at all to that
object, it just *removes* it.

Is the file gone after you unlink it? Yes (modulo refcounting for aliasing
"pointers" aka filenames, but that's the same for any memory manager -
malloc/free just doesn't have any, so you could think of it as a
non-hardlinking filesystem).

Here's another point of fact: C has no problem freeing a variable declared as const. Proof:

Code:

void foo()
{
    const int x = 42;

    printf("%d\n", x);
}

In this example, C automatically allocates memory for an int named 'x'. It is declared const, so it cannot be modified after it comes into existence. Then it is freed when it goes out of scope. The const does not and cannot save it from being freed automatically when it goes out of scope. (I'm talking purely of the C abstract machine. A real implementation might convert the function into a single puts("42") as an obvious and legal optimization; the externally-visible side effects would be identical.)

Here's an analogous example, this time using dynamic memory allocation:

Code:

// free_const() exists solely because of the aforementioned problem
// with free()
void free_const(const void *v)
{
    free((void *)v);
}

int *create_int(int value)
{
    int *x = malloc(sizeof *x);
    assert(x != NULL);
    *x = value;
    return x;
}

/*
 * This is like foo() in the previous example. We dynamically create
 * and initialize an int that we have no interest in modifying after
 * it's initialized, so we save the pointer to a pointer-to-const
 * variable. Then we print the pointed-to object and then free it.
 *
 * We could instead return the pointer or save it in a data structure,
 * then another function would free it at some later time.
 */
void foo()
{
    const int *x = create_int(42);

    printf("%d\n", *x);

    free_const(x);
}

So why would C have no problem freeing a const object that was allocated automatically but have a problem (only according to the free() function's prototype) with doing the same to a const object that was allocated dynamically? And why do neither the Linux kernel nor C++ have the same limitation in their respective memory allocation systems? That's simply an inconsistency in the prototype of free().

Obviously, passing around a pointer to a single int object is kind of silly (there are some good reasons to do so, but that's neither here nor there), but you can use this exact same technique to pass around larger and more complex objects, such as strings and other data structures that you don't want to modify after they are initialized.

I use that pattern with strings all the time--I obtain a string from an outside source, perhaps from a device or from the user or from an Internet host, and then I save the string to a list or some other structure that I can use later with read-only strings, and then when I'm done with the string I simply free it. Since C's free() takes a non-const pointer, I work around it by defining something like free_const() to cast away the const from the pointer and pass it to free(), as I did in my example.


Anyway, Nominal Animal, here's an extremely simple programming problem for you. I give you this structure definition and function skeleton:

Code:

// All strings in this structure are dynamically allocated.
// This is similar to Linus's struct mystruct in the example above.
struct person {
    const char *first_name;
    const char *last_name;
};

// Free a dynamically-allocated person structure and all fields within
// it. This function does not modify the pointed-to person object.
void free_person(const struct person *p)
{
    // your code goes here
}

How would you implement free_person()?

Here's my implementation:

Code:

void free_person(const struct person *p)
{
    free_const(p->first_name);
    free_const(p->last_name);
    free_const(p);
}

Couldn't be easier!

Can you find a problem with any point I've made?

Dude, stop distracting Nominal. I need him to help me with Apache directory index files, not dilly dally with C and malloc() and free().