1 // Created on: 2013-11-12
2 // Created by: Maxim YAKUNIN (myn)
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
17 #ifndef NCollection_AccAllocator_HeaderFile
18 #define NCollection_AccAllocator_HeaderFile
20 #include <NCollection_BaseAllocator.hxx>
21 #include <NCollection_DataMap.hxx>
24 //! Class NCollection_AccAllocator - accumulating memory allocator. This
25 //! class allocates memory on request returning the pointer to the allocated
26 //! space. The allocation units are grouped in blocks requested from the
27 //! system as required. This memory is returned to the system when all
28 //! allocations in a block are freed.
30 //! By comparison with the standard new() and malloc() calls, this method is
31 //! faster and consumes very small additional memory to maintain the heap.
33 //! By comparison with NCollection_IncAllocator, this class requires some more
34 //! additional memory and a little more time for allocation and deallocation.
35 //! Memory overhead for NCollection_IncAllocator is 12 bytes per block;
36 //! average memory overhead for NCollection_AccAllocator is 28 bytes per block.
38 //! All pointers returned by Allocate() are aligned to 4 byte boundaries.
39 //! To define the size of memory blocks requested from the OS, use the
40 //! parameter of the constructor (measured in bytes).
42 class NCollection_AccAllocator : public NCollection_BaseAllocator
44 // --------- PUBLIC CONSTANTS ---------
46 //! Alignment of all allocated objects: 4 bytes
47 static const Standard_Size Align = 4;
49 //! Default block size
50 static const Standard_Size DefaultBlockSize = 24600;
52 //! Number of last blocks to check for free space
53 static const Standard_Integer MaxLookupBlocks = 16;
55 // ---------- PUBLIC METHODS ----------
58 Standard_EXPORT NCollection_AccAllocator(const size_t
59 theBlockSize = DefaultBlockSize);
62 Standard_EXPORT ~NCollection_AccAllocator();
64 //! Allocate memory with given size
65 Standard_EXPORT virtual void* Allocate (const size_t theSize) Standard_OVERRIDE;
67 //! Free a previously allocated memory;
68 //! memory is returned to the OS when all allocations in some block are freed
69 Standard_EXPORT virtual void Free (void* theAddress) Standard_OVERRIDE;
71 // --------- PROTECTED TYPES ---------
73 //! Size value aligned to a 4 byte boundary
76 Standard_Size myValue;
79 AlignedSize(const Standard_Size theValue)
80 : myValue((theValue + Align - 1) & ~(Align - 1)) {}
81 operator Standard_Size() const {return myValue;}
84 //! A pointer aligned to a 4 byte boundary
87 Standard_Byte* myValue;
90 AlignedPtr(const Standard_Address theValue)
91 : myValue((Standard_Byte*)((Standard_Size)theValue & ~(Align - 1))) {}
92 operator Standard_Address () const {return myValue;}
93 operator Standard_Byte* () const {return myValue;}
94 AlignedPtr operator -(const AlignedSize theValue) const
95 {return myValue - theValue;}
96 AlignedPtr operator +(const AlignedSize theValue) const
97 {return myValue + theValue;}
98 AlignedPtr operator -=(const AlignedSize theValue)
99 {return myValue -= theValue;}
100 AlignedPtr operator +=(const AlignedSize theValue)
101 {return myValue += theValue;}
104 //! A key for the map of blocks
105 struct Key {Standard_Size Value;};
111 static Standard_Integer HashCode(const Key theKey, const Standard_Integer theUpper)
112 { return theKey.Value % theUpper + 1; }
114 static Standard_Boolean IsEqual(const Key theOne, const Key theTwo)
115 { return theOne.Value == theTwo.Value; }
118 //! Descriptor of a block
121 Standard_Address address;
122 AlignedPtr allocStart;
124 Standard_Integer allocCount;
126 Block(const Standard_Address theAddress,
127 const Standard_Size theSize,
128 Block* thePrevBlock = 0L)
129 : address(theAddress), prevBlock(thePrevBlock), allocCount(0)
130 {SetFreeSize (theSize);}
132 void SetFreeSize(const Standard_Size theSize)
133 {allocStart = (Standard_Byte*)address + theSize;}
135 Standard_Size FreeSize() const
136 {return (Standard_Byte*)allocStart - (Standard_Byte*)address;}
138 AlignedPtr Allocate(const AlignedSize theSize)
139 {allocCount++; return allocStart -= theSize;}
144 Standard_Boolean IsEmpty() const
145 {return allocCount == 0;}
148 // --------- PROTECTED METHODS ---------
150 //! Calculate a key for the data map basing on the given address
151 inline Key getKey(const Standard_Address theAddress) const
153 Key aKey = {(Standard_Size)theAddress / myBlockSize};
157 //! Find a block that the given allocation unit belongs to
158 Standard_EXPORT Block* findBlock(const Standard_Address theAddress, Key& theKey);
160 //! Allocate a new block and return a pointer to it
161 Standard_EXPORT Block* allocateNewBlock(const Standard_Size theSize);
163 // --------- PROHIBITED METHODS ---------
165 NCollection_AccAllocator (const NCollection_AccAllocator&);
166 NCollection_AccAllocator& operator = (const NCollection_AccAllocator&);
168 // --------- PROTECTED DATA ---------
170 AlignedSize myBlockSize;
172 NCollection_DataMap<Key, Block, Hasher> myBlocks;
174 // Declaration of CASCADE RTTI
176 DEFINE_STANDARD_RTTIEXT(NCollection_AccAllocator,NCollection_BaseAllocator)
179 // Definition of HANDLE object using Standard_DefineHandle.hxx
180 DEFINE_STANDARD_HANDLE (NCollection_AccAllocator, NCollection_BaseAllocator)