Chapter 14 Interpolation: Memory Manipulation APIs

第 14 章 插叙：内存操作 API

本章讨论 UNIX 操作系统的内存分配接口。

1. 内存类型

在运行 C 程序的时候，会分配两种类型的内存。第一种称为栈（stack）内存，它的申请和释放操作是编译器来隐式管理的，所以有时也称为自动（automatic）内存。

1.1. C 申请栈内存很容易，只需要声明变量即可

int a这样就行

编译器会完成剩下的事情。进入函数时候会在 stack 中开辟空间，函数结束时再释放。

所以如果你希望再函数之外调用 variant，请不要放在 stack 中。

1.2. 如果是长期内存的需求，需要所谓堆内存

所有的 malloc 和 free 操作由 programmer 显式完成...

int *x = (int*) malloc(sizeof(int))

得到一个整数变量的指针...

这行代码有几个特点

  1. stack 和 heap memory 的 分配都发生了！

  2. 编译器首先看到 int *x，声明了一个指针变量...分配 stack

  3. 随后调用 malloc() 分配 heap

2. malloc() 调用

malloc 函数很简单，传入要申请的 size of heap space，就会成功返回一个指向新申请空间的 pointer

失败则返回 NULL

2.1. 转化

分配的 pointer...的类型是 void* 的，需要显示转化为需要的类型...这样就好记了！

2.2. 注意一些函数的特殊行为

实际上计算机永远是对的，但是有时候的输出可能会不尽如人意...

这时候需要很强的钻研精神了...

3. free() 调用

分配内存是灯饰的简单部分...而知道何时，如何，以及是否释放内存是困难的...

运用 free(x) 即可

x 表示分配的内存的 指针！

区域大小不会被传入，这部分内容由内存分配库本身记录追踪

4. 常见错误

正确的内存管理...通过编译器的编译是很重要的...

许多新语言支持自动内存管理

automatic memory management...这样的语言中，调用 malloc() 的机制来分配内存时就不需要某些东西来释放空间。

例如：

  1. new ... 或其他东西之后

  2. 这时候 garbage collector 会运行，找出你不再引用的内存，替你释放它...

  3. 根对象：垃圾回收器从程序中直接可访问的对象（如全局变量、栈上的局部变量等）开始，这些称为根对象。

  4. 可达性分析：从根对象出发，遍历对象图，标记所有可达对象。不可达的对象被认为是垃圾。

  5. 垃圾回收算法：使用如标记-清除、引用计数、代际回收等算法来识别和释放不可达对象。

4.1. 忘记分配内存

// 1. forget allocate memory
  /*
  char *src = "hello";
  char *dst;        // error: dst is not allocated
  strcpy(dst, src); // segfault and crash
  return 0;
  */
  char *src = "hello";
  char *dst = (char *)malloc(strlen(src) + 1); // error: dst is not allocated
  strcpy(dst, src);                            // segfault and crash

或者使用 strdup()，让生活更轻松...

4.2. 没有分配足够的内存

  /*
  char *src = "hello";
  char *dst = (char *)malloc(strlen(src));     // too small
  strcpy(dst, src);                            // work properly...
  return 0;
  */

这可能会正常运行

Oddly enough, depending on how malloc is implemented and many other details, this program will often run seemingly correctly. In some cases, when the string copy executes, it writes one byte too far past the end of the allocated space, but in some cases this is harmless, perhaps overwriting a variable that isn’t used anymore. In some cases, these overflows can be incredibly harmful, and in fact are the source of many security vulnerabilities in systems [W06]. In other cases, the malloc library allocated a little extra space anyhow, and thus your program actually doesn’t scribble on some other variable’s value and works quite fine. In even other cases, the program will indeed fault and crash. And thus we learn another valuable lesson: even though it ran correctly once, doesn’t mean it’s correct.

有的情况会有坏处...

TIP: IT COMPILED OR IT RUN != IT IS CORRECT

Just because a program compiled(!) or even ran once or many times correctly does not mean the program is correct. Many events may have conspired to get you to a point where you believe it works, but then something changes and it stops. A common student reaction is to say (or yell) “But it worked before!” and then blame the compiler, operating system, hardware, or even (dare we say it) the professor. But the problem is usually right where you think it would be, in your code. Get to work and debug it before you blame those other components.

4.3. forget init the memory you allocate...

