Utility Modules

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

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.

Hash Table

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.

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.

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.

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().

Go to the first, previous, next, last section, table of contents.