반응형
728x90
반응형

 

다음과 같은 배열들을 순회할 것인데, 

1
2
3
4
int numArr[10] = { 9, 57, 3, 29, 23, };
std::vector<int> numVec(&numArr[0], &numArr[5]);
const char* strArr[3] = { "I'm Shyoo", "Dog", "Mouse" };
 
 cs

전통적인(?), 일반적인 순회 방법과 auto 자동 추론을 이용한 반복과 범위 기반 반복을 각각 실험해본다.

일반적인 순회

1
2
3
4
5
6
7
8
9
10
11
12
13
cout << "[기존 배열 순회 방법]" << endl;
 
for (int i = 0; i < 10; i++)
    cout << numArr[i] << ' ';
cout << endl;
 
for (std::vector<int>::iterator it = numVec.begin(); it != numVec.end(); it++)
    cout << *it << ' ';
cout << endl;
 
for(char ** p = (char **)strArr; p <= strArr+2; p++) // 억지로 계산하는게 꺼림칙하긴 하지만..
    cout << *p << ' ';
cout << endl;
 cs

일반적인 배열, 벡터, 포인터 배열을 순회하는 평범한 코드이다.

자료형 자동 추론을 통한 순회

1
2
3
4
5
6
7
8
9
10
11
12
13
cout << "[자료형 자동 추론]" << endl;
 
for (auto i = 0; i < 10; i++)
    cout << numArr[i] << ' ';
cout << endl;
 
for (auto it = numVec.begin(); it != numVec.end(); it++)
    cout << *it << ' ';
cout << endl;
 
for (auto p = (char**)strArr; p <= strArr + 2; p++)
    cout << *p << ' ';
cout << endl;
 cs

auto 키워드를 통해서 인덱스 역할을 하는 변수의 자료형을 알아서 탐지한다.. 너무 편하다 정말

범위 기반 반복 for을 통한 순회

1
2
3
4
5
6
7
8
9
10
11
12
13
cout << "[범위 기반 for문을 이용한 배열 순회]" << endl;
 
for (auto element : numArr)
    cout << element << ' ';
cout << endl;
 
for (auto it : numVec)
    cout << it << ' ';
cout << endl;
 
for(auto p : strArr)
    cout << p << ' ';
cout << endl;
 cs

다른 언어에서 지원하는 것처럼 c++도 지원한다. 자바스크립트나 파이썬의 for in과 같고, 자바의 for each 구조와 같다.

 

전체 코드 및 실행 결과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::cin;
 
int main(void)
{
    int numArr[10] = { 9, 57, 3, 29, 23, };
    std::vector<int> numVec(&numArr[0], &numArr[5]);
    const char* strArr[3] = { "I'm Shyoo", "Dog", "Mouse" };
 
    cout << "[기존 배열 순회 방법]" << endl;
    for (int i = 0; i < 10; i++)
        cout << numArr[i] << ' ';
    cout << endl;
 
    for (std::vector<int>::iterator it = numVec.begin(); it != numVec.end(); it++)
        cout << *it << ' ';
    cout << endl;
 
    for(char ** p = (char **)strArr; p <= strArr+2; p++) // 억지로 계산하는게 꺼림칙하긴 하지만..
        cout << *p << ' ';
    cout << endl;
 
 
    cout << "[자료형 자동 추론]" << endl;
    for (auto i = 0; i < 10; i++)
        cout << numArr[i] << ' ';
    cout << endl;
 
    for (auto it = numVec.begin(); it != numVec.end(); it++)
        cout << *it << ' ';
    cout << endl;
 
    for (auto p = (char**)strArr; p <= strArr + 2; p++)
        cout << *p << ' ';
    cout << endl;
 
    cout << "[범위 기반 for문을 이용한 배열 순회]" << endl;
 
    for (auto element : numArr)
        cout << element << ' ';
    cout << endl;
 
    for (auto it : numVec)
        cout << it << ' ';
    cout << endl;
 
    for(auto p : strArr)
        cout << p << ' ';
    cout << endl;
 
 
    return 0;
}
 cs

실행이 기가 막히게 잘되는 것을 볼 수 있다.

 

728x90
반응형
저작자표시

'프로그래밍응용 > Modern & STL' 카테고리의 다른 글

Lambda Expression  (0) 2021.01.27
R-Value, Copy Elision, 이동 생성자, RVO, NRVO  (0) 2021.01.26
Iterator 사용 방법 예시  (0) 2021.01.05
Priority Queue  (0) 2021.01.04
Queue  (0) 2021.01.04
728x90
반응형

리스트 기반 큐는 뭐 간단하다. 그냥 일반 큐인데 연결 리스트로 이루어진 큐이다.

기본 형태는 다음과 같다.

매우 간단하다. 그래서 행복하다 

기본적으로 배열 기반의 큐와 똑같이 동작한다. 그러나 배열 기반 큐와 다른 점은 크기가 정해져 있지 않고 동적이고 가변이기 때문에 뭐, 꽉 찬 것으로 보이지만 비어있네, 마네 뭐 이런 배열 기반 큐의 치명적인 단점을 생각할 필요가 없다.

Front 노드 포인터를 통해서 가장 먼저 들어온 노드를 가리키며, 삭제 연산을 진행할 때마다 Front 노드 포인터를 한 노드씩 옮긴다. 그리고 Rear 노드 포인터를 통해서 가장 마지막에 추가된 노드를 가리키며, 삽입 연산을 진행할 때마다, Rear 노드 포인터를 새로운 노드로 갱신한다. 

삽입 연산

 

삭제 연산

 

꽉참/비어짐 확인 연산

꽉 찼는지는 연결 리스트이므로 확인할 필요가 없으니, 비어져있는 상태만 확인하면 되는데 이 역시 매우 간단하다.

Front  노드  포인터가 NULL인지를 확인하면 된다.

메모리 관리

이번에는 연결 리스트 기반 스택으로 관리한다.

코드 및 실행 결과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include <stdio.h>
#include <stdlib.h>
 
#define STACK_LEN 10
 
#define TRUE 1
#define FALSE 0
 
// 공통 노드 정의
struct node
{
    int data;
    struct node* next;
};
 
// 스택으로 메모리 관리.
struct array_stack
{
    struct node* stack_array[STACK_LEN];
    int top_index;
};
typedef array_stack stack;
 
void StackInit(stack* s);
int SIsEmpty(stack* s);
int SIsFull(stack* s); // 증가시키고 대입이기 때문에 현 index에서 증가시키고 대입이 가능한지를 확인해야함.
void SPush(stack* s, struct node* data); // 증가시키고 대입.
struct node* SPop(stack* s);
struct node* SPeek(stack* s);
void ShowStack(stack* s);
 
struct node* CreateNodeAuto(stack* s);
void RemoveAllNodeAuto(stack* s);
 
// 리스트 기반 큐 자료구조(원형일 필요가 없음)
struct list_queue
{
    struct node* front;
    struct node* rear;
    int count;
};
typedef struct list_queue queue;
 
void QueueInit(queue* q);
int QisEmpty(queue* q);
struct node* Dequeue(queue* q);
void Enqueue(queue* q, stack* s, int data);
void ShowQueue(queue* q);
 
// Main
int main(void)
{
    stack s;
    queue q;
 
    QueueInit(&q);
    StackInit(&s);
 
    printf("큐/스택 생성 시작 --- \n");
 
    Enqueue(&q, &s, 1); ShowQueue(&q);
    Enqueue(&q, &s, 2); ShowQueue(&q);
    Enqueue(&q, &s, 3); ShowQueue(&q);
    Enqueue(&q, &s, 4); ShowQueue(&q);
    Enqueue(&q, &s, 5); ShowQueue(&q);
 
    printf("큐 제거 시작 --- \n");
 
    ShowQueue(&q);
    while (!QisEmpty(&q))
    {
        Dequeue(&q);
        ShowQueue(&q);
    }
    fputc('\n', stdout);
 
    printf("스택 제거 시작 --- \n");
    RemoveAllNodeAuto(&s);
    return 0;
}
 
 
// 메모리 관리 스택 관련 함수
 
