dbertoni 00/07/10 15:45:28
Modified: c/src/PlatformSupport ArenaAllocator.hpp ArenaBlock.hpp
ReusableArenaAllocator.hpp ReusableArenaBlock.hpp
Log:
Fixed some problems and added more comments.
Revision Changes Path
1.3 +32 -15 xml-xalan/c/src/PlatformSupport/ArenaAllocator.hpp
Index: ArenaAllocator.hpp
===================================================================
RCS file: /home/cvs/xml-xalan/c/src/PlatformSupport/ArenaAllocator.hpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- ArenaAllocator.hpp 2000/07/10 01:03:41 1.2
+++ ArenaAllocator.hpp 2000/07/10 22:45:28 1.3
@@ -97,8 +97,13 @@
typedef ArenaBlockType::size_type size_type;
- ArenaAllocator(size_type theBlockCount) :
- m_blockCount(theBlockCount),
+ /*
+ * Construct an instance that will allocate blocks of the specified
size.
+ *
+ * @param theBlockSize The block size.
+ */
+ ArenaAllocator(size_type theBlockSize) :
+ m_blockSize(theBlockSize),
m_blocks()
{
}
@@ -115,16 +120,26 @@
}
/*
- * Allocate a block of the appropriate size for an
- * object. Call commitAllocation() when after
- * the object is successfully constructed.
+ * Get size of an ArenaBlock, that is, the number
+ * of objects in each block.
*
- * @return A pointer to a block of memory
+ * @return The size of the block
+ */
+ size_type
+ getBlockSize() const
+ {
+ return m_blockSize;
+ }
+
+ /*
+ * Get the number of ArenaBlocks currently allocated.
+ *
+ * @return The number of blocks.
*/
size_type
getBlockCount() const
{
- return m_blockCount;
+ return m_blocks.size();
}
/*
@@ -134,14 +149,15 @@
*
* @return A pointer to a block of memory
*/
- ObjectType*
+ virtual ObjectType*
allocateBlock()
{
if (m_blocks.size() == 0 ||
m_blocks.back()->blockAvailable() == false)
{
- m_blocks.push_back(new ArenaBlockType(m_blockCount));
+ m_blocks.push_back(new ArenaBlockType(m_blockSize));
}
+ assert(m_blocks.size() > 0 && m_blocks.back() != 0 &&
m_blocks.back()->blockAvailable() == true);
return m_blocks.back()->allocateBlock();
}
@@ -150,14 +166,15 @@
* Commits the allocation of the previous
* allocateBlock() call.
*
- * @param A pointer to a block of memory
+ * @param theObject A pointer to a block of memory
*/
- void
- commitAllocation(ObjectType* theBlock)
+ virtual void
+ commitAllocation(ObjectType* theObject)
{
- assert(m_blocks.size() != 0);
+ assert(m_blocks.size() != 0 &&
m_blocks.back()->ownsBlock(theObject) == true);
- m_blocks.back()->commitAllocation(theBlock);
+ m_blocks.back()->commitAllocation(theObject);
+ assert(m_blocks.back()->ownsObject(theObject) == true);
}
protected:
@@ -171,7 +188,7 @@
ArenaBlockListType m_blocks;
- const size_type m_blockCount;
+ const size_type m_blockSize;
};
1.4 +113 -17 xml-xalan/c/src/PlatformSupport/ArenaBlock.hpp
Index: ArenaBlock.hpp
===================================================================
RCS file: /home/cvs/xml-xalan/c/src/PlatformSupport/ArenaBlock.hpp,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- ArenaBlock.hpp 2000/07/10 01:03:41 1.3
+++ ArenaBlock.hpp 2000/07/10 22:45:28 1.4
@@ -94,13 +94,19 @@
typedef AllocatorType::size_type size_type;
- ArenaBlock(size_type theBlockCount) :
+ /*
+ * Construct an ArenaBlock of the specified size
+ * of objects.
+ *
+ * @param theBlockSize The size of the block (the number of objects it
can contain).
+ */
+ ArenaBlock(size_type theBlockSize) :
m_objectCount(0),
- m_blockCount(theBlockCount),
+ m_blockSize(theBlockSize),
m_objectBlock(0),
m_allocator()
{
- assert(theBlockCount > 0);
+ assert(theBlockSize > 0);
}
~ArenaBlock()
@@ -118,18 +124,24 @@
m_allocator.deallocate(m_objectBlock, 0);
}
+ /*
+ * Allocate a block. Once the object is constructed, you must call
+ * commitAllocation().
+ *
+ * @return a pointer to the new block.
+ */
virtual ObjectType*
allocateBlock()
{
// If no memory has yet been allocated, then allocate it...
if (m_objectBlock == 0)
{
- m_objectBlock = m_allocator.allocate(m_blockCount, 0);
+ m_objectBlock = m_allocator.allocate(m_blockSize, 0);
}
assert(m_objectBlock != 0);
// Any space left?
- if (m_objectCount == m_blockCount)
+ if (m_objectCount == m_blockSize)
{
return 0;
}
@@ -139,9 +151,11 @@
}
}
- // $$$ ToDo: How much error checking, etc. do we do here? Is
- // it worth trying to throw exceptions when things are not
- // what they should be?
+ /*
+ * Commit the previous allocation.
+ *
+ * @param theBlock the address that was returned by allocateBlock()
+ */
virtual void
#if defined (NDEBUG)
commitAllocation(ObjectType* /* theBlock */)
@@ -150,30 +164,56 @@
#endif
{
assert(theBlock == m_objectBlock + m_objectCount);
- assert(m_objectCount < m_blockCount);
+ assert(m_objectCount < m_blockSize);
m_objectCount++;
}
+ /*
+ * Find out if there is a block available.
+ *
+ * @return true if one is available, false if not.
+ */
virtual bool
blockAvailable() const
{
- return m_objectCount < m_blockCount ? true : false;
+ return m_objectCount < m_blockSize ? true : false;
}
- size_type
+ /*
+ * Get the number of objects currently allocated in the
+ * block.
+ *
+ * @return The number of objects allocated.
+ */
+ virtual size_type
getCountAllocated() const
{
return m_objectCount;
}
+ /*
+ * Get the block size, that is, the number
+ * of objects in each block.
+ *
+ * @return The size of the block
+ */
size_type
- getBlockCount() const
+ getBlockSize() const
{
- return m_blockCount;
+ return m_blockSize;
}
- bool
+ /*
+ * Determine if this block owns the specified object. Note
+ * that even if the object address is within our block, this
+ * call will return false if no object currently occupies the
+ * block. See also ownsBlock().
+ *
+ * @param theObject the address of the object.
+ * @return true if we own the object, false if not.
+ */
+ virtual bool
ownsObject(const ObjectType* theObject) const
{
#if !defined(XALAN_NO_NAMESPACES)
@@ -195,26 +235,82 @@
}
}
+ /*
+ * Determine if this block owns the specified object block.
+ * Note that, unlike ownsObject(), there does not need to
+ * be an object at the address.
+ *
+ * @param theObject the address of the object
+ * @return true if we own the object block, false if not.
+ */
+ bool
+ ownsBlock(const ObjectType* theObject) const
+ {
+#if !defined(XALAN_NO_NAMESPACES)
+ using std::less;
+#endif
+
+ // Use less<>, since it's guaranteed to do pointer
+ // comparisons correctly...
+ less<const ObjectType*> functor;
+
+ if (functor(theObject, m_objectBlock) == false &&
+ functor(theObject, m_objectBlock + m_blockSize) == true)
+ {
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+ }
+
protected:
+ /*
+ * Determine if the block should be destroyed. Called by
+ * an instance of DeleteFunctor, this function is for
+ * deriving classes that might want to control the destruction
+ * of things.
+ *
+ * @param theObject the address of the object
+ * @return true if block should be destroyed, false if not.
+ */
virtual bool
shouldDestroyBlock(const ObjectType* /* theObject */) const
{
return true;
}
+ /*
+ * Determine the offset into the block for the given address.
+ * Behavior is undefined if the address is not within our
+ * block
+ *
+ * @param theObject the address of the object
+ * @return the offset
+ */
size_type
getBlockOffset(const ObjectType* theObject) const
{
- assert(ownsObject(theObject) == true);
+ assert(theObject - m_objectBlock < m_blockSize);
return theObject - m_objectBlock;
}
+ /*
+ * Determine the address within our block of the object
+ * at the specified offset.
+ * Behavior is undefined if the offset is greater than the
+ * block size.
+ *
+ * @param theObject the address of the object
+ * @return the offset
+ */
ObjectType*
getBlockAddress(size_type theOffset) const
{
- assert(ownsObject(m_objectBlock + theOffset) == true);
+ assert(theOffset < m_blockSize);
return m_objectBlock + theOffset;
}
@@ -262,7 +358,7 @@
// data members...
size_type m_objectCount;
- const size_type m_blockCount;
+ const size_type m_blockSize;
ObjectType* m_objectBlock;
1.5 +101 -10
xml-xalan/c/src/PlatformSupport/ReusableArenaAllocator.hpp
Index: ReusableArenaAllocator.hpp
===================================================================
RCS file:
/home/cvs/xml-xalan/c/src/PlatformSupport/ReusableArenaAllocator.hpp,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- ReusableArenaAllocator.hpp 2000/07/10 01:03:41 1.4
+++ ReusableArenaAllocator.hpp 2000/07/10 22:45:28 1.5
@@ -94,8 +94,14 @@
AllocatorType,
ReusableArenaBlockType>
BaseClassType;
- ReusableArenaAllocator(size_type theBlockCount) :
- BaseClassType(theBlockCount)
+ /*
+ * Construct an instance that will allocate blocks of the specified
size.
+ *
+ * @param theBlockSize The block size.
+ */
+ ReusableArenaAllocator(size_type theBlockSize) :
+ BaseClassType(theBlockSize),
+ m_lastBlockReferenced(0)
{
}
@@ -103,29 +109,114 @@
{
}
+ /*
+ * Destroy the object, and free the block for re-use.
+ *
+ * @param theObject the address of the object.
+ */
void
destroyObject(ObjectType* theObject)
{
assert(m_blocks.size() != 0);
- const ArenaBlockListType::iterator theEnd = m_blocks.end();
+ // Check this, just in case...
+ if (m_lastBlockReferenced != 0 &&
m_lastBlockReferenced->ownsObject(theObject) == true)
+ {
+ m_lastBlockReferenced->destroyObject(theObject);
+ }
+ else
+ {
+ // Search for the block that owns the object...
+ const ArenaBlockListType::reverse_iterator theEnd
= m_blocks.rend();
- ArenaBlockListType::iterator i = m_blocks.begin();
+ ArenaBlockListType::reverse_iterator i =
m_blocks.rbegin();
+
+ while(i != theEnd)
+ {
+ if ((*i)->ownsObject(theObject) == true)
+ {
+ m_lastBlockReferenced = *i;
+
+
m_lastBlockReferenced->destroyObject(theObject);
+
+ break;
+ }
+ else
+ {
+ ++i;
+ }
+ }
+ }
+ }
- while(i != theEnd)
+ /*
+ * Allocate a block of the appropriate size for an
+ * object. Call commitAllocation() when after
+ * the object is successfully constructed. You _must_
+ * commit an allocation before performing any other
+ * operation on the allocator.
+ *
+ * @return A pointer to a block of memory
+ */
+ virtual ObjectType*
+ allocateBlock()
+ {
+ if (m_lastBlockReferenced == 0 ||
+ m_lastBlockReferenced->blockAvailable() == false)
{
- if ((*i)->ownsObject(theObject) == true)
+ // Search back for a block with some space available...
+ ArenaBlockListType::reverse_iterator i =
m_blocks.rbegin();
+ const ArenaBlockListType::reverse_iterator theEnd
= m_blocks.rend();
+
+ while(i != theEnd)
{
- (*i)->destroyObject(theObject);
+ assert(*i != 0);
- break;
+ if (*i != m_lastBlockReferenced &&
(*i)->blockAvailable() == true)
+ {
+ // Ahh, found one with free space.
+ m_lastBlockReferenced = *i;
+
+ break;
+ }
+ else
+ {
+ ++i;
+ }
}
- else
+
+ if (i == theEnd)
{
- ++i;
+ // No blocks have free space available, so
create a new block, and
+ // push it on the list.
+ m_lastBlockReferenced = new
ReusableArenaBlockType(m_blockSize);
+
+ m_blocks.push_back(m_lastBlockReferenced);
}
}
+ assert(m_lastBlockReferenced != 0 &&
m_lastBlockReferenced->blockAvailable() == true);
+
+ return m_lastBlockReferenced->allocateBlock();
}
+
+ /*
+ * Commits the allocation of the previous
+ * allocateBlock() call.
+ *
+ * @param theObject A pointer to a block of memory
+ */
+ virtual void
+ commitAllocation(ObjectType* theObject)
+ {
+ assert(m_blocks.size() != 0 && m_lastBlockReferenced != 0 &&
m_lastBlockReferenced->ownsBlock(theObject) == true);
+
+ m_lastBlockReferenced->commitAllocation(theObject);
+ assert(m_lastBlockReferenced->ownsObject(theObject) == true);
+ }
+
+private:
+
+ ReusableArenaBlockType* m_lastBlockReferenced;
};
1.3 +127 -112 xml-xalan/c/src/PlatformSupport/ReusableArenaBlock.hpp
Index: ReusableArenaBlock.hpp
===================================================================
RCS file: /home/cvs/xml-xalan/c/src/PlatformSupport/ReusableArenaBlock.hpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- ReusableArenaBlock.hpp 2000/07/10 01:03:41 1.2
+++ ReusableArenaBlock.hpp 2000/07/10 22:45:28 1.3
@@ -64,98 +64,8 @@
#include <PlatformSupport/ArenaBlock.hpp>
-#if 0
-template<class ObjectType,
- class DestroyFunctionType = ArenaBlockDestroy<ObjectType> >
-class ReusableArenaBlockDestroy
-{
-public:
-
- ReusableArenaBlockDestroy() :
- m_freeListSet()
- {
- }
-
- void
- operator()(ObjectType& theObject) const
- {
- if (isOnFreeList(&theObject) == false)
- {
- m_destroyFunction(theObject);
- }
- }
-
- bool
- isOnFreeList(ObjectType* theObject) const
- {
- return m_freeListSet.find(theObject) == m_freeListSet.end() ?
false : true;
- }
-
- void
- destroyObject(ObjectType* theObject)
- {
- assert(theObject != 0);
-
- m_destroyFunction(*theObject);
-
- m_freeListSet.insert(theObject);
- }
-
- ObjectType*
- getNextFromFreeList()
- {
- assert(m_freeListSet.size() != 0);
-
- const FreeListSetType::const_iterator i =
m_freeListSet.begin();
-
- return *i;
- }
-
- bool
- removeFromFreeList(ObjectType* theObject)
- {
- assert(m_freeListSet.size() != 0);
-
- const FreeListSetType::iterator i =
- m_freeListSet.find(theObject);
-
- if (i == m_freeListSet.end())
- {
- return false;
- }
- else
- {
- m_freeListSet.erase(i);
-
- return true;
- }
- }
-
-#if defined(XALAN_NO_NAMESPACES)
- typedef set<ObjectType*> FreeListSetType;
-#else
- typedef std::set<ObjectType*> FreeListSetType;
-#endif
-
- FreeListSetType::size_type
- freeListSize() const
- {
- return m_freeListSet.size();
- }
-
-private:
-
- // Destroy function to call.
- DestroyFunctionType m_destroyFunction;
-
- // Bitmap which tracks which blocks are in use
- // that should not be destroyed.
- FreeListSetType m_freeListSet;
-};
-#endif
-
template<class ObjectType,
class DestroyFunctionType = ArenaBlockDestroy<ObjectType>,
#if defined(XALAN_NO_NAMESPACES)
@@ -173,10 +83,16 @@
DestroyFunctionType,
AllocatorType>
BaseClassType;
- ReusableArenaBlock(size_type theBlockCount) :
- BaseClassType(theBlockCount),
- m_freeList(theBlockCount),
- m_freeListSize(0)
+ /*
+ * Construct an ArenaBlock of the specified size
+ * of objects.
+ *
+ * @param theBlockSize The size of the block (the number of objects it
can contain).
+ */
+ ReusableArenaBlock(size_type theBlockSize) :
+ BaseClassType(theBlockSize),
+ m_freeList(theBlockSize),
+ m_freeBlockCount(0)
{
}
@@ -184,10 +100,16 @@
{
}
+ /*
+ * Allocate a block. Once the object is constructed, you must call
+ * commitAllocation().
+ *
+ * @return a pointer to the new block.
+ */
virtual ObjectType*
allocateBlock()
{
- if (m_freeListSize == 0)
+ if (m_freeBlockCount == 0)
{
return BaseClassType::allocateBlock();
}
@@ -197,14 +119,19 @@
}
}
+ /*
+ * Commit the previous allocation.
+ *
+ * @param theBlock the address that was returned by allocateBlock()
+ */
virtual void
commitAllocation(ObjectType* theBlock)
{
assert(theBlock != 0);
- assert(m_freeListSize == 0 ||
+ assert(m_freeBlockCount == 0 ||
theBlock == getNextFromFreeList());
- if (m_freeListSize == 0)
+ if (m_freeBlockCount == 0)
{
BaseClassType::commitAllocation(theBlock);
}
@@ -214,17 +141,55 @@
}
}
+ /*
+ * Find out if there is a block available.
+ *
+ * @return true if one is available, false if not.
+ */
virtual bool
blockAvailable() const
+ {
+ return m_freeBlockCount != 0 ? true :
BaseClassType::blockAvailable();
+ }
+
+ /*
+ * Get the number of objects currently allocated in the
+ * block.
+ *
+ * @return The number of objects allocated.
+ */
+ virtual size_type
+ getCountAllocated() const
+ {
+ return BaseClassType::getCountAllocated() - m_freeBlockCount;
+ }
+
+ /*
+ * Determine if this block owns the specified object. Note
+ * that even if the object address is within our block, this
+ * call will return false if no object currently occupies the
+ * block. See also ownsBlock().
+ *
+ * @param theObject the address of the object.
+ * @return true if we own the object, false if not.
+ */
+ virtual bool
+ ownsObject(const ObjectType* theObject) const
{
- return m_freeListSize != 0 ? true :
BaseClassType::blockAvailable();
+ return BaseClassType::ownsObject(theObject) &&
!isOnFreeList(theObject);
}
+ /*
+ * Destroy the object, and return the block to the free list.
+ * The behavior is undefined if the object pointed to is not
+ * owned by the block.
+ *
+ * @param theObject the address of the object.
+ */
void
destroyObject(ObjectType* theObject)
{
- assert(ownsObject(theObject) == true &&
- isOnFreeList(theObject) == false);
+ assert(ownsObject(theObject) == true);
m_destroyFunction(*theObject);
@@ -233,6 +198,15 @@
protected:
+ /*
+ * Determine if the block should be destroyed. Returns true,
+ * unless the object is on the free list. The behavior is
+ * undefined if the object pointed to is not owned by the
+ * block.
+ *
+ * @param theObject the address of the object
+ * @return true if block should be destroyed, false if not.
+ */
virtual bool
shouldDestroyBlock(const ObjectType* theObject) const
{
@@ -252,17 +226,39 @@
bool
operator==(const ReusableArenaBlock&) const;
+ /*
+ * Determine if the block is on the free list. The behavior is
+ * undefined if the object pointed to is not owned by the
+ * block.
+ *
+ * @param theObject the address of the object
+ * @return true if block is on the free list, false if not.
+ */
bool
isOnFreeList(const ObjectType* theObject) const
{
- assert(ownsObject(theObject) == true);
+ if (m_freeBlockCount == 0)
+ {
+ return false;
+ }
+ else
+ {
+ assert(ownsObject(theObject) == true);
- const size_type theOffset =
- getBlockOffset(theObject);
+ const size_type theOffset =
+ getBlockOffset(theObject);
- return m_freeList.isSet(theOffset);
+ return m_freeList.isSet(theOffset);
+ }
}
+ /*
+ * Add a block to the free list. The behavior is
+ * undefined if the object pointed to is not owned by the
+ * block.
+ *
+ * @param theObject the address of the object
+ */
void
addToFreeList(const ObjectType* theObject)
{
@@ -271,9 +267,16 @@
m_freeList.set(theOffset);
- ++m_freeListSize;
+ ++m_freeBlockCount;
}
+ /*
+ * Remove a block from the free list. The behavior is
+ * undefined if the object pointed to is not owned by the
+ * block.
+ *
+ * @param theObject the address of the object
+ */
void
removeFromFreeList(const ObjectType* theObject)
{
@@ -282,21 +285,32 @@
m_freeList.clear(theOffset);
- --m_freeListSize;
+ --m_freeBlockCount;
}
+ /*
+ * Get the next block from the free list. Returns 0 if
+ * the free list is empty.
+ *
+ * @return the address of the block
+ */
ObjectType*
getNextFromFreeList()
{
ObjectType* theResult = 0;
-
- const unsigned long theFreeListSize = m_freeList.getSize();
- for(unsigned long i = 0; i < theFreeListSize; ++i)
+ if (m_freeBlockCount > 0)
{
- if (m_freeList.isSet(i) == false)
+ const unsigned long theFreeListSize =
m_freeList.getSize();
+
+ for(unsigned long i = 0; i < theFreeListSize; ++i)
{
- theResult = getBlockAddress(i);
+ if (m_freeList.isSet(i) == true)
+ {
+ theResult = getBlockAddress(i);
+
+ break;
+ }
}
}
@@ -307,7 +321,8 @@
// and that should not be destroyed.
XalanBitmap m_freeList;
- unsigned long m_freeListSize;
+ // The number of blocks on the free list.)
+ unsigned long m_freeBlockCount;
};
