The open source CFD toolbox
HashTableCore.C
Go to the documentation of this file.
1/*---------------------------------------------------------------------------*\
2 ========= |
3 \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4 \\ / O peration |
5 \\ / A nd | www.openfoam.com
6 \\/ M anipulation |
7-------------------------------------------------------------------------------
8 Copyright (C) 2011-2012 OpenFOAM Foundation
9 Copyright (C) 2017-2019 OpenCFD Ltd.
10-------------------------------------------------------------------------------
12 This file is part of OpenFOAM.
13
14 OpenFOAM is free software: you can redistribute it and/or modify it
15 under the terms of the GNU General Public License as published by
16 the Free Software Foundation, either version 3 of the License, or
17 (at your option) any later version.
18
19 OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
20 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
21 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
22 for more details.
23
24 You should have received a copy of the GNU General Public License
25 along with OpenFOAM. If not, see <http://www.gnu.org/licenses/>.
26
27\*---------------------------------------------------------------------------*/
28
29#include "HashTableCore.H"
30#include "uLabel.H"
31
32// * * * * * * * * * * * * * * Static Data Members * * * * * * * * * * * * * //
33
34namespace Foam
35{
37}
38
39// Approximately labelMax/4
40const Foam::label Foam::HashTableCore::maxTableSize(1L << (sizeof(label)*8-3));
41
42
43// * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * * //
44
45Foam::label Foam::HashTableCore::canonicalSize(const label requested_size)
46{
47 if (requested_size < 1)
48 {
49 return 0;
50 }
51 else if (requested_size >= maxTableSize)
52 {
53 return maxTableSize;
54 }
55
56 // Enforce power of two for fast modulus in hash index calculations.
57 // Use unsigned for these calculations.
58 //
59 // - The lower limit (8) is somewhat arbitrary, but if the hash table
60 // is too small, there will be many direct table collisions.
61 // - The upper limit (approx. labelMax/4) must be a power of two,
62 // need not be extremely large for hashing.
63
64 uLabel powerOfTwo = 8u; // lower-limit
65
66 const uLabel size = requested_size;
67 if (size <= powerOfTwo)
68 {
69 return powerOfTwo;
70 }
71
72 if (size & (size-1)) // <- Modulus of i^2
73 {
74 // Determine power-of-two. Brute-force is fast enough.
75 while (powerOfTwo < size)
76 {
77 powerOfTwo <<= 1;
78 }
79
80 return powerOfTwo;
81 }
82
83 return size;
84}
85
86
87// ************************************************************************* //
#define defineTypeNameAndDebug(Type, DebugSwitch)
Define the typeName and debug information.
Definition: className.H:121
Namespace for OpenFOAM.
Bits that are independent of HashTable template parameters.
Definition: HashTableCore.H:57
static const label maxTableSize
Maximum allowable internal table size. Approximately labelMax/4.
Definition: HashTableCore.H:59
static label canonicalSize(const label requested_size)
Return a canonical (power-of-two) of the requested size.
Definition: HashTableCore.C:45