[TIL][Sat] 구조체 / 포인터 / 동적 메모리 할당

구조체 structure

a user-defined data type that allows you to group together different types of variables under a single name.

하나의 이름 하에 다양한 타입의 변수들을 함께 묶어 사용하기 위해 유저가 정의한 데이터 타입

//Red-Black Tree Node를 위한 구조체 코드

enum Color { RED, BLACK };

struct Node {
    int data;
    enum Color color;
    struct Node* parent;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->color = RED; // New nodes are initially red
    newNode->parent = NULL;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    // Example usage of creating a red-black tree node
    struct Node* newNode = createNode(10);

    // Access and use the node members
    printf("Node data: %d, Color: %s\\n", newNode->data, newNode->color == RED ? "RED" : "BLACK");

    return 0;
}

• struct Node* createNode(int data) 에서 struct Node* 는 이 함수가 반환하는 타입이 Node 구조체의 포인터, 즉 Node 구조체의 주소라는 뜻.
• 포인터와 malloc을 사용하여, 이 함수는 선언 시 새로운 노드에 대한 데이터를 동적으로 할당한다. 포인터는 노드의 수가 수시로 바뀔 수 있는 트리 같은 자료구조에서 메모리의 동적 할당을 위해선 필수적이다.

malloc

(struct Node*)malloc(sizeof(struct Node));

1. Node 구조체에 메모리를 할당한다.
2. malloc 함수는 할당된 메모리를 반환하는데, 기본 타입은 void* 이다.
3. 그런데 이 앞에 (struct Node*) 가 이 기본 타입인 void를 포인터 타입 struct Node로 명시적으로 선언하기 때문에 이 결과물의 타입은 struct Node* 가 된다. 즉, Node 구조체가 가리키는 주소(메모리)가 이것의 타입이 된다.

포인터 pointer

선언과 초기화

int* ptr=null;
*ptr = &myVar; #myVar의 주소를 가리킨다.

역참조

• 포인터를 역참조한다는 뜻은 그 포인터가 가리키는 값에 접근한다는 뜻이다.
  • 연산자를 활용.

포인터 연산

• 데이터 타입의 크기라는 관점에서 연산이 이루어진다.
• ex: ptr이 정수형 포인터라면, ptr++는 ptr을 메모리의 다음 정수로 이동시킨다.

동적 메모리 할당

c 기본 라이브러리인 <stdlib.h> 헤더에서 제공되는 함수로 수행된다. 이 기능으로 인하여 배열과 같은 자료구조의 크기를 컴파일 당시에 반드시 알아야만 하는 정적 메모리 할당과는 반대로 프로그램이 실행될 때 메모리를 동적으로 할당할 수 있게 된다.

포인터의 역할

포인터는 다른 변수의 주소를 저장하는 변수로 메모리 블록을 참조하는 용도로 동적 메모리 할당에 필요하다.

Dangling Pointer

메모리 할당이 해제된 메모리 장소를 가리키는 포인터. 포인터가 역참조될 때 undefined behavior로 이어질 수 있다.

배열과 포인터

배열의 구현방법과 메모리 접근 방식 때문에 밀접한 관련이 있다.

배열 저장

배열의 요소는 메모리상에서 틈(gap)없이 바로 다음으로 저장된다. 즉, 배열 하나가 선언될 때 단일의 깨지지 않는 메모리의 영역이 그 원소들을 붙잡고 있기 위해 할당되는 것이다. 이 연속된 메모리 할당은 개당 원소의 사이즈에 따라 메모리 주소를 증가시켜 쉽게 이동할 수 있기 때문에 배열의 인덱싱과 반복을 가능하게 만든다.

따라서, 때로 배열의 이름은 배열의 첫번째 요소(array[0])에 대한 constant pointer처럼 사용될 수 있다.

포인터 연산

