# 动态内存分配器实验修改思路

## 实验目标
实现一个动态内存分配器，支持以下功能：
1. 内存分配（`mm_malloc`）
2. 内存释放（`mm_free`）
3. 内存扩展（`mm_realloc`）

并通过 `traces` 目录下的测试用例，尽可能提高评分。

## 修改内容

### 1. 算法设计思想
- 使用 **隐式空闲链表** 管理内存块。
- 每个块包含头部和尾部，用于存储块大小和分配状态。
- 分配时，使用 **首次适配算法** 找到合适的空闲块。
- 释放时，合并相邻的空闲块以减少内存碎片。
- 通过对齐和块分割优化内存利用率。

### 2. 代码实现
#### 主要宏定义
- `PACK(size, alloc)`：将块大小和分配位打包成一个字。
- `GET` 和 `PUT`：读取和写入地址处的字。
- `HDRP` 和 `FTRP`：计算块的头部和尾部地址。
- `NEXT_BLKP` 和 `PREV_BLKP`：计算下一个和前一个块的地址。

#### 核心函数
1. **`mm_init`**
   - 初始化堆，创建序言块和结尾块。
   - 扩展堆以初始化空闲块。

2. **`extend_heap`**
   - 扩展堆的大小，分配新的空闲块。
   - 初始化新块的头部、尾部和结尾块。

3. **`coalesce`**
   - 合并相邻的空闲块，减少内存碎片。
   - 根据前后块的分配状态，处理 4 种情况。

4. **`mm_malloc`**
   - 调整请求大小以满足对齐要求。
   - 使用 `find_fit` 查找合适的空闲块。
   - 如果没有合适的块，扩展堆。

5. **`mm_free`**
   - 将块标记为空闲。
   - 调用 `coalesce` 合并相邻空闲块。

6. **`mm_realloc`**
   - 如果新大小小于当前块大小，直接返回。
   - 如果新大小大于当前块大小，分配新块并复制数据。

7. **`find_fit`**
   - 遍历隐式链表，找到第一个满足大小要求的空闲块。

8. **`place`**
   - 将请求大小的块放入空闲块中。
   - 如果剩余空间足够大，分割块。

### 3. 测试与优化
- 修改 `TRACE_LIST.txt`，运行不同的 trace 文件。
- 使用 `make` 和 `./malloc -t traces` 测试实现。
- 优化分配和释放逻辑，提高效率和性能。

## 当前状态
- **正确性**：所有 trace 文件均通过测试。
- **效率**：平均效率为 77%。
- **性能**：评分为 84/100。

## 后续优化方向
1. 使用 **显式空闲链表** 或 **分离空闲链表** 提高查找效率。
2. 动态调整堆扩展策略，减少不必要的扩展。
3. 优化块分割和合并逻辑，进一步减少内存碎片。

## 提交要求
- 将 `mm.c` 文件重命名为 `mm_学号.c`，并提交到指定平台。