[루아2.1] Tree.c Tree.h

4 분 소요

Tree.h

Tree.h, Tree.c 파일은 루아 2.1에서 새로 생긴 파일입니다. 루아 1.1에서 그냥 표준 라이브러리 호출로 처리했던 동적 메모리 관리를 트리로 대체한 것으로 보입니다. 검색을 빠르게 하려는 요량으로 보이는데, 코드를 읽으면서 어디에서 트리를 쓰는지도 같이 추적하겠습니다.

#define NOT_USED  0xFFFE


typedef struct TaggedString
{
  unsigned long hash;  /* 0 if not initialized */
  char marked;   /* for garbage collection */
  char str[1];   /* \0 byte already reserved */
} TaggedString;
 
typedef struct TreeNode
{
 struct TreeNode *right;
 struct TreeNode *left;
 unsigned short varindex;  /* != NOT_USED  if this is a symbol */
 unsigned short constindex;  /* != NOT_USED  if this is a constant */
 TaggedString ts;
} TreeNode;

맨 위에 NOT_USED는 값은 의미 없고 쓰지 않는 값이라는 이름이 더 중요합니다. 트리 노드를 새로 생성할 때, 새로 생성한 노드에는 데이터가 없으므로 일단 비어 있는 쓰지 않는 노드라는 표시를 하는데 사용합니다.

TaggedString 구조체는 루아 1.1에서 애매하게 사용했던 문자열 메모리를 명시적으로 관리하려고 만든 자료 구조로 보입니다. 루아 1.1에서는 문자열로 사용하려고 동적 메모리 할당 받은 다음에 첫 번째 바이트를 건너뛰고 문자열 데이터를 저장했었습니다. 건너 뛴 첫 번째 바이트는 나중에 가비지 컬랙터에서 마킹 용도로 사용했고요. 루아 2.1에서는 아예 구조체로 만들어서 해당 위치를 marked라는 멤버 변수로 명시적으로 만들었습니다.

TreeNode는 이름이 설명하듯 트리의 노드 한 개의 자료 구조입니다. right, left 포인터는 트리의 다음 레벨 자손으로 내려가는 포인터일테고요. 심볼과 문자열 상수 인덱스로 보이는 변수 두 개가 있습니다. 그렇다면 루아 2.1에서 트리는 심볼 테이블과 문자열 상수 테이블을 구현하는데 쓰는것으로 보입니다. 마지막으로 TaggedString 인스턴스 선언이 있습니다.

Tree.c

전형적인 트리 자료 구조 구현일 것 같다는 예감이 듭니다. 진짜 그런지 읽어보겠습니다.

#define lua_strcmp(a,b)	(a[0]<b[0]?(-1):(a[0]>b[0]?(1):strcmp(a,b))) 


typedef struct StringNode {
  struct StringNode *next;
  TaggedString ts;
} StringNode;

static StringNode *string_root = NULL;

static TreeNode *constant_root = NULL;

볼 때마다 별 의미없어 보이는 문자열 비교 매크로가 가장 먼저 나옵니다. 심지어 이 문자열 비교 매크로는 어디 공통 헤더에 선언에 놓으면 될것 같은데 매번 C 파일에 조금씩 다르게 선언해 놓네요. 대체 이유가 뭔지 궁금합니다.

그리고 이어서 StringNode라는 구조체가 나옵니다. TaggedString 구조체에 대한 링크드 리스트입니다. 트리와 링크드 리스트를 따로 만드는게 아니라면 같은 문자열 데이터에 대해서 트리로 하나 관계를 만들고, 링크드 리스트로 관계를 또 만들어서 상황에 맞게 사용하려는 것으로 보입니다. 이후에 나오는 코드를 읽을 때 확인하겠습니다. 아니면 심볼 테이블은 링크드 리스트고 문자열 상수 테이블은 트리이고 이런식으로 쓰는 걸지도 모릅니다. 어느쪽일지는 곧 알게 될겁니다.

/*
** Insert a new constant/variable at the tree. 
*/
static TreeNode *tree_create (TreeNode **node, char *str)
{
 if (*node == NULL)
 {
  *node = (TreeNode *) luaI_malloc(sizeof(TreeNode)+strlen(str));
  (*node)->left = (*node)->right = NULL;
  strcpy((*node)->ts.str, str);
  (*node)->ts.marked = 0;
  (*node)->ts.hash = 0;
  (*node)->varindex = (*node)->constindex = NOT_USED;
  return *node;
 }
 else
 {
  int c = lua_strcmp(str, (*node)->ts.str);
  if (c < 0) 
   return tree_create(&(*node)->left, str);
  else if (c > 0)
   return tree_create(&(*node)->right, str);
  else
   return *node;
 }
}

