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

#define MAX_PAGES 1024

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

struct chunk* free_area[11];

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;
    }
    struct chunk* max_chunk = malloc(sizeof(struct chunk));
    max_chunk->power = 20;
    max_chunk->start = 0;
    free_area[8] = max_chunk;
}

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];
        free_area[i] = c->next;
            break;
         }
    }
        if (i > 10) {
            printf("fail to pick up a chunk\n");
            return NULL;
        }


    // 把c进行二分解
    for (int j = i - 1; j >= k; j--) {
        left = malloc(sizeof(struct chunk));
        left->power = c->power - 1;
        left->start = c->start;
        left->next = NULL;
        left->prev = NULL;
        if (free_area[j] != NULL) {
            free_area[j]->prev = left;
        }
        free_area[j] = left;

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

        free(c);
        c = right;

    }
    return c;
}

struct chunk* allocate(unsigned int req) {
    unsigned int power = 0;
    if (req == 0) return NULL;
    if (req < 4 * 1023) return pick(0);
    while ((1 << power) < req) {
        power++;
    }
    return pick(power - 12);
}

void release(struct chunk* c) {
    unsigned int k = c->power - 12;
    struct chunk* buddy = NULL;
    int merged  = 1;


  // 循环合并 c 与其伙伴块
  while (merged) {
    // 判断是否需要继续合并
    merged = 0;

    // 获取 c 的伙伴块
    buddy = free_area[k];

    // 如果 c 与其伙伴块相邻，则合并
    while(buddy != NULL) {
    if (isBuddy(c, buddy)) {
    c->power ++;    
      // 将 buddy 移出 free_area[k]
      if (buddy->prev == NULL) {
        free_area[k] = buddy->next;
      } else {
        buddy->prev->next = buddy->next;
      }
      if (buddy->next != NULL) {
        buddy->next->prev = buddy->prev;
      }

      // 将 c 与 buddy 合并
      if (c->start > buddy->start) {
        c->start = buddy->start;
      }
      free(buddy);
      merged = 1;
      k++;
      break;
    }
    buddy = buddy ->next;
    }
  }

  c -> next = free_area[k];
   if (free_area[k] != NULL) free_area[k] -> prev = c;
  free_area[k] = c;

}
void check() {
    printf("Free Area:\n");
    for (int i = 0; i < 11; i++) {
        printf("Free Area[%d]: ", i);
        struct chunk* chunk = free_area[i];
        while (chunk != NULL) {
            printf("power=%d, start=%x -> ", chunk->power, chunk->start);
            chunk = chunk->next;
        }
        printf("NULL\n");
    }
    printf("\n");
}

int main() {
    init();
    check();
    struct chunk* c100 = allocate(100 * 1024);
    check();    
    struct chunk* c256 = allocate(256 * 1024);
    check();
    struct chunk* c500 = allocate(500 * 1024);
    check();
    release(c100);
    check();
    release(c256);
    check();
    release(c500);
    check();

    return 0;
}