Pointers

You may have already asked the following question: ``Many of my most important and efficient data structures contain pointers. Shouldn't G2++ support pointer types so that I can transmit these data structures in my records?'' This is a very difficult problem to which no universally-acceptable solution has been found, although several interesting schemes have been put forward. Lack of ability to deal with pointers in records is a deficiency of G2++ that we hope to remedy in a future version.

We believe, however, that the presence of pointers in application data structures is not always the result of design necessity; it can also be a symptom of insufficient data hiding. When this is the case, the pointers can be eliminated from the interface, permitting the use of G2++. We illustrate this transformation below.

Consider a C program that uses pointers to implement a ``list'' data structure:

       typedef struct NODE{
           int   value;
           NODE* next;
       }NODE;
       extern NODE *first,*last;

       for(i=0;i<10;i++){
           NODE* temp = (NODE*)malloc(sizeof(NODE));
           if(last){
               last->next=temp;
               last=temp;
           }else{
               first=last=temp;
           }
           last->value=i;
       }

Next, consider the functionally equivalent C++ program which hides the identical pointer-based data structure behind a functional interface:

       class List{
       public:
           ...
           inline List();
           inline void put(int i);
           ...
       private:
           typedef struct NODE{
               int   value;
               NODE* next;
           }NODE;
           NODE *first,*last;
       };

       List::List():first(0),last(0){ }
       void List::put(int i){
           NODE* temp = new NODE;
           if(last){
               last->next=temp;
               last=temp;
           }else{
               first=last=temp;
           }
           last->value=i;
       }

       List x;
       for(i=0;i<10;i++){
           x.put(i);
       }

Note that the C++ program, although it uses the identical pointer-based internal representation, hides the pointers from client code. This means that pointers are no longer a part of the contract between the user of the type (as illustrated by the loop code) and the supplier of the type (illustrated by the body of function put()). Data hiding has an important implication for communication of List values between programs: it means that we are free to choose an external representation for lists independent of their (pointer-based) internal representation. Naturally, such an external representation will not contain any pointers.

To illustrate building the infrastructure for a pointer-based user-defined type, consider Map(C++). A Map is a container type, that is, a type whose objects contain objects of other types. Our G2++ record will contain a single Map from Time(C++) to Bits(C++). Note that since record typenames must be valid identifiers, we must use the name produced by the expansion of the Map macro, namely, Map_Time_Bits.

       mtb.g
           Map_Time_Bits   USER
                   .header Mapstuff.h
                   .isnull is_empty
           mtb     Map_Time_Bits

       Mapstuff.h
           #include <Map.h>
           #include <Time.h>
           #include <Bits.h>
           #include <iostream.h>
   

           ostream& operator<<(ostream& os,
               const Map<Time,Bits>& m);
           istream& operator>>(istream& is,
               Map<Time,Bits>& m);
   

           inline int is_empty(const Map<Time,Bits>& m){
               return m.size()==0;
           }

           mtb     2 37418482 010111 37418499 0110111

       Mapstuff.c
           #include "Mapstuff.h"
           #include "Timeio.h"
           #include "Bitsio.h"
           ostream& operator<<(ostream& os,
             const Map<Time,Bits>& m){
               os << m.size();
   

               Mapiter<Time,Bits> i(m);
               while(++i){
                   os << " ";
                   Tput(os,i.key());
                   os << " " << i.value();
               }
               os << " ";
               return os;
           }
   

           istream& operator>>(istream& is,
             Map<Time,Bits>& m){
               Time t;
               Bits b;
               int count;
               is >> count;
   

               for(int i=0;i<count;i++){
                   Tget(is,t);
                   is >> b;
                   m[t]=b;
               }
               return is;
           }

If caution is not exercised in designing an external representation, an extractor may become confused, fail to construct an object of the appropriate type, and (perhaps most seriously) consume too many characters, causing data in adjacent fields to be lost. Specifically, the designer of an external representation for type U must bear in mind that some future application may define a type T whose objects contain objects of type U. In such an application, the external representation of a U object will be embedded within an external representation of a T object. The designer cannot, in other words, depend on context (for example, the existence of a terminating newline) to determine when an external representation ends. For example, the extra blank written by the Map inserter at the end of the external representation guarantees that Bits extractor will not accidentally consume characters which happen to follow the Map representation in some unforeseen future context.