Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Embedded Systems

Dynamic Run-Time Structures


NOV88: DYNAMIC RUN-TIME STRUCTURES

Todd King is a programmer/analyst with the Institute of Geophysics and Planetary Physics at UCLA. He is also associated with the NASA/JPL Planetary Data System project. Todd can be reached at 1104 N. Orchard, Burbank, CA 91506.


In some instances, an application must deal with data that can have almost any structure. This situation is especially true with database applications where a set of access routines perform the task of extracting data from a database, and making that information available to the application. This involves two interfaces: one between the access routine and the database, and another between the application and the access routine. In most cases, the access routines must be general enough to handle a wide variety of data structures, yet robust enough that the data can be reliably acquired. The best way to meet these criteria is by designing a simple method for data access that serves as a natural extension of the programming language. This article looks at the way to extend the structure concept to do just that.

In general, a structure is a contiguous block of memory that is divided into elements. Each element has a specific data type, possibly a dimension, and a name. When a program that uses structures is compiled, the structure and any reference to its elements are compiled into pointers and offsets. All information about the name assigned to each element is lost. After a particular structure is compiled, its layout becomes fixed and cannot be changed at runtime. So by using conventional structures, a particular application could only support one data format. While this limitation may be fine with some applications, we generally want to have a single application that can deal with any structure. This application is possible if an application can define a structure and the names of its elements at run-time: that is, if there can be dynamically defined data structures with dynamically assigned element names.

Requirements of Dynamically Defined Data Structures

To define a structure dynamically at run-time, an application must perform a few tasks. First, there needs to be a method of specifying elements of the structure, what type each element is, and the name it is to be referenced by. Second, there must be an area of memory set aside for placing the contents of the structure and a method to load the data into the area. Finally, the application must have a way to extract the value associated with a particular element.

To illustrate how to implement dynamic structures, this article examines a special case of structures. In this article, the data types will be limited to those of integer (int), float, and double: all elements will be limited to a single value (no arrays), the element names will be strings of 12 characters or less, and no structure can exceed 1,024 bytes in length. These limitations are self-imposed so that the example in this article will be as clear as possible. Also, the example is designed to be used with databases since database applications typically require dynamic structures to be as highly adaptive as possible. This article describes each step of structure definition and use.

The Data Format

The functions presented here expect the structure definition and the data that the structure is to contain to be in separate external files. The structure definition is in a file with an extension of .def, the data is in a file with the extension of .dat. The two files are associated with each other by a common base name. For example, the file testdata.def would contain the structure definition for the data in the file testdata.dat. This type of physical separation is required for relational databases because each type of information is distinct and different.

The structure definition file has the format

<type> <element name>

where <type> is limited to one of int, float, double. Specifying any other type simply results in an element value of "unknown type." The <element name> can be any name you chose. The length of the name is limited to 12 characters. Only one element definition is allowed per line. The entire file defines only one structure. Think of the base name of the file as the name of the structure.

The data file has a format such that each line of the data file contains all the data for a single structure. The value for each element is specified in terms of textual numbers, with each number separated by a space. Since the definition and data files are textual, it is easy to edit, modify, and enter values.

The Functions

You can define, load, and access a dynamic structure with just four functions. This article discusses functions separately. Listing One contains the dynamic structure header file that all the functions use. Listing Two contains the routines.

Loading the Structure Definition

To use dynamic structures, the first step is to load the structure's definition. You can load this definition with the function

load_v_def(v_file, d_struct) char v_file[ ]; D_STRUCT *d_struct

which interprets the structure definition and prepares the structure for data loading. This function expects the base name (v_file) of the files that contain the structure definition and the data. The structure-definition file must have the extension .def and the data .dat. The file first reads the definition file. The definition declarations look like a C structure definition with the structure wrapper removed with only one variable allowed per line.

Table 1, this page, contains a sample definition file. As load_v_def() reads each line, it extracts the type and name portions. The type is then encoded with a call to v_type(), which compares a textual type to all the allowed types. The type and name are stored in the structure-definition variable, d_struct which is passed to the function.

Table 1: Example structure definition

   int count
   float x
   double y
   float z


After scanning through the definition file load_v_def( ) opens the data file. The file pointer is then stored in the definition structure for use by subsequent calls. This function returns the number of elements defined in the structure or -1 if any failure occurs. A sample call is

printf("%d elements \ n", load_v_defs("example1"));

