// 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;
}
