Lab03 Problems

Question 1: list_elem

Consider the following C snippet that uses our linked list implementation. Modify this pair_list_print() so that it prints the list in reverse order.

listtest.c

#define STR_LEN 128

struct pair {
  struct list_elem elem;
  char name[STR_LEN];
  char value[STR_LEN];
};

void
pair_list_print(struct list *lp)
{
  struct list_elem *e;

  for (e = list_begin(lp); e != list_end(lp); e = list_next(e)) {
    struct pair *p = list_entry(e, struct pair, elem);
    printf("[%s, %s]\n", p->name, p->value);
  }
  return;
}

Question 2: list_entry()

In the listtest.c code snippet above, what is the purpose of the list_entry() macro? What does it do?

Question 3: less()

The lines_list_less() function is used as a comparator for sorting lines in the sort program:

bool
lines_list_less(const struct list_elem *a, const struct list_elem *b, void *aux)
{
  struct line *ap;
  struct line *bp;

  ap = list_entry(a, struct line, elem);
  bp = list_entry(b, struct line, elem);  
  
  return (strcmp(ap->value, bp->value) < 0);
}

Modify this function to sort lines in reverse alphabetical order (Z to A).

Question 4: sorting

In class we discussed two ways to use the list implementation to sort a list of lines: reading lines from a file into a list then calling list_sort() or readling lines from a file and using list_insert_ordered() to insert each line into the list in sorted order. Is one approach faster than the other? Explain your answer.

Question 5: sentinels

In class we discussed the list.c implementation and how it uses sentinel head and tail nodes. What is the purpose of having these sentinel nodes for every list?

Question 6: memory

Consider the following code snippet. What is wrong with this code? Give two ways we can fix the issue.

#define STR_LEN 128

struct pair {
  struct list_elem elem;
  char name[STR_LEN];
  char value[STR_LEN];
};

int
main(int argc, char *argv[])
{
  struct list dmap;
  struct pair *p1;
  
  list_init(&dmap);

  strcpy(&(p1->name), "google.com");
  strcpy(&(p1->value), "142.251.46.174");
  list_push_back(&dmap, &(p1->elem));
}

Question 7: list operations

Consider this code snippet. Add code that removes the first element of the list and adds it to the end of the list. Note there is a list remove function: struct list_elem *list_remove (struct list_elem *).

#define STR_LEN 128

struct pair {
  struct list_elem elem;
  char name[STR_LEN];
  char value[STR_LEN];
};

int
main(int argc, char *argv[])
{
  struct list dmap;
  struct pair p1;
  struct pair p2;
  struct pair p3;
  struct pair p4;

  list_init(&dmap);

  strcpy(p1.name, "google.com");
  strcpy(p1.value, "142.251.46.174");
  list_push_back(&dmap, &p1.elem);

  strcpy(p2.name, "usfca.edu");
  strcpy(p2.value, "23.185.0.2");
  list_push_back(&dmap, &p2.elem);

  strcpy(p3.name, "mit.edu");
  strcpy(p3.value, "104.90.21.210");
  list_push_back(&dmap, &p3.elem);

  strcpy(p4.name, "openai.com");
  strcpy(p4.value, "13.107.238.57");
  list_push_back(&dmap, &p4.elem);

  // ADD YOUR CODE HERE

}