[CS50] week 4 - Memory

初めに

Memo

• 文字列・配列（数字／文字）：
  • 文字列（String、一連のメモリ空間を通りして表現する文字データ）を変数に貯蔵するというのは、初めのバイトのメモリアドレスを保存すること。（コンパイルでは文字列なら必ず\0（nul文字）で終わる。）
  • 数字の配列は、初期化では足りない要素は0が補填されるが最後尾には何も入れられない。（int型の0で補填する。(void *)0（null pointer constant、ヌルポインタ定数）、別名としてよく使われる大文字のNULLではない。）

（自分へのメモ：グローバル変数でもstatic静的変数でもない配列の生存期間が静的記憶域期間か、それとも自動的記憶域期間か、投稿する時点ではまだわかりません。）

---

• pass by value：int、charなどプリミティブ（Primitive）型変数の代入式や、関数の受け渡しするとき変数の値をコピーして使うこと。（引数である変数から値をコピーして、関数の仮引数へ代入する）

• pass by sharing：ポインタ変数の代入式や、関数の受け渡しにメモリアドレスを渡すこと。（渡されたアドレスにアクセスして、中に保存されている値を操作することができる）

---

• メモリとポインタ：
  • メモリアドレスの保存はマップの保存と同じ概念です。
  • 配列のメモリアドレスの保存は初めのバイトのメモリアドレスを保存する。
  • ポインタ変数はあるメモリアドレスを占めてほかの変数のメモリアドレスを格納する。
  • ポインタはメモリアドレスを格納／保持／保存／記憶することで、それをたどってアドレスにある値をアクセスすることができる。
  • ポインタの加減算はメモリアドレスに格納される値の型のサイズ分で、アドレスサイズへの増加、減少をする。（char *なら1バイト、int *なら4バイトなど。）

（ポインタがアドレスを格納することと、参照時に格納されたアドレスに辿ってそこに保存されている値をアクセスすることを、別々に分けて考えると分かりやすくなると思います。）

• ダブルポインタ：

---

• ヌルポインタ（null pointer）：
  • 型（int、char、double...）ごとにヌルポインタが存在する。例えば(void *) 0はvoid型ポインタのヌルポインタ、(int *) 0はint型ポインタのヌルポインタ。
  • void型ポインタのヌルポインタ(void *) 0は汎用ポインタで、代入式によってあらゆるポインタ型のヌルポインタに変換できる。

---

• ヌルポインタ定数（null pointer constant）：
  • ヌルポインタ定数（null pointer constant）は演算結果が0に評価される整数定数式 （代入式）（コメントにより不適切な表現を削除します） のことです。例えば、
    • 0（int 0）
    • 0L（long 0）
    • 0ULL（unsigned long long 0）
    • (void *) 0（type void pointer 0）
    • (void *) 0U（type void pointer unsigned 0）など。

---

• NULL：
  • NULLはヌルポインタ定数（null pointer constant）として、整数0や(void *) 0などの別名でマクロ定義されている。
  • NULLが(void *) 0で定義されるとき、整数0ではないが代入式によってほかのデータ型に暗黙に変換することができる。つまり整数0と等価です。
  • NULLが整数0で定義されるとき、整数型としてのヌルポインタです。
  • NULLはどちらで定義されてもヌルポインタ定数として代入式によって最終的に整数0に変換される。
  • NULLは最終的に整数0に変換される保証はできる（ヌルポインタになる）が、ヌルポインタはNULL以外の可能性がある。（0Lなど）

（自分の感覚ではNULLが(void *)0として定義されると柔軟に型変換できて便利だけど、色々と意味が曖昧過ぎてすべての型をカバーできないし、0として定義されると明示的に型キャストしなきゃいけないのはむしろ分かりやすい。）

stddef.h

# define NULL ((void *) 0) // Macro definition
// or
# define NULL 0 // Macro definition

