dovecot-1.2: primes_closest(): Use exponentially growing primes.
dovecot at dovecot.org
dovecot at dovecot.org
Mon Sep 1 15:17:13 EEST 2008
details: http://hg.dovecot.org/dovecot-1.2/rev/c55a66afddea
changeset: 8142:c55a66afddea
user: Timo Sirainen <tss at iki.fi>
date: Mon Sep 01 15:04:00 2008 +0300
description:
primes_closest(): Use exponentially growing primes.
diffstat:
3 files changed, 57 insertions(+), 39 deletions(-)
src/lib/hash.c | 2 -
src/lib/primes.c | 72 +++++++++++++++++++++++---------------------------
src/tests/test-lib.c | 22 +++++++++++++++
diffs (146 lines):
diff -r 5b845716308d -r c55a66afddea src/lib/hash.c
--- a/src/lib/hash.c Mon Sep 01 15:02:22 2008 +0300
+++ b/src/lib/hash.c Mon Sep 01 15:04:00 2008 +0300
@@ -8,7 +8,7 @@
#include <ctype.h>
-#define HASH_TABLE_MIN_SIZE 109
+#define HASH_TABLE_MIN_SIZE 131
struct hash_node {
struct hash_node *next;
diff -r 5b845716308d -r c55a66afddea src/lib/primes.c
--- a/src/lib/primes.c Mon Sep 01 15:02:22 2008 +0300
+++ b/src/lib/primes.c Mon Sep 01 15:04:00 2008 +0300
@@ -2,40 +2,36 @@
#include "primes.h"
static const unsigned int primes[] = {
- 11,
- 19,
+#define PRIME_SKIP_COUNT 3
+ 17,
37,
- 73,
- 109,
- 163,
- 251,
- 367,
- 557,
- 823,
- 1237,
- 1861,
- 2777,
- 4177,
- 6247,
- 9371,
- 14057,
- 21089,
- 31627,
- 47431,
- 71143,
- 106721,
- 160073,
- 240101,
- 360163,
- 540217,
- 810343,
- 1215497,
- 1823231,
- 2734867,
- 4102283,
- 6153409,
- 9230113,
- 13845163
+ 67,
+ 131,
+ 257, /* next from 2^8 */
+ 521,
+ 1031,
+ 2053,
+ 4099,
+ 8209,
+ 16411,
+ 32771,
+ 65537, /* next from 2^16 */
+ 131101,
+ 262147,
+ 524309,
+ 1048583,
+ 2097169,
+ 4194319,
+ 8388617,
+ 16777259, /* next from 2^24 */
+ 33554467,
+ 67108879,
+ 134217757,
+ 268435459,
+ 536870923,
+ 1073741827,
+ 2147483659,
+ 4294967291 /* previous from 2^32 */
};
static const unsigned int primes_count = N_ELEMENTS(primes);
@@ -44,9 +40,9 @@ unsigned int primes_closest(unsigned int
{
unsigned int i;
- for (i = 0; i < primes_count; i++)
- if (primes[i] >= num)
- return primes[i];
-
- return primes[primes_count - 1];
+ for (i = 31; i > PRIME_SKIP_COUNT; i--) {
+ if ((num & (1 << i)) != 0)
+ return primes[i - PRIME_SKIP_COUNT];
+ }
+ return primes[0];
}
diff -r 5b845716308d -r c55a66afddea src/tests/test-lib.c
--- a/src/tests/test-lib.c Mon Sep 01 15:02:22 2008 +0300
+++ b/src/tests/test-lib.c Mon Sep 01 15:04:00 2008 +0300
@@ -7,6 +7,7 @@
#include "bsearch-insert-pos.h"
#include "aqueue.h"
#include "network.h"
+#include "primes.h"
#include "priorityq.h"
#include "seq-range-array.h"
#include "str-sanitize.h"
@@ -449,6 +450,26 @@ static int cmp_int(const void *p1, const
return i1->num - i2->num;
}
+static void test_primes(void)
+{
+ unsigned int i, j, num;
+ bool success;
+
+ success = primes_closest(0) > 0;
+ for (num = 1; num < 1024; num++) {
+ if (primes_closest(num) < num)
+ success = FALSE;
+ }
+ for (i = 10; i < 32; i++) {
+ num = (1 << i) - 100;
+ for (j = 0; j < 200; j++, num++) {
+ if (primes_closest(num) < num)
+ success = FALSE;
+ }
+ }
+ test_out("primes_closest()", success);
+}
+
static void test_priorityq(void)
{
#define PQ_MAX_ITEMS 100
@@ -791,6 +812,7 @@ int main(void)
test_buffer,
test_mempool_alloconly,
test_net_is_in_network,
+ test_primes,
test_priorityq,
test_seq_range_array,
test_str_sanitize,
More information about the dovecot-cvs
mailing list