포인터에 1을 더하는 건 이 타입의 다음 요소로 포인터를 이동한단 뜻과 같다. 만약 하나의 배열을 가리키는 포인터가 있다면, 포인터를 증가시킴으로서 배열을 순회할 수 있다.

arr = {1,2,3,4,5};

*arr+1 == 2 
//쉽게 생각해서 *가 붙는다면 *가 붙는 포인터가 
// 가리키고 있는 value를 가져온다고 생각하자!

arr == &arr[0]

• arr arr 자체는 배열 전체를 의미하지만, 대부분의 표현에서는'int *' 타입의 배열의 첫번째 요소를 가리키는 포인터로 자동적으로 변환된다.
• &arr[0] 배열의 첫번째 요소의 주소를 명시적으로 가져오며, 이것 또한 배열의 첫번째 요소를 가리키는 포인터이다. 따라서 이 두 표현은 같은 효과를 지닌다: 배열 arr의 첫번째 요소의 메모리 주소를 제공한다.

포인터 연산 코드 : %p 와 casting [wrong]

#include <stdio.h>

int main(void){

    int arr [] ={ 1,2,3,4,5,6};

    printf("arr: %p\\n", (void*)arr);
    printf("*arr: %p\\n", (void*)*arr);
    printf("arr+5: %p\\n", (void*)arr+5);
    printf("*arr+5: %p\\n", (void*)*arr+5);
    printf("*(arr+5): %p\\n", (void*)*(arr+5));

    return 0;
}

$ ./"pinter_target.exe"
arr: 000000000061FE00
*arr: 0000000000000001 #1
arr+5: 000000000061FE05
*arr+5: 0000000000000006 #2
*(arr+5): 0000000000000006 #3

//cast to pointer from integer of different size (in #)

//#1
// *arr 는 arr를 역참조하고 있으므로 배열의 첫번째 요소인 정수를 가져온다. 
//이럴 경우 정수값을 포인터에 casting하는 것이 되고 마는데 이래선 안 된다. 
//따라서 casting 없이 integer로 print해야한다. 

//#2 
//마찬가지로 *arr는 arr를 역참조하고있으므로 1을 반환, 
//여기에 5를 더하므로 정수값을 가져온다. 
//포인터에 이 정수값을 cast하면 안되므로 integer로 print한다. 

//#3
// arr+5는 배열의 5번째 위치(주소)를 나타내고, 
//이를 * 로 역참조하므로 *(arr+5)는 정수값을 가져오고 
//이를 ppointer에 cast할 수 없다. 따라소 정수 integer로 print해야 한다.

코드[수정]

#include <stdio.h>

int main(void){

    int arr [] ={ 1,2,3,4,5,6};

    printf("arr: %p\\n", (void*)arr);
    printf("*arr: %d\\n", *arr);
    printf("arr+5: %p\\n", (void*)(arr+5));
    printf("*arr+5: %d\\n", *arr+5);
    printf("*(arr+5): %d\\n", *(arr+5));

    return 0;
}

$ ./"pinter_target.exe"
arr: 000000000061FE00
*arr: 1
arr+5: 000000000061FE14
*arr+5: 6
*(arr+5): 6

인덱싱

어떤 요소에 접근하기 위해 인덱스를 사용할 때 다음이 성립한다.

arr[index] == *(arr+index)

이 표현은 요소의 메모리 주소를 찾기 위해 시행하는 포인터의 산술연산에 사용되며 value를 찾기 위해 역참조할 때 사용된다.

배열이 포인터로 변함

어떤 배열을 어떤 함수에 전달할 때 사실 실재로 전달되는 건 배열의 첫번째 원소를 가리키는 포인터이다. 이때 배열은 포인터로 변한다.(The array "decays" into a pointer.)

왜?

• 효율성: 배열 탐색에 포인터 사용하기는 메모리에 직접 접근하기 위한 저레벨의 효과적은 기법이다. 다른 추상적인 추가적인 레이어 없이 직접 메모리에 접근하기 때문에 다른 기법보다 빠르다.

