연결리스트 검토 부탁드립니다.

이상하게 자꾸 노드가 엉키는것 같습니다. 연결리스트 구성할때는 값을 찍어봐도 아무 문제가 없어보이는데, 막상 참조하려고 하면 엉뚱한 주소를 가르키고 죽어버립니다.

우선 자료구조입니다.

struct _VersionNode {
        char *filename;
        unsigned char major;
        unsigned char minor;
        unsigned char patchlevel;

        struct _VersionNode *next, *prev;
};

struct _VersionList {
        struct _VersionNode *head, *tail;
        int count;
};

struct _VersionList *BeginVersionList( const char *filename );
struct _VersionNode *CreateVersionNode( struct _VersionList *VersionList );
void DeleteVersionNode( struct _VersionList *VersionList, struct _VersionNode *VersionNode );

이름만 봐도 어떤 목적으로 만들었는지 감이 오실겁니다.
BeginVersionList() 함수는 연결리스트를 생성하는 함수입니다. 주어진 파일명에서 데이터를 읽어서 리스트를 구성합니다.
CreateVersionNode() 함수는 리스트에 새로운 노드를 추가하는 함수입니다. 노드의 메모리를 할당받아서 링크를 구성해주고, 필드를 체워 넣는것은 함수의 밖에서 하도록 하고 있습니다.
DeleteVersionNode() 함수는 리스트 안에서 특정 노드의 링크를 끊고 메모리를 해제하는 함수입니다.
EndVersionList() 함수가 있어야 할것 같지만.. 프로그램 종료할때 커널에서 관리해주므로 직접 구현하지는 않았습니다.

다음은 BeginVersionList() 함수의 구현입니다.

struct _VersionList *BeginVersionList( const char *filename )
{
        FILE *fp = NULL;
        char TempString[512] = { 0, };
        struct _VersionList *VersionList = NULL;
        struct _VersionNode *VersionNode = NULL;

        VersionList = (struct _VersionList *)malloc( sizeof(struct _VersionList) );
        VersionList->count = 0;

        VersionList->head = (struct _VersionNode *)malloc( sizeof(struct _VersionNode) );
        VersionList->tail = (struct _VersionNode *)malloc( sizeof(struct _VersionNode) );
        memset( VersionList->head, 0, sizeof(struct _VersionNode) );
        memset( VersionList->tail, 0, sizeof(struct _VersionNode) );
        VersionList->head->next = VersionList->tail->next = VersionList->tail;
        VersionList->head->prev = VersionList->tail->prev = VersionList->head;
        // 여기까지 리스트를 초기화 하는 부분

        fp = fopen( filename, "r" );
        if( fp == NULL )
                return VersionList;
        while( fgets( TempString, 512, fp ) != NULL )
        {
                if( strlen( TempString ) < 6 )
                        continue;
                VersionNode = CreateVersionNode( VersionList );
                VersionNode->filename = (char *)malloc( (strstr( TempString, " " ) - TempString) + 1 );
                if( sscanf( TempString, "%s %d %d %d", VersionNode->filename, &(VersionNode->major), &(VersionNode->minor), &(VersionNode->patchlevel) ) != 4 )
                {
                        DeleteVersionNode( VersionList, VersionNode );
                        continue;
                }
        }
        fclose( fp );
        // 여기까지, 파일을 열어서 특정 포맷대로 읽어 노드를 구성하는 부분

        printf( "List head %x, List tail %x\n", VersionList->head, VersionList->tail );
        // 디버깅용 찍어보기

        return VersionList;
}

보통 일반적인 연결리스트 생성하는 코드입니다. 데이터를 읽어오는 부분만 추가했습니다. 데이터의 포맷은 위에 sscanf() 함수에 명시한대로 %s %d %d %d 이며, 데이터 자체가 80바이트를 넘지는 않기때문에 TempString 변수에 정적으로 할당한 512 바이트가 부족하거나 하지는 않습니다.

다음은 CreateVersionNode() 함수의 구현입니다.

struct _VersionNode *CreateVersionNode( struct _VersionList *VersionList )
{
        struct _VersionNode *VersionNode = NULL;

        VersionNode = (struct _VersionNode *)malloc( sizeof(struct _VersionNode) );
        VersionNode->filename = NULL;
        VersionNode->major = VersionNode->minor = VersionNode->patchlevel = 0;
        // 새 노드를 위한 메모리를 할당하고, 값을 체운 뒤

