Array Management

Technical Notes

Overview
Structured and Unstructured Arrays
Array Elements
The Comparison Function Used by the Sort/Search Functions
Defining and Initializing Structured Arrays
Manipulating Array Elements
Locating Array Elements
Determining the Status of a Structured Array
Sample Program

Overview

This unit consists of functions and macros which define and initialize arrays, locate array elements, manipulate array elements, and determine the status of an array. Two sets of functions are provided: one for structured arrays and one for standard (unstructured) arrays.

Structured and Unstructured Arrays

Both structured and unstructured arrays are supported by the functions in this unit. Unstructured arrays are contiguous sequences of identically sized and structured elements (this is the traditional definition of an array). Structured arrays are identical to unstructured arrays except they are preceded by an array header. This header maintains the following information about the array: the maximum number of elements, the current number of elements, the size of each element, and the address of the comparison function to be used with the array. The content and organization of the information in structured array headers is documented and defined in ARRAY.H as well as in the documentation for the _array_init function in the Reference Section.

Structured 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.

Array Elements

Each array element may be 1 byte to 64K bytes in size. All array elements in a given array must be identical in size and structure. Elements are origin zero indexed (the index of the first array element is 0; the index of the nth array element is n-1).

The Comparison Function Used by the Sort/Search Functions

Array management functions make no assumptions about the structure or content of array entries. Instead, a programmer-supplied comparison function is called by the array management functions every time two array elements must be compared. The comparison function is the sole indicator of the relative order of array elements. This allows the sorting order of an array to be changed (ascending, descending, etc.) simply by changing the comparison function and resorting the array.

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.

Defining and Initializing Structured Arrays

ARRAY_ALLOC
(Macro) Allocates and initializes a structured array.
_array_init
Initializes a structured array.
The ARRAY_ALLOC macro statically declares a structured array. ARRAY_ALLOC is used to allocate space for an empty structured array and to create and initialize the array header. ARRAY_ALLOC does not initialize the array elements. The array elements may be initialized to 0x00 by using the static directive with ARRAY_ALLOC.

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):

ARRAY_COUNT
array) (array ptr -2) Current number of array elements.
ARRAY_MAX
array) (array ptr -2) Maximum number of array elements.
ARRAY_ESIZE
array) (array ptr -6) Size of each array element, in bytes.
ARRAY_CMPF
array) (array ptr -8 in small code models and -10 in large code models) User comparison function address.
In addition, HEADER_SIZE is defined in ARRAY.H to indicate the exact size of the array header in the current memory model. To ensure compatibility with future releases, HEADER_SIZE should be used any time the size of the header needs to be known. This equate may be used to determine the required size of a structured array buffer, as follows:

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.

Manipulating Array Elements

_array_append
Appends an element to the end of a structured array.
_array_insert
Inserts an element into a structured array.
_array_delete
Removes an element from a structured array.
_array_qsort
Sorts the elements in a structured array.
_quick_sort
Sorts the elements in an array.
These functions add, remove, and sort array elements.

_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.

Locating Array Elements

_array_next
Returns a pointer to the next element in a structured array.
_array_prev
Returns a pointer to the previous element in a structured array.
_array_nth
Returns a pointer to a specified structured array element when given its index.
_array_curn
Returns the index of a specified element in a structured array.
_array_bfind
Searches for an element in a structured array using a binary search.
_array_lfind
Searches for an element in a structured array using a forward linear search.
_array_lfindr
Searches for an element in a structured array using a reverse linear search.
_bin_search
Searches for an element in an array using a binary search.
_lin_search
Searches for an element in an array using a forward linear search.
_lin_rsearch
Searches for an element in an array using a reverse linear search.
These functions locate specified elements in structured and unstructured arrays using linear, binary, and indexed searches.

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.

Determining the Status of a Structured Array

_array_full
Indicates whether or not a structured array is full.
ARRAY_CMPF
(Macro) Returns the address of the comparison function.
ARRAY_CLEAR
(Macro) Clears a structured array.
ARRAY_COUNT
(Macro) Returns the number of elements in a structured array.
ARRAY_EMPTY
(Macro) Indicates whether or not a structured array is empty.
ARRAY_ESIZE
(Macro) Returns the size of each element in a structured array.
ARRAY_FULL
(Macro) Returns a 1 if the array is full, 0 a if it is not full.
ARRAY_MAX
(Macro) Returns the maximum number of elements allowed in array.
These functions and macros indicate the status of a structured array. _array_full indicates whether or not a structured array contains the maximum number of allowed elements. ARRAY_CMPF returns the address of the assembly comparison function to be used for searches and finds on the array. ARRAY_EMPTY indicates whether or not the array contains any elements. ARRAY_FULL indicates whether the array is full, or the maximum number of allowed elements is reached. ARRAY_CLEAR clears a structured array by setting the current element count to zero. ARRAY_COUNT and ARRAY_ESIZE return the current number and size of the elements in an array. ARRAY_MAX returns the maximum number of elements to be allowed in the array.

Sample Program

The sample program shown below uses of a number of array functions and demonstrates inserting elements into a structured array as well as sorting and searching the array using functions for structured and unstructured arrays. The program is listed in its entirety.

#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