思路.md

初始化

• 初始化调用下面这个函数

  struct buddy *buddy_new(int size) {
    struct buddy *self;
    int node_size, i; 
    
    if (size < 1 || !IS_POWER_OF_2(size)) {
      return NULL;
    }
    
    self = (struct buddy *) malloc(2 * size * sizeof(char)); 
    
    self->size = convert(size);
    node_size = self->size + 1; 
    
    for (i = 0; i < 2 * size - 1; i++) {
      if (IS_POWER_OF_2(i + 1))
        node_size = node_size - 1;
      self->longest[i] = (char) node_size;
    }
    
    return self;
  }

• 判断输入的 size 是否合法、为其分配内存、随后初始化每个节点。

分配

• 分配内存空间调用下面这个函数

  int buddy_alloc(struct buddy *self, int size) {
    unsigned index = 0, offset = 0;
    char node_size;
    int lg_size;
    
    if (self == NULL || size <= 0) {
      return -1;
    }
    
    if (!IS_POWER_OF_2(size)) {
      size = fix_size((unsigned int) size);
    }
    
    lg_size = convert(size);
    
    if (self->longest[index] < lg_size)
      return -1;
    
    for (node_size = self->size; node_size != lg_size; node_size -= 1) {
      if (self->longest[LEFT_LEAF(index)] >= lg_size) {
        index = LEFT_LEAF(index);
      } else {
        index = RIGHT_LEAF(index);
      }
    }
    
    self->longest[index] = -1;
    offset = (index + 1) * (1 << node_size) - (1 << self->size);
    
    while (index != 0) {
      index = PARENT(index);
      self->longest[index] = MAX(self->longest[LEFT_LEAF(index)], 
                                 self->longest[RIGHT_L    EAF(index)]);
    }
    return offset;
  }

• 判断输入的数据是否合法
• 判断输入的数据是否大于可分配的块数
• 从第一层开始遍历，如果该层的大小和请求分配块的大小相同，则退出循环。循环的过程中通过判断子节点的大小和请求分配块的大小来选择可分配的块。
• 将该节点的空间大小设置为0（代码中设置为 -1，因为实际存储的是一个数的次幂)。
• 计算偏移量。
• 从该节点开始，进行回溯，不断改变父节点可分配块的大小。
• 返回偏移量。

收回

• 收回内存空间调用下面这个函数

  void buddy_free(struct buddy *self, int offset) {
    int node_size, index;
    char left_longest, right_longest;
    
    assert(self && offset >= 0 && offset < self->size);
    
    node_size = 0;
    index = (1 << self->size) - 1 + offset;
    
    for (; self->longest[index] != -1; index = PARENT(index)) {
      node_size = node_size + 1;
      if (index == 0)
        return;
    }
    
    self->longest[index] = (char) node_size;
    
    while (index) {
      index = PARENT(index);
      node_size = node_size + 1;
      
      left_longest = self->longest[LEFT_LEAF(index)];
      right_longest = self->longest[RIGHT_LEAF(index)];
      
      if (left_longest == right_longest && node_size - left_longest == 1) {
        self->longest[index] = (char) node_size;
      } else {
        self->longest[index] = MAX(left_longest, right_longest);
      }
    }
  }

• 从叶子节点开始向根节点遍历，如果该节点的空间大小为零，则意味着找到了该节点。
• 将节点的大小设置为那一层节点的大小。
• 从该节点出发不断的更新父节点的值，当父节点的两个子节点的空间的和等于父节点的空间的和，则意味着两个子节点中为可分配空间，因此可以将父节点的值设置为该层节点的空间大小。否则父节点的大小是两个子节点中较大的那个节点的大小。