FKEY Programming Tools

By Mark A. Gruenberg, Miami, FL

Programming Tools: What are they?

[Mark A. Gruenberg is currently working on his Master's degree and intends to continue working until he gets his Ph.D. in Electrical Computer Engineering.-ed]

Programming tools aid developers in the development and maintenance of software. There are many examples of programming tools available for the Macintosh such as: TMON, a debugger; ResEdit, a resource builder; Prototyper, user interface builder; MACYACC, a language builder.

THINK C Integrated Environment

Accessing programming tools in THINK C’s integrated development environment is very clumbersome. Unlike Apple’s MPW environment, THINK doesn’t provide developers with facilities to readily develop and access custom programming tools.

FKEYs as Tools in LS Environment

An alternative for implementing programming tools in the THINK C environment is an FKEY resource. An FKEY or function key is a self contained code resource. No parameters are passed to an FKEY from the stack. It operates totally independent from the application which it was called from.

An FKEY is activated from the key board by typing command-shift-# (any number 0-9) keys all at the same time. Since no parameters are passed to the FKEY, a method of communication between the FKEY and the calling program must be devised. One method is, parameters can be passed to an FKEY by storing them in a memory location known by both the calling program and the FKEY. This brings to mind the low memory globals, specifically the Scrap Handle.

In the THINK C environment, the programmer can cut a section of data from a source code listing and pass it to the FKEY via the Scrap Handle for further processing. The FKEY then stores the new processed data back into the Scrap. Back in the THINK C environment the processed data can be accessed by pasting it into the source code. This is the method I will use to communicate between the FKEY and the THINK C environment.

Tools: Automating C Programming Guidelines

The process of writing source code in accordance with acceptable source code guidelines can be vary mechanical and time consuming. This is an excellent candidate for automation. For an excellent book on C Programming Guidelines see a book by the same title written by Thomas Plum.

The Guidelines

The guideline called Lexical Rules for Variables, taken from Plum’s book (See the book titled, “C Programming Guidelines,” pg. 2, by Thomas Plum.) is an excellent candidate for automation. The following is a description of the parts of the guideline which can easily be automated.

STANDARD 1.1exdata

All variable names, external and other names, be alphabetized by name within type.

JUSTIFICATION

This guideline improves the readability of the source code, thus lowering maintenance cost (the cost of maintaining and updating software).

Scrap and FKEYs

The scrap is used in Macintosh’s Operating System to store data that is cut and pasted within or between applications. There are two types of scrap, desk scrap and private scrap. Desk scrap can be used to transfer data between two applications, between an application and a desk accessory, or between two desk accessories. In other words, the desk scrap is available globally in the Macintosh’s operating system. Private scrap is used to store data which is cut and pasted within an application. Private scrap is only accessible within the application that created it. TextEdit scrap is an example of a private scrap used by the TextEdit manager.

The THINK C editor uses TextEdit to manage text formatting and editing. Because of this, the scrap we are interested in is a private scrap, the TEScrap. The FKEY can access the calling program’s private scrap (the TEScrap) using the TextEdit manager functions TEScrapHandle and TEGetScrapLength (For more information on TextEdit scrap see, “Inside Macintosh,” pg. I-373, 378). These functions return data stored in the low memory globals. Because an FKEY is called from GetNextEvent trap, the system is in a stable state. No context switching has taken place and the applications low memory globals are still intact. Thus, the FKEY is able to access the calling applications TEScrap.

Limitations of FKEYs

An FKEY can not use global variables including the QuickDraw globals. Upon entry into the FKEY, register A5 is set up to address the globals of the calling program. If we inadvertently defined and used a global variable named, glob_long= 5L; the long word value 5 would be placed at location -4(A5). This would destroy the data at this location, which most likely would be the calling application’s global variables.

An FKEY can not be segmented and must be less then 32K. The 32K size includes the size of the code and data for the FKEY.

The resource manager is not configured to allow FKEYs can own their own resources. Therefore, resource copying programs and installer programs will not know about the FKEYs associated resources.

Caveats

We can reference QuickDraw globals by using the low-memory global variable, CurrentA5. CurrentA5 points to the QuickDraw variable thePort, the rest of the QuickDraw globals can be addressed as negative offsets from CurrentA5.

THINK C’s assembler allows for the use of program global variables in code resources. To accomplish this you must assemble your project as a code resource, and call the following two functions immediately after main(): RememberA0() and SetUpA4(). These two functions set A4 to point to the beginning of the code resource, where the code resource expects to find the globals. The globals are then addressed off register A4. When exiting a code resource, the values of registers must be returned to their original state. The function RestoreA4(), does this and must be called before the code resource exits.

Resources can be used with an FKEY but it is the responsibility of the user to load the FKEY’s associated resources into the target destination. Therefore, the programmer should take steps to verify that the FKEY’s resources are available before allowing the FKEY to execute and crash.

Figure 1. compares the rate of growth of standard functions.

Sorting

I wanted to use an uncommon sorting algorithm. The algorithm I came up with is called the shell sort after its inventor Donald L. Shell. This algorithm is the fastest of the simple sorting algorithms. The only algorithm faster than the shell sort is the quick sort. The shell sort has a complexity of n1.2, the quick sort is nlogn (see figure 1). Do to the overhead involved in the shell sort it proved to be very inefficient for small number of elements. Since the sorting tool will generally be used to sort small lists the bubble sort proved to be more efficient.

I have included an implementation of the shell sort in the source code listing. Below is an explanation of how the shell sort works. I think you will find the shell sort very interesting and worth your time.

Figure 2. illustrates the shell sort sorting process.

The shell sort is an adaptation of the insertion sort, and is based on diminishing increments. It works by dividing the records to be sorted, r, into groups. The groups are determined by an internal sequence, h, which controls the distance between the records to be compared. Each of the records, r, and r[hs] are compared and swapped, if r > r[hs]. This process is repeated until all the sequences in h have been used. The sorting tends to converge quickly because the records are well ordered. The sorting process has been diagramed in figure 2 for the sequence, h={1,2,3,5,9} and the records r={6,4,1,3,2,5}.

The proper choice of the sequence, h, can significantly reduce the sorting time. Choosing this sequence has been a challenged for computer scientists and to this day we only have empirical data to base a choice of h on. This empirical data shows that it is reasonable to chose h in the following way:

h[1]=1, h[s+1]=3h[s]+1, and stop when h[t+2]   N

Where t, is the current value of the sequence counter, and N, is the number of records to be sorted.

Using the FKEY

Copy the lines of text you wish to be sorted. Then execute the FKEY by typing command-shift-# (FKEY number). If no error occurs, then the sorted lines of text can be pasted back into the selection.

If an error did occur and the FKEY’s resource file is available, an alert will be displayed describing the type of error. If the resource file is not available or there is not enough memory for the alert then a beep will be used to indicate an error.

Installing the FKEY

The FKEY can be installed using ResEdit. You must also remember to install the FKEY’s resources (‘ALERT’ and ‘DILT’). The FKEY can be installed into the system file or an application file. If the FKEY is installed into the system file, it will be available to be used system wide. If it is installed into an application it can only be accessed from the application it was installed into. The later method of installation is probably the most desirable.

Listing:  ToolSort.h

#ifndef _ToolSort_
#define _ToolSort_

#include <stdio.h>

#define NIL 0L

#define No_Error 0
#define End_Error1 /* Selection must end with a carriage return. */
#define Type_Error 2 /* No selection of type ‘TEXT’ in scarp. */
#define Memory_Error 4  /* Not enough memory. */
#define Nil_Hand_Error  8 /* Nil Handle Error. */
#define Empty_Error  16 /* No selection, scrap empty. */
#define Sys_Error32/* A system error, probably relating to the filing 
system. */
#define Scrap_Error64/* Error writing desk scrap. */
#define TEScrap_Error128 /* Error writing writing TEScrap. */

#define DESK_SCRAP 0 /* To get input from the desk scrap set  DESK_SCRAP 
to 1.  If input is from 
 TEScrap set DESK_SCRAP to 0.       */
#define alertID  2

typedef struct SelLineRec
 {
 int    noLines;
 Handle *lines;  /* array of Handles of lines of text */
 } SelLine;

typedef struct SelRec
 {
 long length;    /* length of selection */
 Handle sel;/* handle to selection */
 } SelRec;

typedef Handle Text;

/******* Function Prototypes ****************/

int Bubble(void *elem, int big, int num, int (*comp)(), int (*set)() 
); 
int BuildLines( SelRec validSel, SelLine * selLine );
int Comp( Handle *e1, Handle* e2 );
int DisplayError(unsigned int err);
int GetValidSel(SelRec *validSel);
int SelToText( SelLine sortSel, Text *txt );
int Set( Handle *e1, Handle* e2 );
int ShellSort(void *elem, int big, int num, int (*comp)(), int (*set)() 
); 
int Swap( Handle *e1, Handle* e2 );
int UpdateSel( Handle txt );
long GetSel( Handle *sel );
void main(void);

#endif

Listing:  SortSelection.c

/*======================================================
Module: SortSelection

Purpose:Get a selection and sort it.  Then update the selection with 
the sorted selection.
 
returns:UpdateSel to the scrap.    

Functional Details:

 Get a valid selection
 if error
 exit
 Build the selection into lines of text
 if error
 exit
 Sort the selection lines
 Update the selection with the sorted lines
 if error
 exit
 Dispose all allocated storage
=========================================*/
#include “ToolSort.h”
#include <SetUpA4.h>

void
main()
 {
 SelLineselLine; /* Array of handles to selection lines */
 SelRec validSel;
 /* Handle to selection & selection length */
 Text txt;/* Handle to selection in text format */
 long   err;
 long size;
 int    i;

 RememberA0();   /* Access globals in code resource */
 SetUpA4(); /* Globals accessed off of A4 */
 
 err = GetValidSel( &validSel);
 if ( err != No_Error )
 DisplayError( err );
 
 if ( validSel.sel != NIL )
 {
 size = CompactMem((Size) (2*validSel.length) +1024);
 if ( size < 2*validSel.length+1024 )
 { /* Error not enough memory */
 err = Memory_Error;
 DisposHandle( validSel.sel );
 DisplayError( err );
 }
 else
 {
 err = BuildLines(validSel, &selLine);
 DisposHandle( validSel.sel );/* free memory */
 if ( err )
 DisplayError( err );
 
 if (selLine.noLines > 0) /* test 1 line */
 {
 
 Bubble(selLine.lines, sizeof(selLine.lines[0]), 
 selLine.noLines, Comp, Swap);
 
 err = SelToText( selLine, &txt );
 
 for ( i=0; i<selLine.noLines; i++ ) 
 /* Dispose selLine */
 {
 if ( selLine.lines[i] != NIL )
 {
 DisposHandle( selLine.lines[i] );
 selLine.lines[i] = 0L;   /* mark it disposed */
 }
 }
 if ( selLine.lines != NIL )
 {
 DisposPtr( selLine.lines );
 selLine.lines = 0L; /* mark it disposed */
 }
 
 if ( txt != NIL )
 {
 err = UpdateSel( txt );
 DisposHandle( txt );
 if ( err != noErr )
 DisplayError( err );
 }
 }
 }
 }
 
 RestoreA4();    /* restore reg A4 to its original value */
 }

Listing:  GetSelection.c

#include “ToolSort.h”

/*==================================================
Module: GetValidSel

Purpose:Get a Selection and verify if Selection is correct type, 
 correct format.
 
Returns:Valid-Selection   

Functional Details:

 Verify if Selection Type IS ‘TEXT’
 Check if last character of Selection is eol
 Report errors to user
================================================*/

GetValidSel(validSel)
 SelRec *validSel; /* Ptr to SelRec */
 {
 Handle scrap;   /* Handle to scrap */
 Handle selection; /* Handle to scrap */
 int    error = 0;
 long   length;  /* Scrap length */
 
 length = GetSel( &scrap );
 if ( length > 0 )
 {
 if ( (*scrap)[length-1] != ‘\r’ )
 error += End_Error;
 else
 {
 HLock( scrap );
 error = PtrToHand(*scrap, &selection, length); 
 /* copy scrap */
 HUnlock( scrap );
 
 if (error != noErr)
 error = Memory_Error;
 }
 }
 else
 error = -length;/* if length <0 then error */
 
 if ( error != No_Error )
 {
 validSel->sel = 0L; /* On error set handle to Nil */
 validSel->length = 0;
 }
 else
 {
 validSel->sel = selection;
 validSel->length = length;
 }
 
 return( error );
 }
 
long GetSel( sel )
 Handle *sel;    /* Ptr to a Handle to the scrap */
 {
 int err = noErr;
 long len;/* len of scrap */
 
#if DESK_SCRAP   /* Desk Scrap */
{
 long   offset;  /* offset to start of data */
 ResType type = ‘TEXT’;

 *sel = NewHandle(0L);    /* Allocate minimum space*/
 if (*sel == NIL)/* error check */
 err += Memory_Error;
 else
 {
 len = GetScrap( *sel, type, &offset);
 
 if ( len <= 0 )
 {
 switch( len )
 {
 case NULL:
 err += Empty_Error;
 break;
 case noTypeErr:
 err += Type_Error;
 break;
 case memFullErr:
 err += Memory_Error;
 break;
 default:
 if (len < 0)
 err += Sys_Error;
 }
 *sel = 0L; /* On error set handle to NIL */
 len = -err;/* if length <0 then error */
 }
 }
 
 return( len );
 
}

#else   /* Text edit scrap */

 *sel = TEScrapHandle();
 len = TEGetScrapLen();
 
 if ( len <= 0)
 {
 err = Empty_Error;
 *sel = 0L; /* On error set handle to NIL */
 len = -err;/* if length <0 then error */
 }

 return( len );
 
#endif
 }

Listing:  DiplayError.c

#include “ToolSort.h”
/*========================================================
Module: DisplayError
Purpose:Display the error messages associated with err. 
returns:
Functional Details:
 If alert resources are not available just beep and exit.
 else display error messages.
================================================*/

DisplayError(err)
 unsigned int err;
 {
 int  i;/* index counter */
 int  index[9];  /* index to diagnostics */  
 int  s;/* shift counter */
 Handle h1, h2;
 long   maxmem;
 long grow;
 
 static char *diag[9];
 
 diag[0] = “”;     /*No_Error*/
 diag[1] = “\pSelection must end with a carriage return.”; /*End_Error*/
 diag[2] = “\pNo selection of type ‘TEXT’ in scarp.”;      /*Type_Error*/
 diag[3] = “\pNot enough memory.”;   /*Memory_Error*/
 diag[4] = “\pNil Handle Error.”;    /*Nil_Hand_Error*/
 diag[5] = “\pNo selection, scrap empty.”;                       /*Empty_Error*/
 diag[6] = “\pA system error, probably relating to the filing system.”; 
/*Sys_Error*/
 diag[7] = “\pError writing desk scrap.”;                        /*Scrap_Error*/
 diag[8] = “\pError writing writing TEScrap.”;                   /*TEScrap_Error*/
 
 h1 = GetResource(‘ALRT’, alertID);/* Check for resource load error */
 h2 = GetResource(‘DITL’, alertID);
 if ( h1!=NIL && h2!=NIL )
 {
 for (s=0, i=0; s<9; s++)
 {
 index[s] = 0;   /* initialize index arry to zero */
 if ( 0x0001 & err )
 {
 index[i] = s+1; /* set index array to index of diagnostics */
 i++;
 }
 err >>= 1; /* shift err 1 bit to the right */
 }
 InitCursor();
 ParamText(diag[index[0]],diag[index[1]],
 diag[index[2]],diag[index[3]]);
 StopAlert( alertID, NIL );
 }
 else
 {
 if ( h1 != NIL )
 ReleaseResource( h1 );
 if ( h2 != NIL )
 ReleaseResource( h2 );
 
 maxmem = MaxMem(&grow);
 if ( maxmem > 500L )
 SysBeep( 4 );   /* SysBeep needs memory to work with */
 }
 }

Listing:  BuildLines.c

#include “ToolSort.h”

/*===========================================================
Module: BuildLines
Purpose:Extract the lines of text from validSel and put them
 into the structure SelLine along with the number 
 of lines.
Returns:selLine, err
====================================================*/

BuildLines( validSel, selLine )
 SelRec validSel;/* handle to valid selection */
 SelLine*selLine;/* array of handles to lines */
 {
 register Handle h;/* handle to line of text */
 register int  l = 0;/* line counter */
 register int  len;/* length of selection */
 register int  p = 0;/* selection position pointer */
 int    err = 0; /* memory error flag */
 int    num = 0; /* number of lines */
 char   ch;
 
 if ( (len=validSel.length) <= 0 )
 {
 err = Empty_Error;
 selLine->noLines = 0;
 selLine->lines = 0L;
 }
 else
 {
 for (l=0, p=0; p<len; p++) /* count number of lines */
 {
 ch = (*validSel.sel)[p];
 (ch==’\r’) ? l++: l;
 }
 
 if ( (num=l) <= 0 )
 {
 err = End_Error;
 selLine->noLines = 0;
 }
 else
 {
 selLine->lines = (Handle *)NewPtr( (long) sizeof(Handle)*num );
 
 if ( selLine->lines == NIL )
 {
 err = Memory_Error;
 selLine->noLines = 0;
 }
 else
 {
 h = NewHandle(0L);
 selLine->lines[l=0] = h;
 
 if ( h != NIL )
 {
 for ( l=0, p=0; p<len; p++ )
 {
 ch = (*validSel.sel)[p];
 err = PtrAndHand( &ch, selLine->lines[l], 1L);
 if ( ch==’\r’ && p<len-1 )
 {
 h = NewHandle( 0L );
 selLine->lines[++l] = h;
 if ( h == NIL )
 {
 err = Memory_Error;
 break;
 }
 }
 }
 }
 else
 err = Memory_Error;
 
 if (err == noErr)
 selLine->noLines = num;
 else
 {
 selLine->noLines = 0;
 for (; l >= 0; l-- )/* dispose garbage */
 if ( selLine->lines[l] != NIL )
 {
 DisposHandle( selLine->lines[l] );
 selLine->lines[l] = NIL;
 }
 if ( selLine->lines != NIL )
 {
 DisposPtr( selLine->lines );
 selLine->lines = NIL;
 }
 }
 }
 }
 }

 return( err );
 }

Listing:  Comp & Swap.c

#include “ToolSort.h”

/*=======================================================
Module: Comp
Purpose:Transforms e1 and e2 of type char * to the type Str255. 
 Compares two strings: s1 and s2, returns -1 if
 s1 < s2, 0 if s1 == s2, and 1 if s1 > s2. 
Uses:   
Returns:eq
============================================*/
Comp(e1, e2)
 Handle *e1;
 Handle *e2;
 {
 int    eq = 0;
 int    err;
 long size1;
 long size2;
 Str255 s1;
 Str255 s2;
 
 size1 = GetHandleSize(*e1);
 size2 = GetHandleSize(*e2);
 
 if (size1<255 && size2<255)/* convert s1 & s2 to Str255 */
 {
 s1[0] = size1;  /* set size byte */
 BlockMove( **e1, s1+1, (long)size1);/* copy string */
 
 s2[0] = size2;  /* set size byte */
 BlockMove( **e2, s2+1, (long)size2);/* copy string */

 eq = RelString(s1, s2, (Boolean)0, (Boolean)0);
 }
 return(eq);
 }

/*========================================================
Module: Swap
Purpose:Exchanges e1 with e2.
Returns:
=====================================================*/
Swap(e1, e2)
 Handle *e1;/* pointer to a Handle of a str of char */
 Handle *e2;/* pointer to a Handle of a str of char */
 {
 Handle temp;
 
 temp = *e1;
 *e1 = *e2;
 *e2 = temp;
 }

Listing:  UpdateSel.c

#include “ToolSort.h”

/*=========================================================
Module: UpdateSel
Purpose:Put seltxt into scrap.
Returns:err
=======================================================*/

UpdateSel( txt )
 Handle txt;/* text to be placed into scrap */
 {
 
 long len;/* length of txt */
 long   err = 0; 
 
#if DESK_SCRAP

 if ( txt != NIL )
 {
 len = GetHandleSize( txt );
 err = ZeroScrap();
 if (err == noErr && len > 0)
 {
 HLock( txt );
 err = PutScrap( len, ‘TEXT’, *txt );
 HUnlock( txt );
 }
 }
 else
 err = Nil_Hand_Error;
 
 switch( err )
 {
 case noErr:
 if ( len == 0 )
 err = Empty_Error;
 else if ( len < 0 )
 err = Sys_Error;
 break;
 case noScrapErr:
 err = Scrap_Error;
 break;
 case memFullErr:
 err = Memory_Error;
 break;
 default:
 if (err < 0)
 err = Sys_Error;
 }
 
#else

 if ( txt != NIL )
 {
 len = GetHandleSize( txt );
 err = ZeroScrap();
 if (err == noErr && len > 0)
 {
 HLock( txt );
 err = PutScrap( len, ‘TEXT’, *txt );/* copy txt to Desk scrap */
 HUnlock( txt );
 if ( err == noErr )
 {
 err = TEFromScrap();/* copy desk scrap to TE scrap */
 if ( err != noErr )
 err = TEScrap_Error;
 }
 }
 }
 else
 err = Nil_Hand_Error;

 switch( err )
 {
 case noErr:
 if ( len == 0 )
 err = Empty_Error;
 else if ( len < 0 )
 err = Sys_Error;
 break;
 case noScrapErr:
 err = Scrap_Error;
 break;
 case memFullErr:
 err = Memory_Error;
 break;
 default:
 if (err < 0)
 err = Sys_Error;
 }

 
#endif

 return( err );
 }

Listing:  SelToText.c

#include “ToolSort.h”

/*=======================================================
Module: SelToText
Purpose:Transform the structure SelLine to SelTxt (text).  
Returns:txt, err
========================================================*/

SelToText( sortSel, txt )
 SelLinesortSel; /* array of handles to sorted lines of text */
 Text *txt; /* handle to lines in text format */
 {
 int    err = 0;
 int    num;/* number of lines */
 int  l;/* line number index */
 
 *txt = 0L; 
 num = sortSel.noLines;
 
 if ( num > 0 )
 {
 *txt = NewHandle(0L);
 
 if (*txt != 0L)
 {
 for ( l=0; l<num && err == noErr; l++ )
 {
 HLock( sortSel.lines[l] ); /* HandAndHand deref */
 err = HandAndHand( sortSel.lines[l],*txt);
 HUnlock( sortSel.lines[l] ); 
 }
 if ( err != noErr )
 {
 DisposHandle( *txt );
 *txt = NIL;/* mark handle empty */
 err = Memory_Error;
 }
 }
 else
 err = Nil_Hand_Error;

 }
 else
 err = Empty_Error;

 return ( err );
 }

Listing:  BubbleSort.c

#include “ToolSort.h”
/*=========================================================
Module: bubble
Purpose:Sort array in ascending order.  
Notes:  Sorts and array in increasing order.  This algorithm has a complexity 
of n^2.
Uses:   Function Comp( *type, *type) and function Swap( *type, *type).
Returns:selLine
====================================================*/
Bubble(elem, big, num, comp, swap) 
 void *elem;/* Array of elem pointers*/
 int    big;/* size of the data elements */
 int    num;/* No. elem*/
 int  (*comp)(); /* pointer to comparison function */
 int    (*swap)(); /* pointer to swap function */
 {
 register char *b = elem;
 register int  k,i;
 
 for (k=1; k<=num-1; k++)
 {
 for (i=0; i<num-k; i++)
 {
 if ( (*comp)(b+i*big, b+(i+1)*big) > 0)
 (*swap)(b+i*big, b+(i+1)*big);
 }
 }
 }

Listing:  Shell.c

shell(r, num)
 char *r;
 int    num;
 {
 char h[10];
 char r0;
 int    H,i,j,s;
 
 /* 
 The following array is the sequence h[1]=1, h[s+1]=3*h[s]+1 derived 
from emprical data.  The array has been carried out to the limit bounded 
by num an integer. Please note the sequence h can greatly effect the 
sorting time.
 */
 
 h[9]=29524; h[8]=9841; h[7]=3280; h[6]=1093; h[5]=364;
 h[4]=121; h[3]=40; h[2]=13; h[1]=4; h[0]=1;
 
 for (s=0; h[s+2]<num; ++s)
 ;
 for ( ;s>=0; --s )
 {
 H = h[s];
 for ( i=H; i<num; i++ )
 {
 r0 = r[i];
 j = i-H;
 while ( r0<r[j] && j>=0 && j<num )
 {
 r[j+H] = r[j];
 j -= H;
 }
 r[j+H] = r0;
 }
 }
 }