dovecot-1.2: primes_closest(): Use exponentially growing primes.

[dovecot at dovecot.org]

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,