| 1 |
<html> |
| 2 |
<body> |
| 3 |
<center> |
| 4 |
<pre> |
| 5 |
/* Copyright 2009, UCAR/Unidata and OPeNDAP, Inc. |
| 6 |
See the COPYRIGHT file for more information. */ |
| 7 |
</pre> |
| 8 |
<h1>NCGEN Internals Documentation</h1> |
| 9 |
<h3>Draft: 03/07/2009<br> |
| 10 |
Last Revised: 07/15/2009</h3> |
| 11 |
</center> |
| 12 |
|
| 13 |
<h1><u>Introduction</u></h1> |
| 14 |
This document is an ongoing effort to |
| 15 |
describe the internal operation of the ncgen |
| 16 |
cdl compiler; ncgen is a part of the netcdf |
| 17 |
system. |
| 18 |
<p> |
| 19 |
The document has two primary parts. |
| 20 |
<ol> |
| 21 |
<li><a href="#LANG">Language Support</a> |
| 22 |
-- describes how to add a new output language to ncgen. |
| 23 |
<p> |
| 24 |
<li><a href="#GIT">General Internals Information</a> |
| 25 |
-- describes additional information about the internals; |
| 26 |
parsing, for example. |
| 27 |
</ol> |
| 28 |
|
| 29 |
<h1></u><a name="LANG">Modifying NCGEN to Output a New Language</a></u></h1> |
| 30 |
|
| 31 |
This document outlines the general method for adding |
| 32 |
a new language output to ncgen. Currently, it supports |
| 33 |
binary, C, and (experimentally) NcML and Java. |
| 34 |
Before reading this document, the reader should also |
| 35 |
review the internals.html document. |
| 36 |
<p> |
| 37 |
Also, the reader should note that code is a bit crufty |
| 38 |
and needs refactoring. This is primarily because |
| 39 |
it was originally defined to support only C and |
| 40 |
each new language stresses the code. |
| 41 |
<p> |
| 42 |
In order to get ncgen to generate output for a new |
| 43 |
language, the following steps are required. |
| 44 |
|
| 45 |
<ol> |
| 46 |
<li> <a href="#Misc">Modify various files to invoke the new language output.</a> |
| 47 |
<li> <a href="#Create">Create a new set of generate functions.</a> |
| 48 |
</ol> |
| 49 |
|
| 50 |
<h2><a name="Misc">Modify various files to invoke the new language output.</a></h2> |
| 51 |
The following steps are required to provide the necessary code |
| 52 |
to invoke a new language output. |
| 53 |
For the purposes of this discussion, let us call the language Java. |
| 54 |
|
| 55 |
<h4>ncgen.h</h4> |
| 56 |
<ol> |
| 57 |
<li> Locate the code enabler #defines |
| 58 |
(e.g. <code>#define ENABLE_C</code>) |
| 59 |
and insert a new one of the form |
| 60 |
<pre> |
| 61 |
#define ENABLE_JAVA |
| 62 |
</pre> |
| 63 |
</ol> |
| 64 |
|
| 65 |
<h4>main.c</h4> |
| 66 |
<ol> |
| 67 |
<li> Locate the global declaration (<code>int fortran_flag;</code>) |
| 68 |
and insert a new declaration. |
| 69 |
<pre>int java_flag;</pre> |
| 70 |
|
| 71 |
<li> Locate the initialization (<code>fortran_flag = 0;</code>) |
| 72 |
in the body of the main() procedure and add a new initialization. |
| 73 |
<pre>java_flag = 0;</pre>. |
| 74 |
|
| 75 |
<li>Locate the options processing switch case for -l (<code>case 'l':</code>). |
| 76 |
Duplicate one of the instances there and add to the conditionals. |
| 77 |
It should look like this. |
| 78 |
<pre> |
| 79 |
} else if(strcmp(lang_name, "java") == 0 |
| 80 |
|| strcmp(lang_name, "Java") == 0) {java_flag = 1;} |
| 81 |
</pre> |
| 82 |
|
| 83 |
<li> Just after the options processing switch code, |
| 84 |
there are a number of #ifndef conditionals |
| 85 |
(e.g. <code>#ifndef ENABLE_C</code>). |
| 86 |
Add a new one for Java. |
| 87 |
It should look like this. |
| 88 |
<pre> |
| 89 |
#ifndef ENABLE_JAVA |
| 90 |
if(java_flag) { |
| 91 |
fprintf(stderr,"Java not currently supported\n"); |
| 92 |
exit(1); |
| 93 |
} |
| 94 |
#endif |
| 95 |
</pre> |
| 96 |
</ol> |
| 97 |
|
| 98 |
<h2><a name="Create">Create a new set of generate functions.</a></h2> |
| 99 |
The hard part is creating the actual code generation files. |
| 100 |
To do this, it is easiest to take one of the existing |
| 101 |
generators and modify it, viz: |
| 102 |
<ul> |
| 103 |
<li> copy genc.c genj.c |
| 104 |
<li> copy cdata.c jdata.c |
| 105 |
</ul> |
| 106 |
The genj.c file will do most of the code generation. The jdata.c file |
| 107 |
will generate lists of data constants that come from the CDL data: section. |
| 108 |
There is nothing magical about using two files: they can be refactored |
| 109 |
as desired. |
| 110 |
<p> |
| 111 |
In order to facilitate code generation, it is useful to look |
| 112 |
at the translations produced by other languages. |
| 113 |
The idea is to take these translations and decide what the |
| 114 |
corresponding Java (for example) code would look like. |
| 115 |
Then the idea is to modify the genc code (in genj.c) |
| 116 |
to reflect that translation. |
| 117 |
<p> |
| 118 |
In most of the rest of this discussion, the genc.c and cdata.c |
| 119 |
code will be used to explain the operation. |
| 120 |
Appropriate procedure renaming should be done for new languages |
| 121 |
(e.g, for Java, <i>genc_XXX</i> is changed to <i>genj_XXX</i> |
| 122 |
consistently). |
| 123 |
|
| 124 |
<h3>Useful Output Procedures</h3> |
| 125 |
The following output procedures are defined in genc.c to create C output. |
| 126 |
The idea is that output is accumulated in a <a href="#Bytebuffer">Bytebuffer</a> |
| 127 |
called ccode. Periodically, ccode |
| 128 |
contents are flushed to stdout. |
| 129 |
The relevant procedures from the C code are as follows. |
| 130 |
<ol> |
| 131 |
<li> <code>void cprint(Bytebuffer* buf)</code> |
| 132 |
-- dump the contents of buf to output (ccode actually). |
| 133 |
<li> <code>void cpartial(char* line)</code> |
| 134 |
-- dump the specified string to output. |
| 135 |
<li> <code>void cline(char* line)</code> |
| 136 |
-- dump the specified string to output and add a newline. |
| 137 |
<li> <code>void clined(int n, char* line)</code> |
| 138 |
-- dump the specified string to output preceded by |
| 139 |
<i>n</i> instances of indentation. |
| 140 |
<li> <code>void cflush(void)</code> |
| 141 |
-- dump the contents of ccode to standard output |
| 142 |
and reset the ccode buffer. |
| 143 |
</ol> |
| 144 |
There is, of course, nothing sacred about these procedures: |
| 145 |
feel free to modify as needed. In fact, there are two |
| 146 |
important reasons to modify the code. |
| 147 |
First, the indentation rules may differ from language to language |
| 148 |
(FORTRAN 77 for example). Second, the rules for folding lines |
| 149 |
that are too long differ across languages. |
| 150 |
It is usually easiest to handle both of these issues |
| 151 |
in the output procedures. |
| 152 |
<p> |
| 153 |
The <a href="#Bytebuffer">Bytebuffer</a> type is an important data structure. |
| 154 |
It allows for dynamically creating strings of characters |
| 155 |
(actually arbitrary 8 bit values). |
| 156 |
Most of the operations should be obvious: examine bytebuffer.h. |
| 157 |
It is used widely in this code especially to capture sub-pieces |
| 158 |
of the generated code that must be saved for out-of-order output. |
| 159 |
|
| 160 |
<h3>Code Generation</h3> |
| 161 |
The code generation method used for C is a pretty good |
| 162 |
general paradigm, so this discussion will use it as a model. |
| 163 |
The gen_ncc procedure is responsible for |
| 164 |
creating and dumping the generated C code. |
| 165 |
<p> |
| 166 |
It has at its disposal several global lists of Symbols. |
| 167 |
Note that the lists cross all groups. |
| 168 |
<ul> |
| 169 |
<li>dimdefs - the set of symbols defining dimensions. |
| 170 |
<li>vardefs - the set of symbols defining variables. |
| 171 |
<li>attdefs - the set of symbols defining non-global attributes. |
| 172 |
<li>gattdefs - the set of symbols defining global attributes. |
| 173 |
<li>grpdefs - the set of symbols defining groups. |
| 174 |
<li>typdefs - the set of symbols defining types; note that this list |
| 175 |
has been topologically sorted so that a given type depends only |
| 176 |
on types with lower indices in the list. |
| 177 |
</ul> |
| 178 |
<p> |
| 179 |
The superficial operation of gen_ncc is as follows; the details |
| 180 |
are provided later where the operation is complex. |
| 181 |
<ol> |
| 182 |
<li>Generate header code (e.g. #include <stdio.h>"). |
| 183 |
<li>Generate C type definitions corresponding to the |
| 184 |
CDL types. |
| 185 |
<li>Generate VLEN constants. |
| 186 |
<li>Generate chunking constants. |
| 187 |
<li>Generate initial part of the main() procedure. |
| 188 |
<li>Generate C variable definitions to hold the ncids |
| 189 |
for all created groups. |
| 190 |
<li>Generate C variable definitions to hold the typeids |
| 191 |
of all created types. |
| 192 |
<li>Generate C variables and constants that correspond to |
| 193 |
to the CDL dimensions. |
| 194 |
<li>Generate C variable definitions to hold the dimids |
| 195 |
of all created dimensions. |
| 196 |
<li>Generate C variable definitions to hold the varids |
| 197 |
of all created variables. |
| 198 |
<li>Generate C code to create the netCDF binary file. |
| 199 |
<li>Generate C code to create the all groups in the proper |
| 200 |
hierarchy. |
| 201 |
<li>Generate C code to create the type definitions. |
| 202 |
<li>Generate C code to create the dimension definitions. |
| 203 |
<li>Generate C code to create the variable definitions. |
| 204 |
<li>Generate C code to create the global attributes. |
| 205 |
<li>Generate C code to create the non-global attributes. |
| 206 |
<li>Generate C code to leave define mode. |
| 207 |
<li>Generate C code to assign variable datalists. |
| 208 |
</ol> |
| 209 |
<p> |
| 210 |
The following code generates C code for defining the groups. |
| 211 |
It is fairly canonical and can be seen repeated in variant form |
| 212 |
when defining dimensions, types, variables, and attributes. |
| 213 |
<p> |
| 214 |
This code is redundant but for consistency, the root group |
| 215 |
ncid is stored like all other group ncids. |
| 216 |
Note that nprintf is a macro wrapper around snprint. |
| 217 |
<pre> |
| 218 |
nprintf(stmt,sizeof(stmt),"%s%s = ncid;",indented(1),groupncid(rootgroup)); |
| 219 |
cline(stmt); |
| 220 |
</pre> |
| 221 |
<p> |
| 222 |
The loop walks all group symbols in preorder form |
| 223 |
and generates C code call to nc_def_grp |
| 224 |
using parameters taken from the group Symbol instance (gsym). |
| 225 |
The call to nc_def_grp is succeeded by a call to the |
| 226 |
check_err procedure to verify the operation's result code. |
| 227 |
<pre> |
| 228 |
for(igrp=0;igrp<listlength(grpdefs);igrp++) { |
| 229 |
Symbol* gsym = (Symbol*)listget(grpdefs,igrp); |
| 230 |
if(gsym == rootgroup) continue; // ignore root |
| 231 |
if(gsym->container == NULL) PANIC("null container"); |
| 232 |
nprintf(stmt,sizeof(stmt), |
| 233 |
"%sstat = nc_def_grp(%s, \"%s\", &%s);", |
| 234 |
indented(1), |
| 235 |
groupncid(gsym->container), |
| 236 |
gsym->name, groupncid(gsym)); |
| 237 |
cline(stmt); // print the def_grp call |
| 238 |
clined(1,"check_err(stat,__LINE__,__FILE__);"); |
| 239 |
} |
| 240 |
flushcode(); |
| 241 |
</pre> |
| 242 |
Note the call to indented(). It generates a blank string corresponding |
| 243 |
to indentation to a level of its argument N; level n might result in |
| 244 |
more or less than N blank characters. |
| 245 |
<p> |
| 246 |
Note also that one must be careful when dumping names |
| 247 |
(e.g. gsym->name above) if the name is expected to contain |
| 248 |
utf8 characters. For C, utf8 works fine in strings, but with |
| 249 |
a language like Java, which takes utf-16 characters, |
| 250 |
some special encoding is required to convert the non-ascii |
| 251 |
characters to use the \uxxxx form. |
| 252 |
<p> |
| 253 |
The code to generate dimensions, types, attributes, variables |
| 254 |
is similar, although often more complex. |
| 255 |
<p> |
| 256 |
The code to generate C equivalents of CDL types is |
| 257 |
in the procedure definectype(). |
| 258 |
Note that this code is not the code that invokes e.g. nc_def_vlen. |
| 259 |
The generated C types are used when generating datalists |
| 260 |
so that the standard C constant assignment mechanism will produce |
| 261 |
the correct memory values. |
| 262 |
<p> |
| 263 |
For non-C languages, the interaction between this code and the |
| 264 |
nc_def_TYPE code may be rather more complex than with C. |
| 265 |
<p> |
| 266 |
The genc_deftype procedure is the one that actually |
| 267 |
generates C code to define the netcdf types. |
| 268 |
The generated C code is designed to store the resulting |
| 269 |
typeid into the C variable defined earlier |
| 270 |
for holding that typeid. |
| 271 |
<p> |
| 272 |
Note that for compound types, the NC_COMPOUND_OFFSET |
| 273 |
macro is normally used to match netcdf offsets to |
| 274 |
the corresponding struct type generated in definectype. |
| 275 |
However, there is a flag, TESTALIGNMENT, |
| 276 |
that can be set to use a computed value for the offset. |
| 277 |
And for non-C languages, handling offsets is tricky and is |
| 278 |
addressed in more detail below. |
| 279 |
|
| 280 |
<h3>Data Generation Methods</h3> |
| 281 |
There are basically three known approaches for generating |
| 282 |
the data constants that are passed to, for example, <i>nc_put_vara</i>. |
| 283 |
<ol> |
| 284 |
<li> For C (and C++) it is possible to generate C language constants |
| 285 |
directly into the code using the C initializer syntax. |
| 286 |
This is because CDL was originally defined with C in mind. |
| 287 |
This method can also be used for FORTRAN when doing classic model only. |
| 288 |
<p> |
| 289 |
<li> Generate the binary data |
| 290 |
and convert it to a large single string constant using |
| 291 |
appropriate escaping mechanisms; this was done in the original |
| 292 |
ncgen. |
| 293 |
This method has the advantage that it can be used for most |
| 294 |
languages, but it has (at least) two disadvantages: |
| 295 |
(1) it is not generally portable because the machine architecture |
| 296 |
influences the memory encoding; (2) it loses all information |
| 297 |
about the structure of the memory and hence makes more debugging |
| 298 |
difficult. |
| 299 |
<p> |
| 300 |
<li>Extend the netCDF interface with a set |
| 301 |
of operations to build up the memory structure piece by piece. |
| 302 |
This is the approach taken in the Java generation code. |
| 303 |
<p> |
| 304 |
The idea is that one has a set of procedures in C with a simple |
| 305 |
interface that can be invoked by the output language. |
| 306 |
These procedures do the following. |
| 307 |
<ol> |
| 308 |
<li>Create a dynamically extendible memory buffer (much like Bytebuffer). |
| 309 |
<li>Append an array of instances |
| 310 |
of some primitive type to a specified buffer. |
| 311 |
<li>Invoke nc_put_vara with a specified buffer. |
| 312 |
<li>Reclaim a buffer |
| 313 |
</ol> |
| 314 |
Appropriate calls to these procedures can construct any required memory |
| 315 |
in a portable fashion. |
| 316 |
<p> |
| 317 |
This method is appropriate to use with most non-C languages, with interpretive |
| 318 |
languages (e.g., Ruby and Perl), and even is probably the best way to |
| 319 |
get FORTRAN to handle the full netcdf-4 data model. |
| 320 |
</ol> |
| 321 |
|
| 322 |
<h3>Data Generation: Overview</h3> |
| 323 |
The way to think about data generation is to consider |
| 324 |
the following tree. |
| 325 |
<ul> |
| 326 |
<li>The root is a convenience and represents the whole |
| 327 |
set of variables specified in the CDL "data:" section. |
| 328 |
<li>The nodes in the tree just below the root represent |
| 329 |
the set of variables to which values are assigned in the |
| 330 |
data section. |
| 331 |
<li>The subtrees below each variable are the basetypes |
| 332 |
of each variable. Thus if a variables x has a basetype |
| 333 |
that is a compound type, then the node below x will |
| 334 |
represent the whole compound type and the nodes below |
| 335 |
that compound type node will be the fields of the compound |
| 336 |
type, and so on. |
| 337 |
<li>The leaves of this tree are all of primitive type |
| 338 |
(e.g. NC_CHAR, NC_INT, NC_STRING). |
| 339 |
</ul> |
| 340 |
<p> |
| 341 |
The data generation code is divided into two |
| 342 |
primary groups. One group handles all non-primitive variables |
| 343 |
and types. The other group handles all primitive variables |
| 344 |
and types (especially fields). The reason for this is that |
| 345 |
almost all languages can handle simple lists of primitive values. |
| 346 |
However, for non-primitive types, one of the methods from the previous |
| 347 |
section needs to be used. |
| 348 |
<p> |
| 349 |
Secondarily, the primitive handling code is divided into |
| 350 |
two groups. One group handles the character type |
| 351 |
and the other group handles all other primitive types. |
| 352 |
The code for the first group is in chardata.c and is generally |
| 353 |
usable across all languages. |
| 354 |
<p> |
| 355 |
The reason for this split is for historical reasons. |
| 356 |
It turns out that it is tricky to properly handle variables |
| 357 |
(or Compound type fields) of type NC_CHAR. |
| 358 |
Here the term "proper" means to mimic the output of |
| 359 |
the original ncgen program. To this end, a set of generically useful routines |
| 360 |
are define in the chardata.c file. These routines take a datasource |
| 361 |
and walk it to build a single string of characters, with appropriate fill, |
| 362 |
to correspond to a NC_CHAR typed variable or field. |
| 363 |
Unless your language has special |
| 364 |
requirements, it is probably best to always use these routines to process |
| 365 |
datalists for variables of type NC_CHAR. |
| 366 |
|
| 367 |
<h3>Data Generation: Part I</h3> |
| 368 |
Data generation occurs in several places, but is roughly |
| 369 |
divided into two parts. First, the genc.c code will set up |
| 370 |
appropriate declarations to hold the data. Second, the code |
| 371 |
in cdata.c will generate the actual memory contents that must be |
| 372 |
passed to nc_put_vara. |
| 373 |
<p> |
| 374 |
As a rule, the genc.c code calls a limited set of |
| 375 |
entry points into cdata.c. Again as a rule, |
| 376 |
cdata.c does not call genc.c code except for the closure |
| 377 |
mechanism described below. |
| 378 |
<p> |
| 379 |
The critical pieces of code for part I are the procedures |
| 380 |
genc_defineattr() and genc_definevardata() in genc.c. |
| 381 |
|
| 382 |
<h4>genc_definevardata</h4> |
| 383 |
This procedure is responsible for generating C constants corresponding |
| 384 |
to the data to be assigned to a variable as defined in the "data:" section |
| 385 |
of a CDL file. It is also responsible for |
| 386 |
generating the appropriate nc_put_vara_XXX code to actually assign |
| 387 |
the data to the variable. |
| 388 |
|
| 389 |
<h4>genc_defineattr</h4> |
| 390 |
This procedure is responsible for generating C constants corresponding |
| 391 |
to the data to be assigned to an attribute. |
| 392 |
from a CDL file. It is also responsible for |
| 393 |
generating the appropriate nc_put_att_XXX code to actually define |
| 394 |
the attribute. |
| 395 |
<p> |
| 396 |
As with variables, defining attributes of type NC_CHAR requires use |
| 397 |
of the gen_charXXX procedures. |
| 398 |
|
| 399 |
<h3>Data Generation: Part II</h3> |
| 400 |
The procedures in cdata.c walk a datalist |
| 401 |
and generate a sequence of space separated constants |
| 402 |
and possibly with nested paired braces ("{...}") as needed. |
| 403 |
The result is placed into a specified Bytebuffer. |
| 404 |
<p> |
| 405 |
As an aside, commas are added when needed to the list of constants |
| 406 |
using the <i>commify</i> procedure. |
| 407 |
<p> |
| 408 |
Their are three primary procedures that are called from |
| 409 |
the genj.c code. |
| 410 |
<ul> |
| 411 |
<li>genc_attrdata -- |
| 412 |
store (in its Bytebuffer argument) the sequence of constants |
| 413 |
corresponding to a given attribute datalist. |
| 414 |
<li>genc_scalardata -- |
| 415 |
store the single constant (which may be of a user-defined type) |
| 416 |
corresponding to its variable's datalist. |
| 417 |
<li>and genc_arraydata. |
| 418 |
store the vector of constants corresponding to its variable's datalist. |
| 419 |
This is by far the most complicated of the three procedures. |
| 420 |
</ul> |
| 421 |
<p> |
| 422 |
Internally, each of these three procedures invokes |
| 423 |
the <i>genc_data</i> procedure to process part of a datalist. |
| 424 |
|
| 425 |
|
| 426 |
<h3>Closures and VLEN</h4> |
| 427 |
Closures and VLEN handling are two rather specialized mechanisms. |
| 428 |
|
| 429 |
<h4>Closures</h4> |
| 430 |
The data generation code uses a concept of closure or callback |
| 431 |
to allow the datalist processing to periodically |
| 432 |
call external code to do the actual C code generation. |
| 433 |
The reason for this is that it significantly improves |
| 434 |
performance if the generated datalist is periodically |
| 435 |
dumped to the netcdf .nc file using <i>nc_put_vara</i>. |
| 436 |
Note that the closure mechanism is only used for generating |
| 437 |
variable data; attributes cannot use this mechanism |
| 438 |
since they are defined all at once. |
| 439 |
<p> |
| 440 |
Basically, each call to the callback will generate |
| 441 |
C code for some C constants and calls to nc_put_vara(). |
| 442 |
The closure data structure (struct Putvar) is defined as follows. |
| 443 |
<pre> |
| 444 |
typedef struct Putvar { |
| 445 |
int (*putvar)(struct Putvar*, Odometer*, Bytebuffer*); |
| 446 |
int rank; |
| 447 |
Bytebuffer* code; |
| 448 |
size_t startset[NC_MAX_VAR_DIMS]; |
| 449 |
struct CDF { |
| 450 |
int grpid; |
| 451 |
int varid; |
| 452 |
} cdf; |
| 453 |
struct C { |
| 454 |
Symbol* var; |
| 455 |
} c; |
| 456 |
} Putvar; |
| 457 |
</pre> |
| 458 |
An instance of the closure is created for |
| 459 |
each variable that is the target of nc_put_vara(). |
| 460 |
It is initialized with the variable's symbol, rank, group id and variable |
| 461 |
id. It is also provided with a Bytebuffer into which it is supposed |
| 462 |
to store the generated C code. |
| 463 |
The startset is the cached previous set of dimension indices used |
| 464 |
for generating the nc_put_vara (see below). |
| 465 |
<p> |
| 466 |
The callback procedure (field "putvar") |
| 467 |
for generating C code putvar is assigned to the procedure called cputvara() |
| 468 |
(defined in genc.c). |
| 469 |
This procedure takes as arguments the closure object, |
| 470 |
an <a href="#odometer">odometer</a> describing the current set of dimension indices, |
| 471 |
and a Bytebuffer containing the generated C constants |
| 472 |
to be assigned to this slice of the variable. |
| 473 |
<p> |
| 474 |
Every time the closure procedure is called, it generates a C variable |
| 475 |
to hold the generated C constant. It also generated |
| 476 |
C constants to hold the start and count vectors required |
| 477 |
by <i>nc_put_vara</i>. It then generates an <i>nc_put_vara()</i> call. |
| 478 |
The start vector argument for the nc_put_vara is defined by the startset |
| 479 |
field of the closure. The count vector argument to nc_put_vara |
| 480 |
is computed from the current cached |
| 481 |
start vector and from the indices in the odometer. |
| 482 |
After the nc_put_vara() is generated, the odometer vector |
| 483 |
is assigned to the startset field in the closure for use on the next call. |
| 484 |
<p> |
| 485 |
There are some important assumptions about the state of the odometer |
| 486 |
when it is called. |
| 487 |
<ol> |
| 488 |
<li>The zeroth index controls the count set. |
| 489 |
<li>All other indices are assumed to be at their max values. |
| 490 |
</ol> |
| 491 |
<p> |
| 492 |
In particular, this means that the start vector is zero |
| 493 |
for all positions except position zero. The count vector |
| 494 |
is positions, except zero is the index in the odometer, |
| 495 |
which is assumed to be the max. |
| 496 |
<p> |
| 497 |
For start position zero, the position is taken from the last |
| 498 |
saved startset. The count position zero is the difference between |
| 499 |
that last start position and the current odometer zeroth index. |
| 500 |
|
| 501 |
<h4>VLEN Constants</h4> |
| 502 |
VLEN constants need to be constructed |
| 503 |
as separate C data constants because |
| 504 |
the C compiler will never convert nested |
| 505 |
groups ({...}) to separate memory chunks. |
| 506 |
Thus, ncgen must in several places |
| 507 |
generate the VLEN constants as separate variables |
| 508 |
and then insert pointers to them in the appropriate |
| 509 |
places in the later datalist C constants. |
| 510 |
Note that this process can be very tricky |
| 511 |
for non-C language (see genj.c and jdata.c for one approach). |
| 512 |
<p> |
| 513 |
As an optimization, ncgen tracks which datatypes |
| 514 |
will require use of vlen constants. |
| 515 |
This is any type whose definition is a vlen or whose |
| 516 |
basetype contains a vlen type. |
| 517 |
<p> |
| 518 |
The vlen generation process is two-fold. |
| 519 |
First, in the procedure processdatalist1() in semantics.c, |
| 520 |
the location of the struct Datalist objects |
| 521 |
that correspond to vlen constants is stored in a list called vlenconstants. |
| 522 |
When detected, each such Datalist object is tagged with |
| 523 |
a unique identifier and the vlen length (count). |
| 524 |
These will be used later to generate references to the vlen constant. |
| 525 |
These counts are only accurate for non-char typed variables; |
| 526 |
Special handling is in place to handle character vlen constants. |
| 527 |
<p> |
| 528 |
The second vlen constant processing action is in the |
| 529 |
procedure genc_vlenconstant() in cdata.c First, it walks the |
| 530 |
vlenconstants list and generates C code for C variables to |
| 531 |
define the vlen constant and C code to assign the vlen |
| 532 |
constant's data to that C variable. |
| 533 |
<p> |
| 534 |
When, later, the genc_datalist procedure encounters |
| 535 |
a Datalist tagged as representing a data list, it can generate |
| 536 |
a nc_vlen_t constant as {<count>,<vlenconstantname>} |
| 537 |
and use it directly in the generated C datalist constant. |
| 538 |
|
| 539 |
|
| 540 |
<h2>Utility Data Structures</h2> |
| 541 |
|
| 542 |
<h3>Pool Memory Allocation</h3> |
| 543 |
As an approximation to garbage collection, |
| 544 |
this code uses a pool allocation mechanism. |
| 545 |
The goal is to allow dynamic construction of strings |
| 546 |
that have very short life-times; typically they are used |
| 547 |
to construct strings to send to the output file. |
| 548 |
<p> |
| 549 |
The pool mechanism wraps malloc and records the malloc'd |
| 550 |
memory in a circular buffer. When the buffer reaches its maximum |
| 551 |
size, previously allocated pool buffers are free'd. |
| 552 |
This is good in that the user does not have to litter |
| 553 |
code with free() statements. It is bad in that the pool |
| 554 |
allocated memory can be free'd too early if the memory |
| 555 |
does not have a short enough life. |
| 556 |
If you suspect the latter, then bump the size of the circular buffer |
| 557 |
and see if the problem goes away. If so, then your code |
| 558 |
is probably holding on to a pool buffer too long and should use |
| 559 |
regular malloc/free. |
| 560 |
<p> |
| 561 |
In the end, I am not sure if this is a good idea, but |
| 562 |
if does make the code simpler. |
| 563 |
|
| 564 |
<h3><a name="List">List<a> and <a name="Bytebuffer">Bytebuffer</a></h3> |
| 565 |
The two datatypes List and Bytebuffer are used through out the |
| 566 |
code. They correspond closely in semantics to the Java Arraylist |
| 567 |
and Stringbuffer types, respectively. They are used to help |
| 568 |
encapsulate dynamically growing lists of objects or bytes |
| 569 |
to reduce certain kinds of memory allocation errors. |
| 570 |
<p> |
| 571 |
The canonical code for non-destructive walking of a List<T> |
| 572 |
is as follows. |
| 573 |
<pre> |
| 574 |
for(i=0;i<listlength(list);i++) { |
| 575 |
T* element = (T*)listget(list,i); |
| 576 |
... |
| 577 |
} |
| 578 |
</pre> |
| 579 |
<p> |
| 580 |
Bytebuffer provides two ways to access its internal buffer of characters. |
| 581 |
One is "bbContents()", which returns a direct pointer to the buffer, |
| 582 |
and the other is "bbDup()", which returns a malloc'd string containing |
| 583 |
the contents and is guaranteed to be null terminated. |
| 584 |
|
| 585 |
<h3><a name="odometer">Odometer: Multi-Dimensional Array Handling</a></h3> |
| 586 |
The odometer data type is used to convert |
| 587 |
multiple dimensions into a single integer. |
| 588 |
The rule for converting a multi-dimensional |
| 589 |
array to a single dimensions is as follows. |
| 590 |
<p> |
| 591 |
Suppose we have the declaration <code>int F[2][5][3];</code>. |
| 592 |
There are obviously a total of 2 X 5 X 3 = 30 integers in F. |
| 593 |
Thus, these three dimensions will be reduced to a single dimension of size 30. |
| 594 |
<p> |
| 595 |
A particular point in the three dimensions, say [x][y][z], is reduced to |
| 596 |
a number in the range 0..29 by computing <code>((x*5)+y)*3+z</code>. |
| 597 |
The corresponding general C code is as follows. |
| 598 |
<pre> |
| 599 |
size_t |
| 600 |
dimmap(int rank, size_t* indices, size_t* sizes) |
| 601 |
{ |
| 602 |
int i; |
| 603 |
size_t count = 0; |
| 604 |
for(i=0;i<rank;i++) { |
| 605 |
if(i > 0) count *= sizes[i]; |
| 606 |
count += indices[i]; |
| 607 |
} |
| 608 |
return count; |
| 609 |
} |
| 610 |
</pre> |
| 611 |
In this code, the indices variable corresponds to the x,y, and z. |
| 612 |
The sizes variable corresponds to the 2,5, and 3. |
| 613 |
<p> |
| 614 |
The Odometer type stores a set of dimensions |
| 615 |
and supports operations to iterate over all possible |
| 616 |
dimension combinations. |
| 617 |
The definition of Odometer is defined by the types Odometer and Dimdata. |
| 618 |
<pre> |
| 619 |
typedef struct Dimdata { |
| 620 |
unsigned long datasize; // actual size of the datalist item |
| 621 |
unsigned long index; // 0 <= index < datasize |
| 622 |
unsigned long declsize; |
| 623 |
} Dimdata; |
| 624 |
|
| 625 |
typedef struct Odometer { |
| 626 |
int rank; |
| 627 |
Dimdata dims[NC_MAX_VAR_DIMS]; |
| 628 |
} Odometer; |
| 629 |
</pre> |
| 630 |
The following primary operations are defined. |
| 631 |
<ul> |
| 632 |
<li>Odometer* newodometer(Dimset*) - create an odometer from a set of Dimsets. |
| 633 |
<li>void freeodometer(Odometer*) - release the memory of an odometer. |
| 634 |
<li>int odometermore(Odometer* odom) - return 1 if there are more combinations |
| 635 |
of dimension values. |
| 636 |
<li>int odometerincr(Odometer* odo,int) - move to the next combination |
| 637 |
of dimension values. |
| 638 |
<li>unsigned long odometercount(Odometer* odo) - |
| 639 |
apply the above algorithm to convert the current odometer combination |
| 640 |
into a single integer. |
| 641 |
</ul> |
| 642 |
|
| 643 |
|
| 644 |
|
| 645 |
<h2>Misc. Notes</h2> |
| 646 |
<ul> |
| 647 |
<li> The flag "usingclassic" should be consulted when appropriate to determine |
| 648 |
is this CDL file should be treated as using only the netCDF classic model. |
| 649 |
</ul> |
| 650 |
|
| 651 |
<h2><u>Change Log</u></h2> |
| 652 |
<ul> |
| 653 |
<li>07/04/2009 - First draft. |
| 654 |
</ul> |
| 655 |
|
| 656 |
</body> |
| 657 |
</html> |
| 658 |
|
| 659 |
<p> |
| 660 |
|
| 661 |
|
| 662 |
<i>genc_scalardata</i> or <i>genc_arraydata</i>. |
| 663 |
It stores in its Bytebuffer argument the sequence of constants |
| 664 |
corresponding to a given datalist. Handling commas is a tricky issue |
| 665 |
so you will that many of the non-top-level routines in cdata.c |
| 666 |
take a pointer to a global state element, commap, that determines the |
| 667 |
current state of adding commas. The idea is that at the beginning of |
| 668 |
any (sub-) Datalist, we want to turn off the comma in front of the |
| 669 |
first generated constant and then add commas until be reach the end |
| 670 |
of that (sub-)Datalist. |
| 671 |
|
| 672 |
<h1></u><a name="GIT">General Internals Information</a></u></h1> |
| 673 |
|
| 674 |
<h2><u>Primary NCGEN Data Structures</u></h2> |
| 675 |
There are two primary structures used in ncgen: |
| 676 |
<a href="#Symbol">struct Symbol</a>) and |
| 677 |
<a href="#Datalist">struct Datalist</a>). |
| 678 |
|
| 679 |
<h3><a name="Symbol">struct Symbol</a></h3> |
| 680 |
Symbol objects are linked into hierarchical structures |
| 681 |
to represent netcdf dimensions, types, groups, and variables. |
| 682 |
The struct has the following fields. |
| 683 |
<table> |
| 684 |
<tr><th colspan=3>struct Symbol Fields |
| 685 |
<tr valign=top><td>struct Symbol* next<td>-<td> |
| 686 |
The Symbol objects are all kept on a single linked list. |
| 687 |
No symbol is ever deleted until the end of the program. |
| 688 |
<tr valign=top><td>nc_class objectclass<td>-<td> |
| 689 |
This defines the general class of symbol, one of: NC_GRP, NC_DIM, NC_VAR, NC_ATT, or NC_TYPE. |
| 690 |
<tr valign=top><td>nc_classsubclass<td>-<td> |
| 691 |
This defines the sub class of symbol, one of: |
| 692 |
NC_PRIM, NC_OPAQUE, NC_ENUM, |
| 693 |
NC_FIELD, NC_VLEN, NC_COMPOUND, |
| 694 |
NC_ECONST, NC_ARRAY, or NC_FILLVALUE. |
| 695 |
<tr valign=top><td>char*name<td>-<td> |
| 696 |
The symbol's name. |
| 697 |
<tr valign=top><td>struct Symbol* container<td>-<td> |
| 698 |
The symbol that is the container for this symbol. |
| 699 |
Typically, this the group symbol that contains |
| 700 |
this symbol. |
| 701 |
<tr valign=top><td>struct Symbol location<td>-<td> |
| 702 |
The current group that was open when this symbol was created. |
| 703 |
<tr valign=top><td>List* subnodes<td>-<td> |
| 704 |
The list of child symbols of this symbol. |
| 705 |
For example, a group symbol will have its dimensions, |
| 706 |
types, vars, and subgroups will be in this list. |
| 707 |
<tr valign=top><td>int is_prefixed<td>-<td> |
| 708 |
True if the name of this symbol contains a complete |
| 709 |
prefix path (e.g. /x/y/z). |
| 710 |
<tr valign=top><td>List* prefix<td>-<td> |
| 711 |
A list of the prefix names for this node. |
| 712 |
Note that if is_prefixed is false, then this |
| 713 |
list was constructed from the set of enclosing groups. |
| 714 |
<tr valign=top><td>struct Datalist* data<td>-<td> |
| 715 |
Stores the constants from attribute or datalist |
| 716 |
constructs. |
| 717 |
<tr valign=top><td>Typeinfo typ<td>-<td> |
| 718 |
Type information about this symbol |
| 719 |
as defined by the Typeinfo structure. |
| 720 |
<tr valign=top><td>Varinfo var<td>-<td> |
| 721 |
Variable information about a variable symbol |
| 722 |
as defined by the Varinfo structure. |
| 723 |
<tr valign=top><td>Attrinfo att<td>-<td> |
| 724 |
Attribute information about an attribute symbol |
| 725 |
as defined by the Attrinfo structure. |
| 726 |
<tr valign=top><td>Diminfo dim<td>-<td> |
| 727 |
Dimension information about a dimension symbol |
| 728 |
as defined by the Diminfo structure. |
| 729 |
<tr valign=top><td>Groupinfo grp<td>-<td> |
| 730 |
Group information about a group symbol |
| 731 |
as defined by the Groupinfo structure. |
| 732 |
<tr valign=top><td>int lineno<td>-<td> |
| 733 |
The source line in which this symbol was created. |
| 734 |
<tr valign=top><td>int touched<td>-<td> |
| 735 |
Used in transitive closure operations |
| 736 |
to prevent revisiting symbols. |
| 737 |
<tr valign=top><td>char* lname<td>-<td> |
| 738 |
Cached C or FORTRAN name (not used?). |
| 739 |
<tr valign=top><td>int ncid<td>-<td> |
| 740 |
The ncid/varid/dimid, etc when |
| 741 |
defining netcdf objects. |
| 742 |
</table> |
| 743 |
|
| 744 |
<h4>struct Groupinfo</h4> |
| 745 |
Group symbols primarily keep the group |
| 746 |
containment structure in the subnodes field of the Symbol. |
| 747 |
<p> |
| 748 |
<table> |
| 749 |
<tr><th colspan=3>struct Groupinfo Fields |
| 750 |
<tr valign=top><td>int is_root<td>-<td> |
| 751 |
Is this the root group? |
| 752 |
</table> |
| 753 |
|
| 754 |
<h4>struct Diminfo</h4> |
| 755 |
The only important information about a dimension, |
| 756 |
aside from name, is the dimension size. |
| 757 |
Additionally, type definitions may have anonymous |
| 758 |
(unnamed) dimensions. |
| 759 |
<p> |
| 760 |
<table> |
| 761 |
<tr><th colspan=3>struct Diminfo Fields |
| 762 |
<tr valign=top><td>int isconstant<td>-<td> |
| 763 |
Is this an anonymous dimension? |
| 764 |
<tr valign=top><td>unsigned int size<td>-<td> |
| 765 |
The size of the dimension. |
| 766 |
</table> |
| 767 |
|
| 768 |
<h4>struct Varinfo</h4> |
| 769 |
Variables require two primary pieces of information: |
| 770 |
the set of attributes (including special attributes) |
| 771 |
and dimension information. The dimension information |
| 772 |
is kept in the Typeinfo structure because things |
| 773 |
other than variables have dimensions (e.g. user defined types). |
| 774 |
<p> |
| 775 |
<table> |
| 776 |
<tr><th colspan=3>struct Varinfo Fields |
| 777 |
<tr valign=top><td>int nattributes<td>-<td> |
| 778 |
The number of attributes; this is redundant but useful. |
| 779 |
<tr valign=top><td>List* attributes<td>-<td> |
| 780 |
The list of all attribute symbols associated with this |
| 781 |
variable. |
| 782 |
<tr valign=top><td>Specialdata special<td>-<td> |
| 783 |
Special attribute values. |
| 784 |
</table> |
| 785 |
|
| 786 |
<h4>struct Typeinfo</h4> |
| 787 |
The type information is probably the second most |
| 788 |
used structure in all of the code (second to Symbol itself). |
| 789 |
<p> |
| 790 |
<table> |
| 791 |
<tr><th colspan=3>struct Typeinfo Fields |
| 792 |
<tr valign=top><td>struct Symbol* basetype<td>-<td> |
| 793 |
Provide a reference to the base type of this symbol. |
| 794 |
This applies to other types, variables, and attributes. |
| 795 |
<tr valign=top><td>int hasvlen<td>-<td> |
| 796 |
Does the type have a vlen definition anywhere within it. |
| 797 |
This is used as an optimization to avoid searching datalists |
| 798 |
for vlen constants. |
| 799 |
<tr valign=top><td>nc_type typecode<td>-<td> |
| 800 |
The typecode of the basetype. This is most useful |
| 801 |
when the basetype is a primitive type. |
| 802 |
<tr valign=top><td>unsigned long size<td>-<td> |
| 803 |
The size of this object. |
| 804 |
<tr valign=top><td>unsigned long offset<td>-<td> |
| 805 |
The field offset for fields in compound types. |
| 806 |
<tr valign=top><td>unsigned long alignment<td>-<td> |
| 807 |
The memory alignment (i.e. 1,2,4,or 8). |
| 808 |
<tr valign=top><td>Constant econst<td>-<td> |
| 809 |
For enumeration constants, the actual value of the constant. |
| 810 |
<tr valign=top><td>Dimset dimset<td>-<td> |
| 811 |
The dimension information for the type or variable. |
| 812 |
The dimset stores the number of dimensions and a list |
| 813 |
of pointers to the corresponding dimension symbols. |
| 814 |
</table> |
| 815 |
|
| 816 |
<h4>struct Attrinfo</h4> |
| 817 |
Note that the actual attribute data is stored |
| 818 |
in the data field of the containing Symbol. |
| 819 |
<p> |
| 820 |
<table> |
| 821 |
<tr><th colspan=3>struct Attrinfo Fields |
| 822 |
<tr valign=top><td>struct Symbol* var<td>-<td> |
| 823 |
The variable with which this attribute is associated; |
| 824 |
it is NULL for global attributes. |
| 825 |
<tr valign=top><td>unsigned long count<td>-<td> |
| 826 |
The number of instances associated with the attribute value. |
| 827 |
</table> |
| 828 |
|
| 829 |
<h3><a name="Datalist">Datalists and Datasrcs</a></h3> |
| 830 |
Whenever a datalist is encountered during parsing, it is converted |
| 831 |
to an instance of struct Datalist. |
| 832 |
Each datalist instance contains a vector of instances of |
| 833 |
struct Constant that contains the actual data. |
| 834 |
<p> |
| 835 |
Each datalist instance contains the following information. |
| 836 |
<table> |
| 837 |
<tr><th colspan=3>struct Datalist Fields |
| 838 |
<tr valign=top><td>struct Datalist* next<td>-<td> |
| 839 |
All datalists are chained for reclamation. |
| 840 |
<tr valign=top><td>int readonly<td>-<td> |
| 841 |
Can this datalist be modified? |
| 842 |
<tr valign=top><td>unsigned int length<td>-<td> |
| 843 |
The number of Constant instances in the data field. |
| 844 |
<tr valign=top><td>unsigned int alloc<td>-<td> |
| 845 |
The memory space allocated to the data field. |
| 846 |
<tr valign=top><td>Constant* data<td>-<td> |
| 847 |
The vector in sequential memory of the constants comprising this datalist. |
| 848 |
<tr valign=top><td>struct Symbol* schema<td>-<td> |
| 849 |
The symbol (type, variable, or attribute) defining the structure of this datalist, |
| 850 |
if known. |
| 851 |
<tr valign=top><td>struct Vlen {<td>-<td> |
| 852 |
Information about the vlen instances contained in this datalist. |
| 853 |
<tr><td>unsigned int count; |
| 854 |
<tr><td>unsigned int uid; |
| 855 |
<tr><td>} vlen |
| 856 |
<tr valign=top><td>Odometer* dimdata<td>-<td> |
| 857 |
A tracker to count through dimensions associated with this datalist via the schema. |
| 858 |
</table> |
| 859 |
<p> |
| 860 |
In turn, a Constant instance is defined as follows. |
| 861 |
<pre> |
| 862 |
typedef struct Constant { |
| 863 |
nc_type nctype; |
| 864 |
int lineno; |
| 865 |
Constvalue value; |
| 866 |
} Constant; |
| 867 |
</pre> |
| 868 |
It indicates the type of the value and the source line number (if known) |
| 869 |
in which this constant was created. |
| 870 |
<p> |
| 871 |
The ConstValue type is a union |
| 872 |
of all possible values that can occur |
| 873 |
in a datalist. |
| 874 |
<pre> |
| 875 |
typedef union Constvalue { |
| 876 |
struct Datalist* compoundv; // NC_COMPOUND |
| 877 |
char charv; // NC_CHAR |
| 878 |
signed char int8v; // NC_BYTE |
| 879 |
unsigned char uint8v; // NC_UBYTE |
| 880 |
short int16v; // NC_SHORT |
| 881 |
unsigned short uint16v; // NC_USHORT |
| 882 |
int int32v; // NC_INT |
| 883 |
unsigned int uint32v; // NC_UINT |
| 884 |
long long int64v; // NC_INT64 |
| 885 |
unsigned long long uint64v; // NC_UINT64 |
| 886 |
float floatv; // NC_FLOAT |
| 887 |
double doublev; // NC_DOUBLE |
| 888 |
struct Stringv { // NC_STRING |
| 889 |
int len; |
| 890 |
char* stringv; |
| 891 |
} stringv; |
| 892 |
struct Opaquev { // NC_OPAQUE |
| 893 |
int len; // length as originally written (rounded to even number) |
| 894 |
char* stringv; //as constant was written |
| 895 |
// (padded to even # chars >= 16) |
| 896 |
// without leading 0x |
| 897 |
} opaquev; |
| 898 |
struct Symbol* enumv; // NC_ECONST |
| 899 |
} Constvalue; |
| 900 |
</pre> |
| 901 |
<p> |
| 902 |
Several fields are of particular interest: |
| 903 |
<table> |
| 904 |
<tr><th colspan=3>Selected Constvalue Fields |
| 905 |
<tr valign=top><td>struct Datalist* compoundv<td>-<td> |
| 906 |
This stores nested datalists - typically |
| 907 |
of the form "{...{...}...}". |
| 908 |
<tr valign=top><td>struct Stringv {int len; char* stringv;} stringv<td>-<td> |
| 909 |
Store string constants. |
| 910 |
<tr valign=top><td>struct Opaquev {int len; char* stringv;} opaquev<td>-<td> |
| 911 |
Store opaque constants as written (i.e. abc...), |
| 912 |
without the leading 0x, and |
| 913 |
padded to an even number of characters to be |
| 914 |
at least 16 characters long. |
| 915 |
<tr valign=top><td>struct Symbol* enumv<td>-<td> |
| 916 |
Pointer to an enumeration constant definition. |
| 917 |
</table> |
| 918 |
|
| 919 |
<h4>struct Datasrc</h3> |
| 920 |
When it comes time to generate datalists for output, |
| 921 |
it is necessary to "walk" the datalist (including nested |
| 922 |
datalist). The Datasrc structure is used to do this. |
| 923 |
Its definition is as follows. |
| 924 |
<pre> |
| 925 |
typedef struct Datasrc { |
| 926 |
unsigned int index; // 0..length-1 |
| 927 |
unsigned int length; |
| 928 |
int autopop; // pop when at end |
| 929 |
Constant* data; // duplicate pointer; so do not free. |
| 930 |
struct Datasrc* stack; |
| 931 |
} Datasrc; |
| 932 |
</pre> |
| 933 |
The Datasrc tracks the "current" location in the sequence |
| 934 |
of Constants (taken from a Datalist). The index field indicates |
| 935 |
the current location. |
| 936 |
In effect, Datasrc is the lexer and the code |
| 937 |
that is walking it is in effect parsing the data sequence. |
| 938 |
The following operations are supported (see data.[ch]). |
| 939 |
<ul> |
| 940 |
<li>datalist2src - takes a Datalist and constructs a Datasrc. |
| 941 |
<li>srcpush - assumes the current constant is a nested Datalist |
| 942 |
and pushes into that Datalist. |
| 943 |
<li>srcpushlist - pushes into the passed Datalist argument. |
| 944 |
<li>srcpop - pops the current list and resumes the next list in the |
| 945 |
stack. |
| 946 |
<li>srcnext - return the value at the index |
| 947 |
and then advance the Datasrc index. |
| 948 |
If at the end of the current datalist, then return NULL; |
| 949 |
srcincr is an alias for srcnext. |
| 950 |
<li>srcmore - return 1 is not at the end of the current Datasrc. |
| 951 |
Pushed datalists are not considered. |
| 952 |
<li>srcline - return a usable line number associated with the current |
| 953 |
position of the Datasrc (that is why Constant instances have a line |
| 954 |
number). |
| 955 |
<li>srcpeek - return the value at the index but do not advance. |
| 956 |
If at the end of the current datalist, then return NULL; srcget is an alias |
| 957 |
for srcpeek. |
| 958 |
</ul> |
| 959 |
|
| 960 |
<h2><u>The CDL Parser</u></h2> |
| 961 |
|
| 962 |
The CDL parser and associated lexer |
| 963 |
(primarily files "ncgen.y" and "ncgen.l") |
| 964 |
parse CDL files into various data structures |
| 965 |
for use by the remaining ncgen code. |
| 966 |
The data structures described above, |
| 967 |
(<a href="#Symbol">Symbol</a>, and |
| 968 |
<a href="#Datalist">Datalist</a>) |
| 969 |
are primarily generated by the parser. |
| 970 |
|
| 971 |
<h3>Parse Cliches</h3> |
| 972 |
<h4>Node Stacking</h4> |
| 973 |
One of the issues that must be addressed by any bottom-up |
| 974 |
parser is handling the accumulation of sets of items (nodes, |
| 975 |
etc.). The YACC/Bison parse stack cannot be used |
| 976 |
because the set of accumulated nodes is unbounded |
| 977 |
and the YACC stack mechanism is bounded (i.e. each rule |
| 978 |
has a bounded right hand side length). |
| 979 |
<p> |
| 980 |
The node stacking set of cliches is ubiquitous in the |
| 981 |
parser, so they must be understood to understand how the |
| 982 |
parser works. The cliche here is shown in the handling of, |
| 983 |
for example, the varlist rule, which is defined as follows. |
| 984 |
<pre> |
| 985 |
varlist: varspec |
| 986 |
{$$=listlength(stack); listpush(stack,(elem_t)$1);} |
| 987 |
| varlist ',' varspec |
| 988 |
{$$=$1; listpush(stack,(elem_t)$3);} |
| 989 |
; |
| 990 |
</pre> |
| 991 |
The varlist rule collects variable name declarations (via the varspec rule). |
| 992 |
The idea is to use a separate stack named "stack", and tracking |
| 993 |
the index into the stack of the start of collection of objects. |
| 994 |
The varlist value (in the YACC sense) is defined as an integer |
| 995 |
representing the size of the stack at the start of a list of variables. |
| 996 |
That is what this code does: <code>$$=listlength(stack)</code>. |
| 997 |
<p> |
| 998 |
At the point where the set of varspecs should processed, the following code cliche |
| 999 |
is used. |
| 1000 |
<pre> |
| 1001 |
vardecl: typeref varlist |
| 1002 |
{... |
| 1003 |
stackbase=$2; |
| 1004 |
stacklen=listlength(stack); |
| 1005 |
for(i=stackbase;i<stacklen;i++) { |
| 1006 |
Symbol* sym = (Symbol*)listget(stack,i); |
| 1007 |
... |
| 1008 |
} |
| 1009 |
listsetlength(stack,stackbase);// remove stack nodes |
| 1010 |
} |
| 1011 |
... |
| 1012 |
</pre> |
| 1013 |
The start of the set of variable declaration symbols is extracted |
| 1014 |
as the integer associated with right-side non-terminal $2, e.g. |
| 1015 |
<code>stackbase=$2</code>. |
| 1016 |
The current stack length is obtained from <code>stacklen=listlength(stack)</code>. |
| 1017 |
Then the elements of the stack are extracted one by one using the above loop. |
| 1018 |
Finally, the nodes on the stack are cleared by the code segment |
| 1019 |
<code>listsetlength(stack,stackbase)</code>. |
| 1020 |
|
| 1021 |
<h4><u>Semantic Processing</u></h4> |
| 1022 |
Semantic processing takes the output of the parser |
| 1023 |
and adds various pieces of semantic information. |
| 1024 |
The semantic actions are as follows. |
| 1025 |
<ol> |
| 1026 |
<li> Procedure processtypes(). |
| 1027 |
<ol> |
| 1028 |
<li>Do a topological sort of the types based on dependency |
| 1029 |
so that the least dependent are first in the typdefs list. |
| 1030 |
<li>Fill in type typecodes. |
| 1031 |
<li>Mark types that have a vlen. |
| 1032 |
</ol> |
| 1033 |
<li> Procedure filltypecodes() - Fill in implied type codes. |
| 1034 |
<li> Procedure processvars() - Fill in missing values. |
| 1035 |
<li> Procedure processattributes() - |
| 1036 |
Process attributes to connect to corresponding variable. |
| 1037 |
<li> Procedure processcompound() - |
| 1038 |
Process each compound type to compute its size. |
| 1039 |
<li> Procedure processenums() - |
| 1040 |
Fix up enum constant values. |
| 1041 |
<li> Procedure processdatalists() - |
| 1042 |
Fix up datalists. |
| 1043 |
<li> Procedure checkconsistency() - |
| 1044 |
Check internal consistency. |
| 1045 |
<li> Procedure validate() - |
| 1046 |
Do any needed additional semantic checks. |
| 1047 |
</ol> |
| 1048 |
|
| 1049 |
<h2><u>Generating C Code</u></h2> |
| 1050 |
The source code for generating C code output (via the -c option) |
| 1051 |
is of most interest because it is the pattern to be used |
| 1052 |
for other languages and because, frankly, it is complex and ugly |
| 1053 |
at the moment and so guidance is needed in understanding it. |
| 1054 |
<p> |
| 1055 |
The files genc.[ch] and cdata.c are the primary files for C code generation. |
| 1056 |
The files data.[ch] is also important. |
| 1057 |
|
| 1058 |
<h3><u>Output Routines</u></h3> |
| 1059 |
The output routines are a bit of a mixed bag. |
| 1060 |
It is important to know that code is not directly |
| 1061 |
dumped to the output file; rather is is accumulated |
| 1062 |
in a global Bytebuffer instance called "ccode". |
| 1063 |
<p> |
| 1064 |
The output routines are as follows. |
| 1065 |
<ul> |
| 1066 |
<li>flushcode(void) - flush the ccode buffer to the output file. |
| 1067 |
<li>cprint(Bytebuffer* buf) - dump the contents |
| 1068 |
of buf to the ccode buffer. |
| 1069 |
<li>cpartial(char* line) - dump the contents of line |
| 1070 |
to the ccode buffer, but do not add a trailing newline. |
| 1071 |
<li>cline(char* line) - dump the contents of line |
| 1072 |
to the ccode buffer and add a trailing newline. |
| 1073 |
<li>clined(int n, char* line) - dump the contents of line to the ccode |
| 1074 |
buffer; prefix with n indentations (typically 4 blanks each) |
| 1075 |
and suffix with a trailing newline. |
| 1076 |
</ul> |
| 1077 |
|
| 1078 |
<h3><u>gen_ncc</u></h3> |
| 1079 |
The gen_ncc procedure is responsible for |
| 1080 |
creating and dumping the generated C code. |
| 1081 |
<p> |
| 1082 |
It has at its disposal several global lists of Symbols. |
| 1083 |
Note that the lists cross all groups. |
| 1084 |
<ul> |
| 1085 |
<li>dimdefs - the set of symbols defining dimensions. |
| 1086 |
<li>vardefs - the set of symbols defining variables. |
| 1087 |
<li>attdefs - the set of symbols defining non-global attributes. |
| 1088 |
<li>gattdefs - the set of symbols defining global attributes. |
| 1089 |
<li>grpdefs - the set of symbols defining groups. |
| 1090 |
<li>typdefs - the set of symbols defining types; note that this list |
| 1091 |
has been topologically sorted so that a given type depends only |
| 1092 |
on types with lower indices in the list. |
| 1093 |
</ul> |
| 1094 |
<p> |
| 1095 |
The superficial operation of gen_ncc is as follows; the details |
| 1096 |
are provided later where the operation is complex. |
| 1097 |
<ol> |
| 1098 |
<li>Generate header code (e.g. #include <stdio.h>"). |
| 1099 |
<li>Generate C type definitions corresponding to the |
| 1100 |
CDL types. |
| 1101 |
<li>Generate VLEN constants. |
| 1102 |
<li>Generate chunking constants. |
| 1103 |
<li>Generate initial part of the main() procedure. |
| 1104 |
<li>Generate C variable definitions to hold the ncids |
| 1105 |
for all created groups. |
| 1106 |
<li>Generate C variable definitions to hold the typeids |
| 1107 |
of all created types. |
| 1108 |
<li>Generate C variables and constants that correspond to |
| 1109 |
to the CDL dimensions. |
| 1110 |
<li>Generate C variable definitions to hold the varids |
| 1111 |
of all created variables. |
| 1112 |
<li>Generate C code to create the netCDF binary file. |
| 1113 |
<li>Generate C code to create the all groups in the proper |
| 1114 |
hierarchy. |
| 1115 |
<li>Generate C code to create the type definitions. |
| 1116 |
<li>Generate C code to create the dimension definitions. |
| 1117 |
<li>Generate C code to create the variable definitions. |
| 1118 |
<li>Generate C code to create the global attributes. |
| 1119 |
<li>Generate C code to create the non-global attributes. |
| 1120 |
<li>Generate C code to leave define mode. |
| 1121 |
<li>Generate C code to assign variable datalists. |
| 1122 |
</ol> |
| 1123 |
<p> |
| 1124 |
The following code generates C code for defining the groups. |
| 1125 |
It is fairly canonical and can be seen repeated in variant form |
| 1126 |
when defining dimensions, types, variables, and attributes. |
| 1127 |
<p> |
| 1128 |
This code is redundant but for consistency, the root group |
| 1129 |
ncid is stored like all other group ncids. |
| 1130 |
Note that nprintf is a macro wrapper around snprint. |
| 1131 |
<pre> |
| 1132 |
nprintf(stmt,sizeof(stmt)," %s = ncid;",groupncid(rootgroup)); |
| 1133 |
cline(stmt); |
| 1134 |
</pre> |
| 1135 |
<p> |
| 1136 |
The loop walks all group symbols in preorder form |
| 1137 |
and generates C code call to nc_def_grp |
| 1138 |
using parameters taken from the group Symbol instance (gsym). |
| 1139 |
The call to nc_def_grp is succeeded by a call to the |
| 1140 |
check_err procedure to verify the operation's result code. |
| 1141 |
<pre> |
| 1142 |
for(igrp=0;igrp<listlength(grpdefs);igrp++) { |
| 1143 |
Symbol* gsym = (Symbol*)listget(grpdefs,igrp); |
| 1144 |
if(gsym == rootgroup) continue; // ignore root |
| 1145 |
if(gsym->container == NULL) PANIC("null container"); |
| 1146 |
nprintf(stmt,sizeof(stmt), |
| 1147 |
" stat = nc_def_grp(%s, \"%s\", &%s);", |
| 1148 |
groupncid(gsym->container), |
| 1149 |
gsym->name, groupncid(gsym)); |
| 1150 |
cline(stmt); // print the def_grp call |
| 1151 |
clined(1,"check_err(stat,__LINE__,__FILE__);"); |
| 1152 |
} |
| 1153 |
flushcode(); |
| 1154 |
</pre> |
| 1155 |
<p> |
| 1156 |
The code to generate dimensions, types, attributes, variables |
| 1157 |
is similar, although often more complex. |
| 1158 |
<p> |
| 1159 |
The code to generate C equivalents of CDL types is |
| 1160 |
in the procedure definectype(). |
| 1161 |
Note that this code is not the code that invokes e.g. nc_def_vlen. |
| 1162 |
The generated C types are used when generating datalists |
| 1163 |
so that the standard C constant assignment mechanism will produce |
| 1164 |
the correct memory values. |
| 1165 |
<p> |
| 1166 |
The genc_deftype procedure is the one that actually |
| 1167 |
generates C code to define the netcdf types. |
| 1168 |
The generated C code is designed to store the resulting |
| 1169 |
typeid into the C variable defined earlier |
| 1170 |
for holding that typeid. |
| 1171 |
<p> |
| 1172 |
Note that for compound types, the NC_COMPOUND_OFFSET |
| 1173 |
macro is normally used to match netcdf offsets to |
| 1174 |
the corresponding struct type generated in definectype. |
| 1175 |
However, there is a flag, TESTALIGNMENT, |
| 1176 |
that can be set to use a computed value for the offset. |
| 1177 |
|
| 1178 |
<h3><u>C Constant Datalist Generation</u></h3> |
| 1179 |
All attributes, and some variables, require the |
| 1180 |
construction of a memory object containing data |
| 1181 |
to be assigned to that attribute or variable. |
| 1182 |
The code to do this is by far the most complicated |
| 1183 |
in ncgen. |
| 1184 |
The file cdata.c contains the procedure genc_datalist(), |
| 1185 |
which does most of the heavy lifting. |
| 1186 |
<p> |
| 1187 |
For attributes, the general form generated is |
| 1188 |
<pre> |
| 1189 |
T* attributevar = {...}; |
| 1190 |
</pre> |
| 1191 |
Except for VLENs, the datalist is completely |
| 1192 |
contained in the brackets, with bracket nesting as required. |
| 1193 |
A generated pointer the attributevar is included |
| 1194 |
in the generated call to nc_put_att(). |
| 1195 |
<p> |
| 1196 |
For variables, the general form generated is similar to attributes. |
| 1197 |
<pre> |
| 1198 |
T* varvar = {...}; |
| 1199 |
</pre> |
| 1200 |
Again, VLENs are handled specially. |
| 1201 |
Also, for performance purposes, the datalist |
| 1202 |
is loaded in pieces using nc_put_vara(). This is required if |
| 1203 |
there are UNLIMITED dimensions, but is used for all cases |
| 1204 |
for uniformity. |
| 1205 |
|
| 1206 |
<h4>Datalist Closures</h4> |
| 1207 |
The code uses a concept of closure or callback |
| 1208 |
to allow the datalist processing to periodically |
| 1209 |
call external code to do the actual C code generation. |
| 1210 |
Basically, each call to the callback will generate |
| 1211 |
C code for constants and calls to nc_put_vara(). |
| 1212 |
The closure data structure (struct Putvar) is defined as follows. |
| 1213 |
<pre> |
| 1214 |
typedef struct Putvar { |
| 1215 |
int (*putvar)(struct Putvar*, Odometer*, Bytebuffer*); |
| 1216 |
int rank; |
| 1217 |
Bytebuffer* code; |
| 1218 |
size_t startset[NC_MAX_VAR_DIMS]; |
| 1219 |
struct CDF { |
| 1220 |
int grpid; |
| 1221 |
int varid; |
| 1222 |
} cdf; |
| 1223 |
struct C { |
| 1224 |
Symbol* var; |
| 1225 |
} c; |
| 1226 |
} Putvar; |
| 1227 |
</pre> |
| 1228 |
An instance of the closure is created for |
| 1229 |
each variable that is the target of nc_put_vara(). |
| 1230 |
It is initialized with the variable's symbol, rank, group id and variable |
| 1231 |
id. It is also provided with a Bytebuffer into which it is supposed |
| 1232 |
to store the generated C code. |
| 1233 |
The startset is the cached previous set of dimension indices used |
| 1234 |
for generating the nc_put_vara (see below). |
| 1235 |
<p> |
| 1236 |
The callback procedure (field "putvar") |
| 1237 |
for generating C code putvar is assigned to the procedure called cputvara() |
| 1238 |
(defined in genc.c). |
| 1239 |
This procedure takes as arguments the closure object, |
| 1240 |
an odometer describing the current set of dimension indices, |
| 1241 |
and a Bytebuffer containing the generated C constants |
| 1242 |
to be assigned to this slice of the variable. |
| 1243 |
<p> |
| 1244 |
Every time the closure procedure is called, it generates a C variable |
| 1245 |
to hold the generated C constant. It then generates an nc_put_vara() |
| 1246 |
call. The start vector argument for the nc_put_vara is defined by the startset |
| 1247 |
field of the closure. The count vector argument to nc_put_vara |
| 1248 |
is computed from the current cached |
| 1249 |
start vector and from the indices in the odometer. |
| 1250 |
After the nc_put_vara() is generated, the odometer vector |
| 1251 |
is assigned to the startset field in the closure for use on the next call. |
| 1252 |
<p> |
| 1253 |
There are some important assumptions about the state of the odometer |
| 1254 |
when it is called. |
| 1255 |
<ol> |
| 1256 |
<li>The zeroth index controls the count set. |
| 1257 |
<li>All other indices are assumed to be at their max values. |
| 1258 |
</ol> |
| 1259 |
<p> |
| 1260 |
In particular, this means that the start vector is zero |
| 1261 |
for all positions except position zero. The count vector |
| 1262 |
is positions, except zero is the index in the odometer, |
| 1263 |
which is assumed to be the max. |
| 1264 |
<p> |
| 1265 |
For start position zero, the position is taken from the last |
| 1266 |
saved startset. The count position zero is the difference between |
| 1267 |
that last start position and the current odometer zeroth index. |
| 1268 |
<p> |
| 1269 |
If all of this sounds complex, it is, and if/when I have time |
| 1270 |
I will rethink the whole process of datalist generation |
| 1271 |
from beginning to end. |
| 1272 |
|
| 1273 |
<h4>VLEN Constants</h4> |
| 1274 |
VLEN constants need to be constructed |
| 1275 |
as separate C data constants because |
| 1276 |
the C compiler will never convert nested |
| 1277 |
groups ({...}) to separate memory chunks. |
| 1278 |
Thus, ncgen must in several places |
| 1279 |
generate the VLEN constants as separate variables |
| 1280 |
and then insert pointers to them in the appropriate |
| 1281 |
places in the later datalist C constants. |
| 1282 |
<p> |
| 1283 |
As an optimization, ncgen tracks which datatypes |
| 1284 |
will require use of vlen constants. |
| 1285 |
This is any type whose definition is a vlen or whose |
| 1286 |
basetype contains a vlen type. |
| 1287 |
<p> |
| 1288 |
The vlen generation process is two-fold. |
| 1289 |
First, in the procedure processdatalist1() in semantics.c, |
| 1290 |
the location of the struct Datalist objects |
| 1291 |
that correspond to vlen constants is stored in a list called vlenconstants. |
| 1292 |
When detected, each such struct Datalist object is tagged with |
| 1293 |
a unique identifier and the vlen length (count). |
| 1294 |
These will be used later to generate references to the vlen constant. |
| 1295 |
<p> |
| 1296 |
The second vlen constant processing action is in the |
| 1297 |
procedure genc_vlenconstant() in cdata.c First, it walks the |
| 1298 |
vlenconstants list and generates C code for variables to |
| 1299 |
define the vlen constant and C code to assign the vlen |
| 1300 |
constant's data to that variable. |
| 1301 |
<p> |
| 1302 |
When, later, the genc_datalist procedure encounters |
| 1303 |
a Datalist tagged as representing a data list, it can generate |
| 1304 |
a nc_vlen_t constant as {<count>,<vlenconstantname>} |
| 1305 |
and use it directly in the generated C datalist constant. |
| 1306 |
|
| 1307 |
<h4>Walking the Datalist</h4> |
| 1308 |
To actually generate the C code for a datalist constant, |
| 1309 |
the procedure genc_datalist wraps the Datalist in a Datasrc, |
| 1310 |
and proceeds to walk it constant by constant and generating |
| 1311 |
the corresponding C constant. The bulk of the work |
| 1312 |
is performed in the recursive procedure genc_datalist1(). |
| 1313 |
<p> |
| 1314 |
For better or worse, the code |
| 1315 |
acts like a 1-lookahead parser. This means that it decides |
| 1316 |
what to do based on the current type, the current constant and, when necessary, |
| 1317 |
the next constant in the Datasrc. In practice, the lookahead |
| 1318 |
is hidden, so it is not represented in the following table. |
| 1319 |
<p> |
| 1320 |
<table border=1> |
| 1321 |
<tr><th>Current Type<th>Current Constant<th>action |
| 1322 |
<tr valign=top><td>NC_PRIM<td>Primitive Constant<td>Generate the C constant; convert as necessary. |
| 1323 |
<tr valign=top><td>NC_OPAQUE<td>''<td>'' |
| 1324 |
<tr valign=top><td>NC_ENUM<td>''<td>'' |
| 1325 |
<tr valign=top><td>NC_ENUM<td>''<td>'' |
| 1326 |
<tr valign=top><td>NC_COMPOUND<td>Nested Datalist Constant<td>Push into the datalist and recurse on each field; When done, pop back to previous datalist. |
| 1327 |
<tr valign=top><td>NC_COMPOUND<td>Any other Constant<td> |
| 1328 |
Continue to recurse on each field; This allows |
| 1329 |
specification of fields without enclosing in {...}. |
| 1330 |
<tr valign=top><td>NC_VLEN<td>Nested Datalist Constant<td>Generate the |
| 1331 |
nc_vlen_t instance using the tagged information in the struct Datalist. |
| 1332 |
<tr valign=top><td>NC_FIELD<td>NA<td>If this field is dimensioned, |
| 1333 |
then call genc_fielddata to walk the dimensions. Otherwise, just |
| 1334 |
recurse on genc_datalist1. |
| 1335 |
</table> |
| 1336 |
<p> |
| 1337 |
The genc_fielddata() procedure iterates over a field dimension |
| 1338 |
and calls itself recursively to walk the remaining dimensions. |
| 1339 |
It this is the last dimension, then it calls genc_datalist1 to |
| 1340 |
generate C code for the basetype of the field. |
| 1341 |
|
| 1342 |
<h4>String/Char Handling</h4> |
| 1343 |
All through the genc_datalist code, |
| 1344 |
there are special cases for handling string constants. |
| 1345 |
The reason is, of course, that the string constant "abcd.." |
| 1346 |
may, depending on the type context, be either a string |
| 1347 |
or an array of characters. |
| 1348 |
|
| 1349 |
<h4>Generating Variable Data</h4> |
| 1350 |
The genc_datalist code does not call closures. |
| 1351 |
The closures are used in the genc_vardata() and genc_vardata1() |
| 1352 |
procedures; genc_vardata1 being the recursive procedure that actually |
| 1353 |
calls the closure. |
| 1354 |
<p> |
| 1355 |
The genc_vardata1() procedure, like genc_fielddata, |
| 1356 |
iterates over a top-level dimension and calls itself recursively |
| 1357 |
to iterate over the remaining dimensions. |
| 1358 |
The term "top-level" refers to the fact that these are the dimensions |
| 1359 |
specified for a variable as opposed to field dimensions. |
| 1360 |
<p> |
| 1361 |
When iterating an UNLIMITED dimension, or when iterating the first |
| 1362 |
dimension, the code generates a datalist for this subslice |
| 1363 |
and then calls the closure to generate the C code. |
| 1364 |
|
| 1365 |
|
| 1366 |
<h2><u>Miscellaneous</u></h2> |
| 1367 |
<h4>Pool Memory Allocation</h4> |
| 1368 |
As an approximation to garbage collection, |
| 1369 |
this code uses a pool allocation mechanism. |
| 1370 |
The goal is to allow dynamic construction of strings |
| 1371 |
that have very short life-times; typically they are used |
| 1372 |
to construct strings to send to the output file. |
| 1373 |
<p> |
| 1374 |
The pool mechanism wraps malloc and records the malloc'd |
| 1375 |
memory in a circular buffer. When the buffer reaches its maximum |
| 1376 |
size, previously allocated pool buffers are free'd. |
| 1377 |
This is good in that the user does not have to litter |
| 1378 |
code with free() statements. It is bad in that the pool |
| 1379 |
allocated memory can be free'd too early if the memory |
| 1380 |
does not have a short enough life. |
| 1381 |
If you suspect the latter, then bump the size of the circular buffer |
| 1382 |
and see if the problem goes away. If so, then your code |
| 1383 |
is probably holding on to a pool buffer too long and should use |
| 1384 |
regular malloc/free. |
| 1385 |
<p> |
| 1386 |
In the end, I am not sure if this is a good idea, but |
| 1387 |
if does make the code simpler. |
| 1388 |
|
| 1389 |
<h4>List and Bytebuffer</h4> |
| 1390 |
The two datatypes List and Bytebuffer are used through out the |
| 1391 |
code. They correspond closely in semantics to the Java Arraylist |
| 1392 |
and Stringbuffer types, respectively. They are used to help |
| 1393 |
encapsulate dynamically growing lists of objects or bytes |
| 1394 |
to reduce certain kinds of memory allocation errors. |
| 1395 |
<p> |
| 1396 |
The canonical code for non-destructive walking of a List<T> |
| 1397 |
is as follows. |
| 1398 |
<pre> |
| 1399 |
for(i=0;i<listlength(list);i++) { |
| 1400 |
T* element = (T*)listget(list,i); |
| 1401 |
... |
| 1402 |
} |
| 1403 |
</pre> |
| 1404 |
<p> |
| 1405 |
Bytebuffer provides two ways to access its internal buffer of characters. |
| 1406 |
One is "bbContents()", which returns a direct pointer to the buffer, |
| 1407 |
and the other is "bbDup()", which returns a malloc'd string containing |
| 1408 |
the contents and is guaranteed to be null terminated. |
| 1409 |
|
| 1410 |
<h4><a name="odometer">Odometer: Multi-Dimensional Array Handling</a></h4> |
| 1411 |
The odometer data type is used to convert |
| 1412 |
multiple dimensions into a single integer. |
| 1413 |
The rule for converting a multi-dimensional |
| 1414 |
array to a single dimensions is as follows. |
| 1415 |
<p> |
| 1416 |
Suppose we have the declaration <code>int F[2][5][3];</code>. |
| 1417 |
There are obviously a total of 2 X 5 X 3 = 30 integers in F. |
| 1418 |
Thus, these three dimensions will be reduced to a single dimension of size 30. |
| 1419 |
<p> |
| 1420 |
A particular point in the three dimensions, say [x][y][z], is reduced to |
| 1421 |
a number in the range 0..29 by computing <code>((x*5)+y)*3+z</code>. |
| 1422 |
The corresponding general C code is as follows. |
| 1423 |
<pre> |
| 1424 |
size_t |
| 1425 |
dimmap(int rank, size_t* indices, size_t* sizes) |
| 1426 |
{ |
| 1427 |
int i; |
| 1428 |
size_t count = 0; |
| 1429 |
for(i=0;i<rank;i++) { |
| 1430 |
if(i > 0) count *= sizes[i]; |
| 1431 |
count += indices[i]; |
| 1432 |
} |
| 1433 |
return count; |
| 1434 |
} |
| 1435 |
</pre> |
| 1436 |
In this code, the indices variable corresponds to the x,y, and z. |
| 1437 |
The sizes variable corresponds to the 2,5, and 3. |
| 1438 |
<p> |
| 1439 |
The Odometer type stores a set of dimensions |
| 1440 |
and supports operations to iterate over all possible |
| 1441 |
dimension combinations. |
| 1442 |
The definition of Odometer is defined by the types Odometer and Dimdata. |
| 1443 |
<pre> |
| 1444 |
typedef struct Dimdata { |
| 1445 |
unsigned long datasize; // actual size of the datalist item |
| 1446 |
unsigned long index; // 0 <= index < datasize |
| 1447 |
unsigned long declsize; |
| 1448 |
} Dimdata; |
| 1449 |
|
| 1450 |
typedef struct Odometer { |
| 1451 |
int rank; |
| 1452 |
Dimdata dims[NC_MAX_VAR_DIMS]; |
| 1453 |
} Odometer; |
| 1454 |
</pre> |
| 1455 |
The following primary operations are defined. |
| 1456 |
<ul> |
| 1457 |
<li>Odometer* newodometer(Dimset*) - create an odometer from a set of Dimsets. |
| 1458 |
<li>void freeodometer(Odometer*) - release the memory of an odometer. |
| 1459 |
<li>int odometermore(Odometer* odom) - return 1 if there are more combinations |
| 1460 |
of dimension values. |
| 1461 |
<li>int odometerincr(Odometer* odo,int) - move to the next combination |
| 1462 |
of dimension values. |
| 1463 |
<li>unsigned long odometercount(Odometer* odo) - |
| 1464 |
apply the above algorithm to convert the current odometer combination |
| 1465 |
into a single integer. |
| 1466 |
</ul> |
| 1467 |
|
| 1468 |
<h3><u>Change Log</u></h3> |
| 1469 |
<ul> |
| 1470 |
<li>04/15/2009 - Add major discussion about adding a new output language. |
| 1471 |
<li>03/10/2009 - Fix typos. |
| 1472 |
<li>03/07/2009 - First draft. |
| 1473 |
</ul> |
| 1474 |
|
| 1475 |
</body |
| 1476 |
</html> |
| 1477 |
|