you call malloc() correctly but forget 填写一些值再新分配的内存里...

it lead to unitialized read...

4.4. 忘记释放内存

另一个常见错误称为内存泄漏（memory leak）

如果忘记释放内存，就会发生...

缓慢的泄露内存导致内存不足...

另一些情况，不调用 free() 显得没有错误，那是因为你的程序很短...当程序结束后，进程很快清理空间，这不会造成严重影响，但这确实是一个坏习惯...

长远来看，作为程序员的目标之一是养成良好的习惯，

In the long run, one of your goals as a programmer is to develop good habits; one of those habits is understanding how you are managing memory, and (in languages like C), freeing the blocks you have allocated. Even if you can get away with not doing so, it is probably good to get in the habit of freeing each and every byte you explicitly allocate.

4.5. Freeing Memory Before You Are Done With It

如果在你用完某个内存空间之前释放了它，会造成悬挂指针（dangling pointer）

The subsequent use can crash the program, or overwrite valid memory (e.g., you called free(), but then called malloc() again to allocate something else, which then recycles the errantly-freed memory).

4.6. 重复释放内存

你不止一次释放内存 double free，内存分配库会感到疑惑

crashes are a common outcome

4.7. 错误地调用 free()

When you pass in some other value, bad things can (and do) happen. Thus, such invalid frees are dangerous and of course should also be avoided.

主要是传入的参数错误

正确的参数是 one of the pointers you received from malloc() earlier.

操作系统是最后的门槛，他会一键管理所有的内存操作，就好像所有一切没有发生过一样。所有的 malloc 和free 错误的操作都会没事...使得新手可以肆无忌惮地尝试他们想尝试的东西...

Thus, for short-lived programs, leaking memory often does not cause any operational problems (though it may be considered poor form). When you write a long-running server (such as a web server or database management system, which never exit), leaked memory is a much bigger issue, and will eventually lead to a crash when the application runs out of memory. And of course, leaking memory is an even larger issue inside one particular program: the operating system itself. Showing us once again: those who write the kernel code have the toughest job of all...

编写内核的CSer是很辛苦的...所有一切的规则他们既需要制定，也需要遵守...

5. 底层操作系统支持

malloc() 和 free() 不是系统调用，而是库调用。

他们的本质是 brk 和 sbrk 系统调用...但请不要直接使用，还是要坚持使用 malloc 和 free...

Finally, you can also obtain memory from the operating system via the mmap() call. By passing in the correct arguments, mmap() can create an anonymous memory region within your program — a region which is not associated with any particular file but rather with swap space, something we’ll discuss in detail later on in virtual memory. This memory can then also be treated like a heap and managed as such. Read the manual page of mmap() for more details.

6. 其他调用

内存分配库还支持一切其他调用

  1. calloc() 分配内存，并在返回之前将其置零 this prevents some errors where you assume that memory is zeroed and forget to initialize it yourself

  2. realloc() 创建一个新的更大的内存区域，旧区域复制到其中，并返回新区域的指针。动态拓展...

7. 作业（编码作业）

7.1. Q1

First, write a simple program called null.c that creates a pointer to an integer, sets it to NULL, and then tries to dereference it. Compile this into an executable called null. What happens when you run this program?

CODE

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

int main(int argc, char *argv[])
{
  int *p = NULL;
  *p = 42;
  return 0;
}

OUTPUT

root@LAPTOP-GT06V0GS:~/b# make null
gcc -o null null.c -Wall
root@LAPTOP-GT06V0GS:~/b# ./null
Segmentation fault (core dumped)

EXPALIN

This indicates that the program has crashed due to the attempt to dereference aNULLpointer.

7.2. Q2

Next, compile this program with symbol information included (with the -g flag). Doing so let’s put more information into the executable, enabling the debugger to access more useful information about variable names and the like. Run the program under the debugger by typing gdb null and then, once gdb is running, typing run. What does gdb show you?

OUTPUT

root@LAPTOP-GT06V0GS:~/b# gcc -g -o null null.c
root@LAPTOP-GT06V0GS:~/b# gdb -q null
Reading symbols from null...
(gdb) run
Starting program: /mnt/d/CSLab/osTEP/chapter13/hwk_code/null
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x0000555555555144 in main (argc=1, argv=0x7fffffffdc28) at null.c:7
7         *p = 42;

EXPALIN

