ラベル C言語 の投稿を表示しています。 すべての投稿を表示
ラベル C言語 の投稿を表示しています。 すべての投稿を表示

2011年10月17日月曜日

[CP:AMA] 2 C Fundamentals

Chapter 2: Programing Projects

1.
#include <stdio.h>

int main(void)
{
printf(" *\n");
printf(" *\n");
printf(" *\n");
printf("* *\n");
printf(" * *\n");
printf(" *\n");

return 0;
}


2.
#include <stdio.h>

#define PI 3.14f
#define COEFFICIENT (4.0f / 3.0f)

int main(void)
{
float volume = 0, radius = 0;

printf("Enter the radius of your sphere:");
scanf("%f", &radius);

volume = COEFFICIENT * PI * radius * radius * radius;

printf("The volume of the sphere: %.2f\n", volume);

return 0;
}


4.
#include <stdio.h>

int main(void)
{
float amount = 0;

printf("Enter an amount: ");
scanf("%f", &amount);

printf("With tax added: %0.2f\n", amount * 1.05f);

return 0;
}


5.
#include <stdio.h>

int main(void)
{
float x = 0;

printf("Enter x: ");
scanf("%f", &x);

printf("The answer: %0.2f\n",
3 * x * x * x * x *x +
2 * x * x * x * x -
5 * x * x * x -
x * x +
7 * x -
6);

return 0;
}


6.
#include <stdio.h>

int main(void)
{
float x = 0;

printf("Enter x: ");
scanf("%f", &x);

printf("The answer: %0.2f\n",
((((3 * x + 2) - 5) * x - 1) * x + 7) * x - 6);

return 0;
}


7.
#include <stdio.h>

int main(void)
{
int amount = 0;
int bills20 = 0, bills10 = 0, bills05 = 0, bills01 = 0;

printf("enter a dollar amount: ");
scanf("%d", &amount);

bills20 = amount / 20;
bills10 = (amount - bills20 * 20) / 10;
bills05 = (amount - bills20 * 20 -bills10 * 10) / 5;
bills01 = amount - bills20 * 20 -bills10 * 10 - bills05 * 05;

printf("$20 bills: %d\n", bills20);
printf("$10 bills: %d\n", bills10);
printf(" $5 bills: %d\n", bills05);
printf(" $1 bills: %d\n", bills01);

return 0;
}


8.
#include <stdio.h>

int main(void)
{
float amount_of_loan = 0.0f;
float interest_rate = 0.0f;
float monthly_payment = 0.0f;
float balance_after_first_payment = 0.0f, balance_after_second_payment = 0.0f, balance_after_third_payment = 0.0f;
float monthly_interest_rate = 0.0f;

printf("Enter amount of loan: ");
scanf("%f", &amount_of_loan);
printf("Enter interest rate: ");
scanf("%f", &interest_rate);
printf("Enter monthly payment: ");
scanf("%f", &monthly_payment);

monthly_interest_rate = interest_rate / (100.0f * 12.0f);

amount_of_loan = (amount_of_loan) * (1.0f + monthly_interest_rate);
balance_after_first_payment = amount_of_loan - monthly_payment;
amount_of_loan = (amount_of_loan - monthly_payment) * (1.0f + monthly_interest_rate);
balance_after_second_payment = amount_of_loan - monthly_payment;
amount_of_loan = (amount_of_loan - monthly_payment) * (1.0f + monthly_interest_rate);
balance_after_third_payment = amount_of_loan - monthly_payment;

printf("Balance remaining after first payment: %.2f\n", balance_after_first_payment);
printf("Balance remaining after second payment: %.2f\n", balance_after_second_payment);
printf("Balance remaining after third payment: %.2f\n", balance_after_third_payment);

return 0;
}

2010年7月31日土曜日

[CP:AMA] 7 Basic Types


  • 7.1 Integer Types
    I found no new knowledge.

  • 7.2 Floating Types
    In this book or by C's terminology, the `literals' are called `constants'.

  • 7.3 Character Types
    This section contains nothing new to me.

  • 7.4 Type Conversion
    Just only scanned.

  • 7.5 Type Definitions
    No new knowledge found.

  • 7.6 The sizeof Operator
    No new knowledge found.

  • Q & A
    Mmm, printf can't print the signed values when they are negative.


This chapter seems plane and gentle introduction to the C's type system.
But somewhat boring...

plodding away.

2010年7月24日土曜日

[CP:AMA] 6 LOOPS


  • 6.1 The while Statement
    No new knowledge found.

  • 6.2 The do Statement
    No new knowledge found.

  • 6.3 The for Statement
    I've never used comma expressions...
    "C places no restrictions on the three expressions that control its behavior. Although these expressions usually initialize, test, and update the same variable, there's no requirement that they be related in any way." This is impressive.

  • 6.4 Exiting from a Loop
    No new knowledge found.

  • 6.5 Null Statement
    No new knowledge found.

  • Q & A
    No new knowledge found.


still plodding away...

2010年7月19日月曜日

[CP:AMA] 5 Selection Statements


    Most of C's statements fall into three categories.

    • Selection statements
    • Iteration statements
    • Jump statements

    In another point of view, C's statements classified as below.

    • Single statement

      • Expression statement

    • Compound statement

    This chapter discusses the selection statements and the compound statement.

  • 5.1 Logical Expressions
    No new knowledge found.

  • 5.2 The if Statement
    `if' is a statement, and `? ... :' is an operator or a conditional expression. I see.

  • 5.3 The switch Statement
    No new knowledge found.

  • Q & A
    No new knowledge found.

plodding away.

2010年7月17日土曜日

[CP:AMA] 4 Expressions


    "One of C's distinguishing characteristics is its emphasis on expressions-" Mmm... distinguishing from what? Let's take a tiny survey.

    • Assembly Language: It doesn't seem to have expressions.
    • Fortran: sure. Fortran has expressions in its language specification, but its emphasis is on statements.

    So one can say `for those days that C had been developed C's emphasis on expressions, C's emphasis on expressions is its distinguishing characteristics, except for Lisp'.

  • 4.1 Arithmetic Operators
    No new knowledge found.

  • 4.2 Assignment Operators
    The explanation for side effects is great. I finally understand why the assignment in C is thought to have side effects; because it is an operator or isn't an statement.

  • 4.3 Increment and Decrement Operators
    No new knowledge found.

  • 4.4 Expression Evaluation
    No new knowledge found.

  • 4.5 Expression Statements
    `Expression Statements' is somewhat weird term, but its meaning is clear.
    "C has the unusual rule that any expression can be used as a statement."

  • Q & A
    No new knowledge found.


still plodding away.

2010年7月16日金曜日

[CP:AMA] 3 Formatted Input/Output

An ad hoc introduction to the I/O functions.

  • 3.1 The printf Function

    • "The information that follows the % character specifies how the value is converted from its internal form (binary) to printed form (characters)"; simple but impressive expression.

  • 3.2 The scanf Function

    • I see. scanf is a pattern-matcher.

  • Q & A
    no new knowledge found.


prodding away.

2010年7月11日日曜日