void StackInit(stack* s)
{
    int i = 0;
    s->top_index = -1;
    for (i = 0; i < STACK_LEN; i++) // 순회를 위해서 모두 초기화
        s->stack_array[i] = NULL;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1)
        return TRUE;
    else
        return FALSE;
}
int SIsFull(stack* s) // 증가시키고 대입이기 때문에 현 index에서 증가시키고 대입이 가능한지를 확인해야함.
{
    if ((s->top_index) + 1 < STACK_LEN)
        return FALSE;
    else
        return TRUE;
}
void SPush(stack* s, struct node* data) // 증가시키고 대입임 (top_index가 -1부터 시작하기 때문에)
{
    if (SIsFull(s))
    {
        printf("스택이 가득찼습니다\n");
        return;
    }
    s->stack_array[++(s->top_index)] = data;
    return;
}
struct node* SPop(stack* s)
{
    struct node* rtarget = NULL;
    if (SIsEmpty(s))
    {
        printf("스택이 비어져있습니다\n");
        return NULL;
    }
    rtarget = s->stack_array[s->top_index];
    s->stack_array[s->top_index--] = NULL;
    return rtarget;
}
struct node* SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 비어져있습니다\n");
        return NULL;
    }
    return s->stack_array[s->top_index];
}
 
void ShowStack(stack* s)
{
    int i = 0;
    printf("{(top:%d)} : ", s->top_index);
    for (i = 0; i < STACK_LEN; i++)
        printf("[%p]", s->stack_array[i]), putc('-', stdout);
    putc('\n', stdout);
    return;
}
 
// 내가 정의하는 함수
 
struct node* CreateNodeAuto(stack* s)
{
    struct node* tmp = (struct node*)malloc(sizeof(struct node));
    // 초기화
    tmp->data = 0;
    tmp->next = NULL; // tmp->next = s->head;
    // 메모리 스택에 추가
    SPush(s, tmp);
 
    return tmp;
}
 
void RemoveAllNodeAuto(stack* s)
{
    struct node* rtarget = NULL;
    ShowStack(s);
    while (!SIsEmpty(s))
    {
        rtarget = SPop(s);
        free(rtarget);
        ShowStack(s);
    }
    return;
}
 
// 큐 자료구조 관련 함수
 
void QueueInit(queue* q)
{
    q->front = q->rear = NULL;
    q->count = 0;
    return;
}
int QisEmpty(queue* q)
{
    if (q->front == NULL)
        return TRUE;
    else
        return FALSE;
}
struct node* Dequeue(queue* q)
{
    struct node* target;
    // 기본 동작 - 비었는가 확인 -> 삭제 -> 인덱스 변경
    if (QisEmpty(q))
    {
        printf("Queue가 이미 비었습니다.\n");
        return NULL;
    }
    // target 추출
    target = q->front;
 
    // front를 맨 앞 노드의 다음 노드로 변경
    q->front = q->front->next;
 
    // 카운트 감소
    q->count--;
    return target;
}
void Enqueue(queue* q, stack* s, int data)
{
    // 노드 생성
    struct node* new_node = CreateNodeAuto(s); // 추가되는 노드가 항상 마지막이 된다.
    new_node->data = data;
    new_node->next = NULL;
 
    ShowStack(s);
 
    if (QisEmpty(q)) // 노드가 처음 추가하는 노드라면 front와 rear 모두 갱신
    {
        q->front = q->rear = new_node;
    }
    else // 노드가 처음 추가하는 노드가 아니라면 rear만 갱신
    {
        q->rear->next = new_node;
        q->rear = new_node;
    }
 
    // 카운트 증가
    q->count++;
    return;
}
 
void ShowQueue(queue* q)
{
    struct node* index = NULL;
    printf("{(r:%p/f:%p)} : ", q->rear, q->front);
    for (index = q->front; index != NULL; index = index->next)
        printf("[%p(%d)]", index, index->data), putc('-', stdout);
    putc('\n', stdout);
    return;
}
 
 
 
 
 
 
 
 cs

 

728x90
반응형
저작자표시

'프로그래밍응용 > C 자료구조' 카테고리의 다른 글

C Data Structure - 이진 탐색 트리 1  (0) 2021.01.23
C Data Structure - 덱(디큐?)  (0) 2021.01.22
C Data Structure - 원형 양방향 연결 리스트  (0) 2021.01.19
C Data Structure - 연결 리스트 기반 스택  (0) 2021.01.19
C Data Structure - 스택  (0) 2021.01.18
728x90
반응형

자 오늘도 학습했던 원형 양방향 연결 리스트를 정리할 때가 됐다. 이게 정리를 바로바로 안 하다보니 후, 코드를 다시 이해해야한다. 뭐 복습도 되고 참 좋다;;;

먼저 오늘 할 것은

원형 - 무한 순회가 가능한 -> 그래서 순회에 조건이 꼭 붙는,
양방향 - 노드의 양쪽 링크가 존재하는 -> 그래서 원형 순회 실현이 가능한
연결 리스트

를 포스팅 한다.

원형이라고 해서 개인적으로 위와 같은 형태로  생각하면 혼란만 가중할 것이라고 생각한다. 아래와 같이 말이다.

그래서 우리는 머릿속의 형태를 정해놓고 시작해보고자 한다.

이러한 형태 임을 꼭 기억하고 있어야 한다.

노드 삽입 연산

삽입 연산은 노드가 없을 때와 있을 때로 나눈다.

크 따로 부가 설명이 필요 없을 것 같다ㅋ 

노드 삭제 연산

삭제는 간단하다. 그림 하나로 표현 가능하다.

삭제의 기본이 되는 부분

 

그 이외에 순회 연산

순회 연산은 그냥 노드의 링크를 순방향/역방향으로 타는 인덱스 포인터를 만들어서 순회를 하면 된다. 다만, 원형 연결 리스트인 만큼 무한 반복에 빠질 수 있기 때문에 아래와 같은 조건을 넣어 무한 반복에서 탈출하도록 해야한다.

위 코드는 순방향 순회, 역방향 순회 모두 마찬가지로 해당되는 부분이다.

 

메모리 관리 부분

해당 코드에서 또한 메모리 관리 부분이 따로 있기 때문에 삭제 연산 시에도 바로 메모리를 제거 하지 않고 프로그램 종료 전에 한꺼번에 모두 free 시키도록 되어 있다.

클래스로 stack 컨테이너 어댑터로 아래와 같이 구현되어 있다.

코드 및 실행 결과

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
#include <iostream>
#include <stack>
#include <stdio.h>
 
using namespace std;
 
// 구조체 존
struct node {
    int data;
    struct node* prev;
    struct node* next;
};
 
struct list {
    struct node* head;
    struct node* ci; // current index
    int count;
};
 
// 클래스 존
class NodeMemoryManager // 이 클래스 자체에 템플릿을 때려버리면 여러 타입에 대해서 관리할 수 있다ㅋ
{
private:
    int count; // 내부적인 교차 검증을 위한 count;
    stack<struct node*> allocated_node_address;
public:
    NodeMemoryManager()
    {
        this->count = 0;
    }
    ~NodeMemoryManager()
    {
        int free_count = 0;
        int stack_count = this->allocated_node_address.size(); // 제거하기 전 숫자.
 
        // 스택은 내부적으로 벡터니까 -> 임의 접근이 되지 않을까? -> 불가능 -> 그럴거면 벡터를 쓰지 왜 스택을 쓰나? 스택의 탄생 이유이다.
        while (!this->allocated_node_address.empty())
        {
            free(this->allocated_node_address.top()); // c에서 malloc 할 것이니, free 함수.
            this->allocated_node_address.pop();
            free_count++;
        }
        cout << "모든 메모리가 해체되었습니다[" << free_count << "/" << this->count << "(" << stack_count << ")]" << endl;
    }
    struct node* CreateNodeAuto(void)
    {
        struct node* tmp = (struct node*)malloc(sizeof(struct node));
        // 초기화
        tmp->data = 0;
        tmp->prev = NULL;
        tmp->next = NULL;
        // 스택 추가
        this->AddAllocatedNodeAddress(tmp);
        return tmp;
    }
    void AddAllocatedNodeAddress(struct node* addr)
    {
        this->allocated_node_address.push(addr);
        this->count++;
        return;
    }
    int GetCount()
    {
        return this->count;
    }
    int GetCountByStack()
    {
        return this->allocated_node_address.size();
    }
};
 
