26.6 Real-World Design Techniques

I l @ ve RuBoard

Over the years , people have developed a number of clever design techniques to help organize their programs. This section will discuss some of the more useful ones.

26.6.1 The Linked List Problem

The linked list problem is actually a C problem, but the various solutions and its ultimate solution in C++ provide a good understanding of the various techniques that can be used to solve a problem.

The code I'm working on now has several linked lists:

• Pending message list

• Running process list

• Keyboard event list

• Idle process list

• Registered connection list

• ... and so on.

There is an insert and delete function for each type of list:

 insert_msg / remove_msg insert_run  / remove_run insert_kbd / remove_kbd insert_idle / remove_idle insert_connect / remove_connect  ... and so on  

This is a needless duplication of code. There has to be a better way. In C, one solution is to play games with the data. The trick is to define a common linked-list structure:

 /* C Code */ struct list_head {     struct list_head *next, *prev; }; 

This structure is put at the start of each data structure that may be used in a linked list:

 /* C Code */ struct pending_message_node {      struct list_head list;     /* List info.  Must be first */      struct message the_message;/* The stored message */ }; 

Now we can take advantage of the fact that each mode in our pending message list begins with a list_head , use casting to turn our pending_message_node into a generic node, and use the generic linked list procedures on it:

 /* C "solution" to a difficult code resue problem */ struct pending_message_node *pending_messages = NULL; struct pending_message_node *a_new_message; /* Fill in node */ add_node_to_list(     (struct list_head *)pending_messages,     (struct list_head *)a_new_message); /* Note the C style casts.  This is C code */ 

