include [HTML_REMOVED]

include [HTML_REMOVED]

// 描述一个空闲伙伴内存块的数据结构
struct chunk {
unsigned int power; // 内存块大小的2次幂指数
unsigned int start; // 内存块的起始地址
struct chunk next; // 后向指针
struct chunk prev; // 前向指针
};

// free_area数组，用于组织空闲伙伴内存块
struct chunk* free_area[11];

// 判断两个chunk是否是伙伴
int isBuddy(struct chunk c1, struct chunk c2) {
if (c1->power != c2->power)
return 0;
if ((c1->start ^ c2->start) >> c1->power != 1)
return 0;
return 1;
}

// 初始化操作
void init() {
for (int i = 0; i < 11; i++) {
free_area[i] = NULL;
}
// 假定最大内存为1MB，创建一个描述该块的数据结构
struct chunk max_chunk = (struct chunk)malloc(sizeof(struct chunk));
max_chunk->power = 22;
max_chunk->start = 0;
max_chunk->next = NULL;
max_chunk->prev = NULL;
free_area[10] = max_chunk;
}

// 从free_area[k]摘取一个内存块
struct chunk pick(unsigned int k) {
struct chunk c = NULL;
struct chunk left = NULL;
struct chunk right = NULL;
int i;
for (i = k; i <= 10; i++) {
if (free_area[i] != NULL) {
c = free_area[i];
break;
}
}
if (i > 10) {
printf(“Fail to pick up a chunk\n”);
return NULL;
}
// 从free_area[i]链表中移除c
if (c->prev != NULL) {
c->prev->next = c->next;
}
if (c->next != NULL) {
c->next->prev = c->prev;
}
c->prev = NULL;
c->next = NULL;
// 把c进行二分解
for (int j = i - 1; j >= k; j–) {
left = (struct chunk*)malloc(sizeof(struct chunk));
left->power = c->power - 1;
left->start = c->start;
left->next = free_area[j];
if (free_area[j] != NULL) {
free_area[j]->prev = left;
}
free_area[j] = left;

    right = (struct chunk*)malloc(sizeof(struct chunk));
    right->power = c->power - 1;
    right->start = c->start + (1 << right->power);
    right->prev = NULL;
    right->next = NULL;

    free(c);
    c = right;
}
return c;

}

// 分配内存块
struct chunk* allocate(unsigned int req) {
unsigned int power = 0;
while ((1 << power) < req) {
power++;
}
if (power < 12) {
power = 12;
}
return pick(power - 12);
}

// 回收内存块
void release(struct chunk c) {
int power = c->power;
struct chunk buddy;
while (power < 10) {
unsigned int buddy_start = c->start ^ (1 << power);
buddy = free_area[power];
while (buddy != NULL) {
if (buddy->start == buddy_start) {
break;
}
buddy = buddy->next;
}
if (buddy == NULL) {
break;
}
// 合并c和buddy
if (c->start < buddy->start) {
c->power;
c->next = buddy->next;
if (buddy->next != NULL) {
buddy->next->prev = c;
}
} else {
buddy->power;
buddy->next = c->next;
if (c->next != NULL) {
c->next->prev = buddy;
}
c = buddy;
}
power++;
}
c->prev = NULL;
c->next = free_area[power];
if (free_area[power] != NULL) {
free_area[power]->prev = c;
}
free_area[power] = c;
}

// 打印free_area[]列表及其关联的链表
void check() {
for (int i = 0; i < 11; i++) {
printf(“free_area[%d]: “, i);
struct chunk* c = free_area[i];
while (c != NULL) {
printf(“power=%d, start=0x%08x -> “, c->power, c->start);
c = c->next;
}
printf(“NULL\n”);
}
printf(“\n”);
}

int main() {
init(); // 初始化操作
check();

struct chunk* c100 = allocate(100 * 1024);  // 分配100K
struct chunk* c256 = allocate(256 * 1024);  // 分配256KB内存
struct chunk* c500 = allocate(500 * 1024);  // 分配500KB内存
check();

release(c100);  // 回收内存块
release(c256);
release(c500);
check();

return 0;

}

CC = gcc
CFLAGS = -Wall -Wextra -g

TARGET = buddy_system

all: $(TARGET)

$(TARGET): buddy_system.c $(CC) $(CFLAGS) -o $@ $^

clean:
rm -f $(TARGET)