// 재정의 존
typedef struct list List;
 
// 함수 선언 존
void ListInit(List* list);
void LInsert(List* list, int data);
int LFirst(List* list, int* data);
int LNext(List* list, int* data, int non_exit);
int LPrevious(List* list, int* data, int non_exit);
void LRemove(List* list);
 
// 전역 변수 존
NodeMemoryManager nmm;
 
//메인 함수
int main(void)
{
    List list;
    int data;
 
    ListInit(&list);
 
    // 값 1 ~ 값 8 까지 추가.
    LInsert(&list, 1); LInsert(&list, 2); LInsert(&list, 3); LInsert(&list, 4); LInsert(&list, 5); LInsert(&list, 6); LInsert(&list, 7); LInsert(&list, 8);
 
    LFirst(&list, &data);
 
    // 한 칸 씩 이동
    printf("-------- previous zone \n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
 
    printf("-------- next zone \n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1) == 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
 
    // 순회 및 삭제 처리
    printf("-------- remove zone \n\n");
    if (LFirst(&list, &data))
    {
        if (data == 2)
            LRemove(&list);
        while (LNext(&list, &data, 0))
        {
            if (data == 2)
                LRemove(&list);
        }
        while (LPrevious(&list, &data, 0))
        {
            if (data == 6)
                LRemove(&list);
        }
    }
 
    // 순회
    printf("-------- circuit zone \n");
    if (LFirst(&list, &data))
    {
        printf(" - [%p|%p(%d)|%p] - \n", list.ci->prev, list.ci, list.ci->data, list.ci->next);
        while (LNext(&list, &data, 0))
            printf(" - [%p|%p(%d)|%p] - \n", list.ci->prev, list.ci, list.ci->data, list.ci->next);
        while (LPrevious(&list, &data, 0))
            printf(" - [%p|%p(%d)|%p] - \n", list.ci->prev, list.ci, list.ci->data, list.ci->next);
    }
 
    printf("최종으로 남은 노드의 개수는? ( %d )\n", list.count);
 
    return 0;
}
 
// 함수 정의 존
void ListInit(List* list)
{
    // 헤더 생성 및 초기화
    list->head = NULL;
    // 카운트 초기화
    list->count = 0;
    // 인덱스 노드를 초기화
    list->ci = NULL;
 
    return;
}
 
void LInsert(List* list, int data)
{
    // 새 노드 생성
    struct node* new_node = nmm.CreateNodeAuto();
 
    // 새 노드 초기화
    new_node->data = data;
 
    if (list->head == NULL) // 자료구조 자체가 비어있으면
    {
        new_node->prev = new_node->next = new_node;
    }
    else
    {
        // 새 노드의 양 링크를 연결.
        new_node->next = list->head; // 1. [새 노드] -> 기존 시작 노드 연결
        new_node->prev = list->head->prev; // 2. 기존 끝 노드 <- [새 노드] 연결
 
        // 양쪽 노드의 prev 링크들을 연결.
        new_node->next->prev = new_node; // 새 노드 <- [기존 시작 노드] 연결
        new_node->prev->next = new_node; // 새 노드 <- [기존 끝 노드] 연결
    }
 
    // 헤드와 빈 노드 연결
    list->head = new_node;
 
    // 노드 추가 완료 시, 카운트 증가
    list->count++;
 
    return;
}
 
int LFirst(List* list, int* data)
{
    // 헤드를 검사한다. 널이면 false 반환, 널이 아니면 진행
    if (list->head == NULL)
        return false;
 
    // 인덱스를 옮긴다.
    list->ci = list->head;
 
    // 데이터 참조하여 값을 변경
    *data = list->ci->data;
 
    // true 반환
    return true;
}
 
int LNext(List* list, int* data, int non_exit)
{
    // LFirst 가 실행되지 않은 경우는 false
    if (list->ci == NULL)
        return false;
 
    // 다음 가리키는 것이 헤드가 가리키는 것과 같은지를 확인한다. -> 끝인지를 확인하는 방법 -> 같으면 false 반환
    // 원형이기 때문에 검사가 필요한데, non_exit인자는 원점을 지나쳐 원형으로 계속해서 순회하기 위해서 넣음.
    if ((non_exit == false) && (list->head == list->ci->next))
        return false;
 
    // 인덱스를 옮긴다.
    list->ci = list->ci->next;
 
    // 데이터 참조하여 값을 변경
    *data = list->ci->data;
 
    // true 반환
    return true;
}
 
int LPrevious(List* list, int* data, int non_exit)
{
    // LFirst 가 실행되지 않은 경우는 false
    if (list->ci == NULL)
        return false;
 
    // 해당 노드의 prev가 가리키는 것이 헤드가 가리키는 것과 같인지를 확인한다 -> 끝인지를 확인하는 방법 -> 같으면 false 반환
    if ((non_exit == false) && (list->head == list->ci->prev))
        return false;
 
    // 인덱스를 역행으로 옮긴다.
    list->ci = list->ci->prev;
 
    // 데이터 참조하여 값을 변경
    *data = list->ci->data;
 
    // true 반환
    return true;
}
 
void LRemove(List* list)
{
    // 타겟의 링크들이 끊기기 전에 따로 주소 값을 기록한다.
    struct node* target = list->ci;
 
    // 삭제할 타겟이 head가 가리키고 있는 노드라면
    if (list->head == target)
    {
        // 삭제할 타겟의 양 링크가 본인을 가리킨다면 삭제할 타겟은 하나!
        if (list->head == list->head->next) 
            list->head = NULL;
        else 
            list->head = target->next; // 헤드를 다음 노드로 옮겨준다.
    }
 
    // 타겟의 전 노드의 next 를 타겟의 next로 바꾼다
    target->prev->next = target->next;
 
    // 타겟의 다음 노드의 prev 를 타겟의 prev로 바꾼다
    target->next->prev = target->prev;
 
    // count를 줄인다.
    list->count--;
 
    // 메모리 해체는 NMM 객체가 알아서 해준다.
    return;
}
 cs

728x90
반응형
저작자표시

'프로그래밍응용 > C 자료구조' 카테고리의 다른 글

C Data Structure - 덱(디큐?)  (0) 2021.01.22
C Data Structure - 리스트 기반 큐  (0) 2021.01.20
C Data Structure - 연결 리스트 기반 스택  (0) 2021.01.19
C Data Structure - 스택  (0) 2021.01.18
C Data Structure - 원형 큐  (0) 2021.01.15
728x90
반응형

스택을 연결리스트로 구현해 보았다.

일단 기본 구조에 대한 예시를 나타낸 것이다.

먼저, 왼쪽 구조를 보자. 우리 스택이라고 생각하는 구조이다. Head는 삽입 인덱스를 나타낸다. 소위 말하는 top 변수. 그 왼쪽의 구조를 단순화시켜서 보면 오른쪽처럼 나타낼 수 있다. 오른쪽 구조에서 Head 노드는 새롭게 노드가 삽입될 때 마다 가리키는 것을 갱신시키는데, 이 현상을 자세히 보면 왼쪽 구조에서 head가 옮겨다니는 것과 같다. 

다른 현상을 가지고 생각하기 나름으로 같은 본질을 끌어냈다 크.. 윤성우 교수님께 박수를...

암튼 왼쪽이든 오른쪽이든 위와 같은 본질의 구조를 구현할 것이다.

삽입 연산

1) 헤드와 기존 최 상단 노드의 연결을 끊고, 2) 새 노드와 최상단 노드를 연결하여 새 노드를 최상단 노드로 변경하고,  그 3) 최상단 노드를 헤드가 가리키도록 헤드 값을 갱신 

