1 // File: Template/TSmartArray.h
   2 
   3 // TSmartArray.h : TSmartArray 템플릿 선언
   4 //
   5 
   6 #pragma once
   7 
   8 //------------------------------------------------------------------------------
   9 // TSmartArray 템플릿 설명
  10 //
  11 // [구현 목적]
  12 //      1. 빈 공간을 자동 할당
  13 //      2. 할당된 공간을 이중 링크드로 관리
  14 //      3. 배열처럼 첨자(인덱스)를 통하여 데이터 접근
  15 //      4. 정적 배열 구조
  16 //
  17 // [내부 구조]
  18 //      1. 빈 공간(인덱스)를 관리하는 큐(Queue)
  19 //      2. 인덱스(배열 첨자)로 즉시 접근할 수 있는 이중 링크드 리스트 구조의
  20 //         배열
  21 //
  22 // [장점]
  23 //      1. 빈 공간을 자동 할당 (자동 인덱스(첨자) 관리)
  24 //      2. 할당된 공간만 순환 처리 가능
  25 //
  26 // [단점]
  27 //      1. 추가 메모리 할당 (인덱스 관리, 이중 링크드 리스트)
  28 //
  29 // [사용법]
  30 //      1. 삽입: 인덱스 = Insert( 데이터 포인터 );
  31 //      2. 삭제: 데이터 포인터 = Erase( 인덱스 );
  32 //      3. 검색: 데이터 포인터 = Find( 인덱스 );
  33 //      4. 순환처리: for( INT16 i=Head(); Tail()!=i; i=Next( i ) )
  34 //
  35 //------------------------------------------------------------------------------
  36 
  37 // 상수 선언
  38 const INT16 INVALID_ARRAY_INDEX     = -1;
  39 
  40 
  41 // 템플릿 선언
  42 template< typename _Type, int ARRAY_MAX >
  43 class TSmartArray
  44 {
  45     // 내부 데이터형
  46 protected:
  47     struct _NODE
  48     {
  49         _Type * data;
  50         INT16   prev;
  51         INT16   next;
  52     };
  53 
  54     //--------------------------------------------------------------------------
  55     // 생성자/소멸자
  56 public:
  57     TSmartArray()
  58     {
  59         clear();
  60     }
  61 
  62     ~TSmartArray()  {}
  63 
  64     //--------------------------------------------------------------------------
  65     // 멤버 함수 (Map)
  66 public:
  67     INT16 insert( _Type * data )
  68     {
  69         INT16 idx = _pop();
  70 
  71         if( INVALID_ARRAY_INDEX != idx )
  72         {
  73             INT16 & tail = m_map[ 0 ].prev;
  74 
  75             m_map[ idx ].data   = data;
  76             m_map[ idx ].prev   = tail;
  77             m_map[ idx ].next   = m_map[ tail ].next;
  78 
  79             m_map[ tail ].next  = idx;
  80 
  81             tail = idx;
  82 
  83             ++m_size;
  84         }
  85 
  86         return idx;
  87     }
  88 
  89     _Type * erase( INT16 idx )
  90     {
  91         if( ( idx < 1 ) || ( idx > ARRAY_MAX ) )
  92         {
  93             return NULL;
  94         }
  95 
  96         _Type * data = m_map[ idx ].data;
  97 
  98         if( data )
  99         {
 100             INT16 & prev = m_map[ idx ].prev;
 101             INT16 & next = m_map[ idx ].next;
 102 
 103             m_map[ prev ].next  = next;
 104             m_map[ next ].prev  = prev;
 105 
 106             memset( &m_map[ idx ], 0, sizeof( _NODE ) );
 107 
 108             _push( idx );
 109 
 110             --m_size;
 111         }
 112 
 113         return data;
 114     }
 115 
 116     _Type * find( INT16 idx )
 117     {
 118         if( ( idx < 1 ) || ( idx > ARRAY_MAX ) )
 119         {
 120             return NULL;
 121         }
 122 
 123         return m_map[ idx ].data;
 124     }
 125 
 126     void clear()
 127     {
 128         m_size  = 0;
 129         m_front = 0;
 130         m_rear  = ARRAY_MAX;
 131 
 132         for( INT16 i=0; m_rear>i; ++i )
 133         {
 134             m_queue[ i ] = i + 1;
 135         }
 136 
 137         m_queue[ m_rear ] = INVALID_ARRAY_INDEX;
 138 
 139         //----------------------------------------------------------------------
 140 
 141         memset( m_map, 0, sizeof( m_map ) );
 142     }
 143 
 144     INT16   head()              { return m_map[ 0 ].next; }
 145     INT16   tail()              { return 0; }
 146     INT16   next( INT16 idx )   { return m_map[ idx ].next; }
 147 
 148     INT16   size()              { return m_size; }
 149 
 150     // 멤버 함수 (Queue)
 151 protected:
 152     void _push( INT16 data )
 153     {
 154         _ASSERT( INVALID_ARRAY_INDEX == m_queue[ m_rear ] );
 155 
 156         m_queue[ m_rear ] = data;
 157         m_rear = ( m_rear + 1 ) % ( ARRAY_MAX + 1 );
 158     }
 159 
 160     INT16 _pop()
 161     {
 162         _ASSERT( INVALID_ARRAY_INDEX != m_queue[ m_front ] );
 163 
 164         INT16 data = m_queue[ m_front ];
 165         m_queue[ m_front ] = INVALID_ARRAY_INDEX;
 166         m_front = ( m_front + 1 ) % ( ARRAY_MAX + 1 );
 167         return data;
 168     }
 169 
 170     //--------------------------------------------------------------------------
 171     // 멤버 변수 (Map)
 172 protected:
 173     _NODE m_map[ ARRAY_MAX + 1 ];
 174     INT16 m_size;
 175 
 176     // 멤버 변수 (Queue)
 177 protected:
 178     INT16 m_front;
 179     INT16 m_rear;
 180 
 181     INT16 m_queue[ ARRAY_MAX + 1 ];
 182 
 183 }; // class TSmartArray
 184 
 185 
 186 // 매크로 선언 (순환 처리를 위한 매크로)
 187 #define FOREACH_SMART_ARRAY(i,c)                for(INT16 i=(c).head();(c).tail()!=i;i=(c).next(i))

   1 // 데이터형 선언 (클래스)
   2 class CDATA
   3 {
   4         ...
   5 };
   6 
   7 int main()
   8 {
   9         // 탬플릿 선언
  10         TSmartArray< CDATA, 100 > _array;
  11 
  12         CDATA * pData = new CDATA;
  13 
  14         // 데이터 삽입 (인덱스 반환)
  15         INT16 nIndex = _array.insert( pData );
  16 
  17         // 데이터 검색 (데이터 포인터 반환)
  18         pData = _array.find( nIndex );
  19 
  20         // 데이터 삭제 (데이터 포인터 반환)
  21         pData = _array.erase( nIndex );
  22 
  23         // 순환 처리
  24         FOREACH_SMART_ARRAY( i, _array )
  25         {
  26                 ...
  27         }
  28 
  29         // 초기화
  30         _array.clear();
  31 }