[루아2.4] tree

2 분 소요

tree.c

루아 2.2와 비교해서 루아 2.4의 tree.c 파일은 거의 다시 작성한 수준으로 많이 바꿨습니다. 그래서 루아 2.2 코드와 일대일로 비교하는 것이 의미가 없어보입니다. 그래서 tree.c는 그냥 코드 전체를 읽겠습니다.

#define NUM_HASHS  64

typedef struct {
  int size;
  int nuse;  /* number of elements (including EMPTYs) */
  TaggedString **hash;
} stringtable;

static int initialized = 0;

static stringtable string_root[NUM_HASHS];

static TaggedString EMPTY = {NOT_USED, NOT_USED, 0, 2, {0}};

전역 변수 선언 부분입니다. string_root 배열 갯수를 64개로 했는데 부족한 것 아닌가하는 생각이 듭니다.

static unsigned long hash (char *str)
{
  unsigned long h = 0;
  while (*str)
    h = ((h<<5)-h)^(unsigned char)*(str++);
  return h;
}

해시 함수 계산하는 함수입니다. 공식은 중요치 않습니다. 적당히 잘 퍼지는 값이 나오면 됩니다.

static void initialize (void)
{
  initialized = 1;
  luaI_addReserved();
  luaI_initsymbol();
  luaI_initconstant();
}

static void grow (stringtable *tb)
{
  int newsize = luaI_redimension(tb->size);
  TaggedString **newhash = newvector(newsize, TaggedString *);
  int i;
  for (i=0; i<newsize; i++)
    newhash[i] = NULL;
  /* rehash */
  tb->nuse = 0;
  for (i=0; i<tb->size; i++)
    if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY)
    {
      int h = tb->hash[i]->hash%newsize;
      while (newhash[h])
        h = (h+1)%newsize;
      newhash[h] = tb->hash[i];
      tb->nuse++;
    }
  luaI_free(tb->hash); 
  tb->size = newsize;
  tb->hash = newhash;
}

static TaggedString *insert (char *str, stringtable *tb)
{
  TaggedString *ts;
  unsigned long h = hash(str);
  int i;
  int j = -1;
  if ((Long)tb->nuse*3 >= (Long)tb->size*2)
  {
    if (!initialized)
      initialize();
    grow(tb);
  }
  i = h%tb->size;
  while (tb->hash[i])
  {
    if (tb->hash[i] == &EMPTY)
      j = i;
    else if (strcmp(str, tb->hash[i]->str) == 0)
      return tb->hash[i];
    i = (i+1)%tb->size;
  }
  /* not found */
  lua_pack();
  if (j != -1)  /* is there an EMPTY space? */
    i = j;
  else
    tb->nuse++;
  ts = tb->hash[i] = (TaggedString *)luaI_malloc(sizeof(TaggedString)+strlen(str));
  strcpy(ts->str, str);
  ts->marked = 0;
  ts->hash = h;
  ts->varindex = ts->constindex = NOT_USED;
  return ts;
}

TaggedString *lua_createstring (char *str) 
{
  return insert(str, &string_root[(unsigned)str[0]%NUM_HASHS]);
}

배열에 노드를 추가하는 함수에 연결된 grow() 함수와 initialize() 함수가 있습니다. 쉽게 말해서, 배열에 노드를 추가하려고 할 때 배열이 초기화가 안된 상태라면 initialize() 함수를 호출하고 배열 크기가 모자라면 grow() 함수를 호출하는 것입니다. 코드를 읽어보죠. 현재 사용중인 배열의 노드 갯수에 3을 곱한 값이 배열 사이즈의 두배보다 크면 배열를 늘리거나 초기화합니다. 즉, 배열이 부족하다는 조건을 저렇게 정한 것인데, 왜 저런 숫자를 골랐는지 의문입니다. 초기화 여부도 굳이 initialized 전역 변수를 쓸 필요가 있을까하는 생각이 듭니다. 그냥 변수를 null로 초기화한다음 null 여부를 체크하는 것으로 충분할텐데요.

아무튼 크기 검사를 하고 나면 일치하는 노드가 있는지 찾습니다. 계산한 해시를 배열 크기와 나머지 연산한 결과를 사용합니다. 배열 크기를 넘어가면 안되니까요. 그런데 파일 이름은 트리인데 코드는 트리를 구현하는 것이 아니라 그냥 해시 테이블이네요.

일치하는 노드가 없으면 가비지 컬랙션을 수행하고 배열에 노드를 새로 추가합니다.

댓글남기기