shows that the crash occurred in the main function at line 7 of null.c , specifically at the instruction *p = 42;

(gdb) bt
#0  0x0000555555555144 in main (argc=1, argv=0x7fffffffdc28) at null.c:7
(gdb) info locals
p = 0x0
(gdb) print p
$1 = (int *) 0x0

  1. backtraceThis command shows the call stack at the point of the crash, which can be useful for more complex programs.

  2. info localsThis command shows the values of local variables in the current scope, which can help you understand the state of the program at the point of the crash.

  3. print pThis command prints the value of theptrvariable, which should show that it isNULL.

7.3. Q3

Finally, use the valgrind tool on this program. We’ll use memcheck that is a part of valgrind to analyze what happens. Run this by typing in the following: valgrind --leak-check=yes null. What happens when you run this? Can you interpret the output from the tool?

OUTPUT

root@LAPTOP-GT06V0GS:~/b# valgrind --leak-check=yes ./null

# 程序基本信息
==2020== Memcheck, a memory error detector
==2020== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==2020== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==2020== Command: ./null
==2020==	

# 内存错误报告
==2020== Invalid write of size 4
==2020==    at 0x109144: main (null.c:7)
==2020==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==2020==
==2020==
==2020== Process terminating with default action of signal 11 (SIGSEGV)
==2020==  Access not within mapped region at address 0x0
==2020==    at 0x109144: main (null.c:7)
==2020==  If you believe this happened as a result of a stack
==2020==  overflow in your program's main thread (unlikely but
==2020==  possible), you can try to increase the size of the
==2020==  main thread stack using the --main-stacksize= flag.
==2020==  The main thread stack size used in this run was 8388608.
==2020==

# 堆内存总结
==2020== HEAP SUMMARY:
==2020==     in use at exit: 0 bytes in 0 blocks
==2020==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==2020==

# 内存泄漏总结
==2020== All heap blocks were freed -- no leaks are possible
==2020==

# 错误总结
==2020== For lists of detected and suppressed errors, rerun with: -s
==2020== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)

EXPALIN

分为几个部分:

  1. 程序基本信息

  2. 内存错误报告

  3. 堆内存总结

  4. 内存泄漏总结

  5. 错误总结

7.4. Q4

Write a simple program that allocates memory using malloc() but forgets to free it before exiting. What happens when this program runs? Can you use gdb to find any problems with it? How about valgrind (again with the --leak-check=yes flag)?

CODE

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

int main(int argc, char *argv[])
{
  int *ptr = (int *)malloc(sizeof(int));
  if (ptr == NULL)
  {
    fprintf(stderr, "Memory allocation failed\n");
    return 1;
  }
  *ptr = 42;
  printf("Value stored: %d\n", *ptr);
  return 0;
}

OUTPUT

root@LAPTOP-GT06V0GS:~/b# gcc -g -o q4 q4.c
root@LAPTOP-GT06V0GS:~/b# ./q4
Value stored: 42
root@LAPTOP-GT06V0GS:~/b# gdb -q q4
Reading symbols from q4...
(gdb) run
Starting program: /mnt/d/CSLab/osTEP/chapter13/hwk_code/q4
Downloading separate debug info for system-supplied DSO at 0x7ffff7fc3000
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Value stored: 42
[Inferior 1 (process 2045) exited normally]
(gdb) break main
Breakpoint 1 at 0x55555555519c: file q4.c, line 6.
(gdb) run
Starting program: /mnt/d/CSLab/osTEP/chapter13/hwk_code/q4
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, main (argc=1, argv=0x7fffffffdc38) at q4.c:6
6         int *ptr = (int *)malloc(sizeof(int));
(gdb) print ptr
$1 = (int *) 0x7fffffffdc38
root@LAPTOP-GT06V0GS:~/b# valgrind --leak-check=yes ./q4
==2057== Memcheck, a memory error detector
==2057== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==2057== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==2057== Command: ./q4
==2057==
Value stored: 42
==2057==
==2057== HEAP SUMMARY:
==2057==     in use at exit: 4 bytes in 1 blocks
==2057==   total heap usage: 2 allocs, 1 frees, 1,028 bytes allocated
==2057==
==2057== 4 bytes in 1 blocks are definitely lost in loss record 1 of 1
==2057==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2057==    by 0x1091A5: main (q4.c:6)
==2057==
==2057== LEAK SUMMARY:
==2057==    definitely lost: 4 bytes in 1 blocks
==2057==    indirectly lost: 0 bytes in 0 blocks
==2057==      possibly lost: 0 bytes in 0 blocks
==2057==    still reachable: 0 bytes in 0 blocks
==2057==         suppressed: 0 bytes in 0 blocks
==2057==
==2057== For lists of detected and suppressed errors, rerun with: -s
==2057== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

