[루아2.1] Hash.c Hash.h

6 분 소요

Hash.h

루아는 배열과 리스트 자료 구조를 해시 테이블로 관리합니다. Hash.h와 Hash.c 파일은 해시 테이블을 구현하는 코드가 작성되 있습니다.

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

typedef struct Hash
{
 struct Hash   *next;
 char           mark;
 Word          nhash;
 Word           nuse;
 Node          *node;
} Hash;

해시 테이블 노드는 해시 키와 값입니다. ref가 키이고 val이 값입니다. Hash는 기본적으로 링크드 리스트입니다.

Hash.c

두 번째 읽는 파일이니 빠르게 읽겠습니다.

#define streq(s1,s2)	(s1 == s2 || (*(s1) == *(s2) && strcmp(s1,s2)==0))

#define nhash(t)	((t)->nhash)
#define nuse(t)		((t)->nuse)
#define markarray(t)    ((t)->mark)
#define nodevector(t)	((t)->node)
#define node(t,i)	(&(t)->node[i])
#define ref(n)		(&(n)->ref)
#define val(n)		(&(n)->val)


#define REHASH_LIMIT	0.70	/* avoid more than this % full */


static Hash *listhead = NULL;

/* hash dimensions values */
static Word dimensions[] = 
 {3, 5, 7, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421,
  12853, 25717, 51437, 65521, 0};  /* 65521 == last prime < MAX_WORD */

루아 개발자들은 문자열 비교 함수에 독특한 집착이 있는 것같습니다. 문자열 비교 매크로를 또 만들어 놨네요. 정말 특이한 버릇입니다. 그 아래로 해시 테이블 멤버 변수에 접근하는 매크로를 정의했습니다. REHASH_LIMIT는 주석을 보니 70% 이상 동일 바스켓에 쌓이는 것을 방지하려고 한계값을 지정한 것으로 보입니다. dimensions은 솟수(prime number)를 몇 개 적어놨습니다. 점점 커지긴 하지만 바로 인접 솟수를 나열한 것은 아닙니다. 왜냐면 23 다음 솟수는 29거든요. (참고로 한글 맞춤법 규정에 의하면 prime number도 적을 때는 소수로 적는 것이 옳다고 합니다. 그런데 전 그렇게 적기 싫습니다. 책으로 내는 것도 아닌데 구분하기 쉬운 단어를 쓰렵니다.)

static Word redimension (Word nhash)
{
 Word i;
 for (i=0; dimensions[i]!=0; i++)
 {
  if (dimensions[i] > nhash)
   return dimensions[i];
 }
 lua_error("table overflow");
 return 0;  /* to avoid warnings */
}

아직은 어디에 쓰는지 알 수 없으니 함수 코드만 해석하겠습니다. dimensions 배열에 나열한 솟수에서 파라메터 nhash보다 큰 중 가장 작은 수를 리턴합니다. 예를 들어 nhash가 86이라면 97을 리턴합니다.

static Word hashindex (Hash *t, Object *ref)		/* hash function */
{
 switch (tag(ref))
 {
  case LUA_T_NIL:
   lua_reportbug ("unexpected type to index table");
   return -1;  /* UNREACHEABLE */
  case LUA_T_NUMBER:
   return (((Word)nvalue(ref))%nhash(t));
  case LUA_T_STRING:
  {
   unsigned long h = tsvalue(ref)->hash;
   if (h == 0)
   {
     char *name = svalue(ref);
     while (*name)
       h = ((h<<5)-h)^(unsigned char)*(name++);
     tsvalue(ref)->hash = h;
   }
   return (Word)h%nhash(t);  /* make it a valid index */
  }
  case LUA_T_FUNCTION:
   return (((IntPoint)bvalue(ref))%nhash(t));
  case LUA_T_CFUNCTION:
   return (((IntPoint)fvalue(ref))%nhash(t));
  case LUA_T_ARRAY:
   return (((IntPoint)avalue(ref))%nhash(t));
  default:  /* user data */
   return (((IntPoint)uvalue(ref))%nhash(t));
 }
}

