Previous: Linked List Up: Examples Next: Tree

Linked List with global pointers

If we modify List and ListNode to use global pointers, and allow the compiler to generate the transfer functions, then the code generated by the compiler would look something like this: 


struct ListNode {
  ListNode *global next;
  int data;
  ListNode(int d) { data = d; next = 0; }
  ListNode() {}  // Default constructor to be called before {\tt operator>>}
  friend CCVoid& operator<<(CCVoid&,const ListNode&);
  friend CCVoid& operator>>(CCVoid&,ListNode&);
};


struct List {
  int size;
  ListNode *global head;
  ListNode *global tail;


  List() { head = 0; tail = 0; size = 0; }  // Called before {\tt operator>>}
  void append (ListNode* nn);
  void remove();


  friend CCVoid& operator<<(CCVoid&,const List&);
  friend CCVoid& operator>>(CCVoid&,List&);
  int size;
};


CCVoid& operator<<(CCVoid& v, const ListNode& in) 
{
  v << in.next << in.data;
  return v;
}


CCVoid& operator>>(CCVoid& v, ListNode& out)
{
  v >> out.next >> out.data; 
  return v;
}


CCVoid& operator<<(CCVoid& v,const List& in)
{
  v << in.size << in.head << in.tail; 
  return v;
}


CCVoid& operator>>(CCVoid& v,List& out)
{
  v >> out.size >> out.head >> out.tail; 
  return v;
}

However, these transfer functions would not result in the list being wholly transferred to the other processor object. When a global pointer is transferred, the object it references is not. Thus, the transferred list still points to the same block of memory in the initial processor object. The transferred list would look as shown in Figure .

This is known as a shallow copy of an object. A shallow copy is one where only the object, and not memory referenced by it, is copied. In contrast, a deep copy is one where the object, and all memory referenced by it, is copied. The compiler-defined global pointer transfer is a shallow copy. Thus, if you want a deep copy, you have to write the transfer function yourself.

paolo@cs.caltech.edu