list.h 파일을 보니까
연결리스트에 tail을 찾아주는 함수나 매크로는 없더군요,, Tail을 어떻게 찾아야할까요"??
다음 entry가 NULL이 나올 때까지 계속 list를 traverse해야 할 거 같네요. 그런데 커널의 linked list는 sys/queue.h 에 정의되어 있는 줄 알았는데, 아닌가요? queue.h 에 있는 tail queue 를 쓰시면 tail을 바로 찾으실 수 있어요. ---- Let's shut up and code.
---- Let's shut up and code.
저도 사용을 안 해봤지만, ->prev로 접근하면 안 되나요?
list 전체를 traverse하면 complexity가 O(n)이 될 것 같네요.
리스트란게 원래 그런거죠 :-) 물론 더 효율적으로 할 수 있지만, 그러면 단순함을 희생해야 하구요. 역시나 적절한 곳에 적절한 자료구조- 가 답이 되겠습니다. ---- Let's shut up and code.
커널에서 사용하는 Linked List는 doubly linked list로 알고 있습니다.
list의 head에서 prev로 찾아가면 바로 tail을 찾을 수 있을 것 같습니다.
sys/queue.h 에는 singly, doubly, circular list가 모두 있는 것으로 알고 있습니다.
코드를 보니 커널에서 사용하는 list라면 head에서 prev 참조 한번(O(1))으로 tail이 나오겠는데요.
거기에 있는 hlist면 전체를 끝까지 traverse해야 할 것 같구요.
sys/queue.h 는 글쓴분이 질문하신 커널과는 무관한 부분이네요.
혹시... list_first_entry() 는 있는데, 왜 list_last_entry() 는 없냐는 뜻의 질문이라면...
먼저, list_first_entry() 는 비교적 최근에 들어온 매크로라는 것을 말씀드리겠습니다. hlist 보다도 나중에 들어온 신상입니다.
그리고, 그 매크로의 활용도가 그리 크지 않다는 것을 말씀드리겠습니다. 대강 이런식입니다
while (!list_empty(&my_head)) { my_data = list_first_entry(&my_head, my_data_t, list_node); list_del(&my_data->list_node); (...) }
(빼먹은 게 있어서 추가합니다) 성능 개선의 목적외에 한가지 용도가 더 있긴 합니다.
LOCK(); while (!list_empty(&my_head)) { my_data = list_first_entry(&my_head, my_data_t, list_node); list_del(&my_data->list_node); UNLOCK(); (...) LOCK(); } UNLOCK();
LOCK(); list_for_each_entry_safe(my_data, tmp, &my_head, list_node) { list_del(&my_data->list_node); UNLOCK(); ... LOCK(); } UNLOCK();
OTL
텍스트 포맷에 대한 자세한 정보
<code>
<blockcode>
<apache>
<applescript>
<autoconf>
<awk>
<bash>
<c>
<cpp>
<css>
<diff>
<drupal5>
<drupal6>
<gdb>
<html>
<html5>
<java>
<javascript>
<ldif>
<lua>
<make>
<mysql>
<perl>
<perl6>
<php>
<pgsql>
<proftpd>
<python>
<reg>
<spec>
<ruby>
<foo>
[foo]
다음 entry가 NULL이
다음 entry가 NULL이 나올 때까지 계속 list를 traverse해야 할 거 같네요.
그런데 커널의 linked list는 sys/queue.h 에 정의되어 있는 줄 알았는데, 아닌가요?
queue.h 에 있는 tail queue 를 쓰시면 tail을 바로 찾으실 수 있어요.
----
Let's shut up and code.
----
Let's shut up and code.
저도 사용을 안
저도 사용을 안 해봤지만, ->prev로 접근하면 안 되나요?
list 전체를 traverse하면 complexity가 O(n)이 될 것 같네요.
리스트란게 원래
리스트란게 원래 그런거죠 :-)
물론 더 효율적으로 할 수 있지만, 그러면 단순함을 희생해야 하구요.
역시나 적절한 곳에 적절한 자료구조- 가 답이 되겠습니다.
----
Let's shut up and code.
----
Let's shut up and code.
커널에서 사용하는 Linked List는 doubly linked list로 알고 있습니다.
커널에서 사용하는 Linked List는 doubly linked list로 알고 있습니다.
list의 head에서 prev로 찾아가면 바로 tail을 찾을 수 있을 것 같습니다.
...
sys/queue.h 에는 singly, doubly, circular list가 모두 있는 것으로 알고 있습니다.
코드를 보니
코드를 보니 커널에서 사용하는 list라면 head에서 prev 참조 한번(O(1))으로 tail이 나오겠는데요.
거기에 있는 hlist면 전체를 끝까지 traverse해야 할 것 같구요.
sys/queue.h 는 글쓴분이 질문하신 커널과는 무관한 부분이네요.
혹시... list_first_entry()
혹시... list_first_entry() 는 있는데, 왜 list_last_entry() 는 없냐는 뜻의 질문이라면...
먼저,
list_first_entry() 는 비교적 최근에 들어온 매크로라는 것을 말씀드리겠습니다.
hlist 보다도 나중에 들어온 신상입니다.
그리고,
그 매크로의 활용도가 그리 크지 않다는 것을 말씀드리겠습니다. 대강 이런식입니다
while (!list_empty(&my_head)) { my_data = list_first_entry(&my_head, my_data_t, list_node); list_del(&my_data->list_node); (...) }사정이 이렇다보니 first 건 last 건 아무거나 하나만 있으면 되는지라 list_last_entry() 는 없습니다.
(빼먹은 게 있어서 추가합니다)
성능 개선의 목적외에 한가지 용도가 더 있긴 합니다.
LOCK(); while (!list_empty(&my_head)) { my_data = list_first_entry(&my_head, my_data_t, list_node); list_del(&my_data->list_node); UNLOCK(); (...) LOCK(); } UNLOCK();LOCK(); list_for_each_entry_safe(my_data, tmp, &my_head, list_node) { list_del(&my_data->list_node); UNLOCK(); ... LOCK(); } UNLOCK();OTL
댓글 달기