[루아1.1] hash.c hash.h 읽기

9 분 소요

Hash.h

Hash.h 파일은 아주 짧은 파일입니다. 구현이 있는 Hash.c도 350 줄 정도로 길지 않습니다. 가벼운 마음으로 읽기 시작하겠습니다. 읽기 전에 왜 파일 이름이 해시(Hash)인지 궁금하네요. 해시 함수 관련 알고리즘을 구현한건가… 읽어 보면 알겠지요.

typedef struct node
{
 Object ref;
 Object val;
 struct node *next;
} Node;

typedef struct Hash
{
 char           mark;
 unsigned int   nhash;
 Node         **list;
} Hash;

Hash.h 파일은 Node와 Hash 자료 구조를 정의하면서 시작합니다. Hash 자료 구조가 Node 자료 구조를 포함하고 있으니 Node 자료 구조를 먼저 읽어 보겠습니다. Node 구조체는 모양만 보면 전형적인 링크드 리스트입니다. Object 타입으로 ref와 val이 멤버입니다. 이름만 봐서는 reference와 value 일 것 같습니다. 그럼 Object 타입은 뭔지 찾아 볼까요.

typedef struct Object
{
 Type  tag;
 Value value;
} Object;

Opcode.h에 선언이 있습니다. 멤버는 tag와 value입니다. tag는 Type 타입인데요.

typedef enum
{
 T_MARK,
 T_NIL,
 T_NUMBER,
 T_STRING,
 T_ARRAY,
 T_FUNCTION,
 T_CFUNCTION,
 T_USERDATA
} Type;

이렇게 생긴 enum 선언입니다. MARK, NIL, NUMBER 등 내용은 루아의 기본 자료형입니다. 그렇다면 Object는 루아의 기본 자료형에 대한 구현인듯 합니다. tag로 자료형이 뭔지 저장하고 실제 데이터는 value에 저장하는 방식인듯 합니다. value는 Value 타입이니, Value 타입도 보겠습니다. 제 예상에 공용체가 나와야 할 것 같긴합니다.

typedef union
{
 Cfunction 	 f;
 real    	 n;
 char      	*s;
 Byte      	*b;
 struct Hash    *a;
 void           *u;
} Value;

예상대로 공용체로 선언했군요. 각각 f는 루아의 CFunction, n은 Number, s는 문자열, b는 뭔지 모르겠고, a는 배열, u는 Userdata 값을 표시하려고 선언한 것으로 보입니다.

다시 Hash.h로 가서 Hash 구조체를 보겠습니다. Node 타입은 Hash의 노드 한 개를 추상화하고 있어서 이름도 Node 인 듯합니다. 그리고 Object 타입 멤버인 value가 Hash 타입 자체를 공용체로 다시 레퍼런스 하기 때문에 Hash 자료 구조는 내부에 Hash를 또 가지는 순환 자료 구조입니다. 아직 Hash 자료 구조가 뭘 하는 녀석인지 모르겠으나 왠지 루아 테이블 타입을 구현하는 녀석이 아닐까 하는 생각이 듭니다. 이따가 Hash.c 읽으면서 함수 호출 관계 찾아보면 알 수 있을 겁니다. 루아 테이블 타입이 일종의 연관 배열이고 연관 배열을 구현하는 대표적인 방법이 해시 테이블이니 파일 이름이 Hash 인 것이 이해가 되니까요. 그리고 Table.c에서 Hash.c에 구현한 함수를 사용하는지 확인해 보면 될 것 같습니다. 정말 그런지 Hash.c 파일을 보겠습니다.

Hash.c

#include <string.h>
#include <stdlib.h>

#include "mm.h"

#include "opcode.h"
#include "hash.h"
#include "inout.h"
#include "table.h"
#include "lua.h"

#define streq(s1,s2)	(strcmp(s1,s2)==0)
#define strneq(s1,s2)	(strcmp(s1,s2)!=0)

mm.h 파일은 내용이 없는 파일입니다. 나중에 내용이 채워질지 아니면 없어질지 궁금하군요. opcode.h, hash.h, inout.h, table.h, lua.h 이렇게 몇 개 안되는 헤더 파일을 모두 #include했습니다. streq()와 strneq() 매크로는 strcmp() 함수를 쓴 전형적 패턴의 매크로입니다.

#define nhash(t)	((t)->nhash)
#define nodelist(t)	((t)->list)
#define list(t,i)	((t)->list[i])
#define markarray(t)    ((t)->mark)
#define ref_tag(n)	(tag(&(n)->ref))
#define ref_nvalue(n)	(nvalue(&(n)->ref))
#define ref_svalue(n)	(svalue(&(n)->ref))

