Main Page | Modules | Directories | File List | Globals | Related Pages

XIII. Utility Modules

Some of GM's internal modules may be useful to GM developers, so their APIs are exposed. These modules include the following:

1. CRC Functions

GM provides the following functions, which compute 32-bit CRCs on the contents of memory. These functions are not guaranteed to perform any particular variant of the CRC-32, but these functions are useful for creating robust hashing functions.

2. Hash Table

GM implements a generic hash table with a flexible interface. This module can automatically manage storage of fixed-size keys and/or data, or can allow the client to manage storage for keys and/or data. It allows the client to specify arbitrary hashing and comparison functions.
For example, 
     hash = gm_create_hash (gm_hash_compare_strings, gm_hash_hash_string,
                            0, 0, 0, 0);
creates a hash table that uses null-terminated character string keys residing in client-managed storage, and returns pointers to data in client-managed storage. In this case, all pointers to hash keys and data passed by GM to the client will be the same as the pointers passed by the client to GM.

As another example, 

     hash = gm_create_hash (gm_hash_compare_ints, gm_hash_hash_int,
                            sizeof (int), sizeof (struct my_big_struct),
                            100, 0);
creates a hash table that uses ints as keys and returns pointers to copies of the inserted structures. All storage for the keys and data is automatically managed by the hash table. In this case, all pointers to hash keys and data passed by GM to the client will point to GM-managed buffers. This function also preallocates enough storage for 100 hash entries, guaranteeing that at least 100 key/data pairs can be inserted in the table if the hash table creation succeeds.

The automatic storage management option of GM not only is convenient, but also is extremely space efficient for keys and data no larger than a pointer, because when keys and data are no larger than a pointer, GM automatically stores them in the space reserved for the pointer to the key or data, rather than allocating a separate buffer.

Note that all keys and data buffers are referred to by pointers, not by value. This allows keys and data buffers of arbitrary size to be used. As a special (but common) case, however, one may wish to use pointers as keys directly, rather than use what they point to. In this special case, use the following initialization, and pass the keys (pointers) directly to the API, rather than the usual references to the keys. 

     hash = gm_create_hash (gm_hash_compare_ptrs, gm_hash_hash_ptr,
                            0, DATA_LEN, MIN_CNT, FLAGS);
While it is possible to specify a KEY_LEN of `sizeof (void *)' during initialization and treat pointer keys just like any other keys, the API above is more efficient, more convenient, and completely architecture independent.

Some day the GM hash table API may be extended, but the current API is as follows:

The parameters are as follows:

3. Lookaside List

GM implements a lookaside list, which may be used to manage small fixed-length blocks more efficiently than gm_malloc() and gm_free(). Lookaside lists can also be used to ensure that at least a minimum number of blocks are available for allocation at all times.
GM lookaside lists have the following API:

4. Marks

The GM "mark" API was introduced in GM-1.4. It allows the creation and destruction of mark sets, which allow mark addition, mark removal, and test for mark in mark set operations to be performed in constant time. Marks may be members of only one mark set at a time. Marks have the very unusual property that they need not be initialized before use.
All operations on marks are extremely efficient. Mark initialization requires zero time. Removing a mark from a mark set and testing for mark inclusion in a mark set take constant time. Addition of a mark to a mark set takes O(constant) time, assuming the marks set was created with support for a sufficient number of marks; otherwise, it requires O(constant) average time. Finally, creation and destruction of a mark set take time comperable to the time required for a single call to malloc() and free(), respectively.

Because marks need not be initialized before use, they can actually be used to determine if other objects have been initialized. This is done by putting a mark in the object, and adding the mark to a "mark set of marks in initialized objects" once the object has been initialized. This is similar to one common use of "magic numbers" for debugging purposes, except that it is immune to the possibility that the uninitialized magic number contained the magic number before initialization, so such marks can be used for non-debugging purposes. Therefore, marks can be used in ways that magic numbers cannot.

Marks have a nice set of properties that each mark in a mark set has a unique value and if this value is corrupted, then the mark is implicitly removed from the mark set. This makes marks useful for detecting memory corruption, and are less prone to false negatives than are magic numbers, which proliferate copies of a single value.

Finally, marks are location-dependent. This means that if a mark is copied, the copy will not be a member of the mark set.

The following APIs are provided:

5. Zones

These GM API routines manage an externally specified zone of memory. A zone is a chunk of memory starting and ending on page boundaries. The size and state of each area are encoded in a pair of bit-arrays. All allocated (or freed) areas are maximally aligned.
The following APIs are provided:

6. Mutexes

GM mutex routines have the following API:

7. Buffer Debugging

There are three API functions provided for buffer debugging:

Generated on Sat May 20 19:20:43 2006 for GM by  doxygen 1.4.4