[Example] 이진 검색 트리를 이용한 파일 정렬

#include <windows.h>
#include <tchar.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <malloc.h>
#include <io.h>
#include <process.h>

#define KEY_SIZE 8

#define EMPTY _T ("")
#define YES _T ("y")
#define NO _T("n")
#define CR 0x0D
#define LF 0x0A
#define TSIZE sizeof (TCHAR)

#ifdef _UNICODE 
#define _tstrrchr wcsrchr
#else
#define _tstrrchr strrchr
#endif

#ifdef _UNICODE 
#define _tstrstr wcsstr
#else
#define _tstrstr strstr
#endif

#ifdef _UNICODE 
#define _memtchr wmemchr
#else
#define _memtchr memchr
#endif

#define GetExceptionCode            _exception_code
#define exception_code              _exception_code
#define GetExceptionInformation     (struct _EXCEPTION_POINTERS *)_exception_info
#define exception_info              (struct _EXCEPTION_POINTERS *)_exception_info
#define AbnormalTermination         _abnormal_termination
#define abnormal_termination        _abnormal_termination

unsigned long __cdecl _exception_code(void);
void *        __cdecl _exception_info(void);
int           __cdecl _abnormal_termination(void);

typedef struct _TREENODE
{
 struct _TREENODE *Left, *Right;
 TCHAR key[KEY_SIZE];
 LPTSTR pData;

} TREENODE, *LPTNODE, **LPPTNODE;

#define NODE_SIZE sizeof( TREENODE )
#define NODE_HEAP_ISIZE 0x8000
#define DATA_HEAP_ISIZE 0x8000
#define MAX_DATA_LEN 0x1000
#define TKEY_SIZE KEY_SIZE * sizeof( TCHAR )
#define STATUS_FILE_ERROR 0xE0000001

VOID ReportError (LPCTSTR userMessage, DWORD exitCode, BOOL printErrorMessage);
VOID ReportException (LPCTSTR userMessage, DWORD exceptionCode);
DWORD Options (int argc, LPCTSTR argv [], LPCTSTR OptStr, ...);

LPTNODE FillTree( HANDLE, HANDLE, HANDLE);
BOOL Scan( LPTNODE );
int KeyCompare(LPCTSTR, LPCTSTR);
BOOL InsertTree( LPPTNODE, LPTNODE );

int _tmain(int argc, LPTSTR argv[])
{
 HANDLE hIn = INVALID_HANDLE_VALUE, hNode = NULL, hData = NULL;
 LPTNODE pRoot;
 BOOL noPrint;
 CHAR errorMessage[0x100] = {0x0, };
 
 int iFirstFile = Options( argc, argv, _T("n"), &noPrint, NULL);
 int iFile = 0;

 for( iFile = iFirstFile; iFile < argc; iFile ++ )
 {
  __try
  {
   hIn = CreateFile( argv[iFile], GENERIC_READ, 0, NULL, OPEN_EXISTING, 0, NULL);

   if( hIn == INVALID_HANDLE_VALUE )
   {
    RaiseException( STATUS_FILE_ERROR, 0, 0, NULL );
   }

   __try
   {
    hNode = HeapCreate( HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE, NODE_HEAP_ISIZE, 0);
    hData = HeapCreate( HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE, DATA_HEAP_ISIZE, 0);

    pRoot = FillTree(hIn, hNode, hData);

    _tprintf(_T("Sorted file : %s \n"), argv[iFile]);

    Scan( pRoot );

   }
   __finally
   {
    if( hNode != NULL )
    {
     HeapDestroy( hNode );
    }

    if( hNode != NULL )
    {
     HeapDestroy( hData );
    }

    hNode = NULL;
    hData = NULL;

    if( hIn != INVALID_HANDLE_VALUE )
     CloseHandle(hIn);

    hIn = INVALID_HANDLE_VALUE;
    
   }

  }
  __except( (GetExceptionCode() == STATUS_FILE_ERROR || GetExceptionCode() == STATUS_NO_MEMORY) ? EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH )
  {
   _stprintf( errorMessage, _T("\n %s %s "), _T("sortBT error onfile : "), argv[iFile]);
   ReportError( errorMessage, 0, TRUE );
  }
 }


 return 0;
}

