RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Back to Basics: Manage Collections with a Custom Dictionary : Page 4

Dictionaries are an essential data structure in many of today's programming environments. Use this one in your next Brew application.

Accessing an Item
Accessing an item in the hash can be done one of three ways:
  • Using IDICTIONARY_Get and passing a key to the item you seek.
  • Enumerating across all items using IDICTIONARY_EnumInit and IDICTIONARY_EnumNext.
  • Mapping a function to all elements or a subset of all elements using IDICTIONARY_Comprehend or IDICTIONARY_ForEach.
These are the same general operations you can perform on the vector component described previously, although with the dictionary there's one important distinction: there's no sort order imposed on elements using any of these methods. Elements are returned in the order they reside in the collection, which is a function of the hash function, the key for each item, and the number of items in the collection, as you can see from the insertion implementation.

The implementation of IDICTIONARY_Get deserves attention, because it's the basis for finding an element for deletion as well:

int Dictionary_Get( IDictionary *p, const char *szKey, void **ppObject )
  CDictionary *pMe = DICTIONARY_FROM_INTERFACE( p );
  uint32 index = 0;
  int result = EBADPARM;

  if ( !pMe || !szKey || !ppObject || STRLEN( szKey ) == 0 ) return result;

  *ppObject = NULL;
  result = Dictionary_FindIndex( pMe, szKey, &index );
  if ( result == SUCCESS )
    *ppObject = pMe->pElements[ index ].pValue;
  return result;
Aside from error checking, this doesn’t do much; it defers its real work to Dictionary_FindIndex, copying the result at the returned index into the pointer provided by the caller. Dictionary_FindIndex must hash the key, test the element at that key, and if it doesn't match, probe until it either finds the missing item or searches the entire collection (see Listing 6).

This code begins by computing the ideal location—the hash of the object modulo the number of items in the collection, and tests that element first. If it doesn't match, it walks to the end of the list, and wraps around searching for the desired element only if it doesn't find a match. Remember to check the hash values for equality first, but also check the equality of keys, in case the hash values collide!

Enumeration and mapping—also called completion, a concept taken from languages such as Haskell that provide a clear syntax for completing functions over lists—use a cursor and must check each node explicitly to see if it has an associated key. By testing against the key and not the item, users of the collection can differentiate between items that are not set, items that are set that have a NULL value, and those with a specific value (see Listing 7).

Initializing the enumerator consists of just setting the cursor to zero; each call to Dictionary_EnumNext returns the next key and value with a set key, incrementing the cursor one or more times as necessary until the next item in the collection has past.

The implementation of Dictionary_Comprehend works the same way, except that it also contains the enumeration loop directly.

Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date