Local Memory: 4.1 Special LMem Uses: Chunk Arrays

| Up: GEOS SDK TechDocs | Up | Prev: 4 Special LMem Uses | Next: 4.2 Element Arrays

Very often an application will need to keep track of many different pieces of data and access them by an index. An application can do this in the traditional way, i.e., allocate a block of memory and set it up as an array. However, GEOS provides a mechanism which is often more suitable: the chunk array . The chunk array routines let you dynamically insert or delete elements in the middle of an array; you can get a pointer to an arbitrary element (specified by its index number); you can sort the array based on any arbitrary criterion. The array can be specified as "uniform-size" (all elements the same size, specified when the chunk array is created), or "variable-size" (each element can be created at an arbitrary size and can be resized at will). Note that either type of array can grow or shrink dynamically; while the elements may be of a fixed size, the array need not be.

The chunk array is implemented on top of the LMem routines. The entire array is a single chunk in a local memory heap (hence the name). It therefore has a maximum total size of somewhat less than 64K, and memory efficiency drops significantly if it is larger than roughly 6K. If you need a larger array, you should use a Huge Array (see the VM chapter). If you will be using the chunk array routines, you should include chunkarr.h .

Structure of the Chunk Array

A chunk array is contained in a single chunk in an LMem heap. It begins with a special header structure which specifies certain characteristics of the chunk array: the number of elements in the array, the size of each element (or zero for variable sized arrays), the offset from the start of the chunk to the first element, and the offset from the first element to the end of the array. The header is a structure of type ChunkArrayHeader ; an application can examine the fields of this structure directly or by using chunk array routines. The creating application can request that the chunk array contain some blank space between the header and the first element; it can use that space however it likes.

Elements can be referenced by index number. The first element has index number zero. You can translate element numbers to pointers, and vice versa, by calling ChunkArrayElementToPtr() and ChunkArrayPtrToElement() (see Adding, Removing, and Accessing Elements ).

A uniform-size chunk array has a simple structure. After the header (and the extra space, if any) come the elements. They follow one after another, with no free space between them. An application can request a pointer to any element, specified by index; the chunk array routine multiplies the index by the size of each element and adds the product to the address of the first element, producing a pointer to the requested element. An application can also proceed through the array, going from one element to the next, without specifically requesting pointers.

The structure of a variable-size chunk array is a little bit more complicated. After the header (and extra space) is a lookup-table of two-byte entries, each containing the offset from the start of the chunk to the appropriate element. The chunk array routines maintain this table automatically. When an application wants to reference a given element, the chunk array routine doubles the index number and adds it to the offset to the start of this table; this produces the address of a table entry, which itself contains the offset to the actual element. Effectively, there are two arrays with the same number of elements; the first is a uniform-sized array of offsets to the entries in the second (variable-sized) array. However, this is transparent to the application, which merely requests a pointer to element n and is returned that pointer. It does not need to know or care about the extra table constructed by the chunk array routines.

Creating a Chunk Array

ChunkArrayCreate(), ChunkArrayCreateAt(), ChunkArrayCreateAtHandles(), ChunkArrayHeader

Chunk arrays are created in local memory heaps. An LMem heap can have several chunk arrays, and it can have other types of chunks besides chunk arrays; however, since an LMem heap is limited to 64K in total size, the more you put in the heap, the less room there is for a chunk array to grow.

The first step in creating a chunk array is to create an LMem heap. Create the heap the same way you would any general LMem heap. The heap should probably be left resizable, since that way it will be able to grow to accommodate the chunk array.

Once you have created the heap, use the routine ChunkArrayCreate() to create the chunk array. This routine will allocate a chunk for the chunk array, initialize the array, and return the chunk handle. Since the routine allocates a chunk, it can cause chunk shuffling or heap resizing; thus, all pointers to the heap are invalidated.

ChunkArrayCreate() takes four arguments:

There is another version of this routine which creates a chunk array in an existing chunk. This routine, ChunkArrayCreateAt() , takes three arguments, namely an optr indicating the chunk, the size of each element, and the size of the header. It allocates a chunk array in that chunk, resizing it if necessary, and returns the chunk's handle. Any data in the chunk may be overwritten (except for whatever data falls in the header area after the ChunkArrayHeader ). The version which takes handles is called ChunkArrayCreateAtHandles() .

When you are done with a chunk array, you can free it with LMemFree() the way you would any other chunk.

Adding, Removing, and Accessing Elements