포인터와 함수 pointer & function

function pointers

함수의 주소를 저장하는 포인터 변수. 나중에 이 함수를 부를 때 이 포인터를 사용함.

함수에 포인터 전달하기(Passing Pointers to Functions)

• by Value: 값으로 전달된 포인터는 이 함수가 주소가 있는 장소에 직접 저장해 값을 수정할 수 있도록 하지만 주소 자체는 수정하지 못한다.
• by Refrence 참조에 의한(혹은 포인터의 주소에 의한) 포인터 전달하기는 포인터 그 자체를 수정할 수 있게 허락한다.

함수에게 포인터를 반환받기(Returning Pointers from Functions)

• 누수를 막기 위한 조치로 동적 메모리 할당에서 특히 포인터를 반환할 수 있다.
• 포인터가 자동으로 로컬 변수에 반환되지 않도록 주의해야 함.

* [!!] returning a pointer to a local variable

• problems

  //INCORRECT CODE returns a pointer to an automatic local variable:
  #include <stdio.h>
  
  int* dangerousFunction() {
      int localValue = 42;  // Local variable with automatic storage duration
      return &localValue;   // This is dangerous: returning the address of a local variable
  }
  
  int main() {
      int *intPointer = dangerousFunction();
      // The function has returned, localValue no longer exists,
      // intPointer is now dangling - using it can cause undefined behavior
      printf("%d\\n", *intPointer); // This may print garbage value or cause a crash
      return 0;
  }

• 지역변수는 그것을 에워싸는 블록(enclosing block, 아마도 스택 프레임을 뜻하는 듯)이 시작될 때 자동으로 할당되고 그 블록이 종료되면 자동으로 할당이 해제된다. 이 부분에서 ‘automatic local variable’을 가리키는 포인터를 반환하는 것에서 문제가 발생하는데, 왜냐하면 이 변수는 함수가 반환된 후에는 더 이상 존재하지 않기 때문이다! 따라서 포인터는 dangling 되거나 메모리상에서 명시되지 않은 장소를 가리키게 되어 버린다.
• solution

반환된 포인터가 가리키는 데이터가 함수 종료 후에도 살아있게끔 만들어야 함. 두 가지 방식으로 가능하다.

1. malloc()이나 다른 관련 함수를 이용하여 힙에 데이터를 동적으로 할당하여 올려놓는 방법. 이 방법은 free()로 명시적으로 할당 해제할 때까지 유지된다.
2. 프로그램이 살아있는 동안 유지되는 정적 로컬 변수를 사용하는 방법. 이 경우 thread-safe하지 않을 수 있으므로 고려가 필요함.

3. #include <stdio.h>
   #include <stdlib.h>
   
   int* safeFunction() {
       int* heapValue = malloc(sizeof(int)); // Dynamically allocated memory
       *heapValue = 42;
       return heapValue;  // Safe: heapValue points to memory on the heap
   }
   
   int main() {
       int *intPointer = safeFunction();
       // intPointer is not dangling, and the pointed-to value is valid
       printf("%d\\n", *intPointer); // Correctly prints the value 42
       free(intPointer); // Remember to free the allocated memory
       return 0;
   }

배열과 포인터

• 첫번째 원소를 포인터로 삼아 함수에 전달된다.
• 함수는 포인터를 통해 배열의 내용물을 수정할 수 있음.

이중포인터(Pointers to Pointers)

• 전달받은 포인터 수정을 함수가 할 수 있도록 허락함.
• 문자열의 배열 혹은 동적 배열을 다루기 위해 사용됨.

함수에서의 포인터 연산(Pointer Arithmetic in Functions)

• Incrementing and decrementing pointers.
• Adding or subtracting integers to/from pointers.

인수로서의 함수에 대한 포인터(Pointers to Functions as Arguments)

• Functions can accept function pointers as parameters, allowing for flexible calling of passed-in functions.

