Login | Register   
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

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

Tired of managing collections by hand in your legacy Brew development? Then try using a more general approach, such as a vector or dictionary wrapped in a reusable Brew interface.


advertisement
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-<length + 1 ); result = Vector_GrowTo( pMe, newCapacity ); if ( result == SUCCESS ) { if ( index < pMe-<length ) { MEMMOVE( &pMe-<pElements[ index + 1 ], & pMe-<pElements[ index ], ( pMe-<length - index ) * sizeof( void *) ); pMe-<length++; } else { pMe-<length = index + 1; } pMe-<pElements[ index ] = pObject; } return result;

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



Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap