Technical Notes
OverviewStructured array headers allow advanced operations to be performed on structured arrays while minimizing the argument profile of the array functions. Both types of arrays, structured and unstructured, are accessed by passing the address of the first array element to the appropriate array management function. However, unstructured array operations require all additional array information (number of elements, comparison function address, etc.) to be specified in the function's argument list.
Since structured array headers precede the first element of the array, unstructured array functions may be used on structured arrays. Functions beginning with _array_... are only for use with structured arrays; all other array management functions may be used on either type of array.
The total size of an array cannot exceed 64K bytes. Any number of arrays may be simultaneously managed by the functions in this unit.
The speed of each comparison function directly impacts the performance of array sort/search functions. To maintain the advantage of the sort/search functions' assembly language structure, these functions were designed with an assembly language interface to the comparison function. The comparison function must meet the following requirements:
1. Preserve all registers. 2. Support the following inputs. DS:SI address of the element to compare against (key) ES:DI address of the element to compare (element) 3. Provide the following outputs. JA if key would appear after element in the array (key is greater than element). JE if key would appear at the same location as element in the array (key is equal to element). JB if key would appear before element in the array (key is less than element).Note that the return conditions for the comparison functions only indicate whether key should appear before, at, or after (i.e., JB, JE, or JA) the position of element in the array. If each array element is a single ASCIIZ string, then str_cmp or str_cmpi (no leading underscore) may be used as the comparison function.
The _array_init function dynamically defines and initializes an empty structured array. This function allows an array to be created in a buffer or on a heap at run time.
Structured arrays are declared in the following structure format (where MAX denotes the maximum number of elements allowed in the structured array and SIZE denotes the size of each array element, in bytes):
struct {
void(*cmpf)(void); /* assembly comparison function */
unsigned int size; /* size of each element */
unsigned int max; /* maximum number of elements */
unsigned int cnt; /* number of current elements */
char array[MAX][SIZE]; /* <--- the actual array starts here */
}; /* the array is referenced using ARRAYNAME.array */
WARNING! All functions that operate on structured arrays expect the address of the first element of the array (e.g., the array field in the structure above), NOT the beginning of the structure.
WARNING! Structured arrays should always be created using ARRAY_ALLOC, _array_init, or structures. This ensures that the array header data is always in the proper format for the structured array functions. Some compilers reserve the right to rearrange data that is not encapsulated in structures.
Since the array header precedes the first element in the array and structured arrays are referenced by the first element in the array, array header information may be accessed using the following macros (where array denotes the address of the first element in the array):
Size of buffer = (size * max) + HEADER_SIZE
where size is the size, in bytes, of each array element and max denotes the maximum number of array elements in the structured array.
_array_append appends an element to the end of a structured array. _array_insert inserts an element at a particular position in a structured array without overwriting the previous element. _array_insert may be used on a sorted array in conjunction with _array_bfind to add new elements in sorted order. The _array_delete function removes an element from a structured array.
The _array_qsort and _quick_sort functions sort arrays using a "median of three" recursive quicksort algorithm. _array_qsort is used for structured arrays and _quick_sort is used for unstructured arrays. These sorting functions perform non-stable sorts, meaning that the relative order of identical elements is not preserved.
Given a pointer to the current element, the _array_next and _array_prev functions locate the next or previous array element in a structured array. Given its origin zero index (element number), _array_nth returns a pointer to an element in a structured array. Given its pointer, _array_curn returns the index of the current element.
_array_bfind locates an element in a sorted structured array by using a non-recursive binary search algorithm. If a matching element is found, the address of the element is returned; otherwise, an address is returned at which the element may be inserted (using _array_insert) to maintain the array in sorted order.
_array_lfind and _array_lfindr linearly search a structured array in the forward and reverse directions for a particular element. (An array need not be sorted to use these search functions.) Linear searches are typically much slower than binary searches using _array_bfind, but binary searches require the array to be in sorted order.
_bin_search, _lin_search, and _lin_rsearch operate on unstructured arrays and perform the same functions as the _array_bfind, _array_lfind, and _array_lfindr functions.
#include
#include
ARRAY_ALLOC (test1, 5, 4, str_cmp); /* name, max, size, (ASM) cmpf */
char test2[5][4]; /* max, size */
void main()
{
void * location;
int i, num;
_array_insert(test1.array, "eee", test1.array[0]); /* insert first element */
_array_append(test1.array, "ddd"); /* append the rest */
_array_append(test1.array, "aaa");
_array_append(test1.array, "ccc");
_array_append(test1.array, "bbb");
/* ------ _array_qsort ------ */
_array_qsort(test1.array); /* sort the array */
num = ARRAY_COUNT(test1.array);
for (i = 0; i num; i++)
{ _put_str(test1.array[i]); _put_chr(' '); } /* display elements */
/* ------ _array_bfind ------ */
if(_array_bfind("111", test1.array, &location) == 0)
_put_str("\n\r \"111\" found in array. \n\r");
else
_put_str("\n\r \"111\" not found in array.\n\r");
_str_cpy (test2[0],"eee"); /* load C defined array */
_str_cpy (test2[1],"ddd");
_str_cpy (test2[2],"aaa");
_str_cpy (test2[3],"ccc");
_str_cpy (test2[4],"bbb");
/* ------ _quick_sort ------ */
_quick_sort((void *)test2, 5, sizeof(test2[0]), str_cmp);
for (i = 0; i 5; i++)
{ _put_str(test2[i]); _put_chr(' '); } /* display elements */
/* ------ _bin_search ------ */
if(_bin_search("bbb",(void *)test2, 5, sizeof(test2[0]),
str_cmp, &location) == 0)
_put_str("\n\r \"bbb\" found in array.");
else
_put_str("\n\r \"bbb\" not found in array.");
}
The sample program shown above (ARRAY.C) is provided on the distribution diskettes and may be compiled and linked using the following Microsoft C and Borland C command lines:
Microsoft C:
cl /c /I\msc\include /I\sa\include array.c
link array,array,,\sa\lib\_sas \msc\lib\slibce
Borland C:
bcc /c /ms /I\bc\include /I\sa\include array.c
tlink \bc\lib\c0s array,array,,\sa\lib\_sas \bc\lib\cs