주석에 기능이 한 문장으로 설명되 있습니다. 해시 함수죠. ref가 해시 테이블 키입니다. 해시 테이블은 키의 해시 값을 이용해서 값이 들어갈 바스켓을 결정하죠. ref가 number면 간단하게 나머지 연산해서 위치를 결정합니다. ref가 문자열이면 미리 계산해 놓은 해시 값을 사용합니다. 미리 계산한 해시 값이 없으면 계산합니다. 계산 공식은 딱히 중요하지 않습니다. 그냥 동일한 문자열에 대해 항상 같은 값만 나오면 됩니다. 그외 함수, C 함수, 배열, 사용자 데이터면 포인터 주소 값을 숫자로 간주해서 해시 테이블 크기로 나머지 연산합니다.

Bool lua_equalObj (Object *t1, Object *t2)
{
  if (tag(t1) != tag(t2)) return 0;
  switch (tag(t1))
  {
    case LUA_T_NIL: return 1;
    case LUA_T_NUMBER: return nvalue(t1) == nvalue(t2);
    case LUA_T_STRING: return streq(svalue(t1), svalue(t2));
    case LUA_T_ARRAY: return avalue(t1) == avalue(t2);
    case LUA_T_FUNCTION: return bvalue(t1) == bvalue(t2);
    case LUA_T_CFUNCTION: return fvalue(t1) == fvalue(t2);
    default: return uvalue(t1) == uvalue(t2);
  }
}

두 오브젝트 타입이 같음을 판단하는 함수입니다. 루아 명령어 EQOP를 처리할 때 직접 호출합니다. 그리고 해시 테이블에서 해시 키가 같음을 확인할 때 호출합니다.

static Word present (Hash *t, Object *ref)
{ 
 Word h = hashindex(t, ref);
 while (tag(ref(node(t, h))) != LUA_T_NIL)
 {
  if (lua_equalObj(ref, ref(node(t, h))))
    return h;
  h = (h+1) % nhash(t);
 }
 return h;
}

해시 테이블에서 키 ref에 해당하는 아이템 하나를 검색하는 함수입니다. 검색에 실패하면 그냥 계산해서 나온 해시 값 자체를 리턴합니다.

/*
** Alloc a vector node 
*/
static Node *hashnodecreate (Word nhash)
{
 Word i;
 Node *v = newvector (nhash, Node);
 for (i=0; i<nhash; i++)
   tag(ref(&v[i])) = LUA_T_NIL;
 return v;
}

해시 테이블의 노드 한 개 인스턴스에 메모리를 할당하는 함수입니다.

/*
** Create a new hash. Return the hash pointer or NULL on error.
*/
static Hash *hashcreate (Word nhash)
{
 Hash *t = new(Hash);
 nhash = redimension((Word)((float)nhash/REHASH_LIMIT));
 nodevector(t) = hashnodecreate(nhash);
 nhash(t) = nhash;
 nuse(t) = 0;
 markarray(t) = 0;
 return t;
}

해시 테이블 자체에 메모리 할당하는 함수입니다. 이 함수를 보니 앞에서 솟수를 만들어 놓고 어떻게 쓰는지 알겠습니다. 해시 테이블 크기를 솟수로 결정하는 건데 왜 꼭 솟수를 쓰는지는 아직도 모르겠습니다.

/*
** Delete a hash
*/
static void hashdelete (Hash *t)
{
 luaI_free (nodevector(t));
 luaI_free(t);
}

해시 테이블을 삭제하는 함수입니다. 메모리를 해제하는 것이지요.

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

가비지 컬렉션에서 메모리 객체에 mark를 표시하는 것은 여러 번 읽었습니다. 루아 테이블 타입 자료 구조에 대해서 그 마킹 동작을 하는 함수입니다.

