1 // Created on: 2001-06-26
2 // Created by: Alexander GRIGORIEV
3 // Copyright (c) 2001-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.
16 #include <LDOM_MemManager.hxx>
17 #include <LDOMBasicString.hxx>
20 IMPLEMENT_STANDARD_RTTIEXT(LDOM_MemManager,Standard_Transient)
23 #define MINIMAL_ROOM 3
25 typedef unsigned char LDOM_HashValue; // allocating HASH_MASK integer
27 inline Standard_Integer convertBlockSize (const Standard_Integer aBlockSize)
29 return ((aBlockSize - 1) / sizeof(Standard_Integer)) + 1;
32 inline Standard_Boolean compareStrings (char * const str,
33 const char * theString,
34 const Standard_Integer theLength)
36 // ** This is a bit dangerous (can override the boundary of allocated memory)
37 // return (str[theLength] == '\0' &&
38 // memcmp (str, theString, theLength) == 0);
39 // ** This is a more stable (less performant) solution
40 if (memcmp (str, theString, theLength)) return Standard_False;
41 return (str[theLength] == '\0');
44 //=======================================================================
45 //function : MemBlock::MemBlock
47 //=======================================================================
49 inline LDOM_MemManager::MemBlock::MemBlock (const Standard_Integer aSize,
50 LDOM_MemManager::MemBlock * aFirst)
51 : mySize (aSize), myNext (aFirst)
53 myFreeSpace = myBlock = new Standard_Integer [aSize];
54 myEndBlock = myBlock + aSize;
57 //=======================================================================
58 //function : MemBlock::Allocate
60 //=======================================================================
62 inline void * LDOM_MemManager::MemBlock::Allocate (const Standard_Integer aSize)
64 void * aResult = NULL;
65 if (aSize <= myEndBlock - myFreeSpace) {
66 aResult = myFreeSpace;
72 //=======================================================================
73 //function : MemBlock::AllocateAndCheck
75 //=======================================================================
77 void * LDOM_MemManager::MemBlock::AllocateAndCheck
78 (const Standard_Integer aSize,
79 const LDOM_MemManager::MemBlock *& aFirstWithoutRoom)
81 void * aResult = NULL;
82 Standard_Integer aRoom = (Standard_Integer)(myEndBlock - myFreeSpace);
84 aResult = myFreeSpace;
87 if (aRoom < MINIMAL_ROOM) {
88 if (aFirstWithoutRoom == NULL) aFirstWithoutRoom = this;
90 aFirstWithoutRoom = NULL;
94 //=======================================================================
95 //function : ~MemBlock
96 //purpose : Destructor
97 //=======================================================================
99 LDOM_MemManager::MemBlock::~MemBlock ()
102 MemBlock* aNext = myNext;
105 MemBlock* aNextNext = aNext->myNext;
112 //=======================================================================
113 //function : HashTable
114 //purpose : Constructor
115 //=======================================================================
117 LDOM_MemManager::HashTable::HashTable (/* const Standard_Integer aMask, */
118 LDOM_MemManager& aMemManager)
119 : myManager (aMemManager)
121 Standard_Integer m, nKeys = HASH_MASK + 1;
123 Standard_Integer m = aMask;
124 Standard_Integer nKeys = 1;
131 myTable = (TableItem *) myManager.Allocate (sizeof(TableItem) * nKeys);
132 for (m = 0; m < nKeys; m += 2) {
133 myTable[m].str = NULL;
134 myTable[m].next = NULL;
135 myTable[m+1].str = NULL;
136 myTable[m+1].next = NULL;
140 //=======================================================================
142 //purpose : CRC-16 hash function
143 //=======================================================================
145 Standard_Integer LDOM_MemManager::HashTable::Hash (const char * aString,
146 const Standard_Integer aLen)
148 static const unsigned int wCRC16a[16] =
150 0000000, 0140301, 0140601, 0000500,
151 0141401, 0001700, 0001200, 0141101,
152 0143001, 0003300, 0003600, 0143501,
153 0002400, 0142701, 0142201, 0002100,
156 static const unsigned int wCRC16b[16] =
158 0000000, 0146001, 0154001, 0012000,
159 0170001, 0036000, 0024000, 0162001,
160 0120001, 0066000, 0074000, 0132001,
161 0050000, 0116001, 0104001, 0043000,
164 unsigned int aCRC = 0;
165 const unsigned char * aPtr = (const unsigned char *) aString;
166 for (Standard_Integer i = aLen; i > 0; i--) {
167 const unsigned int bTmp = aCRC ^ (const unsigned int) (* aPtr++);
168 aCRC = ((aCRC >> 8) ^ wCRC16a[bTmp & 0x0F]) ^ wCRC16b[(bTmp >> 4) & 0x0F];
170 return Standard_Integer (aCRC & HASH_MASK /* myMask */);
173 //=======================================================================
174 //function : AddString
175 //purpose : Add or find a string in the hash table
176 //=======================================================================
178 const char * LDOM_MemManager::HashTable::AddString
179 (const char * theString,
180 const Standard_Integer theLen,
181 Standard_Integer& theHashIndex)
183 const char * aResult = NULL;
184 if (theString == NULL) return NULL;
185 Standard_Integer aHashIndex = Hash (theString, theLen);
186 TableItem * aNode = &myTable[aHashIndex];
187 if (aNode -> str == NULL) {
188 LDOM_HashValue * anAlloc = (LDOM_HashValue *)
189 myManager.Allocate (theLen + 1 + sizeof(LDOM_HashValue));
190 anAlloc[0] = LDOM_HashValue (aHashIndex);
191 aNode -> str = (char *) &anAlloc[1];
192 memcpy (aNode -> str, theString, theLen);
193 aNode -> str [theLen] = '\0';
194 aResult = aNode -> str;
196 if (compareStrings (aNode -> str, theString, theLen))
197 aResult = aNode -> str;
199 while (aNode -> next) {
200 aNode = aNode -> next;
201 if (compareStrings (aNode -> str, theString, theLen)) {
202 aResult = aNode -> str;
206 if (aResult == NULL) {
207 // Attention!!! We can make this allocation in a separate pool
208 // improving performance
209 aNode -> next = (TableItem *) myManager.Allocate (sizeof(TableItem));
210 aNode = aNode -> next;
211 LDOM_HashValue * anAlloc = (LDOM_HashValue *)
212 myManager.Allocate (theLen + 1 + sizeof(LDOM_HashValue));
213 anAlloc[0] = LDOM_HashValue (aHashIndex);
214 aNode -> str = (char *) &anAlloc[1];
215 memcpy (aNode -> str, theString, theLen);
216 aNode -> str [theLen] = '\0';
217 aResult = aNode -> str;
218 aNode -> next = NULL;
221 theHashIndex = aHashIndex;
225 //=======================================================================
226 //function : LDOM_MemManager
227 //purpose : Constructor
228 //=======================================================================
230 LDOM_MemManager::LDOM_MemManager (const Standard_Integer aBlockSize)
231 : myRootElement (NULL),
233 myFirstWithoutRoom (NULL),
234 myBlockSize (convertBlockSize(aBlockSize)),
235 myHashTable (NULL) {}
237 //=======================================================================
238 //function : ~LDOM_MemManager
239 //purpose : Destructor
240 //=======================================================================
242 LDOM_MemManager::~LDOM_MemManager ()
245 Standard_Integer aSomme = 0, aCount = 0;
246 MemBlock * aBlock = myFirstBlock;
247 //FILE * out = fopen ("/tmp/dump","w");
250 aSomme += aBlock -> mySize;
251 // for (const Standard_Integer * aPtr = aBlock -> myBlock;
252 // aPtr < aBlock -> myEndBlock; ) {
253 // const char * aStr = (const char *) aPtr;
254 // Standard_Integer aLen = strlen (aStr) + 1;
255 // if (aLen > 1) fprintf (out, "%s\n", aStr);
256 // aPtr += convertBlockSize (aLen);
258 aBlock = aBlock -> Next();
261 cout << ".. Destroying " << aCount << " LDOM memory allocations: "
262 << aSomme / 256 << " kB" << endl;
270 //=======================================================================
271 //function : Allocate
273 //=======================================================================
275 void * LDOM_MemManager::Allocate (const Standard_Integer theSize)
277 void * aResult = NULL;
278 Standard_Integer aSize = convertBlockSize (theSize);
280 if (aSize >= myBlockSize) {
281 myFirstBlock = new MemBlock (aSize, myFirstBlock);
282 aResult = myFirstBlock -> Allocate (aSize);
284 MemBlock * aBlock = myFirstBlock;
285 if (aBlock == NULL) {
286 myFirstBlock = new MemBlock (myBlockSize, myFirstBlock);
287 return myFirstBlock -> Allocate (aSize);
289 aResult = aBlock -> Allocate (aSize);
292 aBlock = aBlock -> Next();
293 const MemBlock * aFirstWithoutRoom = NULL;
294 while (aBlock != myFirstWithoutRoom) {
295 aResult = aBlock -> AllocateAndCheck (aSize, aFirstWithoutRoom);
297 aBlock = aBlock -> Next();
299 myFirstWithoutRoom = (MemBlock *&)aFirstWithoutRoom;
300 if (aResult == NULL) {
301 myFirstBlock = new MemBlock (myBlockSize, myFirstBlock);
302 aResult = myFirstBlock -> Allocate (aSize);
308 //=======================================================================
309 //function : HashedAllocate
310 //purpose : Memory allocation with access via hash table. No new allocation
311 // if already present
312 //=======================================================================
314 const char * LDOM_MemManager::HashedAllocate (const char * theString,
315 const Standard_Integer theLen,
316 Standard_Integer& theHash)
318 if (myHashTable == NULL) myHashTable = new HashTable (* this);
319 return myHashTable -> AddString (theString, theLen, theHash);
322 //=======================================================================
323 //function : HashedAllocate
324 //purpose : Memory allocation with access via hash table. No new allocation
325 // if already present
326 //=======================================================================
328 void LDOM_MemManager::HashedAllocate (const char * aString,
329 const Standard_Integer theLen,
330 LDOMBasicString& theResult)
332 theResult.myType = LDOMBasicString::LDOM_AsciiHashed;
333 Standard_Integer aDummy;
334 const char * aHashedString = HashedAllocate (aString, theLen, aDummy);
335 if (aHashedString != NULL)
336 theResult.myVal.ptr = (void *) aHashedString;
339 //=======================================================================
340 //function : CompareStrings
342 //=======================================================================
344 Standard_Boolean LDOM_MemManager::CompareStrings
345 (const char * theString,
346 const Standard_Integer theHashValue,
347 const char * theHashedStr)
349 if (((LDOM_HashValue *)theHashedStr)[-1] == LDOM_HashValue(theHashValue))
350 if (!strcmp (theString, theHashedStr))
351 return Standard_True;
352 return Standard_False;