Channels ▼
RSS

C/C++

C Programming

Source Code Accompanies This Article. Download It Now.


Dec98: C Programming


I'm having a good time with templates. Several months ago, I published the Persistent Template Library (PTL). PTL illustrates how templates support the definition of generic containers by adding persistence to the STL containers. But templates support much more than just a way to build generic container classes. They are also a medium with which you can express higher levels of abstractions. Last month I discussed a templatized undo/ redo class library that you can use in applications that involve interactive user changes to documents or databases. The undo/redo class library is an example of using templates to form abstractions. It abstracts the undo and redo properties and behavior common to many applications by parameterizing the document or database classes and the atomic items that an application can insert, delete, and replace in the document or database. I have successfully used the undo/redo library in three applications with quite different data requirements; I have plans to use it for yet another application, which I will discuss later in this column. (Hint: The application in question is a descendent of something called "D-Flat" and will use something else called "Quincy 99." More about those things later.)

A Container: multikeymap

The new project, which includes an upgrade to an old column project named "Quincy," includes a source-level debugger. The upgrade involves porting a new compiler version, which has changed the way that it embeds debugging information in a compiled executable file. That effort made me take a hard look at the code that extracts and parses debugging information, a process that involves different kinds of containers. The old code used custom containers because STL was not included in VC++ when I first wrote the program. The old code is complex and difficult to maintain. I decided to throw it all away and use STL.

Then I hit a snag. One of my old custom containers emulated files in relational databases in that its objects could be accessed by their primary key and by a secondary key. I used it to store the relationship between memory addresses in the executing program and their associated source code files and line numbers. The debugger needs to find the memory address when given the file and line number to set a breakpoint. It needs to find the file and line number when given the memory address to report a breakpoint to the programmer. To use STL, I would have to build two std::map containers each with the same data but with opposing keys. This redundancy not only represents a potential disintegration of the two maps, which I could debug away, but it also represents a common programming problem and, therefore, an opportunity to build another abstraction. Listing One (located at the end of this column) is multikeymap.h, the implementation of the multikeymap container.

I did not provide all the features of an STL container in this first multikeymap implementation, although it would be possible. For example, I did not bother with const iterators and references. I should add those things and probably will later.

A multikeymap container is similar to std::map except that an instantiation specifies two key data types instead of only one. The first key is the primary. Only one entry in the container is permitted for any primary key value; this behavior is similar to that of std::map. The second key is the secondary. There may be multiple entries in the container for a secondary key value, similar to the behavior of std::multimap. With this model, you can implement multiple container relationships like those in a relational database. I tested the code with VC++ 5.0 and Quincy 99.

Table 1 presents the multikeymap public interface and includes the type declarations and member functions. The multikeymap code that you download includes a small data-entry application that stores employee data with a primary employee number and a secondary employee name. (It lets you hire two guys named J.D. Hildebrandt, for example -- as if you would.)

Quincies 96 and 97

Now we're getting closer to the new project. Let's talk about Quincy first. Quincy 96 is a Windows 95-hosted integrated development environment for C and C++ DOS text-mode programming. I originally developed it as a training tool to run the exercises in the Al Stevens C/C++ Cram Course CD-ROM, which DDJ still sells. Quincy 96 is a front end to the gnu-win32 port of the GNU C/C++ compilers, which are free for the taking and using. The version that I used ports GNU 2.7.2, which lacks many of the newer C++ features. I made many modifications to the header files and libraries to make the compiler seem more compliant with the emerging standard, but many of those changes were hacks, bandaids, and trickery, all contrived so that compliant code would compile and run on a not-so-compliant compiler suite. Quincy 96 is integrated with the interactive multimedia tutorials on the CD-ROM. Quincy 97 is a version that I developed for the companion CD-ROM of the fifth edition of a tutorial C++ book that I wrote titled Teach Yourself C++. Quincy 97 includes an automated list of exercises from the book chapters so readers can load and execute them. Each exercise loads with its watch windows and other options already programmed to facilitate the lesson it teaches. Quincy's development was the subject of several past "C Programming" columns, and its source code is available from the DDJ web site and on the two CD-ROMs. Its usefulness is limited by the fact that it works only with gnu-win32 beta 10, which is no longer available for download, and it needs the modifications that I made to that particular compiler suite. Everything is included on the CD-ROMs, however.

