 |
Y |
|
|
ou may be wondering why anyone would want to use
a bunch of undocumented array routines, with fairly |
|
|
|
xxxxxxxxxxxxxxx |
limited functionality, when the typical class library these
days includes dozens of useful container classes. Well, if
you're trying to keep your application as small as possible, it
is essential that you make the most of the facilities already
implemented by the operating system.
There are two groups of array functions covered in this
article: those that handle Dynamic Pointer Arrays (all pre-
fixed with DPA), and those that handle Dynamic Structure
Arrays (prefixed with DSA). I'm actually just guessing what
DPA and DSA stand for, but I think it's a fairly plausible
interpretation. The functions are all exported from
COMCTL32.DLL, and they are all exported by ordinal. |
|
| Dynamic Pointer Arrays |
|
Dynamic pointer arrays are the more versatile of the two
array groups. In addition to resizing automatically as items
are added and removed, they can also be sorted and sear-
ched using a callback comparison function. They even
allow you to specify the heap that should be used for me-
mory allocations. That may not sound particularly useful,
until you realise that on Windows 95 these functions default
to using the undocumented shared heap, which may not
always be such a great idea.
Their only real limitation is that the array items can only
be four bytes in size. Typically the items would be pointers
(hence the name 'Dynamic Pointer Array'), but they could
just as easily be integers or some other four byte data item.
If you do choose to use pointers, though, bare in mind that it
is the application's responsibility to allocate and free those
items. |
|
| The DPA Handle |
|
Every array that you create is identified by a DPA handle.
Each of the create functions return a handle, and all other
functions require a handle as their first parameter. A DPA
handle is just a pointer to a 20 byte structure containing |
information about the state of the array. Ideally
you would just treat it as a generic HANDLE, but
that isn't always possible. As an example, the
only efficient way to obtain the array size, is by
accessing the structure directly (see Figure 1 for
the structure definition).
nItems specifies the number of items in the
array. nCapacity, on the other hand, specifies the
maximum number of items that can be placed in
the array before new storage will have to be allo- |
|
|
typedef struct {
int nItems;
LPVOID *lpItems;
HANDLE hHeap;
int nCapacity;
int nDelta;
} * HDPA; |
| Figure 1 DPA Handle Structure |
|
|
|
cated. nDelta specifies the amount by which the array will
grow whenever new storage is required. On NT, though,
this delta value is doubled every time the array is resized
(unless is it already greater than 255). lpItems is a pointer
to the memory where the array items are stored and hHeap
is the heap handle used to allocate that memory. |
|
|
|
|
|
| Creating and Destroying |
|
The functions for createing and destroying arrays can be
seen in Figure 2. To create a new array, you would typi-
cally use the DPA_Create function (ordinal 328). It takes
only one parameter, the delta size, and returns a DPA
handle as the result. If you would like the array data to be |
allocated from a specific heap, you should
use the DPA_CreateEx function (ordinal
340). It requires a second parameter,
which specifies the handle of the heap to
use. If hHeap is NULL, you just get default
heap used by DPA_Create (on Windows
95 it's the undocumented shared heap; on
Windows NT, though, it's just the process
heap).
The DPA_Clone function (ordinal
331) can be used to create a duplicate of
an existing array, by passing the source
handle as the first parameter and NULL as
the second. If you want the new array to
use a different delta size or a different |
|
|
HDPA WINAPI DPA_Create(
int nDelta);
HDPA WINAPI DPA_CreateEx(
int nDelta,
HANDLE hHeap);
HDPA WINAPI DPA_Clone(
HDPA hSource,
HDPA hDest);
BOOL WINAPI DPA_Destroy(
HDPA hArray); |
| Figure 2 Create and Destroy Functions |
|
|
|
heap, you should create the array first with DPA_Create or
DPA_CreateEx, and then pass that handle as the second
parameter to DPA_Clone. Your new array will be
'overwritten' with the data from the source array, but it will
keep its delta size and heap handle.
All of these function return the handle of the newly
created array. If they fail for any reason, the return value
will be NULL. When you are finished using an array, you
should destroy it by passing the handle to DPA_Destroy
(ordinal 329). The return value is TRUE if the array was
destroyed successfully (it even returns TRUE if you pass it a
NULL handle). The return value is FALSE if an error oc-
cured when freeing the data. |
|
|
|
|
|
| Storing Values |
|
The functions related to storing array items can be seen in
Figure 3. The first function, DPA_InsertPtr (ordinal 334), |
will insert an item at a particular point in
the array. If you try to insert an item
beyond the end of the array, the item will
be appended. Typically you would set the
insert position to MAXINT if you wanted to
append an item (a negative insert position
will fail). The return value is the actual
position at which the item was inserted, or
-1 if the insertion failed.
DPA_SetPtr, on the other hand, will
store a value at a particular position in the
array, overwriting the value that was pre-
viously there. It has an ordinal value of
335. If you attempt to store an item
beyond the end of the array, the array will |
|
|
int WINAPI DPA_InsertPtr(
HDPA hArray,
int nPosition,
LPVOID lpItem);
BOOL WINAPI DPA_SetPtr(
HDPA hArray,
int nPosition,
LPVOID lpItem);
BOOL WINAPI DPA_Grow(
HDPA hArray,
int nCapacity); |
| Figure 3 Functions for Storing |
|
|
|
be expanded so that the operation will succeed. The return
value is TRUE if the operation was successful. If the opera-
tion fails, the function will return FALSE.
As mentioned before, the array will automatically resize
itself whenever an insertion operation exceeds the capacity
of the array. If you are adding a large number of items to
an array, it may need t to resize a number of times, which
can be quite a costly operation. To solve this problem, you
can use the DPA_Grow function (ordinal 330) to extend
the capacity of the array, prior to adding any items. Note
that the size is not affected by this operation - only the
capacity. Also note that the new capacity will not necessa-
rily be the exact value you specify, but it will be at least that
large. |
|
|
|
|
|
| Retrieving and Deleting |
|
All the functions necessary for retrieving and deleting items
can be seen in Figure 4. To retrieve a value from an array,
you would use the DPA_GetPtr function (ordinal 332). It
will return the pointer that is stored at the specified offset in |
the array. If you request a value
that is out of range, the function will
return NULL.
To remove a value from the ar-
ray you would use the function
DPA_DeletePtr (ordinal 336). It
will remove an item from a particu-
lar position in the array, and any
following items will be shifted down
by one. If the difference between
the capacity and the actual size is
now greater than the delta size, the
storage area will be reallocated to |
|
|
LPVOID WINAPI DPA_GetPtr(
HDPA hArray,
int nPosition);
LPVOID WINAPI DPA_DeletePtr(
HDPA hArray,
int nPosition);
BOOL WINAPI DPA_DeleteAllPtrs(
HDPA hArray); |
| Figure 4 Functions for Retrieving and Deleting |
|
|
|
use less memory. The return value is the pointer that was
removed from the array. If you attempt to remove a item
that is out of range, the function will return NULL.
To remove all items from the array, you would use the
function DPA_DeleteAllPtrs (ordinal 337). Bare in mind
that the pointers themselves aren't actually deleted, so you
may need to iterate through the array beforehand to free
any memory used by the individual itesm. The return value
is TRUE if the operation was successful. If the operation
fails, the function will return FALSE. |
|
|
|
|
|
| Sorting and Searching |
|
Sorting and searching can be accomplished with the
functions DPA_Sort and DPA_Search (obviously enough). |
Both require that you
specify an applica-
tion-defined callback
function that is used
to compare the rela-
tive order of any two
items (see Figure 5). |
|
|
typedef int (CALLBACK *LPFNDPACOMPARE) (
LPVOID lpItem1,
LPVOID lpItem2,
LPARAM lParam); |
| Figure 5 Comparison Callback Function |
|
|
|
You also get to specify a dword value that will be passed
as the third parameter to your callback function.
The declarations for the sorting and searching functions
can be seen in Figure 6. The DPA_Sort function (ordinal |
|
|
|
|
338) is pretty straightforward. You
specify the array handle, your
callback function, and the value to
pass to the callback, and it will sort
the array using a Merge Sort algo-
rithm. The return value is TRUE if
the array was sorted successfully.
If it was unable to allocate the me-
mory required to perform the sort,
the function will return FALSE.
The DPA_Search function (or-
dinal 339) is a bit more compli-
cated. You specify the pointer that
you're searching for (it gets passed
as the first parameter to your
callback function), and the position
in the array at which you would like
the search to begin. The callback |
|
|
BOOL WINAPI DPA_Sort(
HDPA hArray,
LPFNDPACOMPARE lpfnCompare,
LPARAM lParam);
int WINAPI DPA_Search(
HDPA hArray,
LPVOID lpItem,
int nStartPos,
LPFNDPACOMPARE lpfnCompare,
LPARAM lParam,
DWORD dwFlags);
int WINAPI DPA_GetPtrIndex(
HDPA hArray,
LPVOID lpItem); |
| Figure 6 Sorting and Searching Functions |
|
|
|
| function and the callback value are the same as those used |
|
|
|
|
by DPA_Sort. The flags parameter determines
the method in which the array is searched (see
Figure 7).
Specifying the DPAF_LINEAR_SEARCH
flag, will cause the array to be searched
linearly, starting at the position specified in the
nStartPos parameter. To perform a binary |
|
|
| DPAF_LINEAR_SEARCH |
0x00 |
| DPAF_BINARY_SEARCH |
0x01 |
| DPAF_BINARY_INSERT |
0x07 |
| Figure 7 Search Flags |
|
|
|
search (obviously the array should already be sorted), you
would specify the DPAF_BINARY_SEARCH flag. With the
binary search, the nStartPos parameter is ignored.
In both cases, the function returns the position of the
first matching item, or -1 if the item could not be found.
When doing a binary search, though, you may wish to find
the position at which the item should be inserted if didn't
already exist in the array. In that case you should use the
DPAF_BINARY_INSERT flag.
There is another function, DPA_GetPtrIndex (ordinal
333), which has also been included in this section, although
it may seem a bit out of place. It doesn't use a comparison
function like DPA_Sort and DPA_Search - it just searches
linearly from the start of the array, looking for an exact
match with a pointer stored in the array. If there were no
exact matches, it will return -1. The function delcaration is
also listed in Figure 6. |
|
|
|
|
|
| Dynamic Structure Arrays |
|
Dynamic Structure Arrays provide the same basic functio-
nality as Dynamic Pointer Arrays. All necessary resizing of
the array is handled automatically as items are added and
removed. Unfortunately you don't have the equivalent sor-
ting and searching functionality and you don't have any
control of the heap that is used for the memory allocation
(that means you're going to be stuck with the shared heap
on Windows 95).
The advantage of the Structure Arrays, though, is that
the array elements can be of any size. You can now handle
arrays of structures, without the complication of storing
them as pointers and having to handle all the memory allo-
cation yourself. |
|
| The DSA Handle |
|
The DSA handle has the same basic elements as the DPA
handle, but not always at the same offsets. Each handle
also has one unique element. The DPA handle requires a
heap handle that Dynamic Structure Arrays don't need, and |
the DSA handle as an attribute for storing the size
of the array items which Dynamic Pointer Ar-
rays obviously don't need (see Figure 8 for the
structure definition).
As with the DPA handle, nItems specifies the
number of items in the array, and nCapacity spe-
cifies the maximum number of items that can be
placed in the array before new storage will have
to be allocated. nDelta specifies the amount by
which the array will grow whenever new storage |
|
|
typedef struct {
int nItems;
LPVOID lpItems;
int nCapacity;
int nItemSize;
int nDelta;
} * HDSA; |
| Figure 8 DSA Handle Structure |
|
|
|
is required. lpItems is a pointer to the memory where the
array items are stored and nItemSize specifies the byte size
of each item. |
|
|
|
|
|
| The DSA Functions |
|
|
HDSA WINAPI DSA_Create(
int nItemSize,
int nDelta);
BOOL WINAPI DSA_Destroy(
HDSA hArray); |
| Figure 9 Creation and Destroy Functions |
|
|
|
Most of the DSA functions are pretty
much identical to their DPA counterparts
(the function declarations are listed in
Figures 9, 10, 11 & 12). You create and
destroy Dynamic Structure Arrays with
DSA_Create and DSA_Destroy (ordinals
320 and 321). The only difference bet-
ween the DSA_Create function and the |
|
| DPA_Create function is that the former now requires an |
|
|
|
|
extra parameter specifying the size of
the array items.
Storing items in a structure array is
accomplished with the DSA_InsertItem
function and the DSA_SetItem function
(ordinals 324 and 325). In each case, the
data pointed to by the lpItem parameter
is actually copied into the array (the cor-
responding DPA functions would only
store a pointer to the data). As with the
DPA_SetPtr function, trying to store an
item with DSA_SetItem beyond the end |
|
|
int WINAPI DSA_InsertItem(
HDSA hArray,
int nPosition,
LPVOID lpItem);
BOOL WINAPI DSA_SetItem(
HDSA hArray,
int nPosition,
LPVOID lpItem); |
| Figure 10 Functions for Storing |
|
|
|
| of the array will cause the array to be resized. |
|
|
|
|
Retrieving items is completely
different though. Your one option is
the DSA_GetItem function (ordinal
322), which will copy an item from
the array into a specified buffer. It
returns TRUE if successful, or FALSE
if the requested item was out of
range. The other option, DSA_Get-
ItemPtr (ordinal 323), will return a
pointer to the item in the actual array
buffer. The resulting pointer can |
|
|
BOOL WINAPI DSA_GetItem(
HDSA hArray,
int nPosition,
LPVOID lpBuffer);
LPVOID WINAPI DSA_GetItemPtr(
HDSA hArray,
int nPosition); |
| Figure 11 Functions for Retrieving |
|
|
|
| even be used to modify the item directly. Bare in mind, |
|
|
|
|
though, that any subsequent set or
insert operation could invalidate
that pointer.
The functions for deleting
items, DSA_DeleteItem and
DSA_DeleteAllItems (ordinals
326 and 327) are exactly the same
their DPA equivalents. This time,
though, you don't have to worry |
|
|
BOOL WINAPI DSA_DeleteItem(
HDSA hArray,
int nPosition);
BOOL WINAPI DSA_DeleteAllItems(
HDSA hArray); |
| Figure 12 Functions for Deleting |
|
|
|
| about pointers needing to released. |
|
|
|
|
|
| BACK TO HOME |