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;
}

Solution:

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

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

To print the list in reverse order, we use list_rbegin() to get the last element of the list, and then use list_prev() to iterate backwards until we reach list_rend() (the head of the list).

Question 2: list_entry()

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

Solution:

The list_entry() macro converts a pointer to a list element into a pointer to the structure that contains that list element. In the code, list_entry(e, struct pair, elem) takes the list element pointer e and returns a pointer to the struct pair that contains that list element.

This macro works by calculating the offset of the list element within the containing structure, and then subtracting that offset from the address of the list element to get the base address of the containing structure. This allows us to access the fields of the containing structure (like name and value in the pair struct) after finding a list element.

This design pattern allows the list implementation to be generic, while still allowing type-specific operations on the list elements. The list implementation only knows about list_elem structures, but using the list_entry() macro lets us access the containing structures that have application-specific data.

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).

Solution:

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);
}

To sort in reverse alphabetical order, we simply change the comparison from < 0 to > 0. This way, elements with lexicographically greater values will be considered “less” for the purpose of sorting, resulting in a Z to A order.

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.

Solution:

The two approaches have different time complexities:

1. Reading all lines into a list and then calling list_sort():
   • This approach has a time complexity of O(n log n), where n is the number of lines.
   • According to the implementation in list.c, list_sort() uses a natural iterative merge sort that runs in O(n log n) time and O(1) space.
2. Reading lines and inserting them in order using list_insert_ordered():
   • For each insertion, list_insert_ordered() performs a linear search through the list to find the correct position, which takes O(m) time where m is the current size of the list.
   • For n lines, this results in a worst-case time complexity of O(n²).

Therefore, for large lists, the first approach using list_sort() would be faster since O(n log n) grows more slowly than O(n²).

However, there are some considerations:

• If the input is already nearly sorted, list_insert_ordered() might perform better in practice because it might not need to traverse the entire list for each insertion.
• For small lists, the constant factors and overhead might make the practical difference negligible.
• The list_insert_ordered() approach maintains the list in sorted order at all times, which might be useful if you need to access or display the sorted results while still reading the input.

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?

Solution:

Sentinel nodes (head and tail) in the linked list implementation serve several important purposes:

1. Simplify list operations: They eliminate special cases in list processing. For example, insertion and removal operations don’t need special handling for the first or last element, as every “real” element is always between two other elements (either real elements or sentinels).

2. Reduce edge cases: With sentinel nodes, an empty list still has a well-defined structure (head’s next points to tail, and tail’s prev points to head), so there’s no need to check if the list is empty before many operations.

3. Simplify iteration: Iterating through the list has clean start and end conditions. The loop can start at list_begin() (which is head->next) and end when it reaches list_end() (which is tail).

4. Allow for symmetric operations: The code for traversing forward and backward is symmetric and follows the same pattern.

As noted in the implementation comments, this design allows for operations like list_remove() to be implemented with just two pointer assignments and no conditionals, making the code simpler and less error-prone.

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));
}

Solution:

There are two main issues with this code:

1. Uninitialized pointer: p1 is declared as a pointer to struct pair, but it is never initialized. This means it contains a garbage address, and dereferencing it with p1->name or p1->elem will cause undefined behavior, likely a segmentation fault.

2. Incorrect use of strcpy(): strcpy() expects a pointer to a character array as its first argument, but &(p1->name) takes the address of an already-pointer-like expression. This results in trying to copy the string to the wrong memory location.

Two ways to fix these issues:

Fix 1: Allocate memory dynamically

struct pair *p1 = (struct pair *)malloc(sizeof(struct pair));
if (p1 == NULL) {
  // Handle allocation failure
  return 1;
}

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

Fix 2: Use a stack-allocated structure variable instead of a pointer

struct pair p1;
  
list_init(&dmap);

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

The second solution is often preferable when you don’t need dynamic allocation, as it’s simpler and doesn’t require explicit memory management.

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

}

Solution:

// Remove the first element from the list and add it to the end
struct list_elem *first = list_pop_front(&dmap);
list_push_back(&dmap, first);

Alternatively, without using list_pop_front():

// Remove the first element from the list and add it to the end
struct list_elem *first = list_begin(&dmap);
list_remove(first);  // Remove it from its current position
list_push_back(&dmap, first);  // Add it to the end

Both solutions accomplish the same task, but the first one is more concise as it uses the provided helper function list_pop_front().