위 매크로는 Node 구조체와 Hash 구조체 맴버에 접근하기 편하게 만든 매크로입니다.

#ifndef ARRAYBLOCK
#define ARRAYBLOCK 50
#endif

typedef struct ArrayList
{
 Hash *array;
 struct ArrayList *next;
} ArrayList;

static ArrayList *listhead = NULL;

ArrayList는 Hash 자료형을 array라는 이름으로 선언해서 링크드 리스트로 관리하는 구조체입니다. Hash 자체로 Node 타입의 링크드 리스트를 가지고 있습니다. 그래서 ArrayList는 Node 타입의 2차원 링크드 리스트가 되겠네요. 상식적으로 생각해보면 ArrayList 자체가 해시 테이블이고 array 맴버인 Hash 타입 변수는 해시 테이블 바스켓 한 개입니다. 해시 테이블 바스켓이 충돌(collision) 나면 해당 바스켓에 링크드 리스트나 배열로 연결하는 것이 일반적인 해시 테이블 구현이므로 ArrayList 선언은 매우 전형적인 구현이라고 볼 수 있겠네요.

static int head (Hash *t, Object *ref)		/* hash function */
{
 if (tag(ref) == T_NUMBER) return (((int)nvalue(ref))%nhash(t));
 else if (tag(ref) == T_STRING)
 {
  int h;
  char *name = svalue(ref);
  for (h=0; *name!=0; name++)		/* interpret name as binary number */
  {
   h <<= 8;
   h  += (unsigned char) *name;		/* avoid sign extension */
   h  %= nhash(t);			/* make it a valid index */
  }
  return h;
 }
 else
 {
  lua_reportbug ("unexpected type to index table");
  return -1;
 }
}

head() 함수는 정적 함수입니다. 주석에는 hash function이라고 써 놓고 왜 이름이 head인지 모르겠군요. 첫 번째 릴리즈 코드라서 아직 정리가 안된건지 아니면 어떤 의미가 있는건지 모르겠습니다. 구현을 봐도 가장 단순한 형태의 해시 함수 입니다. 해시 테이블의 바스켓 위치를 받는 가장 간단한 방법이 그냥 해시 테이블 크기로 나머지를 구해서 쓰는 것입니다. 만약 레퍼런스 타입이 문자열일 때는 문자열을 정해진 규칙으로 숫자로 변환해서 나머지를 구해 값을 만듭니다. 규칙은 아무래도 상관없습니다. 같은 입력에 같은 출력이 나오기만 하면 됩니다. 그리고 해시 테이블 크기를 넘으면 안되고요. 구현만 봐서는 주석에 쓴 대로 해시 함수인데 이름이 헷갈리게 하는 군요.

static Node *present(Hash *t, Object *ref, int h)
{
 Node *n=NULL, *p;
 if (tag(ref) == T_NUMBER)
 {
  for (p=NULL,n=list(t,h); n!=NULL; p=n, n=n->next)
   if (ref_tag(n) == T_NUMBER && nvalue(ref) == ref_nvalue(n)) break;
 }  
 else if (tag(ref) == T_STRING)
 {
  for (p=NULL,n=list(t,h); n!=NULL; p=n, n=n->next)
   if (ref_tag(n) == T_STRING && streq(svalue(ref),ref_svalue(n))) break;
 }  
 if (n==NULL)				/* name not present */
  return NULL;
#if 0
 if (p!=NULL)				/* name present but not first */
 {
  p->next=n->next;			/* move-to-front self-organization */
  n->next=list(t,h);
  list(t,h)=n;
 }
#endif
 return n;
}

present() 정적 함수는 해시 테이블 t에서 h 해시값 바스켓의 ref 인덱스를 찾아서 리턴하는 함수 입니다. 쉽게 말해 검색 함수죠. 구현은 특별할 것 없는 직관적인 구현입니다.

static void freelist (Node *n)
{
 while (n)
 {
  Node *next = n->next;
  free (n);
  n = next;
 }
}

freelist() 정적 함수는 이름이 동작을 잘 설명하네요. 노드 리스트 n을 쭉 따라가면서 메모리를 모두 해제합니다.

/*
** Create a new hash. Return the hash pointer or NULL on error.
*/
static Hash *hashcreate (unsigned int nhash)
{
 Hash *t = new (Hash);
 if (t == NULL)
 {
  lua_error ("not enough memory");
  return NULL;
 }
 nhash(t) = nhash;
 markarray(t) = 0;
 nodelist(t) = newvector (nhash, Node*);
 if (nodelist(t) == NULL)
 {
  lua_error ("not enough memory");
  return NULL;
 }
 return t;
}

