[109] | 1 | /**
|
---|
[128] | 2 | * \file cf_list.c
|
---|
[117] | 3 | *
|
---|
[128] | 4 | * \author myusgun <myusgun@gmail.com>
|
---|
| 5 | *
|
---|
[119] | 6 | * \brief 연결 리스트 구현
|
---|
[109] | 7 | */
|
---|
| 8 | #include "cf_list.h"
|
---|
| 9 | #include "cf_local.h"
|
---|
| 10 | #include "cf_error.h"
|
---|
| 11 |
|
---|
| 12 | #include <stdlib.h>
|
---|
| 13 |
|
---|
| 14 | #define ASSERT_CTX(__ctx) \
|
---|
| 15 | if (__ctx == NULL) \
|
---|
| 16 | return CF_ERROR_DS_INVALID_CTX
|
---|
| 17 |
|
---|
| 18 | #define ASSERT_TRAVERSER(__trav) \
|
---|
| 19 | if (__trav == NULL) \
|
---|
| 20 | return CF_ERROR_DS_INVALID_TRAVERSER
|
---|
| 21 |
|
---|
| 22 | #define ASSERT_ARGS(x) \
|
---|
| 23 | if ((x)) \
|
---|
| 24 | return CF_ERROR_DS_INVALID_ARGS
|
---|
| 25 |
|
---|
[151] | 26 | /** 리스트 노드 (cf_traverser의 구현) */
|
---|
[109] | 27 | typedef struct __cf_node__
|
---|
| 28 | {
|
---|
| 29 | void * element;
|
---|
| 30 | struct __cf_node__ * prev;
|
---|
| 31 | struct __cf_node__ * next;
|
---|
| 32 | } CF_NODE;
|
---|
| 33 |
|
---|
[151] | 34 | /** 리스트 컨텍스트 (cf_ctx의 구현) */
|
---|
[109] | 35 | typedef struct __cf_list__
|
---|
| 36 | {
|
---|
| 37 | int size;
|
---|
| 38 | CF_NODE * front;
|
---|
| 39 | CF_NODE * rear;
|
---|
[149] | 40 | } CF_LIST_CONTEXT;
|
---|
[109] | 41 |
|
---|
| 42 | /**
|
---|
| 43 | * 리스트 컨텍스트 생성
|
---|
| 44 | *
|
---|
[119] | 45 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
[109] | 46 | *
|
---|
[119] | 47 | * \param ctx 리스트 컨텍스트 포인터
|
---|
[109] | 48 | */
|
---|
| 49 | int
|
---|
[151] | 50 | CF_List_Create (cf_ctx * ctx)
|
---|
[109] | 51 | {
|
---|
[149] | 52 | CF_LIST_CONTEXT * context = NULL;
|
---|
[109] | 53 |
|
---|
[151] | 54 | ASSERT_CTX (ctx);
|
---|
[109] | 55 |
|
---|
[151] | 56 | context = NEWCTX (CF_LIST_CONTEXT);
|
---|
[109] | 57 | if (context == NULL)
|
---|
| 58 | return CF_ERROR_DS_CREATE_CTX;
|
---|
| 59 |
|
---|
[151] | 60 | *ctx = (cf_ctx) context;
|
---|
[109] | 61 |
|
---|
| 62 | return CF_OK;
|
---|
| 63 | }
|
---|
| 64 |
|
---|
| 65 | /**
|
---|
| 66 | * 리스트 컨텍스트 해제
|
---|
| 67 | *
|
---|
[119] | 68 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
[109] | 69 | *
|
---|
[119] | 70 | * \param ctx 리스트 컨텍스트
|
---|
[109] | 71 | */
|
---|
| 72 | int
|
---|
[151] | 73 | CF_List_Destroy (cf_ctx ctx)
|
---|
[109] | 74 | {
|
---|
[149] | 75 | CF_LIST_CONTEXT * context = (CF_LIST_CONTEXT *) ctx;
|
---|
[109] | 76 |
|
---|
| 77 | ASSERT_CTX (ctx);
|
---|
| 78 |
|
---|
| 79 | CF_List_RemoveAll (ctx);
|
---|
| 80 |
|
---|
| 81 | free (context);
|
---|
| 82 |
|
---|
| 83 | return CF_OK;
|
---|
| 84 | }
|
---|
| 85 |
|
---|
| 86 | /**
|
---|
[151] | 87 | * 리스트 탐색자(traverser)를 Front 위치로 설정
|
---|
[109] | 88 | *
|
---|
[119] | 89 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
[109] | 90 | *
|
---|
[119] | 91 | * \param ctx 리스트 컨텍스트
|
---|
| 92 | * \param traverser 리스트 탐색자 주소
|
---|
[109] | 93 | */
|
---|
| 94 | int
|
---|
[151] | 95 | CF_List_Front (cf_ctx ctx,
|
---|
| 96 | cf_traverser * traverser)
|
---|
[109] | 97 | {
|
---|
[149] | 98 | CF_LIST_CONTEXT * context = (CF_LIST_CONTEXT *) ctx;
|
---|
[109] | 99 |
|
---|
| 100 | ASSERT_CTX (ctx);
|
---|
| 101 | ASSERT_TRAVERSER (traverser);
|
---|
| 102 |
|
---|
[151] | 103 | *traverser = (cf_traverser *) context->front;
|
---|
[109] | 104 |
|
---|
| 105 | return CF_OK;
|
---|
| 106 | }
|
---|
| 107 |
|
---|
| 108 | /**
|
---|
[151] | 109 | * 리스트 탐색자(traverser)를 Rear 위치로 설정
|
---|
[109] | 110 | *
|
---|
[119] | 111 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
[109] | 112 | *
|
---|
[119] | 113 | * \param ctx 리스트 컨텍스트
|
---|
| 114 | * \param traverser 리스트 탐색자 주소
|
---|
[109] | 115 | */
|
---|
| 116 | int
|
---|
[151] | 117 | CF_List_Rear (cf_ctx ctx,
|
---|
| 118 | cf_traverser * traverser)
|
---|
[109] | 119 | {
|
---|
[149] | 120 | CF_LIST_CONTEXT * context = (CF_LIST_CONTEXT *) ctx;
|
---|
[109] | 121 |
|
---|
| 122 | ASSERT_CTX (ctx);
|
---|
| 123 | ASSERT_TRAVERSER (traverser);
|
---|
| 124 |
|
---|
[151] | 125 | *traverser = (cf_traverser *) context->rear;
|
---|
[109] | 126 |
|
---|
| 127 | return CF_OK;
|
---|
| 128 | }
|
---|
| 129 |
|
---|
| 130 | /**
|
---|
[151] | 131 | * 리스트 처음에 새 데이터 삽입
|
---|
[109] | 132 | *
|
---|
[119] | 133 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
[109] | 134 | *
|
---|
[119] | 135 | * \param ctx 리스트 컨텍스트
|
---|
| 136 | * \param element 삽입할 데이터 주소
|
---|
[151] | 137 | */
|
---|
| 138 | int
|
---|
| 139 | CF_List_AddFront (cf_ctx ctx,
|
---|
| 140 | const void * element)
|
---|
| 141 | {
|
---|
| 142 | int result = 0;
|
---|
| 143 | cf_traverser trav = NULL;
|
---|
| 144 |
|
---|
| 145 | ASSERT_CTX (ctx);
|
---|
| 146 |
|
---|
| 147 | result = CF_List_Front (ctx, &trav);
|
---|
| 148 | if (result < 0)
|
---|
| 149 | return result;
|
---|
| 150 |
|
---|
| 151 | return CF_List_InsertBefore (ctx, trav, element);
|
---|
| 152 | }
|
---|
| 153 |
|
---|
| 154 | /**
|
---|
| 155 | * 리스트 끝에 새 데이터 삽입
|
---|
[115] | 156 | *
|
---|
[151] | 157 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
| 158 | *
|
---|
| 159 | * \param ctx 리스트 컨텍스트
|
---|
| 160 | * \param element 삽입할 데이터 주소
|
---|
[109] | 161 | */
|
---|
| 162 | int
|
---|
[151] | 163 | CF_List_AddRear (cf_ctx ctx,
|
---|
| 164 | const void * element)
|
---|
[109] | 165 | {
|
---|
[151] | 166 | int result = 0;
|
---|
| 167 | cf_traverser trav = NULL;
|
---|
| 168 |
|
---|
| 169 | ASSERT_CTX (ctx);
|
---|
| 170 |
|
---|
| 171 | result = CF_List_Rear (ctx, &trav);
|
---|
| 172 | if (result < 0)
|
---|
| 173 | return result;
|
---|
| 174 |
|
---|
| 175 | return CF_List_InsertAfter (ctx, trav, element);
|
---|
| 176 | }
|
---|
| 177 |
|
---|
| 178 | /**
|
---|
| 179 | * 리스트 탐색자(traverser)의 앞에 새 데이터 삽입
|
---|
| 180 | *
|
---|
| 181 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
| 182 | *
|
---|
| 183 | * \param ctx 리스트 컨텍스트
|
---|
| 184 | * \param traverser 리스트 탐색자
|
---|
| 185 | * \param element 삽입할 데이터 주소
|
---|
| 186 | */
|
---|
| 187 | int
|
---|
| 188 | CF_List_InsertBefore (cf_ctx ctx,
|
---|
| 189 | const cf_traverser traverser,
|
---|
| 190 | const void * element)
|
---|
| 191 | {
|
---|
[149] | 192 | CF_LIST_CONTEXT * context = (CF_LIST_CONTEXT *) ctx;
|
---|
[151] | 193 | CF_NODE * node = NULL;
|
---|
| 194 | CF_NODE * newnode = NULL;
|
---|
[109] | 195 |
|
---|
| 196 | ASSERT_CTX (ctx);
|
---|
| 197 |
|
---|
[151] | 198 | newnode = NEWCTX (CF_NODE);
|
---|
[109] | 199 | if (newnode == NULL)
|
---|
| 200 | return CF_ERROR_DS_CREATE_NODE;
|
---|
| 201 |
|
---|
| 202 | newnode->element = (void *) element;
|
---|
| 203 |
|
---|
| 204 | TRY
|
---|
| 205 | {
|
---|
| 206 | if (CF_List_GetSize (ctx) == 0)
|
---|
| 207 | {
|
---|
| 208 | context->front = context->rear = newnode;
|
---|
| 209 | TRY_BREAK;
|
---|
| 210 | }
|
---|
| 211 |
|
---|
[151] | 212 | node = traverser ? (CF_NODE *) traverser : context->front;
|
---|
| 213 |
|
---|
| 214 | newnode->next = node;
|
---|
| 215 | if (node)
|
---|
[109] | 216 | {
|
---|
[151] | 217 | newnode->prev = node->prev;
|
---|
| 218 | node->prev = newnode;
|
---|
| 219 | if (newnode->prev)
|
---|
| 220 | newnode->prev->next = newnode;
|
---|
| 221 | }
|
---|
[109] | 222 |
|
---|
[151] | 223 | if (node == context->front)
|
---|
| 224 | context->front = newnode;
|
---|
| 225 | } NO_CATCH;
|
---|
[109] | 226 |
|
---|
[151] | 227 | context->size++;
|
---|
| 228 |
|
---|
| 229 | return CF_OK;
|
---|
| 230 | }
|
---|
| 231 |
|
---|
| 232 | /**
|
---|
| 233 | * 리스트 탐색자(traverser)의 뒤에 새 데이터 삽입
|
---|
| 234 | *
|
---|
| 235 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
| 236 | *
|
---|
| 237 | * \param ctx 리스트 컨텍스트
|
---|
| 238 | * \param traverser 리스트 탐색자
|
---|
| 239 | * \param element 삽입할 데이터 주소
|
---|
| 240 | */
|
---|
| 241 | int
|
---|
| 242 | CF_List_InsertAfter (cf_ctx ctx,
|
---|
| 243 | const cf_traverser traverser,
|
---|
| 244 | const void * element)
|
---|
| 245 | {
|
---|
| 246 | CF_LIST_CONTEXT * context = (CF_LIST_CONTEXT *) ctx;
|
---|
| 247 | CF_NODE * node = NULL;
|
---|
| 248 | CF_NODE * newnode = NULL;
|
---|
| 249 |
|
---|
| 250 | ASSERT_CTX (ctx);
|
---|
| 251 |
|
---|
| 252 | newnode = NEWCTX (CF_NODE);
|
---|
| 253 | if (newnode == NULL)
|
---|
| 254 | return CF_ERROR_DS_CREATE_NODE;
|
---|
| 255 |
|
---|
| 256 | newnode->element = (void *) element;
|
---|
| 257 |
|
---|
| 258 | TRY
|
---|
| 259 | {
|
---|
| 260 | if (CF_List_GetSize (ctx) == 0)
|
---|
| 261 | {
|
---|
| 262 | context->front = context->rear = newnode;
|
---|
| 263 | TRY_BREAK;
|
---|
[109] | 264 | }
|
---|
| 265 |
|
---|
[151] | 266 | node = traverser ? (CF_NODE *) traverser : context->rear;
|
---|
[109] | 267 |
|
---|
[151] | 268 | newnode->prev = node;
|
---|
| 269 | if (node)
|
---|
| 270 | {
|
---|
| 271 | newnode->next = node->next;
|
---|
| 272 | node->next = newnode;
|
---|
| 273 | if (newnode->next)
|
---|
| 274 | newnode->next->prev = newnode;
|
---|
[109] | 275 | }
|
---|
[151] | 276 |
|
---|
| 277 | if (node == context->rear)
|
---|
| 278 | context->rear = newnode;
|
---|
[109] | 279 | } NO_CATCH;
|
---|
| 280 |
|
---|
| 281 | context->size++;
|
---|
| 282 |
|
---|
| 283 | return CF_OK;
|
---|
| 284 | }
|
---|
| 285 |
|
---|
| 286 | /**
|
---|
[151] | 287 | * 리스트 탐색자(traverser)의 자리에 새 데이터 삽입
|
---|
| 288 | *
|
---|
| 289 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
| 290 | *
|
---|
| 291 | * \param traverser 리스트 탐색자
|
---|
| 292 | * \param element 할당할 데이터 주소
|
---|
| 293 | */
|
---|
| 294 | int
|
---|
| 295 | CF_List_Set (const cf_traverser traverser,
|
---|
| 296 | const void * element)
|
---|
| 297 | {
|
---|
| 298 | CF_NODE * node = (CF_NODE *) traverser;
|
---|
| 299 |
|
---|
| 300 | ASSERT_TRAVERSER (traverser);
|
---|
| 301 |
|
---|
| 302 | node->element = (void *) element;
|
---|
| 303 |
|
---|
| 304 | return CF_OK;
|
---|
| 305 | }
|
---|
| 306 |
|
---|
| 307 | /**
|
---|
| 308 | * 탐색자 위치의 데이터를 가져옴
|
---|
| 309 | *
|
---|
| 310 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
| 311 | *
|
---|
| 312 | * \param traverser 리스트 탐색자
|
---|
| 313 | * \param element 데이터 주소
|
---|
| 314 | */
|
---|
| 315 | int
|
---|
| 316 | CF_List_Get (const cf_traverser traverser,
|
---|
| 317 | void ** element)
|
---|
| 318 | {
|
---|
| 319 | CF_NODE * node = (CF_NODE *) traverser;
|
---|
| 320 |
|
---|
| 321 | ASSERT_TRAVERSER (traverser);
|
---|
| 322 | ASSERT_ARGS (element == NULL);
|
---|
| 323 |
|
---|
| 324 | *element = node->element;
|
---|
| 325 |
|
---|
| 326 | return CF_OK;
|
---|
| 327 | }
|
---|
| 328 |
|
---|
| 329 | /**
|
---|
[109] | 330 | * 리스트에서 탐색자 위치의 항목을 삭제
|
---|
| 331 | *
|
---|
[119] | 332 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
[109] | 333 | *
|
---|
[119] | 334 | * \param ctx 리스트 컨텍스트
|
---|
| 335 | * \param traverser 리스트 탐색자 주소
|
---|
[109] | 336 | */
|
---|
| 337 | int
|
---|
[151] | 338 | CF_List_Remove (cf_ctx ctx,
|
---|
| 339 | cf_traverser * traverser)
|
---|
[109] | 340 | {
|
---|
[149] | 341 | CF_LIST_CONTEXT * context = (CF_LIST_CONTEXT *) ctx;
|
---|
[109] | 342 | CF_NODE * node = NULL;
|
---|
| 343 |
|
---|
| 344 | ASSERT_CTX (ctx);
|
---|
| 345 | ASSERT_TRAVERSER (traverser);
|
---|
| 346 | ASSERT_ARGS (*traverser == NULL);
|
---|
| 347 |
|
---|
| 348 | node = (CF_NODE *) *traverser;
|
---|
| 349 |
|
---|
| 350 | if (node->prev)
|
---|
| 351 | {
|
---|
| 352 | node->prev->next = node->next;
|
---|
| 353 | if (node == context->rear)
|
---|
| 354 | context->rear = node->prev;
|
---|
| 355 | }
|
---|
| 356 |
|
---|
| 357 | if (node->next)
|
---|
| 358 | {
|
---|
| 359 | node->next->prev = node->prev;
|
---|
| 360 | if (node == context->front)
|
---|
| 361 | context->front = node->next;
|
---|
| 362 | }
|
---|
| 363 |
|
---|
| 364 | free (node);
|
---|
| 365 |
|
---|
| 366 | *traverser = NULL;
|
---|
| 367 |
|
---|
| 368 | context->size--;
|
---|
| 369 |
|
---|
| 370 | if (CF_List_GetSize (ctx) == 0)
|
---|
| 371 | context->front = context->rear = NULL;
|
---|
| 372 |
|
---|
| 373 | return CF_OK;
|
---|
| 374 | }
|
---|
| 375 |
|
---|
| 376 | /**
|
---|
| 377 | * 리스트에서 모든 항목을 삭제
|
---|
| 378 | *
|
---|
[119] | 379 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
[109] | 380 | *
|
---|
[119] | 381 | * \param ctx 리스트 컨텍스트
|
---|
[109] | 382 | */
|
---|
| 383 | int
|
---|
[151] | 384 | CF_List_RemoveAll (cf_ctx ctx)
|
---|
[109] | 385 | {
|
---|
[151] | 386 | cf_traverser traverser = NULL;
|
---|
[109] | 387 |
|
---|
| 388 | ASSERT_CTX (ctx);
|
---|
| 389 |
|
---|
| 390 | while (CF_List_GetSize (ctx) > 0)
|
---|
| 391 | {
|
---|
| 392 | CF_List_Front (ctx, &traverser);
|
---|
| 393 | CF_List_Remove (ctx, &traverser);
|
---|
| 394 | }
|
---|
| 395 |
|
---|
| 396 | return CF_OK;
|
---|
| 397 | }
|
---|
| 398 |
|
---|
| 399 | /**
|
---|
| 400 | * 탐색자 위치를 이전으로 이동
|
---|
| 401 | *
|
---|
[119] | 402 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
[109] | 403 | *
|
---|
[119] | 404 | * \param traverser 리스트 탐색자 주소
|
---|
[109] | 405 | */
|
---|
| 406 | int
|
---|
[151] | 407 | CF_List_Prev (cf_traverser * traverser)
|
---|
[109] | 408 | {
|
---|
| 409 | CF_NODE * node = (CF_NODE *) *traverser;
|
---|
| 410 |
|
---|
| 411 | ASSERT_TRAVERSER (traverser);
|
---|
| 412 | ASSERT_ARGS (*traverser == NULL);
|
---|
| 413 |
|
---|
| 414 | node = node->prev;
|
---|
[151] | 415 | *traverser = (cf_traverser *) node;
|
---|
[109] | 416 | if (node == NULL)
|
---|
| 417 | return CF_ERROR_DS_NO_MORE;
|
---|
| 418 |
|
---|
| 419 | return CF_OK;
|
---|
| 420 | }
|
---|
| 421 |
|
---|
| 422 | /**
|
---|
| 423 | * 탐색자 위치를 다음으로 이동
|
---|
| 424 | *
|
---|
[119] | 425 | * \return 성공 시, CF_OK; 실패 시, 오류 코드
|
---|
[109] | 426 | *
|
---|
[119] | 427 | * \param traverser 리스트 탐색자 주소
|
---|
[109] | 428 | */
|
---|
| 429 | int
|
---|
[151] | 430 | CF_List_Next (cf_traverser * traverser)
|
---|
[109] | 431 | {
|
---|
| 432 | CF_NODE * node = (CF_NODE *) *traverser;
|
---|
| 433 |
|
---|
| 434 | ASSERT_TRAVERSER (traverser);
|
---|
| 435 | ASSERT_ARGS (*traverser == NULL);
|
---|
| 436 |
|
---|
| 437 | node = node->next;
|
---|
[151] | 438 | *traverser = (cf_traverser *) node;
|
---|
[109] | 439 | if (node == NULL)
|
---|
| 440 | return CF_ERROR_DS_NO_MORE;
|
---|
| 441 |
|
---|
| 442 | return CF_OK;
|
---|
| 443 | }
|
---|
| 444 |
|
---|
| 445 | /**
|
---|
| 446 | * 리스트에 등록된 항목의 수를 가져옴
|
---|
| 447 | *
|
---|
[119] | 448 | * \return 성공 시, 항목 수; 실패 시, 오류 코드
|
---|
[109] | 449 | *
|
---|
[119] | 450 | * \param ctx 리스트 컨텍스트
|
---|
[109] | 451 | */
|
---|
| 452 | int
|
---|
[151] | 453 | CF_List_GetSize (cf_ctx ctx)
|
---|
[109] | 454 | {
|
---|
[149] | 455 | CF_LIST_CONTEXT * context = (CF_LIST_CONTEXT *) ctx;
|
---|
[109] | 456 |
|
---|
| 457 | ASSERT_CTX (ctx);
|
---|
| 458 |
|
---|
| 459 | return context->size;
|
---|
| 460 | }
|
---|