Lecture 15: 数据结构：结构体、typedef 与信息隐藏 (Data Structures: structs, typedef and Information Hiding)
Lecture 15: 数据结构：结构体、typedef 与信息隐藏 (Data Structures: structs, typedef and Information Hiding)
概述
本讲要解决的问题是：当程序需要同时记录一件事物的多个属性（书的作者、标题、ISBN、页数、价格）时， 如何把它们作为一个整体来组织、传递与保护。引入的机制是 C 的结构体 (struct)、 类型别名 typedef、枚举 enum，以及把”接口”与”实现”分开的头文件 + 不透明类型 (opaque type) 惯用法。 这一讲是第 16 讲动态内存分配的直接前提——malloc 返回的每个对象本质上都是一块”由头文件声明的类型、 由 .c 文件私有定义其字段”的数据，而课程真实的 mem220 分配器正是这种设计的完整范例。
核心概念与底层机制图解
- 结构体：定义 (definition) 与声明 (declaration)：
struct book_t {...};只是定义类型，不分配内存；struct book_t book;才是声明一个变量（对象）。- 直观解释：定义像”表格模板”（有哪些栏），声明像”填好的一张表”；模板本身不占抽屉。
- 底层机制图解：字段按定义顺序连续排列，编译器为每个字段记住固定的偏移 (offset)；
book.pages因此编译成”取book的地址 + 偏移 160，再按int32_t访问”，对齐由编译器负责。 - 作用域与存储期：类型名是文件作用域；变量的存储期取决于声明位置——函数内 automatic（随帧生灭）、 函数外 static、
malloc出来的 dynamic（见第 16 讲）。
sizeof与”成员之和”不是一回事：实测pad_t的成员之和是 6 字节，sizeof却是 12。- 直观解释：
sizeof是”抽屉实际占多大”，包含为对齐留的空隙。 - 底层机制图解：编译器要保证每次字段访问都对齐，因此在字段之间与结构体末尾插入填充 (padding)。 实测
struct {char author[50]; char title[100]; uint64_t isbn; int32_t pages; double price;}的sizeof是 176、成员之和是 170：title结束于 150，isbn需 8 字节对齐，于是插了 2 字节空隙。 永远不要手算结构体大小，用sizeof (变量名)，因为它随 ISA、OS、编译器与编译选项变化。 - 作用域与存储期：
sizeof是编译期运算符（变长数组除外），不产生运行时代码。
- 直观解释：
- 数组的结构体 vs 结构体的数组 (AoS vs SoA)：
- 直观解释：AoS 是”每本书一张卡片，卡片排成一摞”；SoA 是”把所有书的作者抄在一张纸上、 所有书的价格抄在另一张纸上”。
- 底层机制图解：
book_t shelf[10]中每个元素占sizeof(book_t)字节， 所以shelf[i]的地址是base + i * 176——跨步 (stride) 就是结构体大小， 循环访问同一字段时每次要跳过一大段内存，对缓存不友好；SoA （char author[10][50]; double price[10];）让每个字段各自连续，适合批量处理单个字段。 两者存储期一致，差别在”复制一本书”的粒度：176 字节还是 50 字节。
- 按值传递/返回结构体 vs 传指针：
- 直观解释：按值传递像”把整本书复印一份交给对方”，传指针像”告诉他书在第几排第几格”。
- 底层机制图解：C 的参数传递是按值 (call-by-value)，所以把结构体作为参数会复制整个结构体到栈上； 课程示例里的
stack_t含char data[500][200]，约 100,000 字节， 每次调用复制它是不可接受的。因此约定是：传结构体的地址（const stack_t* s）， 并用->访问字段；只在结构体很小（如两个double构成的复数）时才考虑按值。 返回结构体同理：return s;会把整个结构体复制回调用者。 - 作用域与存储期：被调用者拿到的是调用者对象的别名（通过指针）， 所以它能修改调用者的数据；这正是
stack_init (&s)能改变s.top的原因。
typedef与enum：给类型取名字：- 直观解释：
typedef像给类型起绰号；enum像给一组整数贴标签（SPACE_FULL比1好读）。 - 底层机制图解：
typedef struct player_t player_t;让类型名与结构体标签同名，从此不必写struct； 课程代码约定用typedef struct {...} name_t;。enum成员就是整型常量，默认从 0 递增、可显式赋值； 两个常用惯用法：① 末尾放”计数”名（NUM_SPACE_TYPES），数组大小随枚举自动调整； ② 作位向量给 bit 命名（LEFT_WALL=1, RIGHT_WALL=2, UPPER_WALL=4, LOWER_WALL=8, HAS_EXIT=16）。 实测sizeof (space_type_t) = 4，SPACE_EMPTY/FULL/BLOCK = 0/1/2，与switch天然搭配。 - 作用域与存储期：两者都只影响”名字”，不产生运行时对象；
enum常量是编译期常量，可当数组长度。
- 直观解释：
- 结构体里的函数指针：穷人的虚函数 (poor man’s virtual method)：
- 直观解释：给每张表格附上一栏”该找谁办这件事”，不同的表格填不同的办事员。
- 底层机制图解：
struct shape_t { double a, b; double (*area)(const shape_t*); }把”数据”和”操作”放进同一个对象，s->area (s)先取函数指针再间接调用—— 在 x86-64 上是一条call *%rax，与 C++ 虚函数表 (vtable) 的机制同源。 实测sizeof (shape_t) = 40，其中两个函数指针各占 8 字节（area在偏移 24、name在偏移 32）。 调用点describe (&table[0])完全不需要知道对象究竟是矩形还是圆，这就是多态 (polymorphism) 的雏形。 - 作用域与存储期：函数名在表达式里退化为函数指针；结构体赋值会连同函数指针一起复制 （实测
table[0] = table[1]之后，两次describe都打印 circle）。
- 信息隐藏 (Information Hiding)：头文件是接口，
.c文件是私有实现：- 直观解释：
stdio.h也是这个套路——你天天用FILE*，但从不（也不应该）去碰它的字段。 - 底层机制图解：把类型的前向声明 (forward declaration) 放进头文件、 把字段定义放进
.c文件，使用者的代码就只能操控指针，无法依赖内部布局：/* memory_system.h —— 只有接口，没有字段 */ #if !defined(_MEMORY_SYSTEM_H) #define _MEMORY_SYSTEM_H typedef struct memory_system memory_system_t; /* 不完整类型 */ memory_system_t* memory_system_create (size_t capacity); void memory_system_destroy (memory_system_t* ms); #endif /* !defined(_MEMORY_SYSTEM_H) */memory_system_t在这里是不完整类型 (incomplete type)：编译器知道这个名字， 但不知道它有多大，所以memory_system_t ms;或ms->capacity都会编译失败—— 这正是我们想要的保护。课程的真实案例mem220.h更彻底：它只声明四个函数， 连mem_block_t这个名字都不暴露，把块头结构、空闲链表数组、log2_ceil全部关在mem220.c里。 头文件还必须写包含守卫 (include guard)，否则同一个头被两条#include路径各包含一次时， 类型会被重复定义而编译报错。 - 作用域与存储期：不透明类型对象的存储期由创建/销毁函数管理（
_create里malloc，_destroy里free），使用者只持有”句柄 (handle)“——一个不透明指针。 典型签名会带上const（如memory_system_fetch (const memory_system_t*, ...)）来表达”只读”。
- 直观解释：
结构体布局图解（pad_t 的实测字节）：
struct pad_t { char a; int32_t b; char c; }; sizeof = 12（成员之和只有 6）
偏移: 0 1 2 3 4 5 6 7 8 9 10 11
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| a | ### | ### | ### | b (4 字节) | c | ### | ### | ### |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
'A'=41 填充 填充 填充 44 33 22 11 'C'=43 填充（尾部填充）
实测字节: 41 00 00 00 44 33 22 11 43 00 00 00
↑ b 必须在 4 的倍数地址上，所以先塞 3 个洞
↑ 数组里下一个元素也要 4 字节对齐，故尾部再补 3 个洞
换成 struct tight_t { char a; char c; int32_t b; }; sizeof = 8（没有内部填充）
实测字节: 41 43 00 00 44 33 22 11 ← 字段顺序影响大小！
AoS / SoA 图解：
数组的结构体 (Array of Structs): book_t shelf[3]
base+0 base+176 base+352
┌──────────────────┐ ┌──────────────────┐ ┌──────────────────┐
│ book0 的 176 字节 │ │ book1 的 176 字节 │ │ book2 的 176 字节 │
└──────────────────┘ └──────────────────┘ └──────────────────┘
取 shelf[i].price 的地址 = base + i*176 + 168 ← 跨步很大
结构体的数组 (Struct of Arrays):
char author[3][50] ← 连续 double price[3] ← 连续
批量取价格时内存访问是顺序的，缓存友好
代码示例与底层机制分析
示例 1：填充、对齐与 sizeof
代码 (C):
/* l1_layout.c
* 编译： gcc -g -std=c99 -Wall -Werror l1_layout.c -o l1_layout */
#include <stdio.h>
#include <stdint.h>
#include <stddef.h>
#include <string.h>
/* The layout from lecture: one byte, four bytes, one byte. */
typedef struct {
char a;
int32_t b;
char c;
} pad_t;
/* The same fields reordered so that no interior padding is needed. */
typedef struct {
char a;
char c;
int32_t b;
} tight_t;
/* A book, from the structured-data lecture. */
typedef struct {
char author[50];
char title[100];
uint64_t isbn;
int32_t pages;
double price;
} book_t;
static void
dump (const char* label, const void* p, size_t n)
{
const unsigned char* b = p;
size_t i;
printf ("%-11s:", label);
for (i = 0; n > i; i++) {
printf (" %02X", b[i]);
}
printf ("\n");
}
int
main (void)
{
pad_t p;
tight_t t;
memset (&p, 0, sizeof (p));
memset (&t, 0, sizeof (t));
p.a = 'A'; p.b = 0x11223344; p.c = 'C';
t.a = 'A'; t.c = 'C'; t.b = 0x11223344;
printf ("--- pad_t { char a; int32_t b; char c; } ---\n");
printf ("sizeof = %ld, offsets: a=%ld b=%ld c=%ld\n", (long)sizeof (pad_t),
(long)offsetof (pad_t, a), (long)offsetof (pad_t, b),
(long)offsetof (pad_t, c));
dump ("bytes", &p, sizeof (p));
printf ("\n--- tight_t { char a; char c; int32_t b; } ---\n");
printf ("sizeof = %ld, offsets: a=%ld c=%ld b=%ld\n", (long)sizeof (tight_t),
(long)offsetof (tight_t, a), (long)offsetof (tight_t, c),
(long)offsetof (tight_t, b));
dump ("bytes", &t, sizeof (t));
printf ("\n--- book_t ---\n");
printf ("sizeof = %ld bytes, sum of members = %ld bytes\n", (long)sizeof (book_t),
(long)(50 + 100 + 8 + 4 + 8));
printf ("offsets: author=%ld title=%ld isbn=%ld pages=%ld price=%ld\n",
(long)offsetof (book_t, author), (long)offsetof (book_t, title),
(long)offsetof (book_t, isbn), (long)offsetof (book_t, pages),
(long)offsetof (book_t, price));
printf ("title ends at %ld, isbn starts at %ld -> %ld bytes of padding\n",
(long)(offsetof (book_t, title) + 100), (long)offsetof (book_t, isbn),
(long)(offsetof (book_t, isbn) - (offsetof (book_t, title) + 100)));
return 0;
}
真实运行输出:
--- pad_t { char a; int32_t b; char c; } ---
sizeof = 12, offsets: a=0 b=4 c=8
bytes : 41 00 00 00 44 33 22 11 43 00 00 00
--- tight_t { char a; char c; int32_t b; } ---
sizeof = 8, offsets: a=0 c=1 b=4
bytes : 41 43 00 00 44 33 22 11
--- book_t ---
sizeof = 176 bytes, sum of members = 170 bytes
offsets: author=0 title=50 isbn=152 pages=160 price=168
title ends at 150, isbn starts at 152 -> 2 bytes of padding
【代码做什么？】
pad_t把a='A'放在偏移 0，b=0x11223344放在偏移 4，c='C'放在偏移 8。- 用
dump把结构体的原始字节打出来：41 00 00 00 44 33 22 11 43 00 00 00——a后面 3 个00是内部填充，c后面 3 个00是尾部填充，所以sizeof = 12。 tight_t只是把b挪到最后：sizeof变成 8，字节为41 43 00 00 44 33 22 11。book_t打印每个字段的offsetof，并算出title（结束于 150）与isbn（起始于 152）之间的 2 字节空隙。- 三次输出共同说明一件事：结构体的大小与布局由编译器按对齐规则决定，不能手算。
【底层机制透视】 对齐规则的表述是：每个字段必须放在它自身大小的整数倍偏移上（int32_t → 4 的倍数， double/uint64_t → 8 的倍数），而结构体整体的对齐是所有字段对齐要求的最大值， 因此结构体总大小会被补齐到该对齐的倍数（这解释了 pad_t 尾部的 3 个字节： a 占 1 字节、b 占 4 字节、c 占 1 字节共 6 字节，但数组 pad_t v[2] 里第二个元素的 b 也必须 4 字节对齐，所以整体补到 12）。 多数支持字节寻址的 ISA 要求”N 字节的载入/存储必须落在 N 的倍数地址上” （从 0x20000001 载入 32 位值会崩溃；即使允许未对齐访问，速度也可能慢两个数量级）， 所以编译器必须插入填充。实用技巧：大字段排在前面、小字段排在后面通常能减少填充 （tight_t 比 pad_t 小 4 字节）；确实需要紧凑布局时，应该按字节手工序列化，而不是依赖 #pragma pack。
【内存布局图解】（pad_t vs tight_t，见前面的”结构体布局图解”）
【与汇编的对应】 LC-3 没有”结构体”：字段访问完全是基址 + 偏移。设 R2 存放 book_t* book， 那么 book->pages（偏移 160）与 book->price（偏移 168）就是：
; 假设 R2 = &book；LC-3 的 LDR 偏移只有 6 位（0..63），大偏移要先算地址
; 注意：R4 是全局数据指针、R5 是帧指针、R6 是栈指针，临时值只用 R0-R3
LEA R3, BOOK_T_PAGES_OFF ; R3 = 160
ADD R3, R2, R3 ; R3 = &book.pages
LDR R0, R3, #0 ; R0 = book.pages
LEA R3, BOOK_T_PRICE_OFF ; R3 = 168
ADD R3, R2, R3 ; R3 = &book.price
LDR R0, R3, #0 ; R0 = book.price 的低 16 位
ADD R3, R3, #1
LDR R1, R3, #0 ; R1 = 高 16 位（两半拼成一个 32 位值）
; x86-64 上同一段代码会编译成带立即数偏移的取数指令：
; mov 0xa0(%rdi), %eax ; book->pages，偏移 0xa0 = 160
; movsd 0xa8(%rdi), %xmm0 ; book->price，偏移 0xa8 = 168
-> 在机器层面就是一条带立即数偏移的取数指令，没有别的玄机；填充的存在只是让这些偏移”对齐”。
示例 2：结构体 + 操作函数（把接口写成函数，把实现留在帧外）
代码 (C):
/*
* l2b_stack_t.c -- a struct plus the operations that go with it.
* Compile: gcc -g -std=c99 -Wall -Werror l2b_stack_t.c -o l2b_stack_t
*/
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#define MAX_LINES 4
#define MAX_LEN 24
typedef struct {
char data[MAX_LINES][MAX_LEN]; /* the lines, stored newest-first */
int32_t top; /* index of the top; MAX_LINES = empty */
} stack_t;
static int32_t stack_empty (const stack_t* s) { return (MAX_LINES == s->top); }
static int32_t stack_full (const stack_t* s) { return (0 == s->top); }
/* Returns 1 on success, 0 if the stack is full or the string does not fit. */
static int32_t
stack_push (stack_t* s, const char* str)
{
char* write;
int32_t i;
if (stack_full (s)) {
return 0;
}
write = s->data[--s->top]; /* decrement, then use the index */
for (i = 0; '\0' != *str; i++) {
if (MAX_LEN - 1 == i) {
s->top++; /* undo the decrement, then fail */
return 0;
}
*write++ = *str++;
}
*write = '\0';
return 1;
}
/* Returns 1 on success, 0 on failure. Fills buf, truncating if needed. */
static int32_t
stack_pop (stack_t* s, char* buf, int32_t len)
{
const char* read = s->data[s->top];
int32_t i;
if (stack_empty (s)) {
return 0;
}
for (i = 1; len > i && '\0' != *read; i++) {
*buf++ = *read++;
}
*buf = '\0';
s->top++;
return 1;
}
int
main (void)
{
stack_t s;
char buf[MAX_LEN];
/* Passing a stack_t by value would copy all 100 bytes; we pass a pointer. */
printf ("sizeof (stack_t) = %ld bytes\n", (long)sizeof (stack_t));
printf ("&s = %p, &s.data[0][0] = %p (same object, offset 0)\n",
(void*)&s, (void*)&s.data[0][0]);
printf ("offset of top = %ld (measured with pointer subtraction)\n",
(long)((char*)&s.top - (char*)&s));
s.top = MAX_LINES; /* stack_init (&s) */
printf ("push \"first\" -> %d\n", (int)stack_push (&s, "first"));
printf ("push \"second\" -> %d\n", (int)stack_push (&s, "second"));
printf ("push \"third\" -> %d\n", (int)stack_push (&s, "third"));
printf ("push a 30-char string -> %d (too long for %d bytes)\n",
(int)stack_push (&s, "012345678901234567890123456789"), MAX_LEN);
printf ("top is still %d after the failed push\n", (int)s.top);
while (!stack_empty (&s)) {
(void)stack_pop (&s, buf, MAX_LEN);
printf ("pop -> %s\n", buf);
}
return 0;
}
真实运行输出:
sizeof (stack_t) = 100 bytes
&s = 0x7ffd095fb560, &s.data[0][0] = 0x7ffd095fb560 (same object, offset 0)
offset of top = 96 (measured with pointer subtraction)
push "first" -> 1
push "second" -> 1
push "third" -> 1
push a 30-char string -> 0 (too long for 24 bytes)
top is still 1 after the failed push
pop -> third
pop -> second
pop -> first
上面的
&s地址是示意值（每次运行因 ASLR 而不同）；关键是它与&s.data[0][0]完全相同， 而top的偏移恒为 96 =4 × 24，即结构体前 96 字节全是data，top紧接其后。
【代码做什么？】
stack_t把”400 字节的二维字符数组 + 一个栈顶下标”聚合在一起，sizeof实测 100 字节 （4×24 = 96 字节数据 + 4 字节top，对齐到 4 的倍数）。&s与&s.data[0][0]打印出同一个地址，证明data就在偏移 0 处、没有额外开销；top的偏移实测是 96。main把top设为 4（空栈）；stack_push先--s->top再写字符串，所以栈是向下增长的。- 前三次 push 都成功；第四次传入 30 字符的串超过了 23 字符的上限，
stack_push撤销了已经做的--s->top并返回 0，因此top仍然是 1。 - 最后循环
stack_pop直到空栈，输出顺序是third / second / first（后进先出）。
【底层机制透视】 stack_empty 的参数是 const stack_t*：const 承诺”我不会修改你指向的对象”， 指针则避免复制 100 字节。-> 完全等价于 (*s).top——因为 . 的优先级高于 *， 所以必须写括号，C 才提供 -> 作为简写。实测 offset of top = 96 也说明了 “字段访问 = 基址 + 常量偏移”这一本质：s->top 编译成从 s 的第 96 字节处取 4 字节。 stack_push 里”失败时把 top 加回来”体现了要么完整成功、要么完全不动的接口原则； 忘了这一步，失败的 push 会永久吃掉一个栈槽，这类”状态泄漏”是最难查的错误之一。 另外，stack_push 复制了字符串，stack_pop 也必须复制到调用者提供的数组里—— 因为栈内那份随时会被下一次 push 覆盖。课程对此的总结是 “信息隐藏与性能有时互相冲突“：复制两次是浪费，但换来调用者不必关心栈内部的生命周期。
【内存布局图解】
stack_t s（在 main 的栈帧里，起始地址实测 0x7fffa87c6980）
┌───────────────────────────────────────────────┐
│ s.data[0][0..23] ← 偏移 0 │ s.data[1] ← 偏移 24│
│ s.data[2] ← 偏移 48 │ s.data[3] ← 偏移 72│
├───────────────────────────────────────────────┤
│ s.top ← 偏移 96（实测，地址 0x7fffa87c69e0） │ 共 100 字节
└───────────────────────────────────────────────┘
push: top=4（空）→ "first" 存 data[3]，top=3 → "second" 存 data[2]，top=2
→ "third" 存 data[1]，top=1；pop 读 data[top] 后 top++，顺序反过来。
【与汇编的对应】
; stack_init: s->top = MAX_LINES （R0 = 指向 stack_t 的指针）
STKINIT LEA R1, MAX_LINES_VAL
ADD R2, R0, #96 ; top 的偏移是 96（实测）
STR R1, R2, #0 ; (*s).top = 4
RET
; stack_push: 先 --s->top，再把字符逐个写进 s->data[top]
STKPUSH ADD R2, R0, #96
LDR R1, R2, #0 ; R1 = s->top
ADD R1, R1, #-1 ; --s->top
STR R1, R2, #0 ; 写回
; data[top] 的地址 = s + top*24（每行 24 字节）：用循环连加 24 次求偏移
; 注意：R5 是帧指针、R4 是全局数据指针，临时值只用 R0-R3
COPYLP LDR R2, R1, #0 ; R2 = *str（R1 = 读指针，R3 = 写指针）
STR R2, R3, #0 ; *write = *str
ADD R3, R3, #1
ADD R1, R1, #1
; ... 判断是否到达 '\0' 或长度上限 ... ; BRnzp COPYLP
-> 与 [] 在汇编里都是”基址 + 偏移“的算术：s->top 是固定偏移 96， 而 s.data[top] 的偏移要先算 top * 24。这正是讲指针与数组时反复出现的同一条规则。
案例研究：不透明类型与真实的 mem220 分配器
接口（memory_system.h，节选，完整文件见随附源码）:
/* 只有接口，没有任何字段 */
#if !defined(_MEMORY_SYSTEM_H)
#define _MEMORY_SYSTEM_H
typedef struct memory_system memory_system_t; /* 不完整类型：只知道名字 */
memory_system_t* memory_system_create (size_t capacity);
void memory_system_destroy (memory_system_t* ms);
int32_t memory_system_store (memory_system_t* ms, int32_t value);
int32_t memory_system_fetch (const memory_system_t* ms, size_t index, int32_t* out);
size_t memory_system_count (const memory_system_t* ms);
#endif /* !defined(_MEMORY_SYSTEM_H) */
实现（memory_system.c，节选）——字段定义只出现在这个文件里：
#include "memory_system.h"
struct memory_system { /* 使用者永远看不到这个定义 */
int32_t* data; /* 动态分配的数组 */
size_t capacity;
size_t count;
};
memory_system_t*
memory_system_create (size_t capacity)
{
memory_system_t* ms;
if (0 == capacity || NULL == (ms = malloc (sizeof (*ms)))) { return NULL; }
ms->data = malloc (capacity * sizeof (*ms->data)); /* 大小只有本文件知道 */
if (NULL == ms->data) { free (ms); return NULL; } /* 不要泄漏外层对象 */
ms->capacity = capacity; ms->count = 0;
return ms;
}
使用者视角（s5_main.c，节选）与实测输出:
memory_system_t* ms = memory_system_create (4);
/* 下面这行无法编译——这正是信息隐藏的效果：
printf ("%ld\n", ms->capacity); // error: incomplete type */
store 0 : ok
store 10 : ok
store 20 : ok
store 30 : ok
store 40 : rejected (full)
store 50 : rejected (full)
count = 4
fetch [0] : ok, value = 0
fetch [4] : out of range
destroyed
真实课程代码：mem220.h / mem220.c。这一对文件把不透明做到极致—— 头文件连一个结构体名都不暴露，只声明四个函数（与 C 库的 malloc/calloc/realloc/free 一一对应）：
/* mem220.h（节选） */
#if !defined(_MEM220_H)
#define _MEM220_H /* ← 包含守卫：防止重复定义 */
#include <stdint.h>
#define MEM220_MAX_ALLOC_LOG 20
#define MEM220_MAX_ALLOC (1UL << MEM220_MAX_ALLOC_LOG) /* 1 MiB */
void* mem220_allocate (size_t n_bytes); /* 对应 malloc */
void* mem220_allocate_and_zero (size_t n_bytes); /* 对应 calloc */
int32_t mem220_reallocate (void** ptr_to_ptr, size_t n_bytes); /* realloc */
void mem220_free (void* ptr); /* 对应 free */
#endif /* !defined(_MEM220_H) */
实现在 mem220.c 里，全部私有：块头类型、空闲链表数组、log2_ceil 都是 static（文件作用域）， 外部代码既看不到也改不了：
/* mem220.c（节选）—— 这些名字在 mem220.h 里完全不出现 */
typedef struct mem_block_t mem_block_t;
struct mem_block_t {
size_t size; /* 块的字节数（2 的幂） */
mem_block_t* next; /* 空闲链表指针 */
};
static uint8_t* free_bytes; /* 未分配的内存起点 */
static size_t n_free_bytes; /* 未分配的字节数 */
static mem_block_t* mem_bin[MEM220_MAX_ALLOC_LOG+1]; /* 按 2^k 分箱的表头 */
static int32_t init_done = 0;
void*
mem220_allocate (size_t n_bytes)
{
size_t block_size;
int32_t bin;
mem_block_t* new_block;
if (!init_done) { mem220_init (); } /* 首次调用时初始化 */
block_size = n_bytes + sizeof (*new_block); /* 加上块头的开销 */
if (0 == n_bytes || MEM220_MAX_ALLOC < block_size) {
return NULL; /* 0 字节或超大请求 */
}
bin = log2_ceil (block_size); /* 找到 2^k 的箱子 */
if (NULL != mem_bin[bin]) { /* 箱子里有旧块？ */
new_block = mem_bin[bin]; /* 从链表头摘下来 */
mem_bin[bin] = new_block->next;
} else {
n_bytes = (1UL << bin); /* 真正分配 2^k 字节 */
if (n_bytes > n_free_bytes) { return NULL; }
new_block = (mem_block_t*)free_bytes; /* 从堆前面切一块 */
free_bytes += n_bytes;
n_free_bytes -= n_bytes;
new_block->size = n_bytes; /* 把大小写进块头 */
}
return (new_block + 1); /* 返回块头之后的数据 */
}
mem220_free 只有四行有效代码：用 mem_block[-1].size 从 ptr 前面读回块头， 算出 bin 号，再把块头插进 mem_bin[bin] 链表的表头——这就是”自由链表头插、LIFO 复用”的全部秘密。
真实运行输出（用课程自带的测试 + 一个自写驱动）:
$ gcc -g -std=c99 -Wall -Werror mem220.c mem220_test.c -o mem220_test && ./mem220_test
（无输出，退出码 0：1000 字节数据经两次 realloc 后逐字节校验全部通过）
$ ./mem220_demo
MEM220_MAX_ALLOC = 1048576 bytes
five requests of 100 bytes : small[1] - small[0] = 128 bytes （块大小 2^7）
five requests of 1000 bytes: big[1] - big[0] = 1024 bytes （块大小 2^10）
free big[1], big[3], then allocate two more:
again[0] = 0x7f4b493ffea0 ← 最后释放的 big[3] 先被复用（链表头插，LIFO）
again[1] = 0x7f4b493ff6a0
reallocate to 3000 bytes: returned 0, bytes that changed during the move: 0
interface limits: allocate(0) = (nil); allocate(1048577) = (nil);
allocate(1000000) = 0x7f4b49401aa0
这个案例把本讲的几条原则全部体现出来：① 接口与实现分离——使用者只需要四个原型， 看不到 mem_block_t 与分箱表；② static 是头文件之外的第二道墙——mem220_init 与 log2_ceil 在链接器层面就不可见；③ 头文件必须能被安全地包含多次——#if !defined(_MEM220_H) 守卫保证了这一点； ④ 值-结果参数 (value-result argument)——mem220_reallocate (void** ptr_to_ptr, size_t) 接收”指针的地址”且只在成功时改写 *ptr_to_ptr，从签名上避免了 ptr = realloc (ptr, n) 的泄漏陷阱。
常见错误与调试技巧
- 手工计算结构体大小或字段偏移：
malloc (4 + 50)之类的写法在换平台后立刻出错。 调试：用sizeof (变量)与offsetof (类型, 字段)；gcc -Wpadded会提示每个填充位置。 - 用
==比较结构体：C 不支持整体比较（a == b编译报错），手写比较又容易漏字段。 调试：写显式的比较函数；按字节比较要用memcmp (&a, &b, sizeof (a))， 但必须先用memset清零，因为填充字节不会被赋值、内容是随机的。 - 按值传递大结构体：
int32_t f (stack_t s)会复制 100 KB，栈可能直接爆掉。 调试：gcc -fstack-usage；gdb里bt后info frame。 - 混淆
.与->：s->top与(*s).top等价，而*s.top是错的（.优先级更高）。 调试：编译器会报request for member 'top' in something not a structure or union； 用gdb的p *s与p s->top交叉验证。 - 忘记写包含守卫：同一个头被间接包含两次 →
redefinition of 'struct ...'。 调试：gcc -E file.c \| grep -n "struct book_t"看预处理结果里出现了几次。 - 在不透明类型上写
p->field：报dereferencing pointer to incomplete type。 这不是 bug 而是设计生效了。调试：确认自己用的是接口函数； 若确实需要该字段，说明接口缺少一个访问函数（例如memory_system_count()），应该加函数而不是暴露字段。
关键要点
- 结构体定义只是定义类型，不分配内存；字段按定义顺序连续存放，访问即”基址 + 编译期常量偏移”。
- 编译器为对齐插入填充：
sizeof通常大于成员之和，字段顺序会影响大小；永远用sizeof而不要手算。 - C 的参数传递是按值：结构体参数会被整体复制，所以约定是传
const T*并用->（->与(*p).m等价）。 typedef让struct关键字消失，enum把整数命名化（可作switch标签、位向量与数组长度）。- 信息隐藏 = 头文件放接口 +
.c文件放表示：不透明类型让使用者只能拿句柄、调函数；mem220.h/mem220.c是这一原则在课程里的完整范例。
思考题（带答案）
问题 1：下面的结构体在 64 位 Linux/x86-64 上 sizeof 是多少？怎样改写能变小？为什么小了的版本更快也更容易缓存？
struct s_t { char a; double b; char c; int32_t d; };
答案：a 在偏移 0；double b 需 8 字节对齐，故填 7 字节，b 在 8..15；c 在 16； int32_t d 需 4 字节对齐，填 3 字节后落在 20..23 → 总大小 24。 按”大字段优先”重排为 { double b; int32_t d; char a; char c; }：b 在 0..7、d 在 8..11、 a 在 12、c 在 13，尾部补 2 字节 → sizeof = 16，省下 33%。 元素更小意味着同样大小的 cache line 能装下更多元素、遍历时 miss 更少，所以更快。
问题 2：为什么使用者拿到 memory_system_t* 之后写 ms->count 会编译失败？如果确实需要知道元素个数，应该怎么办？
答案：因为 memory_system.h 里只有 typedef struct memory_system memory_system_t; 这条前向声明， struct memory_system 是不完整类型，编译器不知道它有哪些字段、也不知道它多大， 因此无法计算 ->count 的偏移，也无法为 memory_system_t ms; 分配空间。 这正是信息隐藏的目的：使用者只能依赖接口，不能依赖内部布局， 于是实现可以在不改动使用者代码的前提下更换数据结构（例如把数组换成链表）。 需要元素个数时应当在接口里提供访问函数，本讲示例中的 memory_system_count() 就是这样一个函数； mem220 里也有类似的思路——使用者想知道块大小，只能通过接口语义（自己记住请求的字节数）， 而不该去读 ptr[-1] 那个私有块头（虽然 mem220.c 内部确实这么做了）。
问题 3：stack_push 为什么要“复制”字符串？如果改成只保存调用者传入的指针，会出现什么问题？
答案：只保存指针时，栈里存的是调用者缓冲区的地址。调用者一旦改写该缓冲区 （例如循环里反复用同一个 char buf[200] 读入新行），栈中所有元素会同时变成新内容， 栈就失去意义；若缓冲区来自 malloc，还可能产生悬空指针（第 16 讲）。 所以课程选择”push 时复制一份进栈内部”，代价是复制开销与容量上限。 这背后的取舍是：谁负责数据的生命周期——容器复制（安全但费时间/内存），还是调用者保证（快但易错）。 stack_pop 同样必须复制到调用者提供的数组里，因为栈内那份随时会被下一次 push 覆盖； 这正是”信息隐藏与性能有时互相冲突”的具体体现。