6.6 테이블 조사(Table Lookup)

이 절에서는 구조체를 좀 더 설명하기 위해 테이블 조사 패키지의 내부에 대해서 설명하겠다 이 프로그램은 마이크로프로세서나 컴파일러의 심벌 관리 루틴에서 볼수있는 전형적인 것이다. 예를 들어,C의 #define  문을 보면 다음과 같은 라인을 만났을때 

#define IN 1

IN 이라는 이름과 대치 값 1은 테이블에 저장된다. 그 후 다시 IN이 다음과 같이 문장 중에 나타나면 IN은 1로 대치된다.

state = IN;

이름과 대치값을 다루는 것은 두개의 함수에 의해 이루어진다.

install(s,t)는 s라는 이름과 대치 를 테이블에 기억하는데 이때 s와 t는 문자열이다. lookup(s)는 테이블에서 s를 찾아서 그것이 발견된 장소에 대한 포인터를 리턴시키고 s가 없으면 null을 리턴시킨다.

이 알고리즘을 hash search라고 하는데 들어오는 이름은 어떤 작은양의 정수(hash)로 바뀌어서 이것이 포인터의 배열에 대한 지표로 사용된다.(단어가 순서대로 정렬되는 것이 아니다). 각 배열의 원소는 해시값을 갖는 이름의 블록이 시작되는 곳을 가리킨다. 만약에 그 해시값을 갖는 이름이 없으면 NULL이 된다하나의 블록은 이름을 가리키느 포인터 대체할 문장을 가리키는 포인터 그리고 다음 블록의 위치를 가리키는 포인터가 들어있는 구조체이다. 다음블록에 대한 포인터가 null이면 그 체인의 끝을 나타내게 된다.

struct nlist {    /* table entry: */

    struct nlist; /* next entry: */

    char *name;   /* defined name */

    char *defn;   /* replacement text */

};

포인터의 배열은 다음과 같다.

#define HASHSIZE 101

static struct nlist *hashtab[HASHSIZE]; /* pointer table */

lookup와 install에서 모두 쓰이는 해시함수느 이전에 모인 문자열 내의 문자값을 어떤 규칙을 더해서 그값을 배열크기로 나눈 나머지를 취한다. 이것이 가장 좋은 알고리즘은 아니지만 매우 단순하기 때문에 많이 쓰인다.

/* hash: form hash value for string s */

unsigned hash(char *s)

{

    unsigned hashval;

    

    for (hashval = 0; *s != '\0'; s++)

        hashval = *s + 31 * hashval;

    return hashval % HASHSIZE;

}

unsigned arithmetic은 해시 값이 음수가 아님을 보증한다.

해시 과정은 배열 hashtab에서 초기 지표를 정하고 문자열이 발견되면 그 문자열의 hash값을 계산하고 hash번째 요소로 그 문자열이 들어간다 탐색은 lookup에 의해 수행된다. lookup이 그 요소를 찾으면 그에대한 포인터를 리턴하고 찾지 못하면 NULL을 리턴한다.

/* lookup: look for s in hashtab */

struct nlist *lookup(char *s)

{

    struct nlist *np;

    for (np = hashtab[hash(s)]; np != NULL; np = np->next)

        if (strcmp(s, np->name) == 0)

        return np; /* found */

    return NULL; /* not found */

}

lookup에서 for 루프는 리스트를 따라가면서 검색하는 방법인데,표준적인 방법이다.

  for (ptr = head; prt != NULL; prt = ptr -> next) 

        ...

install은 이름이 이미 표안에 있는지를 판정할때 lookup을 사용한다. 만약 나타나 있으면 새로운 정의가 이미 있던것을 대신하게 되고, 만약 그렇지 않으면 새로운 엔트리가 만들어 지는 것이다. 어떤 이유에서든 새로운 엔트리를 위한 자리가 없으면 install은 NULL을 리턴하게 된다.

    

struct nlist *lookup(char *);

char *strdup(char *);

/* install: put (name, defn) in hashtab */

struct nlist *install(char *name, char *defn)

{

    struct nlist *np;

    unsigned hashval;

    

    if ((np = lookup(name)) == NULL) { /* not found */

        np = (struct nlist *) malloc(sizeof(*np));

        if (np == NULL || (np->name = strdup(name)) == NULL)

            return NULL;

        hashval = hash(name);

        np->next = hashtab[hashval];

        hashtab[hashval] = np;

    } else /* already there */

        free((void *) np->defn); /*free previous defn */

    if ((np->defn = strdup(defn)) == NULL)

        return NULL;

    return np;

}

예제 6-5 lookup과 install에 의해 유지되는 테이블에서 어떤 이름과 정의를 없애는 루틴인 undef라는 함수를 작성하라.

예제 6-6 이 장의 루틴을 변형하여 C프로그램을 사용하기에 적당한 인자가 없은 #define 프로세서를 간단하게 구현하라. getch와 ungetch를 참조하면 도움이 될 것이다.