[CP:AMA] 2 C Fundamentals


  • 2.1 Writing a Simple Program
    `cc' of gNewSense.

    sh-3.2$ sudo /usr/sbin/update-alternatives --config cc
    [sudo] password for aka:

    There is only 1 program which provides cc
    (/usr/bin/gcc). Nothing to configure.
    sh-3.2$

  • 2.2 The General Form of a Simple Program

    Very plain and simple explanation about directives, functions and statements! Great!

  • 2.3 Comments
  • 2.4 Variables and Assignment

    • `Variable' is fascinating but troublesome term for beginners.
    • In this book, `variables' is explained as "In C, as in most programming languages, these storage locations are called variables.".
    • This statement seems to correct one as for the C standards. But the concept of variables in Common Lisp is more generalized one. For the present, I don't know the relation of these two concepts. Interesting topic for me.

  • 2.5 Reading Input

    No new knowledge for me found.

  • 2.6 Defining Names for Constants
  • 2.7 Identifiers

    I can't yet believe that beginners are able to understand and distinguish the terms such as names, identifiers, keywords, tokens and symbols at the very beginning of their study of programming languages. Especially the terminology of the C standards seems to have ambiguity in their ontology.

    As for myself, I've already learned Common Lisp, and I've accustomed with relationship of the concept of symbols and the concept of the reader and the evaluator, so I've some feeling like "Though I couldn't tell I really understand what the author wrote, perhaps, these are in the scope of what I've learned in Common Lisp. So move on!", when I've read these sections.

    It doesn't seem hygienic, but anyway, move on.

  • 2.8 Layout of a C Program
  • Q & A
    fun to read!


Still prodding away...

2010年7月6日火曜日

[CP:AMA] 1 Introducing C

Memos; write down interesting topics for myself.

  • 1.1 History of C
    "C99 isn't yet universal" is still true ? According to C99 on Wikipedia, even GCC is still not a compliant implementation. mmm...
  • 1.2 Strengths and Weaknesses of C
    For further reading, I've tried installing lint. But gNewSense seems not to contain it...

    sh-3.2$ aptitude search lint
    p dlint - Checks dns zone information using nameserv
    p fslint - A utility to fix problems with filesystems
    p jlint - A Java Program Checker
    p jlint-doc - Manual for jlint - a Java Program Checker
    p libflint-1.06 - C library for number theory, shared librar
    p libflint-dev - C library for number theory, development f
    p libhtml-lint-perl - Check for HTML errors in a string or file
    p libmarc-lint-perl - Perl extension for checking validity of MA
    p linklint - A fast link checker and web site maintenan
    i A lintian - Debian package checker
    p nslint - Lint for DNS files, checks integrity
    p pylint - python code static checker
    p splint - tool for statically checking C programs fo
    p splint-data - tool for statically checking C programs fo
    p splint-doc-html - tool for statically checking C programs fo
    v weblint -
    p weblint-perl - A syntax and minimal style checker for HTM
    i A xserver-xorg-video-glint - X.Org X server -- Glint display driver
    sh-3.2$

  • Q&A
    No new knowledge found.


Still plodding away.

2010年7月5日月曜日

[CP:AMA] PREFACE

自分なりのポイントをメモ。


  • "Complete coverage of both the C89 standard and the C99 standard."
  • "I've included more information about GCC..."
  • "New coverage of abstract data types" in C.
  • 498 Exercises!
  • "Avoid dependence on a particular machine, compiler, or operating system."
  • the undergraduate level.
  • "Be careful with a starred exercise: either pay close attention and think hard or skip it entirely."


こつこつ。

学習ブログ再開

Twitterを試してみたり、Wiki書いてみたり、業務繁忙だったりと、ずいぶん更新してなかった。

まとめWiki+学習ブログという組み合わせが結構いいかも、と再開してみる。

ただし、業務繁忙は相変わらずなので、超スロウペース。

スロウスタディみたいなものになるのかなぁ。

まずは、一度読んでみたかったK.N.KINGのC PROGRAMMING: A Modern Approachを勉強することにする。

こつこつ。

2009年2月27日金曜日

【Subversion】Subversionにおけるエンコーディングの取扱い

これくらいのまとめを書くのに実は結構な量のソースを読んで七転八倒した。
ソース以外の設計図がないというのはつらい。


Subversionのエンコーディング取扱
--------------------------

Subversionとして文字コード取り扱いの基礎となるのは、

static svn_error_t *
convert_cstring(const char **dest,
const char *src,
xlate_handle_node_t *node,
apr_pool_t *pool);

である。ここでxlate_handle_node_t *nodeが文字コード
の変換を規程するapr_xlate_t *handleを持っている。ち
なみにapr_xlateはAPRのI18N変換ライブラリである。

typedef struct xlate_handle_node_t {
apr_xlate_t *handle;
/* FALSE if the handle is not valid, since its pool is being
destroyed. */
svn_boolean_t valid;
/* The name of a char encoding or APR_LOCALE_CHARSET. */
const char *frompage, *topage;
struct xlate_handle_node_t *next;
} xlate_handle_node_t;

handleは次のよう。

struct apr_xlate_t {
apr_pool_t *pool;
char *frompage;
char *topage;
char *sbcs_table;
iconv_t ich;
};

ここでchar *frompageが変換元文字コードの指定、char
*topageが変換先文字コードの指定である。

さて、handleはget_ntoU_xlate_handle_nodeが作る。

static svn_error_t *
get_ntou_xlate_handle_node(xlate_handle_node_t **ret, apr_pool_t *pool)
{
return get_xlate_handle_node(ret, SVN_APR_UTF8_CHARSET,
SVN_APR_LOCALE_CHARSET,
SVN_UTF_NTOU_XLATE_HANDLE, pool);
}

これはWrapperであり、本体は次のもの。

static svn_error_t *
get_xlate_handle_node(xlate_handle_node_t **ret,
const char *topage, const char *frompage,
const char *userdata_key,
apr_pool_t *pool);

この中で、まずhandleをopenして、

apr_xlate_open(&handle, topage, frompage, pool);

apr_xlate_openによって、handleの中身がどのように
作られるのかというと、

new->ich = iconv_open(topage, frompage);

ということで、とどのつまりtopageとfrompageの組み
合わせで指定してiconvから取得しているのだ。


続いてxlate_handle_node t **retを初期化する。

*ret = apr_palloc(pool, sizeof(xlate_handle_node_t));
(*ret)->handle = handle;
(*ret)->valid = TRUE;
(*ret)->frompage = ((frompage != SVN_APR_LOCALE_CHARSET)
? apr_pstrdup(pool, frompage) : frompage);
(*ret)->topage = ((topage != SVN_APR_LOCALE_CHARSET)
? apr_pstrdup(pool, topage) : topage);
(*ret)->next = NULL;

とする。

さてここで作成されたxlate_handle_node_t型オブジェク
トのhandleメンバがapr_xlate_conv_bufferの引数
convsetとして使われる。


APU_DECLARE(apr_status_t) apr_xlate_conv_buffer(apr_xlate_t *convset,
const char *inbuf,
apr_size_t *inbytes_left,
char *outbuf,
apr_size_t *outbytes_left);

この関数の中身で文字コード変換をしている実体は、
iconvである。(ただしwi32にiconvがないので、それは、
apr_iconvという同梱されているものをつかう)

translated = iconv(convset->ich, (ICONV_INBUF_TYPE)&inbufptr,
inbytes_left, &outbufptr, outbytes_left);

さて、

convert_cstringの中身はわかった。iconvである。
それのtopageとfrompageがどう与えられるかを確認する。

代表的なのは、

svn_error_t *
svn_utf_cstring_to_utf8(const char **dest,
const char *src,
apr_pool_t *pool)
{
xlate_handle_node_t *node;
svn_error_t *err;

SVN_ERR(get_ntou_xlate_handle_node(&node, pool));
err = convert_cstring(dest, src, node, pool);
put_xlate_handle_node(node, SVN_UTF_NTOU_XLATE_HANDLE, pool);
SVN_ERR(err);
SVN_ERR(check_cstring_utf8(*dest, pool));

return SVN_NO_ERROR;
}

svn_error_t *
svn_utf_cstring_from_utf8(const char **dest,
const char *src,
apr_pool_t *pool)
{
xlate_handle_node_t *node;
svn_error_t *err;

SVN_ERR(check_utf8(src, strlen(src), pool));

SVN_ERR(get_uton_xlate_handle_node(&node, pool));
err = convert_cstring(dest, src, node, pool);
put_xlate_handle_node(node, SVN_UTF_UTON_XLATE_HANDLE, pool);

return err;
}

の2つである。これらはほぼシンメトリックだ。

これらを呼び出しているのは例えば、svn_path_*だ。


svn_error_t *
svn_path_cstring_to_utf8(const char **path_utf8,
const char *path_apr,
apr_pool_t *pool)
{
svn_boolean_t path_is_utf8;
SVN_ERR(get_path_encoding(&path_is_utf8, pool));
if (path_is_utf8)
{
*path_utf8 = apr_pstrdup(pool, path_apr);
return SVN_NO_ERROR;
}
else
return svn_utf_cstring_to_utf8(path_utf8, path_apr, pool);
}

svn_error_t *
svn_path_cstring_from_utf8(const char **path_apr,
const char *path_utf8,
apr_pool_t *pool)
{
svn_boolean_t path_is_utf8;
SVN_ERR(get_path_encoding(&path_is_utf8, pool));
if (path_is_utf8)
{
*path_apr = apr_pstrdup(pool, path_utf8);
return SVN_NO_ERROR;
}
else
return svn_utf_cstring_from_utf8(path_apr, path_utf8, pool);
}

ここで重要なのは、APRの内部処理がUTF-8かどうかによっ
て、振舞いをかえているということだ。(ちなみに
svn_path_cstring_to_utf8がOSXでsvnがちゃんとうごく
ようにするためのcore foundationのパッチをあてると
ころ)

get_path_encoding(&path_is_utf8, pool)

これは、与えられたpath_*のエンコーディングではなく、
APRの内部エンコーディングがどうなっているかを問合
わせている。

これが、UTF-8の場合は、

svn_path_cstring_to_utf8 は
*path_utf8 = apr_pstrdup(pool, path_apr); するだけ。

svn_path_cstring_from_utf8 は
*path_apr = apr_pstrdup(pool, path_utf8); するだけ。

UTF-8じゃない場合は、

svn_path_cstring_to_utf8 は
svn_utf_cstring_to_utf8する。

svn_path_cstring_from_utf8 は
svn_utf_cstring_from_utf8する。

ということ。すなわち、

* APRの内部エンコーディングがUTF-8であるというこ
とは、その環境(OSなど)のエンコーディングが
UTF-8であるということの証左である。

* SVNの内部ではエンコーディングはUTF-8である。

* ただし、APR判定で環境がUTF-8の場合は、外部から
与えられたUTF-8バイト列を無変換で内部に取り込
む。APR判定で環境がUTF-8でない場合は、
svn_utf_cstring_*等によって変換処理をして内部
に取り込む。

ということだ。違う言い方をすると、

* UTF-8として内部に取り込まれる方式が二種類ある
が、いずれもNFD/NFCについては気にしておらず、
Subversionの中で、ファイル名やパス文字列を
NFD/NFCのどちらで扱っているかは、Subversionの
中では規程されておらず、Subversionを利用してい
る環境に依存する。

ということだな。



それでは、svn clientがどのようにしてworking
directoryに新規ファイルを追加するのか。そのときに
path名をどう扱っているのかを追ってみよう。



まずsvn addコマンドの本体は次の関数である。

/* This implements the `svn_opt_subcommand_t' interface. */
svn_error_t *
svn_cl__add(apr_getopt_t *os,
void *baton,
apr_pool_t *pool);

この中でいろいろな処理をするが、今関心である文字列
についていえば、

apr_array_header_t *targets;

なる構造が重要である。これを

SVN_ERR(svn_cl__args_to_target_array_print_reserved(&targets, os,
opt_state->targets,
pool));

によって作成した後、

for (i = 0; i < targets->nelts; i++)
{
const char *target = APR_ARRAY_IDX(targets, i, const char *);

svn_pool_clear(subpool);
SVN_ERR(svn_cl__check_cancel(ctx->cancel_baton));
SVN_ERR(svn_cl__try
(svn_client_add4(target,
opt_state->depth,
opt_state->force, opt_state->no_ignore,
opt_state->parents, ctx, subpool),
NULL, opt_state->quiet,
SVN_ERR_ENTRY_EXISTS,
SVN_ERR_WC_PATH_NOT_FOUND,
SVN_NO_ERROR));
}

にて、svn_client_add4を読んで、entriesへの情報の追
加処理を実施している。

さて、ここでtargetsがどのように作られるか確認しよ
う。

svn_error_t *
svn_cl__args_to_target_array_print_reserved(apr_array_header_t **targets,
apr_getopt_t *os,
apr_array_header_t *known_targets,
apr_pool_t
*pool);

は、

svn_opt_args_to_target_array3(targets, os,
known_targets, pool);

のwrapperである。svn_opt_aargs_to_target_array3を
みてみよう。さすがにエンコーディングに関するコメン
トがあるので、そのまま掲載する。


