This patch refactors the next_prime() function from hash.c, so that it can be
used in other hash table implementation. (Note that gl_anyhash_primes.h uses
another technique.)
2025-04-29 Bruno Haible <br...@clisp.org>
next-prime: Add tests.
* tests/test-next-prime.c: New file.
* modules/next-prime-tests: New file.
New module next-prime.
* lib/next-prime.h: New file, based on lib/hash.c.
* lib/next-prime.c: New file, based on lib/hash.c.
* modules/next-prime: New file.
* lib/hash.c: Include next-prime.h.
(is_prime, next_prime): Remove functions.
* modules/hash (Depends-on): Add next-prime.
>From 0b953ba82830f51ce9b939700705d238f9b0c0ba Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Wed, 30 Apr 2025 01:52:17 +0200
Subject: [PATCH 1/2] New module next-prime.
* lib/next-prime.h: New file, based on lib/hash.c.
* lib/next-prime.c: New file, based on lib/hash.c.
* modules/next-prime: New file.
* lib/hash.c: Include next-prime.h.
(is_prime, next_prime): Remove functions.
* modules/hash (Depends-on): Add next-prime.
---
ChangeLog | 10 +++++++++
lib/hash.c | 39 +-------------------------------
lib/next-prime.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++
lib/next-prime.h | 41 +++++++++++++++++++++++++++++++++
modules/hash | 1 +
modules/next-prime | 24 ++++++++++++++++++++
6 files changed, 133 insertions(+), 38 deletions(-)
create mode 100644 lib/next-prime.c
create mode 100644 lib/next-prime.h
create mode 100644 modules/next-prime
diff --git a/ChangeLog b/ChangeLog
index 6314db2094..60fbb0c0d0 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2025-04-29 Bruno Haible <br...@clisp.org>
+
+ New module next-prime.
+ * lib/next-prime.h: New file, based on lib/hash.c.
+ * lib/next-prime.c: New file, based on lib/hash.c.
+ * modules/next-prime: New file.
+ * lib/hash.c: Include next-prime.h.
+ (is_prime, next_prime): Remove functions.
+ * modules/hash (Depends-on): Add next-prime.
+
2025-04-29 Bruno Haible <br...@clisp.org>
New module hashkey-string.
diff --git a/lib/hash.c b/lib/hash.c
index 556c82d5b8..74d016fde3 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -27,6 +27,7 @@
#include "hash.h"
#include "bitrotate.h"
+#include "next-prime.h"
#include "xalloc-oversized.h"
#include <errno.h>
@@ -390,44 +391,6 @@ hash_string (const char *string, size_t n_buckets)
#endif /* not USE_DIFF_HASH */
-/* Return true if CANDIDATE is a prime number. CANDIDATE should be an odd
- number at least equal to 11. */
-
-static bool _GL_ATTRIBUTE_CONST
-is_prime (size_t candidate)
-{
- size_t divisor = 3;
- size_t square = divisor * divisor;
-
- while (square < candidate && (candidate % divisor))
- {
- divisor++;
- square += 4 * divisor;
- divisor++;
- }
-
- return (candidate % divisor ? true : false);
-}
-
-/* Round a given CANDIDATE number up to the nearest prime, and return that
- prime. Primes lower than 10 are merely skipped. */
-
-static size_t _GL_ATTRIBUTE_CONST
-next_prime (size_t candidate)
-{
- /* Skip small primes. */
- if (candidate < 10)
- candidate = 10;
-
- /* Make it definitely odd. */
- candidate |= 1;
-
- while (SIZE_MAX != candidate && !is_prime (candidate))
- candidate += 2;
-
- return candidate;
-}
-
void
hash_reset_tuning (Hash_tuning *tuning)
{
diff --git a/lib/next-prime.c b/lib/next-prime.c
new file mode 100644
index 0000000000..52cebc48d1
--- /dev/null
+++ b/lib/next-prime.c
@@ -0,0 +1,56 @@
+/* Finding the next prime >= a given small integer.
+ Copyright (C) 1995-2025 Free Software Foundation, Inc.
+
+ This file is free software: you can redistribute it and/or modify
+ it under the terms of the GNU Lesser General Public License as
+ published by the Free Software Foundation; either version 2.1 of the
+ License, or (at your option) any later version.
+
+ This file 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 Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+#include <config.h>
+
+/* Specification. */
+#include "next-prime.h"
+
+#include <stdint.h> /* for SIZE_MAX */
+
+/* Return true if CANDIDATE is a prime number. CANDIDATE should be an odd
+ number at least equal to 11. */
+static bool _GL_ATTRIBUTE_CONST
+is_prime (size_t candidate)
+{
+ size_t divisor = 3;
+ size_t square = divisor * divisor;
+
+ while (square < candidate && (candidate % divisor))
+ {
+ divisor++;
+ square += 4 * divisor;
+ divisor++;
+ }
+
+ return (candidate % divisor ? true : false);
+}
+
+size_t _GL_ATTRIBUTE_CONST
+next_prime (size_t candidate)
+{
+ /* Skip small primes. */
+ if (candidate < 10)
+ candidate = 10;
+
+ /* Make it definitely odd. */
+ candidate |= 1;
+
+ while (SIZE_MAX != candidate && !is_prime (candidate))
+ candidate += 2;
+
+ return candidate;
+}
diff --git a/lib/next-prime.h b/lib/next-prime.h
new file mode 100644
index 0000000000..c5ab78e318
--- /dev/null
+++ b/lib/next-prime.h
@@ -0,0 +1,41 @@
+/* Finding the next prime >= a given small integer.
+ Copyright (C) 1995-2025 Free Software Foundation, Inc.
+
+ This file is free software: you can redistribute it and/or modify
+ it under the terms of the GNU Lesser General Public License as
+ published by the Free Software Foundation; either version 2.1 of the
+ License, or (at your option) any later version.
+
+ This file 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 Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+#ifndef _GL_NEXT_PRIME_H
+#define _GL_NEXT_PRIME_H
+
+/* This file uses _GL_ATTRIBUTE_CONST. */
+#if !_GL_CONFIG_H_INCLUDED
+ #error "Please include config.h first."
+#endif
+
+#include <stddef.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+
+/* Round a given CANDIDATE number up to the nearest prime, and return that
+ prime. Primes lower than 10 are merely skipped. */
+extern size_t _GL_ATTRIBUTE_CONST next_prime (size_t candidate);
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_NEXT_PRIME_H */
diff --git a/modules/hash b/modules/hash
index da477d8887..fa1b9852a5 100644
--- a/modules/hash
+++ b/modules/hash
@@ -10,6 +10,7 @@ bitrotate
calloc-posix
free-posix
malloc-posix
+next-prime
bool
stdint-h
xalloc-oversized
diff --git a/modules/next-prime b/modules/next-prime
new file mode 100644
index 0000000000..259db8846e
--- /dev/null
+++ b/modules/next-prime
@@ -0,0 +1,24 @@
+Description:
+Finding the next prime >= a given small integer.
+
+Files:
+lib/next-prime.h
+lib/next-prime.c
+
+Depends-on:
+bool
+stdint-h
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += next-prime.h next-prime.c
+
+Include:
+"next-prime.h"
+
+License:
+LGPLv2+
+
+Maintainer:
+all
--
2.43.0
>From 0b9a45e16a6a7913edf818c79c834eb863b89ccd Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Wed, 30 Apr 2025 02:50:58 +0200
Subject: [PATCH 2/2] next-prime: Add tests.
* tests/test-next-prime.c: New file.
* modules/next-prime-tests: New file.
---
ChangeLog | 4 ++++
modules/next-prime-tests | 9 ++++++++
tests/test-next-prime.c | 46 ++++++++++++++++++++++++++++++++++++++++
3 files changed, 59 insertions(+)
create mode 100644 modules/next-prime-tests
create mode 100644 tests/test-next-prime.c
diff --git a/ChangeLog b/ChangeLog
index 60fbb0c0d0..ee6295754d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
2025-04-29 Bruno Haible <br...@clisp.org>
+ next-prime: Add tests.
+ * tests/test-next-prime.c: New file.
+ * modules/next-prime-tests: New file.
+
New module next-prime.
* lib/next-prime.h: New file, based on lib/hash.c.
* lib/next-prime.c: New file, based on lib/hash.c.
diff --git a/modules/next-prime-tests b/modules/next-prime-tests
new file mode 100644
index 0000000000..cab1e5227d
--- /dev/null
+++ b/modules/next-prime-tests
@@ -0,0 +1,9 @@
+Files:
+tests/test-next-prime.c
+tests/macros.h
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-next-prime
+check_PROGRAMS += test-next-prime
diff --git a/tests/test-next-prime.c b/tests/test-next-prime.c
new file mode 100644
index 0000000000..4a6a25e054
--- /dev/null
+++ b/tests/test-next-prime.c
@@ -0,0 +1,46 @@
+/* Test of next_prime() function.
+ Copyright (C) 2025 Free Software Foundation, Inc.
+
+ This program 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.
+
+ This program 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 this program. If not, see <https://www.gnu.org/licenses/>. */
+
+/* Written by Bruno Haible <br...@clisp.org>, 2025. */
+
+#include <config.h>
+
+/* Specification. */
+#include "next-prime.h"
+
+#include "macros.h"
+
+int
+main ()
+{
+ ASSERT (next_prime (1) == 11);
+ ASSERT (next_prime (3) == 11);
+ ASSERT (next_prime (7) == 11);
+ ASSERT (next_prime (10) == 11);
+ ASSERT (next_prime (11) == 11);
+ ASSERT (next_prime (12) == 13);
+ ASSERT (next_prime (640) == 641);
+
+ ASSERT (next_prime (9551) == 9551);
+ ASSERT (next_prime (9552) == 9587);
+
+ ASSERT (next_prime (43331) == 43331);
+ ASSERT (next_prime (43332) == 43391);
+
+ ASSERT (next_prime (1000000) == 1000003);
+
+ return test_exit_status;
+}
--
2.43.0
