[c/c++][linux]list (2)

https://hiro99ma.blogspot.com/2019/05/cclinuxlist.html

さて、LinuxならOSが提供しているLIST機能が使えることが分かった。
他にもあるのだが、まあ、今回はLISTでよかろう。

新しい要素を追加したい場合、3つの方法がある。

• LIST_INSERT_AFTER
• LIST_INSERT_BEFORE
• LIST_INSERT_HEAD

LIST_INSERT_HEADは無条件で先頭に追加していく。
LISTだから、なんとなくFIFOのような気になるのだが、一方向しかないので、先頭から順番にたどるしかなさそうだ。
先頭からたどる方式で、先頭に追加するのだったら、それはFILOみたいなもんだ。stackだ。

データはLIST_FOREACHでぐるぐる見ていったり、LIST_NEXTで次の要素をたどったりできるので、LIST_INSERT_AFTERやLIST_INSERT_BEFOREを使えば好きな位置に追加できる。
LISTは先頭しかないから、特定の位置まではたどっていくしかない。
末尾に毎回追加するのであれば、最後の要素のアドレスを持っておくとよいのかもしれんな。

---

さて、では毎回末尾に追加したいとしよう。
しかし、初回だけは要素がない。
だからLIST_INSERT_HEADとLIST_INSERT_AFTERを使い分けていたのだが、格好の良い書き方ができないのか？と思ったのが今回の記事だ。

ただ・・・sys/queue.hを見ると、lh_firstで先頭要素を取得し、あとは各要素のle_nextで進んでいくというだけになっている。
そして、lh_firstに代入しているのはLIST_INSERT_HEADだけで、AFTERとBEFOREはle_nextを継ぎ足すだけだ。
初回かどうかの判断は、いるということか。
追加する頻度が多いなら、最初に空の要素を追加して、あとはLIST_INSERT_AFTERだけにするのもよいかもしれんな。

そして気付いたのだが、le_nextだけでなくle_prevもある。
型はダブルポインタ(le_nextはシングルポインタ)で、le_nextのアドレスを代入している。
LIST_INSERT_BEFOREで使っているんだな。

でも、私は一方向だけでいいのだが・・・なんかもったいない。
と思ったら、LISTの次にSLISTというものがあった。
Singly-linked Listということだから、片方向っぽい。

これで十分そうなのだが、SLIST_REMOVEとSLIST_REMOVE_HEADがあるのが注意点か。
LISTの場合は先頭要素のle_prevがlh_firstを持っていて、先頭がLIST_REMOVEされてもlh_firstを更新することができたのだが、完全に一方向しかないSLISTには前の要素を持つことができないので、使う方が見分けねばならぬのだ。

sizeofでLIST_ENTRYとSLIST_ENTRYを見てみると、LIST_ENTRYは16byte、SLIST_ENTRYは8byteだった(WSL)。
大量にINSERTするなら考慮すべきかもしれん。