svn_error_t *
svn_opt_args_to_target_array3(apr_array_header_t **targets_p,
apr_getopt_t *os,
apr_array_header_t *known_targets,
apr_pool_t *pool)
{
int i;
svn_error_t *err = SVN_NO_ERROR;
apr_array_header_t *input_targets =
apr_array_make(pool, DEFAULT_ARRAY_SIZE, sizeof(const char *));
apr_array_header_t *output_targets =
apr_array_make(pool, DEFAULT_ARRAY_SIZE, sizeof(const char *));

/* Step 1: create a master array of targets that are in UTF-8
encoding, and come from concatenating the targets left by apr_getopt,
plus any extra targets (e.g., from the --targets switch.) */

for (; os->ind < os->argc; os->ind++)
{
/* The apr_getopt targets are still in native encoding. */
const char *raw_target = os->argv[os->ind];
SVN_ERR(svn_utf_cstring_to_utf8
/* *****************************************
ここで一発utf8変換(しないかもだけど、をか
ける。UTF-8であることは保証される。
*****************************************/
((const char **) apr_array_push(input_targets),
raw_target, pool));
}

if (known_targets)
{
for (i = 0; i < known_targets->nelts; i++)
{
/* The --targets array have already been converted to UTF-8,
because we needed to split up the list with svn_cstring_split. */
const char *utf8_target = APR_ARRAY_IDX(known_targets,
i, const char *);
APR_ARRAY_PUSH(input_targets, const char *) = utf8_target;
/* ********************************
ここでknown_tagetsをばらして、
input_tagetsに吸収している。
******************************** */
}
}

/* Step 2: process each target. */

for (i = 0; i < input_targets->nelts; i++)
{
const char *utf8_target = APR_ARRAY_IDX(input_targets, i, const char *);
const char *peg_start = NULL; /* pointer to the peg revision, if any */
const char *target; /* after all processing is finished */
int j;

/* Remove a peg revision, if any, in the target so that it can
be properly canonicalized, otherwise the canonicalization
does not treat a ".@BASE" as a "." with a BASE peg revision,
and it is not canonicalized to "@BASE". If any peg revision
exists, it is appended to the final canonicalized path or
URL. Do not use svn_opt_parse_path() because the resulting
peg revision is a structure that would have to be converted
back into a string. Converting from a string date to the
apr_time_t field in the svn_opt_revision_value_t and back to
a string would not necessarily preserve the exact bytes of
the input date, so its easier just to keep it in string
form. */
for (j = (strlen(utf8_target) - 1); j >= 0; --j)
{
/* If we hit a path separator, stop looking. This is OK
only because our revision specifiers can't contain
'/'. */
if (utf8_target[j] == '/')
break;
if (utf8_target[j] == '@')
{
peg_start = utf8_target + j;
break;
}
}
if (peg_start)
utf8_target = apr_pstrmemdup(pool,
utf8_target,
peg_start - utf8_target);

/* URLs and wc-paths get treated differently. */
if (svn_path_is_url(utf8_target))
/* *******************************
ここは(scheme)://(optional_stuff)という形
式をみているだけ。
******************************* */
{
/* No need to canonicalize a URL's case or path separators. */

/* Convert to URI. */
target = svn_path_uri_from_iri(utf8_target, pool);
/* ***************************
ここはいわゆるURI-encodeをするだけ。
UTF-8の部分。
*************************** */
/* Auto-escape some ASCII characters. */
target = svn_path_uri_autoescape(target, pool);
/* ***************************
ここもいわゆるURI-encodeをするだけ。
ASCIIの部分。
*************************** */

/* The above doesn't guarantee a valid URI. */
if (! svn_path_is_uri_safe(target))
return svn_error_createf(SVN_ERR_BAD_URL, 0,
_("URL '%s' is not properly URI-encoded"),
utf8_target);

/* Verify that no backpaths are present in the URL. */
if (svn_path_is_backpath_present(target))
return svn_error_createf(SVN_ERR_BAD_URL, 0,
_("URL '%s' contains a '..' element"),
utf8_target);

/* strip any trailing '/' */
target = svn_path_canonicalize(target, pool);
/* ***************************
target 一丁あがり。
*************************** */
}
else /* not a url, so treat as a path */
{
const char *apr_target;
const char *base_name;
char *truenamed_target; /* APR-encoded */
apr_status_t apr_err;

/* canonicalize case, and change all separators to '/'. */
SVN_ERR(svn_path_cstring_from_utf8(&apr_target, utf8_target,
pool));
/* *************************************
APRの内部表現に変換。
内部表現がUTF-8ならコピーするだけ。
************************************* */
apr_err = apr_filepath_merge(&truenamed_target, "", apr_target,
APR_FILEPATH_TRUENAME, pool);

if (!apr_err)
/* We have a canonicalized APR-encoded target now. */
apr_target = truenamed_target;
else if (APR_STATUS_IS_ENOENT(apr_err))
/* It's okay for the file to not exist, that just means we
have to accept the case given to the client. We'll use
the original APR-encoded target. */
;
else
return svn_error_createf(apr_err, NULL,
_("Error resolving case of '%s'"),
svn_path_local_style(utf8_target,
pool));

/* convert back to UTF-8. */
SVN_ERR(svn_path_cstring_to_utf8(&target, apr_target, pool));
/* *************************************
APRの内部表現からUTF-8に変換。
内部表現がUTF-8ならコピーするだけ。
************************************* */
target = svn_path_canonicalize(target, pool);
/* ***************************
target 一丁あがり。
後続にskip処理があるけどね。
*************************** */

/* If the target has the same name as a Subversion
working copy administrative dir, skip it. */
base_name = svn_path_basename(target, pool);
/* FIXME:
The canonical list of administrative directory names is
maintained in libsvn_wc/adm_files.c:svn_wc_set_adm_dir().
That list can't be used here, because that use would
create a circular dependency between libsvn_wc and
libsvn_subr. Make sure changes to the lists are always
synchronized! */
if (0 == strcmp(base_name, ".svn")
|| 0 == strcmp(base_name, "_svn"))
{
err = svn_error_createf(SVN_ERR_RESERVED_FILENAME_SPECIFIED,
err, _("'%s' ends in a reserved name"),
target);
continue;
}
}

/* Append the peg revision back to the canonicalized target if
there was a peg revision. */
if (peg_start)
target = apr_pstrcat(pool, target, peg_start, NULL);

APR_ARRAY_PUSH(output_targets, const char *) = target;
/* ***************************
targetをoutput_tagetsに登録。
*************************** */
}


/* kff todo: need to remove redundancies from targets before
passing it to the cmd_func. */

*targets_p = output_targets;
/* ***************************
targetsできあがり。
*************************** */

return err;
}


これでtargetsがどうできるのか理解できた。結局、
UTF-8の環境ならば、pathがNFDならNFDであるし、NFCな
らNFCということだ。

さて、これを受け取ってadd4が処理を実施する。
add4の呼び出し部分は