삭제 연산

삭제의 기본 동작은 노란색 글씨와 빨간색 글씨로 표현을 해두었다.

파란색 글씨는 대충 이런 말이다. 할당된 메모리는 따로 이전에 만들어 뒀던 자료구조로 따로 저장하여 관리하고 프로그램 종료 시, 일괄로 삭제하기 때문에 관련 포인터만 변경하고(모든 포인터 연결을 삭제 '처리') 삭제 되었다고 생각하고 진행하라는 의미이다. 

비어짐 확인

이런 구조에서 비어짐을 확인하려면 어떻게 하면 될까? 
> Head가 NULL을 가리키면 텅 빈 상태입니다. (O)
이런 구조에서 꽉 참을 확인하려면 어떻게 하면 될까?
> 연결 리스트 기반이라 꽉 찰 것을 걱정하지 않아도 됩니다.(O) 그 걱정대신 작성자 나이 걱정을.... (ㅜ.ㅜ)

뭐 더 쓸 말이 없다.

 

코드 및 실행 결과

프로그램 코드를 제출하기에 앞서 복습도 할 겸,
이전에 배웠던 원형 큐를 활용하여 메모리가 생성될 때마다 원형 큐에 메모리 주소를 넣고, 프로그램이 종료될 때 일괄적으로 free~~~~~~~ 된다. 그니까 생성만 했다하면 원형 큐에 넣어제끼고, 프로그램이 끝나기 직전에 다 소멸시켜버리는 것이다. 그래서 실행 결과가 지저분하여 실행결과도 약간의 설명을 넣을 예정이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#include <stdio.h>
#include <stdlib.h>
 
#define QUEUE_LEN 11
 
#define TRUE 1
#define FALSE 0
 
struct node
{
    int data;
    struct node* next;
};
 
struct list_stack
{
    struct node* head;
    int count;
};
typedef struct list_stack stack;
 
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
struct array_queue // 배열 기반 원형 큐 구현
{
    int front;
    int rear;
    int count;
    struct node* queue_array[QUEUE_LEN];
};
typedef struct array_queue queue;
 
void QueueInit(queue* q);
int QisEmpty(queue* q);
struct node* Dequeue(queue* q);
void Enqueue(queue* q, struct node* data);
void ShowQueue(queue* q);
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
 
void RemoveAllNodeAuto(queue* q);
struct node* CreateNodeAuto(stack* s, queue* q);
 
// list stack 
void StackInit(stack* s);
int SIsEmpty(stack* s);
 
void SPush(stack* s, queue* q, int data);
int SPop(stack* s, queue* q);
int SPeek(stack* s);
 
int main(void)
{
    stack s;
    queue q;
 
    QueueInit(&q);
    StackInit(&s);
 
    SPush(&s, &q, 1);
    SPush(&s, &q, 2);
    SPush(&s, &q, 3);
    SPush(&s, &q, 4);
    SPush(&s, &q, 5);
 
    while (!SIsEmpty(&s))
        printf("%d ", SPop(&s, &q));
    fputc('\n', stdout);
 
    ShowQueue(&q);
    printf("----------------------------------------------------------\n");
    RemoveAllNodeAuto(&q);
    return 0;
}
 
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
void QueueInit(queue* q)
{
    int i = 0;
 
    q->front = q->rear = 0;
 
    for (i = 0; i < QUEUE_LEN; i++)
        q->queue_array[i] = NULL; // 큐 출력을 위한 초기화
 
    q->count = 0;
    return;
}
int QisEmpty(queue* q)
{
    if (q->front == q->rear)
        return TRUE;
    else
        return FALSE;
}
struct node* Dequeue(queue* q)
{
    struct node* target;
    // 기본 동작 - 비었는가 확인 -> 삭제 -> 인덱스 변경
    if (q->front == q->rear)
    {
        printf("Queue가 이미 비었습니다.\n");
        return NULL;
    }
    target = q->queue_array[q->front];
    q->queue_array[q->front] = NULL;
    q->front = (q->front + 1) % QUEUE_LEN;
    return target;
}
void Enqueue(queue* q, struct node* data)
{
    // 기본 동작 - 꽉 찼는가 확인 -> 삽입 -> 인덱스 변경
    if ((q->rear + 1) % QUEUE_LEN == q->front) // 가득 찬 경우,
    {
        printf("Queue가 가득 찼습니다.\n");
        return;
    }
    q->queue_array[q->rear] = data;
    q->rear = (q->rear + 1) % QUEUE_LEN;
    q->count++;
    return;
}
 
void ShowQueue(queue* q)
{
    int i = 0;
    printf("{(r:%2d/f:%2d)} : ", q->rear, q->front);
    for (i = 0; i < QUEUE_LEN; i++)
        printf("[%2p]", q->queue_array[i]), putc('-', stdout);
    putc('\n', stdout);
    return;
}
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
 
// 내가 정의하는 함수
struct node* CreateNodeAuto(stack* s, queue* q)
{
    struct node* tmp = (struct node*)malloc(sizeof(struct node));
    // 초기화
    tmp->data = 0;
    tmp->next = NULL; // tmp->next = s->head;
    // 큐 추가
    Enqueue(q, tmp);
 
    return tmp;
}
 
void RemoveAllNodeAuto(queue* q)
{
    struct node* rtarget = NULL;
    while (!QisEmpty(q))
    {
        rtarget = Dequeue(q);
        printf("[%p/(%d)]가 제거되었습니다.\n", rtarget, q->count);
        ShowQueue(q);
 
        free(rtarget);
        q->count--;
    }
    return;
}
 
// list stack 
void StackInit(stack* s)
{
    s->count = 0;
    s->head = NULL;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->head == NULL)
        return TRUE;
    else
        return FALSE;
}
 
void SPush(stack* s, queue* q, int data)
{
    // 추가해야할 새로운 노드 생성
    struct node* newnode = CreateNodeAuto(s, q);
    // 새로운 노드의 값 세팅 및 기존 노드로 next 연결
    newnode->data = data;
    newnode->next = s->head;
    // head를 새로운 노드와 연결
    s->head = newnode;
    // count 증가
    s->count++;
    return;
}
int SPop(stack* s, queue* q)
{
    struct node* target = s->head;
    // head 가 Null을 가리키고 있다면 스택이 비어있는 것. 조건 검사 진행
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어있습니다\n");
        return 0;
    }
    // head 를 target의 next, 다음 노드와 연결한다.
    s->head = target->next;
    // count 감소
    s->count--;
 
    return target->data;
}
int SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어있습니다\n");
        return 0;
    }
    return s->head->data;
}
 
 cs

혹시 보는 사람이 있다면 스택 부분만 참고하면 될 듯 합니다. 앞으로도 쭉 요래요..ㅋㅋ

 

728x90
반응형
저작자표시

'프로그래밍응용 > C 자료구조' 카테고리의 다른 글

C Data Structure - 리스트 기반 큐  (0) 2021.01.20
C Data Structure - 원형 양방향 연결 리스트  (0) 2021.01.19
C Data Structure - 스택  (0) 2021.01.18
C Data Structure - 원형 큐  (0) 2021.01.15
C Data Structure - 큐  (0) 2021.01.08
728x90
반응형

스택이란 정말 간단하다.

분명히 내가 이거 그림 그리면서 포스팅을 한거 같은데 아무리 블로그를 뒤져봐도 없다... 그래서 다시 하는 느낌으로 스택 첫 포스팅을 시작한다.

먼저, 

스택이란 무엇인가?