해시 테이블에 바스켓 하나를 새로 생성하는 함수입니다. nhash는 바스켓 하나에 최대한 연결하는 노드 링크드 리스트 개수입니다.

#define newvector(n,s)	((s *)calloc(n,sizeof(s)))

newvector() 매크로는 calloc() 함수를 호출하는 매크로입니다. 그래서 Hash 타입 인스턴스 하나를 만들고 list 맴버에 nhash 만큼 메모리를 확보해서 잡아줍니다.

/*
** Delete a hash
*/
static void hashdelete (Hash *h)
{
 int i;
 for (i=0; i<nhash(h); i++)
  freelist (list(h,i));
 free (nodelist(h));
 free(h);
}

이름이 동작을 충분히 설명하는 함수입니다. freelist() 함수를 안에서 호출합니다. 앞에서 읽었던 함수지요. Hash 인스턴스가 가지고 있는 list 인스턴스를 따라가면서 메모리 해제를 해서 내부에 동적 할당한 메모리를 모두 해제하고 이어서 Hash 타입 인스턴스 자체에 메모리 할당을 해제합니다.

/*
** Mark a hash and check its elements 
*/
void lua_hashmark (Hash *h)
{
 if (markarray(h) == 0)
 {
  int i;
  markarray(h) = 1;
  for (i=0; i<nhash(h); i++)
  {
   Node *n;
   for (n = list(h,i); n != NULL; n = n->next)
   {
    lua_markobject(&n->ref);
    lua_markobject(&n->val);
   }
  }
 } 
}

lua_hashmark() 함수는 동작은 읽으면서 바로 이해할 수 있는 수준으로 코드는 어렵지 않으나 Hash 구조체에 mark 맴버 변수가 하는일이 뭔지 파악이 안되서 함수 목적을 알 수가 없습니다. 동작 자체는 쉽습니다. Hash 구조체에 mark 맴버 변수가 0이면 값을 1로 바꿉니다. 그리고 노드 리스트를 따라가면서 Object 타입 인스턴스에 있는 Hash 타입 변수의 mark도 계속 따라가면서 모든 mark 맴버 변수 값을 다 1로 바꿉니다. 이 mark가 하는일이 대체 뭘까요..

/*
** Garbage collection to arrays
** Delete all unmarked arrays.
*/
void lua_hashcollector (void)
{
 ArrayList *curr = listhead, *prev = NULL;
 while (curr != NULL)
 {
  ArrayList *next = curr->next;
  if (markarray(curr->array) != 1)
  {
   if (prev == NULL) listhead = next;
   else              prev->next = next;
   hashdelete(curr->array);
   free(curr);
  }
  else
  {
   markarray(curr->array) = 0;
   prev = curr;
  }
  curr = next;
 }
}

이 함수를 읽으니 Hash 구조체에 mark 맴버가 하는일이 뭔지 알것 같습니다. 가비지 컬랙션을 구현하는 수단이었습니다. 가비지 컬랙션은 쉽게 말해서 레퍼런스 카운트가 0이면 VM이 알아서 메모리를 해제하는 개념입니다. 루아는 레퍼런스 카운트라는 개념을 더 단순화해서 0과 1로만 처리하는지 lua_hashcollector() 함수 코드를 보면 1이 아닐 때 메모리 해제를 하고, 1일 때는 0으로 바꿉니다.

/*
** Create a new array
** This function insert the new array at array list. It also
** execute garbage collection if the number of array created
** exceed a pre-defined range.
*/
Hash *lua_createarray (int nhash)
{
 ArrayList *new = new(ArrayList);
 if (new == NULL)
 {
  lua_error ("not enough memory");
  return NULL;
 }
 new->array = hashcreate(nhash);
 if (new->array == NULL)
 {
  lua_error ("not enough memory");
  return NULL;
 }

 if (lua_nentity == lua_block)
  lua_pack(); 

 lua_nentity++;
 new->next = listhead;
 listhead = new;
 return new->array;
}

해시 테이블 자체인 ArrayList 구조체의 인스턴스를 생성하는 함수입니다. 함수 코드 자체는 어렵지 않습니다. 그냥 계속 메모리 할당입니다. 한 부분 이해 안되는 곳이 있습니다. lua_nentity 변수와 lua_pack() 함수 부분입니다. 아직은 이해가 되지 않으므로 그냥 넘어가겠습니다. 나중에 lua_pack() 함수를 읽을 때 다시 생각해 보려고 합니다.

