Array dependencies in c?
rcktman77
anyone might be able to provide me with some detailed help on how this
is accomplished in c.
Problem Details:
I have a computational surface mesh around an arbitrary geometry. I
have 3 files containing details of the nodes, cells, and integrated
forces at each cell. The first file contains a node identifier (just a
random number) and the x-, y-, & z- cartesian coordinates of that
particular node for all the nodes in the computational mesh. The
second file contains a surface element identifier (again just a number)
along with the 4 node identifiers from the first file which correspond
to the corners of the quadrilateral cell element for all the cell
elements in the mesh. Finally, the third file contains the surface
element identifier from the second file along with integrated x-, y-,
and z- forces for each one of these elements. By summing all of the
surface forces in a particular direction I would get the corresponding
directed force over the entire arbitrary geometry.
Once I read the data from the three files and save it into three
separate arrays, I would like to be able to sum all of the forces in a
particular cartesian direction based upon it's x-, y-, or z- extent.
Thus the force data from the third file has a dependency on the node
x-, y-, and z- coordinates in the first file. How do I relate these
arrays to each other in order to accomplish this within c?
Any help would be appreciated...
Thanks
Gordon Burditt
>is accomplished in c.
>
>Problem Details:
>
>I have a computational surface mesh around an arbitrary geometry. I
>have 3 files containing details of the nodes, cells, and integrated
>forces at each cell. The first file contains a node identifier (just a
>random number) and the x-, y-, & z- cartesian coordinates of that
>particular node for all the nodes in the computational mesh. The
>second file contains a surface element identifier (again just a number)
>along with the 4 node identifiers from the first file which correspond
>to the corners of the quadrilateral cell element for all the cell
>elements in the mesh. Finally, the third file contains the surface
>element identifier from the second file along with integrated x-, y-,
>and z- forces for each one of these elements. By summing all of the
>surface forces in a particular direction I would get the corresponding
>directed force over the entire arbitrary geometry.
I would read each file into an array or linked list of structures,
but replace identifiers that refer to a different type of structure
with a pointer to that structure. As you read in the second file,
look up the references to a node identifier and find a pointer to
the appropriate node. Once you read everything in, follow the
pointers.
You could use array indexes instead of pointers if you have all of the
nodes in one big array.
struct node: identifier, x, y, z
struct surface_element: identifier, 4 pointers to nodes
struct forces: xforce, yforce, zforce, pointer to surface_element.
Since you'll need to look up each reference to an identifier, you might
want a btree index or whatever to speed up the lookup, which you can
discard after you're through reading in the 3 files. Or perhaps sequential
search to initially calculate the pointer is sufficient.
>Once I read the data from the three files and save it into three
>separate arrays, I would like to be able to sum all of the forces in a
>particular cartesian direction based upon it's x-, y-, or z- extent.
>Thus the force data from the third file has a dependency on the node
>x-, y-, and z- coordinates in the first file. How do I relate these
>arrays to each other in order to accomplish this within c?
A struct forces contains a pointer to a surface_element, which contains
4 pointers to nodes, so a reference, given a pointer to a struct forces,
might look like:
forcep->surface_elementp->node[j].x
Ersek, Laszlo
I have written a program for you. It shouldn't be hard to adapt to your
needs.
I also tried to put my money where my mouth is, and employ those
infamous cleanup routines.
The program shouldn't leak memory or crash in any case, or accept any
invalid input. Please try to break it, if you care. I don't have much
floating point experience (error accumulation etc), so those parts may
be a bit less stable. (I do hope that other parts are correct.)
Thanks,
lacos
/*
This program reads three text files with the following line formats:
nodes: <node-id> <x> <y> <z>
Defines a vertex in 3D space. The coordinates are doubles, the <node-id> is
a non-negative long. The program runs in the C (POSIX) locale. No trailing
whitespace is allowed.
elements: <element-id> <v1> <v2> <v3>
Defines a triangle. All tokens are parsed as non-negative longs. The last
three tokens are vertex identifiers, referring to nodes (vertices) defined
in the previous file. No trailing whitespace is allowed.
lights: <element-id> <x> <y> <z>
Similar in format to the nodes file. Such an entry updates the light vector
for a triangle (surface element) defined in the elements file. Each
triangle must have a light vector, or an error is reported. If multiple
light vectors are given for a triangle, the last one will prevail.
The program computes the amounts (magnitudes) of light absorbed by individual
cells, and prints their sum to stdout. If the compute() function is removed
or replaced (which contains static assertions for the values of NDIM and NVX,
see below), then the number of components in a vector and the number of
vertices in a surface cell can be redefined. This should have a correct
effect on the line formats described above.
Not considering the current malloc() / free() wrappers, and error messages
written to stderr, the program can be considered a module with sharp
boundaries. Currently, said wrappers write a malloc() / free() trace to
stderr.
I hereby place this program, "glow.c", in the public domain. (Don't laugh!)
21-Feb-2010 Laszlo Ersek <la...@caesar.elte.hu>
The lacos_rbtree module is available under the GPL, but it should be easy to
replace. For testing, download lbzip2.tar.gz from http://lacos.hu/, and pick
lacos_rbtree.[ch] from it. The tarball also contains a perl script named
malloc_trace.pl, which can be used to check the allocation trace output by
the wrappers mentioned above.
Compiling with gcc on GNU/Linux:
$ gcc -ansi -pedantic -g3 -O2 -Wall -Wextra -o glow glow.c lacos_rbtree.c -lm
Running:
$ ./glow nodes.txt elements.txt lights.txt 2>trace-and-errors.txt
*/
#define _XOPEN_SOURCE 500 /* SUSv2 */
#include <string.h> /* strrchr() */
#include <stdio.h> /* fprintf() */
#include <stdlib.h> /* EXIT_FAILURE */
#include <errno.h> /* errno */
#include <limits.h> /* LONG_MAX */
#include <math.h> /* HUGE_VAL */
#include <float.h> /* DBL_DIG */
#include <sys/types.h> /* getpid() */
#include <unistd.h> /* getpid() */
#include "lacos_rbtree.h" /* struct lacos_rbtree_node */
/* Size of buffer used for transferring lines from files. */
#define LNSIZ ((size_t)1024)
/* Number of components in a vector. */
#define NDIM ((size_t)3)
/* Number of vertices in a mesh cell (surface element). */
#define NVX ((size_t)3)
/* Basename of the binary. */
static const char *pname;
/*
USAGE:
Build or update a context from objects parsed line-wise from a file.
PARAMETERS:
ctx:
The context to build or update.
proc:
Pointer to function that will modify the context, according to the
line passed to it. Must return 0 if the update was successful and -1 if
not.
teardown:
If not a null pointer, then a pointer to a function that undoes the
modifications to the context up to this point, or destroys the context
completely. Will be called if (*proc)() returns -1, or in case of an IO
error.
fname:
Pathname of the file to parse.
RETURN VALUE:
0
if successful (EOF reached without any error),
-1
otherwise. (*teardown)(ctx) will be called before returning, if teardown
is not a null pointer.
*/
static int
parse(
void *ctx,
int (*proc)(
void *ctx,
const char *line,
const char *fname,
long unsigned lno
),
void (*teardown)(
void *ctx
),
const char *fname
)
{
int ret; /* -1: failure, 0: finished, 1: continue */
FILE *f;
ret = -1;
f = fopen(fname, "r");
if (0 == f) {
(void)fprintf(stderr, "%s: fopen(\"%s\", \"r\"): %s\n", pname, fname,
strerror(errno));
}
else {
long unsigned lno;
ret = 1;
lno = 1LU;
do {
char buf[LNSIZ];
if (0 == fgets(buf, sizeof buf, f)) {
if (ferror(f)) {
(void)fprintf(stderr, "%s: \"%s\":%lu: fgets(): %s\n", pname, fname,
lno, strerror(errno));
ret = -1;
}
else {
ret = 0; /* EOF */
}
}
else {
{
size_t len;
len = strlen(buf);
if (len > 0u && '\n' == buf[len - 1u]) {
buf[len - 1u] = '\0';
}
}
if (-1 == (*proc)(ctx, buf, fname, lno)) {
ret = -1;
}
else {
++lno;
}
} /* line read */
} while (1 == ret);
if (EOF == fclose(f) && 0 == ret) {
(void)fprintf(stderr, "%s: fclose(\"%s\"): %s\n", pname, fname,
strerror(errno));
ret = -1;
}
} /* open successful */
if (-1 == ret && 0 != teardown) {
(*teardown)(ctx);
}
return ret;
}
struct hdr
{
long id; /* object id */
long unsigned lno; /* parsed on line number */
};
/*
Parser context for building a red-black tree from objects parsed from a file.
*/
struct rbt_build
{
/* The tree to build. */
struct lacos_rbtree_node **root;
/*
Pointer to function parsing a new element from a line of the file. The
first member of the constructed element must be an initialized instance of
"struct hdr". This function must return the address of the newly
constructed object on success, and 0 otherwise. Any returned object must be
destructible by a single dealloc() call. The aux tree is a hierarchy of
auxiliary objects, utilized during construction.
*/
struct hdr *(*construct)(
const char *line,
struct lacos_rbtree_node *aux,
long unsigned lno
);
/* Root of tree of auxiliary objects passed to (*construct)(). */
struct lacos_rbtree_node *aux;
};
/* The usual comparator for pointed-to longs. */
static int
cmp_long(const void *v1, const void *v2)
{
long id1,
id2;
id1 = *(const long *)v1;
id2 = *(const long *)v2;
return
id1 < id2 ? -1
: id1 > id2 ? 1
: 0;
}
/* Wrapper function around malloc(). */
static void *
alloc(size_t size, void *ignored)
{
void *ptr;
ptr = malloc(size);
if (0 > fprintf(stderr, "%lu: malloc(%lu) == %p\n",
(long unsigned)getpid(), (long unsigned)size, ptr)) {
abort();
}
return ptr;
}
/* Wrapper function around free(). */
static void
dealloc(void *ptr, void *ignored)
{
if (0 > fprintf(stderr, "%lu: free(%p)\n", (long unsigned)getpid(), ptr)) {
abort();
}
free(ptr);
}
/* Parser callback for constructing an object and adding it to the tree. */
static int
rbt_build_proc(void *v_rbt_build, const char *line, const char *fname,
long unsigned lno)
{
struct rbt_build *rbt_build;
struct hdr *obj;
rbt_build = v_rbt_build;
obj = (*rbt_build->construct)(line, rbt_build->aux, lno);
if (0 == obj) {
(void)fprintf(stderr, "%s: \"%s\":%lu: object construction failed\n",
pname, fname, lno);
}
else {
struct lacos_rbtree_node *new_node;
if (-1 != lacos_rbtree_insert(
/* new_root */ rbt_build->root,
/* new_node */ &new_node,
/* new_data */ obj,
/* cmp */ &cmp_long,
/* alloc */ &alloc,
/* alloc_ctl */ 0)
) {
return 0;
}
if (0 == new_node) {
(void)fprintf(stderr, "%s: \"%s\":%lu: out of memory\n", pname, fname,
lno);
}
else {
struct hdr *coll;
coll = *(void **)new_node;
(void)fprintf(stderr, "%s: \"%s\":%lu:%lu: object id collision: %ld\n",
pname, fname, coll->lno, lno, coll->id);
}
dealloc(obj, 0);
} /* object construction successful */
return -1;
}
/* Destroys a tree and frees all linked-to objects. */
static void
destroy(struct lacos_rbtree_node **root)
{
while (0 != *root) {
void *obj;
lacos_rbtree_delete(
/* new_root */ root,
/* old_node */ *root,
/* old_data */ &obj,
/* dealoc */ &dealloc,
/* alloc_ctl */ 0
);
dealloc(obj, 0);
}
}
static void
rbt_teardown(void *v_rbt_build)
{
destroy(((struct rbt_build *)v_rbt_build)->root);
}
/* Very thin wrapper around strtol(). Internals are meant to be exposed. */
static long
prs_long(const char *str, char **endptr)
{
long tmp;
errno = 0;
tmp = strtol(str, endptr, 0);
return
(0L < tmp && tmp < LONG_MAX)
|| (0L == tmp && *endptr != str)
|| (LONG_MAX == tmp && 0 == errno) ? tmp : -1L;
}
/*
Parse a (coord[0], ..., coord[NDIM-1]) tuple from a string. Return 0 if
successful, -1 if failed.
*/
static int
prs_coord(double coord[NDIM], const char *str, char **endptr)
{
const char *scan;
size_t didx;
scan = str;
didx = 0u;
errno = 0;
do {
double dtmp;
dtmp = strtod(scan, endptr);
if (
((HUGE_VAL == dtmp || -HUGE_VAL == dtmp) && 0 != errno)
|| (0.0 == dtmp && (*endptr == scan || 0 != errno))
) {
return -1;
}
coord[didx] = dtmp;
scan = *endptr;
} while (++didx < NDIM);
return 0;
}
struct vertex
{
struct hdr hdr;
double coord[NDIM];
};
/* Parse a vertex object from a string. */
static struct hdr *
prs_vertex(const char *line, struct lacos_rbtree_node *ignored,
long unsigned lno)
{
struct vertex *vx;
vx = alloc(sizeof *vx, 0);
if (0 != vx) {
char *scan;
vx->hdr.id = prs_long(line, &scan);
if (-1L != vx->hdr.id && -1 != prs_coord(vx->coord, scan, &scan)
&& '\0' == *scan) {
vx->hdr.lno = lno;
return (struct hdr *)vx;
}
dealloc(vx, 0);
}
return 0;
}
struct cell
{
struct hdr hdr;
struct vertex *vertex[NVX]; /* only for navigation */
double light[NDIM]; /* comps. of the light vec, filled in later */
int light_init; /* light vector initialized */
};
/* Parse a cell object from a string, leave light vec uninitialized. */
static struct hdr *
prs_cell(const char *line, struct lacos_rbtree_node *vertices,
long unsigned lno)
{
struct cell *cell;
cell = alloc(sizeof *cell, 0);
if (0 != cell) {
char *scan;
cell->hdr.id = prs_long(line, &scan);
if (-1L != cell->hdr.id) {
size_t vidx;
for (vidx = 0u; vidx < NVX; ++vidx) {
long key;
key = prs_long(scan, &scan);
if (-1L != key) {
struct lacos_rbtree_node *vx_node;
vx_node = lacos_rbtree_find(vertices, &key, &cmp_long);
if (0 != vx_node) {
cell->vertex[vidx] = *(void **)vx_node;
continue;
}
}
break;
}
if (NVX == vidx && '\0' == *scan) {
cell->hdr.lno = lno;
cell->light_init = 0;
return (struct hdr *)cell;
}
}
dealloc(cell, 0);
}
return 0;
}
/* Parser callback for finding a cell and modifying its light vector. */
static int
cell_light_proc(void *v_cells, const char *line, const char *fname,
long unsigned lno)
{
long key;
char *scan;
key = prs_long(line, &scan);
if (-1L == key) {
(void)fprintf(stderr, "%s: \"%s\":%lu: unable to parse object id\n", pname,
fname, lno);
}
else {
struct lacos_rbtree_node *cell_node;
cell_node = lacos_rbtree_find(v_cells, &key, &cmp_long);
if (0 == cell_node) {
(void)fprintf(stderr, "%s: \"%s\":%lu: object id not found: %ld\n",
pname, fname, lno, key);
}
else {
struct cell *cell;
cell = *(void **)cell_node;
if (-1 == prs_coord(cell->light, scan, &scan) || '\0' != *scan) {
(void)fprintf(stderr, "%s: \"%s\":%lu: unable to parse coordinates\n",
pname, fname, lno);
}
else {
cell->light_init = 1;
return 0;
}
}
}
return -1;
}
/*
Compute the total amount of light absorbed by all cells. Return 0 if
successful, and -1 if at least one cell has an uninitialized light vector.
*/
static int
compute(double *sum, struct lacos_rbtree_node *cells)
{
typedef int triangle_mesh[3u == NVX ? 1 : -1];
typedef int space_3d[3u == NDIM ? 1 : -1];
struct lacos_rbtree_node *cell_node;
*sum = 0.0;
for (
cell_node = lacos_rbtree_min(cells);
0 != cell_node;
cell_node = lacos_rbtree_next(cell_node)
) {
struct cell *cell;
double edge1[NDIM], edge2[NDIM];
size_t didx;
cell = *(void **)cell_node;
if (0 == cell->light_init) {
(void)fprintf(stderr, "%s: light vector of cell %ld was not"
" initialized\n", pname, cell->hdr.id);
return -1;
}
for (didx = 0u; didx < NDIM; ++didx) {
edge1[didx]
= cell->vertex[1]->coord[didx] - cell->vertex[0]->coord[didx];
edge2[didx]
= cell->vertex[2]->coord[didx] - cell->vertex[0]->coord[didx];
}
/*
Compute the scalar triple product "light * (edge1 x edge2)". This will
yield, not considering sign, twice the amount of the light absorbed by
this triangle cell.
+-- --+
| |
| light[0] light[1] light[2] |
absorption = | det | edge1[0] edge1[1] edge1[2] | | / 2
| edge2[0] edge2[1] edge2[2] |
| |
+-- --+
*/
*sum += fabs(
cell->light[0] * edge1[1] * edge2[2]
- cell->light[0] * edge1[2] * edge2[1]
+ cell->light[1] * edge1[2] * edge2[0]
- cell->light[1] * edge1[0] * edge2[2]
+ cell->light[2] * edge1[0] * edge2[1]
- cell->light[2] * edge1[1] * edge2[0]) / 2.0;
}
return 0;
}
int
main(int argc, char **argv)
{
int ret;
ret = EXIT_FAILURE;
pname = strrchr(argv[0], '/');
pname = pname ? pname + 1 : argv[0];
if (4 != argc) {
(void)fprintf(stderr, "%1$s: usage: %1$s NODES ELEMENTS LIGHTS\n", pname);
}
else {
struct lacos_rbtree_node *vertices;
struct rbt_build bld;
vertices = 0;
bld.root = &vertices;
bld.construct = &prs_vertex;
bld.aux = 0;
if (-1 != parse(&bld, &rbt_build_proc, &rbt_teardown, argv[1])) {
struct lacos_rbtree_node *cells;
cells = 0;
bld.root = &cells;
bld.construct = &prs_cell;
bld.aux = vertices;
if (-1 != parse(&bld, &rbt_build_proc, &rbt_teardown, argv[2])) {
if (-1 != parse(cells, &cell_light_proc, 0, argv[3])) {
double sum;
if (-1 != compute(&sum, cells)) {
(void)fprintf(stdout, "%.*g\n", (int)DBL_DIG, sum);
if (EOF == fflush(stdout)) {
(void)fprintf(stderr, "%s: fflush(stdout): %s\n", pname,
strerror(errno));
}
else {
ret = EXIT_SUCCESS;
}
}
}
destroy(&cells);
}
destroy(&vertices);
}
}
return ret;
}