(svn_client_add4(target,
opt_state->depth,
opt_state->force, opt_state->no_ignore,
opt_state->parents, ctx, subpool),


であった。さきのtargetsの要素がtargetとして渡され
ている。

svn_client_add4 は、

svn_error_t *
svn_client_add4(const char *path,
svn_depth_t depth,
svn_boolean_t force,
svn_boolean_t no_ignore,
svn_boolean_t add_parents,
svn_client_ctx_t *ctx,
apr_pool_t *pool);

であり、これの主たる処理は、

err = add(path, depth, force, no_ignore, adm_access, ctx, pool);

である。引数のpathがそのままaddの引数のpathになる。
addのIFは、

static svn_error_t *
add(const char *path,
svn_depth_t depth,
svn_boolean_t force,
svn_boolean_t no_ignore,
svn_wc_adm_access_t *adm_access,
svn_client_ctx_t *ctx,
apr_pool_t *pool);

であり、addの対象がファイルであるときは(今はファイ
ルの場合のみを追う)。

err = add_file(path, ctx, adm_access, pool);

が処理本体となる。add_fileを見てみよう。


static svn_error_t *
add_file(const char *path,
svn_client_ctx_t *ctx,
svn_wc_adm_access_t *adm_access,
apr_pool_t *pool)
{
apr_hash_t* properties;
apr_hash_index_t *hi;
const char *mimetype;
svn_node_kind_t kind;
svn_boolean_t is_special;

/* Check to see if this is a special file. */
SVN_ERR(svn_io_check_special_path(path, &kind, &is_special, pool));

if (is_special)
mimetype = NULL;
else
/* Get automatic properties */
/* This may fail on write-only files:
we open them to estimate file type.
That's why we postpone the add until after this step. */
SVN_ERR(svn_client__get_auto_props(&properties, &mimetype, path, ctx,
pool));

/* Add the file */
SVN_ERR(svn_wc_add2(path, adm_access, NULL, SVN_INVALID_REVNUM,
ctx->cancel_func, ctx->cancel_baton,
NULL, NULL, pool));
/* **************************************
ここでsvn_wc_add2を読んでいる。これが本体
*************************************** */

/* ... 後略 ... */
}

というわけでpathをそのまま引き継ぎつつ、今度は
svn_wc_add2を呼んでいる。
svn_wc_add2をみてみよう。


svn_error_t *
svn_wc_add2(const char *path,
svn_wc_adm_access_t *parent_access,
const char *copyfrom_url,
svn_revnum_t copyfrom_rev,
svn_cancel_func_t cancel_func,
void *cancel_baton,
svn_wc_notify_func2_t notify_func,
void *notify_baton,
apr_pool_t *pool)
{
const char *parent_dir, *base_name;
const svn_wc_entry_t *orig_entry, *parent_entry;
svn_wc_entry_t tmp_entry;
svn_boolean_t is_replace = FALSE;
svn_node_kind_t kind;
apr_uint64_t modify_flags = 0;
svn_wc_adm_access_t *adm_access;

SVN_ERR(svn_path_check_valid(path, pool));
/* *******************************
ここはpathに制御文字が入ってないか確認してる
だけ。
******************************* */

/* Make sure something's there. */
SVN_ERR(svn_io_check_path(path, &kind, pool));
/* *******************************
svn_io_check_pathの本体はio_check_path。
ここはpathにsvn_path_cstring_from_utf8
を一回かけた上で、
apr_stat(&finfo, path_apr, flags, pool);
をやる。
apr_statはflagsの値によって、
lstatまたはstatでファイルにあたる。

man 2 stat によると、引数として渡されるfname
のエンコーディングにたいする記述は存在しない。

なので、UTF-8としてもここでNFCで問い合わせるべ
きなのか、それともNFDで問い合わせるべきなのか
はOS次第である。OSXの場合は、このpathはNFDな
ので、statに与えるのもNFDである。statがそれで
正常に動作するかはわからない。後で実験してみよ
う。
******************************* */

/* ... 中略 ... */

if (adm_access)
SVN_ERR(svn_wc_entry(&orig_entry, path, adm_access, TRUE, pool));
/* *******************************
orig_entryにsvn_wc_entry_t オブジェクトを設
定する。その際、ファイルの場合、
SVN_ERR(svn_wc__adm_retrieve_internal(&dir_access, adm_access, path, pool));
を呼ぶ。

ここで、svn_wc_adm_retrieve_internalは
adm_accessをさぐりつつ、dir_accessを構成す
る。

if (associated->set)
*adm_access = apr_hash_get(associated->set, path, APR_HASH_KEY_STRING);

があるので、associatedが指し示す
svn_wc_adm_access_t型構造がset(hash)を持つ
ならば、、、ここよくわからない。というか、
svn_wc_adm_access_t型の使われ方をもっと理解
しないと理解が無理。そしてそれを理解するこ
とは、Subversion全てを理解することのような
気がする。その時間はかけられない。どうする
か。
******************************* */
else
orig_entry = NULL;

/* ... 中略 ... */

/* Split off the base_name from the parent directory. */
svn_path_split(path, &parent_dir, &base_name, pool);
/* *************************************
ここで、pathからbase_nameをとりだす。
ファイルの場合これがファイル名となる。
************************************* */

/* ... 中略 ... */

/* Now, add the entry for this item to the parent_dir's
entries file, marking it for addition. */
SVN_ERR(svn_wc__entry_modify(parent_access, base_name, &tmp_entry,
modify_flags, TRUE, pool));
/* *******************************
ここでbase_nameにて、entriesファイルの書き換え
を実行する。
******************************* */

/* ... 後略 ... */
}

さて、base_nameに辿りつくまでの間いろいろあるのだ
が、エンコーディングの変換は実施されていなさそうだ。
ひとつ気になるのは、すでにentriesに登録済のファイ
ルとのバッティングを調べるところがあるのだが、そこ
で何と何を比べているのかということをわかっていない
ということだ。もしかしたらそこで比較する際にエンコー
ディングの問題が発生しうるかもしれない。

ただ、OSXにおいても、たとえば"が.txt"をsvn addする
こと自体はできたはずなので、それは発生しないという
ことにしておく。OSXで問題が発生するのはsvn status
からだ。

さて、

SVN_ERR(svn_wc__entry_modify(parent_access, base_name, &tmp_entry,
modify_flags, TRUE, pool));

を見なければいけない。
svn_wc__entry_modifyのIFは、

svn_error_t *
svn_wc__entry_modify(svn_wc_adm_access_t *adm_access,
const char *name,
svn_wc_entry_t *entry,
apr_uint64_t modify_flags,
svn_boolean_t do_sync,
apr_pool_t *pool);

であり、まず、

apr_hash_t *entries, *entries_nohidden;
svn_boolean_t entry_was_deleted_p = FALSE;
/* Load ADM_ACCESS's whole entries file. */
SVN_ERR(svn_wc_entries_read(&entries, adm_access, TRUE, pool));
SVN_ERR(svn_wc_entries_read(&entries_nohidden, adm_access, FALSE, pool));

というようにentriesファイルを読み込む。

nameについては、

if (name == NULL)
name = SVN_WC_ENTRY_THIS_DIR;

こんな処理をした上で、

/* If the entry wasn't just removed from the entries hash, fold the
changes into the entry. */
if (! entry_was_deleted_p)
{
fold_entry(entries, name, modify_flags, entry,
svn_wc_adm_access_pool(adm_access));
if (entries != entries_nohidden)
fold_entry(entries_nohidden, name, modify_flags, entry,
svn_wc_adm_access_pool(adm_access));
}

として、entriesにnameという名前でentrをfold_entry
する。ちなみにfold_entryが何かというと、

/* Update an entry NAME in ENTRIES, according to the combination of
entry data found in ENTRY and masked by MODIFY_FLAGS. If the entry
already exists, the requested changes will be folded (merged) into
the entry's existing state. If the entry doesn't exist, the entry
will be created with exactly those properties described by the set
of changes. Also cleanups meaningless fields combinations.

POOL may be used to allocate memory referenced by ENTRIES.
*/
static void
fold_entry(apr_hash_t *entries,
const char *name,
apr_uint64_t modify_flags,
svn_wc_entry_t *entry,
apr_pool_t *pool);

ということ、この関数にてnameのエンコーディングがい
じられることはない。

そして最後に、

SVN_ERR(svn_wc__entries_write(entries, adm_access, pool));

にて、svn_wc__entries_writeにてentryを組み込んだ
entriesをファイルEntriesに書き出す。



ということで、svn_wc__entries_write を調べる必要が
ある。

svn_wc__entries_writeをみてみよう。


svn_error_t *
svn_wc__entries_write(apr_hash_t *entries,
svn_wc_adm_access_t *adm_access,
apr_pool_t *pool)
{
svn_error_t *err = SVN_NO_ERROR;
svn_stringbuf_t *bigstr = NULL;
apr_file_t *outfile = NULL;
apr_hash_index_t *hi;
svn_wc_entry_t *this_dir;

SVN_ERR(svn_wc__adm_write_check(adm_access));

/* Get a copy of the "this dir" entry for comparison purposes. */
this_dir = apr_hash_get(entries, SVN_WC_ENTRY_THIS_DIR,
APR_HASH_KEY_STRING);

/* If there is no "this dir" entry, something is wrong. */
if (! this_dir)
return svn_error_createf(SVN_ERR_ENTRY_NOT_FOUND, NULL,
_("No default entry in directory '%s'"),
svn_path_local_style
(svn_wc_adm_access_path(adm_access), pool));

/* Open entries file for writing. It's important we don't use APR_EXCL
* here. Consider what happens if a log file is interrupted, it may
* leave a .svn/tmp/entries file behind. Then when cleanup reruns the
* log file, and it attempts to modify the entries file, APR_EXCL would
* cause an error that prevents cleanup running. We don't use log file
* tags such as SVN_WC__LOG_MV to move entries files so any existing file
* is not "valuable".
*/
SVN_ERR(svn_wc__open_adm_file(&outfile,
svn_wc_adm_access_path(adm_access),
SVN_WC__ADM_ENTRIES,
(APR_WRITE | APR_CREATE),
pool));

if (svn_wc__adm_wc_format(adm_access) > SVN_WC__XML_ENTRIES_VERSION)
{
apr_pool_t *subpool = svn_pool_create(pool);
bigstr = svn_stringbuf_createf(pool, "%d\n",
svn_wc__adm_wc_format(adm_access)); //#### ここでentriesファイルの中身たる文字列バッファを作成。
/* Write out "this dir" */
write_entry(bigstr, this_dir, SVN_WC_ENTRY_THIS_DIR, this_dir, pool); //#### 起点dir情報を書く。

for (hi = apr_hash_first(pool, entries); hi; hi = apr_hash_next(hi)) //#### 引数で与えられたentries(hash)をひとつづつ処理する。
{
const void *key;
void *val;
svn_wc_entry_t *this_entry;

svn_pool_clear(subpool);

/* Get the entry and make sure its attributes are up-to-date. */
apr_hash_this(hi, &key, NULL, &val); //#### apr_hash_thisでkeyに値を仕込む。apr_hash_thisは要調査。
this_entry = val;

/* Don't rewrite the "this dir" entry! */
if (! strcmp(key, SVN_WC_ENTRY_THIS_DIR ))
continue;

/* Append the entry to BIGSTR */
write_entry(bigstr, this_entry, key, this_dir, subpool); //#### ここでthis_entryを文字列に書き出している。keyが引数になっている。
}

svn_pool_destroy(subpool);
}
else
/* This is needed during cleanup of a not yet upgraded WC. */
write_entries_xml(&bigstr, entries, this_dir, pool);

SVN_ERR_W(svn_io_file_write_full(outfile, bigstr->data,
bigstr->len, NULL, pool), //#### ここでbigstrをoutfileに書き出し。
apr_psprintf(pool,
_("Error writing to '%s'"),
svn_path_local_style
(svn_wc_adm_access_path(adm_access), pool)));

err = svn_wc__close_adm_file(outfile,
svn_wc_adm_access_path(adm_access),
SVN_WC__ADM_ENTRIES, 1, pool);

svn_wc__adm_access_set_entries(adm_access, TRUE, entries);
svn_wc__adm_access_set_entries(adm_access, FALSE, NULL);

return err;
}


この関数の要点は、apr_hash_thisでhashから順次entry
を取り出して、write_entryでそれをバッファに書いて、
svn_io_file_write_fullでそれをファイルに書くという
こと。

apr_hash_thisは、"Get the current entry's details
from the iteration state." とのこと。

とすると、

apr_hash_this(hi, &key, NULL, &val);

は、keyについてそのままわたすだけ。


続いてwrite_entryを調べてみよう。


/* Append a single entry ENTRY to the string OUTPUT, using the
entry for "this dir" THIS_DIR for comparison/optimization.
Allocations are done in POOL. */
static void
write_entry(svn_stringbuf_t *buf,
svn_wc_entry_t *entry,
const char *name, //#### ここでkeyが渡される。
svn_wc_entry_t *this_dir,
apr_pool_t *pool)
{
const char *valuestr;
svn_revnum_t valuerev;
svn_boolean_t is_this_dir = strcmp(name, SVN_WC_ENTRY_THIS_DIR) == 0;
svn_boolean_t is_subdir = ! is_this_dir && (entry->kind == svn_node_dir);

assert(name);

/* Name. */
write_str(buf, name, pool); //#### 渡されたkeyをそのままwrite_strに渡す。

/* Kind. */
switch (entry->kind)
{
case svn_node_dir:
write_val(buf, SVN_WC__ENTRIES_ATTR_DIR_STR,
sizeof(SVN_WC__ENTRIES_ATTR_DIR_STR) - 1);
break;

case svn_node_none:
write_val(buf, NULL, 0);
break;

case svn_node_file:
case svn_node_unknown:
default:
write_val(buf, SVN_WC__ENTRIES_ATTR_FILE_STR,
sizeof(SVN_WC__ENTRIES_ATTR_FILE_STR) - 1);
break;
}

/* Revision. */
if (is_this_dir || (! is_subdir && entry->revision != this_dir->revision))
valuerev = entry->revision;
else
valuerev = SVN_INVALID_REVNUM;
write_revnum(buf, valuerev, pool);

/* URL. */
if (is_this_dir ||
(! is_subdir && strcmp(svn_path_url_add_component(this_dir->url, name,
pool),
entry->url) != 0))
valuestr = entry->url;
else
valuestr = NULL;
write_str(buf, valuestr, pool); //#### URLについてもentry->urlをそのままwrite_str。

/* Repository root. */
if (! is_subdir
&& (is_this_dir
|| (this_dir->repos == NULL
|| (entry->repos
&& strcmp(this_dir->repos, entry->repos) != 0))))
valuestr = entry->repos;
else
valuestr = NULL;
write_str(buf, valuestr, pool);

//... 中略 ...

/* Remove redundant separators at the end of the entry. */
while (buf->len > 1 && buf->data[buf->len - 2] == '\n')
buf->len--;

svn_stringbuf_appendbytes(buf, "\f\n", 2);
}


nameとentry->urlを処理しているのはwrite_strであった。
なのでwrite_strを調べてみよう。


/* If STR is non-null, append STR to BUF, terminating it with a
newline, escaping bytes that needs escaping, using POOL for
temporary allocations. Else if STR is null, just append the
terminating newline. */
static void
write_str(svn_stringbuf_t *buf, const char *str, apr_pool_t *pool)
{
const char *start = str;
if (str)
{
while (*str)
{
/* Escape control characters and | and \. */
if (svn_ctype_iscntrl(*str) || *str == '\\')
{
svn_stringbuf_appendbytes(buf, start, str - start);
svn_stringbuf_appendcstr(buf,
apr_psprintf(pool, "\\x%02x", *str));
start = str + 1;
}
++str;
}
svn_stringbuf_appendbytes(buf, start, str - start); //#### エスケープされた制御文字以外は、ここでappendbytesするだけ。
}
svn_stringbuf_appendbytes(buf, "\n", 1);
}


write_strは、svn_stringbuf_appendbytesでバイトを足すだけだ。

この枝はこれで葉。svn_wc__entries_writeにおける処理の次の枝は、
svn_io_file_write_full だ。

svn_id_file_write_full を見てみよう。


svn_error_t *
svn_io_file_write_full(apr_file_t *file, const void *buf,
apr_size_t nbytes, apr_size_t *bytes_written,
apr_pool_t *pool)
{
apr_status_t rv = apr_file_write_full(file, buf, nbytes, bytes_written);

#ifdef WIN32
#define MAXBUFSIZE 30*1024
if (rv == APR_FROM_OS_ERROR(ERROR_NOT_ENOUGH_MEMORY)
&& nbytes > MAXBUFSIZE)
{
apr_size_t bw = 0;
*bytes_written = 0;

do {
rv = apr_file_write_full(file, buf,
nbytes > MAXBUFSIZE ? MAXBUFSIZE : nbytes, &bw); //#### 実質ここでファイルに書き出している。
*bytes_written += bw;
buf = (char *)buf + bw;
nbytes -= bw;
} while (rv == APR_SUCCESS && nbytes > 0);
}
#undef MAXBUFSIZE
#endif

return do_io_file_wrapper_cleanup
(file, rv,
N_("Can't write to file '%s'"),
N_("Can't write to stream"),
pool);
}


これは、apr_file_write_fullのラッパーであった。
apr_file_write_fullは、

------
apr_status_t apr_file_write_full( apr_file_t * thefile,
const void * buf,
apr_size_t nbytes,
apr_size_t * bytes_written
)

Write data to the specified file, ensuring that all of the data is written before returning.

Parameters:
thefile The file descriptor to write to.
buf The buffer which contains the data.
nbytes The number of bytes to write.
bytes_written If non-NULL, this will contain the number of bytes written.
------

なのでたぶんbufのバイト列を書き出すだけということ
だろう。


さて、svn_wc__entries_writeとは何だったのか。

* svn_wc__entries_writeは、既に作成済みのentries(ハッ
* シュ)をentriesファイルに書き出す処理を実施するが、
* その処理過程にて、entries(ハッシュ)に格納されてい
* るnameなどは無加工である。


またずいぶん長かったが、svn addにてファイルを
working directoryに足すとき、.svn/entitiesファイル
に書かれるファイル名は、コマンドラインでの

$ svn add が.txt

の"が.txt"がNFDならNFD、NFCならNFCということがわかっ
た。

実際にOSXでsvn add が.txtしたときのentriesファイル
をみてみると、

$ od -t x1 -t c entries
... 前略 ...
0000360 36 34 31 61 63 61 64 66 33 0a 0c 0a e3 81 8c 2e
6 4 1 a c a d f 3 \n \f \n が ** ** .
0000400 74 78 74 0a 66 69 6c 65 0a 0a 0a 0a 61 64 64 0a
t x t \n f i l e \n \n \n \n a d d \n
0000420 0c 0a
\f \n
0000422
$

このようにNFCになっている。ということはコマンドラ
インの引数の取り扱いがOSXではNFCであるということだ
ろうか?

GDBで確認してみよう。

int main(int argc, char *argv [])
{
return (0);
}

をコンパイルして"が.txt"を引数にして実行して、GDBでみ
てみると、

(gdb) x/3cx argv[1]
0xbffff3c5: 0xe3 0x81 0x8c

たしかにNFCだ。しかしこれはGDBの所作かもしれないが、
まあよしとしちゃう。(疲弊しているのだ。。。)

ここがOSXでのNFD/NFC問題の一方の原因なのかもしれな
い。


readdirでディレクトリの中身を読取ると、ファイル名は
NFDで返ってくる。同じファイル名でsvn addするとその
引数はNFCで渡される。


だいぶ見えてはきている。

  • Subversionの内部エンコーディングはUTF-8。ただし、それがNFDかNFCかは常に関知していなくて、それぞれそのまま扱う。
  • Subversionの中でエンコーディングの変換をする場合は、APRの内部エンコーディング=環境のエンコーディングという仮定のもと、外部から受け取ったpathについてはUTF-8に変換する。
  • 変換エンジンはiconvである。
  • OSXは、コマンドラインからアプリへの引数の受け渡しはNFCのようだ。さきに確認したようにreaddirはNFDでファイル名を返す。このあたりでアンマッチを発生させている予感。
  • あとstat(2)はNFDなのかNFCなのかも気になる。

  • OSXでsubversionがまともに動くようにするためのpatchは、svn_path_cstring_to_utf8について、core foundationにあるNFCへの変換関数を必ず通るようにする、というものだ。
  • ここで必ずNFCにするようにしておけば、Subversionの内部においては、常にNFCであることが担保されるのであろう。
  • そうすると、ファイルシステム上のファイルは、本体であろうがtext-base/配下であろうがNFDであり、それをsubversionの目で見ると、entriesの内容含めてすべてNFCに統一されてみえるということだろう。

  • CF patch無しのsvnにおける別の状況として、例えば、LinuxマシンでNFCの"が.txt"をcheck inして、それをcheck outした場合はどうなるのだろう。
  • おそらく、OSXのファイルを作るAPIにおいて、外からNFCとして投入されたファイルの名前はNFDに自動変換されるのだろう。
  • そして、entriesの中身はNFCなのだろう。
  • ここでアンマッチが発生して使えないworking directoryが一丁あがりとなるのだろう。

さて、ここからどこまで調べるか。。。。もういいとするか。。。
しかし、精魂尽きた。。。土曜日のShibuya.lispに行けるのだろうか。。。

2009年2月23日月曜日

C言語におけるUTF-8の取り扱い確認


/*

ちょっと調査。

まずemacsでひらがなの「が」をファイルに書くとLinux
とOSXでは違いがあるのかどうか。そのファイルをodで比
べてみる。

まずOSX。

----
$ od -t x1 -t c HIRAGANA-LETTER-GA.txt
0000000 61 62 63 64 0a e3 81 8c 0a
a b c d \n が ** ** \n
0000011
----

続いてLinux。

----
$ od -t x1 -t c HIRAGANA-LETTER-GA.txt
0000000 61 62 63 64 0a e3 81 8c 0a
a b c d \n 343 201 214 \n
0000011
----

違いは無い。

さて、e3 81 8c をUTF-8にて解釈してみる。

ビットにすると、

----
CL-USER(13): (dolist (n (list #xe3 #x81 #x8c))
(format t "~b " n))
11100011 10000001 10001100
NIL
----

である。このビットパターンは、UTF-8としては

1110yyyy 10yxxxxx 10xxxxxx

であり、最大16bitのコードポイントを表現している。

具体的にコードポイント対応部分を抽出すると、

0011 000001 001100

さらにこれを右詰めoctetになおすと、

00110000 01001100

----
CL-USER(14): (dolist (n (list #b00110000 #b01001100))
(format t "~x " n))
30 4c
NIL
----

というわけで、これはNFCの「が」(U+304C)だ。

とどのつまりファイルの中身にはOSは関知していないか
ら、emacsやodが文字をUTF-8のNFCで取り扱っており、そ
こに一貫性がある、ということだろう。

続いてgccのプリプロセッサまでの処理における文字の取
り扱いを確認したい。

前章で実験したところ、gccはC99に完全準拠していなかっ
た。ソースファイルの識別子に多バイト文字が使われて
いた場合は、それをプリプロセス前に国際文字名
(\uxxxx)に変換しなければいけないのだが、それをやっ
てくれていないようだ。それを確認する。

*/
----
#include <stdio.h>
int main(void)
{
int が;
for (が=1;が<10;が++)
printf("%d ", が);

return (0);
}
----
/*

こんなソースでためす。これのod。

----
$ od -t x1 -t c i18n-character-name-2.c
0000000 23 69 6e 63 6c 75 64 65 20 3c 73 74 64 69 6f 2e
# i n c l u d e < s t d i o .
0000020 68 3e 0a 69 6e 74 20 6d 61 69 6e 28 76 6f 69 64
h > \n i n t m a i n ( v o i d
0000040 29 0a 7b 0a 20 20 20 20 20 69 6e 74 20 e3 81 8c
) \n { \n i n t が ** **
0000060 3b 0a 20 20 20 20 20 66 6f 72 20 28 e3 81 8c 3d
; \n f o r ( が ** ** =
0000100 31 3b e3 81 8c 3c 31 30 3b e3 81 8c 2b 2b 29 20
1 ; が ** ** < 1 0 ; が ** ** + + )
0000120 0a 20 20 20 20 20 20 20 20 20 20 70 72 69 6e 74
\n p r i n t
0000140 66 28 22 25 64 20 22 2c 20 e3 81 8c 29 3b 0a 0a
f ( " % d " , が ** ** ) ; \n \n
0000160 20 20 20 20 20 72 65 74 75 72 6e 20 28 30 29 3b
r e t u r n ( 0 ) ;
0000200 0a 7d 0a
\n } \n
0000203
$
----

これをgcc -Eで処理。

includeしているから長くなるが、とにかく変換はしていないようだ。

*/
----
# 1 "i18n-character-name-2.c"
# 1 "<built-in>"
# 1 "<command line>"
# 1 "i18n-character-name-2.c"
# 1 "/usr/include/stdio.h" 1 3 4
# 64 "/usr/include/stdio.h" 3 4
# 1 "/usr/include/_types.h" 1 3 4
# 27 "/usr/include/_types.h" 3 4
# 1 "/usr/include/sys/_types.h" 1 3 4
# 32 "/usr/include/sys/_types.h" 3 4
# 1 "/usr/include/sys/cdefs.h" 1 3 4
# 33 "/usr/include/sys/_types.h" 2 3 4
# 1 "/usr/include/machine/_types.h" 1 3 4
# 34 "/usr/include/machine/_types.h" 3 4
# 1 "/usr/include/i386/_types.h" 1 3 4
# 37 "/usr/include/i386/_types.h" 3 4
typedef signed char __int8_t;


... 中略 ...


static __inline int __sputc(int _c, FILE *_p) {
if (--_p->_w >= 0 || (_p->_w >= _p->_lbfsize && (char)_c != '\n'))
return (*_p->_p++ = _c);
else
return (__swbuf(_c, _p));
}
# 2 "i18n-character-name-2.c" 2
int main(void)
{
int が;
for (が=1;が<10;が++)
printf("%d ", が);

return (0);
}
---
/*

では、文字列定数の中だとちゃんとやってくれるのか?
というところで同じソースを変更して確認する

*/
----
#include <stdio.h>
int main(void)
{
int i;
for (i=1;i<10;i++)
printf("%d が", i);

return (0);
}
----
*/
/*

あり、だめだ。次のように、変換していない。

*/
----
前略 ...

static __inline int __sputc(int _c, FILE *_p) {
if (--_p->_w >= 0 || (_p->_w >= _p->_lbfsize && (char)_c != '\n'))
return (*_p->_p++ = _c);
else
return (__swbuf(_c, _p));
}
# 2 "i18n-character-name-3.c" 2
int main(void)
{
int i;
for (i=1;i<10;i++)
printf("%d が", i);

return (0);
}
----
/*

というわけで、gccの字句関係処理はC99の要求まんまに
実装されているのではなさそうだ。ソース文字集合が
UTF-8そのものである、という作りに見受けられる。

さて、次にファイル名の取り扱いを確認したい。ファイ
ルの中身とちがって、ここはOSの関与がある部分だ。
"が.txt"というファイルを作成する。これの中身を表示
するプログラムで振舞いを確認してみる。APIはCの標準
ライブラリを使う。これは、予測としては不一致なくう
まくいくはず。gccの標準ライブラリがfopenの引数たる
ファイル名をOSXならOSX向けに取り扱ってくれるという
予測だ。

----が.txt---
abcd

-------------

*/
----ga-opne.c----
#include <stdio.h>

int main(void)
{
FILE *fp;
fp = fopen("が.txt", "r");

if (fp == NULL)
printf("failed.\n");
else {
printf("Succeed.\n");
fclose(fp);
}
return (0);
}
--------
/*

----
$ gcc -std=c99 ga-open.c
$ ./a.out
Succeed.
$
----

うまくいった。

さて、ファイル名の取得はどうだろう。ディレクトリに
含まれるファイルの名前を取得する方法は標準Cにはない。
よって、ここから先は処理系次第となる。ただし処理系/環境
がPOSIXだとかSUSとかに対応しているなら、それらAPIを
使うということである程度のポータビリティは期待でき
る。

さて、この領域は、Advanced Programming in the UNIX
Environment (apue.2e)だろう、ということでapue.2eか
らサンプルをとってくる。

----ls1.c----
*/
#include "apue.h"
#include <dirent.h>

int
main(int argc, char *argv[])
{
DIR *dp;
struct dirent *dirp;

if (argc != 2)
err_quit("usage: ls directory_name");

if ((dp = opendir(argv[1])) == NULL)
err_sys("can't open %s", argv[1]);
while ((dirp = readdir(dp)) != NULL)
printf("%s\n", dirp->d_name);

closedir(dp);
exit(0);
}
/*
--------

apue.2eのサイトにあがっているソースをLeopard上でコ
ンパイルするには多少調整が必要。apue.2eが発刊された
ときは、10.3.xだったのだ。それから10.4、10.5とかわ
るなかでOSXはPOSIX対応を進めたため、ヘッダ関係で混
乱があるようだ。

いくつか調整作業をしてmakeと次のコマンドでls1.cをコ
ンパイルした。

gcc -ansi -I/Users/aka/scratch/c-ref/apue.2e/include -Wall -g -DMACOS -L../lib ls1.c ../lib/libapue.a -o ls1

で、そのls1で、が.txtを含むga-testディレクトリの中
身をOSから取得する。



(gdb) n
..
(gdb) p dirp->d_name
$10 = "..\000\000?\r\000\024\000\b\nが.txt\000*", '\0' <repeats 231 times>
(gdb) n
(gdb) p dirp->d_name
$11 = "が.txt\000*", '\0' <repeats 243 times>
(gdb) p/x dirp->d_name
$12 = {0xe3, 0x81, 0x8b, 0xe3, 0x82, 0x99, 0x2e, 0x74, 0x78, 0x74, 0x0, 0x2a, 0x0 <repeats 244 times>}
(gdb)

で、ここでメモリに入ってる

0xe3, 0x81, 0x8b, 0xe3, 0x82, 0x99

が、"が"なのだが、これを先程と同じ方法でUTF-8として
読み解くと、

U+304b U+3099
[HIRAGANA LETTER KA] [COMBINING KATAKANA-HIRAGANA VOICED SOUND MARK]

であることがわかる。ここでNFDがあらわれた!

そのあとは、printfで%sしてるだけなので、この
UTF-8(NFD)が正しく表示されるかは、その表示を担当す
るものによりけりになる。上記のls1->gdb->emacs->screen->Terminal
では実は正常に表示されず、が.txtの"が"と"."の間に妙な文字が表示
されてしまう。(コピペした際に上のgdb出力のこの異常は消えちゃった)
Terminal直ならば問題なくて、

------------
$ ./ls1 ga-test
.
..
が.txt
$
------------

となる。

さて、ここまで来たところで、apue.2eのreaddirの出自
を確認する必要がある。

apue.2eによると、POSIX.1とのこと。
とするとmanにあるのか? man readdir、あった。

-----------
DIRECTORY(3) BSD Library Functions Manual DIRECTORY(3)

NAME
closedir, dirfd, opendir, readdir, readdir_r, rewinddir, seekdir, telldir --
directory operations

LIBRARY
Standard C Library (libc, -lc)

SYNOPSIS
#include <dirent.h>

...
-----------

するとdirentもmanにあるのか? あった。

-----------
DIR(5) BSD File Formats Manual DIR(5)

NAME
dir, dirent -- directory file format

SYNOPSIS
#include <sys/types.h>
#include <sys/dir.h>

DESCRIPTION
Directories provide a convenient hierarchical method of grouping files while
obscuring the underlying details of the storage medium. A directory file is
differentiated from a plain file by a flag in its inode(5) entry. It consists
of records (directory entries) each of which contains information about a file
...
-----------

で、

-----------
*/
struct dirent {
ino_t d_ino; /* file number of entry */
u_int64_t d_seekoff; /* length of this record */
u_int16_t d_reclen; /* length of this record */
u_int16_t d_namlen; /* length of string in d_name */
u_int8_t d_type; /* file type, see below */
char d_name[MAXPATHLEN]; /* name must be no longer than this */
};
/*
-----------

なそうであり、d_nameの中身がどうあるべきかは無い。
まあ、ファイルシステムは環境によって違うからなぁ。

というわけで、このPOSIX.1のreaddir経由でOXとアプリ
がファイル名をやりとりする場合は、エンコードについ
てはアプリ側がOSが何を選択しているかをどこかで知っ
た上で使わないといけないということだ。
*/

これで、Subversionにおけるファイル名の取り扱いを探る準備ができたのかなぁ。

こつこつ。

2009年2月22日日曜日

【C:ARM5】2 字句要素

うーん。字句について理解するだけで結構時間がかかった。。。
めげない、めげない。

/*

2 字句要素 (Lexical Elements)

- "This chapter describes the lexical structure
of the C language--that is, the characters that
may appear in a C source file and how they are
collected into lexical units, or tokens."


2.1 文字集合 (Character Set)

- ソース文字集合(source character set)というとき、
それはいわゆる文字集合そのままであり、エスケープ
表記等は含んでいないことに注意。

- ここでは文字コードは指定していない。文字集合の指
定である。

- 基本的にはISO/IEC 10646のBasic Latinブロックだよ。

- 国によってはその国の文字集合にBasic Latinの中の
文字が含まれていないこともある。そこでCには
ISO/IEC 646-1083のInvariant Code Setだけで書ける
ように、漏れた記号をInvariant code setの文字で表
現する仕組みがあるよ。

2.1.1 実行時文字集合 (Execution Character Set)

- クロスコンパイルを考えよ。ソースをコンパイルする
ときの環境の文字集合とプログラムが実行される環境
の文字集合は必ずしも同じではない。

- 実行時文字集合(execution character set)はバック
スラッシュによるエスケープ表記も含む。

- ソースをコンパイルするときの環境と実行するときの
環境が同じなら、ソース文字集合と実行時文字集合は
同じになる。

2.1.2 空白類文字と行の終わり (Whitespace and Line Termination)

- 空白類文字は隣り合う字句を分離する働きを持つ。

- 論理ソース行の例。gccでコンパイルできた。
*/

int main(void)
{
if (1==2) 1; el\
se 2;
return (0);
}

/*

2.1.3 文字コード (Character Encoding)

- (実行時)文字集合に含まれる各文字には何らかの慣用
的な数値表現が割り当てられている。これを文字コー
ドと呼ぶ。

- Cでは文字コードについていくつかの制約は課すが、
細かな指定はしない。

2.1.4 3文字表記 (Trigraphs)

- ISO 646-1083 Invariant Code Set に含まれる文字だ
けでCプログラムを書くための仕組み。

- 3文字表記(trigraphs)の処理は、字句解析の前に実施
される。かなり先頭の作業。

- 3文字表記の例。gccでは-trigraphsオプションが必要。
*/

int main(void)
??<
return (0);
??>

/*

2.1.5 多バイト文字とワイド文字 (Multibyte and Wide Characters)

- 非英語アルファベットに対応するためにワイド文字
とワイド文字列がある。

- ワイド文字とは、拡張文字集合(extended
character set)の要素のバイナリ表現である。

- 規格Cではワイド文字のためのwint_t型とwchar_t型
がある。

- ワイド文字は16ビットを占めるのが普通である。

- ナルワイド文字以外は、規格Cは拡張文字集合につい
て規程していない。

- ファイル等の外部メディアやCソースプログラムは、
大抵のところバイトの多きさの文字で構成されてい
る(バイト指向)。

- そのため多バイトコードという仕組みが使われる。
多バイトコードとは、バイトの大きさの文字の並び
とワイド文字の並びとの間でロケール固有の写像を
行う方法。

- 1つのワイド文字を、ソース文字集合または実行時文
字集合に含まれる文字(の並び)によって表現したの
が多バイト文字である。

- 多バイト文字は通常のC文字列である。

- 多バイト文字の形式や、多バイト文字とワイド文字
の写像は処理系定義である。

- 多バイト文字の方式には、状態依存型と状態独立型
がある。

- 規格Cは多バイト文字についていくつかの制約を課し
ている。

- 多バイト文字は次の場所で使ってよい。
- 注釈
- 識別子
- ヘッダ名
- 文字列定数
- 文字定数

- 「ソースの物理的表現の中の多バイト文字は、字句
解析、プリプロセス処理、それどころか継続行の接
合よりも前に認識され、ソース文字集合に翻訳され
なければならない。」 う、これわからない。。。

2.2 注釈 (Comments)

- お、Cでも//って使えるんだ。試すと、、、使えた。
*/

// Program to compute the squares of
// the first 10 integers
#include <stdio.h>
void Squares( /* no arguments */)
{
int i;
/*
Loop from 1 to 10,
printing out the squares
*/
for (i=1; i<=10; i++)
printf("%d //squared// is %d\n",i,i*i);
}

int main(void)
{
Squares();
return (0);
}

/*

2.3 字句 (Tokens)

- やっとTokenだ。。。

- 「Cプログラムを構成する文字は、以下に述べる規則
に従って集められて字句となる」うーん。名文だ。

- 字句は5種類。
- 演算子
- 分離子
- 識別子
- キーワード
- 定数

- 「コンパイラは左から右に文字を集めるとき、できる
だけ長い字句を作ろうとする。」

2.4 演算子と分離子 (Operators and Separators)

- 単純演算子
! % ^ など
- 複合代入演算子
+= -= など
- その他の複合演算子
-> ++ など
- 分離子
( ) [ ] など
- 代替綴り
<% %> <: :> など

2.5 識別子 (Identifiers)

- 識別子(名前)はラテン大文字と小文字、数字、アンダ
スコア、国際文字名および処理系定義の多バイト文字
の並びである。ということはgccでUTF-8の日本語も使
えるかも? 試す。
*/

#include <stdio.h>
int main(void)
{
int あ;
for (あ=1;あ<10;あ++)
printf("%d ", あ);

return (0);
}

/*

- これは駄目。-std=c99しても駄目。

- \uでいく。

*/

#include <stdio.h>
int main(void)
{
int \u3041; // あ
for (\u3041=1;\u3041<10;\u3041++)
printf("%d ", \u3041);

return (0);
}

/*

- おお。これは-std=c99ならOK。gccが多バイトからソー
ス文字集合への変換をしてくれないんだなきっと。

- 識別子の文字数の制限には注意が必要。特にリンカな
どの外部のプログラムに露出する場合は、そっちの制
限もあるから。

2.6 キーワード (Keywords)

- 識別子の一部は規格にてキーワードとして定められて
おり、普通の識別子として使ってはいけない。

- キーワードの一覧

auto _Bool break case char _Complex const
continue default do double else enum extern
float for goto if _Imaginary inline int long
register restrict return short signed sizeof
static struct switch typedef union unsigned
void volatile while

2.6.1 既定義識別子 (Predifined Identifiers)

- __func__は既定義識別子であり、プログラマが定義し
てはならない。


2.7 定数 (Constants)

- 別の言語ではリテラルとも言う。Cでは伝統的に
Constantsと呼ぶ。

- この節、型の概念とクロスリファレンスになっている
なぁ。まあしょうがないんだろうな。

2.7.1 整数定数 (Integer Constants)

- まあ、ごちゃごちゃと。割愛。

2.7.2 浮動小数点定数 (Floating-Point Constants)

- これも割愛。

2.7.3 文字定数 (Character Constants)

- 文字定数は、一つ以上の文字をアポストロフィで囲んで書く。

- 文字定数の前にLをつけるとワイド文字定数になる。

- 形式は次のとおり。

文字定数:
' c文字の並び '
L' c文字の並び '

c文字の並び:
c文字
c文字の並び c文字

c文字:
「'、 \ および改行を除く任意のソース文字集合の文字」
エスケープ表記
国際文字名

- 先頭にLを付けない文字定数はint型である。その値は、
実行時文字集合におけるその文字のコードである。

- Lで始まる文字定数はwchar_t型である。ワイド文字定
数は複数の文字と複数のエスケープ表記の並びとなっ
ていて、それらがひとつとなって多バイト文字を表す
のが普通。多バイト文字からから対応するワイド文字
への写像は処理系定義である。その変換を実行時に行
うのはmbtowc関数である。

- 複数文字定数の意味は処理系定義である。

2.7.4 文字列定数 (String Constants)

- 形式は次のとおり。

文字定数:
" s文字の並び "
L" s文字の並び "

s文字の並び:
s文字
s文字の並び s文字

s文字:
「"、 \ および改行を除く任意のソース文字集合の文字」
エスケープ表記
国際文字名

- n文字を含む文字列定数の型はchar [n+1]である。最
後はナル文字'\0'である。

- n文字を含むワイド文字列定数の型はwchar_t [n+1]で
ある。最後はナルワイド文字である。

- 文字列定数の文字を保持しているメモリの内容を書き
換えようとしてはいけない。

2.7.5 エスケープ表記 (Escape Characters)

- 割愛。

2.7.6 文字エスケープコード (Character Escape Codes)

- 割愛。

2.7.7 数値エスケープコード (Numeric Escape Codes)

- 割愛。

2.8 C++との互換性 (C++ Compatibility)

- 割愛。

2.9 文字集合、レパートリおよびコードについて (On Character sets, Repertories and Encodings)

- 国際文字名 (Universal Character Names)は、文字定
数、文字列定数および識別子の中に任意のUCS-2文字
またはUCS-4文字を書く書き方である。
- コードはISO/IEC 10646に従う。

2.10 練習問題 (Execises)

- 割愛。

*/

Cでの日本語の取り扱いを多少理解できた。

こつこつ。

2009年2月16日月曜日

【C:ARM5】1 入門


/*
1 入門

1.1 Cの進化
1.2 Cのどの方言を使うべきか?
1.3 Cプログラムの概観
1.4 規格合致性
1.5 構文記法


- 実行時ライブラリという言葉、気になるな。

- Standard C と Standard C++ の intersection を
Clean C と言うのか。

- 「普通、リンカはCに特化されていない。どのコン
ピュータシステムもリンカは一つで、さまざまな言
語で書かれたプログラムを処理する」なるほど。

- そうだとすると、リンカの入力となるオブジェクト
コードの構造も、コンピュータシステムにおいて単
一なのか?  ・・・単一なのだろう。ある言語がそ
うじゃないコードにコンパイルされたとしたら、そ
れはなんらかの仮想マシン上で動くものなのだろう。

- 規格合致性には二種類あるよ。規格合致ホスト処理
系であることと、規格合致フリースタンディング処
理系であること。後者は埋め込みシステムなど、質
素なターゲット環境向けなんだよ。

- 終端記号は、プログラム中に書かれたとき、そのと
おりに見えなければいけない記号だよ。なるほど、
こういう言い方もあるな。
*/

こつこつ。

【C:ARM5】「Cリファレンスマニュアル」を読む

Subversionのソースを見ていたら、Cの復習がしたくなった。そこで以前から読みたいと思っていたSteeleのCリファレンスマニュアルをちょっと覗いてみようと思う。Lispを知りつくしたSteeleが書くCの本ということでとても興味があったのだ。できれば、自分なりのCommon Lispとの対比も交えていきたい。

2008年11月9日日曜日

【雑】プログラミングを学ぶことについて

子供のときに、コンピュータにちょっと興味をもったことがあって、コンピュータに詳しいというおじさんに、プログラミングできるようになるにはどうしたらいいの? と聞いたことがあった。プログラミング言語っていろいろあるし何やったらいいか、わかんない、という子供心だったと思う。

そのおじさんは、多分真剣に考えてくれて答は次のようなものだった。

  • プログラミング言語は何でもいいので、まずひとつの言語に定めて、それをちゃんとマスターしなさい。
  • マスターするためには、よい問題集を一冊やること。それを繰り返し何度もやることが大事。

結局、子供のときはプログラミング言語に手を出すことはなかったが、今、おじさんの言葉に従ってCommon Lispに絞って、ちゃんとマスターしようとしている。

しかし、このおじさんのアドバイスを拡張しなければいけない、という思いが強くなってきた。このおじさんのアドバイス通りにやるとしたら、C言語しかないのではないか? というのは、プログラミングがちゃんとできるようになるには、基盤として、

  1. あるプログラミング言語とアルゴリズム能力の習得
  2. OSの知識
  3. 効率的にプログラムを書くための環境の知識

が必要に思う。これが例えば1がCommon Lispだとすると、まあ、

  1. Common Lisp
  2. Unix
  3. Emacs

というのが順当になる。2をちゃんと理解するには、C言語は必須であるし、3をちゃんと理解するにはEmacs Lispの理解は必須である。なので、3言語をマスターしなければならない。

これがC言語ならば、

  1. C言語
  2. Unix
  3. Vi

という組み合わせがあって、これはC言語ひとつが言語としては必須と考えてもよいと思えるからだ。

ということで、この際腹をきめる必要がある。破戒して、CL、ELisp、Unix/Cをみつどもえで習得していく必要があるということだ。

2008年9月14日日曜日

C言語はハードウエアにべったり?

感じたことを書いておこうと思う。

  • C言語はハードウエアべったり(ノイマン型べったり)だから速い、とか言われていた。
  • 自分もそれを鵜呑みにして、そう信じていた。

  • でも、パタヘネでコンピュータアーキテクチャを自分自身で確認しなおして、さらにC言語も自分自身で確認しなおすと、どうもべったりとは思えない。
  • パイプラインだとか、記憶階層だとか、そういうような速度に影響を与える重要要素がアーキテクチャにはたくさんあるのだが、それはC言語の言語仕様には見えていない。
  • というか、ものによっては、命令セット(機械語)にも見えていない。逆に、隠蔽した上で、うまく最適化するのがアーキテクチャの善し悪しになっている。IA32はマイクロアーキテクチャなのでそれが顕著だが、MIPSだってそうだ。
  • なので、C言語はあくまでC言語たるモデルに基づいた高級言語にすぎないと思う。
  • それが速い、というのは、おそらく、それが速いようにアーキテクチャが調整されて、コンパイラが作り込まれて、というある意味優遇されている環境によるのではないか。その意味での、癒着構造としてのべったりならわかる。C言語がアーキテクチャにべったりなんじゃなくて、アーキテクチャがC言語にべったり、ということ。同じようだが、違う。
  • マルチコアとかの新しい状況は、本当にこのままC言語を偏重してアーキテクチャを進化させていくので大丈夫なのか、という時期に来ていると感じさせる。

  • C言語を入門する際に、実はこの誤解が学習障害になっているのではないか、と思った。
  • ハードウエアべったりというようにイメージしても、実際のハードウエアは違うからそこがずれている。
  • 一番大きなずれは、変数名などをどのように管理しているかというシンボル管理の側面を、ハードウエアべったりということを意識して、メモリと箱モデルですましてしまい、シンボル管理を言語モデルというか仕様としてどのようにしているかを説明しないところではないか。自分は、C言語の前にCommon Lispをかじっていたので、そのあたりを適宜補って理解することができた。今でもC言語をたいして理解したとはいえないが、それがなかったら、もっとぐだぐだになってしまったと思う。

  • C言語が速いというのは、上のような長年の優遇措置を除けば、静的型付けであることと、OSがC言語でかかれているのでシステムコールを他言語にくらべてもっともダイレクトにcallできること、というのが理由ではないか。

  • というわけで、昔はハードウエアべったりだったのかもしれませんが、今は違うと思う。

  • あ、小さな組み込み系とかで、アーキテクチャがシンプルなものは、今でもべったりというのはありそうですね。

  • C言語が速い、というのは、ある意味事実だが、それが「言語仕様がノイマン型にべったり」だからというのは理由としても違うし、このべったりというのは単体の言明としても違うと思った。

2008年8月28日木曜日

【C算法】第6章 ソート (その8)

週の前半は、、、と毎週いっている。なんとかせねば。なんとか生きて乗り切った、という感じ。
さて、木構造が終わったので、6-8 ヒープソート。。。


  • 順序木  :兄弟の間に順序関係を有する木。
    無順序木 :兄弟の間に順序関係を有しない木。

    2進木  :度数がたかだか2の木。
    2分木  :兄弟に左右の区別がある2進木。

    完全2分木:根から下方へむかって、同一レベルでは左から順に詰められている2分木
    2分探索木:ノードの値とくらべて、左部分木の値は小さく、右部分木の値は大きい。
    ヒープ  :親の値が子の値以上になっている完全2分木。兄弟の大小関係は任意。
    半順序木 :ヒープの別名。

  • 完全2分木に配列の要素をわりあてたときの様相。

    a[i]の親はa[(i - 1) / 2]
    a[i]の左の子はa[i * 2 + 1]
    a[i]の右の子はa[i * 2 + 2]

    なんで??
  • ためす。

    1の親は、(1 - 1)/2 = 0
    1の左の子は、1 * 2 + 1 =3
    1の右の子は、1 * 2 + 2 =4
    2の親は、(2 - 1)/2 = 0
    2の左の子は、2 * 2 + 1 =5
    2の右の子は、2 * 2 + 2 =6
    3の親は、(3 - 1)/2 = 1
    3の左の子は、3 * 2 + 1 =7
    3の右の子は、3 * 2 + 2 =8
    4の親は、(4 - 1)/2 = 1
    4の左の子は、4 * 2 + 1 =9
    4の右の子は、4 * 2 + 2 =10

    たしかにそうなっている。なんでこうなるの?
  • まず、heapを階層毎にグループにわけると、
    {{0},{1,2},{3,4,5,6},{7,8,9,10,11,12,13,14},...}
    となる。法則性はある。。。かんがえる。。。
  • a[n]の子まで添字をふるには、まず、a[n]の階層の残りのノードと、既存のノード*2だけノードを処理する必要がある。
    ところで、木の左端の要素の系列は階層で上から下にならべると、a[0],a[1],a[3],a[7],a[15],...となる。これは(2^n) - 1である(n = 0,1,2,...)。
    一方各階層のノード数は、2^n (n=0,1,2,...)である。
    すると、a[(2^n) - 1]の子供に辿りつく前に添字をふるべきノードは同じ階層の残りだから、(2^n)-1個ある。ゆえに左端のノードについてはa[i]の子のノードがa[i*2 + (1 or 2)]というのはなりたっている。
    つぎに2^n個の階層のノードで、(2^n)-1から数えてたどりつくまでにp個のノードを経るような(p=[0,(2^n)-1])ノードに着目しよう。すなわち、(2^n)-1+pという添字のノードだ。
    さて子のノードに辿りつくまでに添字をふるべきノードの数は、同じ階層で、(2^n)-p個ある。ひとつしたの階層でもふるべきであり、同じ階層でその対象となるのは、p個だから、2*p個の添字をふる。よって、ふられる添字は、(2^n) - p + 2*p = (2^n)+p。
    さて、親の添字は、(2^n)-1+pであり、子の一歩のノードの添字は、(2^n)+p-2+(2^n)+p=2((2^n)-1+p)だから、これもa[i]の子がa[i*2 + ( 1 or 2)]というのがなりたつ。■
    これで親から子はわかった。
  • 子から親は、親から子を逆転させればOK。
  • これで、heapというデータ構造を配列で実現できることがわかった。
  • あとはちょいちょい。

おお!ついに「新版C言語によるアルゴリズムとデータ構造」を読了した!
これで、

  • 「例解UNIXプログラミング教室」
  • 「アルゴリズムC」
  • 「新コンピュータサイエンス講座 コンパイラ」
  • 「Operationg Systems Design and Implementation 3rd Ed.」

のどれでも手をつけられるようになった。
どれからいこうかなぁ。シプサとの関連で、コンパイラにしとこうかな。

2008年8月24日日曜日

【C算法】第10章 木構造

だんだん終局が近づいてきた。

  • n進木:ノードの度数がたかだかnの木。
  • 2進木:ノードの度数がたかだか2の木。
  • 2分木:ノードの度数がたかだか2であり、子に左右の区別がある木。
  • 2分探索木:キー値について、どのノードにおいても、それの左部分木のノードは小さく、それの右部分木のノードは大きい2分木。
  • 2分探索木を深さ優先探索して通りがけ順でみると、キー値の昇順でノードが得られる。
  • いまさらながら、2分探索木はおなじメンツでも違う構成があることに気付いた。

      6
     / \
    2   7
     \
      3

        6
       / \
      3   7
     / 


  • 完全2分木

    • 最下層以外は全て「詰まって」いる。
    • 最下層は、左側から詰めていく。
    • 根から下流へ、各層を左から右へと添字をふっていくと、配列の添字に対応できる。

          0
         / \
        1   2
       / \
      3   4


  • ん? list10-2で

    else if (cond < 0)
    SearchNode(p->left, x);
    else
    SearchNode(p->right, x);

    は、次の間違いでは?

    else if (cond < 0)
    return (SearchNode(p->left, x));
    else
    return (SearchNode(p->right, x));


最後のほうがぐだぐだになったが木構造がおわった。
次回は6-8 ヒープソート。

2008年8月23日土曜日

【C算法】第8章 線形リスト (その2)

こつこつ。

  • 演習9-1。そうか、enumの要素と関数名も衝突するんだ。
  • ちょっとだけ、日本語を読み書きするようにC言語を読み書きする感覚がでてきた。ちょっとだけ。
  • ポインタで書かれたものを頭の中で追ったり頭の中でいじくりまわしたりするのが楽しくなってきた。

おお、線形リストがおわった。次回は「木構造」。