Simple Application Framework  1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Saf/Algo/Struct/HashTablePolicy.h
Go to the documentation of this file.
00001 /*
00002     This file is part of Simple Application Framework (Saf) library.
00003     Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>
00004 
00005     This library is free software: you can redistribute it and/or modify
00006     it under the terms of the GNU General Public License as published 
00007     by the Free Software Foundation, either version 3 of the License, or
00008     (at your option) any later version.
00009 
00010     Saf is distributed in the hope that it will be useful,
00011     but WITHOUT ANY WARRANTY; without even the implied warranty of
00012     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013     GNU General Public License for more details.
00014 
00015     You should have received a copy of the GNU General Public License
00016     along with Simple Application Framework library. If not, 
00017     see <http://www.gnu.org/licenses/>.
00018 */
00019 
00028 #ifndef SAF_ALGO_STRUCT_HASHTABLEPOLICY_H
00029 #define SAF_ALGO_STRUCT_HASHTABLEPOLICY_H
00030 
00031 #include "../../Type.h"
00032 #include "../../Math/Range.h"
00033 #include "../../Collection/Pair.h"
00034 #include "../../OverflowException.h"
00035 #include "../Selection/MinMax.h"
00036 #include "../../Math/Calculus/Powers.h"
00037 
00038 namespace Saf
00039 {
00040     namespace Algo
00041     {        
00042         namespace Struct
00043         {
00057             namespace HashPolicy
00058             {
00063                 class PowerOf2Policy
00064                 {
00065                 public:
00075                     Collection::Pair<bool,Size> ShouldResize(Size elements, Size buckets)
00076                     {
00077                         if (elements > buckets) // Maximum load factor is 1.0
00078                         {
00079                             return Collection::Pair<bool,Size>(true, NextBucketCount(buckets + 1));
00080                         }
00081 
00082                         return Collection::Pair<bool,Size>(false, 0);
00083                     }
00084 
00086                     Size BucketIndex(Size hash, Size buckets) const
00087                     {
00088                         return hash & (buckets - 1);
00089                     }
00090 
00094                     Size NextBucketCount(Size bucketHint) const
00095                     {
00096                         return Selection::Max(Size(32), Math::Calculus::RoundUpToPowerOf2(bucketHint));
00097                     }
00098 
00102                     Size OptimalBucketCount(Size bucketHint, Size elements) const
00103                     {
00104                         return NextBucketCount(Selection::Max(bucketHint, elements));
00105                     }
00106                 };
00107 
00112                 class SAF_DLL_EXPORT PrimePolicy
00113                 {
00114                 protected:
00116                     static Size ms_primes;
00118                     static Size ms_primeList[];
00119 
00120                 public:
00130                     Collection::Pair<bool,Size> ShouldResize(Size elements, Size buckets) const
00131                     {
00132                         if (elements >= buckets) // Maximum load factor is 1.0
00133                         {
00134                             return Collection::Pair<bool,Size>(true, NextBucketCount(buckets + 1));
00135                         }
00136 
00137                         return Collection::Pair<bool,Size>(false, 0);
00138                     }
00139 
00141                     Size BucketIndex(Size hash, Size buckets) const
00142                     {
00143                         return hash % buckets;
00144                     }
00145 
00149                     Size NextBucketCount(Size bucketHint) const
00150                     {
00151                         Size *pid = Math::Range::LowerBound(ms_primeList, 
00152                             ms_primeList + ms_primes, bucketHint);
00153                         
00154                         if (pid == ms_primeList + ms_primes)
00155                         {
00156                             throw OverflowException(SAF_SOURCE_LOCATION, "Bucket count overflow.");
00157                         }
00158 
00159                         return *pid;
00160                     }
00161 
00165                     Size OptimalBucketCount(Size bucketHint, Size elements) const
00166                     {
00167                         return NextBucketCount(Selection::Max(bucketHint, elements));
00168                     }
00169                 };
00170             }
00171         }
00172     }
00173 }
00174 
00175 #endif