struct chunk {
unsigned int power;
unsigned int start;
struct chunk next;
struct chunk prev;
};

void init() {
for (int i = 0; i < 11; i++) {
free_area[i] = NULL;
}

struct chunk maxChunk = (struct chunk)malloc(sizeof(struct chunk));
maxChunk->power = 19; // 1MB
maxChunk->start = 0;
maxChunk->next = NULL;
maxChunk->prev = NULL;

free_area[8] = maxChunk;
}
struct chunk pick(unsigned int k) {
struct chunk c = NULL;
struct chunk left = NULL;
struct chunk right = NULL;

for (int i = k; i <= 10; i++) {
if (free_area[i] != NULL) {
c = free_area[i];
break;
}
}

if (c == NULL) {
printf(“fail to pick up a chunk\n”);
return 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 = NULL;
left->prev = NULL;
// 将left加入free_area[j]
// …

right = (struct chunk*)malloc(sizeof(struct chunk));
right->power = c->power - 1;
right->start = c->start + (1 << right->power);
right->next = NULL;
right->prev = NULL;
// 将right加入free_area[j]
// ...

// 释放c占据的内存
free(c);

c = right;

}

return c;
}
struct chunk* allocate(unsigned int req) {
unsigned int power = 12; // 4KB
unsigned int size = 4096;

while (size < req) {
power++;
size *= 2;
}

return pick(power);
}
void check() {
for (int i = 0; i < 11; i++) {
printf(“Free area %d:\n”, i);
struct chunk* current = free_area[i];
while (current != NULL) {
printf(“Power: %d, Start: %d\n”, current->power, current->start);
current = current->next;
}
printf(“\n”);
}
}
int main() {
init();
check();

struct chunk c100 = allocate(100 * 1024); // 100KB
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

TARGET = buddy_system
SRCS = buddy_system.c
OBJS = $(SRCS:.c=.o)

.PHONY: all clean

all: $(TARGET)

(TARGET):
(OBJS)
(CC)
(CFLAGS) -o @
^

%.o: %.c
(CC)
(CFLAGS) -c -o @
<

clean:
rm -f (TARGET)
(OBJS)