gb_save.w

模拟器提供了一个简单易用的平台

}
break;

@ @d buffer (&item_buf[MAX_SV_STRING+3]) /* the last 81 chars of |item_buf| */

@<Private v...@>=
static char item_buf[MAX_SV_STRING+3+81]; /* an item to be output */

@ When all fields of a record have been filled in, we call |finish_record|
and hope that it returns~0.

@<Private f...@>=
static long finish_record()
{
  if (gb_char()!='\n')
    return (panic_code=syntax_error-8); /* garbage present */
  gb_newline();
  comma_expected=0;
  return 0;
}

@ @<Fill in |g->n|, |g->m|, and |g|'s utility fields@>=
panic_code=0;
comma_expected=1;
fillin(g->n,'I');
fillin(g->m,'I');
fillin(g->uu,g->util_types[8]);
fillin(g->vv,g->util_types[9]);
fillin(g->ww,g->util_types[10]);
fillin(g->xx,g->util_types[11]);
fillin(g->yy,g->util_types[12]);
fillin(g->zz,g->util_types[13]);
if (finish_record()) goto sorry;

@ The rest is easy.

@<Fill in the fields of all |Vertex| records@>=
{@+register Vertex* v;
  gb_string(str_buf,'\n');
  if (strcmp(str_buf,"* Vertices")!=0)@/
    panic(syntax_error+3); /* introductory line for vertices is missing */
  gb_newline();
  for (v=verts;v<last_vert;v++) {
    fillin(v->name,'S');
    fillin(v->arcs,'A');
    fillin(v->u,g->util_types[0]);
    fillin(v->v,g->util_types[1]);
    fillin(v->w,g->util_types[2]);
    fillin(v->x,g->util_types[3]);
    fillin(v->y,g->util_types[4]);
    fillin(v->z,g->util_types[5]);
    if (finish_record()) goto sorry;
  }
}

@ @<Fill in the fields of all |Arc| records@>=
{@+register Arc* a;
  gb_string(str_buf,'\n');
  if (strcmp(str_buf,"* Arcs")!=0)
    panic(syntax_error+4); /* introductory line for arcs is missing */
  gb_newline();
  for (a=arcs;a<last_arc;a++) {
    fillin(a->tip,'V');
    fillin(a->next,'A');
    fillin(a->len,'I');
    fillin(a->a,g->util_types[6]);
    fillin(a->b,g->util_types[7]);
    if (finish_record()) goto sorry;
  }
}

@ @<Check the checksum and close the file@>=
{@+long s;
  gb_string(str_buf,'\n');
  if (sscanf(str_buf,"* Checksum %ld",&s)!=1)
    panic(syntax_error+5); /* checksum line is missing */
  if (gb_raw_close()!=s && s>=0)
    panic(late_data_fault); /* checksum does not match */
}

@* Saving a graph. Now that we know how to restore a graph, once it has
been saved, we are ready to write the |save_graph| routine.

Users say |save_graph(g,"foo.gb")|; our job is to create a file
|"foo.gb"| from which the subroutine call |restore_graph("foo.gb")|
will be able to reconstruct a graph equivalent to~|g|, assuming that
|g| meets the restrictions stated earlier.  If nothing goes wrong,
|save_graph| should return the value zero.  Otherwise it should return
an encoded trouble report.

We will set things up so that |save_graph| produces
a syntactically correct file |"foo.gb"| in almost
every case, with explicit error indications written at the end of the file
whenever certain aspects of the given graph have had to be changed.
The value |-1| will be returned if |g==NULL|; the value
|-2| will be returned if |g!=NULL| but the file |"foo.gb"| could not
be opened for output; the value |-3| will be returned if memory is
exhausted. In other cases a file |"foo.gb"| will be created.

Here is a list of things that might go wrong, and the corresponding
corrective actions to be taken in each case, assuming that
|save_graph| does create a file:

