Reading: List Code

Reading: Examples/list.h, Examples/list.c

Please submit a question by 9 p.m. on Thursday, 28 April 2011.

What is list_foreach actually doing? Is it like the for-each procedure in Scheme?

Yes, that's the intent.

Is there an easier way to make a repeated list as in Scheme's (make-list n val)?

It's pretty straightforward to write one.

struct list *
make_list (int n, char *val)
{
  struct list *lst = list_new ();
  for (i = 0; i < n; i++)
    list_prepend (lst, val);
  return lst;
} // make_list

Why didn't you put the globals in the header file?

So that I can include the header file in multiple places.

What is the following statement in list_new for?

  if (lst == NULL) return NULL;

We allocate space for lst with malloc. As we've discussed, malloc can fail. If it fails, it returns NULL. So we use the same failure message. If we don't do that, the line that assigns to lst->head will cause a segfault.

If we have list_insert do we really need list_append?

Yes. The precondition of list_insert is that the position is less than the length of the list and it inserts before that position.

How is list_foreach implemented?

I'm not sure that I understand this question. The implementation is right there.

In what situations would it be more effective (and for what reasons) to use a linked list instead of an array?

When you want to grow the collection.

Is there full code for list_delete and list_cut somewhere on the course website?

No. We'll develop list_cut in class. You'll write list_delete in the lab.

Does list_cut preserve the original list?

No.

Say list_cut is called multiple times with different values of n on the same list. Would the first instance produce a list of length - 1 and the second of length - 2 or would both just have one value missing?

Since list_cut modifies the list, the first call will remove one element and the second will remove another. The list will be two elements shorter.

list_cut and list_delete seem very similar. Is the only difference that list_delete searches for a specific string?

One deletes by position, the other by content.

Is the purpose of list.c is to make lists? By adding, deleting, or combining other lists to make one bigger list?

The purpose of list.c is to enable the client programmer to work with lists - user-ordered, dynamically sized sequences of values.

I do not understand this code.

void
list_foreach (struct list *lst, int (*fun)(char *))
{
  struct node *current = lst->head;
  while (current != NULL)
    {
      fun (car (current));
      current = cdr (current);
    } // while
} // list_foreach

Okay, let's see. fun is a function that you apply to strings. We step through the list, grabbing values car (current) and applying the function. We advance to the next node using cdr.

I understand the actual code quite well but I am still a bit unclear with how all the macros are used.

EXPERIMENT is used when we want to see what happens when we execute a line of code. It prints out the line and then executes it. PRINT_INT and similar functions are used to check results created by the lines we experiment with. By combining these, we can print out a list of steps we're doing and the values we get from that. (A debugger will do the same thing, but I find this easier to look at.)

CHECK_INT is used for unit testing. It checks whether two integers are the same and reports an error (and increments the count of errors) if they are not). There's also a CHECK_PTR and CHECK_STR.

Freeing Memory

What does free (garbage) do?

free is the counterpart to malloc. If you allocate memory, you have a responsibility to free it when you're done. (I made a joke about that in class on Wednesday.) If you don't call free, eventually you'll run out of memory. Even if you don't run out of memory, you'll still clog up your user's computer.

Is free defined somewhere else? Or is it already in one of the standard libs?

You can tell that it's part of the standard libraries by writing man 3 free.

In list_clear, I don't see what the point of garbage is. Am I interpreting it wrong? Or is it just giving garbage something and then immediately dumping it out with free?

You are correct that we are repeatedly having garbage point somewhere and then immediately freeing that location with free. But we're not allocating when we have garbage point somewhere. Instead, we're pointing it somewhere that we know was previously allocated. That is, since all of the nodes in the list were created with cons, and cons calls malloc, the nodes were allocated with malloc.

I'm confused about the difference between list_clear and list_free. What distinguishes them?

Could you explain the list_clear and list_free programs?

list_clear removes all the elements, but leaves the list there so that we can add new elements if we wish. list_free frees all the memory associated with the list. After list_free, it would be a bad idea to use the list.

When can list_free be more useful than list_clear?

If you're never going to use the list again, you have a responsibility to free the memory associated with it.

In list_free(struct list* lst) you set all the values to NULL first. Is it safe to assume that free will do this automatically? I see that in your comments you say it's safer and I was wondering why that was? Is it just considered a good practice to avoid memory leaks?

I don't set them to NULL first. I set them to NULL retrospectively. free does not set them to NULL. I do so so that the client does not accidentally attempt to access them.

Questions That Are Hard To Address

Could I come in during your office hours and go through this code with you? I'm having a hard time with it.

I am booked in office hours today, but Monday should work. You should also figure out some more after class and lab.

Are the libraries you are using in a file we cannot see? Such as mem.h?

Everything should be in Examples/Lists.

Is this actually supposed to compile?

Yes. It compiles. Just type make.

What does -> do?

Given a pointer to a structure, it gets a field of that structure. But you should know this by now. It's in the book. We've used it in class (repeatedly). It's in a previous set of answers.

Code Errors

Shouldn't list_prepend follow the structure of list_append for incrementing length, and doing more book-keeping stuff if the list was originally empty?

Yes, list_prepend should increment length. You may recall that there were two calls to increment length in list_append. I think the line moved from one function to the other. I blame gremlins. I've fixed it, at least for the time being.

Alternately: That was a test to see how closely people were reading. You are the only one who passes.