But there are other ways. The next few paragraphs briefly discuss various other options for compiling C++ programs on a PC under Windows 95/98/NT. A list of URLs at the end of this column tells where you can learn more about the compilers and download them to use on your machine. I will not compare or benchmark these compilers. They are all ports of the same GNU compilers, and they are all free. Most of this information comes from the Internet. If I get some of the implied chronology wrong, I apologize in advance. Visit the web sites to learn more.

Gnu-win32

Gnu-win32 from Cygnus is designed to support compiling and executing GNU development tools on a Win32 platform. It retains the UNIX flavor of things often at the expense of MS-DOS and Win32 platform characteristics. That is not a bad thing; that is what Cygnus intended to do. Compiling programs with gnu-win32 and executing those programs requires that a DLL named cygwin.dll be installed to support the port's POSIX emulation layer. Executables are often incompatible with different releases of the DLL. That, too, is not a bad thing. The product is still in beta (Version 19 at last look), and you can expect those kinds of changes. I froze my Quincy 96 and 97 implementations at gnu-win32 beta 10 because they kept changing things that affected my port, and, since the compiler version remained essentially the same through the betas, I saw no reason to expend the effort to try to keep up.

Egcs

Egcs is a project that releases frequent experimental versions of the GNU compiler with newer language features installed. Egcs is close to being an ANSI/ISO conforming compiler, as close to the standard language as any commercial compiler available on the PC. The library is not as current, but the compiler is capable (or close to capable) of compiling a standard C++ library whenever they get one ready. Egcs is being built on several platforms including DOS, Irix, AIX, Win32, Linux, Solaris, and PowerPC.

DJGPP

DJGPP is a port of the GNU C/C++ compilers to the MS-DOS platform. I included an earlier version of this compiler on the companion diskette with the fourth edition of my tutorial C++ book. Since MS-DOS has that infamous 1-MB addressing limit (remember real mode?), DJGPP uses a DOS extender program for the compilers and the executables that they compile. DJGPP is the handiwork of D.J. DeLorie, and is a respected and mature implementation. A text-mode IDE named RHIDE works as a front end to the DJGPP compiler.

Mingw32

Somewhere along the way, a programmer named Jan-Jaap VanderHeijden configured the gnu-win32 compiler to compile programs by including header files specifically meant to link programs with the Win32 run-time DLLs instead of through the cygwin.dll POSIX emulation layer. That project was called Mingw32, an abbreviation for "Minimalist Gnu-Win32." Later, Jan-Jaap compiled and linked the compiler and its tools themselves by using the Mingw32 headers, and all dependency on cygwin.dll went away. Coincident with this (from the perspective of its relevance to my needs, soon to be revealed) was the release of newer versions of the GNU compiler, which support more of Standard C++. Also coincident (from the same perspective) was the release of libraries and header files that support Windows 95/98 GUI application development.

Egcs-Mingw32

A programmer named Mumit Khan combined Mingw32 with Egcs, and the result is a leading edge C++ compiler that runs under Win32 and supports the Windows API. This compiler suite consists of libraries and header files from several sources, each of which has its own licensing policies, but all of which are free for your use. The same could be true of the other GNU-based compiler suites as well. This, however, is the one that I plan to use, so my research stopped here.

Quincy 99

The combination of a near-standard C++ compiler that runs in a Win32 DOS box, is independent of proprietary DLLs, and supports Windows 95/98 program development was too much for me to ignore -- for three reasons.

First, it's almost time for a new edition of my book, which I did not want to undertake until I could provide working exercises and a compiler that supports more of standard C++ than earlier books, Quincies, and GNUs did.