우리는 스택을 이미 알고 있다. 스택은 프링글스이다. 아래의 그림을 보자.

우리는 세 개의 감자칩 중에서 어떤 감자칩이 제일 먼저 들어갔는지 알 수 있다. 바로 A이다. 어떻게 알았지? 출입구가 하나이고, 원통 내부의 크기는 서로가 뭐 어떻게 비집고 해서 바꿀 수 있는 사이즈가 아니다. 

A가 먼저 들어갔고 -> 그 다음 B가 그 위에 쌓이고 -> 그 후 C가 들어가면서 그 위에 쌓이는 것이다.

이렇듯 스택은 쌓이는 특징을 가지고 있다. 그렇다면 안의 감자칩을 꺼내먹을 때에는 어떻게 할까? 

가장 나중에 들어간 C가 제일 먼저 다시 나오고 -> 그 다음 B가 나오고 -> 가장 먼저 들어간 A가 제일 늦게 나온다. 

이렇게 나중에 들어간 값이 제일 먼저 나오는 구조를 후입선출 구조라고 한다.

단순 배열 기반 스택에서의 삽입

어려울 것이 전혀 없다. 그냥 값이 들어오는데로 쌓아올린다고 생각하고 인덱스를 증가시키면서 값을 추가하면 된다.

82를 삽입 전(왼) / 82를 삽입 후(오)

하나도 어렵지 않다. 이렇게 보면 그냥 배열 끝에 값을 추가하는 것 같다. 우리는 스택에 값을 추가하는 행위를 push 라고 할 것이다. 삭제 연산을 보자. 

단순 배열 기반 스택에서의 삭제

3 값이 튀어나가면서 삭제 처리가 되어 버리고, 삽입 인덱스가 하나 감소한다.

마지막 하나 남은 1이 튀어 나가며 값이 삭제 처리 되고, 삽입 인덱스가 갈 곳을 잃는데 이 때, 삽입 인덱스를 -1로 하자. 그러면 나중에 빈 스택 상태에서 값을 추가할 때, 삽입 인덱스를 증가시키면 [-1] 에서 [0]으로 바뀌어서 자연스럽게 값을 추가하면 될 뿐만 아니라, 스택이 비어있는지 비어있지 않는지 삽입 인덱스가 -1인지 아닌지를 보면 된다.

그리고 우리는 삭제하는 연산을 pop 한다고 할 것이다.

단순 배열 기반 스택에서의 비워짐과 꽉참을 확인

또한 간단하다.
인덱스가 비워져 있는지를 확인하기 위해선 아까 삭제 연산에의 약속대로 삽입 인덱스가 -1인지를 확인하면 된다. 
인덱스가 가득차 있는지를 확인하기 위해선 현재 삽입 인덱스가 배열의 길이랑 같은지를 확인하면 된다.

코드 및 실행 결과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include <stdio.h>
#define STACK_LEN 10
 
#define TRUE 1
#define FALSE 0
 
struct array_stack
{
    int stack_arr[STACK_LEN];
    int top_index;
};
 
typedef array_stack stack;
 
void StackInit(stack* s);
int SIsEmpty(stack* s);
void SPush(stack* s, int data);
int SPop(stack* s);
int SPeek(stack* s);
 
int main(void)
{
    stack s;
    StackInit(&s);
 
    SPush(&s, 1);
    SPush(&s, 2);
    SPush(&s, 88);
    SPush(&s, 125);
    SPush(&s, 9912);
 
    while (!SIsEmpty(&s))
        printf("[%d] ", SPop(&s));
    fputs("\n", stdout);
 
    if (SIsEmpty(&s))
        printf("스택이 텅 비었습니다.\n");
    return 0;
}
 
void StackInit(stack* s)
{
    s->top_index = -1;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1) // 같아도 된다고?
        return TRUE;
    else
        return FALSE;
}
void SPush(stack* s, int data)
{
    if (s->top_index == STACK_LEN)
    {
        printf("스택이 꽉 찼습니다.\n");
        return;
    }
 
    s->stack_arr[++(s->top_index)] = data;
    printf("스택에 %d 값이 추가 되었습니다.\n", s->stack_arr[s->top_index]);
    return;
}
int SPop(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어져 있습니다.\n");
        return -1; // 적절치 않다. -1 또한 값으로 넣을 수 있기 때문에. -> 차라리 프로그램을 종료시키는게 적절.
    }
    return s->stack_arr[s->top_index--];
}
int SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 텅 비었습니다.\n");
        return -1;
    }
    return s->stack_arr[s->top_index];
}
 cs

728x90
반응형
저작자표시

'프로그래밍응용 > C 자료구조' 카테고리의 다른 글

C Data Structure - 원형 양방향 연결 리스트  (0) 2021.01.19
C Data Structure - 연결 리스트 기반 스택  (0) 2021.01.19
C Data Structure - 원형 큐  (0) 2021.01.15
C Data Structure - 큐  (0) 2021.01.08
C Data Structure - 퀵 정렬  (0) 2021.01.06
728x90
반응형

Epoll 모델을 구현해 볼 시간이다. 

먼저, 필요로 하는 변수들이다.

코드는 중요한 변수만 넣었고, 그림에는 주석과 내가 작성한 그대로 캡춰한 것이니 함께 보면 좋을 것 같다.

1
2
3
int epoll_fd; // Epoll Instance
struct epoll_event* epoll_events; // 변화가 일어난 디스크립터들에 대해서 저장할 저장소(only 동적 할당)
struct epoll_event epoll_event;    // EPOLL_CTL_ADD 로 epoll_ctl 시 사용됨.
 cs

다음으로는 초기화 과정이다

1
2
3
4
5
6
7
8
9
// epoll 인스턴스 저장소 생성.
this->epoll_fd = epoll_create(Server::SERVER__CONSTVAR__MAX_USER_COUNT);
// 변화가 발생한 디스크립터들만 저장되는 구조체이며, 반드시 동적할당.
this->epoll_events = (struct epoll_event*)malloc(sizeof(struct epoll_event) * Server::SERVER__CONSTVAR__MAX_USER_COUNT);
// 이벤트 등록을 위한 준비
this->epoll_event.events = EPOLLIN;
this->epoll_event.data.fd = this->serv_sock;
// 이벤트 종류 등록
epoll_ctl(this->epoll_fd, EPOLL_CTL_ADD, this->serv_sock, &this->epoll_event);
 cs

그림으로 충분히 설명될꺼라고 생각한다.

이어서, 접속 요청이나 데이터 수신을 위해 epoll_wait 함수를 호출하는 부분이다

1
2
int changed_fd_count = 0;
changed_fd_count = epoll_wait(this->epoll_fd, this->epoll_events, Server::SERVER__CONSTVAR__MAX_USER_COUNT, -1);
 cs

2번 라인에서 epoll instance(epoll_fd)와 변화된 파일 디스크립터를 저장할 버퍼의 주소 값(epoll_events), 변화될 이벤트를 저장할 갯수, -1 값이 순서대로 들어간다. 

epoll_wait의 마지막 인자에 -1 값이 들어간다면 파일 디스크립터의 변화가 생겨서 이벤트가 발생할 때까지 무한 대기에 들어간다.

그리고 가장 중요한 것은 select 모델에서 처럼 매번의 epoll_wait 함수 호출마다 등록된 파일 디스크립터의 배열을 전달하지 않는다.

다음은 epoll_wait 함수 호출로 받아온 리턴 값 별 처리이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
changed_fd_count = epoll_wait(this->epoll_fd, this->epoll_events, Server::SERVER__CONSTVAR__MAX_USER_COUNT, -1); // -1 전달 시 이벤트 발생까지 무한 대기
if (changed_fd_count == -1)
    HandleStatus("SERVER", true, "epoll_wait() Error\n");
if (changed_fd_count == 0)
    return 0;
