Node Deletion/Deallocation requires node removal from start of port list and addition to end of free list. Following steps are performed to move a node from free list start to port list end.

• Get Port List Start Pointer
• Get Next Port Node address in Port List by reading Link Memory at Port List Start address. 
• Update Port List Start Pointer with read information from Link Memory.
• Update Port List End Pointer, in case port list is empty
• Create Link in Free List - Write to Link Memory at Free List End address with recently Freed Node information.
• Update Free List End Pointer
• Update Free List Start pointer if Free list was empty.

// Free a Node
//         * Get Buffer Address from Start of Queue List
//         * Update Queue List
//         * Update Free List
//         * Update Link Memory
//  Returns updated pointer

int freenode (int queue) {
  int node2bfree = -999;
  int queue_start = qStart[queue], queue_end = qEnd[queue];

  // Get Current Node
  if (queue_start != -999) {
    node2bfree = queue_start;
  } else {
    return -999;
  }

  // Update queue List
  if (queue_start == queue_end) {
    qStart[queue] = qEnd[queue] = -999;
  } else {
    qStart[queue] = linkmem[queue_start];
  }

  // Update Freelist
  if (flStart == -999) {
     flStart = node2bfree;
     flEnd   = node2bfree;
  } else {
     // Update Link Memory
     linkmem[flEnd] = node2bfree;
     flEnd = node2bfree;
  }

  return node2bfree;
}

A debug function is provided to calculate the length of a given list. Any number other than -999 points to port/queue list and -999 means Free List. This function parses through Link Memory for the queue pointed by num and calculates queue size, as explained in following ANSI C code snippet.

// Check Queue Size

// num = -999 is Free List else it is queue pointed by 'num'

int checkq (int num) {
   int start, end, cur;
   int  i = 1;

   if (num == -999) {
     start = flStart;
     end   = flEnd;
   } else {
     start = qStart[num];
     end   = qEnd[num];
   }

   if (start == -999) {
      if (num == -999)
        printf ("Length of Free List - 0\n");
      else
        printf ("Length of List %d - 0\n", num);
      return 0;
   } else if(start == end) {
      if (num == -999)
        printf ("Length of Free List - 1\n");
      else
        printf ("Length of List %d - 1\n", num);
      return 1;
   }

   for (cur = start; cur != end; cur=linkmem[cur]) i++;
 
   if (num == -999)
     printf ("Length of Free List - %d\n", i);
   else
     printf ("Length of List %d - %d\n", num, i);

   return i;

} 

Following code squence is used to model and verify Link List implementation in ASIC/Hardware. First, Link List initialization is performed and few node additions/deletions are performed for each queue. Then, a loop is executed for 500 times and random node additions/deletions are performed. At each stage, debug function is called to print status information.

   int i, queue_size[NUM_QUE];

   int q2add, q2del;

   init ();
   checkq(-999);

   for (i = 0; i < NUM_QUE; i++) {
     addnode(i);
     addnode(i);
     queue_size[i] = 2;
   }

   checkq(-999);
   for (i = 0; i < NUM_QUE; i++) checkq(i);

   for (i = 0; i < NUM_QUE; i++) {
     freenode(i);
     queue_size[i]--;
   }

   checkq(-999);
   for (i = 0; i < NUM_QUE; i++) checkq(i);

   for (i = 0; i < 500; i++) {
     q2add = random()%NUM_QUE;
     addnode(q2add);
     queue_size[q2add]++;

     // Make sure that queue has valid data
     q2del = random()%NUM_QUE;
     if (queue_size[q2del] > 0) {
       freenode(q2del);
       queue_size[q2del]--;
     }
   }

   checkq(-999);
   for (i = 0; i < NUM_QUE; i++) {
     checkq(i);
     printf ("%d -- %d\n", i, queue_size[i]);
   }

Another check can be added to above code sequence based on List Size. Combined Length of all lists should be same as NUM_BUF always, otherwize implementation is not correct and there is a memory leak issue in the system.