link list-小專題-記憶體管理-best fit allocation

// allocate a memory in a linked list by best fit
MemInfo *best_fit_mem_alloc(unsigned size)
{
   MemInfo *best_fit = NULL, *data, *rush;
   // record the smallest difference
   int smallest_diff = INT_MAX;
   // assigned this from head node for un-used memory
   rush = head_free;
   // find out the best fit
   while (rush != NULL) {
      if (rush->size > size &&
                (rush->size - size) < smallest_diff) {
         smallest_diff = rush->size - size;
         best_fit = rush;
      }
      rush = rush->next;
   }
   // if we could find out the best fit
   if (best_fit != NULL) {
      // allocate a memory
      data = (MemInfo*) malloc(sizeof(MemInfo));
      data->begin = best_fit->begin;
      data->size = size;
      if (best_fit->size > size) {
         best_fit->begin += size;
         best_fit->size -= size;
      }
      else {
         // jusdge if this is head
         if (best_fit == head_free)
            head_free = best_fit->next;
         else
            best_fit->prev->next = best_fit->next;
         // if this is not tail
         if (best_fit->next != NULL)
            best_fit->next->prev = best_fit->prev;
         free(best_fit);
      }
   }
   return (data);
}

基本上best fit和first fit整體的程式邏輯是相同的，唯一不同的地方就是前面要尋找出最適合大小的size的node而已。因此這邊就導入了一個pointer: rush專門用來當成是迴圈從head跑到最後。唯有這種方式才能找到最適合大小的size。

因此我們修改下while的條件為rush != NULL表示rush要從頭跑到尾，然後best_fit的指標就是專門記載"目前最適合的node"的位置，我們並添加了一個smallest_diff就是專門記載"目前最適合的node"的size和我們需要大小的差異。差異越小的越是滿足最適合大小的要件：

   while (rush != NULL) {
      if (rush->size > size &&
                (rush->size - size) < smallest_diff) {
         smallest_diff = best_fit->size - size;
         best_fit = rush;
      }
      rush = rush->next;
   }

所以我們這邊就多添加了一個if就是專門記載best_fit以及smallest_diff，記錄最適合大小的pointer以及size差異值。如果目前的node: rush的size比我們要allocate的size還大，並且size的差異呢，還比上一筆best_fit的差異還小的話，那麼它就會比上一筆best_fit還更適合當最適合大小的node。這邊的邏輯便然是如此。

接下來的程式就會和first fit是一模一樣的做法，詳情就請參考上一篇的first fit allocation。