ChunkArrayAppend(), ChunkArrayAppendHandles(), ChunkArrayInsertAt(), ChunkArrayInsertAtHandle(), ChunkArrayDelete(), ChunkArrayDeleteHandle(), ChunkArrayDeleteRange(), ChunkArrayDeleteRangeHandles(), ChunkArrayElementResize(), ChunkArrayElementResizeHandles(), ChunkArrayElementToPtr(), ChunkArrayElementToPtrHandles(), ChunkArrayPtrToElement(), ChunkArrayPtrToElementHandle(), ChunkArrayGetElement(), ChunkArrayGetElementHandles()

The chunk array library provides a high-level interface for working with the arrays. The application specifies a request in general terms (e.g., "Insert a new element before element five," "Give me a pointer to element 20"). The routines take care of the low-level memory management: inserting bytes, swapping chunks to make room, etc. These routines depend on the LMem routines; therefore, the block containing the LMem heap must be locked or fixed when you use these routines (or any other chunk array routines).

When you call a chunk array routine, you must pass the handles specifying the chunk. As with other routines which act on a chunk, these routines come in two formats: one in which the chunk is specified with an optr, and one in which it is specified with the global memory handle and the chunk handle.

Adding elements to a chunk array is easy. To add an element to the end of a chunk array, use the routine ChunkArrayAppend() . This routine automatically updates the ChunkArrayHeader (and the lookup-table, if elements are variable-sized). The routine takes two arguments, namely the optr and the size of the new element. The size must be greater than zero. If the array elements are uniform-sized, the size argument is ignored. The routine will resize the chunk to accommodate the new element, update its header table (and lookup table if necessary), and return a pointer to the element. Since the chunk is resized, all other chunk pointers (and pointers within the chunk array) are invalidated. The version which takes handles is named ChunkArrayAppendHandles() .

You can also add an element within the middle of an array. The routine ChunkArrayInsertAt() takes three arguments, namely the optr, a pointer to the location at which to insert the element, and the size of the element (ignored for uniform-sized arrays). The size must be greather than zero. The routine will insert the appropriate number of bytes at that location in the chunk, update the header and lookup-table, and return a pointer to the new element. Pointers to chunks are invalidated. The version which takes the chunk handle, ChunkArrayInsertAtHandle() , is slightly unusual in that it is passed the chunk handle but not the global memory handle; the routine gets the segment address of the chunk from the passed pointers.

When you are done with an element, free it with ChunkArrayDelete() . This routine takes two arguments, namely the optr and a pointer to the element to be deleted. It shrinks the chunk; thus, it is guaranteed not to shuffle chunks, so chunk pointers remain valid (though pointers to elements within the chunk array will be invalidated if the elements come after the deleted element). Again, the handle version, ChunkArrayDeleteHandle() , is passed the chunk handle but not the global handle.

If you need to delete several consecutive elements, call ChunkArrayDeleteRange() . This routine takes three arguments: the optr to the chunk array, the index of the first element to delete, and the number of elements to delete. The specified elements will be deleted. As with ChunkArrayDelete() , the global and local heaps will not be shuffled. The handle version, ChunkArrayDeleteRangeHandles() , is passed the global handle of the LMem heap and the chunk handle of the chunk array instead of the optr to the chunk array.

Elements in variable-sized arrays can be resized after creation with the routine ChunkArrayElementResize() . This routine takes three arguments: the optr, the element number, and the new size. The new size must be greater than zero. The routine resizes the element and updates the lookup table. If the new size is larger than the old, null bytes will be added to the end of the element; chunks may be shuffled, so all chunk pointers are invalidated. If the new size is smaller than the old, the element will be truncated. This is guaranteed not to shuffle chunks, so pointers to chunks remain valid, though pointers within the array may be invalidated. The version which takes handles, ChunkArrayElementResizeHandles() , is passed both the global memory handle and the chunk handle.

