Saf/Algo/Struct/HashTablePolicy.h

Go to the documentation of this file.

/*
    This file is part of Simple Application Framework (Saf) library.
    Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>

    This library is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published 
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Saf is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Simple Application Framework library. If not, 
    see <http://www.gnu.org/licenses/>.
*/

#ifndef SAF_ALGO_STRUCT_HASHTABLEPOLICY_H
#define SAF_ALGO_STRUCT_HASHTABLEPOLICY_H

#include "../../Type.h"
#include "../../Math/Range.h"
#include "../../Collection/Pair.h"
#include "../../OverflowException.h"
#include "../Selection/MinMax.h"
#include "../../Math/Calculus/Powers.h"

namespace Saf
{
    namespace Algo
    {        
        namespace Struct
        {
            namespace HashPolicy
            {
                class PowerOf2Policy
                {
                public:
                    Collection::Pair<bool,Size> ShouldResize(Size elements, Size buckets)
                    {
                        if (elements > buckets) // Maximum load factor is 1.0
                        {
                            return Collection::Pair<bool,Size>(true, NextBucketCount(buckets + 1));
                        }

                        return Collection::Pair<bool,Size>(false, 0);
                    }

                    Size BucketIndex(Size hash, Size buckets) const
                    {
                        return hash & (buckets - 1);
                    }

                    Size NextBucketCount(Size bucketHint) const
                    {
                        return Selection::Max(Size(32), Math::Calculus::RoundUpToPowerOf2(bucketHint));
                    }

                    Size OptimalBucketCount(Size bucketHint, Size elements) const
                    {
                        return NextBucketCount(Selection::Max(bucketHint, elements));
                    }
                };

                class SAF_DLL_EXPORT PrimePolicy
                {
                protected:
                    static Size ms_primes;
                    static Size ms_primeList[];

                public:
                    Collection::Pair<bool,Size> ShouldResize(Size elements, Size buckets) const
                    {
                        if (elements >= buckets) // Maximum load factor is 1.0
                        {
                            return Collection::Pair<bool,Size>(true, NextBucketCount(buckets + 1));
                        }

                        return Collection::Pair<bool,Size>(false, 0);
                    }

                    Size BucketIndex(Size hash, Size buckets) const
                    {
                        return hash % buckets;
                    }

                    Size NextBucketCount(Size bucketHint) const
                    {
                        Size *pid = Math::Range::LowerBound(ms_primeList, 
                            ms_primeList + ms_primes, bucketHint);
                        
                        if (pid == ms_primeList + ms_primes)
                        {
                            throw OverflowException(SAF_SOURCE_LOCATION, "Bucket count overflow.");
                        }

                        return *pid;
                    }

                    Size OptimalBucketCount(Size bucketHint, Size elements) const
                    {
                        return NextBucketCount(Selection::Max(bucketHint, elements));
                    }
                };
            }
        }
    }
}

#endif