CodeReading: EmacsLisp "defsubr"関数

Kazuki Ohta, 2005/01/28


前回は関数登録の仕組みを解き明かす部分でdefsubr関数の出現まで追ったが、今回はさらにその中身まで見ていきたいと思う。

defsubrはsrc/lread.cで次のように定義されている。
void
defsubr (sname)
     struct Lisp_Subr *sname;
{
  Lisp_Object sym;
  sym = intern (sname->symbol_name);
  XSETSUBR (XSYMBOL (sym)->function, sname);
}
intern関数でシンボル名からシンボルを取り出し、それに対してXSETSUBRで関数をセットしている。おそらくintern内で何かしらシンボルの管理を行っていて、名前に対応するポインタを返しているのだろう。では、internを覗いて見る。この関数もsrc/lread.cで定義されている。
/* Intern the C string STR: return a symbol with that name,
   interned in the current obarray.  */

Lisp_Object
intern (str)
     const char *str;
{
  Lisp_Object tem;
  int len = strlen (str);
  Lisp_Object obarray;

  obarray = Vobarray;
  if (!VECTORP (obarray) || XVECTOR (obarray)->size == 0)
    obarray = check_obarray (obarray);
  tem = oblookup (obarray, str, len, len);
  if (SYMBOLP (tem))
    return tem;
  return Fintern (make_string (str, len), obarray);
}
コメントによるとobarrayという配列を管理し、名前による対応付けを行っているようだ。つまり、「ハッシュ」だ。

obarrayは実際にはグローバル変数Vobarrayである事が見て取れる。最初のif文では、obarrayがVECTOR型である事、そしてsizeが0で無い事を確認し、もしそうでなければcheck_obarrayでobarrayを検査する。そしてoblookupで名前からLisp_Objectを検索する。ここでtemがSYMBOL型で有ればそのまま返すが、そうでなければFinternという関数が呼ばれている。

ここではcheck_obarrayは省略し、oblookupとFinternを順番に見ていく事にする。Error処理は読み出すと長そうだから...。最初はoblookup。
/* Return the symbol in OBARRAY whose names matches the string
   of SIZE characters (SIZE_BYTE bytes) at PTR.
   If there is no such symbol in OBARRAY, return nil.

   Also store the bucket number in oblookup_last_bucket_number.  */

Lisp_Object
oblookup (obarray, ptr, size, size_byte)
     Lisp_Object obarray;
     register const char *ptr;
     int size, size_byte;
{
  int hash;
  int obsize;
  register Lisp_Object tail;
  Lisp_Object bucket, tem;

  if (!VECTORP (obarray)
      || (obsize = XVECTOR (obarray)->size) == 0)
    {
      obarray = check_obarray (obarray);
      obsize = XVECTOR (obarray)->size;
    }
  /* This is sometimes needed in the middle of GC.  */
  obsize &= ~ARRAY_MARK_FLAG;
  /* Combining next two lines breaks VMS C 2.3.  */
  hash = hash_string (ptr, size_byte);
  hash %= obsize;
  bucket = XVECTOR (obarray)->contents[hash];
  oblookup_last_bucket_number = hash;
  if (EQ (bucket, make_number (0)))
    ;
  else if (!SYMBOLP (bucket))
    error ("Bad data in guts of obarray"); /* Like CADR error message */
  else
    for (tail = bucket; ; XSETSYMBOL (tail, XSYMBOL (tail)->next))
      {
	if (SBYTES (SYMBOL_NAME (tail)) == size_byte
	    && SCHARS (SYMBOL_NAME (tail)) == size
	    && !bcmp (SDATA (SYMBOL_NAME (tail)), ptr, size_byte))
	  return tail;
	else if (XSYMBOL (tail)->next == 0)
	  break;
      }
  XSETINT (tem, hash);
  return tem;
}
しかしコメントがしっかりしていて良いですね。これも結構長い関数なのにコメントだけで動きがつかめる。最初は先ほどと同じくobarrayのチェックから。その次はGC用の対策だろうか。ARRAY_MARK_FLAGはsrc/lisp.hで次のように定義されている。
/* In the size word of a vector, this bit means the vector has been marked.  */