/*
** If the hash node is present, return its pointer, otherwise create a new
** node for the given reference and also return its pointer.
** On error, return NULL.
*/
Object *lua_hashdefine (Hash *t, Object *ref)
{
 int   h;
 Node *n;
 h = head (t, ref);
 if (h < 0) return NULL; 
 
 n = present(t, ref, h);
 if (n == NULL)
 {
  n = new(Node);
  if (n == NULL)
  {
   lua_error ("not enough memory");
   return NULL;
  }
  n->ref = *ref;
  tag(&n->val) = T_NIL;
  n->next = list(t,h);			/* link node to head of list */
  list(t,h) = n;
 }
 return (&n->val);
}

lua_hashdefine() 함수의 동작은 주석에 설명이 잘 적혀 있습니다. 해시 태이블 t와 인덱스 ref가 파라메터로 넘어오면 head() 함수를 호출해서 해시값을 구합니다. 그러고나면 present() 함수를 호출해서 노드를 찾습니다. 만약 노드가 없으면 노드를 새로 생성합니다. 노드를 새로 생성하면 노드의 값에는 nil을 기본값으로 넣습니다.

/*
** Internal function to manipulate arrays. 
** Given an array object and a reference value, return the next element
** in the hash.
** This function pushs the element value and its reference to the stack.
*/
static void firstnode (Hash *a, int h)
{
 if (h < nhash(a))
 {  
  int i;
  for (i=h; i<nhash(a); i++)
  {
   if (list(a,i) != NULL)
   {
    if (tag(&list(a,i)->val) != T_NIL)
    {
     lua_pushobject (&list(a,i)->ref);
     lua_pushobject (&list(a,i)->val);
     return;
    }
    else
    {
     Node *next = list(a,i)->next;
     while (next != NULL && tag(&next->val) == T_NIL) next = next->next;
     if (next != NULL)
     {
      lua_pushobject (&next->ref);
      lua_pushobject (&next->val);
      return;
     }
    }
   }
  }
 }
 lua_pushnil();
 lua_pushnil();
}

주석에 설명이 있듯, firstnode() 정적 함수는 바로 이어서 나오는 lua_next() 함수에서 쓰려고 만든 정적 함수입니다. firstnode() 함수는 이름을 보면 해시 테이블 a에서 h 해시 함수 값 바스켓에 첫 번째 노드를 어떻게 하는 함수 같습니다. 어떻게 하는지 계속 읽겠습니다. 해시 테이블 list 멤버를 먼저 찾아서 리스트 노드가 NULL인지 검사합니다. 일단 루아 구현에서 메모리 할당이 되었는지 확인하는 것이지요. 메모리 할당이 되었다면 이제 루아 VM 수준에서 값이 nil인지 봅니다. nil이 아닌 첫 번째 노드를 리턴합니다.

void lua_next (void)
{
 Hash   *a;
 Object *o = lua_getparam (1);
 Object *r = lua_getparam (2);
 if (o == NULL || r == NULL)
 { lua_error ("too few arguments to function `next'"); return; }
 if (lua_getparam (3) != NULL)
 { lua_error ("too many arguments to function `next'"); return; }
 if (tag(o) != T_ARRAY)
 { lua_error ("first argument of function `next' is not a table"); return; }
 a = avalue(o);
 if (tag(r) == T_NIL)
 {
  firstnode (a, 0);
  return;
 }
 else
 {
  int h = head (a, r);
  if (h >= 0)
  {
   Node *n = list(a,h);
   while (n)
   {
    if (memcmp(&n->ref,r,sizeof(Object)) == 0)
    {
     if (n->next == NULL)
     {
      firstnode (a, h+1);
      return;
     }
     else if (tag(&n->next->val) != T_NIL)
     {
      lua_pushobject (&n->next->ref);
      lua_pushobject (&n->next->val);
      return;
     }
     else
     {
      Node *next = n->next->next;
      while (next != NULL && tag(&next->val) == T_NIL) next = next->next;
      if (next == NULL)
      {
       firstnode (a, h+1);
       return;
      }
      else
      {
       lua_pushobject (&next->ref);
       lua_pushobject (&next->val);
      }
      return;
     }
    }
    n = n->next;
   }
   if (n == NULL)
    lua_error ("error in function 'next': reference not found");
  }
 }
}

lua_next() 함수는 구현 코드의 패턴이 지금까지 읽었던 함수들하고 다릅니다. lua_getparam() 같은 함수는 루아를 임베딩 스크립트로 포함하고 있는 프로그램(루아에서는 호스트 프로그램이라고 부릅니다)에서 호출하는 루아 API입니다. lua_next() 호출을 추적하면 Table.c에 tablebuffer라는 함수 포인터 테이블에 연결되있습니다. 루아 빌트인 함수 구현인가? 아직 모르겠습니다. 이 함수는 지금이 아니라 나중에 Table.c 파일을 읽을 때 흐름을 파악하면서 같이 읽는 것이 더 좋을것 같습니다.

댓글남기기