which loads in the definition of the structure contained in the file example1.def and opens the file example1.dat for the structure data may be read.

Reading a Structure

After a structure is defined and the data file opened, the structure data may be read with this call:

   read_data(d_struct)
   D_STRUCT*d_struct

This call reads a single line from the data file associated with the dynamic structure d_struct and stores the line in a reserved data space. Once a dynamic structure is loaded with data, the value for any element can be retrieved. Because these routines are designed to work with databases, read_data() is usually called multiple times. Each time it is called, the structure is loaded with the next structure of data. The function returns NULL when there is no more data available; otherwise, the function returns a pointer to the data space for the structure. Table 2, this page, lists data that works with these routines.

Table 2: Data which can be used with the data structure definition in Table 1

   1      10.0          20.0             30.0
   2      32.0          64.0            128.0
   3       9.0          18.0             36.0
   4       0.1           1.0             10.0
   5       2.0           4.0              8.0
   6      10.0         100.0           1000.0
   7      12.6       14567.89        123.89
   8      56.7       12598.90        234.75
   9      27.9        1234.90        123.6

Accessing Structure Elements

The value associated with an element in a dynamic structure can be accessed with this function:

   get_v_value(v_name, d_struct)
   char v_name[];
   D_STRUCT *d_struct

Each element in a dynamic structure has an associated name. Since the name is represented as a string of characters, a string with the element name in it is passed to get_v_name() each time the value for an element is needed. The function then searches all the elements of the structure d_struct for the name. If the function finds an element, then the data associated with that element is extracted from the data space. Since we chose to limit the example to numeric types, the data is transformed to a double variable. This transformation is made so that only one function is needed to access all numeric types.

Completing the Read

After completing a scan through the data file, the data file associated with the dynamic structure should be closed. The function

   end_read(d_struct)
   D_STRUCT*d_struct;

performs the close of the file pointer associated with the dynamic structure d_struct.

Using the Element Values

An example of how to use the values of the dynamic structure is the function

   print_v_value(v_name, d_struct)
   char v_name[];
   D_STRUCT *d_struct;

This function prints the value associated with the element with the name v_name, which is the dynamic structure d_struct. The function looks at the type of the element, formats the value accordingly and prints the value into a field that is (at least) 16 characters wide. This function checks if the element is declared and if the declared type is supported. If a valid element is requested, a call to get_v_value() is made. The return value from get_v_value() is typecast to its declared type to remove any ambiguity for printf(). If the return value is assigned to a variable, then the value would automatically be typecast by the action of the assignment. Since get_v_value() returns a double, the value may be assigned to any numeric type without any loss of precision, regardless of the elements numeric type.

The Sample Program

The sample program in Listing Three uses all the functions presented here. Its purpose is to print to the screen, in a simple tabular format, the requested elements of a dynamic structure. The structure to use and the element names to print are given on the command line. The, syntax following the program name is

<d_struct>  <element_name>
      [<element_name> ...]

where <d_struct> will be the base name of the structure file and <element_name> can be any name you choose, whether it is in the structure or not. If the given <element_name> is in the structure, then the value associated with it is printed, if <element_name> is not the structure, the phrase "Unknown element" is printed. If <element_name> is in the structure definition file and the element is specified as a type that is not supported, the phrase "Unknown type" is printed. The example scans through the data file and displays as many lines as there are structures in the data file.

Extensions of The Concept

