0029302: Foundation Classes, NCollection - optimize iteration of indexed maps
[occt.git] / 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 consequtive 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 }