13. Utility Modules

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

13.1 CRC Functions
13.2 Hash Table
13.3 Lookaside List
13.4 Marks
13.5 Page Allocation

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

- unsigned long gm_crc (void *ptr, unsigned long len)

computes a CRC-32 of the indicated range of memory.

- unsigned long gm_crc_str (char *ptr)

computes a CRC-32 for the indicated string.

13.2 Hash Table

13.2.1 Introduction
13.2.2 Hash Table API

13.2.1 Introduction

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.

13.2.2 Hash Table API

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

- struct gm_hash * gm_create_hash (long (*gm_client_compare) (void *key1, void *key2), gm_u32_t (*gm_client_hash) (void *key1), unsigned long key_len, unsigned long data_len, unsigned long min_cnt, int flags)

returns a newly-created gm_hash structure or 0 if the hash table could not be created. The parameters are as follows:

gm_client_compare

the function used to compare keys and may be any of

gm_hash_compare_ints

gm_hash_compare_longs

gm_hash_compare_ptrs

gm_hash_compare_strings

or may be a client-defined function.

gm_client_hash

the function to be used to hash keys and may be any of

gm_hash_hash_int

gm_hash_hash_long

gm_hash_hash_ptr

gm_hash_hash_string

or may be a client-defined function.

key_len

specifies the length of the keys to be used for the hash table, or 0 if the keys should not be copied into GM-managed buffers.

data_len

specifies the length of the data to be stored in the hash table, or 0 if the data should not be copied into GM-managed buffers.

min_cnt

specifies the number of entries for which storage should be preallocated.

flags

should be 0 because no flags are currently defined.

- void gm_destroy_hash (struct gm_hash *h)

frees all resources associated with the hash table, except for any client-allocated buffers.

- void gm_hash_rekey (struct gm_hash *hash, void *old_key, void *new_key)

finds each entry with key old_key and changes the key used to store the data to new_key. This call is guaranteed to succeed.

- void * gm_hash_remove (struct gm_hash *hash, void *key)

removes an entry associated with key from the hash table hash and returns a pointer to the data associated with the key, or 0 if no match exists. If the data resides in a GM-managed buffer, it is only guaranteed to be valid until the next operation on the hash table.

- void * gm_hash_find (struct gm_hash *hash, void *key_ptr)

finds an entry associated with key from the hash table hash and returns a pointer to the data associated with the key, or 0 if no match exists.

- gm_status_t gm_hash_insert (struct gm_hash *hash, void *key, void *data)

stores the association of key and data in the hash table hash. The key *key (or data *data) is copied into the hash table unless the table was initialized with a key_len (or data_len) of 0.

13.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:

- struct gm_lookaside * gm_create_lookaside (unsigned long entry_len, unsigned long min_entry_cnt)

returns a newly created lookaside list to be used to allocate blocks of entry_len bytes. min_entry_cnt entries are preallocated.

- void gm_destroy_lookaside (struct gm_lookaside *l)

frees a lookaside list and all associated resources, including any buffers currently allocated from the lookaside list.

- void * gm_lookaside_alloc (struct gm_lookaside *l)

returns a buffer of size entry_len specified when the entry list l was created, or 0 if the buffer could not be allocated.

- void gm_lookaside_free (void *ptr)

frees a block of memory previously allocated by a call to gm_lookaside_alloc(). The contents of the block of memory are guaranteed to be unchanged until the next operation is performed on the lookaside list.

13.4 Marks

13.4.1 Introduction to Marks

The GM "mark" API is new to 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. For example, they may be used to solve the following exercise:

Exercise for the Reader:

Given a mark set with preallocated storage for N marks and an uninitialized(3) block of memory large enough to hold an array of N elements and and array of N marks, write code to initialize the array, insert an element in the array, remove an element from the array, and test for presense of an element in the array, each in constant (bounded) time. No amortization of time is allowed.

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.

13.4.2 The Mark API

- gm_status_t gm_create_mark_set (struct gm_mark_set **set, unsigned long init_count)

Return a pointer to a new mark set at set with enough preallocated resources to support init_count. Return GM_SUCCESS on success. Requires time comperable to malloc().

- void gm_destroy_mark_set (struct gm_mark_set *set)

Free all resources associated with mark set *set. Requires time comperable to free().

- gm_status_t gm_mark (struct gm_mark_set *set, gm_mark_t *m)

Add *mark to set. Requires O(constant) time if the mark set has preallocated resources for the mark. Otherwise, requires O(constant) average time.

- int gm_mark_is_valid (struct gm_mark_set *set, gm_mark_t *m)

Return nonzero value if *mark is in set. Requires O(constant) time.

- void gm_unmark (struct gm_mark_set *set, gm_mark_t *m)

Remove *mark from set. Requires O(constant) time.

- void gm_unmark_all (struct gm_mark_set *set)

Remove all marks from set. Requires O(constant) time.

13.5 Page Allocation

The following GM API allows pages to be allocated and freed.

- void * gm_page_alloc ()

allocate a page-aligned buffer of length GM_PAGE_LEN.

- void gm_page_free (void *addr)

frees the page at addr previously allocated by gm_page_alloc().