LPTNODE FillTree (HANDLE hIn, HANDLE hNode, HANDLE hData)
{
 LPTNODE pRoot = NULL, pNode;
 DWORD nRead, i;
 BOOL atCR;
 TCHAR dataHold[MAX_DATA_LEN];
 LPTSTR pString;
     
 while (TRUE) {
  pNode = HeapAlloc (hNode, HEAP_ZERO_MEMORY, NODE_SIZE);
  pNode->pData = NULL;
  (pNode->Left) = pNode->Right = NULL;

  if (!ReadFile (hIn, pNode->key, TKEY_SIZE,
    &nRead, NULL) || nRead != TKEY_SIZE)
  
   return pRoot; 
  atCR = FALSE;   

  for (i = 0; i < MAX_DATA_LEN; i++) {
   ReadFile (hIn, &dataHold[i], TSIZE, &nRead, NULL);
   if (atCR && dataHold[i] == LF) break;
   atCR = (dataHold[i] == CR);
  }
  dataHold[i - 1] = _T('\0');


  pString = HeapAlloc (hData, HEAP_ZERO_MEMORY,
    (SIZE_T)(KEY_SIZE + _tcslen (dataHold) + 1) * TSIZE);
  memcpy (pString, pNode->key, TKEY_SIZE);
  pString[KEY_SIZE] = _T('\0');
  _tcscat (pString, dataHold);
  pNode->pData = pString;

  InsertTree (&pRoot, pNode);

 } 
 return NULL;
}

BOOL InsertTree (LPPTNODE ppRoot, LPTNODE pNode)
{
 if (*ppRoot == NULL) {
  *ppRoot = pNode;
  return TRUE;
 }
 if (KeyCompare (pNode->key, (*ppRoot)->key) < 0)
  InsertTree (&((*ppRoot)->Left), pNode);
 else
  InsertTree (&((*ppRoot)->Right), pNode);
 return TRUE;
}

int KeyCompare (LPCTSTR pKey1, LPCTSTR pKey2)
{
 return _tcsncmp (pKey1, pKey2, KEY_SIZE);
}

static BOOL Scan (LPTNODE pNode)
{
 if (pNode == NULL)
  return TRUE;
 Scan (pNode->Left);
 _tprintf (_T ("%s\n"), pNode->pData);
 Scan (pNode->Right);
 return TRUE;
}


DWORD Options (int argc, LPCTSTR argv [], LPCTSTR OptStr, ...)
{
 va_list pFlagList;
 LPBOOL pFlag;
 int iFlag = 0, iArg;

 va_start (pFlagList, OptStr);

 while ((pFlag = va_arg (pFlagList, LPBOOL)) != NULL
    && iFlag < (int)_tcslen (OptStr)) {
  *pFlag = FALSE;
  for (iArg = 1; !(*pFlag) && iArg < argc && argv [iArg] [0] == _T('-'); iArg++)
   *pFlag = _memtchr (argv [iArg], OptStr [iFlag],
     _tcslen (argv [iArg])) != NULL;
  iFlag++;
 }

 va_end (pFlagList);

 for (iArg = 1; iArg < argc && argv [iArg] [0] == _T('-'); iArg++);

 return iArg;
}

VOID ReportException (LPCTSTR userMessage, DWORD exceptionCode)
{ 
 if (lstrlen (userMessage) > 0)
  ReportError (userMessage, 0, TRUE);

 if (exceptionCode != 0) 
  RaiseException (
   (0x0FFFFFFF & exceptionCode) | 0xE0000000, 0, 0, NULL);
 
 return;
}

VOID ReportError (LPCTSTR userMessage, DWORD exitCode, BOOL printErrorMessage)
{
 DWORD eMsgLen, errNum = GetLastError ();
 LPTSTR lpvSysMsg;
 _ftprintf (stderr, _T("%s\n"), userMessage);
 if (printErrorMessage) {
  eMsgLen = FormatMessage (FORMAT_MESSAGE_ALLOCATE_BUFFER | FORMAT_MESSAGE_FROM_SYSTEM,
    NULL, errNum, MAKELANGID (LANG_NEUTRAL, SUBLANG_DEFAULT),
    (LPTSTR) &lpvSysMsg, 0, NULL);
  if (eMsgLen > 0)
  {
   _ftprintf (stderr, _T("%s\n"), lpvSysMsg);
  }
  else
  {
   _ftprintf (stderr, _T("Last Error Number; %d.\n"), errNum);
  }

  if (lpvSysMsg != NULL) LocalFree (lpvSysMsg); 
 }

 if (exitCode > 0)
  ExitProcess (exitCode);

 return;
}

​

출처 : Windows 시스템 프로그래밍 윈도우즈 API 핵심 바이블​