Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualL. Spiro

Posted 01 November 2012 - 04:12 PM

I mentioned that in the post but it was a bit hidden under a small wall of text.
I have underlined it for clarity.


Why unsigned char* over char*?

When working with strings, I use char. With data, unsigned char. The reason is for safety while using the >> operator.
With char, it will carry the sign bit, which is rarely desirable when working with raw binary data.


L. Spiro

#3L. Spiro

Posted 01 November 2012 - 04:08 PM

I mentioned that in the post but it was a bit hidden under a small wall of text.
I have underlined it for clarity.


L. Spiro

#2L. Spiro

Posted 01 November 2012 - 04:07 PM

I hit Quote instead of Edit. Please delete me.

#1L. Spiro

Posted 01 November 2012 - 04:06 PM

I will post some code with explanations that should answer all your questions and cover the tricky spots out for which you need to watch. This is taken from my CVector<> template, and the key parts are:
Allocating the list of elements (copying them to a new location)
Inserting items
Removing items
Destroying the whole list of items


There are also 2 helper functions:

LSVOID LSE_CALL				Construct( LSUINT32 _tIndex ) {
			new( &m_ptData[_tIndex] ) _tType;
		}

		LSVOID LSE_CALL				Destroy( LSUINT32 _tIndex ) {
			// This gives warning C4100 when this class is created with types that have no destructor,
			//	claiming _tIndex is unreferenced.
			// Erase this warning with some do-nothing code.
#ifdef LSE_VISUALSTUDIO
			static_cast<LSUINT32>(_tIndex);
#endif	// #ifdef LSE_VISUALSTUDIO
			m_ptData[_tIndex].~_tType();
		}

The array is stored as T * as was mentioned above, so I construct and destruct objects via that index.


The first function that would be called is the allocator:
/**
		 * Allocate a given number of elements.
		 * If the allocation is less than what there already is, items are removed.
		 *
		 * \param _ui32Total Number of elements to allocate.
		 * \return Returns true if there was enough memory to allocate the given amount of
		 *	objects.  If _ui32Total is 0, true is always returned.
		 */
		LSBOOL LSE_CALL							Allocate( LSUINT32 _ui32Total ) {
			// If allocating 0 bytes, just reset the list.
			if ( !_ui32Total ) {
				Reset();
				return true;
			}
			if ( Parent::m_tLen == _ui32Total ) { return; }	// Nothing to do.
			// Destroy items that are going to be removed.
			if ( Parent::m_tLen ) {
				for ( LSUINT32 I = Parent::m_tLen; --I >= _ui32Total; ) {
					Parent::Destroy( I );
				}
			}
			// Adjust the length.
			if ( Parent::m_tLen > _ui32Total ) {
				Parent::m_tLen = _ui32Total;
			}
			// Attempt to allocate.
			_tType * ptNew = reinterpret_cast<_tType *>(m_paOurAllocator->Alloc( _ui32Total * sizeof( _tType ) ));
			if ( !ptNew ) { return false; }
			// Construct and copy all the items in the newly allocated array.
			for ( LSUINT32 I = Parent::m_tLen; I--; ) {
				// Construct new.
				new( &ptNew[I] ) _tType;
				// Copy from old to new.
				ptNew[I] = Parent::m_ptData[I];
				// Destroy old.
				Parent::Destroy( I );
			}
			// Remove the old list.
			if ( Parent::m_ptData ) {
				m_paOurAllocator->Free( Parent::m_ptData );
			}
			// Success.
			Parent::m_ptData = ptNew;
			Parent::m_tAllocated = _ui32Total;
			return true;
		}

Special case #1: Handle allocating a size of 0 differently; it should just deallocate everything and free all memory. Otherwise you will attempt to allocate 0 bytes.
Here it is possible to allocate 6 objects when the list already contains more than 6 objects, so the first step is to destroy all the objects that are going to be deallocated.
Destroy them one-by-one from the end of the list.
Then I allocate with my own memory manager but you should use ::malloc(). Nothing in the new array is constructed yet so the next loop constructs the objects and copies from the old list to the new list via the = copy operator. Again one-by-one.
I am not handling exceptions here but you may want to do so.
Finally the old list is freed. You would use ::free().


