So far the last few articles of this series have talked about sorting a lookup table at run time to enable the use of a binary search to speed up string lookups. Sorting the constant list at run time is a bit inefficient and sorting the list at compile time would eliminate the sorting setup time as well as any additional memory. It is actually fairly simple to do if using a make based project build. In this article we will examine the details of using a Makefile to build the lookup table as part of the build process.
There are a number of ways this can be done the method explored here is to have the lookup table declared as a string table. The file in which it is declared compiles in one of two ways. When a compiler define is set the file is designed to run on the build machine. It will sort the lookup table and print the results. When run without the define it will include a file that is the output of the previous system and use that lookup table.
Here we see an example of a lookup table. It starts by including all of the files that declare the various command handlers. Note how these are wrapped in a #if section. When building the lookup table these files are not needed—only when actually declaring the lookup table.
The next section is the lookup table itself. Note that although the lookup table is actually a string and a function, the deceleration is done with two strings. The sort program needs strings, but will output the command handler without quotes in the built output.
Following the lookup table is the program that can sort the list just above it. This program uses the standard library’s build-in qsort function for doing the sorting. The sorted output is printed to standard out and formatted to be the body of an array of command handlers. That is the end of all the code that runs at compile time.
The last section starts with declaring the actual lookup table used by the program. It includes a file in the middle of the HANDLERS table. This works because in C, a #include is like any other pre-processor macro. All it does is substitute the contents of the specified file at that location. In this case it is simply importing all the values of the lookup table from what is presumably the output of the previous section of the file.
Lastly is a function to actually use the lookup table. It is a binary search of the sorted array to find and return the handler for the given command just like we’ve outlines in previous articles. That’s it for the lookup table itself.
The other part of the setup is the Makefile.
Here I am using a universal Makefile. It will simply build every C file in the directory tree. Where it departs for a typical universal Makefile is an additional dependency. There is a rule to make a file called sortedTable.inc. To do this, it runs the local compiler to build lookupTable.c with the define LOOKUP_LIST declared. This will compile a program that will print out the sorted command handler list. After building this program is run and the output redirected to sortedTable.inc thus creating the sorted lookup.
The only other step is to apply this dependency to all the C object files. Without this the build process is setup to first create all the object directories, compile all C files to objects, and then link all objects. The new process now creates all object directories, creates the sorted lookup table, compiles and links. Dependencies still work. A change made to the lookup table will result in a new sorted lookup table list and recompile of lookupTable.c. A change to one of the function handler C files will only recompile that handler. A change to a handler header file will cause lookupTable.c to recompile but not regenerate the lookup table.
This concept can be used for non-make based projects as well. Any compile system with a pre-build command can be used to build the sorted lookup table. Rather than compile and running a local program the Makefile could use a scripting language like Python or even shell utilities to build the sorted list. This would likely require some restructuring of how the initial lookup table is initially declared but is otherwise follows the same setup.
For very small micro processors this method might be the best. There is no sorting overhead on the target processor at all and the binary search adds a negligible amount of code to the lookup process while giving it a lookup speed increase that improves the larger the lookup table.