커널에서 사용하는 연결 리스트에서요,,

jaewonm의 이미지

list.h 파일을 보니까

연결리스트에 tail을 찾아주는 함수나 매크로는 없더군요,,
Tail을 어떻게 찾아야할까요"??

sangwoo의 이미지

다음 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.

dorado2의 이미지


저도 사용을 안 해봤지만, ->prev로 접근하면 안 되나요?

list 전체를 traverse하면 complexity가 O(n)이 될 것 같네요.

sangwoo의 이미지

리스트란게 원래 그런거죠 :-)
물론 더 효율적으로 할 수 있지만, 그러면 단순함을 희생해야 하구요.
역시나 적절한 곳에 적절한 자료구조- 가 답이 되겠습니다.
----
Let's shut up and code.

----
Let's shut up and code.

승원의 이미지

커널에서 사용하는 Linked List는 doubly linked list로 알고 있습니다.

list의 head에서 prev로 찾아가면 바로 tail을 찾을 수 있을 것 같습니다.

clique의 이미지

sys/queue.h 에는 singly, doubly, circular list가 모두 있는 것으로 알고 있습니다.

dorado2의 이미지


코드를 보니 커널에서 사용하는 list라면 head에서 prev 참조 한번(O(1))으로 tail이 나오겠는데요.

거기에 있는 hlist면 전체를 끝까지 traverse해야 할 것 같구요.

sys/queue.h 는 글쓴분이 질문하신 커널과는 무관한 부분이네요.

bushi의 이미지

혹시... 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);
    (...)
 }
list_for_each_entry_safe() 보다 키보드는 좀 더 두드려야하지만 성능은 더 좋습니다.
사정이 이렇다보니 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

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <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].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <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].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <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].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <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].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.