Kenneth Pugh, a principal in Pugh-Killen Associates, teaches C language courses for corporations. He is the author of C Language for Programmers and All On C, and was a member on the ANSI C committee. He also does custom C programming for communications, graphics, image databases, and hypertext. His address is 4201 University Dr., Suite 102, Durham, NC 27707. You may fax questions for Ken to (919) 489-5239. Ken also receives email at kpugh@dukemvs.ac.duke.edu(Internet).
For those on the West Coast, I'll be speaking at C plus C++ in Action September 21-25 at the Santa Clara Marriott. P.J. Plauger will be giving one of the keynote speeches.
Q
I use a linked list to hold a list of selections that the user will choose from. There is a noticeable delay when paging up and down through the list. How can this be improved?
Miles Brenton
New York, NYA
Your speed problem probably has nothing to do with the linked list itself, but with what else you are doing in your program. An example of the speed difference can be seen on Macintoshes. The Mac uses a linked list for strings that are choices in list boxes and for lists of files that are displayed as folders. As a test, make up two folders, one with fifty files of the same type and one with two hundred files of the same type. You can use the Save As command from one of your application programs to do this.
Open up the folders in the Finder. Choose a view that lists the icons by name, such as View by Name. When you scroll up and down a page at a time in each folder on a common processor, such as the MacPlus, you will notice a distinct difference in time in the response. The scroll box in the smaller folder will be able to keep up with your clicks. The scroll box in the larger folder will have some time lag.
Start the application and select Open and then each test folder in turn. When you scroll up and down by a page, you will hardly notice any difference between the two folders.
The list operations in the Finder may be making additional system calls for every file on the list as it pages up and down the list. Or it may simply output every name and let the system do the clipping or names that are outside the list window. Otherwise one would expect that that there would be no time difference between the large and small folder. Perhaps a reader who is a Mac expert might be able to explain what is going on.
When you have these folders open in the Finder, especially the larger one, you may notice the wait cursor (the clock) up for a long time. On my MacPlus, a folder with fifty files takes about a second to display. A folder with one hundred can take up to fifteen seconds. A folder with two hundred can take up to a minute or so. (If you don't notice this time difference, try viewing the the folders with a different option such as By Kind) The discrepancy in times can be attributed to a number of factors.
First, one would expect a linear increase in time, simply due to the number of files. Second, the file information may be more scattered across the disk for large folders. This increase may not necessarily be linear. Third, there appears to be a large sort time that is proportional to the square of the number of files. This third factor brings us a comparison of linked lists versus arrays of pointers for storing and accessing list items.
Let's start with a review of linked lists versus arrays. Linked lists have two advantages over arrays for storing data. First, the size does not have to be fixed in advance. Second, it is easy to insert and delete an item by simply manipulating a couple of pointers.
There is one main disadvantage. It takes time to access a particular element. Listing 1 provides a concrete example. To keep it simple, I used a singly-linked list.
To get to the third node in the list, you need to go around a loop twice and do one assignment and one indirection per loop. If the list were long (say 100 elements) and you needed to get to an element in the middle (say the fiftieth one), you would go around the loop 49 times.
The nodes were declared and initialized in reverse order, since each one needs the address of the next one. The structs were declared as static as older compilers do not support initialization of automatic aggregates (arrays, structs, and unions).
Let's contrast this with the array approach. This version will use an array of pointers.
#include <stdio.h> #define SIZE_STRINGS 4 void main() { static char *strings[SIZE_STRINGS] = { "First", "Second", "Third", "Fourth" }; printf("Third string value is %s", strings [2] ); }Accessing the third string is simply a matter of using a subscript. Regardless of the number of strings, the time to access a particular element is constant.You can easily extend the list or insert a new node into the list. For example:
static struct s_node new_node = { NULL, "Fifth"}; fourth_node.next_node = &new_node;Arrays cannot be extended. Their size is fixed at compile time. However you could use a pointer whose memory is malloc'ed and which would be realloc'ed if extension was necessary. That gets into a couple of matters that would complicate the current comparison.Although it took longer with the linked list to get to the third node, you can delete it quickly. You simply rearrange the pointers:
second_node.next_node = &fourth_node;Now third_node is no longer in the list. To delete an element from the array, you need to move the elements down.
for (counter = 2; counter < SIZE_STRINGS - 1; counter++) {, strings[counter] = strings[counter + 1]; } string[SIZE_STRINGS - 1] = NULL;It will take a little bit of time to do the move. You could decrease the time at the expense of clarity by using the memmove function instead of the loop:
memmove(&strings [counter], &strings [counter + 1], sizeof(char *) * ( (SIZE_STRINGS - 1) - 2) ) );The time difference between the two approaches for accessing a particular value can be significant - a factor of three to ten, depending on the compiler. This difference for accessing the elements may not be noticeable for a fast processor, but for slow processors with long lists, it may be a factor.The preceding is not the only factor in a slow down. With linked lists, you typically allocate the memory for each value on the list, rather than retrieve it from some fixed area in memory. For example, you probably have some statements in your code as:
new = malloc(sizeof(struct s_node); new->string_value = malloc(strlen(string) + 1); strcpy(new_string_value, string_to_be_added_to_list);With arrays, one typically creates a large array for storage of the strings (or allocates an entire block of memory at a time):
static char strings_array[SIZE_STRINGS] [MAX_STRING]; strings[i] = strings_array[i]; strncpy(strings[i], string_to_be_added_to_list, MAX_STRING);The mallocs will take some initialization time for the list, but will not affect the paging up and down time. However, if you are working in a multi-tasking environment, you are probably using handles (pointers to pointers), rather than simple pointers. Each handle should be locked before it is used and unlocked afterwards. The additional system calls required to do this for each element on the list may add considerable time to paging your way through the list. With the array version, you might simply lock the entire block at the beginning of the list selection routine and unlock it at the end.You could speed up the linked list version by allocating a large block of memory once and doing your linked list allocations from it. That way you would only need to lock and unlock a single handle.
The difference in sort times of a linked list versus an array can be a significant factor in initially displaying a list. To sort the array version, you can simply call qsort with the array of pointers. I'm not familar with techniques for sorting a linked list, but no speedy way pops to mind. Perhaps one of our readers might have a fast linked-list sort routine. (KP)
Q
I want to be able to read in arguments from the command line and use them to control my program. How do I do this? Also why is main sometimes declared as returning void and sometimes as returning int? Also, how can I pass values between programs that I call using system?
A
The main function actually receives two arguments, which are not always listed. These two arguments are a count of command-line tokens and an array of pointers to these tokens. When a C program is executed, the first instruction to be executed is not the first line of main. It is the first instruction in a startup routine.
This startup routine, usually written in assembly language, accesses a buffer in which the operating system has copied the command line that you typed to execute the program. It parses the line into tokens that are strings of characters separated by white space (spaces or tabs). The count of tokens and pointers to each null-terminated token are passed to main. The first token is the name by which the program is executed. If that is not available, it is set to "".
By convention, main's parameters are declared as argc and argv. You are at liberty to name them whatever you want, but I have never seen them called anything else. Also, you can interpret the tokens however you like. Operating system convention suggests that you use a hyphen (-) or a forward slash (/) as a prefix to any options other than filenames.
Listing 2 illustrates how this might work. It simply checks for a single option after each dash or slash prefix. Some conventions suggest that multiple single-letter options be permitted after a prefix. Some also differentiate between lower and upper case options.
This program expects one filename plus the following options:
-d or/d turn on debug -t or/t turn on tracing -nX or/nX do something X timesThe second part of your question is an interesting one. main is like every other function. If the execution of the function reaches the closing brace, the function implicitly returns to the calling function with a garbage return value. If you have a return statement with a value after it, it will return with that value. The calling function is the startup function. The value that main returns to it is passed back to the operating system as the condition code (or error level or program-termination code). It is that value that can be tested in a .bat file, shell script, or executable.If you call exit, the value that you pass it is treated as the return value from main. You could specify and code main in a number of ways. If you had a valid return value, you could use:
int main() { ... return 1; }or
int main() { ... exit(1); }Some compilers will complain with warnings that you failed to return a value in a function whose header designates it as returning an int. The ANSI standard states that the prototype for main can be either int main; or int main(int argc, char *argv[]).To avoid the warning, many programmers code main as returning void. This is not ANSI standard, but appears to be commonplace. To eliminate the warning, you might code:
int main() { ... exit(1); return 1; }The return would never be reached. This is inelegant, but the only way I know to avoid the warning and leave main as returning an int.As for the third part of your question, there is an easy way to pass values between programs. Suppose you have a program such as a_prog which outputs values to stdout. You want to use the output in another program. You could redirect the output to a file and then open this file. For example:
FILE *input; system("a_prog > temp_out"); input = fopen ("temp_out", "r");Of course you could reverse the process and send data to a program that processed input from stdin.
FILE *output; output = fopen("temp_in","w); /* Do writes here */ fclose(output); system("b_prog < temp_in");If you were on UNIX, you could use popen, but that is not as portable as this method. You could use the command-line pipe (|) on UNIX and MS-DOS (e.g. a_prog | b_prog) if the design of your programs permitted it. With this pipe example, a_prog is only executed once and its output is available to b_prog. If b_prog needed to execute a_prog several times within itself, then the pipe would not be an alternative.If you only had a few values, then you could place them on the command line (assuming the other program is written to accept them in this manner).
char command_line[100]; int one, two, three; sprintf("c_prog %d %d %d", one, two, three); system (command_line);The c_prog program would need access to those parameters.A third way of passing values is much less portable, but will work if programs are executed in the same address space. You could pass the addresses of variables - in particular of structures. For example, in the calling program, you might have:
struct s_some_structure { /* Lots of members to pass */ }; struct s_some_structure structure_to_pass; char command_line [100] sprintf("d_prog %p",&structure_to_pass); system(command_line);The called program would look something like:
main(int argc, char *argv[]) { struct s_some_structure *pstructure_to_receive; sscanf(argv [1],"%p",&pstructure_to_receive); ... }Okay, it's not pretty, but it is a lot faster than writing to a file. And I repeat — it works only if all programs run in the same address space. One such case is MS-DOS using far pointers operating in real mode in the same DOS session. It does have the one advantage of saving space if you are using large structures. You do not need a copy of the structure data in both environments.If you come across a different environment on which this does not work, you can always write the structure to a binary file in the calling program and read it in the called program. This assumes that both programs are running on the same type of processor or ones which represent numbers and characters in the same manner.
Q
Why does this code set the array properly with one compiler, but not with another? I want to set each element of the array to the value of its subscript.
main() { int array[10]; int i; for (i = 0; i < 10;) { array[i] = i++; } }AThis is due to the old undefined order of evaluation problem plus the post-increment evaluation time. The standard states that for the post-increment and post-decrement operators, the variable will be changed anytime after it is used in the expression and by the time the next sequence point is reached. There is a large list of sequence points, but the most common is the statement terminator.
Either the element reference on the left hand side is evaluated first or the value on the right hand side may be evaluated first. If it is the former, then you will get the value of i into array[i]. If it is the latter and if the increment operation is delayed until the end of the statement, you will get the same result. If it is the latter and the increment operation takes place immediately after the evaluation of i, then you will get the value of i into array[i+1].
The ANSI standard permits the increment to take place anytime from the access time of the variable to the sequence point. This leads to a wide variety of potential orders of operations. For example, the increment could take place after the right-hand side is evaluated and after the value of i is retrieved for the array subscript calculation, but before the assignment operation is completed.
I always recommend using the increment and decrement operators as stand-alone operators. There is little, if any, additional execution time. If you are using it on a register variable and the compiler actually puts it into a register, then there is no extra execution time. The above loop would be written as:
for (i = 0; i < 10;) { array[i] : i; i++; }If you wanted to try to save time, then you might use:
for {i = -1; i++ < 10;) { array[i] = i; }but it would be ugly.Q
Kicking around on USENET is a question on how to handle an array of strings that are needed by the program in many places. The problem was posed starting with:
#define STRING0 "Zero" #define STRING1 "First" #define STRING2 "Second" ... #define STRING100 "One hundredth"What is the best way to handle this situation?A
Using #defines will cause the contents of the string to be repeated at least once in every object file in which it is used. With a single file, the compiler may merge all repetitions of use to a single storage area, but that is not guaranteed. For example, if File One contains
printf(STRING1); printf(STRING1);and File Two contains
printf(STRING1);"First" will be stored in memory at least twice and probably three times in the linked program.An initial way to overcome this is to use a global array of pointers to strings. This is the solution that was proposed on USENET.
char *string[] = {"Zero","First", "Second", ... "One hundredth"};File One
printf(string[1]); printf(string[1]);File Two
printf(string[1]);In order to avoid the problem of having a large global array, and to ease portability problems, one could use a function to access these strings. This would look like
char *get_string(int index) { static char *string[] = {"Zero","First", "Second", ... "One hundredth"}; return string[index]; }File One
printf(get_string(1); printf(get_string(1));File Two
printf(get_string(1));Now all strings that may need to be changed in a program are gathered in one function. To make this even more portable and dynamically changeable, it could be written as shown in Listing 3.This reads in the strings from a file called string.fil. They are new-line terminated strings. You can easily change the value of any of the strings with a text editor without recompiling the program. The strings will sit in memory from the heap, rather than static memory.
You could make up #defines as
#define INITITAL_STRING 1 #define BUTTON_LABEL 2and in your code use
printf(get_string[INITIAL_STRING]); printf(get_string[BUTTON_LABEL]);Each line of the file could contain a label as well as a string value, such as:1 Initial string
2 Button stringThis way it would be possible to reorder the strings in the file in a logical manner. Now the system starts to look a lot like a Windows resource source file.