Linked List Implementation in ASIC – Hardware

For node additions and deletions, a node is removed from start of list (or free list) and added into end of free list (or Port List). Snapshot of various components and lists may look like as shown in following figure.



As mentioned before, Node Allocation requires node removal from start of free list and addition to end of requestor queue. Following steps are performed to transfer a node from free list start to port list end.

  • Get Free List Start Pointer
  • Get Next Free Node Address in Free List by reading Link Memory at Free List Start address. 
  • Update Free List Start Pointer with read information from Link Memory.
  • Update Free List End Pointer, in case free list is empty
  • Create Link in Port List – Write to Link Memory at Port List End address with recent allocated Node information (Start of Free List)
  • Update Port List End Pointer
  • Update Port List Start pointer if port list was empty.

Following function implements node allocation algorithm, as outlined above for a queue. Argument to this function is queue number and function returns address of allocated buffer.

// Allocate a Node
//         * Get Buffer Address from Start of Free List
//         * Update Free List
//         * Update Port List
//         * Update Link Memory
//  Returns updated pointer
int addnode (int queue) {
  int node2badd = -999, prev_qend;
  // Get Current Free Node
  if (flStart != -999) {
    node2badd = flStart;
  } else {
    return -999;
  // Update Free List
  if (flStart == flEnd) {
    flStart = flEnd = -999;
  } else { 
    flStart = linkmem[flStart];
  // Update Queue/Port List
  if (qStart[queue] == -999) {
     qStart[queue] = node2badd;
     qEnd[queue]   = node2badd;
  } else {
     prev_qend   = qEnd[queue];
     qEnd[queue] = node2badd;
     // Update Link Memory
     linkmem[prev_qend] = node2badd;

  return node2badd;

Leave a Reply

Your email address will not be published. Required fields are marked *