With a little work, you can make the routines in the example even more useful. One immediate addition is to rewrite the routines to handle binary data. Even with binary data, the structure definition file should be text, which allows for readable self-documented data. Also, adherent to relational models, the structure definition, and data should be separate files. Other additions include changing the names of elements, allowing the element values to be written (in the example, they're read only), and adding new data types.

_DYNAMIC RUN-TIME STRUCTURES_ by Todd King

[LISTING ONE]

<a name="01fb_0011">


/* Dynamic structure include file */

#ifndef _V_STRUCT_
#define _V_STRUCT_

#include <stdio.h>

char *Var_types[] = { "int", "float", "double", ""};
enum V_TYPES { UNKNOWN=-1, INT, FLOAT, DOUBLE };

#define MAX_VAR     256
#define MAX_NAME    16
#define MAX_DATA    1024

typedef struct {
  char name[MAX_NAME];
  enum V_TYPES type;
} ELEMENT;

typedef struct {
  ELEMENT element[MAX_VAR];
  int count;
  char data[MAX_DATA];
  FILE *source;
} D_STRUCT;

#endif



<a name="01fb_0012"><a name="01fb_0012">
<a name="01fb_0013">
[LISTING TWO]
<a name="01fb_0013">


#include "d_struct.h"

/* Returns the number of definitions, -1 if any error occurs */
int load_v_defs(v_file, d_struct)
char v_file[];
D_STRUCT *d_struct;
{
  int cnt;
  char type_text[12];
  char file_name[16];
  FILE *fptr;

/* Open variable definition of variable names/record structure */
  strcpy(file_name, v_file);
  strcat(file_name, ".DEF");
  fptr = fopen(file_name, "r");
  if(fptr == NULL) return(-1);

/* Initialize */
  d_struct->count = 0;

/* load in definitions */

  cnt = d_struct->count;
  while(fscanf(fptr, "%s %s", type_text,
    d_struct->element[cnt].name) != EOF)
  {
    d_struct->element[cnt].type = v_type(type_text);
    cnt++;
    if(cnt > MAX_VAR) return(-1);
  }
  d_struct->count = cnt;
  fclose(fptr);

/* Now open data file - leave open for reading of data */
  strcpy(file_name, v_file);
  strcat(file_name, ".DAT");
  d_struct->source = fopen(file_name, "r");
  if(d_struct->source == NULL) return(-1);
  return(d_struct->count);
}


/* Invalid type returns -1, otherwise index of type in 'Var_types' */
int v_type(type_text)
char type_text[];
{
  int i = 0;

  while(strlen(Var_types[i]) != 0)
  {
    if(strcmp(type_text, Var_types[i]) == 0) return(i);
    i++;
  }
  return(-1);
}

/* Brings a record into the data workspace */
char *read_data(d_struct)
D_STRUCT *d_struct;
{
  return(fgets(d_struct->data, MAX_DATA, d_struct->source));
}


/* extracts a data value from the record */
/* which corresponds to a dynamic name   */
double get_v_value(v_name, d_struct)
char v_name[];
D_STRUCT *d_struct;
{
  int i;
  double dval;
  char tmp_fmt[256], fmt[256];

  strcpy(fmt, "");
  for(i=0; i< d_struct->count; i++)

  {
    if(strcmp(d_struct->element[i].name, v_name) == 0)
    {
      strcpy(tmp_fmt, fmt);
      strcat(tmp_fmt, "%lf");
      sscanf(d_struct->data, tmp_fmt, &dval);
      return(dval);
    }
    strcat(fmt, "%*lf ");
  }
  return(0l);
}

/* Terminates the all reads - clean up */
int end_read(d_struct)
D_STRUCT *d_struct;
{
  close(d_struct->source);
}

/* Prints a variable - in a format according to its type */
int print_v_value(v_name, d_struct)
char v_name[];
D_STRUCT *d_struct;
{
  int i;

  for(i=0; i<d_struct->count; i++)
  {
    if(strcmp(v_name, d_struct->element[i].name) == 0)
    {
      switch(d_struct->element[i].type)
      {
    case INT:
      printf("%16d ", (int)get_v_value(v_name, d_struct));
      break;
    case FLOAT:
      printf("%16.6f ", (float)get_v_value(v_name, d_struct));
      break;
    case DOUBLE:
      printf("%16.6lf ", (double)get_v_value(v_name, d_struct));
      break;
    default:
      printf("%16s ", "Unknown type");
      break;
      }
      return(1);
    }
  }
  printf("%16s ", "Unknown Variable");
  return(0);
}



<a name="01fb_0014"><a name="01fb_0014">
<a name="01fb_0015">
[LISTING THREE]
<a name="01fb_0015">

/* Example program - reads data and prints it on the screen */
/* Command line arguments are:                              */
/*      example <filename> <colname> [<colname> ...]        */

#include "vman_1.c"

main(argc, argv)
int argc;
char *argv[];
{
  int i;
  double dval;
  D_STRUCT d_struct;

  if(argc < 3) {
    printf("Proper usage: example <filename> <colname>  [<colname> ...]\n");
    exit(-1);
  }

  load_v_defs(argv[1], &d_struct);
  for(i=2; i<argc; i++) printf("  %12s   ", argv[i]);
  printf("\n");
  while(read_data(&d_struct))
  {
    for(i=2; i<argc; i++)
    {
      print_v_value(argv[i], &d_struct);
    }
    printf("\n");
  }
  end_read(&d_struct);
}










Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.