Helper class to determine table resizing policy

hashset_sizing_policy.py

// This file is was adapted from the GNU ISO C++ Library, 
// by the 6.006 staff. If you're interested you can find a mirror
//  of the original file at https://goo.gl/dgO3KR

// 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, or (at your option) any later
// version.

// This library 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.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

import struct
import bisect

num_distinct_sizes_32_bit = 30
num_distinct_sizes_64_bit = 62
num_distinct_sizes = num_distinct_sizes_32_bit if struct.calcsize("P") * 8 == 32 else num_distinct_sizes_64_bit

sizes = [5, 11, 23, 47, 97, 199, 409, 823, 1741, 3469, 6949, 14033, 28411, 57557, 116731, 236897, 480881, 976369, 
	 1982627, 4026031, 8175383, 16601593, 33712729, 68460391, 139022417, 282312799, 573292817, 1164186217, 
	 2364114217, 4294967291, 8589934583, 17179869143, 34359738337, 68719476731, 137438953447, 274877906899,
	 549755813881, 1099511627689, 2199023255531, 4398046511093, 8796093022151, 17592186044399, 35184372088777,
	 70368744177643, 140737488355213, 281474976710597, 562949953421231, 1125899906842597, 2251799813685119, 
	 4503599627370449, 9007199254740881, 18014398509481951, 36028797018963913, 72057594037927931, 
	 144115188075855859, 288230376151711717, 576460752303423433, 1152921504606846883, 2305843009213693951, 
	 4611686018427387847, 9223372036854775783, 18446744073709551557]

def get_nearest_larger_size(n):
    i = bisect.bisect_right(sizes, n)
    if i != len(sizes): return sizes[i]
    else: raise ValueError

def get_nearest_smaller_size(n):
    i = bisect.bisect_left(sizes, n)
    if i: return sizes[i-1]
    else: raise ValueError