gb_save.w

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

% This file is part of the Stanford GraphBase (c) Stanford University 1993
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
@i gb_types.w

\def\title{GB\_\,SAVE}

\prerequisites{GB\_\,GRAPH}{GB\_\,IO}
@* Introduction. This GraphBase module contains the code for
two special utility routines, |save_graph| and |restore_graph|, which
convert graphs back and forth between the internal representation that is
described in {\sc GB\_\,GRAPH} and a symbolic file format that is described
below. Researchers can use these routines to transmit graphs between
computers in a machine-independent way, or to use GraphBase graphs with other
graph manipulation software that supports the same symbolic format.

All kinds of tricks are possible in the \CEE/ language, so it is
easy to abuse the GraphBase conventions and to create data structures that
make sense only on a particular machine. But if users follow the
recommended ground rules, |save_graph| will be able to transform their
graphs into files that any other GraphBase installation will be able
to read with |restore_graph|. The graphs created on remote machines will
then be semantically equivalent to the originals.

Restrictions: Strings must contain only standard printable characters, not
including \.\\ or \." or newline, and must be at most 4095 characters long;
the |g->id| string should be at most 154 characters long. All
pointers to vertices and arcs must be confined to blocks within the
|g->data| area; blocks within |g->aux_data| are not saved or restored.
Storage blocks in |g->data| must be ``pure''; that is,
each block must be entirely
devoted either to |Vertex| records, or to |Arc| records, or to
characters of strings. The |save_graph| procedure places all
|Vertex| records into a single |Vertex| block and
all |Arc| records into a single |Arc| block, preserving the
relative order of the original records where possible; but it does not
preserve the relative order of string data in memory. For example, if
|u->name| and |v->name| point to the same memory location in the saved
graph, they will point to different memory locations (representing equal
strings) in the restored graph. All utility fields must conform to
the conventions of the graph's |util_types| string; the \.G option, which
leads to graphs within graphs, is not permitted in that string.

@d MAX_SV_STRING 4095 /* longest strings supported */
@d MAX_SV_ID 154 /* longest |id| supported, is less than |ID_FIELD_SIZE| */

