link list-小專題-記憶體管理-free

// move the nth node out from occupied list
MemInfo *move_out(int n)
{
   MemInfo *rush = head_occupy;
   // get the nth node
   while (n != 0) {
      rush = rush->next;
      n--;
   }
   // prev->rush->next
   // prev->next
   if (rush->next != NULL)
      rush->next->prev = rush->prev;
   if (rush == head_occupy)
      head_occupy = rush->next;
   else
      rush->prev->next = rush->next;
   return rush;
}

// move node to free list
void free_(MemInfo *node)
{
   MemInfo *rush, *prev;
   // initialize rush as head
   rush = head_free;
   // find out the position where node should
   // be put in
   while (rush->begin < node->begin) {
      prev = rush;
      rush = rush->next;
   }
   // if this node should be put in the first place
   if (rush == head_free) {
      // if rush is right after node
      if (rush->begin == node->begin + node->size) {
         // then merge them together
         rush->begin = node->begin;
         rush->size += node->size;
      }
      // otherwise
      else {
         node->next = rush;
         node->prev = NULL;
         rush->prev = node;
         head_free = node;
      }
   }
   // if node is right after prev
   else if (prev->begin + prev->size == node->begin) {
      // merge them together
      prev->size += node->size;
      // if they are connected together
      if (prev->begin + prev->size == rush->begin) {
         prev->size += rush->size;
         prev->next = rush->next;
         if (rush->next != NULL)
            rush->next->prev = prev;
      }
   }
   // else, connect them
   else {
      node->next = rush;
      node->prev = prev;
      rush->prev = node;
      prev->next = node;
   }

}

free_()這個function是要free掉一個已經使用的node。因此為了示範，我們必須從occupied的list中拿出一個node出來free掉。

因此這邊我們就寫了一個function：move_out()，它將會從occupied list中移出第n個node出來。

我們declare一個pointer rush讓它從head_occupy開始去找第n個node，然後用while迴圈去判斷是否到達第n個node：

   MemInfo *rush = head_occupy;
   // get the nth node
   while (n != 0) {
      rush = rush->next;
      n--;
   }

因此這邊的rush就會是第n個node，當然最好的判斷式應當是：

while(rush != NULL &&n != 0) {
   rush = rush->next;
   n--;
}
if (n != 0) {
   printf("occupied list doesn't has %d elements!\n", n);
   return;
}

否則如果這個occupied list根本就不足n個element的時候，rush將不會是well defined的指標，它將會跑到NULL去，接著rush->next將會不存在。

接著稍微注意尾端與前端之後，就該把rush這個node從中移除掉：

   if (rush->next != NULL)
      rush->next->prev = rush->prev;
   if (rush == head_occupy)
      head_occupy = rush->next;
   else
      rush->prev->next = rush->next;

最後return rush便完成了我們要的move_out的function，也就是初步的free就應當先把node移出去。
接著這個移出去的node將會放到free的list上。但是要放在哪裡就必須取決於它的位置begin。因此在free_()中我們需要一個迴圈，為了找出適當的位置：

   while (rush->begin < node->begin) {
      prev = rush;
      rush = rush->next;
   }

如果有找到適當的位置，那麼rush將會是下一個節點，同時prev將會是上一個節點。

接著我們開始判斷位置對應關係，首先如果這個node的begin於free的list中是最小的，那麼它該置放在head的位置：

   if (rush == head_free) {
      // if rush is right after node
      if (rush->begin == node->begin + node->size) {
         // then merge them together
         rush->begin = node->begin;
         rush->size += node->size;
      }
      // otherwise
      else {
         node->next = rush;
         node->prev = NULL;
         rush->prev = node;
         head_free = node;
      }
   }

這時候我們必須要注意的一點就是，如果rush正好記憶體的位置是接在node的後端的話，那麼我們就直接將這兩個node整併成同一個node：

      if (rush->begin == node->begin + node->size) {
         // then merge them together
         rush->begin = node->begin;
         rush->size += node->size;
      }

而如果中間有斷層的話，就不用這樣處理，就直接linked list接上去就可以了：

      else {
         node->next = rush;
         node->prev = NULL;
         rush->prev = node;
         head_free = node;
      }

要注意的是head的前端是NULL，而這邊由於NODE是最小的位置因此他將會是head。

接下來：

   else if (prev->begin + prev->size == node->begin) {
      // merge them together
      prev->size += node->size;
      // if they are connected together
      if (prev->begin + prev->size == rush->begin) {
         prev->size += rush->size;
         prev->next = rush->next;
         if (rush->next != NULL)
            rush->next->prev = prev;
      }
   }

如果他並非擺在head的位置，但是它正巧在記憶體中的位置是在prev的後方接密緊鄰，那麼它應當要跟prev併為同一個node：

      prev->size += node->size;

同時要注意的是，如果這時後面那一個node如果正好也緊密接鄰的話，同樣我們把後面的node與前方已併完的node再次併一次：

      if (prev->begin + prev->size == rush->begin) {
         prev->size += rush->size;
         prev->next = rush->next;
         if (rush->next != NULL)
            rush->next->prev = prev;
      }

這時後要注意的是prev的next指向的地方需要改正。那麼為什麼上一次處裡不需要改正prev->next = node->next呢? 因為node並沒有next，而且prev的next並不需要改。最後的if就是判斷是否為尾端，如果不是尾端我們再行處理，否則NULL的prev是沒有定義的。

最後，如果並沒有併攏情形，那麼就正常處理，前面與node結合，後面與node結合：

   else {
      node->next = rush;
      node->prev = prev;
      rush->prev = node;
      prev->next = node;
   }