for (int i = 0, fd = -1; i < changed_fd_count && (fd = this->epoll_events[i].data.fd); i++)
{
    if (fd == this->serv_sock) // 접속 요청
    {
        AcceptConnectionRequest(this->serv_sock);
        this->PrintConsoleNowUser();
    }
    else // 수신 및 종료
    {
        r_var = this->ReceiveData(fd);
        if (r_var == Server::SERVER__RETURNVAR__DISCONNECT_USER) {
            this->Disconnect(fd);
               this->PrintConsoleNowUser();
        } else {
            if (this->HandlePacketMessage(fd) == Server::SERVER__RETURNVAR__TERMINATE_BY_ADMIN)
                return Server::SERVER__RETURNVAR__TERMINATE_BY_ADMIN;
        }
    }
}
 cs

중요한 것은 6번 라인에서 돌아가는 반복문이 등록된 모든 파일 디스크립터를 대상으로 하는 것이 아니라, 변화가 일어난 파일 디스크립터의 수 만큼만 반복이 이루어진다는 점이다.

좀 더 세분화 했을 때, 접속 요청에 따른 수락 시 클라이언트 파일 디스크립터의 등록이다.

1
2
3
this->epoll_event.events = EPOLLIN;
this->epoll_event.data.fd = this->clnt_sock;
epoll_ctl(this->epoll_fd, EPOLL_CTL_ADD, this->clnt_sock, &this->epoll_event);
 cs

접속해 온 클라이언트 소켓 파일 디스크립터에 대해서 수신에 대해서 감시하겠다 라는 의미로 EPOLLIN 이벤트로 등록한다

 

접속한 클라이언트가 종료할 경우를 확인한다

종료하려는 클라이언트의 파일 디스크립터를 당연히 원본 fd_set의 배열에서 빼줘야한다. 종료하는데 지니고 있어서 뭐 하는가 ㅎㅎ..

대충 큰 처리 방법들은 한 번씩 다 훑어봤다.

728x90
반응형
저작자표시

'프로그래밍응용 > Socket' 카테고리의 다른 글

C기반 I/O Multiprocessing - 9. 멀티 프로세싱에서 좀비 문제  (0) 2021.02.01
C기반 I/O Multiprocessing - 8. 드디어 올리는 멀티 프로세싱  (0) 2021.02.01
C기반 I/O Multiplexing - 6. Select와 Epoll의 차이점과 Epoll 컨셉  (0) 2021.01.18
C기반 I/O Multiplexing - 5. Select 모델의 단점  (0) 2021.01.18
C기반 I/O Multiplexing - 4. Level Trigger와 Edge Trigger  (0) 2021.01.17
728x90
반응형
 

C기반 I/O Multiplexing - 5. Select 모델의 단점

자, 오늘도 기록을 한다 지난 포스팅들을 보면 select 모델들을 학습했다. 그런데 이 select 모델은 굉장한 단점들이 있다고 하더라.. 단점들로 인해서 발생하는 현상부터 말하자면 다음과 같다. 클

typingdog.tistory.com

이전 포스팅에서 select 모델의 단점에 대해서 기록했다.

결론적으로 단점은 다음과 같다.

1. select 반환 값에 따라 행동을 할 때, 등장하는 등록된 파일 디스크립터들을 대상으로 하는 반복문
2. Select 함수를 호출할 때마다 관찰 대상의 인자 전달.

결국, 등록된 파일 디스크립터들을 매번 통째로 넘기고, 통째로 결과를 받아오기 때문에 운영체제에게 넘기고 받고 하는 과정도 부담스럽고, 뭐가 변했는지 알려면 모든 파일 디스크립터들을 대상으로 반복문도 오지게~ 돌려야한다.

그러나 초기에 파일 디스크립터들을 넘기고, 갱신되는 부분들만 넘기고 받는다면 운영체제에게 데이터를 주고 받는 과정에서 발생하는 오버헤드를 줄일 수 있고, 등록된 파일 디스크립트 전체를 대상으로 돌던 반복문을 갱신된 파일 디스크립터에 대해서만 반복문을 돌리면 되니 매우 효율적일 수 밖에 없다. 이런 방식으로 동작하는 것이 바로 Epoll 모델이다.

Epoll 모델의 컨셉

Epoll 모델의 컨셉은 파일 디스크립터들을 등록하고, 이벤트 발생 대기 함수를 실행하여 변화된 파일 디스크립터들을 뽑아내어 처리한다는 Select 모델의 컨셉과 다를 바가 없다. 이를 전제로 차이를 확인하면서 컨셉을 보자.

파일 디스크립터 저장소 생성

파일 디스크립터를 저장할 수 있는 저장소의 생성이다. 이 저장소를 Epoll Instance 라고 하며, 이 인스턴스 또한 파일 디스크립터를 부여받는다. 이 fd를 이용하여 파일 디스크립터를 추가 및 제거할 때 저장소를 지목(?) 할 때 쓴다.

epoll_create 로 저장소를 생성하며, 인자로 들어가는 크기 정보는 절대적인 것이 아니라 운영체제가 참고로만 사용한다고 한다.

파일 디스크립터의 등록

epoll_ctl 함수는 감시할 파일 디스크립터를 등록 및 삭제, 수정하는 함수이다. Select 모델에서의 FD_ 매크로들의 기능을 하나의 함수로 수행하도록 되어 있으며, 파일 디스크립터마다 관찰할 이벤트 유형을 지정할 수 있다.

먼저 추가, 삭제, 변경(수정) 부분이다.

이러한 매크로 상수를 값으로 넣을 수 있다. 용도에 맞게.

관찰 대상의 이벤트 유형을 등록할 때에는 아래와 같은 자료형에 값을 넣어서 인자 전달을 한다.

왼쪽 구조체에서 events 라는 부분에 이벤트의 종류를 명시하면 되는데 우리가 만드는 프로그램은 서버이므로 수신 이벤트에 초점을 맞춘다. 그러므로 아래와 같이 EPOLLIN 이라는 매크로 상수를 사용한다.

참고 ) Epoll 등록가능한 이벤트는 enum으로 열거되어 있다.

Epoll_wait 함수의 호출

epoll_wait 함수를 이용하여 변화하는 이벤트를 솎아낸다 ㅋㅋ 이 함수를 통해서 변화가 발생하는 파일 디스크립터들만 뽑아낼 수 있다! 어디에? 두 번째 인자로 전달되는 버퍼 변수에!

기본 컨셉은 select 모델과 다를 부분이 크게 없으며, 약간 약간의 차이이다. 그리고 select 모델에서 level trigger 적인 특성을 지닌 것처럼 epoll 모델은 level trigger가 기본 형태이다.

다음 포스팅에는 코드 레벨에서 정리를 해볼 것이다.

728x90
반응형
저작자표시

'프로그래밍응용 > Socket' 카테고리의 다른 글

C기반 I/O Multiprocessing - 8. 드디어 올리는 멀티 프로세싱  (0) 2021.02.01
C기반 I/O Multiplexing - 7. Epoll 모델 구현 코드  (0) 2021.01.18
C기반 I/O Multiplexing - 5. Select 모델의 단점  (0) 2021.01.18
C기반 I/O Multiplexing - 4. Level Trigger와 Edge Trigger  (0) 2021.01.17
C기반 I/O Multiplexing - 3. Select 함수 활용 코드  (0) 2021.01.17
728x90
반응형

자, 오늘도 기록을 한다 

지난 포스팅들을 보면 select 모델들을 학습했다. 그런데 이 select 모델은 굉장한 단점들이 있다고 하더라..

단점들로 인해서 발생하는 현상부터 말하자면 다음과 같다.

클라이언트를 동시에 수용할 수 있는 수가 100 을 넘기가 힘들다.

뭐 나처럼 프리 서버나 만드는 수준이라면 상관없겠지만, 그래도 100명은 너무 적지 않나 싶다. 그렇다면 왜 그런지 알아보자.

Select 모델의 단점

