さて、intlistを使ってみよう。 #include <stdio.h> #include "intlist.h" #define UNUSED_ARG(x) (void)(x) static int issup(cintelem_t p, cintelem_t q, void *arg) { UNUSED_ARG(arg); return intelem_get_val(p) > intelem_get_val(q); } static intlist_t make</stdio.h>…

計数処理についてなんとかなりそうなのでintlistの全体をコーディングしてみる。 intlist.c #include <stddef.h> #include <stdlib.h> #include <assert.h> #include "listsort.h" #include "intlist.h" #define UNUSED_ARG(x) (void)(x) struct tag_intlist { intelem_t head; unsigned lo</assert.h></stdlib.h></stddef.h>…

さて。#60の最後で書いたように、 > 利用者が提供する比較処理にカウント処理を埋め込むことはできない わけで、それならどうするかを考える必要がある。 利用者が提供する比較処理中に利用者自身が計数処理の埋め込みを強制させないのなら、 リスト側で利用…

インタフェイスで定義した不完全型を具象化する構造体の定義を考える。 struct tag_intlist { intelem_t head; unsigned long compare_counts; unsigned long swap_counts; }; struct tag_intelem { int val; intelem_t next; }; struct tag_intiter { intel…

とりあえず整数値を持つ要素のリストのインタフェイスを宣言しておく。 intlist.h #ifndef INTLIST_H_INCLUDED #define INTLIST_H_INCLUDED typedef struct tag_intlist *intlist_t; typedef const struct tag_intlist *cintlist_t; typedef struct tag_inte…

役に立つといっても単に整列処理時にリスト側で用意した処理が何回くらい呼び出されたかをカウントできるものを、という程度。 この機能はリスト側が用意し、利用者にその情報を提供するようにする。 単なるカウント処理でなく利用者が任意の処理を埋め込め…

計算量の話とかやってるので、それに役立つようなリストを作ってみようと思う。

前回の方針に従ってlistsortを変更する。 インタフェイスは変えないのでヘッダファイルに変更はない。 listsort.c #include "listsort.h" void listsort( void *list, void *(*head)(const void *, void *), void *(*next)(const void *, const void *, void…

実際の整列処理においてはどの程度時間的性能が変化しているのか確かめてみた。 次のような計測プログラムを書いた。 test_ilist2_2.c #include <stdio.h> #include <stdlib.h> #include <time.h> #include "ilist2.h" #define UNUSED_ARG(x) (void)(x) static int issup(ielem_t p, iel</time.h></stdlib.h></stdio.h>…

前回書いた関数prev2をilist2.cに組み込み、適当にリストを整列させてみる。 ilist2.c ...snip static void prev2(ielem_p p1, ielem_p *pp1, ielem_p p2, ielem_p *pp2) { int b1 = 1, b2 = 1; ielem *q = &ilist; *pp1 = *pp2 = NULL; for (;;) { if (b1 &…

前回述べた二つの要素の一つ前の要素を同時に求める関数を書いてみる。 ilist2.cを利用する。 同時に二つの一つ前の要素を求める関数はprev2とする。 test_ilist2_prev.c #include <stdio.h> #include <stdlib.h> #include <time.h> #include <assert.h> #include "ilist2.h" #define UNUSED_ARG(x</assert.h></time.h></stdlib.h></stdio.h>…

ilistやilist2、ilist3で定義している関数prevは、 与えられた要素の一つ前の要素を返す関数だが、 単連結リストであるがゆえにその時間計算量は要素数の一次オーダーになる。 この性能は純粋な単連結リストであれば緩和のしようがないと思う。 ここでの問題…

以前に行ったようにインタフェイスを介さずに参照からリストの情報を見たり操作したりできるだろうか。 #include <stdio.h> #include <stdlib.h> #include <time.h> #include "ilist3.h" #define UNUSED_ARG(x) (void)(x) static int issup(ielem_t p, ielem_t q, void *arg) { UNUSED_A</time.h></stdlib.h></stdio.h>…

ilist3を使用してみる。 ilist2を用いたサンプルコードtest_ilist2.cと同じことをilist3を使って行うコードを書いてみる。 $ diff test_ilist2.c test_ilist3.c 6c6 < #include "ilist2.h" --- > #include "ilist3.h"が、test_ilist2.cとの違いは単に用いる…

ilist3を実装してみよう。 ilist2では静的に定まっている数の要素を配列に格納するようにしていた。 そこで、要素の参照として配列のインデックスを用いることにする。 ilist3.c #include <stddef.h> #include <stdlib.h> #include <assert.h> #include "listsort.h" #include "ilist3.h" #</assert.h></stdlib.h></stddef.h>…

参照として要素のアドレスを利用するリストの問題点を前回書いた。 そこで、ilist2と同様の機能を持つが、アドレスを外部に晒さない単連結リストilist3を考えてみる。 まずは、そのインタフェイスから考える。 ilist3.h #ifndef ILIST3_H_INCLUDED #define I…

ilist2は要素の参照としてそのアドレスを返している。 なので、このようなことができる。 #include <stdio.h> #include <stdlib.h> #include "ilist2.h" static void print(void) { ielem_t p; for (p = ihead(); iisvalid(p); p = inext(p)) printf("%d ", ival(p)); putchar('</stdlib.h></stdio.h>…

これまでリストの要素の参照という言葉で抽象的に表現していたが、 結局のところ要素へのポインタでもってしか実装してこなかった。 ばっさり、アドレスをもって要素の位置とすることにしてしまってもいいかもしれないが。 ただ、アドレスを直接晒す実装では…

関数内で変更がなされない引数には積極的にconstを付けるのは、 誤りを予防するのに役立つため悪くないことだと思う。 test_sclist.cローカルの関数printについても、 リストの内容を変更することはないので、 引数listの型をsclist_t型からcsclist_t型に変…

前回の話に基づいてコードを変更する。 といっても、インタフェイスの見直しだけであり、 引数のうち関数中で変更されるべきでないものと、 呼び出し側で変更されては困るものを返すものを洗い出して、 const修飾した型に変更、もしくはその逆を行う。 sclis…

前回、名前とスコアが要素であるリストsclistに少し言及したので、 少しそのコードを眺めていたら妙ちくりんなことをしているのに気が付いた。 sclistのインタフェイスsclist.hは#23で定義しており、 それを実装したコードsclist.cは#24にある。 また、#25で…

test_ilist.cと同じ処理をするものを書いてみる。 test_ilist2.c #include <stdio.h> #include <stdlib.h> #include <sys/types.h> #include <unistd.h> #include <time.h> #include "ilist2.h" #define UNUSED_ARG(x) (void)(x) static int issup(ielem_t p, ielem_t q, void *arg) { UNUSED_ARG(arg); return </time.h></unistd.h></sys/types.h></stdlib.h></stdio.h>…

ilist2.hに基づいて作ってみる。 が、実際にやっている処理はilistの場合と変わっていない。 単に新しいインタフェイスに合わせているだけである。 ilist2.c #include <stddef.h> #include <stdlib.h> #include "listsort.h" #include "ilist2.h" #define UNUSED_ARG(x) (void)(x</stdlib.h></stddef.h>…

listsortにとっては問題のない関数群を他に開放すると問題を起こしうるということで、 ならば、開放しなければいいということに落ち着く。 リストの要素に関する情報提供の機能を開放したいなら、 listsortへ提供する関数群は開放せず、それと異なる定義の関…

listsortを使うために必要なlistsort.hで定義している関数群head,next,isvalid,swapは、 listsortで使っている分には問題ないのだが、一般に供用するには問題が出てきそうである。 test_ilist.cのprint関数で使っているようなおとなし目の使い方ならいいと思…

listsort内での交換関数swapは前回述べたような使われ方しかしないのだから、 供用すべき交換関数の第二引数pと第三引数qには、 ある要素とその次の要素が与えられるとして実装してしまい、 他でswapの実装を使用する場合はそれ以外の要素の与え方をしてはい…

ilist.cにバグがあった。 要素の交換関数iswapは整列関数listsortで使われる分には問題なく正しく動くのだが、 一般に期待される機能を実現し切れていない。 すなわち、 #include <stdio.h> #include <stdlib.h> #include "ilist.h" #define head ihead(NULL, NULL) #define isv</stdlib.h></stdio.h>…

test_ilist.c #include <stdio.h> #include <stdlib.h> #include <sys/types.h> #include <unistd.h> #include <time.h> #include "ilist.h" #include "listsort.h" #define UNUSED_ARG(x) (void)(x) static int issup(const void *p, const void *q, void *arg) { UNUSED_ARG(arg); return ival(p) > ival(q); </time.h></unistd.h></sys/types.h></stdlib.h></stdio.h>…

リストを実装してみる。 ilist.c #include <stddef.h> #include <stdlib.h> #include "ilist.h" #define UNUSED_ARG(x) (void)(x) typedef struct tag_ielem ielem; struct tag_ielem { int v; ielem *n; }; #ifndef NELEM #define NELEM 10 #endif static ielem ilist = {0, NUL</stdlib.h></stddef.h>…

作成した整列関数を使ってみるために、 整列関数側で対象のリストが持つべきとしたインタフェイスを備えたリストを作ってみる。 単純に整数値をリストの要素のデータとして持つものにしてみよう。 ilist.h #ifndef ILIST_H_INCLUDED #define ILIST_H_INCLUDE…