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 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;
  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   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 {
 237 #ifdef DEB
 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 }