b311480e |
1 | // Created on: 2001-06-26 |
2 | // Created by: Alexander GRIGORIEV |
973c2be1 |
3 | // Copyright (c) 2001-2014 OPEN CASCADE SAS |
b311480e |
4 | // |
973c2be1 |
5 | // This file is part of Open CASCADE Technology software library. |
b311480e |
6 | // |
d5f74e42 |
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 |
973c2be1 |
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. |
b311480e |
12 | // |
973c2be1 |
13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. |
7fd59977 |
15 | |
16 | #include <LDOM_MemManager.hxx> |
17 | #include <LDOMBasicString.hxx> |
18 | |
19 | IMPLEMENT_STANDARD_HANDLE (LDOM_MemManager, MMgt_TShared) |
20 | IMPLEMENT_STANDARD_RTTIEXT (LDOM_MemManager, MMgt_TShared) |
21 | |
22 | #define HASH_MASK 255 |
23 | #define MINIMAL_ROOM 3 |
24 | |
25 | typedef unsigned char LDOM_HashValue; // allocating HASH_MASK integer |
26 | |
27 | inline Standard_Integer convertBlockSize (const Standard_Integer aBlockSize) |
28 | { |
29 | return ((aBlockSize - 1) / sizeof(Standard_Integer)) + 1; |
30 | } |
31 | |
32 | inline Standard_Boolean compareStrings (char * const str, |
33 | const char * theString, |
34 | const Standard_Integer theLength) |
35 | { |
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'); |
42 | } |
43 | |
44 | //======================================================================= |
45 | //function : MemBlock::MemBlock |
46 | //purpose : |
47 | //======================================================================= |
48 | |
49 | inline LDOM_MemManager::MemBlock::MemBlock (const Standard_Integer aSize, |
50 | LDOM_MemManager::MemBlock * aFirst) |
51 | : mySize (aSize), myNext (aFirst) |
52 | { |
53 | myFreeSpace = myBlock = new Standard_Integer [aSize]; |
54 | myEndBlock = myBlock + aSize; |
55 | } |
56 | |
57 | //======================================================================= |
58 | //function : MemBlock::Allocate |
59 | //purpose : |
60 | //======================================================================= |
61 | |
62 | inline void * LDOM_MemManager::MemBlock::Allocate (const Standard_Integer aSize) |
63 | { |
64 | void * aResult = NULL; |
65 | if (aSize <= myEndBlock - myFreeSpace) { |
66 | aResult = myFreeSpace; |
67 | myFreeSpace += aSize; |
68 | } |
69 | return aResult; |
70 | } |
71 | |
72 | //======================================================================= |
73 | //function : MemBlock::AllocateAndCheck |
74 | //purpose : |
75 | //======================================================================= |
76 | |
77 | void * LDOM_MemManager::MemBlock::AllocateAndCheck |
78 | (const Standard_Integer aSize, |
79 | const LDOM_MemManager::MemBlock *& aFirstWithoutRoom) |
80 | { |
81 | void * aResult = NULL; |
7dc9e047 |
82 | Standard_Integer aRoom = (Standard_Integer)(myEndBlock - myFreeSpace); |
7fd59977 |
83 | if (aSize <= aRoom) { |
84 | aResult = myFreeSpace; |
85 | myFreeSpace += aSize; |
86 | } |
87 | if (aRoom < MINIMAL_ROOM) { |
88 | if (aFirstWithoutRoom == NULL) aFirstWithoutRoom = this; |
89 | } else |
90 | aFirstWithoutRoom = NULL; |
91 | return aResult; |
92 | } |
93 | |
94 | //======================================================================= |
95 | //function : ~MemBlock |
96 | //purpose : Destructor |
97 | //======================================================================= |
98 | |
99 | LDOM_MemManager::MemBlock::~MemBlock () |
100 | { |
101 | delete [] myBlock; |
102 | delete myNext; |
103 | } |
104 | |
105 | //======================================================================= |
106 | //function : HashTable |
107 | //purpose : Constructor |
108 | //======================================================================= |
109 | |
110 | LDOM_MemManager::HashTable::HashTable (/* const Standard_Integer aMask, */ |
111 | LDOM_MemManager& aMemManager) |
112 | : myManager (aMemManager) |
113 | { |
114 | Standard_Integer m, nKeys = HASH_MASK + 1; |
115 | /* |
116 | Standard_Integer m = aMask; |
117 | Standard_Integer nKeys = 1; |
118 | while (m) { |
119 | nKeys *= 2; |
120 | m /= 2; |
121 | } |
122 | myMask = nKeys - 1; |
123 | */ |
124 | myTable = (TableItem *) myManager.Allocate (sizeof(TableItem) * nKeys); |
125 | for (m = 0; m < nKeys; m += 2) { |
126 | myTable[m].str = NULL; |
127 | myTable[m].next = NULL; |
128 | myTable[m+1].str = NULL; |
129 | myTable[m+1].next = NULL; |
130 | } |
131 | } |
132 | |
133 | //======================================================================= |
134 | //function : Hash |
135 | //purpose : CRC-16 hash function |
136 | //======================================================================= |
137 | |
138 | Standard_Integer LDOM_MemManager::HashTable::Hash (const char * aString, |
139 | const Standard_Integer aLen) |
140 | { |
141 | static const unsigned int wCRC16a[16] = |
142 | { |
143 | 0000000, 0140301, 0140601, 0000500, |
144 | 0141401, 0001700, 0001200, 0141101, |
145 | 0143001, 0003300, 0003600, 0143501, |
146 | 0002400, 0142701, 0142201, 0002100, |
147 | }; |
148 | |
149 | static const unsigned int wCRC16b[16] = |
150 | { |
151 | 0000000, 0146001, 0154001, 0012000, |
152 | 0170001, 0036000, 0024000, 0162001, |
153 | 0120001, 0066000, 0074000, 0132001, |
154 | 0050000, 0116001, 0104001, 0043000, |
155 | }; |
156 | |
157 | unsigned int aCRC = 0; |
158 | const unsigned char * aPtr = (const unsigned char *) aString; |
159 | for (Standard_Integer i = aLen; i > 0; i--) { |
160 | const unsigned int bTmp = aCRC ^ (const unsigned int) (* aPtr++); |
161 | aCRC = ((aCRC >> 8) ^ wCRC16a[bTmp & 0x0F]) ^ wCRC16b[(bTmp >> 4) & 0x0F]; |
162 | } |
163 | return Standard_Integer (aCRC & HASH_MASK /* myMask */); |
164 | } |
165 | |
166 | //======================================================================= |
167 | //function : AddString |
168 | //purpose : Add or find a string in the hash table |
169 | //======================================================================= |
170 | |
171 | const char * LDOM_MemManager::HashTable::AddString |
172 | (const char * theString, |
173 | const Standard_Integer theLen, |
174 | Standard_Integer& theHashIndex) |
175 | { |
176 | const char * aResult = NULL; |
177 | if (theString == NULL) return NULL; |
178 | Standard_Integer aHashIndex = Hash (theString, theLen); |
179 | TableItem * aNode = &myTable[aHashIndex]; |
180 | if (aNode -> str == NULL) { |
181 | LDOM_HashValue * anAlloc = (LDOM_HashValue *) |
182 | myManager.Allocate (theLen + 1 + sizeof(LDOM_HashValue)); |
183 | anAlloc[0] = LDOM_HashValue (aHashIndex); |
184 | aNode -> str = (char *) &anAlloc[1]; |
185 | memcpy (aNode -> str, theString, theLen); |
186 | aNode -> str [theLen] = '\0'; |
187 | aResult = aNode -> str; |
188 | }else{ |
189 | if (compareStrings (aNode -> str, theString, theLen)) |
190 | aResult = aNode -> str; |
191 | else |
192 | while (aNode -> next) { |
193 | aNode = aNode -> next; |
194 | if (compareStrings (aNode -> str, theString, theLen)) { |
195 | aResult = aNode -> str; |
196 | break; |
197 | } |
198 | } |
199 | if (aResult == NULL) { |
200 | // Attention!!! We can make this allocation in a separate pool |
201 | // improving performance |
202 | aNode -> next = (TableItem *) myManager.Allocate (sizeof(TableItem)); |
203 | aNode = aNode -> next; |
204 | LDOM_HashValue * anAlloc = (LDOM_HashValue *) |
205 | myManager.Allocate (theLen + 1 + sizeof(LDOM_HashValue)); |
206 | anAlloc[0] = LDOM_HashValue (aHashIndex); |
207 | aNode -> str = (char *) &anAlloc[1]; |
208 | memcpy (aNode -> str, theString, theLen); |
209 | aNode -> str [theLen] = '\0'; |
210 | aResult = aNode -> str; |
211 | aNode -> next = NULL; |
212 | } |
213 | } |
214 | theHashIndex = aHashIndex; |
215 | return aResult; |
216 | } |
217 | |
218 | //======================================================================= |
219 | //function : LDOM_MemManager |
220 | //purpose : Constructor |
221 | //======================================================================= |
222 | |
223 | LDOM_MemManager::LDOM_MemManager (const Standard_Integer aBlockSize) |
224 | : myRootElement (NULL), |
225 | myFirstBlock (NULL), |
226 | myFirstWithoutRoom (NULL), |
227 | myBlockSize (convertBlockSize(aBlockSize)), |
228 | myHashTable (NULL) {} |
229 | |
230 | //======================================================================= |
231 | //function : ~LDOM_MemManager |
232 | //purpose : Destructor |
233 | //======================================================================= |
234 | |
235 | LDOM_MemManager::~LDOM_MemManager () |
236 | { |
0797d9d3 |
237 | #ifdef OCCT_DEBUG |
7fd59977 |
238 | Standard_Integer aSomme = 0, aCount = 0; |
239 | MemBlock * aBlock = myFirstBlock; |
240 | //FILE * out = fopen ("/tmp/dump","w"); |
241 | while (aBlock) { |
242 | aCount ++; |
243 | aSomme += aBlock -> mySize; |
244 | // for (const Standard_Integer * aPtr = aBlock -> myBlock; |
245 | // aPtr < aBlock -> myEndBlock; ) { |
246 | // const char * aStr = (const char *) aPtr; |
247 | // Standard_Integer aLen = strlen (aStr) + 1; |
248 | // if (aLen > 1) fprintf (out, "%s\n", aStr); |
249 | // aPtr += convertBlockSize (aLen); |
250 | // } |
251 | aBlock = aBlock -> Next(); |
252 | } |
253 | if (aCount > 1) |
254 | cout << ".. Destroying " << aCount << " LDOM memory allocations: " |
255 | << aSomme / 256 << " kB" << endl; |
256 | //fclose (out); |
257 | #endif |
258 | delete myFirstBlock; |
259 | if (myHashTable) |
260 | delete myHashTable; |
261 | } |
262 | |
263 | //======================================================================= |
264 | //function : Allocate |
265 | //purpose : |
266 | //======================================================================= |
267 | |
268 | void * LDOM_MemManager::Allocate (const Standard_Integer theSize) |
269 | { |
270 | void * aResult = NULL; |
271 | Standard_Integer aSize = convertBlockSize (theSize); |
272 | |
273 | if (aSize >= myBlockSize) { |
274 | myFirstBlock = new MemBlock (aSize, myFirstBlock); |
275 | aResult = myFirstBlock -> Allocate (aSize); |
276 | }else{ |
277 | MemBlock * aBlock = myFirstBlock; |
278 | if (aBlock == NULL) { |
279 | myFirstBlock = new MemBlock (myBlockSize, myFirstBlock); |
280 | return myFirstBlock -> Allocate (aSize); |
281 | } |
282 | aResult = aBlock -> Allocate (aSize); |
283 | if (aResult) |
284 | return aResult; |
285 | aBlock = aBlock -> Next(); |
286 | const MemBlock * aFirstWithoutRoom = NULL; |
287 | while (aBlock != myFirstWithoutRoom) { |
288 | aResult = aBlock -> AllocateAndCheck (aSize, aFirstWithoutRoom); |
289 | if (aResult) break; |
290 | aBlock = aBlock -> Next(); |
291 | } |
292 | myFirstWithoutRoom = (MemBlock *&)aFirstWithoutRoom; |
293 | if (aResult == NULL) { |
294 | myFirstBlock = new MemBlock (myBlockSize, myFirstBlock); |
295 | aResult = myFirstBlock -> Allocate (aSize); |
296 | } |
297 | } |
298 | return aResult; |
299 | } |
300 | |
301 | //======================================================================= |
302 | //function : HashedAllocate |
303 | //purpose : Memory allocation with access via hash table. No new allocation |
304 | // if already present |
305 | //======================================================================= |
306 | |
307 | const char * LDOM_MemManager::HashedAllocate (const char * theString, |
308 | const Standard_Integer theLen, |
309 | Standard_Integer& theHash) |
310 | { |
311 | if (myHashTable == NULL) myHashTable = new HashTable (* this); |
312 | return myHashTable -> AddString (theString, theLen, theHash); |
313 | } |
314 | |
315 | //======================================================================= |
316 | //function : HashedAllocate |
317 | //purpose : Memory allocation with access via hash table. No new allocation |
318 | // if already present |
319 | //======================================================================= |
320 | |
321 | void LDOM_MemManager::HashedAllocate (const char * aString, |
322 | const Standard_Integer theLen, |
323 | LDOMBasicString& theResult) |
324 | { |
325 | theResult.myType = LDOMBasicString::LDOM_AsciiHashed; |
326 | Standard_Integer aDummy; |
327 | const char * aHashedString = HashedAllocate (aString, theLen, aDummy); |
328 | if (aHashedString != NULL) |
329 | theResult.myVal.ptr = (void *) aHashedString; |
330 | } |
331 | |
332 | //======================================================================= |
333 | //function : CompareStrings |
334 | //purpose : Compare |
335 | //======================================================================= |
336 | |
337 | Standard_Boolean LDOM_MemManager::CompareStrings |
338 | (const char * theString, |
339 | const Standard_Integer theHashValue, |
340 | const char * theHashedStr) |
341 | { |
342 | if (((LDOM_HashValue *)theHashedStr)[-1] == LDOM_HashValue(theHashValue)) |
343 | if (!strcmp (theString, theHashedStr)) |
344 | return Standard_True; |
345 | return Standard_False; |
346 | } |