1. select 반환 값에 따라 행동을 할 때, 등장하는 등록된 파일 디스크립터들을 대상으로 하는 반복문

이게 첫 번째 문제이다. 아래 코드를 보면 된다.

55번 라인에서 select 함수를 호출한 뒤 반환되는 값에 따라서 변화한 파일 디스크립터의 수만큼 반복 루프를 도는 것도 아니고, 전체 등록된 파일 디스크립터의 수만큼 반복 루프 및 조건 검사를 진행한다.

이 말인 즉슨, 파일 디스크립터가 딱 하나 변한다고 하더라도 전체를 검사한다는 소리이다. -> 매우 비효율적이다.

2. Select 함수를 호출할 때마다 관찰 대상의 인자 전달.

위 그림에서 51번 라인에서 등록된 파일 디스크립터들을 최신화하고, 55번 라인에서 select 함수의 인자로 전달을 한다. 이러한 인자 전달은 select 함수 내에서만 사용되고 마는 것이 아니다. 

파일 디스크립터의 변화를 파악한다는 것은 수신 버퍼, 쓰기 버퍼 등을 확인하는 작업이기 때문에 운영체제의 관리 대상이다. 운영체제의 도움이 필요한 것이다.  즉, 전달된 인자를 운영체제에게까지 전달하여 운영체제의 도움을 받아야 한다는 소리인데..

응용 프로그램 단에서 운영체제에게 이렇게 많은 데이터를 전달한다는 것은 부담이 크다고 한다. 

그래서 운영체제에게 관찰 대상에 대한 정보를 초기에 한 번 알려주고, 갱신되는 부분에 대해서만 알려주는 방식을 사용하면 되지않을까 라는 생각에서 나온 것이 Epoll 방식이다. 윈도우에서는 IOCP 라는 개념으로 발전되었다고 한다.

다음 번 포스팅은 Epoll 이다. Epoll 모델이 기존 Select 모델에 비해 무엇이 달라졌는지 정도 확인과 작성 코드를 분석하는 시간을 갖겠다.

 

 

 

728x90
반응형
저작자표시

'프로그래밍응용 > Socket' 카테고리의 다른 글

C기반 I/O Multiplexing - 7. Epoll 모델 구현 코드  (0) 2021.01.18
C기반 I/O Multiplexing - 6. Select와 Epoll의 차이점과 Epoll 컨셉  (0) 2021.01.18
C기반 I/O Multiplexing - 4. Level Trigger와 Edge Trigger  (0) 2021.01.17
C기반 I/O Multiplexing - 3. Select 함수 활용 코드  (0) 2021.01.17
C기반 I/O Multiplexing - 2. Select 함수 사용하기 전에 컨셉을 보자  (0) 2021.01.17
728x90
반응형

 이전 포스팅 때, 두 개념을 언급했다.

Level-Trigger와 Edge Trigger의 차이를 그냥 Epoll 함수 공부를 할 때에는 잘 몰랐는데, 아래와 같은 상황에서 다시 생각해보게 되었다.

select 로 넘어온 디스크립터 변화의 갯수만큼 처리를 하지 않고 그냥 넘어가면 어떻게 될까?

라는 의문에서 부터 시작 되었다. 

Level Trigger 란? 

아래부터는 윤성우, 『열혈 tcp/ip 소켓 프로그래밍』, 오렌지미디어(2009), p376-p377. 이렇게 인용이 됩니다

윤성우 선생님/교수님의 책에 잘 정리가 되어 있어서, 비유 예시를 인용합니다. 내용을 좀 바꾸려다가 인용하는거 그냥 쓸께유 ㅋㅋ

아들 : 엄마 세뱃돈으로 5,000원 받았어요.
엄마 : 훌륭하구나

아들 : 엄마 옆집 숙희가 떡볶이 사달래서 사줫더니 2,000원 남았어요.
엄마 : 장하다 우리 아들 ~

아들 : 엄마 변신가면 샀더니 500원 남았어요.
엄마 : 그래 용돈 다 쓰면 굶으면 된다!

아들 : 엄마 여전히 500원 갖고 있어요. 굶을 수 없잖아요
엄마 : 그래 매우 현명하구나!

아들 : 엄마 여전히 500원 갖고 있어요. 끝까지 지켜야지요.
엄마 : 그래 힘내거라!

레벨 트리거의 핵심은 굵을 글씨이다.

5,000원이 들어온 이후에는 더 이상 돈이 발생하거나 더해지지 않았다.
>> 5,000원 어치의 이벤트 변화가 발생했다라고 생각하면 된다.

500원에서 계속 변화가 없음에도 불구하고 500원이 있다고 알란다.
>> 파일 디스크립터의 변화가 없더라도 처음에 들어온 것에 비해 남아있기만 한다면 계속해서 이벤트가 등록된다.

이러한 동작 방식이 레벨 트리거 방식이다. 

select 로 넘어온 디스크립터 변화의 갯수만큼 처리를 하지 않고 그냥 넘어가면 어떻게 될까?

그러므로 위와 같은 의문은 잘 해결된다. 등록된 이벤트만큼 처리하지 않더라도 이벤트가 다시 알려지기 때문에 당장 바로 처리하지 않아도 해당 이벤트가 무시되는 것이 아니라, 시간이 흘러감에 따라 처리할 수 있다는 뜻이다. 

그렇다면 엣지 트리거 방식은 무엇일까?

 Edge Trigger 란?

아래부터는 윤성우, 『열혈 tcp/ip 소켓 프로그래밍』, 오렌지미디어(2009), p376-p377. 이렇게 인용이 됩니다

아들 : 엄마 세뱃돈으로 5,000원 받았어요.
엄마 : 음 다음엔 더 노력하거라.(근데 과연 무슨 노력을 해야하는 것일까...? ㅋㅋㅋㅋ)

아들 : ..........................................
엄마 : 말 좀 해라! 그 돈 어쨌냐? 계속 말 안 할거냐?

딱 한 번 5,000원이 들어왔을 때, 이벤트가 등록되고, 그 이후에는 아무리 계속 남아있다고 해도 이벤트가 추가로 등록되지 않는다.

이런 차이가 있다.

다음 번에는 Select 모델의 한계에 대해서 포스팅 할 예정이다.

728x90
반응형
저작자표시

'프로그래밍응용 > Socket' 카테고리의 다른 글

C기반 I/O Multiplexing - 6. Select와 Epoll의 차이점과 Epoll 컨셉  (0) 2021.01.18
C기반 I/O Multiplexing - 5. Select 모델의 단점  (0) 2021.01.18
C기반 I/O Multiplexing - 3. Select 함수 활용 코드  (0) 2021.01.17
C기반 I/O Multiplexing - 2. Select 함수 사용하기 전에 컨셉을 보자  (0) 2021.01.17
C기반 I/O Multiplexing - 1. Multiprocessing과 Multiplexing 비유  (0) 2021.01.15
728x90
반응형
 

C기반 I/O Multiplexing - 2. Select 함수 사용하기 전에 컨셉을 보자

C기반 I/O Multiplexing - 1. Multiprocessing과 Multiplexing 비유 최근, 아니 비교적 최근에 어떤 게임 클라이언트를 활용한 게임 서버를 만드는 프로젝트를 진행했던 적이 있고, 지금도 조금씩 조금씩 하고

typingdog.tistory.com

여기서 개념과 컨셉을 확인했다.

코드 분석도 중요하다. 왜냐하면 코드에서 드러나는 select 기반 모델의 특징들이 있기 때문이다.

먼저, 필요로 하는 변수들이다.

코드는 중요한 변수만 넣었고, 그림에는 주석과 내가 작성한 그대로 캡춰한 것이니 함께 보면 좋을 것 같다.

struct timeval timeout; // select 함수의 시간을 지정.
fd_set fd_pool; // 비트 배열이라고 생각.

 

다음으로는 초기화 과정이다

