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