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
  18 #include <TCollection.hxx>
  19
  20 // The array of prime numbers used as consequtive steps for
  21 // size of array of buckets in the map.
  22 // The prime numbers are used for array size with the hope that this will
  23 // lead to less probablility of having the same hash codes for
  24 // different map items (note that all hash codes are modulo that size).
  25 // The value of each next step is chosen to be ~2 times greater than previous.
  26 // Though this could be thought as too much, actually the amount of
  27 // memory overhead in that case is only ~15% as compared with total size of
  28 // all auxiliary data structures (each map node takes ~24 bytes),
  29 // and this proves to pay off in performance (see OCC13189).
  30 #define NB_PRIMES 12
  31 static const Standard_Integer Primes[NB_PRIMES+1] = {
  32      101,
  33     1009,
  34     2003,
  35     5003,
  36    10007,
  37    20011,
  38    37003,
  39    57037,
  40    65003,
  41   100019,
  42   209953,   // The following are Pierpont primes taken from Wikipedia [List of prime numbers]
  43   472393,
  44   995329
  45 };
  46
  47 Standard_Integer TCollection::NextPrimeForMap(const Standard_Integer N)
  48 {
  49   Standard_Integer i;
  50   for (i = 0; i < NB_PRIMES; i++)
  51     if (Primes[i] > N) break;
  52   return Primes[i];
  53 }