FD_ZERO(&this->fd_pool);
FD_SET(this->serv_sock, &this->fd_pool); 
 // this->serv_sock = socket(PF_INET, SOCK_STREAM, 0); 에서의 리턴 값이다. 
this->fd_max = this->serv_sock; //초기화 하는 시점을 기준으로 가장 나중에 생성된 파일 디스크립터.

 

이어서, 접속 요청이나 데이터 수신을 위해 select 함수를 호출하는 부분이다

// select 함수 호출 시, 값이 리셋되므로 this->fd_pool을 바로 사용하지 않고 임시 변수 fd_temp_pool로 사용한다.
fd_set fd_temp_pool = this->fd_pool; 

// 타임 설정
this->timeout.tv_sec = select_sec;
this->timeout.tv_usec = select_usec;

this->fd_num = select(this->fd_max + 1, &fd_temp_pool, 0, 0, &this->timeout);
// fd_max+1인 이유는 파일 디스크립터는 0부터 시작하며 생성될 때마다 1씩 증가한다. 
// 그러므로 생성된 파일 디스크립터 중 최대값에 +1을 하면 그 갯수가 나온다.

fd_temp_pool에 대입하는 부분이 중요하다. select 함수가 호출하면 변화되는 부분을 표현할 때, 인자로 넘어온 fd_set 주소 값을 이용하여 변화된 파일 디스크립터 외에 나머지에 해당하는 부분은 값을 탈락시킨다.

그렇기 때문에 등록해놓은 파일 디스크립터 정보들이 탈락할 수 있는, 원본이 바뀌는 구조이기 때문에 꼭 임시 변수에 최신화된 파일 디스크립터 정보들을 넣어주고, 임시 변수를 통해서 select 함수로의 인자 전달이 이루어져야 한다.

다음은 select 함수 호출로 받아온 리턴 값별 처리이다.

--

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
if (this->fd_num > 0 ) // >0:성공,
    if (FD_ISSET(this->serv_sock, &fd_temp_pool)) 
    {    // fd_pool에 serv_sock에 대한 변화가 존재한다면 양수 반환 -> 서버 소켓의 변화 -> 접속 의미.
        AcceptConnectionRequest(this->serv_sock);
        this->PrintConsoleNowUser();
    }
    else // 기존 접속된 클라이언트의 수신 및 종료
    {
        int r_var;
        for (int i = 0; i < this->now_user_count; i++) // 이렇게 순회를 도는 이유는 다음에 나오는 this->client[i] 때문에.
        {
            if (FD_ISSET(this->client[i], &(fd_temp_pool)))
            {
                r_var = this->ReceiveData(this->client[i]);
                if (r_var == Server::SERVER__RETURNVAR__DISCONNECT_USER) {
                    this->Disconnect(this->client[i]);
                    this->PrintConsoleNowUser();
                    break; // 동시에 여러 디스크립터들이 변화할 수 있는가를 확인해 본후 주석
                 } else {
                    if (this->HandlePacketMessage(this->client[i]) == Server::SERVER__RETURNVAR__TERMINATE_BY_ADMIN)
                        return Server::SERVER__RETURNVAR__TERMINATE_BY_ADMIN;
                    break; // 동시에 여러 디스크립터들이 변화할 수 있는가를 확인해 본후 주석
                }
            }
        }
    }
else if (this->fd_num == 0) // 0:timeout,
    return 0;
else // -1:실패
    HandleStatus("SERVER", true, "Select() Error\n");
 cs

fd_num이라는 이름의 정수형 변수로 리턴 값을 받는다. 이 때 넘어온 리턴 값에 따라 처리를 하는데, 일단 fd_num이 0보다 크다는 소리는 등록된 파일 디스크립터들 중에서 수신 관련하여 변화가 그 수 만큼 있었다는 소리이다.

아니, 그러면! select 한 번 호출 뒤 반환 값이 5가 나오면 5개의 변화가 있었다는 소리이고, 그러면 다섯 번을 처리해줘야 하는데, 현재 조건문 구조로는 다섯 번을 절대 처리하지 않는다. 이게 도대체 무슨 이유일까? 아니 무슨 말을 하고 있는지 이해가 가는가?

위 그림과 같다. 현재 5개의 파일 디스크립터에 변화가 발생했다.( 1번의 접속 요청 변화 , 4번의 수신 요청 변화 )

2번 줄을 보면 serv_sock의 변화가 생겼다. serv_sock에 수신할 데이터가 있다는 소리고 listen 소켓에서 수신할 데이터가 있다는 소리는 접속 처리를 한다는 소리이다. 근데 2번과 7번이 if ~ else 구조이기 때문에 if문에서 한 번 처리해버리면 다른 처리는 그냥 넘어가게 된다. 무시된다는 소리다.

하지만 이는 select 모델의 레벨 트리거적인 특성으로 인해 처리되지 않은 이벤트가 다음 select 함수 호출 때, 다시 드러나게 되고 이를 처리하게 된다. 

아니 그러면 이벤트가 발생했을 때 다 처리할 수 있게끔 하면 되지 않는가? -- 이건 그냥 코드 작성 스타일이다. 이벤트가 전부 감지 되었을 때 다 처리를 하려거든 매 select 마다 많은 루프를 돌려야 한다. 아래와 같이 말이다.

for( i < fd_num ) // 모든 접속자 혹은 리스너 파일 디스크립터들에 대해서 
{
    if(FD_ISSET(i, fd_temp_pool)) // 변화가 있었는지 검사를 하고 다녀야 한다.
    { 
        ...
    }
}

 

뭐 아무튼 본론으로 돌아와서, 위 코드에서 2번 줄의 접속 요청 수신 관련 listen 소켓에서의 변화가 일어나지 않았다면 else 구문인 7번 줄에 들어가고 이 경우는 데이터 수신에 관련된 경우이다. 

그러니까 파일 디스크립터의 변화가 있긴 있었는데 (1번 줄) 접속 요청은 아니고(2번줄), 수신에 관련된 파일 디스크립터의 변화가 있었던 것이다. 이 경우에는 어떤 파일 디스크립터에서 변화가 생겼는지 알아보기 위해 순회한다. 12번 줄을 통해 처리한다.

그리고 27번 줄에서는 select 반환 값이 0인 경우로, select에 지정된 시간 동안 파일 디스크립터들에서 아무 변화가 없었던 케이스가 된다. 뭐 이 경우에는 다시 select 함수를 호출하면 된다.

좀 더 세분화 했을 때, 접속 요청에 따른 수락 시 클라이언트 파일 디스크립터의 등록이다.

좀 더 세분화 했을 때, 변화가 발생한 클라이언트 파일 디스크립터로 부터 수신처리이다

접속한 클라이언트가 종료할 경우를 확인한다

FD_CLR(disconnect_target_fd, &this->fd_pool);
close(disconnect_target_fd);
this->now_user_count--;

종료하려는 클라이언트의 파일 디스크립터를 당연히 원본 fd_set의 배열에서 빼줘야한다. 종료하는데 지니고 있어서 뭐 하는가 ㅎㅎ..

대충 큰 처리 방법들은 한 번씩 다 훑어봤다.

다음은 간단하게 Level Trigger 와 Edge Trigger에 대해서 정말 간단하게 정리해보고자한다.

728x90
반응형
저작자표시

'프로그래밍응용 > Socket' 카테고리의 다른 글

C기반 I/O Multiplexing - 6. Select와 Epoll의 차이점과 Epoll 컨셉  (0) 2021.01.18
C기반 I/O Multiplexing - 5. Select 모델의 단점  (0) 2021.01.18
C기반 I/O Multiplexing - 4. Level Trigger와 Edge Trigger  (0) 2021.01.17
C기반 I/O Multiplexing - 2. Select 함수 사용하기 전에 컨셉을 보자  (0) 2021.01.17
C기반 I/O Multiplexing - 1. Multiprocessing과 Multiplexing 비유  (0) 2021.01.15

+ Recent posts

티스토리툴바