b311480e |
1 | // Created on: 1993-01-14 |
2 | // Created by: Remi LEQUETTE |
3 | // Copyright (c) 1993-1999 Matra Datavision |
973c2be1 |
4 | // Copyright (c) 1999-2014 OPEN CASCADE SAS |
b311480e |
5 | // |
973c2be1 |
6 | // This file is part of Open CASCADE Technology software library. |
b311480e |
7 | // |
d5f74e42 |
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 |
973c2be1 |
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. |
b311480e |
13 | // |
973c2be1 |
14 | // Alternatively, this file may be used under the terms of Open CASCADE |
15 | // commercial license or contractual agreement. |
7fd59977 |
16 | |
42cf5bc1 |
17 | |
18 | #include <TCollection.hxx> |
7fd59977 |
19 | |
20 | // The array of prime numbers used as consequtive steps for |
21 | // size of array of buckets in the map. |
7fd59977 |
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). |
7fd59977 |
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). |
7fd59977 |
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 | } |