        VersionNode->next = VersionList->tail;
        VersionNode->prev = VersionList->tail->prev;
        VersionNode->next->prev = VersionNode->prev->next = VersionNode;
        // 리스트에 삽입한다. 새로운 노드는 리스트의 맨 끝(tail 의 바로 앞)에 위치한다.

        printf( "New node %x, prev %x, next %x\n", VersionNode, VersionNode->prev, VersionNode->next );
        // 디버깅용 찍어보기

        VersionList->count += 1;
        return VersionNode;
}

여기가 의심스럽습니다. 우선 노드를 위한 메모리를 할당하고, 링크를 구성한 뒤에, 할당된 메모리를 리턴해서, 호출측에서 리턴값을 사용해 필드의 값을 체워넣도록 하고 있습니다. 위에 BeginVersionList() 함수에서 보면 CreateVersionNode() 를 호출한 뒤에 리턴된 값으로 데이터를 체워넣고 있는것을 알 수 있습니다. 제 딴에는 코딩의 편의를 위해 이런식의 방법을 택했는데.. 일단 찍어보기에서 나온 결과로는 문제가 없는것 같습니다.

다음은 DeleteVersionNode() 함수의 구현입니다.

void DeleteVersionNode( struct _VersionList *VersionList, struct _VersionNode *VersionNode )
{
        VersionNode->next->prev = VersionNode->prev;
        VersionNode->prev->next = VersionNode->next;
        VersionList->count -= 1;

        if( VersionNode->filename != NULL )
                free( VersionNode->filename );
        free( VersionNode );

        return;
}

노드의 링크를 끊고, 메모리를 해제하는 일을 합니다.

이 연결리스트 로직을 테스트하기 위해 main() 함수를 작성했습니다.

int main( void )
{
        struct _VersionList *VersionList = NULL;
        struct _VersionNode *VersionNode = NULL;

        VersionList = BeginVersionList( "version.info" );
        // version.info 파일의 내용을 데이터로 하는 리스트를 생성

        VersionNode = VersionList->head->next;
        // 첫번째 노드를 가르키게 한 뒤,
        while( VersionNode != VersionList->tail )
        {
                // 값을 출력
                printf( "노드 %x, prev %x, next %x\n", VersionNode, VersionNode->prev, VersionNode->next );
                printf( "파일이름 %s, 버젼 %d.%d.%d\n", VersionNode->filename, VersionNode->major, VersionNode->minor, VersionNode->patchlevel );
                
                // 값을 출력한 뒤에는, 다음 노드로 이동
                // 만약 다음노드가 tail 이면 루프를 탈출한다.
                VersionNode = VersionNode->next;
        }

        return 0;
}

테스트를 위해 사용한 데이터인 version.info 는 다음과 같은 텍스트 파일입니다.

hello.exe 1 2 3
world.dat 1 0 1

다음은 이 코드를 실행시킨 결과입니다.

New node 8049e60, prev 8049cc0, next 8049cd8
New node 8049e88, prev 8049e60, next 8049cd8
List head 8049cc0, List tail 8049cd8
노드 8049e60, prev 8049cc0, next 8049e88
파일이름 hello.exe, 버젼 1.2.3
노드 8049e88, prev 8049e60, next 8040000
파일이름 world.dat, 버젼 1.0.1
Segmentation fault

보시면.. 리스트의 head(8049cc0) 와 tail(8049cd8) 이 만들어지고, 노드 2개(8049e60, 8049e88) 가 정상적인 링크 구조를 가지고 만들어짐을 알 수 있습니다. 그리고 첫번째 노드 8049e60 과, 두번째 노드 8049e88 을 잘 참조해서 데이터를 출력하는데.. 문제는 두번째 노드 8049e88 의 next 가 생성될때와는 다르게 바뀌어있는것을 볼 수 있습니다. 생성될때는 8049cd8 로, 의도했던대로 리스트의 tail 을 제대로 가르키고 있는데, 참조할때는 전혀 엉뚱한 값인 8040000 이 튀어나옵니다.

어디서 버퍼를 침범했거나, 메모리를 부족하게 할당받았다거나 하는 부분은 안보이는것 같구요..

참 기본적인건데 왜 이러는지 잘 모르겠네요. 실행환경은 레드햇 7.3 발할라, gcc 2.96 입니다.