Back to Basics: How to Manage Collections in Your Legacy Brew Applications

here’s something about sitting down to write a Brew application in C that makes me go back to basics: the very basics, like writing my own linked list each time instead of leveraging one of the hundreds of implementations I have laying around, or not re-using any of the data structures I’ve written for various projects. This is especially maddening when targeting the large number of legacy Brew handsets, because without things like IVectorModel, you end up worrying about your data collections instead of the algorithm you’re trying to implement.

In this article and the next, I’ll give you two popular collections, the vector and the dictionary, implemented as Brew interfaces that you can use in your applications. Both require nothing more than rudimentary Brew standard library calls, making them suitable for legacy handsets that are the vast majority of handsets in the hands of consumers today. Both support not just item insertion and access, but enumeration and mapping as well, giving you an additional layer of abstraction when working with your data. This month, I’ll focus on the vector, and next time I add the dictionary to the mix. You can download the implementation of these collections here.

Introducing the Vector
A vector, as I’m sure you know, is a data structure containing a group of elements that you access by an index. Unlike a traditional array in C, a vector implementation usually has two key features that make it more convenient to use:

  • They provide dynamic storage, resizing as needed when additional elements are inserted.
  • They provide bounds checking to prevent out-of-bounds access errors.

In addition, many vector implementations provide additional facilities, including:

  • The ability to insert an element at an arbitrary location, shifting elements down to accommodate the new element.
  • The ability to delete an element at an arbitrary location, shifting elements back to close the gap.
  • An enumerator to access each element of the vector in turn.

The vector presented here has all of these features, plus one idea borrowed from higher-level languages like Python and Haskell: list comprehensions. This vector implementation includes a ForEach method that lets you invoke a function for each element of the vector, as well as a Comprehend method that applies a test function to each element in turn, invoking a second function only on those items for which the test function returns true. Finally, the implementation lets you specify an item destructor for the vector’s contents, so that the vector is suitable for storing both pointers to data structures and interfaces.

This vector implementation stores its elements in an array allocated at runtime that periodically grows as additional items are inserted?specifically, you can specify an initial capacity and an increment to the capacity; once the vector is full it automatically increments its capacity by the size you specify, preserving its initial contents and reporting an error if the reallocation fails. It does not, however, shrink when items are removed; in my experience, most vectors go through a life cycle in which many items are initially added, then the vector is used for item access with little mutation to its contents for a prolonged period, and then the vector is released. As with many vector implementations, once an item is inserted in the vector, the vector owns the item; deleting or replacing an item results in the vector calling the destructor you supply to destroy any element at the location you indicate.

Obviously, this implementation poses trade-offs. If raw speed for item access is your primary goal, you may not want the overhead of function calls for item access or bounds checking. Similarly, its behavior is somewhat non-deterministic when adding or inserting elements, as you do not directly control its reallocation behavior. Finally, if memory is at a premium, the fact that the vector doesn’t shrink may be an issue. However, for many applications, a simple implementation such as this suffices.

The Vector Interface
As with other Brew components, I begin by declaring the component’s virtual table and interface. Even though I don’t make this class available as an extension, I use Brew’s component-oriented approach to keep my implementation modular and discrete from any specific applications (see Listing 1).

This should all be familiar to you if you’ve ever declared a Brew interface; I begin by specifying the interface (IVector), then the virtual table that the interface uses, with function pointers for each of the methods in the virtual table. Finally, I declare access methods for each of the elements of the virtual table, using Brew’s GET_PVTBL helper macro to perform the appropriate cross-casting and virtual table access.

Behind the scenes, a private data structure mirrors the interface structure and has additional fields for the vector’s private data members:

typedef struct CVector{  struct IVectorVtbl  *pvt;  uint32 nRefs;  void **pElements;  uint32 initial;  uint32 capacity;  uint32 increment;  uint32 length;  PFNFREE pfnDeallocator;  uint32 cursor;  IVectorVtbl vt;} CVector;#define VECTOR_FROM_INTERFACE( p )  ((CVector *)p)

I’ll explain each of these members as I use them. For now, it’s important that you understand that the private structure is cast-compatible with the interface, and that I allocate memory for the virtual table at the bottom of the private data structure.

Although the vector implements Brew’s component paradigm, it’s not a true component in that I don’t create an instance by calling ISHELL_CreateInstance. Instead, I call IVECTOR_New, which allocates enough space for the vector and initializes its private data (see Listing 2).