@d bad_type_code 0x1 /* illegal character, is changed to |'Z'| */
@d string_too_long 0x2 /* extralong string, is truncated */
@d addr_not_in_data_area 0x4 /* address out of range, is changed to |NULL| */
@d addr_in_mixed_block 0x8 /* address not in pure block, is |NULL|ified */
@d bad_string_char 0x10 /* illegal string character, is changed to |'?'| */
@d ignored_data 0x20 /* nonzero value in |'Z'| format, is not output */ 

@<Private v...@>=
static long anomalies; /* problems accumulated by |save_graph| */
static FILE *save_file; /* the file being written */

@ @<External f...@>=
long save_graph(g,f)
  Graph *g; /* graph to be saved */
  char *f; /* name of the file to be created */
{@+@<Local variables for |save_graph|@>@;@#
  if (g==NULL || g->vertices==NULL) return -1; /* where is |g|? */
  anomalies=0;
  @<Figure out the extent of |g|'s internal records@>;
  save_file=fopen(f,"w");
  if (!save_file) return -2; /* oops, the operating system won't cooperate */
  @<Translate |g| into external format@>;
  @<Make notes at the end of the file about any changes that were necessary@>;
  fclose(save_file);
  gb_free(working_storage);
  return anomalies;
}

@ The main difficulty faced by |save_graph| is the problem of
translating vertex and arc pointers into symbolic form. A graph's
vertices usually appear in a single block, |g->vertices|, but its arcs
usually appear in separate blocks that were created whenever the
|gb_new_arc| routine needed more space. Other blocks, created by
|gb_save_string|, are usually also present in the |g->data| area.  We
need to classify the various data blocks. We also want to be able
to handle graphs that have been created with homegrown methods of
memory allocation, because GraphBase structures need not conform to
the conventions of |gb_new_arc| and |gb_save_string|.

A simple data structure based on \&{block\_rep} records will
facilitate our task.  Each \&{block\_rep} will be set up to contain
the information we need to know about a particular block of data
accessible from |g->data|. Such blocks are classified into four
categories, identified by the |cat| field in a \&{block\_rep}:

@d unk 0 /* |cat| value for blocks of unknown nature */
@d ark 1 /* |cat| value for blocks assumed to hold |Arc| records */
@d vrt 2 /* |cat| value for blocks assumed to hold |Vertex| records */
@d mxt 3 /* |cat| value for blocks being used for more than one purpose */

@<Type...@>=
typedef struct {
  char *start_addr; /* starting address of a data block */
  char *end_addr; /* ending address of a data block */
  long offset; /* index number of first record in the block, if known */
  long cat; /* |cat| code for the block */
  long expl; /* have we finished exploring this block? */
} block_rep;

@ The |block_rep| records don't need to be linked together in any fancy way,
because there usually aren't very many of them. We will simply create
an array, organized in decreasing order of |start_addr| and |end_addr|, with a
dummy record standing as a sentinel at the end.

A system-dependent change might be necessary in the following code,
if pointer values can be longer than 32 bits, or if comparisons between
pointers are undefined.
@^system dependencies@>

@<Private v...@>=
static block_rep* blocks; /* beginning of table of block representatives */
static Area working_storage;

@ Initially we set the |end_addr| field to the location following a
block's data area. Later we will change it as explained below.

The code in this section uses the fact that all bits of storage blocks
are zero until set nonzero. In particular, the |cat| field of each
|block_rep| will initially be |unk|, and the |expl| will be zero;
the |start_addr| and |end_addr| of the sentinel record will be zero.

@<Initialize the |blocks| array@>=
{@+Area t; /* variable that runs through |g->data| */
  for (*t=*(g->data),block_count=0;*t;*t=(*t)->next) block_count++;
  blocks=gb_typed_alloc(block_count+1,block_rep,working_storage);
  if (blocks==NULL) return -3; /* out of memory */
  for (*t=*(g->data),block_count=0;*t;*t=(*t)->next,block_count++) {
    cur_block=blocks+block_count;
    while (cur_block>blocks&&(cur_block-1)->start_addr<(*t)->first) {
      cur_block->start_addr=(cur_block-1)->start_addr;
      cur_block->end_addr=(cur_block-1)->end_addr;
      cur_block--;
    }
    cur_block->start_addr=(*t)->first;
    cur_block->end_addr=(char*)*t;
  }
}