// Valid
// when NULL is defined by ((void *) 0)
// it will covert to any type pointer with assignment expression
FILE *fp = NULL; // implicit type conversion

// when NULL is defined by 0
printf("%p", (void *)0);
printf("%p", (void *)NULL);

// OK in C
int *a = 0;
// null pointer constant, it will convert to int type pointer

int *b = (int *) 0;
// int type null pointer

// OK in C, Not OK in C++
int *c = (void *) 0;
// null pointer constant, it will convert to int type pointer

// malloc() return void* => implicit type conversion => int*
int *iPtr = malloc(1000 * sizeof(int));

// explicit casting
int *iPtr = (int *)malloc(1000 * sizeof(int));

---

• 記憶域期間（ストレージ期間、storage duration）：
  • ライフタイム（Lifetime）／生存期間などと同義。
  • 静的記憶域期間（Static storage duration）
    • 生存期間はプログラムの開始から終了まで。例えば、
      • グローバル変数
      • staticで静的に宣言された変数（グローバルとローカル同様）
      • 宣言のみで初期化されてない変数はint型なら(int)0で自動的に初期化される。
      • 宣言のみで初期化されてないポインタはNULL（(void *)0）で自動的に初期化される。
  • 自動的記憶域期間（Automatic storage duration）
    • 宣言されたブロック範囲内だけ生存する。範囲外になると消滅する。
    • 変数に明示的に値をアサインするまで初期化されない。
  • 動的記憶域期間（動的割り付け記憶域期間、Dynamic storage duration）
    • malloc()などで動的メモリ割り当てて保存し、free()で解放されるまで続く。

（静的ストレージはプログラムの開始から終了までずっと生きる変数、動的ストレージは必要なとき関数によってメモリ割り当てて何らかの処理が終わると使っていたメモリ解放する。自動的ストレージは関数の呼び出しごとに生存と破棄が繰り返されるローカル変数（自動変数）、実行からreturnまでが生存期間、終了したらメモリが自動的に解放される。）

// Static storage duration // global variable
int num = 2;
int main(void)
{
  num++;
  printf("%d\n", num); // 3
  num++;
  printf("%d\n", num); // 4
  return 0;
}

// Static storage duration // static variable
void staticVariableIncrement(void)
{
  static int num = 2;
  num++;
  printf("Num is %d\n", num);
}

void normalVariableIncrement(void)
{
  int num = 2;
  num++;
  printf("Num is %d\n", num);
}

int main(void)
{
  staticVariableIncrement(); // Num is 3
  staticVariableIncrement(); // Num is 4

  normalVariableIncrement(); // Num is 3
  normalVariableIncrement(); // Num is 3
  return 0;
}

// global variable // file scope
int globalX = 1; // Static storage duration

void func(void)
{
  // local variable // block scope
  static int staticX = 2; // Static storage duration
  int funcX = 3;          // Automatic storage duration
}

int main(void)
{
  // local variable // block scope
  int mainX = 4; // Automatic storage duration
  {
    // local variable // block scope
    int blockX = 5; // Automatic storage duration
  }
  return 0;
}

---

• スコープ

---

• 十六進法（Hexadecimal）
  • 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f全16個。
  • 1 バイト（8 bits）での2進数の可読性を高めるために、8 bitsを 4 bitsずつ分けて16進数で表示する。例えば1111 1111⇒ff（0xff）、1101 1000⇒d8（0xd8）。
  • ほとんどのJPEG画像データが255, 216, 255⇒ff d8 ff (or 0xff, 0xd8, 0xff)というパターンから始まり、ff d9で終わる。
  • 0x自体は16進数の表記方法なだけで特に意味ない。後ろから桁によって16^1、16^0などで10進数に変換することができる。例えば0xffは15 * 16^1 + 15 * 16^0 = 256、つまり第256番目の意味で、RGBの表記範囲0-255では255として表している。（0もカウントされて全部256個あります。）

---

Practices