#ifndef ARRAY_MARK_FLAG
#define ARRAY_MARK_FLAG ((EMACS_INT) ((EMACS_UINT) 1 << (VALBITS + GCTYPEBITS - 1)))
#endif /* no ARRAY_MARK_FLAG */
GC用のマークフラグ、それもvector用の。ここではこのFLAGをnotしてsizeにandしている事から、FLAG bitを0にしている事が分かる。何故かというと、GC中にはマークフラグが1になる事が有るが、これではvectorの正しいsizeが得られないのでここでクリアしている。つまり、obarrayがマークされている状態で呼び出されると、(本来のsize + (1 << ARRAY_MARK_FLAG))がobsizeとして得られてしまうのだ。なぜsize部分にGC情報を...と思うかもしれないが、これはlisp.hで見たようにcellのサイズを8 byteにする為の涙ぐましい努力である。

hash_stringはハッシュ関数。結果をhashに代入し、vectorのcontentsからbucketを取り出す。hashはコメント通りにoblookup_last_bucket_numberに保存しておく。

その次のif文が個人的には気持ち悪い。しかし良く見てみると、oblookupの返り値からhashの値を得られるようにするという意図が見える。SYMBOLじゃ無い場合はエラーを吐く。その次のfor文ではbucketが何やらリストのように振る舞っている。「オープンハッシュ法」を使っている訳ですな。リストを辿っていって、名前と対応するものが有ればtailを返し、最後まで辿って見付からなければループを抜ける。定石。

一応hash_stringも見ておこう。
static int
hash_string (ptr, len)
     const unsigned char *ptr;
     int len;
{
  register const unsigned char *p = ptr;
  register const unsigned char *end = p + len;
  register unsigned char c;
  register int hash = 0;

  while (p != end)
    {
      c = *p++;
      if (c >= 0140) c -= 40;
      hash = ((hash<<3) + (hash>>28) + c);
    }
  return hash & 07777777777;
}
マジックナンバーが飛び出す。うーん、なんだこれ?なんか効率的なhash関数の実装に関する方法が詰まっているのかなぁ。知っている方は教えて下さい。

さて、oblookupは見終わったので次はFinternを見ていく(in src/lread.c)。
DEFUN ("intern", Fintern, Sintern, 1, 2, 0,
       doc: /* Return the canonical symbol whose name is STRING.
If there is none, one is created by this function and returned.
A second optional argument specifies the obarray to use;
it defaults to the value of `obarray'.  */)
     (string, obarray)
     Lisp_Object string, obarray;
{
  register Lisp_Object tem, sym, *ptr;

  if (NILP (obarray)) obarray = Vobarray;
  obarray = check_obarray (obarray);

  CHECK_STRING (string);

  tem = oblookup (obarray, SDATA (string),
		  SCHARS (string),
		  SBYTES (string));
  if (!INTEGERP (tem))
    return tem;

  if (!NILP (Vpurify_flag))
    string = Fpurecopy (string);
  sym = Fmake_symbol (string);

  if (EQ (obarray, initial_obarray))
    XSYMBOL (sym)->interned = SYMBOL_INTERNED_IN_INITIAL_OBARRAY;
  else
    XSYMBOL (sym)->interned = SYMBOL_INTERNED;

  if ((SREF (string, 0) == ':')
      && EQ (obarray, initial_obarray))
    {
      XSYMBOL (sym)->constant = 1;
      XSYMBOL (sym)->value = sym;
    }

  ptr = &XVECTOR (obarray)->contents[XINT (tem)];
  if (SYMBOLP (*ptr))
    XSYMBOL (sym)->next = XSYMBOL (*ptr);
  else
    XSYMBOL (sym)->next = 0;
  *ptr = sym;
  return sym;
}
あれ?またoblookupするのか?これは結構効率悪くないか?

うーん、とりあえず置いといて処理を見ていく。oblookupで見付からなかった場合にはFmake_symbolで新しいシンボルを作成する。そしてinternedを設定。そしてstringの最初の一文字が":"もしくはobarrayがinitial_obarrayの場合はconstantフラグを立て、valueにはsym自身をセットする。

XINT(tem)ってのがhash内のbucketの位置なので、contentsからそこを引っ張ってくる。もしそのbucketが空じゃなければ(Symbolだったら)nextを現在の先頭slotに設定。空だったら0にする。そしてsymをbucketの先頭に挿入して処理終了と。

二重oblookupを防ぐにはどうしたら良いんだろうか?安直な方法としてはinternから直接Finternだけを呼び出す方法が有るが、これだとmake_stringする手間が有る。internは色々な場所で使われる関数なので、内部でこのような無駄なobjectを生成しているとGCの頻度が高くなってしまい逆に効率が落ちそうだ。なのでoblookupしない版のFinternを作成し、それをinternとFintern両方から呼び出すというのが良さそうだ。んーでもなんでやってないんだろう?


[ return ]