If you have the index of an element and you want to access that element, use the routine ChunkArrayElementToPtr() . It takes three arguments: the optr, the element number, and a pointer to a word-length variable. The routine writes the size of the element in the variable and returns a pointer to the element. (If you are not interested in the element's size, pass a null pointer.) It does not change the chunk in any way, so no pointers are invalidated. If you pass an index which is out-of-bounds, ChunkArrayElementToPtr() will treat it as the index of the last element. (The constant CA_LAST_ELEMENT is often used for this purpose.) However, the error-checking version will always fatal-error if passed the index CA_NULL_ELEMENT (i.e. 0xffff). The version which takes handles is named ChunkArrayElementToPtrHandles() .

If you know the address of an element and you need to find out its index, use the routine ChunkArrayPtrToElement() . This routine takes two arguments, namely the optr and a pointer to the element. It returns the index number of the element. The version which takes the chunk handle, ChunkArrayPtrToElementHandle() , is passed the chunk handle and the pointer but not the global memory handle.

You can copy an element to a specified location with the routine ChunkArrayGetElement() . This routine takes three arguments: the optr, the element number, and a pointer to a buffer big enough to hold the entire element. The routine will copy the element to the specified buffer. The version which takes handles is called ChunkArrayGetElementHandles() .

Chunk Array Utilities

ChunkArrayGetCount(), ChunkArrayGetCountHandles(), ChunkArrayZero(), ChunkArrayZeroHandles(), ChunkArrayEnum(), ChunkArrayEnumHandles(), ChunkArrayEnumRange(), ChunkArrayEnumRangeHandles(), ChunkArraySort(), ArrayQuickSort(), bsearch()

To find out how many elements are in a chunk array, use the routine ChunkArrayGetCount() . This routine takes one argument, namely the optr. It returns the number of elements in the array. It does not change the array; no pointers are invalidated. The version which takes handles is named ChunkArrayGetCountHandles() .

If you want to delete all elements in the array but you don't want to free the array itself, use the routine ChunkArrayZero() . This routine takes one argument, namely the optr. It does not return anything. This routine deletes all the elements in the array, updates the header and lookup tables, and resizes the chunk. Since the chunk is truncated, no chunks are swapped, so no chunk pointers are invalidated (though pointers to elements are, naturally, invalidated). The version which takes handles is named ChunkArrayZeroHandles() .

If you want to apply a function to every element in the array, use ChunkArrayEnum() . This routine is passed three arguments:

The callback routine should be written to take two arguments:

ChunkArrayEnum() can be used for many different purposes, depending on the nature of the callback routine. For example, it can perform some action on every element (in which case it ought always to return false ); it can analyze the data in the various elements; it can check to see if any element meets some criterion. If it needs to write its results, it might do so at the location indicated by the pointer. ChunkArrayEnum() will not cause heap shuffling unless the callback routine causes it; thus, if the callback routine avoids shuffling the heap, it can (for example) be passed a pointer to a chunk in the same LMem heap as the chunk array. The version which is passed handles is named ChunkArrayEnumHandles() .

There is another version of ChunkArrayEnum() which acts on a range of elements. This routine is called ChunkArrayEnumRange() . This routine takes the same arguments as ChunkArrayEnum() , plus two more: a start index, and a number of elements to enumerate. ChunkArrayEnumRange() calls the callback routine for the element with the specified index, and for every element thereafter until it has processed the specified number of elements. You can have it enumerate to the end of the chunk array by passing a count of 0xffff. There is a version which takes handles called ChunkArrayEnumRangeHandles() .

You can get into trouble if more than one thread of execution is accessing a single ChunkArray and one or both of these threads is using one of the ChunkArrayEnum...() routines. The error-checking version of the kernel detects this situation and generates a CHUNK_ARRAY_ENUM_INSERT_OR_DELETE_RUN_BY_MULTIPLE_THREADS warning if it detects such. If your code is getting this warning, you should add some synchronization between threads. While one thread is enumerating through chunks in the chunk array, the other should do nothing to enumerate the same array, nor alter the array in any way.

The chunk array library also provides a sorting routine, ChunkArraySort() . This routine performs a modified Quicksort on the array, using insertion sorts for subarrays below a certain size. The sort routine takes three arguments: the chunk array's optr, a pointer to a comparison function, and a word of data which is passed to the comparison function.

Whenever the sort routine needs to decide which of two elements comes first, it calls the comparison routine. The comparison routine takes two arguments, namely the optr and the word of data passed to ChunkArraySort() . It returns a signed word with the following significance: If the first of the elements should come first in the sorted array, it returns a negative number; if the first element ought to come after the second, it should return a positive number; and if it doesn't matter which comes first, it should return zero. You can write a general-purpose comparison routine which can compare based on any of several parts of the element, and you can use the data word to instruct it which part to sort on; or you can use the data word to tell it to sort in ascending or descending order. ChunkArraySort() does not cause heap shuffling as long as the comparison routine does not. The routine which takes handles is called ChunkArraySortHandles() .

ChunkArraySort() is based on a more general array sorting routine, ArrayQuickSort() . ChunkArraySort() reads data about the array from the array header and passes the information to ArrayQuickSort() . You can call ArrayQuickSort() directly for arrays which are not chunk arrays, provided all elements are of uniform size. ArrayQuickSort() takes five arguments: a pointer to an array (which should be locked or fixed in memory), the number of elements in the array, the size of each element, a pointer to a callback routine (which has exactly the same format as the ChunkArraySort() callback routine), and a data word to pass to that callback routine. It does not return anything.

Note that ChunkArraySort() is currently implemented only for chunk arrays with fixed-sized elements.

The bsearch() routine conducts a binary search on an a sorted array.

Example of Chunk Array Usage

This section contains an example of how a chunk array might be used. It shows several common chunk array actions, including sorting the array.

Code Display 16-2 Example of Chunk Array Usage

/*
 *	Declarations (not in any routine)
 */
/* We want to store some data right after the chunk array header, so we define our
 * own header structure. Data in this structure (except for the ChunkArrayHeader
 * proper) will not be affected by the chunk array routines. */
typedef struct {
	ChunkArrayHeader			standardChunkArrayHeader;
	int			someData;
	float			someMoreData;
} MyChunkArrayHeader;
/* For simplicity, we define a structure which will be used for each element in the
 * array. (This is entirely optional.) */
typedef struct {
	char	someText[80];
	int	anInteger;
	float	aFloat;
} MyElementStructure;
/* We define some values to pass to the sort routine. The routine will sort by a
 * different field depending on what value it's passed. */
#define	SORT_ARRAY_BY_STRING				0
#define	SORT_ARRAY_ASCENDING_BY_INT				1
#define	SORT_ARRAY_DESCENDING_BY_FLOAT				2
/* This is the routine we will use to sort the array. We pass the address of this
 * routine to ChunkArraySort(), which will call this routine to compare elements.
 * It returns a negative number if the first element should come before the second
 * in the sorted array, and a positive integer if the second should come before the
 * first. If the elements can be in either order, it returns zero. */
sword _pascal MyElementCompareRoutine(
	MyElementStructure 			*e1,	/* Address of first element */
	MyElementStructure 			*e2,	/* Address of second element */
	word		valueForCallback) 		/* Datum passed in to ChunkArraySort() */
{
	/* We sort differently depending on what the value of valueForCallback is.
	 * That way, we can use this one routine for all our sorting.
	 */
	switch(valueForCallback) {
	    case SORT_ARRAY_ASCENDING_BY_INT:
	    /* Compare the elements based on their integer fields. Smaller int
	     * comes first.*/
		if (e1->anInteger < e2->anInteger)
		    return(-1);
		else if (e1->anInteger > e2->anInteger)
		    return(1);
		else return(0);
		break;
	    case SORT_ARRAY_DESCENDING_BY_FLOAT:
	    /* Compare the elements based on their float fields. Larger float
	     * comes first.*/
		if (e1->aFloat > e2->aFloat)
		    return(-1);
		else if (e2->aFloat < e2->aFloat)
		    return(1);
		else return(0);
		break;
	    case SORT_ARRAY_BY_STRING:
		/* In this case, we call the localization routine to compare the
		 * two strings. The localization routine has the same return
		 * conventions as this routine, so we return its result directly.
		 */
			return(LocalCmpStrings(e1->someText, e2->someText, 40));
			break;
	    default:
		/* If we get here, we were passed a bad callback word. The callback
		 * routine therefore does not express a preference in ordering the
		 * two elements; it shows this by returning zero.
		 */
	} /* end of switch */
}
/* All of the above appears in some declaration section. The code below might
 * appear in any routine which creates a chunk array. First, the declarations:
 */
MemHandle			blockWithHeap;
chunkHandle			myChunkArray;
MyChunkArrayHeader			*chunkArrayAddress;
MyElementStructure			*currentElement;
/* Now the code. Here, blockWithHeap has already been set to hold the block handle
 * of an LMem heap.
 */
MemLock(blockWithHeap); /* Always lock LMem heap before acting on it */
myChunkArray = ChunkArrayCreate(blockWithHeap, 
			sizeof(MyElementStructure), /* Size of each element */
			sizeof(MyChunkArrayHeader) /* Size of header */
			0);
/* Let's write some data into our part of the header. We need the array's address: */
chunkArrayAddress = LMemDerefHandles(blockWithHeap, myChunkArray);
chunkArrayAddress->someData = 42;						/* This data won't be affected */
chunkArrayAddress->someMoreData = 2.7182818;						/* by chunk array actions */
/* Now, let's create an element: */
currentElement = ChunkArrayAppendHandles(blockWithHeap, myChunkArray, 0);
	/* That invalidates chunkArrayAddress */
currentElement->anInteger = 1999;
currentElement->aFloat = 1.4142135;
strcpy(currentElement->someText, 				"Work is the curse of the drinking class.\n" \
				"  --Oscar Wilde")
/* We're done with the array for the moment, so we unlock it: */
MemUnlock(blockWithHeap);
/* Let's assume that several other elements are created now. */
/* . . . */
/* Now we need to sort the array: */
MemLock(blockWithHeap);
ChunkArraySortHandles(blockWithHeap, myChunkArray, 
		SORT_ARRAY_ASCENDING_BY_INT, /* this is passed to comp. routine */
		MyElementCompareRoutine);
/* Array is now sorted! */
| Up: GEOS SDK TechDocs | Up | Prev: 4 Special LMem Uses | Next: 4.2 Element Arrays