트리의 노드 한 개를 새로 만드는 함수입니다. 문자열 자체는 정렬해서 right나 left로 들어갑니다. 바이너리 트리네요. 복잡해 보이지만 그냥 매우 일반적인 바이너리 트리 노드 생성 구현체입니다.

TaggedString *lua_createstring (char *str) 
{
  StringNode *newString;
  if (str == NULL) return NULL;
  lua_pack();
  newString = (StringNode *)luaI_malloc(sizeof(StringNode)+strlen(str));
  newString->ts.marked = 0;
  newString->ts.hash = 0;
  strcpy(newString->ts.str, str);
  newString->next = string_root;
  string_root = newString;
  return &(newString->ts);
}

아~ 이 함수를 보니 Tree.c 파일을 읽기 시작할 때 가졌던 의문이 해소됩니다. 같은 문자열 데이터에 대해 링크드 리스트, 트리를 만드는게 아니라 constant_root와 string_root를 각각 트리와 링크드 리스트로 관리하는가 봅니다. 분명 다르게 관리하고 호출하는 경로도 다른데 constant_root와 string_root를 왜 구분했고 어떻게 다른건지 모르겠네요.

TreeNode *lua_constcreate (char *str) 
{
 return tree_create(&constant_root, str);
}

그냥 tree_create() 함수를 호출하면서 트리 루트 노드를 constant_root로 지정한 래퍼(wrapper) 함수입니다.

/*
** Garbage collection function.
** This function traverse the string list freeing unindexed strings
*/
Long lua_strcollector (void)
{
  StringNode *curr = string_root, *prev = NULL;
  Long counter = 0;
  while (curr)
  {
    StringNode *next = curr->next;
    if (!curr->ts.marked)
    {
      if (prev == NULL) string_root = next;
      else prev->next = next;
      luaI_free(curr);
      ++counter;
    }
    else
    {
      curr->ts.marked = 0;
      prev = curr;
    }
    curr = next;
  }
  return counter;
}

아직 루아 가비지 컬랙션이 mark를 어떻게 쓰는건지 제대로 파악하지 못하고 있습니다. 그래도 확실히 아는 것은 루아는 mark가 0인 문자열 데이터를 가비지 컬랙션 대상으로 식별해서 메모리를 해제한다는 것입니다.

/*
** Return next variable.
*/
static TreeNode *tree_next (TreeNode *node, char *str)
{
 if (node == NULL) return NULL;
 else if (str == NULL) return node;
 else
 {
  int c = lua_strcmp(str, node->ts.str);
  if (c == 0)
   return node->left != NULL ? node->left : node->right;
  else if (c < 0)
  {
   TreeNode *result = tree_next(node->left, str);
   return result != NULL ? result : node->right;
  }
  else
   return tree_next(node->right, str);
 }
}

TreeNode *lua_varnext (char *n)
{
  TreeNode *result;
  char *name = n;
  while (1)
  { /* repeat until a valid (non nil) variable */
    result = tree_next(constant_root, name);
    if (result == NULL) return NULL;
    if (result->varindex != NOT_USED &&
        s_tag(result->varindex) != LUA_T_NIL)
      return result;
    name = result->ts.str;
  }
}

주석을 보나 이름을 보나 파라메터 str이 저장된 트리 노드의 다음 노드를 리턴하는 함수로 생각됩니다만, 구현이 이상하네요. 위에 lua_createstring() 함수를 보면 left에 작은 값이 들어가는 바이너리 서치 트리인데, 그러면 흔히 상식적으로 말하는 next()란 정렬 순서대로 파라메터 str의 다음 문자열이 있는 노드를 리턴해야 할텐데 왜 left를 리턴하고 또, left가 null일 때 right를 리턴하는지 모르겠습니다. 저러면 뭔가 꼬일텐데.. 노드를 돌리지 않고 AVL을 만드는건가? 별 의심을 다 해봤으나 딱히 의도를 파악할 수 없었습니다.

아래에 lua_varnext() 함수를 봐도 그냥 정말 next 노드를 찾아서 그 노드가 비어있는 노드가 아니고 값이 nil이 아닌지 확인한다음 리턴하는 함수입니다. 이게 정상 동작하는지 조차 의심스럽습니다. 다음 릴리즈에서 어떻게 변경되는지 꼭 확인해야 겠습니다.

댓글남기기