Second, I would like to include some simple GUI applications as exercises in the book. (There is no better way to explain class hierarchy than with a graphics class library.) Consequently, I am now working on Quincy 99, a version that integrates the latest Egcs-Mingw32 compiler and allows the development of Windows 95/98 GUI applications. I've already used Quincy 99 to compile and run Petzold's hellowin.c program from the classic Programming Windows 95 book (Microsoft Press, 1996). By the time you read this column, the first release of Quincy 99 should be available on my web site and DDJ's.

Third, I have a new project in mind...

D-Flat 2000

Those of you who have stayed with me over the years will surely recall D-Flat, a DOS text-mode application framework function library with application windows, pop-down menus, controls, dialog buttons, and so on. The D-Flat project lasted a couple of years during the late 1980s and early 1990s, and ran out of steam when GUIs and Windows in particular finally achieved dominance as the user-interface paradigm of choice. I described D-Flat in a series of columns, with each column adding a feature to the framework. It grew bigger than I originally planned mostly because reader interest in the project kept it going.

Lately, I've been itching to develop a GUI application framework that wraps around the Windows (and perhaps other) GUI APIs and uses the C++ template idiom as the abstraction mechanism with which programmers express the association between an application and the operating environment.

Enter D-Flat 2000, an as-yet vaporware GUI application framework class library that compiles under Quincy 99. An ambitious undertaking to say the least. I announced these intentions during a live audio interview on DDJ's TechnetCast "radio" show (http://www.technetcast.com/). You can log on and listen to the interview with your RealAudio player.

I do not want to use a commercial development environment for this new project. Any programmer with a PC that runs Windows 95 should be able to freely get and experiment with this software without having to buy anything. Consequently, Quincy 99 is essential to this project.

I should emphasize that the purpose of D-Flat 2000 is not to overthrow or replace MFC, OWL, or anyone else's favorite application framework. I use MFC for Windows programming and usually suggest that others do the same. Quincies 96, 97, and 99 are all MFC projects (although my plans include porting Quincy 2000 someday to D-Flat 2000). MFC, however, is an evolved framework, originally developed in the dark ages of C++ language evolution and understanding. MFC has quirks and baggage carried over from its earlier implementations. It widely pollutes the global namespace. It employs proprietary container classes and data types that should be replaced by standard C++ features. They can't improve MFC a lot because many improvements would involve throwing out a lot of junk, which would break a lot of legacy code.

D-Flat 2000 will instead be an experiment in abstraction and the application of leading-edge standard C++ features to implement a framework. This concept is an important element of the argument for the project's existence. Recent forays into templates have convinced me that, for programs that do not exchange objects across networks or with other programs, that do not need an independent binary architecture, and that do not exist in the realm of source code platform independence, templates are an ideal medium with which to express abstractions. Ideal -- but not perfect. There are some performance issues to deal with when you build with templates, particularly in the areas of code size, but this project involves research into the expression of complex abstractions. If the results are compelling enough, we might build better development tools to fit the paradigm. Without this goal, however, there would be no justification for yet another Windows framework.

Do I expect to effect significant change in the way most programmers write GUI applications? No, I do not. My objectives are to build better tools for my own use, expose those tools to scrutiny by publishing them, improve them based on the reactions of others, and experiment with different programming idioms for data and algorithmic abstractions. And to have some fun doing it.

I'm not going to get into Microsoft-specific platforms such as DDE, ActiveX, and DCOM. At least I don't plan to. If you need that stuff, use the tools from the big guys. My goal is to develop a small framework that supports the most common GUI operations, a framework that might be ported to other platforms just as some readers ported the original D-Flat to Windows NT, OS/2, DOS extended platforms, and UNIX. As it happens, I work with a Win32 computer and there is now a Win32 compiler that supports my needs, so Win32 is the first platform that I will target. After that, who knows?

