/*! Sunrise Data Dictionary Library * * @brief a library for hashtable storage of arbitrary data objects * with built-in reference counting and guaranteed order iteration. * * @file dd_hashtable_size.c * calculate hashtable sizes * * @author Benjamin Kowarsch * * @note The author's true email address is herewith specifically excluded * from the license of this software. You are _not permitted_ to make the * author's true email address available to any third party. You may only * pass on the modified version of the email address as presented above. * * (C) 2006 Sunrise Telephone Systems Ltd. All rights reserved. * * @cond LICENSE_TERMS * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the "Software"), * to deal in the Software without restriction, including without limitation * the rights to use, copy, modify, merge, publish, distribute, sublicense, * and/or sell copies of the Software, and to permit persons to whom the * Software is furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice shall be included * in all copies or substantial portions of the Software. * * Under no circumstances is it permitted for any licensee to take credit for * the creation of the Software, to claim authorship or ownership in the * Software or in any other way give the impression that they have created * the Software. Credit to the true authors and copyright holders of the * Software is absolutely mandatory and must be given as follows: * * Software packages incorporating the Software or substantial portions of it * shall display a copyright notice for the Software in the same manner as * they display any other copyright notice; shall display an authorship * notice for the Software in the same manner as they display any other * authorship notice; and shall display the license terms or a reference to * the license terms of the Software in the same manner as they display any * other license or license reference. * * GUI-based or GUI-alike interactive installers installing the Software or * substantial portions of it, shall display the Software's copyright notice, * authorship notice and license terms in full during the installation * process. Other installers such as shell command driven package installers * on Unix systems shall display copyright, authorship and license in the * same manner as for any other software. Installers shall allow users to * install the license file for the Software along with the Software itself. * * Software which makes use of but does not incorporate, nor bundle, nor * install the Software or substantial portions of it, is NOT required to * display any copyright, authorship, license terms or license reference for * the Software. Static linking to the Software constitutes 'incorporating', * dynamic linking to the Software constitutes 'making use of' the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER * DEALINGS IN THE SOFTWARE. * * In countries and territories where the above no-warranty disclaimer is * not permissible by applicable law, the following terms apply: * * NO PERMISSION TO USE THE SOFTWARE IS GRANTED AND THE SOFTWARE MUST NOT BE * USED AT ALL IN SUCH COUNTRIES AND TERRITORIES WHERE THE ABOVE NO-WARRANTY * DISCLAIMER IS NOT PERMISSIBLE AND INVALIDATED BY APPLICABLE LAW. HOWEVER, * THE COPYRIGHT HOLDERS HEREBY WAIVE THEIR RIGHT TO PURSUE OFFENDERS AS LONG * AS THEY OTHERWISE ABIDE BY THE TERMS OF THE LICENSE AS APPLICABLE FOR USE * OF THE SOFTWARE IN COUNTRIES AND TERRITORIES WHERE THE ABOVE NO-WARRANTY * DISCLAIMER IS PERMITTED BY APPLICABLE LAW. THIS WAIVER DOES NOT CONSTITUTE * A LICENSE TO USE THE SOFTWARE IN COUNTRIES AND TERRITORIES WHERE THE ABOVE * NO-WARRANTY DISCLAIMER IS NOT PERMISSIBLE AND INVALIDATED BY APPLICABLE * LAW. ANY LIABILITY OF ANY KIND IS CATEGORICALLY RULED OUT AT ALL TIMES. * * @endcond */ #include "dd_settings.pp" #include "dd_hashtable_size.h" // ========================================================================== // P R I V A T E D A T A // ========================================================================== // -------------------------------------------------------------------------- // private array: _dd_prime_table // -------------------------------------------------------------------------- // // An array of unsigned integers which holds the nearest prime numbers // greater than multiples of 256 in the range of 0 to 32768. static const cardinal _dd_prime_table[] = { // 0, 256, 512, 768, 1024, 1280, 1536, 1792, 2048, 2304, 257, 257, 521, 787, 1031, 1283, 1543, 1801, 2053, 2309, // 2560, 2816, 3072, 3328, 3584, 3840, 4096, 4352, 4608, 4864, 2579, 2819, 3079, 3329, 3593, 3847, 4099, 4357, 4621, 4871, // 5120, 5376, 5632, 5888, 6144, 6400, 6656, 6912, 7168, 7424, 5147, 5381, 5639, 5897, 6151, 6421, 6659, 6917, 7177, 7433, // 7680, 7936, 8192, 8448, 8704, 8960, 9216, 9472, 9728, 9984, 7681, 7937, 8209, 8461, 8707, 8963, 9221, 9473, 9733, 10007, // 10240, 10496, 10752, 11008, 11264, 11520, 11776, 12032, 12288, 12544, 10243, 10499, 10753, 11027, 11273, 11527, 11779, 12037, 12289, 12547, // 12800, 13056, 13312, 13568, 13824, 14080, 14336, 14592, 14848, 15104, 12809, 13063, 13313, 13577, 13829, 14081, 14341, 14593, 14851, 15107, // 15360, 15616, 15872, 16128, 16384, 16640, 16896, 17152, 17408, 17664, 15361, 15619, 15877, 16139, 16411, 16649, 16901, 17159, 17417, 17669, // 17920, 18176, 18432, 18688, 18944, 19200, 19456, 19712, 19968, 20224, 17921, 18181, 18433, 18691, 18947, 19207, 19457, 19717, 19973, 20231, // 20480, 20736, 20992, 21248, 21504, 21760, 22016, 22272, 22528, 22784, 20483, 20743, 21001, 21269, 21517, 21767, 22027, 22273, 22531, 22787, // 23040, 23296, 23552, 23808, 24064, 24320, 24576, 24832, 25088, 25344, 23041, 23297, 23557, 23813, 24071, 24329, 24593, 24841, 25097, 25349, // 25600, 25856, 26112, 26368, 26624, 26880, 27136, 27392, 27648, 27904, 25601, 25867, 26113, 26371, 26627, 26881, 27143, 27397, 27653, 27917, // 28160, 28416, 28672, 28928, 29184, 29440, 29696, 29952, 30208, 30464, 28163, 28429, 28687, 28933, 29191, 29443, 29717, 29959, 30211, 30469, // 30720, 30976, 31232, 31488, 31744, 32000, 32256, 32512, 32768 30727, 30977, 31237, 31489, 31751, 32003, 32257, 32531, 32771 } /* _prime_table */; static const cardinal _ATTR(unused) *_dd_smallest_prime_in_table = &_dd_prime_table[0]; static const cardinal *_dd_largest_prime_in_table = &_dd_prime_table[(sizeof(_dd_prime_table) / sizeof(cardinal)) - 1]; // ========================================================================== // P R I V A T E F U N C T I O N S // ========================================================================== inline static cardinal _dd_approximate_prime_256(cardinal num) _ATTR(_ai_, pure); inline static cardinal _dd_approximate_prime_32k(cardinal num) _ATTR(_ai_, pure); // -------------------------------------------------------------------------- // private function: _dd_approximate_prime_256(num) // -------------------------------------------------------------------------- // // Returns a prime number approximating determined as follows: // // value: 0-7 8-11 12-17 18-37 38-67 68-131 132-193 194-256 // prime: 7 11 17 37 67 131 193 257 inline static cardinal _dd_approximate_prime_256(cardinal num) { // binary decision tree - maximum three tests if (num < 38) { if (num < 12) { if (num < 8) return 7; else return 11; } else /* 13-37 */ { if (num < 18) return 17; else return 37; } // enf if } else /* 38-256 */ { if (num < 132) { if (num < 68) return 67; else return 131; } else /* 132-256 */ { if (num < 194) return 193; else return 257; } // end if } // end if } // end _dd_approximate_prime_256 // -------------------------------------------------------------------------- // private function: _dd_approximate_prime_32k(num) // -------------------------------------------------------------------------- // // Returns a prime number approximating . The prime number returned is // the nearest prime greater than 's nearest multiple of 256 in the // range of 0 to 32768. If is out of range, the largest prime for // the range is returned. inline static cardinal _dd_approximate_prime_32k(cardinal num) { if (num <= 32768) return _dd_prime_table[(num + 255) % 256]; else return *_dd_largest_prime_in_table; } // end _dd_approximate_prime_32k // ========================================================================== // P U B L I C F U N C T I O N I M P L E M E N T A T I O N S // ========================================================================== // -------------------------------------------------------------------------- // function: dd_hashtable_size_for_requested_minimum(value) // -------------------------------------------------------------------------- // // Calculates and returns the hashtable size for requested minimum value // . The size is determined by approximating to a prime // number greater than but near . // // If is less than 257, the size returned will be determined // according to the following table: // // value: 0-7 8-11 12-17 18-37 38-67 68-131 132-193 194-256 // size : 7 11 17 37 67 131 193 257 // // If is between 257 and 32767, the size returned will be the // nearest prime number greater than 's nearest multiple of 256. // // If is greater than 32767, the size returned will be 32771. inline cardinal dd_hashtable_size_for_requested_minimum(cardinal value) { if (value <= 257) return _dd_approximate_prime_256(value); else return _dd_approximate_prime_32k(value); } // end dd_hashtable_size_for_requested_minimum; // END OF FILE