@ @<Local variables for |save...@>=
register block_rep *cur_block; /* the current block of interest */
long block_count; /* how many blocks have we processed? */

@ The |save_graph| routine makes two passes over the graph. The
goal of the first pass is reconnaissance: We try to see where everything
is, and we prune off parts that don't conform to the restrictions.
When we get to the second pass, our task will then be almost trivial.
We will be able to march through the known territory and spew out a copy
of what we encounter. (Items that are ``pruned'' are not actually
removed from |g| itself, only from the portion of~|g| that is saved.)

The first pass is essentially a sequence of calls of the |lookup| macro,
which looks at one field of one record and notes whether
the existence of this field extends the known boundaries of the graph.
The |lookup| macro is a shorthand notation for calling the |classify|
subroutine. We make the same assumption about field sizes as the
|fill_field| routine did above.
@^system dependencies@>

@d lookup(l,t) classify((util*)&(l),t) /* explore field |l| of type |t| */

@<Private f...@>=
static void classify(l,t)
  util *l; /* location of field to be classified */
  char t; /* its type code, from the set $\{\.Z,\.I,\.V,\.S,\.A\}$ */
{@+register block_rep *cur_block;
  register char* loc;
  register long tcat; /* category corresponding to |t| */
  register long tsize; /* record size corresponding to |t| */
  switch (t) {
  default: return;
  case 'V': if (l->I==1) return;
    tcat=vrt;
    tsize=sizeof(Vertex);
    break;
  case 'A': tcat=ark;
    tsize=sizeof(Arc);
    break;
  }
  if (l->I==0) return;
  @<Classify a pointer variable@>;
}

@ Here we know that |l| points to a |Vertex| or
to an |Arc|, according as |tcat| is |vrt| or |ark|. We need to check that
this doesn't violate any assumptions about all such pointers lying
in pure blocks within the |g->data| area.

@<Classify a pointer variable@>=
loc=(char*)l->V;
for (cur_block=blocks; cur_block->start_addr>loc; cur_block++) ;
if (loc<cur_block->end_addr) {
  if ((loc-cur_block->start_addr)%tsize!=0 || loc+tsize>cur_block->end_addr)
    cur_block->cat=mxt;
  if (cur_block->cat==unk) cur_block->cat=tcat;
  else if (cur_block->cat!=tcat) cur_block->cat=mxt;
}

@ We go through the list of blocks repeatedly until we reach a stable
situation in which every |vrt| or |ark| block has been explored.

@<Figure out the extent of |g|'s internal records@>=
{@+long activity;
  @<Initialize the |blocks| array@>;
  lookup(g->vertices,'V');
  lookup(g->uu,g->util_types[8]);
  lookup(g->vv,g->util_types[9]);
  lookup(g->ww,g->util_types[10]);
  lookup(g->xx,g->util_types[11]);
  lookup(g->yy,g->util_types[12]);
  lookup(g->zz,g->util_types[13]);
  do@+{@+activity=0;
    for(cur_block=blocks;cur_block->end_addr;cur_block++) {
      if (cur_block->cat==vrt && !cur_block->expl)
        @<Explore a block of supposed vertex records@>@;
      else if (cur_block->cat==ark && !cur_block->expl)
        @<Explore a block of supposed arc records@>@;
      else continue;
      cur_block->expl=activity=1;
   }
  }@+while (activity);
}

@ While we are exploring a block, the |lookup| routine might classify
a previously explored block (or even the current block) as |mxt|.
Therefore some data we assumed would be accessible will actually be
removed from the graph; contradictions that arose might no longer exist.
But we plunge ahead anyway, because we aren't going to try especially
hard to ``save'' portions of graphs that violate our ground rules.

@<Explore a block of supposed vertex records@>=
{@+register Vertex*v;
  for (v=(Vertex*)cur_block->start_addr;@|