EXPALIN

gcc 运行输出:

  1. 正常打印值

  2. 程序正常退出

  3. 貌似没有错误...

gdb 输出:

  1. 一开始 run 没有任何报错, 顺利退出

  2. 然后加上断点, 再次 run

  3. print ptr 检查指针的值

  4. 貌似也是正常?

valgrind 输出:

  1. 程序正常运行：程序运行并输出了Value stored: 42

  2. 内存泄漏检测:

    1. 程序退出时，仍有 4 字节的内存未释放，位于 1 个内存块中。

    2. 程序中进行了 2 次内存分配，1 次释放，总共分配了 1,028 字节。

    3. 确定丢失了 4 字节的内存，位于 1 个内存块中。

    4. 内存泄漏发生在malloc调用处。

看来只有valgrind才是真神 ! ! !

7.5. Q5

Write a program that creates an array of integers called data of size 100 using malloc; then, set data[100] to zero. What happens when you run this program? What happens when you run this program using valgrind? Is the program correct?

CODE

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

int main(int argc, char *argv[])
{
  int *data = (int *)malloc(sizeof(int) * 100);
  if (data == NULL)
  {
    fprintf(stderr, "Memory allocation failed\n");
    return 1;
  }
  data[100] = 0;
  free(data);
  return 0;
}

OUTPUT

root@LAPTOP-GT06V0GS:~/b# gcc -g -o q5 q5.c
root@LAPTOP-GT06V0GS:~/b# ./q5
root@LAPTOP-GT06V0GS:~/b# valgrind --leak-check=yes ./q5
==2068== Memcheck, a memory error detector
==2068== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==2068== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==2068== Command: ./q5
==2068==
==2068== Invalid write of size 4
==2068==    at 0x1091E5: main (q5.c:12)
==2068==  Address 0x4a841d0 is 0 bytes after a block of size 400 alloc'd
==2068==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2068==    by 0x1091A5: main (q5.c:6)
==2068==
==2068==
==2068== HEAP SUMMARY:
==2068==     in use at exit: 0 bytes in 0 blocks
==2068==   total heap usage: 1 allocs, 1 frees, 400 bytes allocated
==2068==
==2068== All heap blocks were freed -- no leaks are possible
==2068==
==2068== For lists of detected and suppressed errors, rerun with: -s
==2068== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

EXPALIN

  1. 正常运行, 貌似正常输出

  2. 如果用 valgrind

    1. 则会报错

    2. Invalid write of size 4程序试图写入一个无效的地址

    3. 写入的地址位于分配的内存块之后，具体是分配的 400 字节内存块的最后一个字节之后

    4. Heap Summary 正常, 即没有分配的内存未释放的现象...

7.6. Q6

Create a program that allocates an array of integers (as above), frees them, and then tries to print the value of one of the elements of the array. Does the program run? What happens when you use valgrind on it?

CODE

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

int main(int argc, char *argv[])
{
  int *data = (int *)malloc(sizeof(int) * 100);
  if (data == NULL)
  {
    fprintf(stderr, "Memory allocation failed\n");
    return 1;
  }
  data[0] = 0;
  data[100] = 0;
  free(data);
  printf("data[0] = %d\n", data[0]);
  return 0;
}

OUTPUT