함수 포인터의 배열(Arrays of Function Pointers)

• Implementing simple polymorphism.
• Creating lookup tables for functions.

void pointer

• 어떤 타입의 함수던 가리킬 수 있지만 직접적인 역참조를 할 수 없다.(Can point to a function of any type but cannot be dereferenced directly.)

null 포인터

메모리 주소를 가리키지 않는 포인터인데, 다른 의미있는 무언가를 가리키지 않는 포인터임을 알리기 위해 사용된다.

특정 주소를 아직 할당하지 않을 때 포인터를 null로 초기화하는 것이 좋다.

pointer to pointer

이중 간접 사용(multiple indirection)의 형태로 포인터의 연쇄를 뜻한다. (**) 로 사용함. 함수 안에서 포인터를 수정할 때나 포인터의 동적 배열을 다룰 때 사용한다.

#include <stdio.h>

void initPointer(int **pp) {
    int *p = (int*)malloc(sizeof(int));
    *p = 10;
    *pp = p;
}

int main() {
    int *ptr = NULL;
    initPointer(&ptr);
    printf("%d\\n", *ptr);
    free(ptr);
    return 0;
}

포인터와 자료구조

포인터는 동적으로 메모리를 할당하고 요소 간을 탐색하며 데이터를 효율적으로 처리하기 위해 데이터 구조와 함께 광범위하게 사용된다. 연결리스트나 트리, 그래프와 같은 제각각의 요소들이 다른 요소들과 동적인 연결이 필요한 복잡한 데이터 구조에서 사용될 수 있다.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node* createNode(int data) {
    Node *newNode = malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int main() {
    Node *head = createNode(1);
    head->next = createNode(2);
    
    Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\\n");
    
    // Free the allocated memory
    while (head != NULL) {
        Node *temp = head;
        head = head->next;
        free(temp);
    }
    
    return 0;
}

포인터 보안 Pointer Safety

포인터가 유효한 메모리 공간을 가리키고 있는지.

안전하지 않은 포인터는 분할 오류, 메모리 누수나 기타 취약성을 초래할 수 있다. 경계 검사, 적절한 초기화 및 세심한 메모리 관리와 같은 기술이 필수적이다.

• null check

• #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  
  int main() {
      size_t size = 10;
      char *safeString = malloc(size);
      if (safeString != NULL) {
          strncpy(safeString, "SafeString", size - 1);
          safeString[size - 1] = '\\0'; // Ensuring the string is null-terminated
      }
      printf("%s\\n", safeString);
      free(safeString);
      return 0;
  }

타입 캐스팅

Type casting with pointers is used to treat a block of memory as a different type than it was originally allocated for.

메모리 블록을 원래 그것이 할당된 것과 다른 유형으로 취급할 때 사용된다.

This is particularly useful when dealing with generic data structures and functions that operate on void * pointers. Type casting allows for the interpretation of the memory block in the required format.

#include <stdio.h>

int main() {
    int a = 10;
    void *vptr = &a;
    int *iptr = (int *)vptr; // Casting void pointer to int pointer
    printf("%d\\n", *iptr);
    return 0;
}

함수 포인터(함수를 가리키는 포인터)

함수 포인터는 변수에 함수를 할당하고 다른 함수에 전달하거나 다른 함수로부터 반환할 수 있게 한다.

이는 C 언어에서 고차 함수(higher-order functions)를 다룰 수 있는 기본적인 구성 요소이며, 콜백 함수(callback functions), 이벤트 핸들러(event handlers), 인터페이스 구현(interface implementations)과 같은 시나리오에서 널리 사용된다.

동적 메모리 할당

메모리 관리

heap (heap vs stack)

동적 메모리 할당에 사용되는 메모리 영역이며 메모리 블록이 할당되는 구역이며 임의의 순서로 해제되는 영역이다. 힙은 스택과 다른데, 스택은 정적 메모리 할당과 함수 파라미터, 지역변수, 그리고 함수 콜이 저장되는 점에서 다르다.

힙의 메모리를 할당할 수 있고, 이 메모리는 free로 해제되거나 프로그램이 끝날때까지 할당을 유지한다.

	heap	stack
	동적 메모리 할당에 사용됨	정적 메모리 할당
		함수 파라미터, 지역변수, 함수 콜

• visual representation of the heap (by ChatGPT)

For a visual representation of the heap, you can imagine a big chunk of space where blocks of memory can be allocated and freed in any order. The visual representation would not be structured like an array; it would be more like various-sized blocks that can fit wherever there is space for them.

메모리 누수Memory Leaks

• free되지 않았을 때 발생

Dangling Pointers

• 메모리 할당이 해제된 메모리 장소를 가리키는 포인터. 포인터가 역참조될 때 undefined behavior로 이어질 수 있다.

Memory Corruption 메모리 오염

• 프로그램이 메모리 할당을 잘못 관리하여 자신의 데이터를 덮어쓸 가능성이 있을 때 발생한다.

Memory Fragmentation 메모리 조각화

Over time, the heap can become fragmented with blocks of free memory interspersed with allocated blocks, which can lead to inefficient use of memory and allocation failures.

함수

sizeof

sizeof

선언된 타입이나 변수의 사이즈를 bytes단위로 정하기 위해 사용되는 연산자이다. 어떤 특정 데이터 타입에 메모리를 얼마나 할당 해야 할지 알아야 하는 메모리 할당에 유용하다.

1. 단일 변수/ 기본 데이터 타입/ 기본 데이터 타입의 배열/ 단일 구조체 / 구조체의 배열에 메모리 할당

   1. //단일 변수
      int *p = (int*)malloc(sizeof(int)); 
      // Allocate memory for one int
      
      //기본 데이터 타입의 배열
      int *array = (int*)malloc(10 * sizeof(int)); 
      // Allocate memory for an array of 10 ints
      
      //단일 구조체
      typedef struct {
          int a;
          double b;
      } MyStruct;
      MyStruct *s = (MyStruct*)malloc(sizeof(MyStruct)); 
      // Allocate memory for one MyStruct
      
      //구조체 배열
      MyStruct *array_of_structs = (MyStruct*)malloc(10 * sizeof(MyStruct)); 
      // Allocate memory for an array of 10 MyStructs

2. 존재하는 단일 변수 / 단일 포인터의 크기 측정

3. MyStruct s;
   MyStruct *ps = (MyStruct*)malloc(sizeof(s)); // Allocate memory the size of s
   
   int *ptr;
   size_t size = sizeof(ptr); // Size of the pointer, not the int it may point to
   

4. calloc 과 realloc 에서 사용: 각 원소 혹은 메모리 블록의 새로운 사이즈의 사이즈를 측정하기 위해 쓸 수 있음.

   int *array = (int*)calloc(10, sizeof(int)); // Allocate and zero-initialize an array of 10 ints
   array = (int*)realloc(array, 20 * sizeof(int)); // Resize the array to 20 ints
   ​

 

size_t

어떤 대상의 사이즈를 나타내는 데이터 타입으로 unsigned integer type이다. 즉, non-negative한 값만 나타낼 수 있다는 뜻. 주로 sizeof 연산에 대한 반환값의 타입으로 사용되는데 object의 크기는 bytes에서 절대 음수로 나올 수 없기 때문이다.

size_t 는 배열 인덱싱이나 루프 카운팅, 그리고 크기를 받거나 리턴하는 메모리 할당과 문자열 조작에 대한 기본 라이브러리 기능에 특히 많이 사용된다. 왜냐하면 는 가장 큰 가능한 대상의 크기를 포함하는 것을 보장할 수 있 때문이다. (This is because size_t is guaranteed to be big enough to contain the size of the largest possible object on your platform (e.g., the maximum array size).)

size_t size = sizeof(int); // Stores the size of an integer in bytes
//In this example, size will typically be 4 on many modern systems, 
//because an int is commonly 4 bytes in size. on a 64-bit system, 
//it is typically a 64-bit unsigned integer.

malloc(size_t size)

memory allocation ⇒ malloc

https://youtu.be/SuBch2MZpZM?si=z_uj6ymTuEpGNQmy

 

• 초기화되지 않는 메모리
• null pointer

특정한 사이즈(bytes)의 메모리 블록을 할당하고 블록의 시작점을 가리키는 *void 타입의 포인터를 반환한다. *void 타입은 어떤 형태의 포인트로 cast가 가능하다. 메모리는 초기화되지 않는데, 이는 쓰레기 값을 갖고 있음을 뜻한다.

int *ptr = (int*)malloc(10 * sizeof(int)); 
// Allocates space for an array of 10 integers.

calloc(size_t num, size_t size)

contiguous allocation ⇒ calloc

• 0 초기화
• 배열 할당

calloc은 원소들을 가진 하나의 배열에 대한 메모리를 할당하고 이 할당한 메모리를 가리키는 포인터를 반환한다. 이 배열의 원소들은 각각이 ${size} bytes 의 길이를 가졌으며, 모든 bits가 0으로 초기화된다.

//prototype for 'calloc' func
void *calloc(size_t num_elements, size_t element_size);

int *ptr = (int*)calloc(10, sizeof(int)); 
// Allocates and zeros an array of 10 integers.
// 10: 공간을 할당할 정수 요소의 갯수를 나타냄.
// sizeof(int) 각 정수의 크기를 나타

• num_elements: 할당하고자 하는 요소의 갯수 The number of elements you want to allocate.
• element_size: 각 요소의 bytes 사이즈 The size of each element in bytes.

	malloc	calloc
[!!] argument	할당할 크기 전부의 크기	원소의 갯수와 각 원소의 갯수
allocates..	a single block of memory(단일 메모리 블록)	memory for an array of elements and initializes all bytes in the allocated space to zero(할당된 공간의 bytes를 모두 0으로 초기화 한 배열) It initializes the allocated memory to zero.
returns..	할당된 메모리를 가리키는 void* 타입의 포인터를 반환하는데, malloc도 요청한 메모리를 할당하는 데 실패하면 NULL을 반환한다.	calloc then returns a pointer to the allocated memory, which is suitably aligned for any kind of variable, or NULL if the allocation fails. (모든 종류의 변수에 적합하게 정렬된 할당된 메모리를 가리키는 포인터를 반환하는데, 만약 할당이 실패하면 NULL을 반환한다.)

 

*realloc(void ptr, size_t new_size)

• 할당된 메모리의 크기를 증감한다
• 이동할 경우 기존의 크기와 새 크기의 최소 크기까지 원본 새 장소로 복사된다.

이전에 malloc이나 calloc이 할당한 ptr이 가리키는 메모리 블록의 크기를 재정의한다. 만약 메모리 블록의 크기가 커진다면 새로 증가한 부분은 초기화되지 않는다.

int *ptr = (int*)malloc(10 * sizeof(int)); // Allocation
ptr = (int*)realloc(ptr, 20 * sizeof(int)); 
// Resizes the previous array to 20 integers.

Free(void free(void ptr))*

• 메모리 누수 방지
• 중복 해방 금지(doble free - x)

이전에 할당된 메모리 블록의 할당을 해제한다. 할당 후 dangling pointer를 막기 위해 NULL로 포인터를 세팅하는 게 좋다.

free(ptr);
ptr = NULL;

포인터 연산

• 포인터 더하기 (앞으로 이동)
• 포인터에서 빼기 (뒤로 이동)
• 포인터와의 차이점

메모리 할당 실패

• NULL 포인터 다루기
• global variable Errno

할당 전략

• Best Fit
• Worst Fit
• First Fit