A long time ago, Leor Zolman wrote and distributed the BDS C Compiler for CP/M (what's that?). Following a several-year hiatus from computer-compulsiveness to learn some people skills, he got married, dragged his disbelieving wife to Kansas and joined the staff of R&D Publications, Inc. Two years later his wife has almost forgiven him. You can reach him at leor@rdpub.com or uunet!bdsoft!rdpub!leor.
Here at R&D Publications, we do most of our internal data processing on a single SCO XENIX/386 system running the latest available releases of the Informix database system for XENIX. At any time, there may be up to 30 users sharing the system. Many of those users run under the FACET/TERM software package to launch multiple login sessions on their individual serial terminals. Thus it is not unusual to see up to 50 logical users, and perhaps up to 150 system processes, active at any single point during the business day. Despite the load, the system response time experienced by our users is pretty darn good.
And now for the punch line: our CPU is just an inexpensive 386/25 Taiwanese clone. Even with 12Mb of RAM, system units such as this one sell for about half the price of the 10Mb hard disk drive I purchased in 1980. My intention isn't to tout the cost-effectiveness of imported hardware; I just think it is remarkable how well a contemporary entry-level CPU can be made to perform. A system load such as ours could have brought even a minicomputer system to its knees not so long ago.
One way we've managed to streamline our system is to eliminate as many CPU-intensive tasks as possible from the daily during-business-hours load. We did this partially through the design of a general-purpose sequential overnight job spooler. From among the set of tasks that used to be routinely run during the day, we looked for the worst bottlenecks. We then modified the shell scripts that control these programs to allow users to schedule the programs for overnight execution.
The CMENU menu system I shall be describing in this series of columns was originally created as part of our effort to reduce the overall daily system load. In the end, CMENU also brought some welcome spinoffs: it significantly reduced the Technical Department's maintenance requirements, and enhanced the usability, speed, and efficiency of the menu system for our users.
The 50-Percent Solution
R&D's entire internal business management system revolves around menus. All the menus stem from two root menus we invoke from the system prompt. The first of these two menus contains all invoice processing and customer-related tasks. The second main menu handles our advertising subsystems and personal utilities (E-mail, calendar maintenance, business letter generation, etc.). Counting all the submenus and sub-sub-menus, there are roughly 300 distinct menu options in the system. Many of these are shell scripts that manage standardized parameter entry and invoke Informix report generators.Before CMENU, this entire menu system ran under Informix's own menu-processing scheme. Menu headers and their associated lists of menu items existed as database tables in a master/detail relationship. The mechanism supplied by Informix for creating and maintaining the menu system relied on a screen form built to work with Informix's general-purpose table query tool, Perform. This screen, unfortunately, allows only one menu selection to appear on the screen at a time, which made on-line searches for a particular item in the menu hierarchy a repetitive, time-consuming operation.
Informix integrated their menu-maintenance programs into their new-generation SQL runtime module, but imposed the limitation that each database can contain only a single associated menu system. Since there were two distinct menu hierarchies which we used with our one major database, we had to create a dummy database just to support the existence of a second independent menu hierarchy. Each time a user invoked a menu, the menu program launched two system processes. The first was an SQL interpreter to run the user-interface portion of the menu, and the second was a back-end SQL engine that interfaced with the actual database. Then, in the cases where we had logically isolated some additional menu subsystems from the main menus (as when developing new subsystems or when we had not yet ported an existing application from our old Informix 3.3 system and the menus were still in the old format), any invocation of an external (non-integrated) submenu from the main menu system meant that
Clearly, this was not an effective use of system resources.
- all the processes from the main menu were still active,
- a new set of processes was launched to handle the new menu, and
- yet more processes came along when the user made a selection from the new menu!
In contrast to the clumsy internal implementation and maintenance difficulties of Informix's menu system, the end-user interface portion of the Informix system is remarkably clean, intuitive, and generally user friendly. I chose largely to retain the look and feel of their user interface in designing CMENU as a replacement for their menu system. This choice allowed changeover at R&D to take place with a minimum of retraining. After installation of the new CMENU system, a short e-mail message to all users outlining CMENU's few extensions to the Informix menu system's user interface sufficed for the entire retraining.
The Best Of Both Worlds
To the end-user, CMENU-based menus appear roughly the same as their Informix-based predecessors. Internally, however, CMENU works quite differently. Rather than being built on top of a complex database package, CMENU is a standalone system using a pre-compilation scheme to make execution (interpretation) of menus as efficient as possible.The menu compiler module, named cmenu, compiles an ASCII-format menu specification file containing any number of "menu screen" specifications into an intermediate binary object format. The menu runner module, rmenu, loads the intermediate file(s) into RAM and executes the menu system as specified.
The advantage of pre-compiled menu specifications is that most of the hard work of parsing the source code and compiling it into a form suitable for efficient runtime interpretation only happens once, at compilation time. When rmenu is invoked, it only has to display the text on the screen, interpret the user's keystrokes, process menu navigation commands, and submit the action commands associated with selected menu commands to the operating system for execution.
To reduce the number of processes needing to be launched by the runtime menu system, rmenu employs a recursive data structure. Separate screens of a menu system may be compiled either together in one source file or separately in distinct physical source files. At runtime there is no need to spawn additional processes just to traverse up and down through the menu structure, even when that structure contains separately compiled menu files. A single process coordinates all the dynamic loading and menu navigation operations.
Through a rich, powerful repertoire of options in the CMENU specification language, a high level of control over menu behavior is possible in response to the varying requirements of application programs and shell scripts. Some applications, for example, may require a prompt after their completion to allow users to read vital information left on the screen immediately before the application terminated. Other applications never leave any useful information on the screen and so do not require a prompt. Still other applications may sometimes require a prompt and sometimes not, based upon their exit status code. Any of these cases can be handled easily by CMENU (at least the UNIX version) through appropriate use of the specification language.
Two Programs, Two Personalities
The cmenu and rmenu programs share a common intermediate menu object format and not much else. Each evolved in its own style of programming, necessarily distinct from the other due to the disparate natures of the two connected tasks.The menu compiler, cmenu, operates as an iterative state machine. It processes the source file text sequentially, and maintains all state information in global data shared by all the token-processing functions of the program.
To understand why such a scheme is appropriate for the cmenu program, note that the CMENU specification language, like C itself, is not block-structured. In C, you define all functions at one top level and can't define functions within functions (although you can reference functions from within other functions). Other constructs in C, such as expressions, do have a recursive nature, but there are no such recursive expression structures in a CMENU specification. Thus, a sequential approach works well for parsing CMENU source code and also makes the program less complicated.
On the other hand, the sort of simplicity inherent to cmenu wouldn't work for rmenu without severely limiting its power. At run time, menus must be callable from other menus, and, ideally, there should be no structural limitation on the depth to which menus nest. In practice, of course, memory may eventually run out.
Several steps can be taken to increase the practical limit on the number of menus or total menu items a single logical menu system can contain. The first is to design a longitudinal menu tree structure, to take maximum advantage of the dynamic loading features of CMENU. The second is to compile the CMENU program using the huge memory model, so array-size limitations are eliminated. All my testing was performed with the CMENU programs compiled with the default "small" memory model, for efficiency.
So, one way rmenu differs from cmenu is that rmenu's menu processing functions support recursion. There is only one trivial case where rmenu would not employ recursion: when a complete menu system consists of only a single menu file, and that file contains only a solitary menu definition with no submenu references. In any other configuration, recursive calls will always occur.
...And At Least Two Operating Systems
Another distinction between the two programs is platform-dependence. Both programs support C compilers of varying ANSI-compliance, but aside from that, cmenu's code is pretty much system-independent. Since cmenu simply compiles a text file into a binary file, the issue of real-time user interface management (i.e., curses) does not arise.rmenu, however, must deal with the user's screen. Pandora's box immediately opens, because DOS and UNIX systems have completely different ideas of what the user's terminal is like. UNIX sees terminals as serial devices, while DOS sees them as direct memory-mapped devices (that is an oversimplification, but it'll suffice for present purposes).
A standard utility library for managing the screen — the curses library — is available with most UNIX-like systems. The curses library represents enough of a standard that several PC-based implementations have even popped up. I selected a PC curses package that we distribute through our CUG library. The package is called, appropriately, "PC Curses" (CUG volume 298), and it was written by Jeff Dean (who, by the way, volunteered extensive assistance to me in checking out the CMENU package for bugs and portability issues. Thank you Jeff!).
PC Curses allows the CMENU system to be compiled under DOS with very few conditionally compiled variations in the terminal-handling code. This is possible because Jeff's library uses the same standard function names as the UNIX versions of curses.
There are some minor variations between the UNIX and DOS flavors of curses, and there are also other areas of the CMENU system that must be handled differently between UNIX/XENIX and DOS. The most irritating one involves the idea of "current working directory," or CWD, and how the CWD can change unexpectedly after submitting command strings to the respective operating system's command processors.
Under UNIX, a subshell can never alter the parent shell's current working directory, period. There are subtle tricks for letting a child process have a say in setting the CWD of its parent, but ultimately the parent is always in control of its own CWD.
Not so under DOS. Once you pass an unknown command string to the command processor under DOS, you can't know for sure where the CWD will be upon return. The current working directory and currently selected drive (two distinct global modes, as we'll see later) must be saved before making any system calls. Then, upon return from system calls, those settings must be restored.
Finally, screen and terminal characteristics may vary from system to system. Features such as lines per screen, column width, and operation of certain keys are terminal-dependent. Under UNIX, for example, certain versions of curses support predefined cursor key codes and certain others do not. Under XENIX, at least one curses library function name is different than the equivalent curses function name on other UNIX-variants. CMENU's header files try to handle known variations such as this, to keep the program text as uncluttered with conditional compilation directives as possible.
The CMENU system may be compiled interchangeably under either DOS or XENIX without requiring any changes to the code; just use the appropriate makefile for the target operating system. Figure 1 shows the makefile for DOS. This version works specifically with the Borland C++ make program, but can easily be adapted to other dialects of make. Figure 2 shows the UNIX/XENIX version of the makefile.
Each makefile uses the C compiler's -D command line option to define the target operating system and cause the appropriate variations of system-dependent code to be compiled. Several lines at the top of the makefile may be customized as needed to configure CMENU properly for the desired target environment.
There may be issues with UNIX-variants (other than XENIX) that I haven't foreseen. One area that I know must be changed for other UNIX systems is the way the makefile specifies the names of the curses library object files. It works as supplied on XENIX, but I can make no other guarantees.
The CMENU language
Figure 3 shows a modified BNF description of CMENU's menu definition language. This section presents a detailed English description.A CMENU description file has one or more menu definitions. The first menu appearing in the file is always the main menu for that file, and need not have a name. Since additional menus appearing in the same file can only be accessed by name via the lmenu (local menu) option in the main menu, all such additional menus must be given unique names.
Each menu definition begins with a menu clause, consisting of the keyword menu, an identifier (optional only for the main menu, required otherwise), and an optional colon. After the menu clause come any desired menu options, followed by the item definitions. The menu definition is complete when the endmenu keyword appears.
A menu system may consist of any number of separate menu files (or compiled units). Traversal across compiled units at runtime is totally transparent from the user's point of view.
Selecting and returning from an external menu (that is, a separately compiled unit) appears the same as selecting and returning from a local menu, since the user receives no indication that another compiled unit has just been dynamically loaded. Within a single menu definition, global menu options may be specified immediately after the opening menu clause, but before the first item has appeared. If such options appear in a menu, they control screen processing for the entire menu (but not for any submenus that might be invoked). The available menu options and their functions are:
path — Defines the default path for all action items in the menu
escape, noescape — Tells whether to allow shell escapes
spacing — Sets vertical spacing between items (single or double)
columns — Tells number of horizontal columns to be used (1 - 6)
There is code supporting the compilation of a text alignment option, but there is currently no runtime support for this option. There didn't seem any real need for it. In case someone wants to add customized options to CMENU, I've left the code in as a template to provide a starting point for work on such extensions.
After all desired menu options have been specified, the item definitions follow. Each item definition begins with an item clause, consisting of the keyword item, an optional item identifier, an optional colon, and an optional text string (the text string is optional only because the item text may alternatively be specified in its own text clause later in the item definition).
Not all components of the item clause are always optional. If the clause does not include an item identifier but does include a text string, a colon between the item keyword and the text string is required. This keeps the text string from getting parsed as an item identifier. When both an identifier and item text are present, the colon may be omitted.
The only strict requirement for each item definition, other than the item clause itself, is an action clause. The action clause must be one of the following:
action — Execute a system command, or set of commands
lmenu — Run a local menu (one in the active .mnc unit)
emenu — Run an externally compiled .mnc unit
exit — Return to the previous menu; if none, exit
A menu does not require an exit action, since the user may directly exit a menu anytime via the e or x runtime keystroke commands. Sometimes, though, displaying the exit option on the screen with other menu items can be useful. I've included the exit action code to provide that capability.
Before or after the action code, some item options may also appear. Many of these item options have default behaviors that apply in the absence of explicit directions. Such defaults are hard-wired at rmenu compile time by definitions in the rmenu.h header file. They may be chosen to suit the specific requirements of your user environment. Any item options stated explicitly in a CMENU specification always override the defaults. These are the available item options:
text — If the text isn't part of the item clause, a text clause must be provided.
help — A help message, appearing only when the highlight bar is on the associated option.
path — A full pathname overrides the default path; a relative pathname is appended onto the default path.
prompt, noprompt — Controls whether the system pauses for a keystroke following termination of an action item.
pause, nopause — Equivalent to prompt/noprompt above (I couldn't decide which terms were clearer, so I left them both in).
preclear, nopreclear — Controls whether an explicit screen clear occurs before execution of an action item.
nextitem — Tells where to send the highlight after the current item has been executed. Options are:
first — to the first item in the menu
last — to the last item in the menu
next — to the next item in sequence
<ident> — to the item with the given identifier
If no nextitem clause is present, the default is for the highlight to remain on the item that was just run.
The path string, if specified, causes a cd command to be pre-pended to the action string when running under a UNIX variant. If running under DOS, then both a cd and a drive selection operation are performed, to ensure that the named drive/directory is current before the associated action statement executes.
Under UNIX, the action clause (with possibly pre-pended cd statement) is passed directly to a system() call. DOS does not support multiple commands on a single command line the way UNIX does, but some special processing supports compound statements under DOS. This code begins by scanning the action text for semicolons. If it finds any, then it breaks the action text into a set of individual subcommands as delimited by the semicolons. Each subcommand is then processed by an independent system() call. This allows several DOS commands to be chained together in a single action clause text string.
Upon completion of all listed actions, the original drive and path are restored under DOS. Under UNIX, this isn't necessary, since a child shell cannot alter the parent's current directory.
An item definition implicitly ends when either another item clause or an endmenu keyword is encountered.
CMENU Language Minutiae
The preceding section sums up the high-level structure CMENU language. There remain only a few syntactic details to mention before moving on.Tokens in the CMENU language are delimited by one or more of the following: any whitespace (space, tab, or newline), ; (semicolon) or , (comma). Figure 4 and Figure 5 illustrate the format I use, but there is no reason (syntactically) that you couldn't create something to rival Don Libes's "Obfuscated C Code" winners if that is what you want to do.
The parser considers a string to be any sequence of printable characters that is not a keyword and does not contain any whitespace. Strings are legal as the operand of a path, text, or action clause, and as labels where needed. Single or double quotes may be used to delimit a string, and, except in the case of labels, prudence dictates doing so. The quotes, however, are not strictly required if the string contains no whitespace; I have, in a rush, written lines such as
action mailwith only a token amount of guilt (sorry) for omitting the quotes around mail. Within a string, all characters are taken literally, including the backslash character (\). There is no provision for specifying control characters. There is only one restriction on allowable character codes within a string: single and double quote characters cannot both appear within the same string. If you need to include double quotes within a string, delimit that string with single quotes (and vice-versa).If your editor can generate control characters, you can put them into CMENU strings. In practice, however, I've never run across the need to insert a non-printable character into any CMENU text string.
Identifiers, used to assign labels to menus and items, follow the same naming rules as C variables, with one exception: case is insignificant. Internally, all identifier names are represented by lower-case characters.
Any token beginning with a digit is parsed as the beginning — and typically the end, since meaningful values are all single-digit here — of a decimal integer value, appropriate only as the operand to either the spacing or columns options.
Finally, the # character (except inside a quoted string) denotes a comment. All characters from # to the end of the line are ignored. A line may begin with #.
The Saga Of Pathname Delimiters
Even after years of programming in C under DOS, I still forget to double up the backslashes in pathname strings at least haft of the time. For example, I'll have a statement at the top of my C program that looks something like:
#define PATH "c:\foo\bar"The compiler sees a string containing c:, a formfeed, oo, a backspace, and ar. This is clearly not the intended result. What I really meant to write was:
#define PATH "c:\\foo\\bar"This kind of goof draws no compilation errors; often, it isn't until after I've become thoroughly confused and fired up the debugger that I find the mistake and kick myself. To keep from having to use the double-backslash notation in CMENU source files, I decided not to give the backslash character any special meaning in the CMENU specification language. As described above in the section on strings, there is no notation for escape sequences and single backslashes in strings are taken literally.Originally, I had included a feature in cmenu whereby any forward-slash (/) characters encountered in path clauses are automatically mapped into the paths-delimiter character appropriate for the target operating system (i.e., either a back- or forward-slash.) I did this only for the path clause, however, because that is when most CMENU pathnames appear. Later, Jeff Dean pointed out to me that pathnames written with forward-slash (/) characters under DOS worked just as well as ones with backslash (\) characters! My copy of the Waite Group's MS-DOS Bible didn't mention any such equivalence, however, so I began to wonder.
As it turns out, the slash-translation is performed by the C file I/O library functions supplied with the various C compiler packages, and not by DOS itself. Performing such translation explicitly within a C program for DOS is therefore redundant, and I removed my original translation code from CMENU.
Then, I found that pathnames written with forward-slashes worked correctly in path statements, but not in action clauses. Thinking more about it, I ought not have been surprised: CMENU action statements are run by simply passing the supplied action text to the operating system's own command interpreter, not to a C file I/O function. Thus the slash-translation provided in the C file I/O library never gets performed, and DOS ends up choking on the forward-slashes.
The net result of all this is the following rule of thumb: to be absolutely safe, always use backslashes. If you prefer to use forward-slashes, then use them only in a path clause, never in an action clause.
A Sample Menu System
Figure 4 and Figure 5 represent a small-scale menu system illustrating most of CMENU's features. I've arbitrarily chosen a UNIX-based example, but a DOS version would not be too different.In t.mnu (Figure 4) , the main menu has no identifier label (OK for the initial menu in a file), allows shell escapes, and is to be displayed with double spacing on the screen. There are nine items in this main menu.
The first item illustrates the automatic prompting feature of CMENU that is in effect when the DEF_PROMPT symbol (to be covered later in the rmenu section) is set to ON_ERROR. This causes rmenu, in the absence of an explicit prompt or noprompt option, to prompt after an action has been completed if and only if the status returned by that action is non-zero. In this example, a prompt is issued only if the user typed an e in response to the prompt displayed by the test.sh shell script (see Figure 6) . Upon return from test.sh, the highlight bar moves over to the item labeled "zot" below.
Since DOS systems do not provide standardized support for direct return values from system calls, the ON_ERROR option for the DEF_PROMPT feature is only meaningful under UNIX. Under DOS, DEF_PROMPT may be set to either YES or NO, and individual menu items may always override that default by including the prompt or noprompt options.
The second item in the main menu calls up an external menu, t2.mnc, located in subdirectory test. Since the item path is given relatively (that is, no leading / character or, if it were under DOS, no drive letter either), the path is treated as a subdirectory of the current default menu path. Since no path clause was specified in the menu options section, the default menu path is the current working directory at the moment of rmenu invocation.
The third and fourth items illustrate different ways to invoke an action. Using the exec command (UNIX only) saves a process.
Item zot (lines 34-38) contains help text. This text is displayed on the screen only when the highlight bar is on that item. Note that in order to display the double quotes around the word "Zot," the entire help text is delimited by single quotes.
Finally, the prompt command in menu item zot causes a prompt to be issued after the action is executed, forcing the user to press a key before the information left on the screen is erased and the menu screen is redisplayed.
The next item simply illustrates how nextitem specifications may be backward as well as forward.
The next item invokes the local menu named bar, appearing at the end of the file. The last few items are just filler, to illustrate what happens when the total number of items exceeds the capacity of the default screen arrangement. Since there are 18 lines available for item information in the standard 24-line screen setup, double spacing the items means that only nine would fit in the single-column format. If an additional menu item were created by cloning the filler items, then rmenu would automatically go into two-column mode in order to preserve the double spacing specified in line 13. If the spacing were set to 1 or omitted entirely, rmenu would go into single-spacing mode and remain in single-column mode. There is a function in rmenu devoted entirely to determining the most appropriate screen arrangement for any given menu. That function uses a heuristic based upon the number of items in the menu and any explicit spacing and column directives given. I'll cover this, in gory detail, when discussing the rmenu program later on in the series.
Following the endmenu keyword, a second local menu named bar is defined. The local menu options serve to disable shell escapes and to set the default path for actions in this menu to /usr/bin. Since setting a path this way just generates a cd statement before running an action, a named action need not necessarily reside in the directory specified in a path clause, as long as the program can be found somewhere along the default system path. In many system paths, the current directory is searched first; if this is the case on your system, any executable commands in the directory named by a path clause take precedence over similarly named commands residing elsewhere along the system path.
There is nothing startlingly new about the three items in the bar menu. I used semicolons instead of newline to separate some of the clauses, just to show that it's permissible.
The second menu file, t2.mnu (Figure 5) also lacks interesting features; it was included to complete the illustration of a two-file menu system. Note that the default path for all actions is the same as the default path of the calling menu (in this case, the path specified by the second item in the first menu of the t.mnu file), since menu foo contains no explicit path clause to override that default path.
One final note: an action clause may contain explicit commands to change the path, effectively superseding all previous default paths. An extraneous cd command may be executed if a path clause is given and an explicit cd command is present within the action text. Such extra cd commands generate only a negligible quantity of CPU overhead and may be effectively ignored.
Common Menu
Data Structures
There are three header files in the CMENU package. The master header file, cmenu.h, contains the symbolic constant definitions (#define statements) that control common data structures and operating-system-specific code for both the cmenu and rmenu programs. cmenu.h is included by all program modules, so it performs the inclusion of the standard C header file, stdio.h.Besides including cmenu.h, the cmenu and rmenu programs each have their own personal header files, named ccmenu.h and rcmenu.h respectively. Both of these header files use the symbolic constants and data types defined in cmenu.h to build the actual data structures needed to perform their specific tasks.
We'll look first at the common, elementary structures defined in cmenu.h, so we can see how cmenu and rmenu later build upon them.
The Basics
As noted earlier, cmenu and rmenu share the intermediate .mnc file format; consequently, most of cmenu.h (Listing 1) is devoted to declarations of the structure types used in that format. The two major structures are named MENU and ITEM. Within these two structure types, string elements are all defined as char arrays (as opposed to pointers), Boolean elements have type BOOL (really just char), logical and multiple-choice elements have type char, and numeric elements have type int (even though they would never be negative and probably never exceed a value of 255).The logical elements have three possible values: YES, NO, and DEFAULT (as opposed to the Booleans, which can only be TRUE or FALSE). YES and NO values appear when an explicit option was written for that element in a menu or item definition; the value DEFAULT signifies that no explicit option was written, and rmenu should, in that case, perform the actions dictated by a set of default action definitions specified in the rcmenu.h header file.
If a text element is not specified, it is represented as the null string (first character is a '\0'). If a numeric element is omitted, the value inserted is DEFAULT, as described above.
A MENU (a typedefed alias for struct menu) contains the following elements:
title — The menu title, displayed at the top of a menu screen
path — The default action path for all items (absolute or relative)
nitems — The number of items present in the menu
align — (not used)
columns — Number of columns specified for the item display
spacing — Spacing specified for the column display
widest — Length of the widest item text (in characters)
escape — Whether shell escapes are permitted
An ITEM (really struct item) contains:
text — The text to be put up to represent that item (may be truncated if the space is needed for multiple columns)
path — the path for the item (absolute or relative)
action — The text of the command(s) to be submitted to a system() call when the item is chosen to be run, orthe name of an external menu if the action is emenu
help — The text of any help info, put up on the screen when the item is under the highlight bar (never truncated)
pre_clear (logical) — Whether to clear the screen before the action
post_clear (logical) — Whether to clear the screen after the action
prompt (logical) — Whether to pause before returning to menu
acttyp (multi-choice) — Tells what brand of action to perform (choices: command, lmenu, emenu or exit — represented by the ACT_* symbolic constants)
lmenunum — If the acttyp is ACT_LMENU, specifies the index for the specified local menu in the menu table
nextcode (multi-choice) — Tells how the next item is to be determined (choices: first, last, next, or direct — NXT_* symbols)
nextitem — If nextcode is NXT_DIRECT, this contains the index of the next item to be highlighted.
The way that MENU and ITEM objects are combined is not specified in cmenu.h, because that combination is different in cmenu than it is in rmenu. For the remainder of this installment I'll focus on the cmenu program and its own data data structures.
The .mnc Format
The format of compiled .mnc files is summarized in Figure 7. Remember, this is a binary format, not an ASCII one.The first item in an .mnc file is an integer value that tells how many (local) menus are defined in the file. Immediately following this count is the MENU structure for the first menu, and after that come the ITEM structures for each item in the menu. The number of items in each menu is part of the information stored in the associated MENU header, so there's no need to store separate item counts in the file format.
That's it; the .mnc format is fairly simple, conceptually. To actually generate it, however, requires a bit more complexity... now the real fun begins!
At Last, cmenu
The cmenu program is essentially a big state machine, whose purpose is to scan through the sequential ASCII token stream of one or more CMENU specification files and produce a correctly compiled .mnc output file corresponding to each input file.At the heart of cmenu's operation is a structure named keywords, defined in ccmenu.h (Listing 2, lines 190-228). keywords defines a couple of attributes to be associated with each possible keyword token. The tokens represent each symbol, keyword, or special condition (such as EOF) that the CMENU language recognizes.
The first attribute, keyword, is the text of the keyword itself; for tokens that have no printing text associated with them, I've contrived some special identifying sequences (see lines 191 and 223-226) that assisted me during interactive debugging of the cmenu program.
The other attribute is a pointer to the processing function called when the associated token shows up in the input stream. All token processing functions are named do_whatever, where whatever is the name of the token. There are also additional do_whatever functions not tied to a particular token, but called occasionally under special circumstances.
An enumeration constant list (lines 43-58) defines a symbolic name for each keyword. These symbolic names appear in exactly the same order as their corresponding keywords table entries; thus, the symbolic name for each token has a value equal to that token's physical index position in the keywords array. Since the symbolic values are used to represent tokens during the parsing of input text, this arrangement has a side-effect that facilitates debugging of the cmenu program: you can keep a running display of the ASCII string associated with the most recently parsed token by placing the expression
keywords[token].keywordinto a watch window.For compilers that do not support enumeration constants, the "old-fashioned" way of defining a set of sequential symbolic values is shown in lines 60-99. This section of conditionally-compiled code is used instead of the enum section when __STDC__ (a pre-defined symbolic constant indicating ANSI compliance) is undefined.
There are a couple of key global state variables that describe which portion of a menu definition is currently being processed. The first of these, in_menu, is a simple Boolean variable telling whether or not a menu definition is being processed. in_menu remains FALSE until the first menu clause is encountered; from that point on, in_menu is TRUE between each menu clause and endmenus keyword, FALSE otherwise.
The other critical state variable is in_item. This one is set to TRUE every time the first item clause of a menu is encountered, and reset to FALSE (along with in_menu) each time endmenu is processed.
Both of these state variables are initialized to FALSE near the start of do_menu(), and thereafter their values toggle as necessary under control of the appropriate token-processing functions.
With the keywords structure and state variables all in place, cmenu's main processing loop can be frightfully simple. Indeed, lines 71-81 of Listing 3 (a partial listing of the source file cmenu1.c) make up this entire loop. The code relies, however, on the token scanning function gettok() to parse the next little piece of the input stream into a token value and associated detail values.
If the next token is a string, for example, then gettok() returns the token T_STRING. The actual text of the string is stuffed into a global char array named tparam.
The main loop can prevent the token-processing functions from having to perform a common error-checking test by making sure that, when not currently within a menu (i.e., whenever in_menu is FALSE), the menu keyword is the next token scanned. Whenever any token other than menu is encountered outside of a menu definition, an error is reported (line 75) and processing of the current file terminates.
No other error condition is as universally easy to detect, so any further diagnostics are relegated to specific token-processing functions. Lines 78-80 dispatch control to the appropriate processing function, and check for the possibility of a fatal error before continuing on to the next loop iteration.
Information Economy
Now let's return to the ccmenu.h header file and investigate some new data structures.The CMENU language supports forward references in both menu and item label references, so we need some way of keeping track of which menus and items have been defined so far, which ones have not, and where those references came from so they can be resolved when possible, or diagnosed as unresolved reference errors otherwise.
There is also the matter of the menu and item identifier names. There is no place for those identifiers in the .mnc file format, since by the time the .mnc file is written, each reference to a menu or item has been resolved into an integer index value that allows direct access to the menu or item desired through a simple indexing operation.
So, what's needed is a set of data structures that contain the elementary MENU and ITEM structures as subsets of larger structures. These larger structures add the additional pieces of data necessary to support the compilation process, but still allow the essential MENU and ITEM information to be extracted, in the required elementary format, when the time comes to write an output file.
The typedefs for just such a set of incremental structures can be found in lines 27-37 of Listing 2. The first definition, IINFO, is a structure containing just two elements: a name string, and an INFO structure. The second typedef, MINFO, is a structure containing a name string, a Processed flag to indicate completion of menu processing, a MENU structure describing the properties of the menu, and an array of pointers to the IINFO structures that make up the individual items associated with the menu.
The decision to use an array of pointers to structures in the Items array, but actual instances for the other structure elements (Item and Menu), actually came about as the result of much trial-and-error. The goal was to find an ideal balance for this application between memory-efficiency and coding clarity. In C, unfortunately, those two properties tend to unfold in inversely proportional quantities within any sufficiently complex application. Finding the right balance can be a challenging task.
In order to make efficient use of available memory when the size of an array is not fixed at compile time, we need to use dynamic memory allocation to obtain exactly the needed quantity of memory, and no more, at runtime. When the storage for an object is allocated dynamically, then pointers must be used to access the data — and manipulating pointers to objects is usually more complex than manipulating just the objects themselves.
If more than one level of dynamic arrays are involved, then things get positively twisted. In my first design for cmenu, I attempted to use a data structure that had multiple levels of dynamically-allocated arrays. (Anyone remember the tricky dynamically-allocated arrays from my Mini-Database System series in CUJ last year? And that was only one level!) Needless to say, it was a mess. I learned, however, that it was still possible to squeeze much good use out of CMENU's small-model memory space even without many of the dynamic allocation tricks. Most of the memory goes to hold ITEM information, anyway; why not restrict dynamic allocation to only the memory needed for ITEM structures? The resulting code is much easier to document and understand than my earlier multilayered dynamic scheme.
The MINFO structure applies to a single menu only, so there is an array of MAX_MENUS MINFO structures defined in line 235 as MInfo. The dimension of MAX_MENUS limits the number of structures that may be defined within a single source module; if long menu source files give you memory problems, reducing the value of MAX_MENUS offers quick memory relief (but might make it necessary to split some large .mnu files into smaller pieces).
The final major data structure in the cmenu program is the forward-reference table, fwd_refs, defined in lines 241-245. This table performs the task of tracking forward references to named items in a menu. No such corresponding table is needed to handle forward menu references, however. Here is why: The order of items within a menu is significant; they should appear on the screen in the same order as their specification in the source file. Yet, how is the compiler supposed to behave when a reference is made to an as-yet-undefined item, one that could appear anywhere from the current point in the menu source to the end of the menu? Does the compiler immediately create an item record reserved for the future item, and add it to the array of items? If so, then the physical order of the items gets messed up (this isn't an obvious side-effect; my first stab at this code utilized an IINFO "Processed" flag similar to the MINFO flag of the same name, without taking the aforementioned phenomenon into consideration. Surprise, I couldn't get forward references to work!)
Rather than creating an IINFO structure when a forward reference in encountered, the present scheme simply registers the reference into the fwd_refs table (including the line number of the reference, for diagnostic purposes), and goes on processing more menu items. Whenever a new labeled item definition is encountered, cmenu makes a quick check to see if any references have been made to that item label; if found, the references are resolved by copying the index number of the new item definition into the location whose address was saved in the forward reference table. If any unresolved references remain at the end of the menu definition, the precise line number of the reference can even be supplied in the error diagnostic. The code that handles this is not very complicated, but has proven immensely effective. If I were really smart, I would have written it this way in the first place, but then I'd have missed another opportunity to play with Turbo Debugger!
The remaining definitions in ccmenu.h are for miscellaneous scratch pointers, global variables, and constants. Next time, we'll journey through the rest of cmenu's procedural code.