src/TCollection/TCollection.cxx

   1 // Created on: 1993-01-14
   2 // Created by: Remi LEQUETTE
   3 // Copyright (c) 1993-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 #include <TCollection.hxx>
  18
  19 #include <Standard_OutOfRange.hxx>
  20
  21 // The array of prime numbers used as consecutive steps for
  22 // size of array of buckets in the map.
  23 // The prime numbers are used for array size with the hope that this will
  24 // lead to less probablility of having the same hash codes for
  25 // different map items (note that all hash codes are modulo that size).
  26 // The value of each next step is chosen to be ~2 times greater than previous.
  27 // Though this could be thought as too much, actually the amount of
  28 // memory overhead in that case is only ~15% as compared with total size of
  29 // all auxiliary data structures (each map node takes ~24 bytes),
  30 // and this proves to pay off in performance (see OCC13189).
  31 #define THE_NB_PRIMES 24
  32 static const Standard_Integer THE_TCollection_Primes[THE_NB_PRIMES] =
  33 {
  34          101,
  35         1009,
  36         2003,
  37         5003,
  38        10007,
  39        20011,
  40        37003,
  41        57037,
  42        65003,
  43       100019,
  44       209953, // The following are Pierpont primes [List of prime numbers]
  45       472393,
  46       995329,
  47      2359297,
  48      4478977,
  49      9437185,
  50     17915905,
  51     35831809,
  52     71663617,
  53    150994945,
  54    301989889,
  55    573308929,
  56   1019215873,
  57   2038431745
  58 };
  59
  60 // =======================================================================
  61 // function : NextPrimeForMap
  62 // purpose  :
  63 // =======================================================================
  64 Standard_Integer TCollection::NextPrimeForMap(const Standard_Integer N)
  65 {
  66   for (Standard_Integer aPrimeIter = 0; aPrimeIter < THE_NB_PRIMES; ++aPrimeIter)
  67   {
  68     if (THE_TCollection_Primes[aPrimeIter] > N)
  69     {
  70       return THE_TCollection_Primes[aPrimeIter];
  71     }
  72   }
  73   throw Standard_OutOfRange ("TCollection::NextPrimeForMap() - requested too big size");
  74 }