static void call_fallbacks (void)
{
  Hash *curr_array;
  Object t;
  tag(&t) = LUA_T_ARRAY;
  for (curr_array = listhead; curr_array; curr_array = curr_array->next)
    if (markarray(curr_array) != 1)
    {
      avalue(&t) = curr_array;
      luaI_gcFB(&t);
    }
  tag(&t) = LUA_T_NIL;
  luaI_gcFB(&t);  /* end of list */
}

fallback이 나오는 부분은 전혀 이해를 못하겠습니다.

/*
** Garbage collection to arrays
** Delete all unmarked arrays.
*/
Long lua_hashcollector (void)
{
 Hash *curr_array = listhead, *prev = NULL;
 Long counter = 0;
 call_fallbacks();
 while (curr_array != NULL)
 {
  Hash *next = curr_array->next;
  if (markarray(curr_array) != 1)
  {
   if (prev == NULL) listhead = next;
   else              prev->next = next;
   hashdelete(curr_array);
   ++counter;
  }
  else
  {
   markarray(curr_array) = 0;
   prev = curr_array;
  }
  curr_array = next;
 }
 return counter;
}

모든 해시 테이블 인스턴스에 가비지 컬랙터를 돌립니다.

/*
** Create a new array
** This function inserts the new array in the array list. It also
** executes garbage collection if the number of arrays created
** exceed a pre-defined range.
*/
Hash *lua_createarray (Word nhash)
{
 Hash *array;
 lua_pack();
 array = hashcreate(nhash);
 array->next = listhead;
 listhead = array;
 return array;
}

루아 코드에서 루아 테이블 타입 변수를 하나 선언하면 CREATEARRAY 명령어를 수행합니다. CREATEARRAY 명령어를 처리할 때 이 함수를 호출합니다. 즉, 이 함수는 해시 테이블 하나를 새로 만듭니다. 이 해시 테이블이 루아 테이블 타입 변수인것이죠. 새로 만든 해시 테이블은 listhead 변수로 관리하는 링크드 리스트에 연결합니다.

/*
** Re-hash
*/
static void rehash (Hash *t)
{
 Word i;
 Word   nold = nhash(t);
 Node *vold = nodevector(t);
 nhash(t) = redimension(nhash(t));
 nodevector(t) = hashnodecreate(nhash(t));
 for (i=0; i<nold; i++)
 {
  Node *n = vold+i;
  if (tag(ref(n)) != LUA_T_NIL && tag(val(n)) != LUA_T_NIL)
   *node(t, present(t, ref(n))) = *n;  /* copy old node to new hahs */
 }
 luaI_free(vold);
}

해시 테이블 크기를 바꾸는 동작을 하는 함수로 보입니다. 새로운 해시 테이블 노드에 메모리를 할당하고 기존 해시 테이블 노드 값을 새 노드에 복사합니다. 그리고 남는 노드는 nil로 초기화합니다. 복사가 다 끝나면 기존 해시 테이블 노드는 메모리 해제합니다.

/*
** If the hash node is present, return its pointer, otherwise return
** null.
*/
Object *lua_hashget (Hash *t, Object *ref)
{
 Word h = present(t, ref);
 if (tag(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h));
 else return NULL;
}

앞서 읽었던 present() 함수를 호출해서 해시 테이블에서 키로 아이템을 검색하여 값을 리턴하는 함수입니다. 키에 해당하는 아이템이 없으면 null을 리턴합니다.

/*
** If the hash node is present, return its pointer, otherwise create a new
** node for the given reference and also return its pointer.
*/
Object *lua_hashdefine (Hash *t, Object *ref)
{
 Word   h;
 Node *n;
 h = present(t, ref);
 n = node(t, h);
 if (tag(ref(n)) == LUA_T_NIL)
 {
  nuse(t)++;
  if ((float)nuse(t) > (float)nhash(t)*REHASH_LIMIT)
  {
   rehash(t);
   h = present(t, ref);
   n = node(t, h);
  }
  *ref(n) = *ref;
  tag(val(n)) = LUA_T_NIL;
 }
 return (val(n));
}

해시 테이블에서 키로 아이템을 검색하고 있으면 리턴, 없으면 해시 테이블에 추가합니다.

댓글남기기