Volume Number: 14 (1998)
Issue Number: 11
Column Tag: Tools Of The Trade

Getting to Know c-tree Plus

by Andy Dent BSC MACS AACM

FairCom Server - the invisible database engine

Let's say you are such a fan of MacTech Magazine that you can't wait for normal delivery and have it sent Federal Express. You just used a FairCom Server (Federal Express incorporate the FairCom Server into their routing boxes). If you phoned in your order through an Alcatel exchange, you probably dealt with another FairCom Server and if (horrors) you are sitting in front of an Intel-powered computer then right now you are also benefiting from a FairCom Server (used to run Intel's production line). Although the FairCom Server is a staple of many Fortune 500 companies, the non-programming public rarely hears of it (or at least not as much as Oracle, Sybase or even MS Access). From the company's start, nearly 20 years ago, FairCom has gone about their business quietly providing embedded file management tools to C programmers.

In this article I want to introduce you to c-tree Plus, the C language programming tool for working with FairCom Server. I'll talk a little about the strengths and limitations of that tool, so you can decide if it's right for your next project. After that, I want to describe my own experiences in developing a C++ wrapper layer for c-tree Plus called OOFILE and explain how OOFILE can work with c-tree to offer a more complete programming solution.

The Basics of c-tree Plus

When you buy a c-tree Plus developer kit, you receive a cross-platform source code product (Macintosh, Unix, OS/2 and that other operating system). The package allows single and multi-user (file-sharing) deployment - all royalty-free. You also receive a developer license to run the FairCom Server; but if you want to deploy the server (rather than use file-sharing) you need to purchase servers for each site you deploy to. FairCom's servers are reasonably priced by comparison with most and run on a wide range of platforms from DOS (honestly, even DOS) to the most powerful Unix workstations, and of course - the Macintosh. FairCom's web lists more platforms and includes a comment that c-tree Plus runs on over one hundred operating system/hardware combinations.

Models of Data Management

In the last couple of years the range of c-tree Plus deployment models has expanded to include linkable servers for combining your application code with the FairCom Server, multi-threaded variants and the LOCLIB model which allows simultaneous use of servers and local single-user files. The server also now has two Java interfaces, one of which is RMI.

It is unusual for a client-server product to include a shared-file multi-user model. The shared-file mode of deployment is certainly attractive for producing shrink-wrap applications (both because it allows royalty-free distribution and also because it doesn't require your customers to run a server) and you should consider it. However, there are significant trade-offs that you need to be aware of. First, on a security basis, if your files are visible on a file server (to allow sharing) then they are accessible through other means. The recent version 6.8 of c-tree Plus adds encryption - but there is still the danger that someone could access the files using the ODBC driver. However, if you use the server, password protection on the server controls ODBC connections.

There is also the general performance issue of client-server vs. shared file models. The client-server model is more efficient. With complex data manipulation, using shared files generates many network operations. Even index searches still involve several data retrievals depending on the size and depth of the index. Batch functions in c-tree Plus mean operations such as deletion or searching for and retrieving many record pointers are handled by a single server call. A server will also cache records centrally whereas the calls to the library for the shared file must immediately write all data back to the disk, and cannot cache values because of possible changes by other users.

Finally, the single-user and client-server models of operation provide transaction logging and data recovery. With shared files there is no central point controlling access to the data and so transactions are not supported. This makes it possible for a series of operations to be halted partway, causing database inconsistency if not outright corruption.

Understand, these issues are not c-tree specific but a general flaw with shared files, and well-known amongst users of other databases such as Microsoft's Jet Engine (that comes with Access and Visual BASIC). These are issues you'll need to consider when it's time for you to choose which data management model is right for your next project.

The Pleasure of being Well-Connected

FairCom supports the Macintosh True Believer. The Macintosh servers allow you to communicate using both TCP/IP and AppleTalk protocols simultaneously. The same applies to the client libraries, so a Macintosh application could be interacting with both a local server on your AppleTalk network and out onto the Internet to a server running on Unix or Windows NT. Unlike some other servers, an application can open connections to many FairCom servers simultaneously. Each connection has its own security and file contexts.

Other server models support appropriate ranges of communication protocols, such as NetBIOS on Windows networks. One of the most interesting is the shared memory server for Unix. This provides ultra-high speed communications when the only clients are processes running on the same machine as the server.

Which End is Up?

This is a critical question for an Australian writing to a predominantly US audience! More seriously, if you've ever tried to store data in files moved between platforms, you will have run into the problem that Macintosh processors are Big-Endian like SPARC RISC chips whilst the Intel world is Little-Endian. FairCom refer to these as HIGH_LOW and LOW_HIGH formats respectively.

Ignoring this problem is commonly known as playing Cowboys and Endians with your integers and is usually fatal. Some (all?) PowerPC models can have their endian orientation set but in the Macintosh world of course are used in the same orientation as the 68K family.

The c-tree Plus libraries have two ways to solve the endian problem, depending on which model of database you are using. If you're using the FairCom Server, the data is stored in the native format of the server machine. If you're using the single-user or shared-file libraries you must build your libraries with the UNIFRMAT flag which stores data in the Intel format. In either case, the data delivered to your application code matches the platform on which you are running.

Mixing models and platforms has one problem with file compatibility. If a database is used with the FairCom Server on a Mac or SPARC server it will be in the native format, so can't be copied to a PC. A workaround is to use the LOCLIB model to have a PC application copy data from the server and write it out to a single-user local database.

In contrast to server file format issues, using the UNIFRMAT model allows you to copy documents around regardless of platform. This suits the document model of many desktop applications.

Although c-tree Plus is described primarily as a record-oriented engine and indifferent to the contents of your records, to manage endian conversion you need to supply additional information to the database engine. This brings us to the Data Object Definition Array.

Doobie, doobie DODA

There are a number of reasons why you might want to supply a record schema to c-tree Plus, so it knows the fields within your record and not just their total length.

1. As described above, you need the library to know where binary fields such as integers are stored, so it can swap bytes depending on the platform.
2. FairCom offers a character-oriented report-writer product, r-tree, which allows you to specify field names in calculation scripts and design a report by field name
3. The ODBC driver for general access to the database requires a schema. (Sadly, there is only a Windows version of the driver available.)
4. The functions for specifying indexes when creating the database allow you to specify fields using the DODA - a less error-prone method than specifying in terms of record offsets.

The DODA provides a list of field definitions that include the data type: a predefined set of typical integer, string and floating point types. It is saved in a c-tree Resource (not to be confused with the Macintosh variety) and so provides an embedded schema in the data file that can be read by the products mentioned above, or your own code.

What is Fixed and what is Not

Variable length text is a pain in databases. One of the file modes you can choose is to define some or all of your record as being variable length. This saves on storage. You can still have indexes defined on variable length text fields, so if you need to search on such fields but expect their size to vary widely then variable length records is a good way to go. The DODA allows you to define fields with either 2 or 4 byte leading lengths as well as strings with delimiters.

We have not used indexed variable length fields in OOFILE for our local consulting but FairCom's implementation has a good reputation judging by the positive comments on CompuServe.

A little, or a whole lotta Locking

One of the biggest problems with cross-platform database engines is locking. Relational databases typically use page-locking which locks chunks of the file and can inadvertently lock many records which should be available to other users. The record-locking in c-tree Plus avoids this problem, and also provides for read locking which allows many readers of a record, whilst banning any writes to change the record. DOS and Windows don't support read locks natively in the operating system but FairCom have a workaround. Their approach can be used to share a file on an NT server between Mac and Windows users and have mutual locking.

The simplest use of locking in c-tree Plus is to leave locking solely to the library. You can get away with this if write collisions are not expected - automatic locking on the index files guarantees there won't be any corruption just because two people write different records at the same time. More stringent locking is easily enabled with the LockISAM call and you can choose between having locks acquired automatically for each record accessed, or explicitly locking as you go.

Togetherness is not always a wonderful thing

If you programmed with 4th Dimension version 1, dBase or FoxPro, you will be used to a database consisting of multiple files. This is inconvenient for applications, although usually much more efficient. One significant benefit is that using a single file for each database table allows optimal use of fixed-length records. This is one reason why FoxPro and other xBase engines are so fast and why big mainframe databases used to have fixed-length fields in ISAM.

Structuring your database as some or all individual files, or grouping data into superfiles is very simple in c-tree Plus. The default behaviour is a single .dat and .idx physical for each data file. The .idx file will therefore contain as many index trees as there are indexes declared on the c-tree data file. However, you can choose to have some index trees allocated to a different physical index file, if you wanted to separate a particularly dynamic index from the others. A large and active index could even be stored on its own disk, if you wanted to take advantage of disk-level caching in your operating system.

A simple directory-like prefix is used to group multiple files into a superfile. Just prefix the data file name with the superfile name, separated with a | character. For example, if I wanted to open a superfile called 'school.db' which contained 'teachers' and 'students' I would:

1. open the superfile 'school.db'
2. open the data file 'school.db|teachers'
3. open the data file 'school.db|students'

An implication of the simplicity of this scheme is that you can have multiple superfiles open at once, which neatly satisfies the typical desktop application's requirement to open multiple document. Even though the data files may have the same names, the prefixing keeps them unique. In desktop terms, think of using different folders to separate out identically named files.

Just because you create say twenty data files in a superfile, you are not forced to open them every time you use that superfile. The directory idiom extends to just allowing you to access a single data file, regardless of the original number or order creation.

The most significant downside to using superfiles is that they interweave all your data. This means that database rebuilds are complicated, all records are inherently variable length and so some performance advantages are lost. There is also an 18 byte header for each record, which could be significant in very large databases with small records (our largest user stores about 9 million records a month with separate files under Unix - as our ISP it's in my interest to keep them happy).

The flexibility of the c-tree Plus model means however that you can keep temporary files out of the superfile that is your main database. Many is the time I wanted to do that with 4D, cringing at the thought of several hundred thousand temporary records being created and deleted and fragmenting my single database.

Other Goodies

There are many features of c-tree Plus we don't have room to cover in detail. In the spirit of completeness, some of the more powerful are:

• key compression for trailing bytes or leading common strings
• indexing only parts of fields, and easy building of compound keys
• indexes with custom collation (FairCom have a large European user base) or reverse sort order
• mirroring data to another file
• skipping null values in the index
• conditional indexes, with a formula defined to filter membership of the index
• transaction histories, making use of the transaction logfiles for auditing all operations on a record and tracing an item through the files
• a portable threading model that can be used to provide threading across all the environments supported by c-tree Plus.

That completes our brief tour of c-tree, and should give an idea of some of what the FairCom solution provides. Next we'll take a look at OOFILE and see how c-tree and OOFILE can work in concert to offer a unique and powerful solution for database programmers.

It's easy to feel old when you mention ISAM and the twenty-somethings in the audience give you only a blank look. If I say "like dBase" that means more to many people In a world of relational databases the ISAM model is not taught or mentioned much in textbooks any more.

ISAM stands for Indexed Sequential Access Method. There are many products around that incorporate the word ISAM including Infomix's C-ISAM http://www.informix.com/informix/techbriefs/cisam/cisam.htm and there is a formal standard defining ISAM in the Open environment http://www.opengroup.org/prods/dmm4.htm.

At its simplest, ISAM is a model where a relationship is defined between the datafile and keys and the file access library is responsible for maintaining that relationship by updating index values as the record is changed.

In contrast, a simple engine which provides data storage and indexes requires the application programmer to add and delete keys as appropriate. FairCom refer to this as their low--evel model and allow you to interoperate with both ISAM and low-level functions on the same database.

The number of function calls required for low-level indexed file programming is vastly higher than with the ISAM model, with consequential potential for bugs. A subtler point is the benefit of ISAM in a client-server environment, where the key maintenance is being performed by a server process and thus vastly reducing the number of network operations.

Very large databases used to be developed with this model and many of the high performance transaction systems used variants. My oldest copy (3rd. Edition) of C.J. Date's "An Introduction to Database Systems" discusses how the IMS hierarchical database used ISAM variants as a storage model. This ran on IBM's OS/VS mainframe operating system. Later textbooks have dropped discussions of anything other than the relational and object-oriented database models.

OOFILE and c-tree Plus - Developing a Wrapper

The overview of c-tree Plus features will have given you a good idea why I chose it as a strong foundation for further development. Now let's see what went into wrapping it to present a surface much more palatable to database programmers, and how C++ makes this possible.

While some marketers might be tempted to over-describe c-tree Plus as a database, FairCom's technical writers are careful to use the term file manager. The distinction they draw is based on granularity of the data - c-tree Plus lets you deal with data a single file at a time and doesn't provide higher level structuring. That's where OOFILE comes into the picture. OOFILE is a database framework that provides entry level structuring on top of the c-tree Plus files. In formal terms, OOFILE is closer to the object-oriented than the relational database model. The main distinction is that relationships between data tables are defined in OOFILE schema rather than being implied by runtime joins.

Everything I ever hated about...

The OOFILE project started as a result of several issues that converged in 1994:

• ACI had not delivered on the previous year's promise to make 4D object-oriented.
• Friends and I wanted a simple toolkit to develop shrink-wrap applications without massive royalties. The cost of licensing 4D servers was high at the time, and I had a lot of reasons to include Unix as a desired platform.
• A long-standing appreciation for the ease of programming offered by the dBase model, (coupled with an awareness of just how easy it was to cause bugs with side effects and out of sequence commands).
• No cross-platform multi-user C++ database frameworks existed that defined cross-platform as including the Macintosh.
• Very impressive performance from c-tree Plus in an earlier project. We used a IIci AppleShare server and LocalTalk connections to Classics running System 7 in 2Mb of RAM for a classified ads data entry system. Performance such as 1-second lookups was amazing for the hardware.
• I inherited enough money to spend 6 months studying C++ idioms and writing the core engine.
• Several years of database development had shown a need for an engine that would scale to comfortably handle millions of records.
• I was going crazy trying to think in 4D, FoxBase, Object Pascal and C all at the same time and wanted to focus on a single language, covering all platforms, that would be familiar or at least attractive to new graduates hired as junior programmers.

In my more wry moments I've described OOFILE as being primarily driven by my private gripe list about every database tool I've used in the past. There were also lessons well learned. In particular, from the larger 4D systems I developed came the idiom of using set operations heavily to optimize data manipulation.

The OOFILE pastry around the c-tree Plus filling

OOFILE adds many features to the record-oriented model of c-tree Plus, apart from just being a C++ layer around FairCom's libraries. As an access layer, the idea was to provide true field-oriented logic like dBase or 4D. Thanks to C++ operator overloading we were able to accomplish this. The lack of operator overloading in Java means the syntax for field access would have to be a lot more complicated if we port OOFILE to Java.

The most significant features OOFILE adds are:

• relationships with referential integrity, including cascading updates to join fields
• non-indexed searching and sorting, including sorting by multiple fields. Searches and sorts are programmed identically regardless of indexes.
• calculated fields, with user-defined calculation objects of arbitrary complexity
• word and phonetic indexing
• full set operations, for combining sets of records
• Wildcard searches, with * and ? wildcards by default, but user specified characters able to be used (often a convenience if you expect users to type asterisk characters in their data).

Consultant cooks

I have been accused of treating the world, and my clients, as a huge laboratory, and the original design of OOFILE was no exception. I've long held the opinion that user-interface design principles and techniques could be applied to designing programming libraries. Part of this opinion is the idea of safer programming via fewer syntax traps. If I'm programming after 16 hours and even more coffees, I don't want to have to think too much about my database statements.

One of the main parts of a UI design process is consultation, with the aim of getting many different viewpoints. I sought help from the Internet and CompuServe, establishing a mailing list of interested parties. Well before coding began, we argued out OOFILE syntax.

There's a delightful term UI design called The Principle of Least Astonishment. which helps you choose between behaviours inflicted on your user. When in doubt, do whatever is least likely to astonish. I set this as a guideline for the mailing list, so we debated OOFILE commands on the basis of the expectation that people would bring from their past database encounters. Function names were picked for familiarity to the 4D and dBase crowd. If the name or use of a function was interpreted differently by members of the mailing list, we removed or renamed it. It's ironic that this approach led to OOFILE being quite different to the ermerging ODMG standard for object-oriented databases.

Developing a new language via Operator-overloading

One of the most powerful, and often abused, features of C++ is operator overloading. I believe it should only be used to provide similar semantics to existing data types. It has allowed OOFILE to provide the same sort of syntax as in 4GL (4th Generation Languages) programming languages like dBase, 4th Dimension (4D) and many others.

The following example shows simple field access, assuming that there is currently a valid record. This might be the result of a newRecord() call, or possibly a search which has returned a given record.

Accessing Fields in a Database
When copying data into a field, the operator=(const char*) is 
overriden for a character field, so we can use simple assignment:
   Employee.lastName = "Dent";
To retrieve data from a field, the cast operator is overriden, 
such as the operator double.
   double bossSalary = Employee.salary;

Searches in OOFILE work by creating a dbQueryClause object which describes the search, and which a backend can choose to parse however it likes. (A future implementation might even generate an SQL statement based on the query object.)

This was one of the most contentious issues in designing the OOFILE syntax, with wild variations in the proposals for building the queries. The approach shown below has the benefit of being completely type-checked by the compiler. You can't accidentally specify an incorrect compound search and have the program compile.

Searches
In a simple search, we override operator== to create a 
dbQueryClause object:
   Employee.search( Employee.salary == 99000 );

A complex search creates one dbQueryClause by combining two 
others. We are overriding the operator== shown above as well 
as operator> and operator||:
   Employee.search( Employee.salary == 99000 ||
   Employee.hourlyRate > 20);

Generating the schema and the OOFILE storage model

Whether dealing with c-tree Plus or dBase files, you need a way to map C++ data structures to the structure handled by the database. With c-tree Plus, there are also index definitions to provide.

One of the earliest constraints on OOFILE was refusing to write a preprocessor for the database - everything had to be runtime evaluation. The result of a very iterative design was using persistent base classes not just for the record but for the fields within the record. Every field stored in the database is a subclass of dbField.

Having this degree of control, it is relatively trivial for an OOFILE database table to know which fields are within the table - they register themselves with the current table in the dbField constructor. This gives us a dictionary of dbField objects for each table.

Generating the DODA and other c-tree Plus schema structures is then a case of iterating through the dbField dictionary, filling in the field and index definitions that FairCom expect.

The most important thing to know about the OOFILE storage model is that we use fixed-length records for all the main storage, and combine our BLOB fields (including variable-length text) into one separate file. This has several benefits. If using separate files then record iteration is very efficient, and record pointers are guaranteed not to move. By combining our text fields into one file per database, unlike dBase with its many dbt files, we get more efficient space filling from a mixture of fields.

OOF_ctreeBackend::BuildDODA
Excerpts from our schema building, showing how fields are evaluated 
and the special case of BLOB fields handled by storing a record 
pointer and length. Note how we use the OOF_ctreeBackend method
MapFieldTypeToCtreeDODAType() to decide how the field will be stored. 
This implies that a given field subclass doesn't know how it is 
stored - it tells the database what type of content it needs.

      unsigned int numFields = mFields.count();
...
      for (unsigned int i = 0; i < numFields; i++) {
         dbField *fld = mFields[i]; 
         if (FieldHasStorage(fld)) {
            iDODA = mFieldCtreeMap[i].mDODAfieldNo;
            ret[iDODA].fsymb = fld->fieldName();
            ret[iDODA].fadr = 0;  

            if (fld->fieldIsBlob()) { // pair of fields needed
                // record pointer to BLOB as variable-length record 
               ret[iDODA].ftype = CT_INT4; 
               ret[iDODA].flen = 4;
               ret[iDODA-1].ftype = CT_INT4; // length of BLOB
               ret[iDODA-1].flen = 4;
...
            }
            else {
               ret[iDODA].ftype = MapFieldTypeToCtreeDODAType(fld->nativeType());
               ret[iDODA].flen = mFieldBufMap[i].mLength;
               if (fld->storesCalculatedValues())
                  fieldHasStoredCalculator(fld);           } // not a blob
            expectNextFieldAt = mFieldBufMap[i].mOffset + 
                                mFieldBufMap[i].mLength;
            lastDODA = iDODA;
         } 
      } // loop through fields

Set-Oriented Processing

Every 4D programmer worth their salt makes heavy use of sets for intersecting and combining data. Whilst c-tree Plus has some set functions, they are not sufficiently flexible for our purposes, being oriented toward scanning a set of record with a common partial key. I wanted a set model that was a combination of the 4D sets and selections - able to be sorted and let us go directly to records.

Sets of record pointers are still reasonably space efficient (arrays of unsigned longs) and well-supported by c-tree Plus. The DoBatch function allows you to specify a partial key and retrieve just the record numbers without having to load the records. Most importantly, this is a single operation, which cuts down dramatically on network overhead to the server.

If you just need to intersect or check membership in sets of records, there is no need to sort based on the data, so operations on the sets can take place purely in client memory. When it comes to finally displaying records, a sort requires iteration across every record in the set.

One final optimization was designed for the case where we have all records selected, typically consider a GUI browser on a very big selection before the user specifies some subselection. To avoid record iteration, a selection of all records tries to use an index to sort and doesn't load the record pointers. They will only be loaded if there is no suitable index to providing the sorting. This means, with a little careful planning by the database designer, your GUI can browse massive lists without a significant startup delay.

Toward an abstract backend for record-oriented databases

The first release of OOFILE was purely a framework for the database syntax I wanted to use on top of c-tree Plus. However we swiftly encountered the need to store temporary databases in RAM and then to exchange data using the dBase III+ and IV standards. Fortunately, all these applications can be viewed as a similar record-oriented model. Thus, about half the functionality of the existing c-tree Plus backend was moved into a common partially-abstract base class OOF_SimpleRecordBackend. This provides common logic for all the non-indexed operations.

The concrete subclasses provide indexed operations (for c-tree Plus) and the basics of getting data to and from the disk. Simple data storage management includes operations such as stepping through records and returning some kind of record pointer.

A rewrite of this magnitude could have been a nightmare, but OOFILE from the start was designed with an abstract layer hiding the storage metaphor from the dbTable, dbField and dbView classes with which applications interact (thanks to Jim Coplien). A much more complex task would be to write an SQL or ODBC backend, which would probably be a sibling to our SimpleRecordBackend and might have wildly-different ways to retrieve data.

Figure 1. OOFILE main database classes showing abstraction of storage into OOF_simpleRecordBackend class.

c-tree Plus and OOFILE Shows C++ at its Schizophrenic Best

The ideal of C++ was that it would provide a powerful object oriented language but retain backward compatibility with C. We have found over the last few years that this works very well in practice.

In particular, using the principles of abstraction and encapsulation paid off hugely when the simple c-tree Plus wrapper had to be expanded to handle multiple database formats. I cannot emphasize this too highly. Designing in this manner should be as habitual as brushing your teeth or backing up (pick your analogy depending on hygiene or paranoia levels).

A final lesson to take away is just how similar common data models may be underneath. The dBase standard is a great way to interchange data with almost any database product available. The ISAM model offers efficient key management. Both are essentially the same in their model of record-oriented data storage, which maps well to the compile-time structure definition of C++ programs.

Andy Dent lives in Perth, Western Australia with more computers and C++ compilers than anyone else he knows. He develops cross-platform developer tools, puts Windows after Unix on his list of preferred operating systems and enjoys user-interface design, ice-skating, kung fu and poetry as breaks from debugging. More about all of these activities can be found at http://www.highway1.com.au/adsoftware/ and he promises to get a domain name real soon now.