@(gb_save.h@>=
extern long save_graph();
extern Graph *restore_graph();

@ Here is an overview of the \CEE/ code, \.{gb\_save.c}, for this module:

@p
#include "gb_io.h" /* we use the input/output conventions of {\sc GB\_\,IO} */
#include "gb_graph.h"
 /* and, of course, the data structures of {\sc GB\_\,GRAPH} */
@h@#
@<Type declarations@>@;
@<Private variables@>@;
@<Private functions@>@;
@<External functions@>

@* External representation of graphs. The internal representation of
graphs has been described in {\sc GB\_\,GRAPH}. We now need to supplement
that description by devising an alternative format suitable for
human-and-machine-readable files.

The following somewhat contrived example illustrates the simple conventions
that we shall follow:
$$\let\par=\cr \obeylines %
\vbox{\halign{\.{#}\hfil
* GraphBase graph (util\_types IZAZZZZVZZZZSZ,3V,4A)
"somewhat\_contrived\_example(3.14159265358979323846264338327\\
9502884197169399375105820974944592307816406286208998628)",1,
3,"pi"
* Vertices
"look",A0,15,A1
"feel",0,-9,A1
"",0,0,0
* Arcs
V0,A2,3,V1
V1,0,5,0
V1,0,-8,1
0,0,0,0
* Checksum 271828
}}$$
The first line specifies the 14 characters of |util_types| and the total number
of |Vertex| and |Arc| records; in this case there are 3 vertices and
4~arcs. The next line or lines specify the |id|,
|n|, and |m| fields of the |Graph| record, together with any utility
fields that are not being ignored. In this case, the |id| is a rather
long string; a string may be broken into parts by ending the initial parts
with a backslash, so that no line of the file has more than 79 characters.
The last six characters of |util_types| refer to the utility fields of the
|Graph| record, and in this case they are \.{ZZZZSZ}; so all utility
fields are ignored except the second-to-last, |yy|, which is of type
string. The |restore_graph| routine will construct a |Graph| record~|g| from
this example in which |g->n=1|, |g->m=3|, and |g->yy.S="pi"|.

Notice that the individual field values for a record are separated by commas.
If a line ends with a comma, the following line contains
additional fields of the same record.

After the |Graph| record fields have been specified, there's a special line
`\.{*\ Vertices}', after which we learn the fields of each vertex in turn.
First comes the |name| field, then the |arcs| field, and then any
non-ignored utility fields. In this example the |util_types|
for |Vertex| records are \.{IZAZZZ}, so the utility field values are
|u.I| and |w.A|. Let |v| point to the first |Vertex| record (which incidentally
is also pointed to by |g->vertices|), and let |a| point to the first
|Arc| record. Then in this example we will have |v->name="look"|,
|v->arcs=a|, |v->u.I=15|, and |v->w.A=(a+1)|.

After the |Vertex| records comes a special line `\.{*\ Arcs}', followed by
the fields of each |Arc| record in an entirely analogous way. First
comes the |tip| field, then the |next| field, then the |len|, and finally
the utility fields (if any). In this example the |util_types|
for |Arc| utility fields are \.{ZV}; hence field |a| is ignored, and
field~|b| is a pointer to a |Vertex|. We will have |a->tip=v|, |a->next=(a+2)|,
|a->len=3|, and |a->b.V=(v+1)|.

The null pointer |NULL| is denoted by \.0. Furthermore, a |Vertex| pointer
is allowed to have the special value \.1, because of conventions
explained in {\sc GB\_\,GATES}. (This special value appears in the fourth
field of the third arc in the example above.) The |restore_graph| procedure
does not allow |Vertex| pointers to take on constant values
greater than~1, nor does it permit the value `\.1' where an |Arc|
pointer ought to be.

There should be exactly as many |Vertex| and |Arc| specifications as
indicated after the utility types at the beginning of the file.  The
final |Arc| should then be followed by a special checksum line, which
must contain either a number consistent with the data on all the previous
lines or a negative value (which is not checked).
All information after the checksum line is ignored.

Users should not edit the files produced by |save_graph|, because an
incorrect checksum is liable to ruin everything. However, additional
lines beginning with `\.*' may be placed as comments at the very
beginning of the file; such lines are immune to checksumming.

@ We can establish these conventions firmly in mind by writing the
|restore_graph| routine before we write |save_graph|. The subroutine
call |restore_graph("foo.gb")| produces a pointer to the graph
defined in file |"foo.gb"|, or a null pointer in case that file
is unreadable or incorrect. In the latter case, |panic_code|
indicates the problem.

@<External functions@>=
Graph *restore_graph(f)
  char *f; /* the file name */
{@+Graph *g=NULL; /* the graph being restored */
  register char *p; /* register for string manipulation */
  long m; /* the number of |Arc| records to allocate */
  long n; /* the number of |Vertex| records to allocate */
  @<Open the file and parse the first line; |goto sorry| if there's trouble@>;
  @<Create the |Graph| record |g| and fill in its fields@>;
  @<Fill in the fields of all |Vertex| records@>;
  @<Fill in the fields of all |Arc| records@>;
  @<Check the checksum and close the file@>;
  return g;
sorry: gb_raw_close();@+gb_recycle(g);@+return NULL;
}

@ As mentioned above, users can add comment lines at the beginning
of the file, if they put a \.* at the beginning of every such line.
But the line that precedes the data proper must adhere to
strict standards.

@d panic(c)@+{@+panic_code=c;@+goto sorry;@+}

@<Open the file...@>=
gb_raw_open(f);
if (io_errors) panic(early_data_fault); /* can't open the file */
while (1) {
  gb_string(str_buf,')');
  if (sscanf(str_buf,"* GraphBase graph (util_types %14[ZIVSA],%ldV,%ldA",
       str_buf+80,&n,&m)==3 && strlen(str_buf+80)==14) break;
  if (str_buf[0]!='*') panic(syntax_error); /* first line is unreadable */
}

@ The previous code has placed the graph's |util_types| into
location |str_buf+80| and verified that it contains precisely
14 characters, all belonging to the set $\{\.Z,\.I,\.V,\.S,\.A\}$.

@<Create the |Graph| record |g| and fill in its fields@>=
g=gb_new_graph(0L);
if (g==NULL) panic(no_room); /* out of memory before we're even started */
gb_free(g->data);
g->vertices=verts=gb_typed_alloc(n==0?1:n,Vertex,g->data);
last_vert=verts+n;
arcs=gb_typed_alloc(m==0?1:m,Arc,g->data);
last_arc=arcs+m;
if (gb_trouble_code) panic(no_room+1);
   /* not enough room for vertices and arcs */
strcpy(g->util_types,str_buf+80);
gb_newline();
if (gb_char()!='"') panic(syntax_error+1);
 /* missing quotes before graph |id| string */
p=gb_string(g->id,'"');
if (*(p-2)=='\n' && *(p-3)=='\\' && p>g->id+2) {
  gb_newline(); gb_string(p-3,'"');
}
if (gb_char()!='"') panic(syntax_error+2);
 /* missing quotes after graph |id| string */
@<Fill in |g->n|, |g->m|, and |g|'s utility fields@>;

@ The |util_types| and |id| fields are slightly different from other string
fields, because we store them directly in the |Graph| record instead of
storing a pointer. The other fields to be filled by |restore_graph|
can all be done by a macro called |fillin|, which invokes a subroutine
called |fill_field|. The first parameter
to |fillin| is the address of a field in a record; the second parameter
is one of the codes $\{\.Z,\.I,\.V,\.S,\.A\}$. A global variable
|comma_expected| is nonzero when this field is not the first in its record.

The value returned by |fill_field| is nonzero if something goes wrong.

We assume here that a utility field takes exactly as much space as
a field of any of its constituent types.
@^system dependencies@>

@d fillin(l,t) if (fill_field((util*)&(l),t)) goto sorry

@<Private f...@>=
static long fill_field(l,t)
  util *l; /* location of field to be filled in */
  char t; /* its type code */
{@+register char c; /* character just read */
  if (t!='Z'&&comma_expected) {
    if (gb_char()!=',') return (panic_code=syntax_error-1); /* missing comma */
    if (gb_char()=='\n') gb_newline();
    else gb_backup();
  }
  else comma_expected=1;
  c=gb_char();
  switch (t) {
  case 'I': @<Fill in a numeric field@>;
  case 'V': @<Fill in a vertex pointer@>;
  case 'S': @<Fill in a string pointer@>;
  case 'A': @<Fill in an arc pointer @>;
  default: gb_backup();@+break;
  }
  return panic_code;
}    

@ Some of the communication between |restore_graph| and |fillin| is best
done via global variables.

@<Private v...@>=
static long comma_expected; /* should |fillin| look for a comma? */
static Vertex *verts; /* beginning of the block of |Vertex| records */
static Vertex *last_vert; /* end of the block of |Vertex| records */
static Arc *arcs; /* beginning of the block of |Arc| records */
static Arc *last_arc; /* end of the block of |Arc| records */

@ @<Fill in a numeric field@>=
if (c=='-') l->I=-gb_number(10);
else {
  gb_backup();
  l->I=gb_number(10);
}
break;

@ @<Fill in a vertex pointer@>=
if (c=='V') {
  l->V=verts+gb_number(10);
  if (l->V>=last_vert || l->V<verts)
    panic_code=syntax_error-2; /* vertex address too big */
}@+else if (c=='0' || c=='1') l->I=c-'0';
else panic_code=syntax_error-3; /* vertex numeric address illegal */
break;

@ @<Fill in an arc pointer@>=
if (c=='A') {
  l->A=arcs+gb_number(10);
  if (l->A>=last_arc || l->A<arcs)
    panic_code=syntax_error-4; /* arc address too big */
}@+else if (c=='0') l->A=NULL;
else panic_code=syntax_error-5; /* arc numeric address illegal */
break;

@ We can restore a string slightly longer than the strings we can save.

@<Fill in a string pointer@>=
if (c!='"')
  panic_code=syntax_error-6; /* missing quotes at beginning of string */
else {@+register char* p;
  p=gb_string(item_buf,'"');
  while (*(p-2)=='\n' && *(p-3)=='\\' && p>item_buf+2 && p<=buffer) {
    gb_newline(); p=gb_string(p-3,'"'); /* splice a broken string together */
  }
  if (gb_char()!='"')
    panic_code=syntax_error-7; /* missing quotes at end of string */
  else if (item_buf[0]=='\0') l->S=null_string;
  else l->S=gb_save_string(item_buf);