The only default value worth mentioning that this function introduces is the function pointer DefaultFree, which simply points to a static function that invokes Brew’s FREE on the pointer passed, and provides a default destructor for vectors that point to data on the heap. Note that IVECTOR_New doesn’t actually allocate the initial space used by the vector; this is a small optimization in case a vector is created but never used, and makes the resizing code a little simpler.

Inserting Items in the Vector
There are three ways to put something in the vector: by replacing an element’s value that’s already there (IVECTOR_ReplaceAt), by inserting an item into a specific location and shifting everything after it forward one (IVECTOR_InsertAt), and by adding an item at the end of the vector (which is really a special case of InsertAt, as you will soon see). In each case, the strategy is similar: see if there’s room for the element; if so, place the element; if not, grow the vector’s store of elements pElements and place the element. In the case of an insertion, placing the element is a little trickier, because I first need to move subsequent items to make room for the new item. Let’s take a look at the simplest case, IVECTOR_ReplaceAt:

static int Vector_ReplaceAt( IVector *p, uint32 index, void *pObject ){  CVector *pMe = VECTOR_FROM_INTERFACE( p );  uint32  newCapacity;  int result = SUCCESS;  if ( !pMe ) return EBADPARM;  newCapacity = MAX( index, pMe->length );  result = Vector_GrowTo( pMe, newCapacity );    if ( result == SUCCESS )  {    if ( pMe->pElements[ index ] ) (pMe->pfnDeallocator)( pMe->pElements[ index ] );    pMe->pElements[ index ] = pObject;    if ( index > pMe->length )       pMe->length = index;  }  return result;}

IVECTOR_ReplaceAt begins by determining if more space is necessary, by computing the new size of the vector (either the current length, or the new index if the new index is off the end of the current element store). If necessary?if the new size required is larger than the current capacity?the vector is resized. Once the size issue has been taken care of, any existing element at that location is freed using the vector element’s destructor function and the new element placed at the given location. Finally, if the new index is larger than the length of the vector, the vector’s length is updated; that lets you write code such as:

IVECTOR_ReplaceAt( vector, 0, STRDUP(“hello” ) );IVECTOR_ReplaceAt( vector, 4, STRDUP( “world” ) );

Results in a five-element vector whose first and last items point to the strings hello and world, respectively.

InsertAt is similar to ReplaceAt: first it resizes the vector if necessary, and then it inserts the item you provide at the index you specify, making room for the new item before placing it in the store:

