Data structures: frames and tags

Previous: Overview of the program and main() ] [ Top: xmltools index ] [ Next: Global variables (state) ]

I define two struct for storing information about the parse state. Effectively, the current parse stack consists of those nodes between the root and whichever element we're currently parsing. This stack is implemented as a doubly-linked list of FRAMEs.

Within the frame, we stash things like the name of the element at that position, its level in the tree, and a linked list of TAG structures, which are used to count how many of each variety of child elements have been encountered. (This allows us to use numeric position; after all, item(2) refers to the third item encountered, which means that we have to know how many items we've already seen each time an item comes along.)

So the second struct is the TAG struct, of course.

Note that none of our four actions requires keeping any more information on hand than the current slice of the tree. That's one of the advantages of working with streams; the disadvantage is of course that you're restricted in what you can do, and the whole shebang is harder to understand.
typedef struct _frame FRAME;
typedef struct _tag TAG;

struct _frame {
   const char * name;
   int level;
   int offset_in_parent;
   int empty;
   FRAME * back;
   FRAME * next;
   TAG * subitems;

   const char * locator;

struct _tag {
   const char * name;
   int count;
   TAG * next;

Freeing frames and the stack
As long as we've defined our data structures, I'm going to go ahead and show how we free them. (To allocate them is easy: I just use malloc() -- but when I free a frame I need to free its tag list as well.)

Here's how we free a frame:
void free_frame (FRAME * frame)
   TAG * cur;
   TAG * next;
   cur = frame->subitems;
   while (cur) {
      next = cur->next;
      free ((void *) cur);
      cur = next;
   if (frame->level > 0) free ((void *) frame);
And in cases where we know the action is complete and we bail out before processing the entire input file (well, OK, this only applies to snip, because the other three actions are required to output all remaining input), we have a dandy little function to free all the outstanding stack frames.
void free_stack ()
   FRAME * cur;

   while (top->level > 0) {
      cur = top;
      top = top->back;
      free_frame (cur);
   free_frame (top);
Previous: Overview of the program and main() ] [ Top: xmltools index ] [ Next: Global variables (state) ]

This code and documentation are released under the terms of the GNU license. They are additionally copyright (c) 2000, Vivtek. All rights reserved except those explicitly granted under the terms of the GNU license.