[pintOS] - list 라이브러리 고찰

list_begin VS list_front

list_begin

/* Returns the beginning of LIST.  */
struct list_elem *
list_begin (struct list *list) {
	ASSERT (list != NULL);
	return list->head.next;
}

list_front

/* Returns the front element in LIST.
   Undefined behavior if LIST is empty. */
struct list_elem *
list_front (struct list *list) {
	ASSERT (!list_empty (list));
	return list->head.next;
}

차이

• list_begin은 초기화 여부(list_init)만 확인(ASSERT) 하고 head.next를 반환한다. 즉 tail이 반환될 수도 있다.
• list_front는 list_empty여부 (!list_begin==list_tail) 를 확인하여 첫번째 요소를 반환한다. 즉 비어있는 리스트에 쓰면 에러난다.

고찰

• list 라이브러리 내부 함수 구현용으로는 list_begin이 유용하겠지만, list를 가져다 쓰는 main 입장에서는 list가 비어있지 않은 경우에 순회를 도는 로직이 많으므로 empty여부 확인 후 list_front를 쓰는 것이 많을 것 같다.
• list_begin으로 head.next를 구한 후 tail이 아닌 동안 while문을 도는 패턴도 활용 가능하다.

list_remove 주의점

list_remove

struct list_elem *
list_remove (struct list_elem *elem) {
	ASSERT (is_interior (elem));
	elem->prev->next = elem->next;
	elem->next->prev = elem->prev;
	return elem->next;
}

주의점

• head, tail이 아닐 때만 동작한다. ASSERT를 뱉는다면 empty를 제대로 확인 안했거나, 반복문을 돌면서 tail을 만났는데 remove하려고 한 경우이다.
• list_elem은 제거되지만 elem→next는 여전히 원래의 next를 가리킨다.
  • 함수에서도 이를 이용해, 다음 elem을 반환한다.
  • 리스트에서 이미 제거된 elem도 리스트의 일원인척 할 수 있으므로 주의
• return값으로 제거된 elem이 아니라 그 다음 elem을 가리킨다.

list활용 구현 패턴

전체 순회 패턴

struct list_elem* elem = list_begin(list);
struct list_elem* next_elem;
while(elem!=list_tail(list)){
	next_elem = list_next(elem); // next가 바뀌기 전 저장
	
	//순회 본문. 삭제, 삽입 등이 일어날 수 있음

	elem = next_elem;
}

• 단순 제거라면 next_elem이 필요하지 않겠지만, 제거 후 해당 elem이 다른 리스트로 들어가게 된다면 필요하다.
• next_elem = remove_list(elem) 코드를 써도 무방하다.
  • 하지만 조건부 삭제라면 next_elem 갱신 없이 무한루프를 돌 수 있으므로 위의 패턴이 더 일반적인 패턴이다.

제거 패턴

while (!list_empty (&destruction_req)) {
		struct thread *victim =
			list_entry(list_pop_front (&destruction_req), struct thread, elem);
		// free(victim->donor_list);
		palloc_free_page(victim);
	}