static int Vector_InsertAt( IVector *p, uint32 index, void *pObject ){  CVector *pMe = VECTOR_FROM_INTERFACE( p );  uint32  newCapacity;  int result = SUCCESS;  if ( !pMe ) return EBADPARM;  newCapacity = MAX( index, pMe-

Adding an item on the end of the vector is the same as inserting it at the last item of the array:

static int Vector_Add( IVector *p, void *pObject ){  CVector *pMe = VECTOR_FROM_INTERFACE( p );  if ( !pMe ) return EBADPARM;  return Vector_InsertAt( p, pMe->length, pObject );}

The Vector_GrowTo function is a private function that simply determines if the array has sufficient capacity, and if it doesn't, creates a new array of elements and copies the existing elements to the new array before destroying the old array. If it's being invoked for the first time, it creates the amount required by the initial allocation, otherwise it increments the size appropriately. It uses several helper functions to demystify what we're doing (see Listing 3).

Deleting Elements
There are three ways to delete elements:

  • Replace an existing element with NULL by calling IVECTOR_ReplaceAt. This does not affect the position of any other item in the vector.
  • Delete an existing item by calling IVECTOR_Delete. This moves every item after the item you're deleting back one position after freeing the item you delete.
  • Delete all existing items by calling IVECTOR_DeleteAll, which releases each item in the vector and releases the vector's element store at pElements.
  • IVECTOR_Delete is the most interesting of the methods, as you see here:

    static int Vector_Delete( IVector *p, uint32 index ){  CVector *pMe = VECTOR_FROM_INTERFACE( p );  if ( !pMe ) return EBADPARM;  if ( index > pMe->length ) return ENOSUCH;  if ( pMe->pElements[ index ] ) (pMe->pfnDeallocator)( pMe->pElements[ index ] );MEMMOVE( &pMe->pElements[ index ], &pMe->pElements[ index + 1 ],                           ( pMe->length - index - 1 ) * sizeof( void * ) );  pMe->length--;  return SUCCESS;}

    The routine opens simply enough, validating the incoming index, and if invalid, returning an error. Next the code calls the registered deallocator on the indicated element. Once that's done, it uses MEMMOVE to slide each element after the deleted element down one, covering the deleted element. Finally, the length of the vector is decremented to reflect the change in indexes.

    I could implement IVECTOR_DeleteAll with successive calls to IVECTOR_Delete with an index of zero, but of course it's far more efficient to move the loop to within IVECTOR_DeleteAll and skip the MEMMOVE operation entirely:

    static int Vector_DeleteAll( IVector *p  ){  CVector *pMe = VECTOR_FROM_INTERFACE( p );  uint32 i;  if ( !pMe ) return EBADPARM;  for ( i  = 0; i < pMe->length;  i++ )  {    if ( pMe->pElements[ i ] ) (pMe->pfnDeallocator)(pMe->pElements[ i ] );  }  FREEIF( pMe->pElements );  pMe->capacity = 0;  pMe->length = 0;  return SUCCESS;}

    Accessing Elements
    There are three ways to access elements in the vector: one at a time using IVECTOR_Get, through the enumeration interface, or through the comprehension interface. As all boil down to a dereference of an element of pElement, let's look at IVECTOR_Get first:

    static int Vector_Get( IVector *p, uint32 index, void **ppObject ){  CVector *pMe = VECTOR_FROM_INTERFACE( p );  if ( !p  || !ppObject ) return EBADPARM;  if ( index < pMe->length )  {    *ppObject = pMe->pElements[ index ];    return SUCCESS;  }  else  {    return ENOSUCH;  }}

    This is straightforward: do some argument checking, validate the incoming index, and return either a pointer to the indexth item of the vector or an error on failure.

    The enumeration methods are trivial as well; I encourage you to look at the implementation if you can’t see how it would work. The IVECTOR_Comprehend method is a little trickier, because it uses a loop and a function pointer to determine what should happen to each element, and then a second function pointer to actually do something to the elements that meet the match criteria:

    static int Vector_Comprehend( IVector *p,                                                            PFNMAPITEMTEST pfnTestItem, PFNMAPITEM pfnEachItem, void *pCtx ){	CVector *pMe = VECTOR_FROM_INTERFACE( p );	uint32 cursor;	if ( !pMe ) return EFAILED;	if ( !pfnEachItem ) return EBADPARM;	for ( cursor = 0; cursor < pMe->length; cursor++ )	{		if ( !pfnTestItem || 		     (pfnTestItem)( pCtx, &cursor, pMe->pElements[ cursor ] ) )		{			(pfnEachItem)( pCtx, &cursor, pMe->pElements[ cursor ] );		}	}	return SUCCESS;}

    The code begins with the obligatory error checking, and then simply loops over each item in the vector. If there's no match function, the code assumes that the iteration should match each item in the vector; if there's a match function, the match function is invoked and the each function is invoked only if the match function returns true.

    It should be obvious?convince yourself if it isn't!?that you can write IVECTOR_ForEach in terms of IVECTOR_Comprehend. I do this in the header file, defining IVECTOR_ForEach with a NULL item test function.

    Versatility Means Freedom
    Brew's component oriented approach lends itself well to the construction of big components, such as media codecs or GUI widgets. It's just as useful, though, for the small things, like collections, that you're apt to just dash off again and again. Why not just write it once and use it over and over again?

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Overview

The Latest

your company's audio

4 Areas of Your Company Where Your Audio Really Matters

Your company probably relies on audio more than you realize. Whether you’re creating a spoken text message to a colleague or giving a speech, you want your audio to shine. Otherwise, you could cause avoidable friction points and potentially hurt your brand reputation. For example, let’s say you create a

chrome os developer mode

How to Turn on Chrome OS Developer Mode

Google’s Chrome OS is a popular operating system that is widely used on Chromebooks and other devices. While it is designed to be simple and user-friendly, there are times when users may want to access additional features and functionality. One way to do this is by turning on Chrome OS

homes in the real estate industry

Exploring the Latest Tech Trends Impacting the Real Estate Industry

The real estate industry is changing thanks to the newest technological advancements. These new developments — from blockchain and AI to virtual reality and 3D printing — are poised to change how we buy and sell homes. Real estate brokers, buyers, sellers, wholesale real estate professionals, fix and flippers, and beyond may