#9 [Lua 1.1] hash.h, hash.c 파일 읽기

hash.h

/*
** hash.h
** hash manager for lua
** Luiz Henrique de Figueiredo - 17 Aug 90
** $Id: hash.h,v 2.1 1994/04/20 22:07:57 celes Exp $
*/

#ifndef hash_h
#define hash_h
//Node와 Hash 자료 구조를 정의하면서 시작합니다. 
//Hash 자료 구조가 Node 자료 구조를 포함하고 있습니다.
//Node 구조체는 모양만 보면 전형적인 링크드 리스트입니다. Object 타입으로 ref와 val이 멤버입니다. 이름만 봐서는 reference와 value 일 것 같습니다. 
typedef struct node
{
 Object ref;
 Object val;
 struct node *next;
} Node;

/***아래 참조
Object는 아래와 같다.
typedef struct Object
{
 Type  tag;
 Value value;
} Object;

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는 아래와 같다.
각각 f는 루아의 CFunction, n은 Number, s는 문자열, b는 뭔지 모르겠고, a는 배열, u는 Userdata 값을 표시하려고 선언한 것으로 보입니다.
typedef union
{
 Cfunction 	 f;
 real    	 n;
 char      	*s;
 Byte      	*b;
 struct Hash    *a;
 void           *u;
} Value;
***********/

//테이블 타입을 구현한 어레이
typedef struct Hash
{
 char           mark;
 unsigned int   nhash;
 Node         **list;
} Hash;


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

 

 

hash.c

/*
** hash.c
** hash manager for lua
** Luiz Henrique de Figueiredo - 17 Aug 90
*/

char *rcs_hash="$Id: hash.c,v 2.1 1994/04/20 22:07:57 celes Exp $";

#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)

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



//Node 구조체와 Hash 구조체 맴버에 접근하기 편하게 만든 매크로.
#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))

#ifndef ARRAYBLOCK
#define ARRAYBLOCK 50
#endif


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

static ArrayList *listhead = NULL;


//head() 함수는 정적 함수입니다. 
//가장 단순한 형태의 해시 함수 입니다. 해시 테이가의 바스켓 위치를 받는 가장 간단한 방법이 그냥 해시 테이블 크기로 나머지를 구해서 쓰는 것입니다. 
//만약 레퍼런스 타입이 문자열일 때는 문자열을 정해진 규칙으로 숫자로 변환해서 나머지를 구해 값을 만듭니다. 규칙은 아무래도 상관없습니다. 같은 입력에 같은 출력이 나오기만 하면 됩니다. 그리고 해시 테이블 크기를 넘으면 안되고요.

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;
 }
}

//present() 정적 함수는 해시 테이블 t에서 h 해시값 바스켓의 ref 인덱스를 찾아서 리턴하는 함수
//쉽게 말해 검색 함수
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;
}

// 노드 리스트 n을 쭉 따라가면서 메모리를 모두 해제합니다.
static void freelist (Node *n)
{
 while (n)
 {
  Node *next = n->next;
  free (n);
  n = next;
 }
}

/*
** Create a new hash. Return the hash pointer or NULL on error.
*/

//해시 테이블에 바스켓 하나를 새로 생성하는 함수입니다. 
//nhash는 바스켓 하나에 최대한 연결하는 노드 링크드 리스트 개수입니다.
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*); //newvector() 매크로는 calloc() 함수를 호출하는 매크로입니다. 
										 //그래서 Hash 타입 인스턴스 하나를 만들고 list 맴버에 nhash 만큼 메모리를 확보해서 잡아줍니다.
 if (nodelist(t) == NULL)
 {
  lua_error ("not enough memory");
  return NULL;
 }
 return t;
}

/*
** Delete a hash
*/
//freelist() 함수를 안에서 호출합니다. 
//Hash 인스턴스가 가지고 있는 list 인스턴스를 따라가면서 메모리 해제를 해서 내부에 동적 할당한 메모리를 모두 해제하고 이어서 Hash 타입 인스턴스 자체에 메모리 할당을 해제합니다.
static void hashdelete (Hash *h)
{
 int i;
 for (i=0; i<nhash(h); i++)
  freelist (list(h,i));
 free (nodelist(h));
 free(h);
}


/*
** Mark a hash and check its elements 
*/
//Hash 구조체에 mark 맴버 변수가 0이면 값을 1로 바꿉니다. 
//그리고 노드 리스트를 따라가면서 Object 타입 인스턴스에 있는 Hash 타입 변수의 mark도 계속 따라가면서 모든 mark 맴버 변수 값을 다 1로 바꿉니다. 
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);
   }
  }
 } 
}
 
/*
** Garbage collection to arrays
** Delete all unmarked arrays.
*/
//Hash 구조체에 mark 맴버가 하는일이 뭔지 알것 같습니다. 가비지 컬랙션을 구현하는 수단이었습니다. 
//가비지 컬랙션은 쉽게 말해서 레퍼런스 카운트가 0이면 VM이 알아서 메모리를 해제하는 개념입니다. 
//루아는 레퍼런스 카운트라는 개념을 더 단순화해서 0과 1로만 처리하는지 lua_hashcollector() 함수 코드를 보면 1이 아닐 때 메모리 해제를 하고, 1일 때는 0으로 바꿉니다.
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;
 }
}


/*
** 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.
*/
//해시 테이블 자체인 ArrayList 구조체의 인스턴스를 생성하는 함수입니다. 

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;
}


/*
** 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.
*/
//현재 해쉬 노드면 현재 포인터를 넘긴다.
//해시 태이블 t와 인덱스 ref가 파라메터로 넘어오면 head() 함수를 호출해서 해시값을 구합니다.
//그러고나면 present() 함수를 호출해서 노드를 찾습니다. 만약 노드가 없으면 노드를 새로 생성합니다.
//노드를 새로 생성하면 노드의 값에는 nil을 기본값으로 넣습니다.
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);
}


/*
** 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.
*/
//firstnode() 정적 함수는 바로 이어서 나오는 lua_next() 함수에서 쓰려고 만든 정적 함수입니다.
//firstnode() 함수는 이름을 보면 해시 테이블 a에서 h 해시 함수 값 바스켓에 첫 번째 노드를 어떻게 하는 함수 같습니다.
//해시 테이블 list 멤버를 먼저 찾아서 리스트 노드가 NULL인지 검사합니다. 
//일단 루아 구현에서 메모리 할당이 되었는지 확인하는 것이지요. 
//메모리 할당이 되었다면 이제 루아 VM 수준에서 값이 nil인지 봅니다. 
//nil이 아닌 첫 번째 노드를 리턴합니다.
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();
}


//lua_next() 함수는 구현 코드의 패턴이 지금까지 읽었던 함수들하고 다릅니다.
//lua_getparam() 같은 함수는 루아를 임베딩 스크립트로 포함하고 있는 프로그램(루아에서는 호스트 프로그램이라고 부릅니다)에서 호출하는 루아 API입니다. 
//lua_next() 호출을 추적하면 Table.c에 tablebuffer라는 함수 포인터 테이블에 연결되있습니다.
//이 함수는 지금이 아니라 나중에 Table.c 파일에서 참조.
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");
  }
 }
}