Storage Pool

• Also called AV-List (Available List)
• Collection of free nodes

Why I need this?

當node要delete，做memory release?

• 做
  • 每次都要call destructor來delete掉。
  • memory需要很計較的時候。
• 不做
  • 把要release的node先存成available linked list，之後要new node時就不用再要記憶體，直接先從AV-List裡去拿。
  • 因為要new一塊可用的記憶體是需要system call的timimg cost。

Implementation

Two functions needed:

• getNode: 從 AV-list 中取得一 free node，AV-list 要順移一位。
  • $O(1)$
• retNode(): 插入一 free node 到 AV-list 中，大部份是串到 head。
  • $O(1)$

Nodeptr getNode {
    Nodeptr p = avail;
    if (p != NULL)
        avail = avail->link;
    return p;
}

void retNode(Nodeptr x) {
    x->link = avail;
    avail = x;
}

Advantages

• Reduce memory allocation and release operations.
• Usually implemented in single linked list.