This technique depends on the fact that the compiler lays out the memory for a structure with the first field (in this case list ) first. This sort of layout is not required by the standard, but almost all compilers do it. (And those that don't cause people who depend on this feature a lot of headaches . They'll be forced to rewrite their code so it doesn't depend on compiler-dependent features.)

The C solution to this problem is pretty good given the limitation of the C language. But the C++ language gives us many more techniques for solving this problem.

The use of C casts is just the poor man's way of doing base and derived classes. The C++ equivalent is:

 /* Not a good solution.  See below */ class list {     private:         list *next;         list *prev;     public:         // Rest of the stuff }; class pending_message_node: public list {     // .... message data }; 

But there is a problem with this organization. The list and the message have nothing in common. A list is not a refinement of a message, and a message is not a refinement of a list.

Code that wants to process a message and doesn't want to deal with a list item can't deal with a pending_message_node . We could write it as:

 /* Not a good solution still */ class list {     // ... }; class pending_message {     // ... } class pending_message_node: public list, public pending_message {    // Nothing needed here }; 

This "structure" merely rearranges a badly designed data structure into one that's even more silly.

Ideally we want to organize our information like this:

 class pending_message {     // ... }; class pending_message_list {     // List stuff     public:         class pending_message message; }; 

But now we're back to the problem that started this discussion. We're going to have to create a list for every type of object:

 class msg_list .... class keypress_list ... class event_list ... class free_block_list ... 

This means that to properly design our data, we're going to have a lot of almost identical classes. This would be a lot of duplication of effort, except for one thing: templates. The result is that we can write all these classes using one template:

 template class list<typename data> {     // List stuff     public:         data node; }; 

One last note: it's a little easier that this. We don't have to write the list class ourselves . It's already part of the Standard Template Library (STL):

 #include <list> class msg { /* .... */ }; std::list<msg> message_list; class keypress { /* ..... */}; std::list<keypress> keypress_list; 

Thus we've taken the long way round to discover that all you need to solve the "list problem" is to use the STL. But it's interesting how the problem can be solved using a language with limited features (C), as well as seeing a number of designs to avoid.

26.6.2 Callbacks

Let's suppose you are writing a text editor. There are three main modules to this program:

• A keyboard module that reads and decodes input

• A buffer/file module that keeps track of the text being edited

• A set of command modules that provide commands that change the text

One of the keyboard module's jobs is to read the keyboard input and call the appropriate command function. The mapping of keys to commands is accomplished through the use of a configuration file (also under control of the keyboard module).

So to do its job, the keyboard module needs to know the names of all the commands and what function to call to execute them.

One way to organize this information is to create a table containing this information and give it to the keyboard processor:

 struct cmd_info {      const char *command;      void (*function)(  ); }[] cmd_table = {      {"delete", do_delete},      {"search", do_search},      {"exit",   do_exit},     .... 

But this means that the module containing the table must know every command in the system. This way of doing things causes two major problems. First, we have discarded our module hierarchy and invalidated some of the information hiding we have so carefully built up. Now, one module, the command table module, needs to know everything. Second, we have to maintain the thing. Any time any one of the command modules changes, the file containing the command table must change as well.

Figure 26-5 shows our module layout.

Figure 26-5. Editor module design

A better solution is to build this table at run time. During initialization time, the top command module is told to register all the user -level commands. For example, it may register the "exit" command:

 keyboard_module::register_command("exit", &do_exit); 

The top-level command module knows about its submodules and tells them to register their commands. They in turn call the subsubmodules, and so on.

The result is that the command table is built up at run time. Thus, we let the computer keep track of all the commands instead of doing it manually. This is more reliable and easier to do.

Figure 26-6 shows these module interactions.

Figure 26-6. New Editor module design

Thus callbacks let us organize things so that the program configures itself automatically.

26.6.3 Decoupling the Interface and Implementation

Let's suppose we wish to create a simple database. In it we will store a person's name and phone number. A class to handle this might look like the following:

 class phone_book {     public:          void store(const std::string& name, const std::string& number);          std::string& lookup(const std::string& name);          void remove(const std::string& name);          // .. additional member functions     private:          // Implementation dependent stuff  }; 

This class definition is then stuck in a header file for all to use.

The problem is that we are forced by C++ to put implementation-dependent stuff in the header file. This means that the user knows implementation details that are none of her business. It also means that we cannot provide more than one implementation of our phone book class. (We could play some games with derived classes, but that just moves the problem down a level to the derived class.)

Let's change our definition slightly and write our class as follows :

 class phone_book_implementation; class phone_book {     public:          void store(const std::string& name, const std::string& number);          std::string& lookup(const std::string& name);          void remove(const std::string& name);          // .. additional member functions     private:          phone_book_implementation *the_implementation;  }; 

Note that we did not define what the phone_book_implementation actually is. C++ is perfectly happy to create a pointer to it without knowing anything about it (other than that it is a class of some sort).

It is the job of the phone_book constructor to connect the implementation with the interface. In this example, we use a array-based phone book implementation:

 phone_book::phone_book(  ) {     the_implementation = new phone_book_array_implementatation; } 

But there is nothing to prevent us from using a hash-based implementation:

 phone_book::phone_book(  ) {     the_implementation = new phone_book_hash_implementatation; } 

Using this system, we've decoupled the implementation from the interface. This is a good thing (mostly). In this case the caller does not know which implementation was selected.

For example, we could use array-based implementations if we have, say, 1-100 names, a hash for 100-10,000, a small database such as MySQL for 10,000 to 10,000,000, and a commercial database for more than 10,000,000.

What's more, it is possible to switch implementations at run time. For example:

 phone_book::store(const std::string& name, const std::string& number) {     number_of_entries++;     if (need_to_switch_from_hash_to_mysql_database(  )) {         phone_book_implementation *new_implementation =             new phone_book_msql_impelemntation;         copy_database(new_implementation, the_implementation);         delete(the_implementation);         the_impelementation = new_implementation;     }     // .. rest of the function }; 

As you can see, this design has certain advantages. By decoupling the implementation from the interface, we've gained tremendous flexibility in choosing an implementation.

The design also has some drawbacks, the biggest of which is that it adds an extra layer between the phone_book user and the implementation. In most simple programs, this layer is not needed. Also, the use of derived classes in such a situation is no longer a simple matter of C++; instead, it requires some tricky coding. But this does serve to show what you can do with C++ to solve problems creatively.

I l @ ve RuBoard