All DatabasesMacTech Vol 10-1994
Handles
Volume Number: 10
Issue Number: 1
Column Tag: C Workshop
Handles, Hiccups, & Trees
Reducing SetHandleSize calls
By Ken Earle, Dynabyte
Note: Source code files accompanying article are located on MacTech CD-ROM or
source code disks.
The problem: here and there in your app you need to repeatedly append data to the
end of a Handle. All those SetHandleSize() calls are giving your Apple a hint of Lemon.
The alternative is to scan all the data first so you can determine the final Handle size in
advance-inelegant at best, and often not much faster.
The solution: fewer SetHandleSize() calls, combined with a data structure and a
few functions to keep track of how big the Handle is, and how much of it you’ve used.
The code with this text implements a simple scheme for cutting down on
SetHandleSize() calls, in “Hiccup.c” and “Hiccup.h”. Usage is illustrated in “Tree.c”
and “Tree.h”, which provide a general binary tree package. Use of the binary tree is
illustrated in “TreeExample.c”, and to see an illustration of that-run it. All code is for
THINK C, but getting it to run under MPW should require at most a few small changes.
Handling Handles with Hiccups
You have yourself a Handle, and you want to add little bits and pieces to the end of
it, possibly all of the same size, possibly not. So many SetHandleSize() calls, so little
time.
To cut down on the number of calls to SetHandleSize(), it will be necessary to
ask, each time we call it, for enough memory to accomodate several additions-and so
we’ll need to keep track of how much of the Handle has actually been used, as well as
the “real” size of the Handle. When the amount used plus the amount we need at the
moment exceeds the real size of the Handle, then we do another SetHandleSize(), again
asking for enough incremental memory to handle several more additions. So instead of
growing smoothly, our Handle will stay the same size for several additions and then
“hiccup” to a substantially larger size. When finished adding, we shrink the Handle
down to the size actually used.
In pseudocode, it goes like this (see “Hiccup.h” and “Hiccup.c” as you go):
/*1*/
#include "Hiccup.h
and then inside some function
HH hh; // declare a “hiccup handle handler”
long startSize = best guess on total bytes needed,
increment = enough bytes for a few additions;
if (!HicNew(&hh, startSize, increment))
use smaller startSize, or give up;
while (more entries to append)
{
hh.dataPtr = pointer to new data;
hh.dataSize = size of new data in bytes;
if (!HicAdd(&hh))
use smaller increment, or give up;
}
HicClose(&hh);//shrink Handle to final size
The newly created handle full of stuff is "hh.h".
There’s no hard rule for estimating the starting size or the increment amount:
startSize should be close to the expected final size, if you can estimate it, and
increment should be at least several times the average entry size. A bit of
experimenting, stopwatch in hand, helps with the final fine-tuning.
If the data you’re copying into your new handle comes from some other Handle,
then lock that other Handle while calling HicAdd(), HicAddPtr(), or HicAddPtrSize() -
they move memory when calling SetHandleSize(). Note that if hh.dataPtr or hh.dataSize
don’t change then you just need to set them once, before the first call to HicAdd(). It’s
quite OK to change the value of hh.inc (the “increment”) while adding entries, and it
doesn’t have to be a multiple of hh.dataSize - it just has to be positive. Some other
options and variations are available, as described in the source code.
Handling Trees with Hiccups
“Tree.h” and “Tree.c” provide a binary threaded tree package based on Handles,
using the “Hiccup” functions for memory management. The “tree” is an array of nodes
stored in a single Handle, with “left” and “right” links to other nodes being indexes
into the node array. A thread is simply the negative of an array index. The root node of
the tree just provides a place to start, and counts as being above all other nodes.
Many trees containing different kinds of data can be created and managed at once,
since node addition and comparison is done with pointers to functions that you write,
one set for each kind of data, and there are no static variables. “TreeExample.c” shows
a couple of uses, including examples of data addition and comparison functions for data
which also consists of an array of structures in a Handle.
No function is provided for deleting specific nodes (it would be rather complex
and slow). In general, the “array in a Handle” approach suffers if frequent deletions
from the array are required.
Figure 1. A standard view of a threaded tree, and a more literal view as an array of
nodes in a Handle. Circled numbers indicate the order in which the nodes were added,
small letters are the ASCII values of the nodes. Links are shown straight, threads as
curved lines. Note the array preserves the original order of the nodes, as well as
imposing ASCII order with the links.
Onwards (hic)
Armed with the more efficient Handle handling in “Hiccup.c”, you’re in a good
position to implement standard data structures such as stacks and hash tables using
Handles instead of the usual malloc’d pointers that you find in textbooks. A linked list
of structures can be replaced by a Handle holding an array of the structures, and the
linkage pointers become long ints representing byte or array offsets into the Handle. If
associated data is variable in size, it’s often appropriate to store the data in a second
separate Handle, and pointers-to-data are replaced by integer offsets into that Handle.
The main drawback of the Handle approach is that deletions from an array in a
Handle are more expensive to do than deletions from a linked list: on average, to delete
an array entry properly you have to BlockMove() half of the Handle, and look at all of
the linkage offsets. However, occasional deletes are usually quite tolerable.
Advantages? The textbook advantage would be that many many pointers could
fragment your heap, whereas a few Handles won’t. Another advantage is that using
Handles is good practice doing things “the Macintosh way”. The main practical
advantage, though, is that once you have your sophisticated structures bottled up in one
or two Handles you can write them as-is to disk, and read them back as-is (those
integer offsets remain valid, unlike pointers)-and since Macintosh file management is
a leading cause of hair loss, you may well prefer the lesser pain of Handles. Then again,
real C programmers wear hair shirts....
At one extreme, a simple static array may be all you need to hold some data. At the
other extreme, you may need a Handle which in turn holds other Handles which in turn
hold other Handles and so on (Apple events, for example), or a linked list of
nonrelocatable blocks. But when you need to manage a variable amount of data, and
won’t be deleting very often, the simplest solution is often to load it into a Handle and
give it the hiccups.
Listing: Hiccup.h
/*2*/
/* Hiccup.h - interface and struct for Hiccup.c routines to
grow handles in large steps while adding small bits to them.
Usage: see Hiccup.h
*/
#pragma once
/* A separate HH is passed for each handle being hiccuped.
All positions and sizes are in bytes. */
typedef struct HicHandle // hiccup handle(r)
{
Handle h;
long realSize; // >= used size
long inc; // increment, > 0.
long freePos; // used size, = next free position
long dataSize; // of one entry. May be 0.
void *dataPtr; // locked! May be NULL.
} HicHandle, *HHPtr;
#ifndef HH
#define HH HicHandle
#endif
/* Hiccup.c functions */
Boolean HicNew(HHPtr hP, long startSize, long increment);
Boolean HicAdd(HHPtr hP);
Boolean HicAddPtr(HHPtr hP, void *dataPtr);
Boolean HicAddPtrSize(HHPtr hP, void *dataPtr,
long dataSize);
void HicClose(HHPtr hP);
void HicDispose(HHPtr hP);
Listing: Hiccup.c
Codeexamplestart
/* 3 */
/* Hiccup.c - allocate handles in lumps to minimize
time spent moving memory around.
Usage:
-call HicNew(), passing address of an HH (hP), desired
starting size and increment size
-if entries will be all the same size, set hP->dataSize
-if entries will be all from the same (locked) place, set
hP->dataPtr
-call any of HicAdd(), HicAddPtr(), HicAddPtrSize()
repeatedly to add entries. If data is being added from
an existing handle, make sure it's locked!
-when done adding call HicClose()
-note entries are always added at end of handle.
-"dataSize" can be varied, and "inc" need not be larger
than "dataSize
-to restart with existing handle;
set up HH with h, realSize, inc, freePos,
and then proceed as above.
-to start with a dummy entry, call HicNew() followed by
hP->freePos += size of dummy entry,
or Add a dummy entry.
-Dispos of a handle in the usual way, or call HicDispose.
-comment out "H_FULL_CHECKING" after final testing
/* 4 */
*/
#define H_FULL_CHECKING // if defined, check more errors
// struct "HH" and function prototypes for hiccups
#include "Hiccup.h
// Just loads segment - sometimes handy while testing
Referenced by (32):