ここからのデモモードは映像から取り上げて練習のつもりで書いたものです。（一部改変あり）
誤解を招いてしまったり、至らなかったところがあればご容赦ください。

Compare

#include <stdio.h>
#include <string.h>

int main(void)
{
  printf("string 1: ");
  char str1[10];
  scanf("%s", str1);

  printf("string 2: ");
  char str2[10];
  scanf("%s", str2);

  // if (strcmp(str1, str2) == 0)
  // {
  //   printf("two strings are same\n");
  // }
  // else
  // {
  //   printf("two strings are different\n");
  // }

  for (int i = 0, length = strlen(str1); i < length; i++)
  {
    if (str1[i] != str2[i])
    {
      printf("two strings are different\n");
      return 1;
    }
  }
  printf("two strings are same\n");

  return 0;
}

@taqu さんからのご指摘により、
下の例は長さのチェックも入れるように編集しました。

#include <stdio.h>
#include <string.h>

int main(void)
{
  printf("string 1: ");
  char str1[10];
  scanf("%s", str1);

  printf("string 2: ");
  char str2[10];
  scanf("%s", str2);

  if (strlen(str1) != strlen(str2))
  {
    printf("two strings are different\n");
    return 1;
  }

  for (int i = 0, length = strlen(str1); i < length; i++)
  {
    if (str1[i] != str2[i])
    {
      printf("two strings are different\n");
      return 1;
    }
  }
  printf("two strings are same\n");

  return 0;
}

Copy

#include <stdio.h>
#include <stdlib.h> // malloc()
#include <string.h> // strlen()
#include <ctype.h>  // toupper()
#include <cs50.h>   // get_string()
// #define arrSize(x) (sizeof(x) / sizeof((x)[0])) // x can't be pointer

int main(void)
{
  char *str1 = get_string("string 1: ");

  // char array ended with '\0', remember to plus 1
  char *str2 = malloc((strlen(str1) + 1) * sizeof(char));

  // sanity check
  if (str1 == NULL || str2 == NULL)
  {
    return 1;
  }

  // copy value // pass by value
  // i <= length // copy str1's value up through '\0' byte
  for (int i = 0, length = strlen(str1); i <= length; i++)
  {
    str2[i] = str1[i];
  }
  printf("str1 is %s, str2 is %s\n", str1, str2);

  if (strlen(str2) > 0)
  {
    str2[0] = toupper(str2[0]);
  }
  printf("str1 is %s, str2 is %s\n", str1, str2);

  // str2 is dynamic storage duration
  free(str2);
  return 0;
}

// string 1: aaa
// str1 is aaa, str2 is aaa
// str1 is aaa, str2 is Aaa

Swap

#include <stdio.h>