As I said in the TechnetCast interview, these are plans, but they are not an ironclad promise. I don't have the first line of D-Flat 2000 code written yet, but many notes are strewn around the office and scrawled on the whiteboard. The first job is to get Quincy 99 working. After that, I might get well into the D-Flat 2000 project and decide that it is a bad idea. That's one of the advantages of being in the business of writing code so that I can write about code -- there are no beancounters beating me over the head and applying pressure because they've already announced the product and borrowed money against vaporware receivables. Beancounters don't understand the "R" in "R&D." The project's future notwithstanding, it will produce some useful fallouts. I have begun the project by porting the Egcs-Mingw32 compiler to Quincy 99, and that effort, still underway, has already delivered some new template abstractions and polished some others, among them the undo/redo library from last month, the multikeymap container that I described earlier in this column, and a data block marking algorithm that I will describe in a future column. So, even if the D-Flat 2000 research reveals that the idea is ill-conceived, some useful byproducts will fall from it.

As Swaine Might Put it...

A prize of little or no value awaits the first reader who sends me an e-mail message explaining the origins of the name D-Flat for the original project. The prize? Prominent mention in this column as the winner. Its value? You can show it to your boss and claim to be on first name terms with an internationally known trade press media notable luminary. Whatever that's worth.

DDJ

Listing One

// ----- multikeymap.h

</p>
#ifndef MULTIKEY_MAP_H
#define MULTIKEY_MAP_H


</p>
#include <map>
#include <vector>


</p>
namespace DDJCProgrammingColumnMultikeymap  {
// P = primary key
// S = secondary key
// T = data record being contained and indexed
template<class P, class S, class T>
class multikeymap   {
    typedef std::map<P, T>                          datastore;
    typedef std::pair<P,T>                          pridata;
    typedef std::pair<S, P>                         secdata;
    typedef std::multimap<S, P>                     keystore;
    typedef typename keystore::iterator             keyiter;
public:
    typedef typename datastore::iterator            iterator;
    typedef typename datastore::reverse_iterator    reverse_iterator;
    typedef typename datastore::reference           reference;
    typedef typename datastore::size_type           size_type;
private:
    datastore items;
    keystore secondarymap;
    keyiter searcher;
public:
    size_type size() const
        { return items.size(); }
    iterator begin()
        { return items.begin(); }
    iterator end()
        { return items.end(); }
    reverse_iterator rbegin()
        { return items.rbegin(); }
    reverse_iterator rend()
        { return items.rend(); }
    bool empty() const
        { return items.empty(); }
    void clear()
    {
        items.clear();
        secondarymap.clear();
    }
    bool insert(const P& p, const S& s, const T& t)
    {
        std::pair<iterator, bool> rtn = items.insert(pridata(p,t));
        if (rtn.second == true)
            secondarymap.insert(secdata(s, p));
        return rtn.second;
    }
    iterator find(const P& p)
    {
        return items.find(p);
    }
    iterator find_first(const S& s)
    {
        keyiter iter = secondarymap.lower_bound(s);
        if (iter != secondarymap.end() && (*iter).first == s)   {
           searcher = iter;
            return items.find((*iter).second);
        }
        return items.end();
    }
    iterator find_next()
    {
        S s = (*searcher).first;
        if (++searcher != secondarymap.end())
            if ((*searcher).first == s)
                return items.find((*searcher).second);
        return items.end();
    }
    bool erase(const P& p)
    {
        if (items.erase(p)) {
            // --- build a list of secondary keys to erase
            std::vector<S> keys;
            for (keyiter siter = secondarymap.begin(); 
                        siter != secondarymap.end(); siter++)
                if ((*siter).second == p)
                    keys.push_back((*siter).first);
            // --- delete secondary key indexes that point to primary
            typename std::vector<S>::iterator kiter;
            for (kiter = keys.begin(); kiter != keys.end(); kiter++)
                secondarymap.erase(*kiter);
            return true;
        }
        return false;
    }
};
} //  namespace CProgrammingColumnMultikeymap
#endif

Back to Article

DDJ


Copyright © 1998, Dr. Dobb's Journal

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video