src/LDOM/LDOM_MemManager.cxx

   1 // Created on: 2001-06-26
   2 // Created by: Alexander GRIGORIEV
   3 // Copyright (c) 2001-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   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.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #include <LDOM_MemManager.hxx>
  17 #include <LDOMBasicString.hxx>
  18
  19
  20 IMPLEMENT_STANDARD_RTTIEXT(LDOM_MemManager,Standard_Transient)
  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;
  82   Standard_Integer aRoom = (Standard_Integer)(myEndBlock - myFreeSpace);
  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   MemBlock* aNext = myNext;
 103   while (aNext)
 104   {
 105     MemBlock* aNextNext = aNext->myNext;
 106     aNext->myNext = 0;
 107     delete aNext;
 108     aNext = aNextNext;
 109   }
 110 }
 111
 112 //=======================================================================
 113 //function : HashTable
 114 //purpose  : Constructor
 115 //=======================================================================
 116
 117 LDOM_MemManager::HashTable::HashTable (/* const Standard_Integer   aMask, */
 118                                        LDOM_MemManager&         aMemManager)
 119      : myManager        (aMemManager)
 120 {
 121   Standard_Integer m, nKeys = HASH_MASK + 1;
 122 /*
 123   Standard_Integer m     = aMask;
 124   Standard_Integer nKeys = 1;
 125   while (m) {
 126     nKeys *= 2;
 127     m     /= 2;
 128   }
 129   myMask = nKeys - 1;
 130 */
 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;
 137   }
 138 }
 139
 140 //=======================================================================
 141 //function : Hash
 142 //purpose  : CRC-16 hash function
 143 //=======================================================================
 144
 145 Standard_Integer LDOM_MemManager::HashTable::Hash (const char * aString,
 146                                                    const Standard_Integer aLen)
 147 {
 148   static const unsigned int wCRC16a[16] =
 149   {
 150     0000000,    0140301,    0140601,    0000500,
 151     0141401,    0001700,    0001200,    0141101,
 152     0143001,    0003300,    0003600,    0143501,
 153     0002400,    0142701,    0142201,    0002100,
 154   };
 155
 156   static const unsigned int wCRC16b[16] =
 157   {
 158     0000000,    0146001,    0154001,    0012000,
 159     0170001,    0036000,    0024000,    0162001,
 160     0120001,    0066000,    0074000,    0132001,
 161     0050000,    0116001,    0104001,    0043000,
 162   };
 163
 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];
 169   }
 170   return Standard_Integer (aCRC & HASH_MASK /* myMask */);
 171 }
 172
 173 //=======================================================================
 174 //function : AddString
 175 //purpose  : Add or find a string in the hash table
 176 //=======================================================================
 177
 178 const char * LDOM_MemManager::HashTable::AddString
 179                                           (const char             * theString,
 180                                            const Standard_Integer theLen,
 181                                            Standard_Integer&      theHashIndex)
 182 {
 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;
 195   }else{
 196     if (compareStrings (aNode -> str, theString, theLen))
 197       aResult = aNode -> str;
 198     else
 199       while (aNode -> next) {
 200         aNode = aNode -> next;
 201         if (compareStrings (aNode -> str, theString, theLen)) {
 202           aResult = aNode -> str;
 203           break;
 204         }
 205       }
 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;
 219     }
 220   }
 221   theHashIndex = aHashIndex;
 222   return aResult;
 223 }
 224
 225 //=======================================================================
 226 //function : LDOM_MemManager
 227 //purpose  : Constructor
 228 //=======================================================================
 229
 230 LDOM_MemManager::LDOM_MemManager (const Standard_Integer aBlockSize)
 231      : myRootElement            (NULL),
 232        myFirstBlock             (NULL),
 233        myFirstWithoutRoom       (NULL),
 234        myBlockSize              (convertBlockSize(aBlockSize)),
 235        myHashTable              (NULL) {}
 236
 237 //=======================================================================
 238 //function : ~LDOM_MemManager
 239 //purpose  : Destructor
 240 //=======================================================================
 241
 242 LDOM_MemManager::~LDOM_MemManager ()
 243 {
 244 #ifdef OCCT_DEBUG
 245   Standard_Integer aSomme = 0, aCount = 0;
 246   MemBlock * aBlock = myFirstBlock;
 247 //FILE * out = fopen ("/tmp/dump","w");
 248   while (aBlock) {
 249     aCount ++;
 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);
 257 //    }
 258     aBlock = aBlock -> Next();
 259   }
 260   if (aCount > 1)
 261     cout << ".. Destroying " << aCount << " LDOM memory allocations: "
 262          << aSomme / 256 << " kB" << endl;
 263 //fclose (out);
 264 #endif
 265   delete myFirstBlock;
 266   if (myHashTable)
 267     delete myHashTable;
 268 }
 269
 270 //=======================================================================
 271 //function : Allocate
 272 //purpose  :
 273 //=======================================================================
 274
 275 void * LDOM_MemManager::Allocate (const Standard_Integer theSize)
 276 {
 277   void                  * aResult = NULL;
 278   Standard_Integer      aSize = convertBlockSize (theSize);
 279
 280   if (aSize >= myBlockSize) {
 281     myFirstBlock = new MemBlock (aSize, myFirstBlock);
 282     aResult = myFirstBlock -> Allocate (aSize);
 283   }else{
 284     MemBlock * aBlock = myFirstBlock;
 285     if (aBlock == NULL) {
 286       myFirstBlock = new MemBlock (myBlockSize, myFirstBlock);
 287       return myFirstBlock -> Allocate (aSize);
 288     }
 289     aResult = aBlock -> Allocate (aSize);
 290     if (aResult)
 291       return aResult;
 292     aBlock = aBlock -> Next();
 293     const MemBlock * aFirstWithoutRoom = NULL;
 294     while (aBlock != myFirstWithoutRoom) {
 295       aResult = aBlock -> AllocateAndCheck (aSize, aFirstWithoutRoom);
 296       if (aResult) break;
 297       aBlock = aBlock -> Next();
 298     }
 299     myFirstWithoutRoom = (MemBlock *&)aFirstWithoutRoom;
 300     if (aResult == NULL) {
 301       myFirstBlock = new MemBlock (myBlockSize, myFirstBlock);
 302       aResult = myFirstBlock -> Allocate (aSize);
 303     }
 304   }
 305   return aResult;
 306 }
 307
 308 //=======================================================================
 309 //function : HashedAllocate
 310 //purpose  : Memory allocation with access via hash table. No new allocation
 311 //           if already present
 312 //=======================================================================
 313
 314 const char * LDOM_MemManager::HashedAllocate (const char           * theString,
 315                                               const Standard_Integer theLen,
 316                                               Standard_Integer&      theHash)
 317 {
 318   if (myHashTable == NULL) myHashTable = new HashTable (* this);
 319   return myHashTable -> AddString (theString, theLen, theHash);
 320 }
 321
 322 //=======================================================================
 323 //function : HashedAllocate
 324 //purpose  : Memory allocation with access via hash table. No new allocation
 325 //           if already present
 326 //=======================================================================
 327
 328 void LDOM_MemManager::HashedAllocate         (const char             * aString,
 329                                               const Standard_Integer theLen,
 330                                               LDOMBasicString&       theResult)
 331 {
 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;
 337 }
 338
 339 //=======================================================================
 340 //function : CompareStrings
 341 //purpose  : Compare
 342 //=======================================================================
 343
 344 Standard_Boolean LDOM_MemManager::CompareStrings
 345                                         (const char             * theString,
 346                                          const Standard_Integer theHashValue,
 347                                          const char             * theHashedStr)
 348 {
 349   if (((LDOM_HashValue *)theHashedStr)[-1] == LDOM_HashValue(theHashValue))
 350     if (!strcmp (theString, theHashedStr))
 351       return Standard_True;
 352   return Standard_False;
 353 }