void swap(int *a, int *b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int main(void)
{
  int x = 1;
  int y = 2;

  printf("x is %d, y is %d\n", x, y);
  // &: dereference operator // assign address
  swap(&x, &y); // pass by sharing memory address
  printf("x is %d, y is %d\n", x, y);

  return 0;
}
// x is 1, y is 2
// x is 2, y is 1

Pointer arithmetic

#include <stdio.h>
#include <string.h>
#include <cs50.h>

int main(void)
{
  char *str1 = get_string("string: ");
  if (str1 == NULL)
  {
    return 1;
  }

  for (int i = 0, length = strlen(str1); i < length; i++)
  {
    // pointer* store the first byte of address
    // when i++, it will jump to next byte of address
    // *(str1 + i) == str1[i]
    printf("%c\n", *(str1 + i));
  }

  return 0;
}
// string: abc
// a
// b
// c

Pointer Gotchas, pointer & pointee

pointer & pointee

• pointer：ポインタ変数自身。
• pointee：ポインタ変数が保存するアドレス。
  この二つの関係性は映像では非常に分かりやすく説明されています。

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

int main(void)
{
  int *x;
  int *y;

  x = malloc(sizeof(int));
  *x = 42; // valid
  // *y = 13; // invalid

  y = x;
  *y = 13;
  printf("x is %p, y is %p\n", x, y);
  printf("access the address inside x, will find %d\n", *x);
  printf("access the address inside y, will find %d\n", *y);
  return 0;
}
// x is 0x55f1a69442a0, y is 0x55f1a69442a0
// access the address inside x, will find 13
// access the address inside y, will find 13

• int *x;
  • int *：整数型ポインタ
  • int *x;：整数型ポインタ変数x
  • xに入れられる値はメモリアドレス。
  • *xに入れられるのはそのアドレスに保存できる値（ここでは整数型）。
  • xが初期化されていない（確保されたアドレスを配っていない）ままで*xへアクセスして値を代入するなどの操作が不適切です。

（自分的には、*x = 42;はアサイン（assign）というより、*（dereference operator）によってxに保存されているメモリアドレスへ値を運ぶ・入れるほうがグッときます。）

（そして前のvoid swap(int *a, int *b)のように、関数の呼び出しごとに自動的記憶域が得られるから、先に確保されたアドレスを配らなくても特に問題がなさそうに見えますが、投稿時にまだよくわからないです。）

Pointer rules

ポインタのルールに気になって調べた文章一部の例を使用しています。映像の例ではない。

int main(void)
{
  // valid
  int x = 100; // x is int variable
  int *ptr;    // ptr is integer pointer
  ptr = &x;    // take the address of x, then put the address to ptr

  // now use * dereference operator to point to the address inside ptr
  printf("the address inside ptr is %p\n", ptr);
  printf("the value of the address inside ptr is %d\n", *ptr);

  return 0;
}
// the address inside ptr is 0x7ffddf9d6b98
// the value of the address inside ptr is 100

int main(void)
{
  // valid
  int x; // x is declared, which means x get a memory address
  int *ptr;
  ptr = &x; // initialization with address of x

  printf("the address inside ptr is %p\n", ptr);
  printf("the value of the address inside ptr is %d\n", *ptr);

  return 0;
}
// the address inside ptr is 0x7ffc7974fba8
// the value of the address inside ptr is 0

#include <stdio.h>

int main(void)
{
  int x = 100;
  int *ptr;
  ptr = &x;

  printf("the address of *ptr is %p\n", &ptr);  // &: take address of ptr
  printf("the stored address inside *ptr is %p\n", ptr);
  printf("the value of address inside *ptr is %d\n", *ptr); // *: go to address of ptr

  int *ptr2;
  ptr2 = ptr;

  printf("the address of *ptr2 is %p\n", &ptr2);
  printf("the stored address inside *ptr2 is %p\n", ptr2);
  printf("the value of address inside *ptr2 is %d\n", *ptr2);

  return 0;
}
// the address of *ptr is 0x7ffc13bb32d0 // different address
// the stored address inside *ptr is 0x7ffc13bb32d8 // same address of x
// the value of address inside *ptr is 100 // same value of x

// the address of *ptr2 is 0x7ffc13bb32c8 // different address
// the stored address inside *ptr2 is 0x7ffc13bb32d8 // same address of x
// the value of address inside *ptr2 is 100 // same value of x

• &（address extraction operator or address-of operator）：変数自身のアドレスを参照する。上の例は&xは自身の参照アドレスをptrに渡したり、&ptrはポインタ変数ptr自身を保存するアドレスを参照して出力する。
• *（dereference operator）：ポインタ変数が保存しているアドレスへアクセス。上の例では、xのアドレスへアクセスして値を出力する。

int main(void)
{
  // invalid
  int x;
  int *ptr;
  *ptr = 100; // ptr didn't store any memory address, it may cause run-time error
  ptr = &x; // we should initialize ptr before setting value by dereferencing *

  printf("the address inside ptr is %p\n", ptr);
  printf("the value of the address inside ptr is %d\n", *ptr);

  return 0;
}
// error: variable 'ptr' is uninitialized when used here [-Werror,-Wuninitialized]

int main(void)
{
  // valid
  int *ptr = NULL; // declared, and initialized with null pointer constant "NULL"
  // NULL is not a memory address, NULL is a pointer which is pointing to nowhere
  // so NULL will initialize a pointer safely

  // this is the same
  // int *ptr;
  // ptr = NULL;

  printf("the address inside ptr is %p\n", ptr);
  printf("the value of the address inside ptr is %d\n", *ptr);

  return 0;
}
// the address inside ptr is(nil)
// Segmentation fault(core dumped) // error message

int main(void)
{
  // valid
  int x = 100;
  int *ptr1 = &x; // declared, and initialized with taking address of x
  // it is the same as:
  // int *ptr1;
  // ptr1 = &x;

  int *ptr2;
  ptr2 = ptr1; // share the same address inside ptr1

  printf("the address inside ptr1 is %p\n", ptr1);
  printf("the value of the address inside ptr1 is %d\n", *ptr1);
  printf("the address inside ptr2 is %p\n", ptr2);
  printf("the value of the address inside ptr2 is %d\n", *ptr2);

  return 0;
}

// the address inside ptr1 is 0x7ffd8c570558
// the value of the address inside ptr1 is 100
// the address inside ptr2 is 0x7ffd8c570558
// the value of the address inside ptr2 is 100

Valgrind

Memory leak checker

#include <stdlib.h>

void f(void)
{
  int *x = malloc(10 * sizeof(int));
  // x[10] = 0;  // x's length is 10, start from index 0 to 9
  // ==13790== LEAK SUMMARY:
  // ==13790==    definitely lost: 40 bytes in 1 blocks

  // ==13790== 1 errors in context 1 of 2:
  // ==13790== Invalid write of size 4
  // ==13790==    at 0x10915A: f (valgrindtest.c:6)
  // ==13790==    by 0x109183: main (valgrindtest.c:21)
  // ==13790==  Address 0x4bb5068 is 0 bytes after a block of size 40 alloc'd
  // ==13790==    at 0x4848899: malloc

  // solution
  x[9] = 0;
  free(x);
  // ==14350== All heap blocks were freed -- no leaks are possible
}

int main(void)
{
  f();
  return 0;
}

struct

構造体(struct)：複数のデータ型の値を集めて一つのオブジェクトとして扱う集合のこと。
（やっと馴染みのあるのに触れられてちょっと嬉しいです...）

structdata.h

typedef struct
{
  char *name;
  char *academic;
} student;

structdemo.c

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// use "", which means search everywhere
#include "structdata.h" // user-defined head file
#define STUDENTS 3

int main(void)
{
  student students[STUDENTS];
  // the variable name is "students", and its type is called "student", an array!
  // like an array have "STUDENTS"(equal to 3) elements

  for (int i = 0; i < STUDENTS; i++)
  {
    students[i].name = get_string("name: ");
    students[i].academic = get_string("academic: ");
  }

  for (int i = 0; i < STUDENTS; i++)
  {
    printf("%s is in %s\n", students[i].name, students[i].academic);
  }
}
// Harry is in Gryffindor
// Newton is in Hufflepuff
// Severus is in Slytherin

structdemo2.c

#include <cs50.h>
#include <stdio.h>
#include <string.h>

#include "structdata.h" // user-defined head file
#define STUDENTS 3

int main(void)
{
  student students[STUDENTS];

  for (int i = 0; i < STUDENTS; i++)
  {
    students[i].name = get_string("name: ");
    students[i].academic = get_string("academic: ");
  }

  // FILE *fopen(const char *pathname, const char *mode);
  FILE *file = fopen("students.csv", "w"); // open file "students.csv" with "w"rite mode
  if (file != NULL)
  {
    for (int i = 0; i < STUDENTS; i++)
    {
      // int fprintf(FILE *stream, const char *format, ...);
      // to this file address, write string, with values
      fprintf(file, "%s, %s\n", students[i].name, students[i].academic);
    }
    fclose(file);
  }
}

students.csv

Harry, Gryffindor
Newton, Hufflepuff
Severus, Slytherin

Defining custom data types

car.h

// typedef <old name> <new name>;
typedef unsigned char something;
// place at the top of .c file, or in a .h file separately

// example in cs50.h
typedef char *string;
// char * = string

// defining a struct
// struct car
// {
//   int year;
//   char model[10];
//   char plate[7];
//   int odometer;
//   double engine_size;
// };

// typedef struct car carData;

// or
typedef struct car
{
  int year;
  char model[10];
  char plate[7];
  int odometer;
  double engine_size;
} carData;

typedefdemo.c

#include <stdio.h>
#include <string.h>
#include "car.h"

int main(void)
{
  carData myCar; // variable declaration
  // type name: carData
  // variable name: myCar

  myCar.year = 2011;
  strcpy(myCar.plate, "CS50");
  myCar.odometer = 50505;

  printf("Manufactured Date is %d\n", myCar.year);
  printf("Number Plate is %s\n", myCar.plate);
  printf("Odometer is %d\n", myCar.odometer);
  return 0;
}
// Manufactured Date is 2011
// Number Plate is CS50
// Odometer is 50505

File pointers

• fopen()

#include <stdio.h>
FILE *ptr = fopen(<file name>, <operation>);

FILE *ptr1 = fopen("file1.txt", "r"); // "r": read
FILE *ptr2 = fopen("file2.txt", "w"); // "w": write // overwrite the entire file
FILE *ptr3 = fopen("file3.txt", "w"); // "a": append // start writing from the end of the file

---

• fclose()

fclose(<file pointer>);

fclose(ptr1);

---

• fgetc()

// fgetc: file get character
char ch = fgetc(<file pointer>);
// note: the file pointer must be "r" for read

char ch = fgetc(ptr1); // first call will pointing to the first character

// After reading the character, the file pointer is advanced to next character.
// If pointer is at end of file or if an error occurs EOF(End of File) file is returned by this function. 

// Linux command "cat" which essentially does just this
char ch;
while ((ch = fgetc(ptr)) != EOF)
{
  printf("%c", ch);
}

---

• fputc()

fputc(<character>, <file name>)
// write or append the specified character to the pointed-to file
// note: in "w" mode or "a" mode

fputc('A', ptr2);
fputc('!', ptr3);

// copy one file to another
// command line "cp" does just this
char ch;
while((ch = fgetc(ptr)) != EOF)
{
  fputc(ch, ptr2);
}

---

• fread()

fread(<buffer>, <size>, <qty>, <file pointer>);
// <buffer>: a pointer to the location where we're going to store information
// <size>: how large unit of information
// <qty>: quantity, how many unit of information we want to acquire
// <file pointer>: from which file we want to get them
// note: in "r" mode

int arr[10]; // 10 four-byte units
fread(arr, sizeof(int), 10, ptr);
// read 40 bytes of the information
// from the file pointer ptr
// store those 40 bytes in arr

// dynamically storage // saving it on the heap, not stack
double *arr2 = malloc(sizeof(double) * 80);
fread(arr2, sizeof(double), 80, ptr);
// array is a pointer, address itself, so we don't have to &(ampersand) it

// get one character from the file
char c;
fread(&c, sizeof(char), 1, ptr);
// char is not an array, we have to use & to get the address

---

• fwrite()

fwrite(<buffer>, <size>, <qty>, <file pointer>);
// note: in "w" or "a" mode

int arr[10]; // maybe already filled with information
fwrite(arr, sizeof(int), 10, ptr);
// write and collecte information from arr, put it into the file pointer

double *arr2 = malloc(sizeof(double) * 80);
fwrite(arr2, sizeof(double), 80, ptr);

char c;
fwrite(&c, sizeof(char), 1, ptr);
// write information from the address of c, put it into file pointer