The Reset() function frees all memory and sets the object back to its initial state. It can be called in the destructor for your vector-like class.
/**
		 * Reset the list completely.
		 */
		LSVOID LSE_CALL							Reset() {
			for ( LSUINT32 I = Parent::m_tLen; I--; ) {
				Parent::Destroy( I );
			}
			if ( Parent::m_ptData ) {
				m_paOurAllocator->Free( Parent::m_ptData );
				Parent::m_ptData = NULL;
			}
			Parent::m_tLen = Parent::m_tAllocated = 0;
		}
Very simple.


Inserting objects has a few special cases.
/**
		 * Insert an element.
		 *
		 * \param _tVal The item to insert.
		 * \param _ui32Index The index where the item is to be inserted.
		 * \return Returns false if memory could not be allocated.  In this case, the list is not modified.
		 */
		LSBOOL LSE_CALL							Insert( const _tType &_tVal, LSUINT32 _ui32Index ) {
			assert( _ui32Index <= Parent::m_tLen );
			// If inserting at the end, just push the item.
			if ( _ui32Index == Parent::m_tLen ) { return this->Push( _tVal ); }

			// Now we know we are inserting in the middle somewhere.
			if ( Parent::m_tLen == Parent::m_tAllocated ) {
				// Overflow checking.
				_tDataType tNewTotal = Parent::m_tAllocated + _uAllocSize;
				assert( tNewTotal > Parent::m_tAllocated );
				if ( !Allocate( tNewTotal ) ) { return false; }
			}

			// Move other items.
			// Since this is not a PoD handler, we cannot simply move memory.
			// The last item has not been constructed yet, so we cannot call its copy operator yet.
			this->Construct( Parent::m_tLen );
			// Move items up one-by-one.
			for ( LSUINT32 I = Parent::m_tLen; I > _ui32Index; --I ) {
				Parent::m_ptData[I] = Parent::m_ptData[I-1UL];
			}
			// No need to destroy/construct the item at the given location.  Its copy operator should handle freeing of
			//	its memory.
			Parent::m_ptData[_ui32Index] = _tVal;
			++Parent::m_tLen;
			return true;
		}
First a few basic checks, and then a possible allocation if needed. Then the important parts.
Special case #2: The last item will soon have an object copied into it, so it is constructed. Be careful not to overlook this.
Then objects are copied over one-by-one.
The object at the insertion point has already been constructed, so calling its copy operator is enough.


Finally, removing items follows.
/**
		 * Remove elements without reallocating.
		 *
		 * \param _ui32Index The start index of the items to be removed.
		 * \param _ui32Total The number of items to remove.
		 */
		LSVOID LSE_CALL							RemoveRangeNoDealloc( LSUINT32 _ui32Index, LSUINT32 _ui32Total ) {
			if ( _ui32Total == 0UL ) { return; }
			assert( _ui32Index < Parent::m_tLen );
			assert( _ui32Index + _ui32Total <= Parent::m_tLen );
			LSUINT32 ui32End = Parent::m_tLen - _ui32Total;
			
			// Copy items over it.
			// Since this is not a PoD handler, we cannot simply move memory.
			LSUINT32 ui32CopyEnd = Parent::m_tLen - _ui32Total;
			for ( LSUINT32 I = _ui32Index; I < ui32CopyEnd; ++I ) {
				Parent::m_ptData[I] = Parent::m_ptData[I+_ui32Total];
			}

			// Destroy the tail items that were moved down.
			for ( LSINT32 I = Parent::m_tLen; --I >= ui32End; ) {
				// Destruct the item.
				Parent::Destroy( I );
			}
			Parent::m_tLen = Parent::m_tLen - _ui32Total;
		}
Again we start with basic checks.
Then we move all the items down by whatever number is in _ui32Total using just the copy operator.
That leaves _ui32Total number of trailing duplicates at the end of the array, so a second loop destroys those items.
If you wanted to have a RemoveRange() function that resizes the list, it would just call this function internally and then call Allocate() with a new list size.


That is basically all there is too it. There are just a few places where you have to be careful to construct objects, and remember to keep the construction and destruction count the same for every object.
Once an object is constructed you can just use = operator to copy into it.
As was mentioned, you can’t just move memory, so you have to move each object one-by-one as shown here.

This should cover all the issues you will have with your own implementation.


L. Spiro


PARTNERS