root@LAPTOP-GT06V0GS:~/b# make q6
gcc -o q6 q6.c -Wall
q6.c: In function ‘main’:
q6.c:15:3: warning: pointer ‘data’ used after ‘free’ [-Wuse-after-free]
   15 |   printf("data[0] = %d\n", data[0]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
q6.c:14:3: note: call to ‘free’ here
   14 |   free(data);
      |   ^~~~~~~~~~
root@LAPTOP-GT06V0GS:~/b# ./q6
data[0] = 1635446788
root@LAPTOP-GT06V0GS:~/b# gcc -g -o q6 q6.c
root@LAPTOP-GT06V0GS:~/b# valgrind --leak-check=yes ./q6
==2099== Memcheck, a memory error detector
==2099== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==2099== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==2099== Command: ./q6
==2099==
==2099== Invalid write of size 4
==2099==    at 0x10920F: main (q6.c:13)
==2099==  Address 0x4a841d0 is 0 bytes after a block of size 400 alloc'd
==2099==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2099==    by 0x1091C5: main (q6.c:6)
==2099==
==2099== Invalid read of size 4
==2099==    at 0x109225: main (q6.c:15)
==2099==  Address 0x4a84040 is 0 bytes inside a block of size 400 free'd
==2099==    at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2099==    by 0x109220: main (q6.c:14)
==2099==  Block was alloc'd at
==2099==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2099==    by 0x1091C5: main (q6.c:6)
==2099==
data[0] = 0
==2099==
==2099== HEAP SUMMARY:
==2099==     in use at exit: 0 bytes in 0 blocks
==2099==   total heap usage: 2 allocs, 2 frees, 1,424 bytes allocated
==2099==
==2099== All heap blocks were freed -- no leaks are possible
==2099==
==2099== For lists of detected and suppressed errors, rerun with: -s
==2099== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

EXPALIN

其实如果 gcc 开 warnning 的话是会有报错的, 运行也能正常. 但是输出的值不正确...

如果用 valgrind 就能看出

  1. 越界写入

    1. Invalid write of size 4

    2. 程序试图写入一个超出分配内存范围的地址。

  3. 使用已释放的内存

    1. Invalid read of size 4

    2. 程序试图读取一个已经释放的内存块。

7.7. Q7

Now pass a funny value to free (e.g., a pointer in the middle of the array you allocated above). What happens? Do you need tools to find this type of problem?

CODE

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

int main(int argc, char *argv[])
{
  int *data = (int *)malloc(sizeof(int) * 100);
  if (data == NULL)
  {
    fprintf(stderr, "Memory allocation failed\n");
    return 1;
  }
  data[50] = 50;
  free(&data[50]);
  return 0;
}

OUTPUT

root@LAPTOP-GT06V0GS:~/b# make q7
gcc -o q7 q7.c -Wall
q7.c: In function ‘main’:
q7.c:13:3: warning: ‘free’ called on pointer ‘data’ with nonzero offset 200 [-Wfree-nonheap-object]
   13 |   free(&data[50]);
      |   ^~~~~~~~~~~~~~~
q7.c:6:22: note: returned from ‘malloc’
    6 |   int *data = (int *)malloc(sizeof(int) * 100);
      |                      ^~~~~~~~~~~~~~~~~~~~~~~~~
root@LAPTOP-GT06V0GS:~/b# ./q7
free(): invalid pointer
Aborted (core dumped)
root@LAPTOP-GT06V0GS:~/b# valgrind --leak-check=yes ./q7
==2128== Memcheck, a memory error detector
==2128== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==2128== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==2128== Command: ./q7
==2128==
==2128== Invalid free() / delete / delete[] / realloc()
==2128==    at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2128==    by 0x1091FC: main (in /mnt/d/CSLab/osTEP/chapter13/hwk_code/q7)
==2128==  Address 0x4a84108 is 200 bytes inside a block of size 400 alloc'd
==2128==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2128==    by 0x1091A5: main (in /mnt/d/CSLab/osTEP/chapter13/hwk_code/q7)
==2128==
==2128==
==2128== HEAP SUMMARY:
==2128==     in use at exit: 400 bytes in 1 blocks
==2128==   total heap usage: 1 allocs, 1 frees, 400 bytes allocated
==2128==
==2128== 400 bytes in 1 blocks are definitely lost in loss record 1 of 1
==2128==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2128==    by 0x1091A5: main (in /mnt/d/CSLab/osTEP/chapter13/hwk_code/q7)
==2128==
==2128== LEAK SUMMARY:
==2128==    definitely lost: 400 bytes in 1 blocks
==2128==    indirectly lost: 0 bytes in 0 blocks
==2128==      possibly lost: 0 bytes in 0 blocks
==2128==    still reachable: 0 bytes in 0 blocks
==2128==         suppressed: 0 bytes in 0 blocks
==2128==
==2128== For lists of detected and suppressed errors, rerun with: -s
==2128== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

EXPALIN

  1. 这个比较简单, 就是分配和释放的东西不是同一个东西...

  2. 普通的 gcc 可以发现

  3. 当你运行起来, free() 也会检查也能发现 甚至你用valgrind也可以发现

    1. Invalid free()无效的 free() 调用

    2. 内存泄漏 程序分配了 400 字节的内存，但没有正确释放，导致内存泄漏。

  5. 其实是同一个问题, 就是预先分配的内存没有正确释放, 和没释放是一样的...

7.8. Q8

Try out some of the other interfaces to memory allocation. For example, create a simple vector-like data structure and related routines that use realloc() to manage the vector. Use an array to store the vectors elements; when a user adds an entry to the vector, use realloc() to allocate more space for it. How well does such a vector perform? How does it compare to a linked list? Use valgrind to help you find bugs.

CODE

// vector.h
#ifndef VECTOR_H
#define VECTOR_H

#include <stdlib.h>

typedef struct
{
  int *data;
  size_t size;
  size_t capacity;
} Vector;

// Initialize a new vector
void vector_init(Vector *vec);

// Add an element to the vector
void vector_add(Vector *vec, int value);

// Free the memory allocated for the vector
void vector_free(Vector *vec);

#endif
// vector.c
#include "vector.h"
#include <stdio.h>
#include <stdlib.h>

void vector_init(Vector *vec)
{
  vec->data = NULL;
  vec->size = 0;
  vec->capacity = 0;
}

void vector_add(Vector *vec, int value)
{
  if (vec->size == vec->capacity)
  {
    size_t new_capacity = vec->capacity == 0 ? 1 : vec->capacity * 2;
    int *new_data = realloc(vec->data, new_capacity * sizeof(int));
    if (!new_data)
    {
      fprintf(stderr, "Memory allocation failed\n");
      exit(EXIT_FAILURE);
    }
    vec->data = new_data;
    vec->capacity = new_capacity;
  }
  vec->data[vec->size++] = value;
}

void vector_free(Vector *vec)
{
  free(vec->data);
  vec->data = NULL;
  vec->size = 0;
  vec->capacity = 0;
}
// main.c
#include "vector.h"
#include <stdio.h>

int main()
{
  Vector vec;
  vector_init(&vec);

  for (int i = 0; i < 100; i++)
  {
    vector_add(&vec, i);
  }

  for (size_t i = 0; i < vec.size; i++)
  {
    printf("%d ", vec.data[i]);
  }
  printf("\n");

  vector_free(&vec);
  return 0;
}

OUTPUT

root@LAPTOP-GT06V0GS:~/b# gcc -g -o vector_example vector.c main.c
root@LAPTOP-GT06V0GS:~/b# ./vector_example
0 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
root@LAPTOP-GT06V0GS:~/b# valgrind --leak-check=yes ./vector_example
==2140== Memcheck, a memory error detector
==2140== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==2140== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==2140== Command: ./vector_example
==2140==
0 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
==2140==
==2140== HEAP SUMMARY:
==2140==     in use at exit: 0 bytes in 0 blocks
==2140==   total heap usage: 9 allocs, 9 frees, 2,044 bytes allocated
==2140==
==2140== All heap blocks were freed -- no leaks are possible
==2140==
==2140== For lists of detected and suppressed errors, rerun with: -s
==2140== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

EXPALIN

Performance Analysis: Vector

  • Advantages: Contiguous memory allocation, efficient random access.

    • 使用 realloc

    • 内存分配连续, 便于随机访问

    • 需要多次分配内存

  • Disadvantages: Potential for multiple reallocations, which can be costly.

    • 可能需要多次重新分配内存，这可能会带来较高的成本

Linked List:

  • Advantages: Dynamic size, efficient insertions and deletions.

    • 动态大小

    • 每次创造新结点需要 malloc Node, 而不是一个固定容量

  • Disadvantages: Non-contiguous memory allocation, inefficient random access.

    • 内存分配不连续，随机访问效率低

总结:

  • 向量（Vector）：适用于随机访问频繁且大小相对稳定的场景。

  • 链表（Linked List）：适用于需要频繁插入和删除操作的场景。

7.9. Q9

Spend more time and read about using gdb and valgrind. Knowing your tools is critical; spend the time and learn how to become an expert debugger in the UNIX and C environment.

respect!!!

PreviousChapter 13 Abstraction: Address SpacesNextChapter 17 Free Space Management

Last updated